Как я могу получить образцы, обнаруженные bzip2? (или любой другой алгоритм сжатия)

Question

У меня есть огромный файл, состоящий из символов «0», «1», «2», «3».Нет пробелов, ничего больше.Просто эти 4 персонажа.Я использовал bzip2, чтобы сжать его, и размер файла уменьшился с X до 0,05 * X.Я хотел бы знать, какие строки / шаблоны были найдены bzip2 для получения сжатой версии файла (например, 0123213232, 0123121212222112 и т. Д.).Есть ли простой способ извлечь эту информацию либо из фактического файла bz2, либо запустив bzip2 с какой-либо специальной опцией командной строки?

Если вы знаете ответ для какой-либо другой существующей программы сжатия, я также будуинтересно услышать об этом.

Спасибо за любую помощь.

Best, Surikator.

Answer 1

Bzip2 использует преобразование Берроуза-Уилера для преобразования повторяющихся последовательностей байтов в последовательности одного и того же байта обратимым образом. Затем он использует алгоритм move-to-front для преобразования повторяющихся байтов в нулевые последовательности. После этого он использует кодирование Хаффмана для назначения более коротких символов более частым байтам (возможно, нулям). Вы можете найти более подробную информацию на странице Википедии .

Answer 2

преобразование Барроуза-Уилера

Это также называется сортировка блоков . Если вам не нравится читать Википедию, то читайте Математические основы информатики 1999: http://books.google.ee/books?id=OcJjpqAi15EC&pg=PA34&lpg=PA34&dq=mathematica+Burrows%E2%80%93Wheeler+transform&source=bl&ots=KaOOIPJcKC&sig=5PzHG9UQeg3opr1FUMq8mPAxfn4&hl=et&ei=Y6vPTLfVFsqCOozvvPcE&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBMQ6AEwAA#v=onepage&q&f=false

код Хаффмана

Для ввода: "this is an example of a huffman tree". Двоичное дерево, как это, построено:

Затем используется для построения таблицы кодирования:

 Char ' ' nr(32)    | binary:00100000 | new binary:111
 Char 'a' nr(97)    | binary:01100001 | new binary:001
 Char 'e' nr(101)   | binary:01100101 | new binary:000
 Char 'f' nr(102)   | binary:01100110 | new binary:1101
 Char 'h' nr(104)   | binary:01101000 | new binary:1100
 Char 'i' nr(105)   | binary:01101001 | new binary:1001
 Char 'l' nr(108)   | binary:01101100 | new binary:01101
 Char 'm' nr(109)   | binary:01101101 | new binary:1000
 Char 'n' nr(110)   | binary:01101110 | new binary:1011
 Char 'o' nr(111)   | binary:01101111 | new binary:01100
 Char 'p' nr(112)   | binary:01110000 | new binary:01111
 Char 'r' nr(114)   | binary:01110010 | new binary:01110
 Char 's' nr(115)   | binary:01110011 | new binary:1010
 Char 't' nr(116)   | binary:01110100 | new binary:0101
 Char 'u' nr(117)   | binary:01110101 | new binary:01001
 Char 'x' nr(120)   | binary:01111000 | new binary:01000

Новый двоичный файл может быть прочитан, только если у вас есть такое же дерево, так что оно также поддерживается в выводе. Также длина данных хранится, потому что сумма новых двоичных файлов не является полным байтовым номером.

Открытое программное обеспечение

Вы можете просто прочитать

• справочные страницы: http://www.bzip.org/1.0.5/bzip2-manual-1.0.5.html
• или источник: http://www.bzip.org/1.0.6/bzip2-1.0.6.tar.gz

Answer 3

bzip2 не имеет возможности для этого, и он не работает точно так, как я думаю, вы думаете, что это работает.В любом случае, вы можете найти код для различных частей в алгоритме.Как упомянул @stribika, он использует Burrows-Wheeler и переходит к передним алгоритмам, прежде чем прокачивать его через кодировщик Хаффмана.Google должен получить некоторые результаты для преобразования Уилера Берроу на выбранном вами языке.

Однако, исходя из того, что вы ищете, я думаю, что вам нужно больше кодировщика в стиле словаря.Возможно, вас заинтересует алгоритм LZW:

http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch

Он создаст словарь строк, как вы показали.