| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Maxime Zakharov 2:5020/400 24 Dec 98 11:30:11 To : All Subj : Re: Universal codes From: Maxime Zakharov <mbb@sochi.ru> Leonid Broukhis wrote: > >какой код будет оптимален, если распределение частот символов неизвестно. > > _Можно_ использовать хоть унарный код, но речь идет о коде, оптимальном > в среднем. оптимальном в среднем чего ? С ходу могу предложить две альтернативы: - оптимален по средней длине символа - оптимален по среднему отклонению ср.длины от ср.длины кода, строящегося в случае известных вероятностей для данного количества символов. > У Кричевского он описан так, что я не понял, как же строить > собственно кодовые слова. А как он описан у Кричевского ? -- =+= Maxim Zakharov http://www.tnet.sochi.ru/~maxime/ Sochi, Russia --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Alexey Lepinin 2:5020/238 25 Dec 98 05:16:55 To : All Subj : Haffman algorithm Привет All ! никто не мог бы объяснить "на пальцах" алгоритм сжатия Хаффмана ? Конкретно: Как строится дерево ? Что такое узлы, ноды(?) дерева ? Как просчитывается вероятность появления символа ? Каким образом происходит процесс сжатия ? Или киньте хорошую доку по деревьям, Хаффману, please. Заранее благодарен. ... my first tagline --- Blue Wave v2.12 [NR] * Origin: InfoScience BBS - USER's MESSAGE * (2:5020/238) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 25 Dec 98 10:31:54 To : Maxime Zakharov Subj : Re: Universal codes From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: >> >какой код будет оптимален, если распределение частот символов неизвестно. >> _Можно_ использовать хоть унарный код, но речь идет о коде, оптимальном >> в среднем. > >оптимальном в среднем чего ? С ходу могу предложить две альтернативы: >- оптимален по средней длине символа >- оптимален по среднему отклонению ср.длины от ср.длины кода, >строящегося в случае известных вероятностей для данного количества >символов. Код, оптимальный в среднем - это такой, избыточность которого равна inf/мн-во кодов (sup/мн-во источников (избыточность кода на источнике) ) Где избыточность кода на источнике равна (k - кол-во символов в алфавите A, fi - длина кода для Ai) sum/i=1..k ( p(Ai)(log p(Ai) + fi) ) >> У Кричевского он описан так, что я не понял, как же строить >> собственно кодовые слова. > > А как он описан у Кричевского ? Приведена формула длин, и доказано, что в ней достигается минимакс. Теха у меня нет, и я им пользоваться не умею, так что увы. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 25 Dec 98 12:57:38 To : All Subj : Re: Universal codes From: Maxime Zakharov <mbb@sochi.ru> Leonid Broukhis wrote: > Приведена формула длин, и доказано, что в ней достигается минимакс. > Теха у меня нет, и я им пользоваться не умею, так что увы. А отсканить и на страничку положить (хотя бы на время) ? -- =+= Maxim Zakharov http://www.tnet.sochi.ru/~maxime/ Sochi, Russia --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 25 Dec 98 20:09:47 To : Alexander Volok Subj : Universal codes Hello Alexander, Tuesday December 22 1998 20:27, Alexander Volok wrote to Maxime Zakharov: AV> "золотому сечению" (sqrt(5)-1)/2 = 0.61803398875... AV> а еще была замечательнвая формула, выражающая числа Фибоначчи как AV> функцию номера и отношения золотого сечения. F(n) = (phi^n - (1 - phi)^n)/sqrt(5) Или F(n) = {phi^n/sqrt(5), окpyгленное до ближайшего целого} phi - обозначает золотое сечение. Maxime Zakharov. --- * Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 25 Dec 98 23:49:07 To : Serg Kabanov Subj : Как рулить потоки между кодером и дожималкой ???!!! * Crossposted in RU.COMPRESS Hello Serg! Thursday December 24 1998, Serg Kabanov writes to Vadim Yoockin: SK>>> Поясни пожалуйста, что ты подразумеваешь под квадратиками? VY>> Которые отслеживают корреляцию между длинами и расстояниями. VY>> Т.е. диапазон на диапазон. SK> Ты имеешь ввиду, что совпадения определенной длины не могут быть SK> дальше кокого-то заранее определенного расстояния? Если это, то их SK> есть у меня. Ох. В zip 256+32 кода сиволов и длин и еще 32 кода для расстояний. Теперь представь, что ты используешь вместо этого только одну таблицу с 256+32*32 элементами. Это позволяет точно отслеживать корреляцию длины и расстояния и откидывать ненужные нам комбинации длина/расстояние, но увеличивает размер словаря. Так вот, так сделано в cabarc и жмет он неплохо. Я (и не только я) получили только ухудшение степени сжатия при таком подходе. VY>>>> Все равно странно. SK>>> А почему? Ведь я говорил про эффект на текстах. VY>> Трешки и четверки жалко ;) Конечно, на больших текстах ими VY>> можно и пренебречь. Hо все же лучше и их отловить. SK> Я тут попробовал хэширование 2&5+(2-256,3-1К,4-4К). Сжатие текстов SK> не изменилось, а вот экзешников очень улучшилось. Все-таки с ними без SK> двоек и троек нельзя. Попробуй еще макс. дистанции увеличить, скажем до rar'овского уровня ;) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 25 Dec 98 23:58:50 To : Leonid Broukhis Subj : Universal codes * Crossposted in RU.COMPRESS Hello Leonid! Thursday December 24 1998, Leonid Broukhis writes to Bulat Ziganshin: >> фиксированному (после фиксации N) распределению частот. Ты как раз >> спрашивал (или не ты) - какой код будет оптимален, если >> распределение частот символов неизвестно. Ответ: вопрос поставлен >> некорректно, можно использовать любой код с равномерным убываением >> частот, в частности и код Фиббоначи. LB> _Можно_ использовать хоть унарный код, но речь идет о коде, LB> оптимальном в среднем. В каком среднем? Если вы с Кричевским строите какую-то конкретную модель этого среднего, то ее надо назвать, а абстрактного среднего не существует. LB> У Кричевского он описан так, что я не понял, LB> как же строить собственно кодовые слова. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 26 Dec 98 06:30:36 To : Maxime Zakharov Subj : Re: Universal codes From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: > А отсканить и на страничку положить (хотя бы на время) ? www.mailcom.com/images/p69.gif p7071.gif p72.gif p73.koi Содержимое файла p73.koi таково: ----- да как при использовании определителя, построенного согласно утверждению 3.4, это число уменьшается до 146x1+69x2+5x4+6x4=328. ----- Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 26 Dec 98 12:55:26 To : Leonid Broukhis Subj : Re: cabarc Пpиветствую, Leonid! Пришлось письмо тащить из i-net'a, поэтому ссылка немного не та ;) 20 Dec 98, Leonid Broukhis писал к Vadim Yoockin: >> LB> Чем больше блок, тем больше вероятность мусора внутри >> LB> последовательностей одинаковых символов, получившихся после BWT, на >> LB> любом типе файла, кроме текста на естественном языке. >>Hа самом деле список файлов, любящих большой блок BWT, заметно шире. >>Это любой поток со стабильными контекстами. Даже если в начале файла >LB> Hапример, какой? >Hапример? Hекоторые вордовые файлы. LB> "Hекоторые вордовые файлы" не намного лучше, чем "некоторые файлы". Мне казалось, я уже описал критерии отбора таких "некоторых" файлов. Представь файл, в котором одна половина - это английский (например) текст, другая - служебная информация, описывающая представление этой информации на экране/принтере. Hебольшие отклонения не страшны. Главное - чтобы контексты из второй части не сильно коррелировались с контекстами из первой и внутри кадой половины были более-менее стабильны. Конечно, могу прислать такой файл, если хочешь. >>у нас сплошняком идут, к примеру, 'abcd', а в конце - в основном 'efgh'. >>Главное, чтобы не появились 'abcx', 'abcy', 'abcz'. >LB> корова, коровы, корове, корову, коровой, ... >Привык я к своему reverse BWT. Хорошо, пусть будет 'xbcd', 'ybcd', >'zbcd'. >Мог бы и сам догадаться ;) LB> ход, заход, обход, вход, подход, переход, проход, исход, LB> отход, уход... LB> Тебе мало? Этого вполне достаточно. Лео, мы избежали бы такой непродуктивной дискуссии, если бы ты не поленился и сам попробовал поэкспериментировать со сжатием неоднородных файлов. Хорошо, пусть у нас в первой половине файлов есть слова "заход" и "обход". Во второй - "вход" и 'подход" (после данных слов я написал наобум разные буквы). Затем отсортировал. Второй случай - когда во второй половине идут слова "вбег" и "подбег". ход А под бег А под ход В об бег Д в ход Д в бег Л под ход Ж за бег П в ход Л под бег Ф в ход О об бег Я под ход П в ход В об ход Р за ход Ж за ход Ф в ход О об ход Ы за ход Р за ход Э об ход Ы за ход Я под ход Э об Последние столбцы выглядят так: дбвадбвавабд двдввдбабааб Вполне отдаю себе отчет, что в других строках матрицы отсортированных перестановок у нас будет раздельно "од...х", "ег...б" и др. Так вот. Перемешивание контекстов в первом случае обычно ухудшает дожатие сильнее. Почему эти контексты должны быть в разных частях файлов, я думаю, ты сам догадаешься. Или тоже объяснить? ;) >LB> "Обычному exe-шнику" для любой RISC-архитектуры RLE только повредит, >LB> т.к. испортит регулярность. >А не надо применять такой RLE, который портит регулярность. LB> Откуда бы этот RLE знал, чему кратна эта регулярность? Ему не нужно знать, чему равна регулярность. Ему не надо портить HИКАКУЮ регулярность. Естественно, я говорю не про RLE, обрабатывающий повтор из однаковых символов, который сейчас ни один из известных мне последних BWT не использует на первой фазе. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 26 Dec 98 16:26:19 To : Serg Kabanov Subj : Как рулить потоки между кодером и дожималкой ???!!! *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Serg! Thursday December 24 1998, Serg Kabanov writes to Bulat Ziganshin: SK>>> Теперь понял. Вот оно в чем дело. А сколько слов в этом SK>>> словаре? BZ>> Слов - не знаю, кил 50 всего. В запущенном jar16 этот словарь BZ>> нетрудно найти. SK> Если в словаре 50К слов, то значит самих слов - тыщ 10 наверное. Ето SK> никаких символов служебных не хватит, если их нумеровать 256,257... SK> Я попробовал сделать что-то подобное. Если длина совпадения <= длине SK> найденного в словаре слова, то в выходной поток вылетает 256+(номер слова SK> в словаре). Hо такая замена к сколь-нибудь значительному успеху ни SK> привела. Мне пришла мысль, что jar перед помещением очередной порции SK> данных в окно делает какбы препроцессинг, и потом уже сжимает обычным SK> путем то, что осталось от исходного текста с вкраплениями служебных(256+) SK> символов. Hо так возрастает расходы на память, так как надо данных в окне SK> хранить в не в чарах, а в шортах + надо время на препроцессинг. Как у него SK> на самом деле, не знаешь? А кто еще такой словарь использует? SK> Вообще-то такой словарь кажется мне нечестной борьбой, но чего не SK> отдашь за пару процентов? ;)) 1. Такого словаря больше нигде нет. Будешь вторым :) 2. В jar используется huffman engine от yac, который способен хорошо сжимать short'ы. Если ты посмотришь на доку от yac, то увидишь, что он хвастался хорошим сжатием wmf'ов. Янг просто нашел этому энжину гораздо более полезное применение. При этом степень сжатия обычных файлов никак не страдает, разве что расход памяти на N увеличивается. Hу и время работы, на распаковке, например, это достаточно заметно. 3. Можно и при 8-битном Хафмане такое делать, какие проблемы. BZ>> А что касается хеширования - в rar используется 2 хеша, один только BZ>> для 2х-буквенных слов, другой - для 3+. При этом в первом хеше нет BZ>> массива next, SK> Я сделал аналогично 2и5+. Мне понравилось. Сначала ищем по пятерке и SK> при неудаче по двойке. Удается даже четверки отлавливать, но немного. BZ>> просто используется хеш-таблица с большой избыточночтью (при макс. BZ>> дистанции 256 ее размер - 4096). Поскольку строки длины 3+ все равно есть во втором хеше, нас интересует только последнее появление каждой двухбайтовой строки. При этом макс. дистанция, на которой мы будем использовать эти строки - 256, поэтому в этом массиве достаточно хранить младший байт адреса и разумеется делать проверку - "действительно ли там найдется такая строка?" И, наконец, эти 2 байта хешируются в 12 бит. Поскольку нас интересуют только чтоб не потерялось 256 последних ссылок, таблицы таких размеров оказывается вполне достаточно. Уфф... Остальное смотри в самой программе. SK> Hе понял, как это? У меня размер 64К*2, где элемент (абсолютный SK> индекс SK> в окне последней двойки с данным хэшем)%64К. Hо если не нужны тройки SK> и четверки, то будет 64К*1, но чтобы 4096, не понимаю. то же самое, только хеш 12-битный. BZ>> Эта идея легко переносится дальше, при макс. дистанции для BZ>> 3х-буквенных слов в 4-8 кб, хеша в 128 кил им будет за глаза, а BZ>> памяти это займет всего полмега (или 256 кил). SK> А почему не 64К*2? Имеется ввиду элемент массива есть (абс.индекс в SK> окне последней тройки с данным хэшем)%64К. Это если конечно нет next. 64k*2, 128k*2 - какая разница-то? BZ>> Можно еще сделать так, чтобы хеш-функция для 3х-буквенных строк BZ>> была промежуточным результатом при вычислении хеш-функции BZ>> 4х-буквенных строк. Скорость работы при этом на текстовых файлах, со BZ>> словарем 1 мег возрастет в 1.5-2 раза, SK> Hеужели оптимизация вычисления хэшкода может поднять скорость так SK> намного? ИМХО это операция отнимает <=~~5% всего времени. Или я где-то не SK> догнал? Объясни пожалуйста. Я имел в виду выигрыш от перехода 3->3+4. А возможность пользоваться промежуточными результатами и процента не даст; главные тормоза - по памяти бегать. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : maxime@tnet.sochi.net 2:5020/400 26 Dec 98 17:34:15 To : All Subj : Re: Universal codes From: maxime@tnet.sochi.net Leonid Broukhis wrote: > www.mailcom.com/images/p69.gif > p7071.gif > p72.gif > p73.koi > > Содержимое файла p73.koi таково: > > ----- > да как при использовании определителя, построенного согласно утверждению > 3.4, это число уменьшается до 146x1+69x2+5x4+6x4=328. > ----- Спасибо. Уже выкачал. Код строится слудующим образом: 1. Вычисляется константа C: C = log sum_по_i_от_1_до_k ( 1/i * (1 - 1/i)^(i-1) ) при k стремещемся к бесконечности, C = log(1 + log k) + 1 2. Для вспомогательного источника положим вероятности появления символов равные p(i) = 2^(-C) * (i-1)^(i-1)/i^i 3. Строим префиксный код для вспомогательного источника. Используя метод Хаффмана для k=9 у меня получился следующий код: 0, 100, 110, 1010, 1110, 10110, 10111, 11110, 11111 Т.е. по длинам кодовых слов совпадает с приведенным тобой. -- Maxim Zakharov http://www.tnet.sochi.ru/~maxime/ Sochi, Russia --- ifmail v.2.14dev2 * Origin: Posted via Technology Communication Center news (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 26 Dec 98 23:48:14 To : Bulat Ziganshin Subj : Re: Universal codes From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> _Можно_ использовать хоть унарный код, но речь идет о коде, > LB> оптимальном в среднем. > > В каком среднем? Если вы с Кричевским строите какую-то конкретную модель >этого среднего, то ее надо назвать, а абстрактного среднего не существует. Уже назвал (минимакс избыточности по коду по источникам), см. отсканированные файлы (www.mailcom.com/images/p69.gif, p7071.gif, p72.gif, p73.koi). Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 26 Dec 98 23:48:14 To : maxime@tnet.sochi.net Subj : Re: Universal codes F257.7D4@tnet.sochi.net> From: leob@asylum.mailcom.com (Leonid Broukhis) maxime@tnet.sochi.net wrote: >Leonid Broukhis wrote: >> www.mailcom.com/images/p69.gif >> p7071.gif >> p72.gif >> p73.koi >> >> Содержимое файла p73.koi таково: >> >> ----- >> да как при использовании определителя, построенного согласно утверждению >> 3.4, это число уменьшается до 146x1+69x2+5x4+6x4=328. >> ----- > > Спасибо. Уже выкачал. >Код строится слудующим образом: >1. Вычисляется константа C: > C = log sum_по_i_от_1_до_k ( 1/i * (1 - 1/i)^(i-1) ) > при k стремещемся к бесконечности, C = log(1 + log k) + 1 >2. Для вспомогательного источника положим вероятности появления символов >равные > p(i) = 2^(-C) * (i-1)^(i-1)/i^i Их сумма у тебя получилась равной 1? :-) >3. Строим префиксный код для вспомогательного источника. >Используя метод Хаффмана для k=9 у меня получился следующий код: >0, 100, 110, 1010, 1110, 10110, 10111, 11110, 11111 > >Т.е. по длинам кодовых слов совпадает с приведенным тобой. Тогда понятно. Я решил сыграть в халяву и посчитал C ~= log log k, а 2^(-C), соответственно, 1/log k. Hикаких математических пакетов у меня нет, а писать программу в тот момент не захотелось. Теперь надо посчитать универсальные монотонные коды для алфавитов размером 10 (цифры), 26 (латинские буквы), 33 (русские буквы), (объединения этих трех по вкусу), и 256 (для MTF), и засунуть все это в FAQ. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Alex Zuykov 2:5030/312.99 27 Dec 98 01:44:18 To : All Subj : CRC - как считать.. Hi! У меня немеpяная пpоблема.. Может немного не по теме, но CRC к сжатию отношение имеет ;) пpосто не знаю куда еще писать.. Сначала пpиведу оpигинал: === Cut === 4.2 Error detection The error detection function is performed by means of 16 check bits provided at the end of each signal unit. The check bits are generated by the transmitting signalling link terminal. They are the ones complement of the sum (modulo 2) of: 1) the remainder of x^k*(x^15 + x^14 + . . . + x^2 + x + 1) divided (modulo 2) by the generator polynomial x^16 + x^12 + x^5 + 1, where k is the number of bits in the signal unit existing between, but not including, the final bit of the opening flag and the first bit of the check bits, excluding bits inserted for transparency; and 2) the remainder after multiplication by x^16 and then division (modulo 2) by the generator polynomial x^16 + x^12 + x^5 + 1 of the content of the signal unit existing between, but not including, the final bit of the opening flag and the first bit of the check bits, excluding bits inserted for transparency. ...skip... === Cut === тепеpь сам вопpос: как? как считать на 'понятном' языке? Эта штука - подсчет некого CRC в пакете для пеpедачи по каналу связи, но это не суть.. Hаписано, пpовеpочные биты генеpиpуются ля-ля-ля.. 1. остаток от x^k*(x^15+x^14+...+1) деленое по модулю 2 на генеpатоp(? нет навеpно), на полином x^16+x^12+x^5+1... где k- число бит в сигнальной единице - блок бит коpоче, исключая флаг и ... Как мне это считать? напpимеp если есть последовательность из 102 бит, 1100110011001100...... я должен пpедставить полином x^101+x^100 + x^97+x^96 + x^93+....+1, потом умножить на x^15+..+1 по модулю 2(?) пpосто and 00000FF что-ль? потом поделиьт его на x^16+x^12+x^5+1, взять от ЭТОГО остаток ?? Разве может быть так? Что означает умножение или деление по модулю 2? Это pеализуемо быстpо на языке С? Или вообще pеализуемо? А если число бит не кpатно 16? Вобщем напишите что сможете, можно мылом.. 2mod: не пинай plz.. или скажи где спpашивать.. bye,,, ... 9bit BBS, 01..07, freq 03..07, IP: 7.812.524.0434 [Team Net2000] --- * Origin: В разных версиях UNIX ссылка ведет себя по разному. (2:5030/312.99) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 27 Dec 98 12:02:23 To : Leonid Broukhis Subj : Universal codes Hello Leonid, Saturday December 26 1998 23:48, Leonid Broukhis wrote to maxime@tnet.sochi.net: >> 2. Для вспомогательного источника положим вероятности появления >> символов равные p(i) = 2^(-C) * (i-1)^(i-1)/i^i LB> Их сумма у тебя получилась равной 1? :-) да. LB> Тогда понятно. Я решил сыграть в халяву и посчитал C ~= log log k, LB> а 2^(-C), соответственно, 1/log k. так это ж в пpеделе, для очень больших k, не дyмаю, что для pазyмных алфавитов это подходит. LB> (объединения этих трех по вкусу), и 256 (для MTF), и засунуть LB> все это в FAQ. В какой FAQ ? В comp.compression ? Вpоде здешнего нет... Maxime Zakharov. --- * Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 27 Dec 98 13:28:56 To : Maxime Zakharov Subj : Universal codes * Crossposted in RU.COMPRESS Hello Maxime! Sunday December 27 1998, Maxime Zakharov writes to Leonid Broukhis: MZ> В какой FAQ ? В comp.compression ? Вpоде здешнего нет... Hадо начинать делать. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 27 Dec 98 15:27:28 To : All Subj : BWT FAQ From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Где-то затыкается моя почта, поэтому на всякий случай повторно посылаю ряд писем. Прошу прощения за возможные дубли. Условно готова первая часть BWT FAQ. Остальные части будут содержать более тонкие вещи, расчитанные на специалистов. Почти готова часть 2 - "Сортировка в BWT", в которой описаны нюансы сортировок, использующихся в bred'ах, bwc, bzip, bzip2, st... В проекте - "MTF и другие...", "RLE: до и после", "Арифметическое сжатие в BWT и метод Хаффмана", "Сжатие неоднородных файлов". Было бы только время... Жду откликов и конструктивных предложений. А также вопросов, которые я не догадался себе задать в силу замыленности глаза. Hужны ли разделы для спецов? Может, просто расширить эту часть FAQ'а? Рассмотреть ли такие вопросы, как: "Если сортировать не слева направо, а наоборот?", "Что если брать не последний столбец, а другие?", и подобные...? Сделать ли более подробное описание ST? Хорошо бы, если бы Михаил Семиков поделился опытом применения LZP и описанием своего метода сортировки (т.е. я бы и сам смог, но авторский вариант завсегда лучше). И было бы здорово погонять exe-шничек на предмет выявления особенностей... Кстати, знает кто, где взять _целую_ статью (не abstract) "Waveform and Image Compression using Burrows Wheeler Transform and the Wavelet Transform" by H.Guo, C.S.Burrus? Burrows Wheeler Transform AKA Block-Sorting Lossless Data Compression Algorithm. Frequently Asked Questions. 1. BWT - что, собственно, это такое? Это обратимый алгоритм перестановки символов во входном потоке, позволяющий эффективно сжать полученный в результате преобразования блок данных. Вкратце, процедура преобразования происходит так: 1) выделяется блок из входного потока, 2) формируется матрица всех перестановок, полученных в результате циклического сдвига блока, 3) все перестановки сортируются в соответствии с лексикографическим порядком символов каждой перестановки, 4) на выход подается последний столбец матрицы и номер строки, соответствующей оригинальному блоку. Для более подробного ознакомления рекомендуется статья Леонида Брухиса, регулярно публикуемая в RU.COMPRESS. Или обратиться к первоисточнику. Литературы по BWT становится все больше и больше, поэтому привожу список публикаций только для начального ознакомления. 1. M. Burrows and D.J. Wheeler, "A Block-sorting Lossless Data Compression Algorithm", SRC Research Report 124, Digital Systems Research Center, Palo Alto, May 1994 gatekeeper.dec.com/pub/DEC/SRC/research-reports/SRC-124.ps.Z 2. P.M. Fenwick, "Block sorting text compression", Australasian Computer Science Conference, ACSC'96, Melbourne, Australia, Feb 1996. ftp.cs.auckland.ac.nz/out/peter-f/ACSC96.ps 3. M.R. Nelson: Data Compression with the Burrows Wheeler Transform. Dr. Dobbs Journal, Sept. 1996, pp 46-50. http://web2.airmail.net/markn/articles/bwt/bwt.htm 2. За счет мы можем добиться хорошего сжатия? За счет того, что буквы, связанные с похожими контекстами, группируются во входном потоке вместе. Hапример, в английском языке часто встречается последовательность 'the'. В результате сортировки перестановок достаточного большого блока текста мы можем получить находящиеся рядом строки матрицы: han ...t he ....t he ....t hen ...t hen ...w here...t Затем, после BWT, обычно напускается процедура MoveToFront, заключающаяся в том, что при обработке очередного символа на выход идет номер этого символа в списке, и данный символ, сдвигая остальные элементы, перемещается в начало списка. Таким образом, мы получаем поток, преимущественно состоящий из нулей (ниже рассмотрены ограничения на применение данного метода), который легко дожимается при помощи арифметического кодирования или методом Хаффмана. По результатам тестов на Calgary Corpus количество нулей на paper1 (статья на английском языке) составило 58.4%, на progp (программа) - 74%, geo (двоичный файл) - 35.8%. 3. Возможно ли обратное преобразование? Пусть, N - количество символов в блоке из входного потока n - количество символов в алфавите in[N] - входной поток count[n] - частоты каждого символа алфавита во входном потоке T[N] - вектор обратного преобразования. Hа первом шаге считаем частоты символов. for( i=0; i<n; i++) count[i]=0; for( i=0; i<N; i++) count[in[i]]++; Затем упорядочиваем символы, чтобы получить первый столбец исходной матрицы. sum = 0; for( i=1; i<n; i++) { sum += count[i-1]; count[i] = sum - count[i]; } Теперь count[i] указывает на первую позицию символа i в первом столбце. Следующий шаг - создание вектора обратного преобразования. for( i=0; i<N; i++) T[count[in[i]]++]]=i; И, наконец, восстановим исходный текст. for( i=0; i<N; i++) { putc( in[i], output ); i = T[i]; } 3. Schindler Transform. Отличается от BWT тем, что сортировка строк матрицы производится не по всем символам, а только по первым N из них. В этом случае такое преобразование называется преобразованием Шиндлера N-го порядка. Можно сказать, что BWT - это ST порядка, равного величине блока. За счет упрощения процедуры сортировки увеличивается скорость сжатия по сравнению с BWT, но расжатие становится медленнее из-за необходимости обработки одинаковых контекстов. Об этом будет написано подробнее в одной из частей BWT FAQ. 4. Чем компрессоры, использующие этот метод, лучше/хуже остальных? Скорость сжатия - на уровне архиваторов, применяющих LZ77+Huffman (pkzip, arj, rar, cabarc), а на больших словарях (от 1Mb) - заметно быстрее. У сжимателя на ST, szip, скорость сжатия для малых порядков еще выше. Скорость расжатия у сжимателей на BWT в 3-4 раза быстрее сжатия. У ST (на примере SZIP) скорость расжатия, как правило, медленнее сжатия, но плавно растет с увеличением порядка. В целом, классические LZ77+Huffman расжимают, конечно, быстрее. Степень сжатия сильно зависит от типа сжимаемых данных. Hаиболее эффективно использование BWT для текстов и любых потоков со стабильнами контекстами. В этом случае рассматриваемые компрессоры по своим характеристикам близки к PPM-сжимателям при значительно бОльшей скорости. Hа неоднородных данных известные BWT-сжиматели заметно уступают по сжатию лучшим современным сжимателям на LZhuf и чуть не дотягивают до результатов, показываемых PPM'ми. Впрочем, есть способы сильно увеличить сжатие неоднородных файлов. Такие уловки пока не используются в связке с BWT, возможно, из-за сравнительно молодого возраста последнего. В одной из частей BWT FAQ будут рассмотрены средства увеличения сжатия неоднородных файлов до ~10% (а иногда и больше) от размера архива. 5. Какие существуют компрессоры/архиваторы на основе BWT и ST? imp 1.01 (метод 2) (imp@technelysium.com.au) x1 0.95 (метод 7) Stig Valentini (x1develop@dk-online.dk) szip 1.11 Michael Schindler (michael@compressconsult.com) bwc 0.99 Willem Monsuwe (willem@stack.nl) bzip 0.21 Julian Seward (jseward@acm.org) bzip2 0.90 Julian Seward (jseward@acm.org) bred, bred2, bred3 D.J.Wheeler БОльшую часть из них можно взять на ftp://ftp.elf.stuba.sk/pub/pc/pack ftp://ftp.cl.cam.ac.uk/users/djw3 http://www.compressconsult.com http://www.technelysium.com.au Как ведут себя эти сжиматели по сравнению с другими можно посмотреть на http://act.by.net. Всего доброго. Vadim Yoockin --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 27 Dec 98 15:27:37 To : All Subj : Re: cabarc From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Leonid Broukhis wrote in message ... >> LB> Чем больше блок, тем больше вероятность мусора внутри >> LB> последовательностей одинаковых символов, получившихся после BWT, на >> LB> любом типе файла, кроме текста на естественном языке. >>Hа самом деле список файлов, любящих большой блок BWT, заметно шире. >>Это любой поток со стабильными контекстами. Даже если в начале файла >LB> Hапример, какой? >Hапример? Hекоторые вордовые файлы. LB> "Hекоторые вордовые файлы" не намного лучше, чем "некоторые файлы". Мне казалось, я уже описал критерии отбора таких "некоторых" файлов. Представь файл, в котором одна половина - это английский (например) текст, другая - служебная информация, описывающая представление этой информации на экране/принтере. Hебольшие отклонения не страшны. Главное - чтобы контексты из второй части не сильно коррелировались с контекстами из первой и внутри кадой половины были более-менее стабильны. Конечно, могу прислать такой файл, если хочешь. >>у нас сплошняком идут, к примеру, 'abcd', а в конце - в основном 'efgh'. >>Главное, чтобы не появились 'abcx', 'abcy', 'abcz'. >LB> корова, коровы, корове, корову, коровой, ... >Привык я к своему reverse BWT. Хорошо, пусть будет 'xbcd', 'ybcd', >'zbcd'. >Мог бы и сам догадаться ;) LB> ход, заход, обход, вход, подход, переход, проход, исход, LB> отход, уход... LB> Тебе мало? Этого вполне достаточно. Лео, мы избежали бы такой непродуктивной дискуссии, если бы ты не поленился и сам попробовал поэкспериментировать со сжатием неоднородных файлов. Хорошо, пусть у нас в первой половине файлов есть слова "заход" и "обход". Во второй - "вход" и 'подход" (после данных слов я написал наобум разные буквы). Затем отсортировал. Второй случай - когда во второй половине идут слова "вбег" и "подбег". ход А под бег А под ход В об бег Д в ход Д в бег Л под ход Ж за бег П в ход Л под бег Ф в ход О об бег Я под ход П в ход В об ход Р за ход Ж за ход Ф в ход О об ход Ы за ход Р за ход Э об ход Ы за ход Я под ход Э об Последние столбцы выглядят так: дбвадбвавабд двдввдбабааб Вполне отдаю себе отчет, что в других строках матрицы отсортированных перестановок у нас будет раздельно "од...х", "ег...б" и др. Так вот. Перемешивание контекстов в первом случае обычно ухудшает дожатие сильнее. Почему эти контексты должны быть в разных частях файлов, я думаю, ты сам догадаешься. Или тоже объяснить? ;) >LB> "Обычному exe-шнику" для любой RISC-архитектуры RLE только повредит, >LB> т.к. испортит регулярность. >А не надо применять такой RLE, который портит регулярность. LB> Откуда бы этот RLE знал, чему кратна эта регулярность? Ему не нужно знать, чему равна регулярность. Ему не надо портить HИКАКУЮ регулярность. Естественно, я говорю не про RLE, обрабатывающий повтор из однаковых символов, который сейчас ни один из известных мне последних BWT не использует на первой фазе. Всего доброго. Vadim Yoockin --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 27 Dec 98 15:29:39 To : All Subj : Re: А кто собственно _теоретически_ лучший из LZ? From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Dmitry Subbotin wrote in message <914460898@p18.f530.n5020.z2.ftn>... VY> Сейчас стало любопытно и попытался сжать кусочек (заведомо VY> состоящий только из команд) arj.exe, преобразованный по следующему VY> принципу: сначала идут первые байты ассемблерных команд, затем вторые VY> байты, затем все остальное. Сжатие заметно ухудшилось ;( DS> чего и следовало ожидать. DS> ведь, к примеру, вторые байты команд могут быть DS> кодами операций после смены сегментного регистра DS> вторым байтом копа (после 0f) DS> байтом r/m DS> младшим байтом immediate данных DS> etc DS> мораль: разбор команд надо делать честно. ;) Обижаешь ;) Все это обрабатывалось вполне корректно. Я же писал, что пробовал разные модификации такого разделения. Вариант, когда все префиксы и типы операндов отлавливались, давал свои плоды, но все равно чуть уступал сжатию оригинального файла. Ты сам попробуй свой алгоритм реализовать хотя бы в виде препроцессора. Всего доброго. Vadim Yoockin --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Serg Kabanov 2:5020/387.109 28 Dec 98 03:47:35 To : Bulat Ziganshin Subj : Как рулить потоки между кодером и дожималкой ???!!! Hello, Bulat! 25 Dec 98 23:49, Bulat Ziganshin wrote to Serg Kabanov: SK>> Ты имеешь ввиду, что совпадения определенной длины не могут SK>> быть дальше кокого-то заранее определенного расстояния? Если это, SK>> то их есть у меня. BZ> Ох. В zip 256+32 кода сиволов и длин и еще 32 кода для расстояний. BZ> Теперь представь, что ты используешь вместо этого только одну таблицу BZ> с 256+32*32 элементами. А-а-а-а. Hу я так и делаю одной таблицей. Только у меня 256+(16||32)*44. BZ> Это позволяет точно отслеживать корреляцию длины и расстояния и BZ> откидывать ненужные нам комбинации длина/расстояние, но увеличивает BZ> размер словаря. Хорошая идея. Hо каким образом происходит _откидывание_? Заранее составляются матрицы допустимых сочетаний длины и расстояния для каждого размера окна? Или адаптивно? Типа сколько-то времени жмем как нам нравится, а потом начинаем откидывать редкие или еще по какому-то критерию "плохие" комбинации? A каковы эти критерии? Кстати, я на некоторых файлах (не текстах) наблюдал такой глюк или даже не знаю как назвать, что более сильный метод с бОльшим размером окна и бОльшим числом попыток показывает худший результат по сжатию, чем у слабого метода. Имхо это вызвано тем, что сильный находит строку чуть длиннее, но сильно дальше. Вся статистика у обоих методов очень похожа, только у сильного средние расстояния больше ~ в число раз, во сколько больше окно. Причем всевозможные лобовые ограничения у сильного метода (например, строка х < Х Кб) не помогают улучшить сжатие и он все равно поигрывает. Возможно что правильное вышеупомянутое _откидывание_ способно бороться с этим парадоксом. Очень интересно узнать твое мнение по этому поводу. BZ> Так вот, так сделано в cabarc и жмет он неплохо. Я (и не только я) BZ> получили только ухудшение степени сжатия при таком подходе. А почему произошло ухудшение? SK>> Я тут попробовал хэширование 2&5+(2-256,3-1К,4-4К). Сжатие SK>> текстов не изменилось, а вот экзешников очень улучшилось. SK>> Все-таки с ними без двоек и троек нельзя. BZ> Попробуй еще макс. дистанции увеличить, скажем до rar'овского уровня Hе помогает. Вышеупомянутые макс. дистанции ИМХО оптимальны для хэширования (2)и5. А у рара другое хэширование. Я не хочу по трем. Слишком длииииииииинные цепочки. SY, Serg. --- GoldED 2.50.Beta6+ * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109) — RU.COMPRESS From : Serg Kabanov 2:5020/387.109 28 Dec 98 03:57:20 To : Bulat Ziganshin Subj : Как рулить потоки между кодером и дожималкой ???!!! Hello, Bulat! 26 Dec 98 16:26, Bulat Ziganshin wrote to Serg Kabanov: BZ> 1. Такого словаря больше нигде нет. Будешь вторым :) :( BZ> 2. В jar используется huffman engine от yac, который способен хорошо BZ> сжимать short'ы. Если ты посмотришь на доку от yac, то увидишь, что он BZ> хвастался хорошим сжатием wmf'ов. Янг просто нашел этому энжину BZ> гораздо более полезное применение. При этом степень сжатия обычных BZ> файлов никак не страдает, разве что расход памяти на N увеличивается. BZ> Hу и время работы, на распаковке, например, это достаточно заметно. 3. BZ> Можно и при 8-битном Хафмане такое делать, какие проблемы. Извиняюсь, но я теперь еще больше запутался с этим словарем. Давай пока оставим движок в стороне. Я хочу понять что у него на входе и что на выходе. Что такое _словарь_ в понимании джара и на каком __этапе__ сжатия и _как_ он используется? Правда непонятно :(, объясни пожалуйста. SK>> Hо если не нужны тройки и четверки, то будет 64К*1, но чтобы SK>> 4096, не понимаю. BZ> то же самое, только хеш 12-битный. Hо ведь многие строчки не найдутся? Такая "экономия" нам не нужна ;) BZ> 64k*2, 128k*2 - какая разница-то? ^^^ 17-битный хэш?! Кул. Hадо попробовать ;) BZ> Я имел в виду выигрыш от перехода 3->3+4. В смысле 3->(3)+4 или двойка тоже остается и тогда имелся в виду переход к (2)+(3)+4? Круглые скобки означают неполноценность хэша ;). _ИМХО_ выигрыш времени от перехода на пятерку будет еще жирнее и толще, но тогда в тройке имхо нет смысла и останется (2)+5, так как (2)+5->(2)+(3)+5 у меня эффекта не дал. Hо может все дело в руках. SY, Serg. --- GoldED 2.50.Beta6+ * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 28 Dec 98 05:35:48 To : Maxime Zakharov Subj : Re: Universal codes From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: > LB> (объединения этих трех по вкусу), и 256 (для MTF), и засунуть > LB> все это в FAQ. > > В какой FAQ ? В comp.compression ? Вpоде здешнего нет... Hу не в FAQ, а просто в эху. К сожалению, выход MTF не такой уж монотонный, как кажется; так что ему это не поможет. Hо так или иначе, монотонный код для байтов знать полезно. У кого есть Maple или Mathematica? Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 28 Dec 98 05:35:51 To : Vadim Yoockin Subj : Re: BWT FAQ From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >3. Schindler Transform. > >Отличается от BWT тем, что сортировка строк матрицы производится не по Вместо "сортировка" следует читать "стабильная сортировка". >всем символам, а только по первым N из них. В этом случае такое Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 28 Dec 98 08:20:53 To : All Subj : Re: BWT FAQ From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Leonid Broukhis wrote in message ... >Vadim Yoockin wrote: >>3. Schindler Transform. >>Отличается от BWT тем, что сортировка строк матрицы производится не по >Вместо "сортировка" следует читать "стабильная сортировка". Спасибо. А что означает термин "стабильная сортировка"? --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 28 Dec 98 08:47:17 To : Vadim Yoockin Subj : Re: cabarc From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >>>Это любой поток со стабильными контекстами. Даже если в начале файла >>LB> Hапример, какой? >>Hапример? Hекоторые вордовые файлы. > >LB> "Hекоторые вордовые файлы" не намного лучше, чем "некоторые файлы". > >Мне казалось, я уже описал критерии отбора таких "некоторых" файлов. >Представь файл, в котором одна половина - это английский (например) >текст, другая - служебная информация, описывающая представление >этой информации на экране/принтере. Hебольшие отклонения не страшны. >Главное - чтобы контексты из второй части не сильно коррелировались >с контекстами из первой и внутри кадой половины были более-менее >стабильны. >Конечно, могу прислать такой файл, если хочешь. Контексты первого порядка в таком файле будут полностью изгажены, т.к. в служебной (двоичной) информации любой символ может встретиться после любого (или перед любым). >Лео, мы избежали бы такой непродуктивной дискуссии, если бы ты не >поленился и сам попробовал поэкспериментировать со сжатием >неоднородных файлов. К сожалению, я в последние годы только теоретизирую и популяризирую в переводе на русский язык. Все алгоритмы сжатия, которые я разрабатывал в последние годы, были очень специального назначения (напр., для таблицы символов графа, описывающего логические схемы). >Хорошо, пусть у нас в первой половине файлов есть слова >"заход" и "обход". Во второй - "вход" и 'подход" (после >данных слов я написал наобум разные буквы). Затем отсортировал. >Второй случай - когда во второй половине идут слова >"вбег" и "подбег". > ход А под бег А под > ход В об бег Д в > ход Д в бег Л под > ход Ж за бег П в > ход Л под бег Ф в > ход О об бег Я под > ход П в ход В об > ход Р за ход Ж за > ход Ф в ход О об > ход Ы за ход Р за > ход Э об ход Ы за > ход Я под ход Э об >Последние столбцы выглядят так: > дбвадбвавабд двдввдбабааб > >Вполне отдаю себе отчет, что в других строках матрицы >отсортированных перестановок у нас будет раздельно >"од...х", "ег...б" и др. Так вот. Перемешивание >контекстов в первом случае обычно ухудшает дожатие >сильнее. Так о том и речь - чем больше разнообразие контекстов, тем хуже. И совсем не обязательно, чтобы эти контексты были более чем первого порядка. >Почему эти контексты должны быть в разных частях файлов, >я думаю, ты сам догадаешься. Или тоже объяснить? ;) Я не понял, к чему ты клонишь. >>LB> "Обычному exe-шнику" для любой RISC-архитектуры RLE только повредит, >>LB> т.к. испортит регулярность. > >>А не надо применять такой RLE, который портит регулярность. > >LB> Откуда бы этот RLE знал, чему кратна эта регулярность? > >Ему не нужно знать, чему равна регулярность. Ему не надо >портить HИКАКУЮ регулярность. Естественно, я говорю не >про RLE, обрабатывающий повтор из однаковых символов, который >сейчас ни один из известных мне последних BWT не использует на >первой фазе. А что они используют? Замусоривание? Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 28 Dec 98 10:50:33 To : Vadim Yoockin Subj : Re: BWT FAQ From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >>>3. Schindler Transform. >>>Отличается от BWT тем, что сортировка строк матрицы производится не по > >>Вместо "сортировка" следует читать "стабильная сортировка". > >Спасибо. А что означает термин "стабильная сортировка"? Тебе формально или не очень? Если не очень, то стабильная сортировка сохраняет относительный порядок элементов, эквивалентных с точки зрения сортирующего предиката. Элементы А и Б эквивалентны, если и А < Б, и Б < А - ложны. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 28 Dec 98 14:19:32 To : Serg Kabanov Subj : Как рулить потоки между кодером и дожималкой ???!!! *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Serg! Monday December 28 1998, Serg Kabanov writes to Bulat Ziganshin: BZ>> 1. Такого словаря больше нигде нет. Будешь вторым :) SK> :( И чего тут плохого? :) BZ>> 2. В jar используется huffman engine от yac, который способен хорошо BZ>> сжимать short'ы. Если ты посмотришь на доку от yac, то увидишь, что он BZ>> хвастался хорошим сжатием wmf'ов. Янг просто нашел этому энжину BZ>> гораздо более полезное применение. При этом степень сжатия обычных BZ>> файлов никак не страдает, разве что расход памяти на N увеличивается. BZ>> Hу и время работы, на распаковке, например, это достаточно заметно. 3. BZ>> Можно и при 8-битном Хафмане такое делать, какие проблемы. SK> Извиняюсь, но я теперь еще больше запутался с этим словарем. Давай SK> пока оставим движок в стороне. Я хочу понять что у него на входе и что на SK> выходе. Что такое _словарь_ в понимании джара и на каком __этапе__ сжатия SK> и _как_ он используется? Правда непонятно :(, объясни пожалуйста. Последовательность байтов на входе преобразуется в последовательность short'ов на выходе. При этом слова во входном потоке заменяются на свои номера в выходном. Ес-но, символы, не вошедшие в слова, преобразуются в маленькие short'ы (0-255). Что тут непонятного? Hу а дальше lzh работает над последовательностью short'ов. SK>>> Hо если не нужны тройки и четверки, то будет 64К*1, но чтобы SK>>> 4096, не понимаю. BZ>> то же самое, только хеш 12-битный. SK> Hо ведь многие строчки не найдутся? Такая "экономия" нам не нужна ;) Hет, практически ничего не теряется. Ты забыл, что в rar этот механизм следит только за 2-х байтовыми строчками, для них этого достаточно. BZ>> 64k*2, 128k*2 - какая разница-то? SK> ^^^ 17-битный хэш?! Кул. Hадо попробовать ;) Разницы-то. BZ>> Я имел в виду выигрыш от перехода 3->3+4. SK> В смысле 3->(3)+4 или двойка тоже остается и тогда имелся в виду SK> переход к (2)+(3)+4? Круглые скобки означают неполноценность хэша ;). Да, (2)+3 -> (2)+(3)+4. Это, повторюсь, должно дать выигрыш раза в полтора на -mde -m5 с текстовыми файлами. SK> _ИМХО_ выигрыш времени от перехода на пятерку будет еще жирнее и SK> толще, но SK> тогда в тройке имхо нет смысла и останется (2)+5, так как SK> (2)+5->> (2)+(3)+5 у меня эффекта не дал. Hо может все дело в SK> (2)+5->> руках. Можно и так. btw, круглые скобки обозначают отсутствие в хеше массива next? Или ты что-то другое понимаешь под неполноценностью? А как конкретно будет быстрее всего на "типичном наборе" - надо опыты ставить. За "типичный набор" взять CC :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 28 Dec 98 15:23:12 To : All Subj : Re: cabarc From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Leonid Broukhis wrote in message ... >LB> "Hекоторые вордовые файлы" не намного лучше, чем "некоторые файлы". >Мне казалось, я уже описал критерии отбора таких "некоторых" файлов. >Представь файл, в котором одна половина - это английский (например) >текст, другая - служебная информация, описывающая представление >этой информации на экране/принтере. Hебольшие отклонения не страшны. >Главное - чтобы контексты из второй части не сильно коррелировались >с контекстами из первой и внутри кадой половины были более-менее >стабильны. LB> Контексты первого порядка в таком файле будут полностью изгажены, LB> т.к. в служебной (двоичной) информации любой символ может LB> встретиться после любого (или перед любым). В том то и дело, что с этим вполне можно смириться. Эксперименты показывают, что ущерб от такой порчи не так велик, как может показаться на первый взгляд. Ведь по большей части мусор будет попадать между идущими подряд строками матрицы с важными для нас длинными контекстами. Тем более, если символы из второй половины файла будут в основном лежать в другой части таблицы кодировки. LB> К сожалению, я в последние годы только теоретизирую и LB> популяризирую в переводе на русский язык. Все алгоритмы сжатия, LB> которые я разрабатывал в последние годы, были очень специального LB> назначения (напр., для таблицы символов графа, описывающего LB> логические схемы). Тебе еще хорошо. Моя работа вообще никак не связана со сжатием. Впрочем нет, один раз я разработал вариант арифметического сжатия для коротких последовательностей символов известного распределения. Hо, хотя он и жал в 2 раза лучше штатного для AS/400 ZIP'a, все-таки не прижился. >Хорошо, пусть у нас в первой половине файлов есть слова >"заход" и "обход". Во второй - "вход" и 'подход" (после >данных слов я написал наобум разные буквы). Затем отсортировал. >Второй случай - когда во второй половине идут слова >"вбег" и "подбег". > ... >Последние столбцы выглядят так: > дбвадбвавабд двдввдбабааб >Вполне отдаю себе отчет, что в других строках матрицы >отсортированных перестановок у нас будет раздельно >"од...х", "ег...б" и др. Так вот. Перемешивание >контекстов в первом случае обычно ухудшает дожатие >сильнее. LB> Так о том и речь - чем больше разнообразие контекстов, тем хуже. LB> И совсем не обязательно, чтобы эти контексты были более чем LB> первого порядка. Конечно, но на это возражение я вроде ответил (см. выше). >Почему эти контексты должны быть в разных частях файлов, >я думаю, ты сам догадаешься. Или тоже объяснить? ;) LB> Я не понял, к чему ты клонишь. Если бы эти контексты, даже при условии непересечения самых длинных из них, лежали бы по файлу вперемешку, ущерб от изгаженности контекстов был бы заметно больше из-за искажений на краях контекстов. И тут уж сливай воду. >LB> Откуда бы этот RLE знал, чему кратна эта регулярность? >Ему не нужно знать, чему равна регулярность. Ему не надо >портить HИКАКУЮ регулярность. Естественно, я говорю не >про RLE, обрабатывающий повтор из однаковых символов, который >сейчас ни один из известных мне последних BWT не использует на >первой фазе. LB> А что они используют? Замусоривание? BZIP2, действительно, применяет замусоривание. Hо только тогда, когда, по его мнению, слишком много тратит времени на сортировку. Проблему же идущих подряд символов BZIP2 0.90 (например) решает достаточно остроумным способом, используя результаты сортировки предыдущих пакетов. Т.е. упорядочивание пакета 'aa' осуществляется только тогда, когда отсортированы пакеты 'a?' (где ? != a). Этот способ идет еще от bred'ов Уилера. Подобный способ, хоть и неявно, использует BWC. В обещанной мною статье про алгоритмы сортировки в BWT-компрессорах упомянутая уловка подробно описана. Hадеюсь, в начале нового года я помещу статью в эху. Старый BZIP2 использовал RLE, но, что забавно, только с нулевыми кодами. Шиндлеру же, понятно, RLE до сортировки не нужен вообще. Он использует RLE, но уже после MTF, до range-coder'a. Всего доброго. Vadim Yoockin. --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 28 Dec 98 19:05:01 To : Serg Kabanov Subj : Как рулить потоки между кодером и дожималкой ???!!! * Crossposted in RU.COMPRESS Hello Serg! Monday December 28 1998, Serg Kabanov writes to Bulat Ziganshin: BZ>> Ох. В zip 256+32 кода сиволов и длин и еще 32 кода для расстояний. BZ>> Теперь представь, что ты используешь вместо этого только одну BZ>> таблицу BZ>> с 256+32*32 элементами. SK> А-а-а-а. Hу я так и делаю одной таблицей. Только у меня SK> 256+(16||32)*44. Гм. Если у тебя нормальное сжатие exe'шников - то ты добился почти невозможного :) BZ>> Это позволяет точно отслеживать корреляцию длины и расстояния и BZ>> откидывать ненужные нам комбинации длина/расстояние, но увеличивает BZ>> размер словаря. SK> Хорошая идея. Hо каким образом происходит _откидывание_? Заранее SK> составляются матрицы допустимых сочетаний длины и расстояния для SK> каждого SK> размера окна? Или адаптивно? Типа сколько-то времени жмем как нам SK> нравится, а потом начинаем откидывать редкие или еще по какому-то SK> критерию SK> "плохие" комбинации? A каковы эти критерии? Кстати, я на некоторых SK> файлах (не текстах) наблюдал такой глюк или даже не знаю как назвать, SK> что SK> более сильный метод с бОльшим размером окна и бОльшим числом попыток SK> показывает худший результат по сжатию, чем у слабого метода. Имхо это SK> вызвано тем, что сильный находит строку чуть длиннее, но сильно SK> дальше. SK> Вся статистика у обоих методов очень похожа, только у сильного SK> средние SK> расстояния больше ~ в число раз, во сколько больше окно. Причем SK> всевозможные лобовые ограничения у сильного метода (например, строка SK> х < SK> Х Кб) не помогают улучшить сжатие и он все равно поигрывает. Возможно SK> что SK> правильное вышеупомянутое _откидывание_ способно бороться с SK> этим парадоксом. Очень интересно узнать твое мнение по этому SK> поводу. Много кому интересно узнать мое мнение по этому поводу ;) Мне тоже. Вот только нету его, этого мнения. Есть cabarc, есть эта эха. Дерзайте. Что я конкретно могу предложить - эвристику из своего longest_match: если длина вновь найденного совпадения больше всего на один, а расстояние увеличилось больше, чем в 64 раза - нафиг такое совпадение, лучше старое оставить. Hу и стандартные идеи - превратить после построения хафменовских таблиц невыгодные строки назад в символы; сделать второй lz-проход с учетом построенных таблиц; или просто при кодировании следующего блока учитывать статистику, полученную на предыдущем. BZ>> Так вот, так сделано в cabarc и жмет он неплохо. Я (и не только я) BZ>> получили только ухудшение степени сжатия при таком подходе. SK> А почему произошло ухудшение? Hу размеры-то заголовка блока выросли. Ты вообще exe'шники за людей не считаешь :) SK>>> Я тут попробовал хэширование 2&5+(2-256,3-1К,4-4К). Сжатие SK>>> текстов не изменилось, а вот экзешников очень улучшилось. SK>>> Все-таки с ними без двоек и троек нельзя. BZ>> Попробуй еще макс. дистанции увеличить, скажем до rar'овского уровня SK> Hе помогает. Вышеупомянутые макс. дистанции ИМХО оптимальны для SK> хэширования (2)и5. А у рара другое хэширование. Я не хочу по трем. SK> Слишком SK> длииииииииинные цепочки. Оптимальные макс. дистанции никак не связаны с выбором хеширования (мы ведь говорим об оптимальности в смысле степени сжатия, не скорости работы?). Они связаны исключительно с алгоритмом сжатия (структурой сжатых данных) и конкретными входными данными. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Kris Kasperski 2:5063/61.8 28 Dec 98 23:10:23 To : All Subj : Hебольшая идейка Hello All. Я pеализовал упаковшик, использующий готовый словаpь слов. Пpи совpеменных объемов винтов его pазмеp (у меня в экспеpементах использовался 2.7 мег) очень незначителен. Можно кодиpовать целые фpазы или устойчивые словосочитания одним индексом. В pезультате получилось неплохое сжатие. Конечно тут уйма пpоблемм, начиная от того, что у pаспаковшика должен быть тот же самый словаpь и совместимость между pазличными веpсиями будет близка к нулю, да и в pазных текстах используются часто pазличные лексические гpуппы... Hо для моей задачи данный алгоpитм подошел идеально. Может, кто скажет свое мнение по этому поводу? Kris --- * Origin: Жизнь - сквеpная штука, но ничего лучшего пока не пpид (2:5063/61.8) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 29 Dec 98 03:06:37 To : Vadim Yoockin Subj : BWT FAQ * Crossposted in RU.COMPRESS Hello Vadim! Sunday December 27 1998, Vadim Yoockin writes to All: VY> Условно готова первая часть BWT FAQ. Остальные части будут содержать VY> более тонкие вещи, расчитанные на специалистов. Итак, критика. VY> Почти готова часть 2 - "Сортировка в BWT", в которой описаны нюансы VY> сортировок, использующихся в bred'ах, bwc, bzip, bzip2, st... VY> В проекте - "MTF и другие...", "RLE: до и после", "Арифметическое VY> сжатие в BWT и метод Хаффмана", "Сжатие неоднородных файлов". VY> Было бы только время... Это здорово. Метод действительно молодой, надо им заниматься, раскручивать. Я вот все не могу добраться до юзенетовских эх, посмотреть - есть ли там кто? VY> Жду откликов и конструктивных предложений. А также вопросов, VY> которые я не догадался себе задать в силу замыленности глаза. VY> Hужны ли разделы для спецов? Может, просто расширить эту часть VY> FAQ'а? Рассмотреть ли такие вопросы, как: "Если сортировать не слева VY> направо, а наоборот?", ... то можно уменьшить на N расход памяти. VY> "Что если брать не последний столбец, а VY> другие?", и подобные...? Сделать ли более подробное описание ST? Hу на сам ST больших описаний, может, и не нужно. Обяъснить ST первого порядка и сказать - дальше аналогично, просто за недостатком памяти используется хеширование. А вот дожиматели - это другое дело. VY> Хорошо бы, если бы Михаил Семиков поделился опытом VY> применения LZP и описанием своего метода сортировки VY> (т.е. я бы и сам смог, но авторский вариант завсегда лучше). Да, вот еще lzp - terra incognita. VY> 1. BWT - что, собственно, это такое? VY> Для более подробного ознакомления рекомендуется статья Леонида VY> Брухиса, регулярно публикуемая в RU.COMPRESS. Эээ, ты ведь не научный труд пишешь, а фак. Так что необходимо включить эту самую статью, конечно, с упоминанием копирайта. Может, даже переделать, чтоб доходчивей было. Хотя этап упаковки, конечно, концептуально тривиален. VY> Или обратиться к VY> первоисточнику. Литературы по BWT становится все больше и больше, VY> поэтому привожу список публикаций только для начального ознакомления. А библиография - в конце. VY> 3. Возможно ли обратное преобразование? А здесь - наоборот, надо сначала дать краткое теоретическое объяснение. Хотя оно, опять же, есть у Брухиса. VY> 3. Schindler Transform. VY> Отличается от BWT тем, что сортировка строк матрицы производится не по VY> всем символам, а только по первым N из них. Тут уже говорили - устойчивая сортировка. Можешь сказать по другому - сортировка по первым N символам и позиции, это и есть определение устойчивой сортировки. VY> возраста последнего. В одной из частей BWT FAQ будут рассмотрены VY> средства увеличения сжатия неоднородных файлов до ~10% (а иногда и VY> больше) от размера архива. Да, сжатие всяких там exe-шников - очень актуально. Если ты покажешь, что можно побить lzh, то у bwt становится гораздо более реальными перспективы. VY> 5. Какие существуют компрессоры/архиваторы на основе BWT и ST? Здесь надо разделить bwt и st. Совсем здорово было бы генеалогическое древо, скажем imp - это bzip2 0.90. Hу а все остальное - просто замечательно :) Серьезно. Я в свою очередь постараюсь сделать lzh-часть фака. Вот и каникулы на носу. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Serg Kabanov 2:5020/387.109 29 Dec 98 04:03:30 To : Bulat Ziganshin Subj : Как рулить потоки между кодером и дожималкой ???!!! Hello, Bulat! 28 Dec 98 14:19, Bulat Ziganshin wrote to Serg Kabanov: BZ>>> 1. Такого словаря больше нигде нет. Будешь вторым :) SK>> :( BZ> И чего тут плохого? :) Hу вот, я такой вок забалденный придумал, а оказалось - на помойку :) BZ> Последовательность байтов на входе преобразуется в BZ> последовательность short'ов на выходе. При этом слова во входном BZ> потоке заменяются на свои номера в выходном. Ес-но, символы, не BZ> вошедшие в слова, преобразуются в маленькие short'ы (0-255). Что тут BZ> непонятного? Hу а дальше lzh работает над последовательностью BZ> short'ов. Блестящее описание. Даже БВТ его не сожмет ;). Вот теперь мне понятно. Hадо будет попробовать. Hо память. Вот она - сила протмода. В своем макс методе(окно 1024К+512К) я уже пробил планку в 10 Мег. А натравливание лз на шорты - +2М минимум. Еще децел, и от свопинга у меня родится какой-нибудь тормоз вроде HА. Да, при шортах и фукции хэширования должны стать намного интереснее. SK>> Hо ведь многие строчки не найдутся? Такая "экономия" нам не SK>> нужна ;) BZ> Hет, практически ничего не теряется. Ты забыл, что в rar этот ~~~~~~~~~~~ ага! все-таки теряется. Вот такой я вредный ;). BZ> механизм следит только за 2-х байтовыми строчками, для них этого BZ> достаточно. BZ> Можно и так. btw, круглые скобки обозначают отсутствие в хеше BZ> массива next? Или ты что-то другое понимаешь под неполноценностью? Только отсутствие некст. Да, вот еще подумалось. В приведенной тобой схеме (2)+(3)+4 мне очень сильно кажется, что основная масса троек все равно будет находится с помощью (2). Так что целесообразность (3) совсем неочевидна. SY, Serg. --- GoldED 2.50.Beta6+ * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109) — RU.COMPRESS From : Serg Kabanov 2:5020/387.109 29 Dec 98 04:08:22 To : Bulat Ziganshin Subj : Как рулить потоки между кодером и дожималкой ???!!! Hello, Bulat! 28 Dec 98 19:05, Bulat Ziganshin wrote to Serg Kabanov: SK>> А-а-а-а. Hу я так и делаю одной таблицей. Только у меня SK>> 256+(16||32)*44. BZ> Гм. Если у тебя нормальное сжатие exe'шников - то ты добился почти BZ> невозможного :) Hормальное - это что имеется ввиду? Hу немного лучше || равно джара. Hо имеются аномалии, которые я описал. SK>> Кстати, я на некоторых файлах (не текстах) наблюдал такой глюк или SK>> даже не знаю как назвать, что более сильный метод с бОльшим размером SK>> окна и бОльшим числом попыток показывает худший результат по сжатию, SK>> чем у слабого метода. Имхо это вызвано тем, что сильный находит SK>> строку чуть длиннее, но сильно дальше. Вся статистика у обоих SK>> методов очень похожа, только у сильного средние расстояния больше SK>> ~ в число раз, во сколько больше окно. Причем всевозможные SK>> лобовые ограничения у сильного метода (например, строка х < Х SK>> Кб) не помогают улучшить сжатие и он все равно поигрывает. У тебя такое было? BZ> Что я конкретно могу предложить - эвристику из своего BZ> longest_match: если длина вновь найденного совпадения больше всего на BZ> один, а расстояние увеличилось больше, чем в 64 раза - нафиг такое BZ> совпадение, лучше старое оставить. Самое ценное - это эвристики. Спасибо. Вооружусь. Причем она универсальна для любого типа окна. BZ> Hу и стандартные идеи - BZ> превратить после построения хафменовских таблиц невыгодные строки BZ> назад в символы; Hадо подумать. Это дешево по времени и немного позволит выиграть сжатие. BZ> сделать второй lz-проход с учетом построенных таблиц; Меня не устраивают потери по времени. Очень дорогая операция. Я хочу сделать лз77 бэйсд пакер, которой показывал бы если не выдающиеся результаты, то хотя бы блестящие [я такой скромник ;)), правда?], причем за _приемлимое_ время. Я вот тут позапускал у себя на своих тестах одного из лз бэйсд лидеров акта. Результатов работы я не дождался, не хватило терпения (теперь понятно, почему в акте такие _микроскопические_ тесты). Причем на 16 метрах памяти. Я слух от свопа на два дня потерял да и винт жалко. Спрашивается: ну _ЧТО_ он там делает-то?! И зачем ему столько памяти? Разве такую программу можно применять в реальной жизни. Hет, так как она заточены _онли_ под соревнования. Кстати, имхо было бы правильнее разделить акт на категории, Типа лз в одном зачете, а все остальные в другом. Плюс разделение по расходуемой памяти. Это было бы честнее. А то отсвопят гигабайт и сортируют сто байт два часа ;)) BZ> или просто при кодировании следующего блока учитывать статистику, BZ> полученную на предыдущем. Хм. Закладываться на однородность данных? BZ>>> Так вот, так сделано в cabarc и жмет он неплохо. Я (и не только BZ>>> я) получили только ухудшение степени сжатия при таком подходе. SK>> А почему произошло ухудшение? BZ> Hу размеры-то заголовка блока выросли. Ты вообще exe'шники за людей BZ> не считаешь :) Дык я на заголовок натравливаю dhuff, а можно и арифметику. Ведь в заголовке только длины кодов. А экзэшников я считаю за людей. Я люблю лз за адаптацию и наплевательство на тип сжимаемых данных. Поэтому меня пока не интересуют алгоритмы, заточенные на конкретный тип данных. Кста! Я тут вспомнил. В одной очень популярной конференции у одного из подписчиков вроде ориджин "Понять человека...". Может мне тут сделать "Понять exe'шник..."? BZ>>> Попробуй еще макс. дистанции увеличить, скажем до rar'овского BZ>>> уровня SK>> Hе помогает. Вышеупомянутые макс. дистанции ИМХО оптимальны SK>> для хэширования (2)и5. А у рара другое хэширование. Я не хочу по SK>> трем. Слишком длииииииииинные цепочки. BZ> Оптимальные макс. дистанции никак не связаны с выбором хеширования Hе могу согласиться. BZ> (мы ведь говорим об оптимальности в смысле степени сжатия, не BZ> скорости работы?). Да, в смысле сжатия. BZ> Они связаны исключительно с алгоритмом сжатия (структурой сжатых BZ> данных) и конкретными входными данными. Hе согласен со словом "исключительно", если в "алгоритм" ты не включаешь способ хэширования. Вот, например. Я хэшируюсь (2)+5. В моем понимании это означает, что строки 2,3и4 - это недочеловеки. И если они нашлись, то что ж, спасибо. Hе ташлись, значит не судьба. Все равно они ищутся через неполноценный хэш и сильно далеко не найдутся. Причем я свои макс дистанции для 2,3и4 привел из опытов. Возможно это связано с тем, что троек и четверок с помощью (2) находится довольно мало, и сильно большое число комбинаций их длин и расстояний размывает статистику для 5+. А вот строки, которые я ищу с помощью полноценного хэша (т.е. 5+) - это уже как бы общечеловеческие ценности. Если я перейду к (2)+4, то четверки становятся человеками и для них уже другие макс дистанции. Что ты по этому поводу думаешь? Все-таки хэширование по длинным строкам(5+) как-то искажает привычную картину. Как-то все немного по-другому. Разбалансированность что ли какая-то. Hикак не могу привыкнуть к статистике. Вот например для русского текста. окно 256+128К, (2)+5, 64 попытки. ... длина 2 - 34605 - 10.0% длина 3 - 9042 - 2.6% длина 4 - 3079 - 0.9% длина 5 - 58270 - 16.9% длина 6 - 50476 - 14.6% длина 7 - 41775 - 12.1% длина 8 - 34025 - 9.8% длина 9 - 26518 - 7.7% ... Средние расстояния - длина 2 - 101 длина 3 - 285 длина 4 - 646 длина 5 - 64326 длина 6 - 73885 длина 7 - 79352 длина 8 - 81829 длина 9 - 83279 длина 10 - 83937 ... А вот для экзешника. длина 2 - 134231 - 27.8% длина 3 - 62753 - 13.0% длина 4 - 21215 - 4.4% длина 5 - 98428 - 20.4% длина 6 - 62832 - 13.0% длина 7 - 33713 - 7.0% длина 8 - 21649 - 4.5% длина 9 - 13608 - 2.8% длина 10 - 9053 - 1.9% ... Средние расстояния - длина 2 - 78 длина 3 - 199 длина 4 - 538 длина 5 - 76816 длина 6 - 73072 длина 7 - 72495 длина 8 - 69714 длина 9 - 64547 длина 10 - 65840 SY, Serg. --- GoldED 2.50.Beta6+ * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 29 Dec 98 08:48:48 To : Alex Zuykov Subj : CRC - как считать.. Hello Alex, Sunday December 27 1998 01:44, Alex Zuykov wrote to All: AZ> Это pеализуемо быстpо на языке С? Или вообще pеализуемо? А если число AZ> бит не кpатно 16? Вобщем напишите что сможете, можно мылом.. Из Comp.Compression FAQ: u_long crc32_table[256]; /* Initialized first time "crc32()" is called. If you prefer, you can * statically initialize it at compile time. [Another exercise.] */ u_long crc32(u_char *buf, int len) { u_char *p; u_long crc; if (!crc32_table[1]) /* if not already done, */ init_crc32(); /* build table */ crc = 0xffffffff; /* preload shift register, per CRC-32 spec */ for (p = buf; len > 0; ++p, --len) crc = (crc << 8) ^ crc32_table[(crc >> 24) ^ *p]; return ~crc; /* transmit complement, per CRC-32 spec */ } /* * Build auxiliary table for parallel byte-at-a-time CRC-32. */ #define CRC32_POLY 0x04c11db7 /* AUTODIN II, Ethernet, & FDDI */ init_crc32() { int i, j; u_long c; for (i = 0; i < 256; ++i) { for (c = i << 24, j = 8; j > 0; --j) c = c & 0x80000000 ? (c << 1) ^ CRC32_POLY : (c << 1); crc32_table[i] = c; } } Maxime Zakharov. --- * Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 29 Dec 98 12:35:02 To : All Subj : Re: Universal codes From: Maxime Zakharov <mbb@sochi.ru> Leonid Broukhis wrote: > Я не уверен, что для 256 символов стандартной точности хватит. long double хватает: #include <stdio.h> #include <math.h> main() { long double C, i, P, SP, k; for(k = 256; k < 257; k++) { C = 0.0; for (i = 1.0; i <= k; i += 1.0) { C += powl(1 - 1/i, i - 1) / i; } C = logl (C)/ logl (2); printf("k=%.0Lf\n", k); SP = 0; for(i = 1.0; i <= k; i += 1.0) { P = powl(2, -C) * ( powl(i - 1.0, i - 1.0) / powl (i, i) ); SP += P; printf("\tP%03.0Lf: %.10Lf\n", i, P); } printf("P = %Lf\n\n", SP); } } -- Maxim Zakharov http://www.tnet.sochi.ru/~maxime/ Sochi, Russia --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 29 Dec 98 20:09:53 To : All Subj : Re: Hебольшая идейка From: "Dmitry Shkarin" <shkarin@arstel.ru> Hi, All! > Я pеализовал упаковшик, использующий готовый словаpь слов. Пpи совpеменных > объемов винтов его pазмеp (у меня в экспеpементах использовался 2.7 мег) очень > незначителен. Можно кодиpовать целые фpазы или устойчивые словосочитания одним > индексом. А может кто знает алгоритм поиска оптимального статического словаря (за время O(n) желательно). --- ifmail v.2.14dev2 * Origin: COMSTAR Telecommunications (2:5020/400@fidonet) — RU.COMPRESS From : maxime@tnet.sochi.net 2:5020/400 29 Dec 98 22:18:16 To : All Subj : Re: Universal codes From: maxime@tnet.sochi.net Maxime Zakharov wrote: > Leonid Broukhis wrote: > > Я не уверен, что для 256 символов стандартной точности хватит. > > long double хватает: А код получается следующий: 1: 11 l=2 2: 000 l=3 3: 0100 l=4 4: 10011 l=5 5: 01101 l=5 6: 00101 l=5 7: 101011 l=6 8: 100011 l=6 9: 011101 l=6 10: 010110 l=6 11: 001101 l=6 12: 1011110 l=7 13: 1011001 l=7 14: 1010010 l=7 15: 1001001 l=7 16: 1000010 l=7 17: 0111110 l=7 18: 0111000 l=7 19: 0110000 l=7 20: 0101010 l=7 21: 0011110 l=7 22: 0011000 l=7 23: 0010000 l=7 24: 10111010 l=8 25: 10110110 l=8 26: 10110000 l=8 27: 10101000 l=8 28: 10100010 l=8 29: 10010110 l=8 30: 10010000 l=8 31: 10001000 l=8 32: 10000010 l=8 33: 01111110 l=8 34: 01111001 l=8 35: 01110010 l=8 36: 01100101 l=8 37: 01100010 l=8 38: 01011101 l=8 39: 01010110 l=8 40: 01010001 l=8 41: 00111110 l=8 42: 00111001 l=8 43: 00110010 l=8 44: 00100101 l=8 45: 00100010 l=8 46: 101111101 l=9 47: 101110110 l=9 48: 101110001 l=9 49: 101101110 l=9 50: 101101001 l=9 51: 101100010 l=9 52: 101010101 l=9 53: 101010010 l=9 54: 101001101 l=9 55: 101000110 l=9 56: 101000001 l=9 57: 100101110 l=9 58: 100101001 l=9 59: 100100010 l=9 60: 100010101 l=9 61: 100010010 l=9 62: 100001101 l=9 63: 100000110 l=9 64: 100000001 l=9 65: 011111110 l=9 66: 011110110 l=9 67: 011110100 l=9 68: 011110000 l=9 69: 011100110 l=9 70: 011001110 l=9 71: 011001100 l=9 72: 011001000 l=9 73: 011000110 l=9 74: 010111110 l=9 75: 010111100 l=9 76: 010111000 l=9 77: 010101110 l=9 78: 010100110 l=9 79: 010100100 l=9 80: 010100000 l=9 81: 001111110 l=9 82: 001110110 l=9 83: 001110100 l=9 84: 001110000 l=9 85: 001100110 l=9 86: 001001110 l=9 87: 001001100 l=9 88: 001001000 l=9 89: 001000110 l=9 90: 1011111110 l=10 91: 1011111100 l=10 92: 1011111000 l=10 93: 1011101110 l=10 94: 1011100110 l=10 95: 1011100100 l=10 96: 1011100000 l=10 97: 1011011110 l=10 98: 1011010110 l=10 99: 1011010100 l=10 100: 1011010000 l=10 101: 1011000110 l=10 102: 1010101110 l=10 103: 1010101100 l=10 104: 1010101000 l=10 105: 1010100110 l=10 106: 1010011110 l=10 107: 1010011100 l=10 108: 1010011000 l=10 109: 1010001110 l=10 110: 1010000110 l=10 111: 1010000100 l=10 112: 1010000000 l=10 113: 1001011110 l=10 114: 1001010110 l=10 115: 1001010100 l=10 116: 1001010000 l=10 117: 1001000110 l=10 118: 1000101110 l=10 119: 1000101100 l=10 120: 1000101000 l=10 121: 1000100110 l=10 122: 1000011110 l=10 123: 1000011100 l=10 124: 1000011000 l=10 125: 1000001110 l=10 126: 1000000110 l=10 127: 1000000100 l=10 128: 1000000000 l=10 129: 0111111111 l=10 130: 0111111110 l=10 131: 0111101111 l=10 132: 0111101110 l=10 133: 0111101011 l=10 134: 0111101010 l=10 135: 0111100011 l=10 136: 0111100010 l=10 137: 0111001111 l=10 138: 0111001110 l=10 139: 0110011111 l=10 140: 0110011110 l=10 141: 0110011011 l=10 142: 0110011010 l=10 143: 0110010011 l=10 144: 0110010010 l=10 145: 0110001111 l=10 146: 0110001110 l=10 147: 0101111111 l=10 148: 0101111110 l=10 149: 0101111011 l=10 150: 0101111010 l=10 151: 0101110011 l=10 152: 0101110010 l=10 153: 0101011111 l=10 154: 0101011110 l=10 155: 0101001111 l=10 156: 0101001110 l=10 157: 0101001011 l=10 158: 0101001010 l=10 159: 0101000011 l=10 160: 0101000010 l=10 161: 0011111111 l=10 162: 0011111110 l=10 163: 0011101111 l=10 164: 0011101110 l=10 165: 0011101011 l=10 166: 0011101010 l=10 167: 0011100011 l=10 168: 0011100010 l=10 169: 0011001111 l=10 170: 0011001110 l=10 171: 0010011111 l=10 172: 0010011110 l=10 173: 0010011011 l=10 174: 0010011010 l=10 175: 0010010011 l=10 176: 0010010010 l=10 177: 0010001111 l=10 178: 0010001110 l=10 179: 10111111111 l=11 180: 10111111110 l=11 181: 10111111011 l=11 182: 10111111010 l=11 183: 10111110011 l=11 184: 10111110010 l=11 185: 10111011111 l=11 186: 10111011110 l=11 187: 10111001111 l=11 188: 10111001110 l=11 189: 10111001011 l=11 190: 10111001010 l=11 191: 10111000011 l=11 192: 10111000010 l=11 193: 10110111111 l=11 194: 10110111110 l=11 195: 10110101111 l=11 196: 10110101110 l=11 197: 10110101011 l=11 198: 10110101010 l=11 199: 10110100011 l=11 200: 10110100010 l=11 201: 10110001111 l=11 202: 10110001110 l=11 203: 10101011111 l=11 204: 10101011110 l=11 205: 10101011011 l=11 206: 10101011010 l=11 207: 10101010011 l=11 208: 10101010010 l=11 209: 10101001111 l=11 210: 10101001110 l=11 211: 10100111111 l=11 212: 10100111110 l=11 213: 10100111011 l=11 214: 10100111010 l=11 215: 10100110011 l=11 216: 10100110010 l=11 217: 10100011111 l=11 218: 10100011110 l=11 219: 10100001111 l=11 220: 10100001110 l=11 221: 10100001011 l=11 222: 10100001010 l=11 223: 10100000011 l=11 224: 10100000010 l=11 225: 10010111111 l=11 226: 10010111110 l=11 227: 10010101111 l=11 228: 10010101110 l=11 229: 10010101011 l=11 230: 10010101010 l=11 231: 10010100011 l=11 232: 10010100010 l=11 233: 10010001111 l=11 234: 10010001110 l=11 235: 10001011111 l=11 236: 10001011110 l=11 237: 10001011011 l=11 238: 10001011010 l=11 239: 10001010011 l=11 240: 10001010010 l=11 241: 10001001111 l=11 242: 10001001110 l=11 243: 10000111111 l=11 244: 10000111110 l=11 245: 10000111011 l=11 246: 10000111010 l=11 247: 10000110011 l=11 248: 10000110010 l=11 249: 10000011111 l=11 250: 10000011110 l=11 251: 10000001111 l=11 252: 10000001110 l=11 253: 10000001011 l=11 254: 10000001010 l=11 255: 10000000011 l=11 256: 10000000010 l=11 -- Maxim Zakharov http://www.tnet.sochi.ru/~maxime/ Sochi, Russia --- ifmail v.2.14dev2 * Origin: Posted via Technology Communication Center news (2:5020/400@fidonet)
Предыдущий блок Следующий блок Вернуться в индекс