Занимательная информатика

[spamsink]

Берём большой файл со списком русских слов, включая словоформы. Он в кодировке Win-1251, а не в Unicode - или чтобы короче был, или потому что некоторые операционные системы до сих пор тупят. Его длина - 18265150 байт.

Чтобы смотреть на него в линуксе, делаем, как указано в инструкции,

iconv -f WINDOWS-1251 -t UTF-8 russian.txt > russian.utf-8

и получаем файл длиной 34993984.

Насмотревшись на этот файл, решаем его не выбрасывать, а сжать, попробовав оба варианта файла и две программы сжатия - gzip и bzip2, обе с ключом -9.

Итого, ls -lSr russian*

-rw-r--r-- 1 spamsink users  3814446 Jul 22 19:40 russian.txt.gz
-rw-r--r-- 1 spamsink users  4164422 Jul 22 18:27 russian.utf-8.bz2
-rw-r--r-- 1 spamsink users  4326903 Jul 22 18:25 russian.txt.bz2
-rw-r--r-- 1 spamsink users  4659786 Jul 22 19:41 russian.utf-8.gz
-rw-r--r-- 1 spamsink users 18265150 Jul 22 19:39 russian.txt
-rw-r--r-- 1 spamsink users 34993984 Jul 22 19:40 russian.utf-8

Меня позабавило не то, что russian.txt.gz самый маленький - это более или менее объяснимо, а то, что russian.txt.bz2 больше, чем russian.utf-8.bz2. Вот это я навскидку объяснить не могу.

Comments

[lxe]

Это лишний раз подтверждает, что если архиватору, как и человеку, давать передышку, его средняя производительность возрастет.

[spamsink]

:) На самом деле Хаффменовское кодирование всему виной.

[sassa_nf]

16-bit Huffman codes?..

[spamsink]

В смысле?

Нет, дело в изменении распределения символов: если частоты самых частых символов близки к степеням двойки, то кодирование будет более эффективным, а если далеки, то менее. Например, возьмём по 1 MB символов a, b, c. В этом случае их частоты будут 1/3 у каждого, хаффменовский код одного будет однобитный, двух других - двухбитный, итого 5 Mb. С другой стороны, если взять 1.6 MB a и по 0.8 MB b и c, то коды их будут такие же, их суммарная длина 3.2 MB, а результат сжатия - 4.8 Mb.

[sassa_nf]

I don't get it how in your opinion the frequency of a could change.

My thinking was: if bz2 is looking for 2-byte sequences, then win-1251 has more unique 2-byte sequences than utf-8.

[spamsink]

The BWT algorithm does not look for any particular sequences; it performs an ingenious form of reversible sorting of the rotations of the input string, so that all characters preceding similar contexts are grouped together (reading an article about the algorithm soon after it first became known, in 1994, has caused me an "intellectual orgasm") which causes a lot of character repetitions; then a "move-to-front" transform, so that repeated characters are encoded as zeros, the next previously seen character is encoded as 1, etc.; then a run length encoding pass, then a Huffman coding pass.
As a result, most utf-8 first bytes would be grouped together and will shrink to almost nothing after MTF+RLE, which should have had almost no negative effect on the compression rate, but by themselves they could not bring about any positive effect, because extra bytes are extra bytes.

But, that perturbs the relative frequencies of the byte values, which may be enough to change the Huffman encoding, making it closer to the optimal, if it happened that in compressing of the original file the encoding was far from the optimal.

[sassa_nf]

Interesting