Как эффективно распаковать файл, закодированный Хаффманом
Я нашел много вопросов, задающих это, но некоторые объяснения были очень трудны для понимания, и я не мог понять концепцию, как эффективно распаковать файл.
Я нашел эти связанные вопросы:
Код Хаффмана с таблицей поиска
Как быстро декодировать код Хаффмана?
Но я не понимаю объяснения. Я знаю, как регулярно кодировать и декодировать дерево Хаффмана. Прямо сейчас в моей программе сжатия я могу записать любую следующую информацию в файл
условное обозначение
код Хаффмана (длинный без знака)
длина кода Хаффмана
Я планирую получить текстовый файл, разделить его на небольшие текстовые файлы и сжать каждый по отдельности, а затем распаковать этот файл, отправив все небольшие сжатые файлы с соответствующей таблицей поиска (не знаю, как выполнить эту часть), чтобы графический процессор Nvidia, чтобы попытаться распаковать файл параллельно, используя какую-то таблицу поиска.
У меня есть 3 вопроса:
Какую информацию я должен записать в файл в заголовке, чтобы построить таблицу поиска?
Как мне воссоздать эту таблицу из файла?
Как использовать его для быстрого декодирования файла, закодированного Хаффманом?
Решение
Не пытайтесь писать сами, если это не дидактическое упражнение. использование Zlib, LZ4, или любую из нескольких других бесплатных библиотек сжатия / распаковки, которые гораздо лучше протестированы, чем все, что вы сможете сделать.
Вы говорите только о кодировании Хаффмана, указывая на то, что вы получите только небольшую часть доступного сжатия. Большая часть сжатия в упомянутых библиотеках происходит из соответствующих строк. Посмотрите «LZ77».
Что касается эффективного декодирования Хаффмана, вы можете посмотреть, как это делает zlib’s inflate. Он создает таблицу поиска для наиболее значимых девяти бит кода. Каждая запись в таблице имеет либо символ и количество битов для этого кода (меньше или равно девяти), либо, если предоставленные девять битов являются префиксом более длинного кода, эта запись имеет указатель на другую таблицу для разрешения остальной код и количество битов, необходимых для этой вторичной таблицы. (Существует несколько таких вторичных таблиц.) Если для длины кода меньше девяти, существует несколько записей для одного и того же символа. На самом деле, 29-п несколько записей для n-битного кода.
Таким образом, для декодирования вы получаете девять битов от входа и получаете запись из таблицы. Если это символ, вы удаляете количество битов, указанное для кода, из вашего потока и испускаете символ. Если это указатель на вторичную таблицу, то вы удаляете из потока девять битов, получаете количество битов, указанное в таблице, и просматриваете его там. Теперь вы определенно получите символ для выброса и количество оставшихся битов для удаления из потока.
Другие решения