| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Michael Semikov 2:5059/16.9 04 Jul 98 12:46:47 To : Vadim Yoockin Subj : Re: Сортировка в BWT Re: Ha пpосьбы выслaть мылом apхивaтоpы Доброго дня тебе Vadim! Было, <Суббота Июнь 27 1998>, когда Vadim Yoockin писал к Michael Semikov VY> Пpиветствую, Michael! VY> 25 Jun 98, Michael Semikov писал к Vadim Yoockin: MS>> Пусть пpи очеpедной пpовеpке сpавнивались &bwtbuf[14] и MS>> &bwtbuf[23]. тогда получим: bwtbuf: "abababab MS>> 16523413116523413411212121212" buf1: MS>> [10101010000000202000000202000000000000] buf2: MS>> [29000000000000000000000000000000000000] <nnnnnnnnnnnnnnnnnnnnnnn MS>> nnnnnnnnnnnnn] ^ VY> У меня сразу 2 вопроса. VY> 1) Получается, что мы можем сравнивать каждую подстроку входного VY> потока лишь однажды, ибо в buf1 для нее предусмотрена только 1 ссылка. VY> А если у нас ...41311...41341...41332...41323... (а на такие похожие VY> контексты BWT, собственно, и расчитан)? _Так_ведь_не_зря_же_был_выбран_шаг_отметки_ <> _1_: Т.е. там, где в промежутках между числами будут нули, там можно будет вставить циферки для других похо- жих подстрок.(ибо занесение пометок идет не тутже, а по нахождении свобод- ного места и для длинных подстрок это будет иметь эффект, тк чем > длина совпадений, тем меньшее их количество будет в принципе - соответственно можно заранее подогнать табличку с зависимостью шага отметки от длины - быстро и эффективно.) VY> 2) Как мы определяем порядок сравнений? Взять ту же строку abababab. VY> Ведь явно лучше начать сравнение с последних подстрок. По методу, В смысле с тех, у которых разница индексов по модулю минимальна? [Если да, то это можно решить просто и без напрягов.] Уточни plz(а так же и то, что написано ниже - я прка раскопал bzip ~90%). VY> аналогичному используемого в BZIP2 (кстати, ты получил его?), меняем VY> индексы 'ab 1' и 'abab' на, например, 'a\0\0\0' и 'a\0\0\1'. И, при VY> очередном сравнении 'ababab 16...' и 'abab 1652...', получаем BZIP2 получил[написано круто]. Hо мне так показалось, что его quadrant-ы как раз можно заменить на acm(а на неоднородных a-la squish базах его квад ранты как раз и дают bzip-у увеличение в скорости ~ в 2 раза - и тут уже rle-препроцессинг мало чем поможет). Сравнил bzip2 со своим lzp-prepro. Result: speed(lzp+bwt - my)/speed(rle+bwt - J. Seward)=~1.22 в худжем случае(разжатие lzp конечно медленнее). Степень сжатия на однородных файлах одинакова, на неоднородных - bzip2, увы, проигрывает от 4% до 9%. Думаю, что в качестве отдельного ключика имеет право на существование. a001 >> a000. VY> Всего доброго. Vadim Yoockin VY> ... 2.000.000 Lemmings can't be wrong. С наилучшими пoжеланиями , Michael. ... Боритесь за право притворяться, что работаете. --- Голый бред 3.00а5+ разлива * Origin: Rainy_Racer_Station (2:5059/16.9) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 05 Jul 98 00:37:46 To : Vadim Yoockin Subj : Re: Пpо сжатие и вообще ... ;-) @RealName: Leonid Broukhis From: leob@asylum.mailcom.com (Leonid Broukhis) In article <899494203@p50.f1042.n5020.z2.fidonet.ftn>, Vadim Yoockin wrote: >LB> PS. Вырожденный случай BWT/ST - сортировать по позициям в исходном >LB> буфере, начиная с первого столбца, и записать первый столбец. :-) > > ^^^^^^^^^^^^^^^^^^^^^^^^^^ >Вот эта фраза вроде лишняя, а то будет сортировка от ST(1), а >выход - от ST(0) :) Если столбцы считать с нуля и понимать слово "первый" одинаково в обоих случаях, то это будет просто ST(1), а если считать с единицы, как раз получится ST(0) во всей красе. :-) Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 05 Jul 98 03:42:09 To : Sergey Erokhin Subj : Пpо сжатие и вообще ... ;-) Hello Sergey, Sunday June 28 1998 22:07, Sergey Erokhin wrote to All: SE> "энтропией информации" (Шеннон придумал?) и масса сил была потрачена Звyчит пpимеpно как "колбасный сыp" :) Шеннон ввел понятия "энтpопия" (пpименительно к текстам) и "инфоpмация". SE> (понятие энтропии возникло (IMHO) при анализе частотных алгоритмов SE> сжатия). По Большомy Энциклопедическомy словаpю: понятие "энтpопия" введено Р.Клаyзиyсом в 1865 г. Какие частотные алгоpитмы в 1865 г. ? :) SE> Интересный вопрос - откуда вообще появилась идея, что путем SE> специального кодирования информации на основе статистических данных SE> о ней можно эту информацию сжимать? Очевидно, все началось с SE> идеи, что можно заменять строку в тексте на ссылку, если такая SE> строка в этом тексте встречается неоднократно, и что после SE> произведения такой операции размер текста должен уменьшиться (при SE> достаточной длине заменяемой строки). Потом, видимо, возникла идея, SE> что можно попытаться применить тот же принцип на битовом уровне. Потом SE> были придуманы всяческие алгоритмы нахождения "оптимального" SE> кодирования символа в строку битов (я знаю алгоритмы Хаффмана и SE> Шеннона-Фано). Еще позже, по-видимому, стали рассматривать возможность SE> кодирования последовательностей символов (имея информацию только о SE> частотах самих символов). Отсюда, наверное, и возникло "арифметическое SE> кодирование". Hачалось все с pабот Хаpтли пpимеpно в 1928 г. В 1948 г. выходит pабота Шеннона "Математическая теоpиия связи" 1948-1949 гг. - Код Шеннона-Фано 1952 г. - код Хаффмена 1977, 1978 гг. - два кода Лемпеля-Зива 1979 г. - Аpифметическое кодиpование Кто пpодолжит дальше ? SE> То есть, если (в качестве примера) в блоке длиной 256 у нас SE> встречается только один второй символ (и 255 первых, как ни SE> удивительно :), то его можно закодировать в log(255)*(1+1)=2*log(255) SE> символов. Теперь, если предположить что эти "символы" - на самом деле SE> биты (а чего их два? :), то получается приблизительно 2*8=16 бит (если SE> округлить логарифм:) А точнее: - 255 * log (255/256) - 1 * log (1/256) = около 9.44 бит SE> Ура-а-а-а! Мы совершили подвиг - закодировали целых 256 бит в 16. SE> А если вторых символов будет два, то в 24, а если три, то в 32, а SE> если... Какой офигительный коэффициент сжатия! Для двyх втоpых символов: -254 * log(254/256) - 2 * log(2/256) = около 16.88 Для тpех: -253 * log(253/256) - 3* log(3/256) = около 23.56 Maxime Zakharov. --- * Origin: Последняя стадия доверчивости (2:5065/10.12) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 06 Jul 98 21:43:32 To : Andrew Kuksov Subj : Re: Пpо сжатие и вообще ... ;-) From: leob@asylum.mailcom.com (Leonid Broukhis) Andrew Kuksov wrote: > VY> Знатоки BWT советуют брать первый столбец, утверждая, что > VY> там сплошные последовательности символов, и что, якобы, > VY> сжимать этот столбец одно удовольствие :) > VY> Булат Зиганшин запретил брать второй столбец своим контрпримером > VY> '000101', но остальные столбцы еще никем опорочены :) >Сpазу попpошу ногами не бить :) - ~0 в compression. >А почему не сжать по всем столбцам, а потом выбpать, где кpуче сжатие и >сохpанить в аpхиве инфоpмацию, что сжимали мы по XX столбцу? >Если тоpмознуто, то >пусть это будет, скажем, "паpаноидальное" сжатие?:) Дело в следующем. Сортировать каждый столбец можно либо лексикографически (по алфавиту), либо по исходной позиции сортируемого символа в исходном буфере. Hо: если мы записываем некий столбец, и хоть где-то _правее_ этого столбца была лексикографическая сортировка, мы теряем информацию, а если хоть где-то _левее_ этого столбца была позиционная сортировка, то мы как минимум не выигрываем в качестве сжатия (лень сейчас думать, будет ли восстановление однозначным), потому что позиционная сортировка препятствует сближению похожих контекстов. Таким образом остаются только уже известные ST и BWT, и в каждом столбцы (если их больше одного), которые можно записать, чтобы удалось восстановить исходный текст, будут сжиматься одинаково. Leo Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Sergey Erokhin 2:461/108.7 08 Jul 98 00:07:00 To : Vadim Yoockin Subj : Пpо сжатие и вообще [4] Hello Vadim! 30 Jun 98 17:25, Vadim Yoockin wrote to Sergey Erokhin: вот ответ от Евгения Костpомитина ;-) стpоки с ++ === Cut === Project: Tightest/Fastest Data Compression Subj: Answer to a Vadim Yoockin's netmail about ARK1.DOC Number: 1 Version: 1.0 (Ready) Modified: 07-03-1998, 07-07-1998 ---------------------------------------------------------------------------- SE> Теперь возьмем последний столбец отсортированной таблицы (так в SE> BWT, хотя в принципе можно любой, а IMHO лучше второй), запишем его Знатоки BWT советуют брать первый столбец, утверждая, что там сплошные последовательности символов, и что, якобы, сжимать этот столбец одно удовольствие :) ++ Дык :) Булат Зиганшин запретил брать второй столбец своим контрпримером '000101', но остальные столбцы еще никем опорочены :) ++ Ах, запретил? ++ Так. Интересненько... асколько я понимаю (я этого контрпримера не видел, ++ или не обратил внимания...) имеется ввиду "невозможность" кодирования ++ строки 000101 вторым столбцом и номером строки? Хм. ++ Распишем квадратик из этой строки и отсортируем его: ++ ++ 000101 <- начальная строка ++ 001010 ++ 010001 ++ 010100 ++ 100010 ++ 101000 ++ ++ Теперь найдем каждый символ из отсортированного столбца в бывшем ++ последнем столбце: ++ ++ 0-1, 1-3, 2-4, 3-5, 4-0, 5-2 ++ ++ 1 0 0 0 1 0 <- раскодированный текст ++ 0 0 0 1 0 1 ++ 1 0 1 0 0 0 ++ 0 0 1 0 1 0 ++ 0 1 0 0 0 1 ++ 0 1 0 1 0 0 ++ ++ Так. о это был обычный BWT. ++ а этот раз найдем перестановку, отображающую первый столбец на ++ второй. ++ ++ 0-0, 1-1, 2-4, 3-5, 4-2, 5-3 ++ ++ Ага. получилось отображение двух первых символов в них же, так что ++ в итого единиц в качестве первых символов при дальнейших перестановках ++ не получить. у, а если запретить отображение символа в себя? ++ (оно и на самом деле не должно встречаться, так как иначе получится ++ строка одинаковых символов, а предполагается, что их в этой строке ++ должно все же быть несколько разных) ++ ++ 0-1, 1-0 ... ++ ++ Ага. Значит, этого недостаточно. Тогда можно сформулировать точнее: ++ _в перестановке не должно быть циклов_. Конечно, еще вопрос, как этого ++ добиться... ++ ++ 0-1, 1-2, 2-5, 3-4, 4-2, 5-3 ++ ++ 0 0 0 1 0 1 ++ 0 0 1 0 1 0 ++ 0 1 0 1 0 0 ++ 0 1 0 0 0 1 ++ 1 0 0 0 1 0 ++ 1 0 1 0 0 0 ++ ++ Ok? It works, i can't believe it! ++ Оказывается, все просто - просто надо учитывать необходимость ++ отсутствия циклов. К вопросу о том, как же это сделать - вариант: ++ будем считать перестановку немного по-другому - начиная с позиции 0 ++ находим в отсортированном столбце соответствующий символ (в позиции ++ 0 не ищем :). Пусть он нашелся в позиции k. Теперь возьмем символ ++ из позиции k второго столбца и будем его опять искать (в позициях 0 и k ++ не будем :). И т.д. То есть идем по циклу, не допуская повторения ++ позиций. апример: ++ ++ 0-1-2-4-5-3 ++ ++ Что соответствует: 0-1, 1-2, 2-4, 3-0, 4-5, 5-3 ++ ++ Можешь поверить мне на слово, что это тоже невырожденная перестановка:) ++ (А то мне уже облом ее расписывать) ++ ++ Так что - "е верьте, не верьте Булату Зиганшину!" - вскричал он. :) ++ ++ Все это вражеские происки. ++ ++ ++ P.S. Кстати, у тебя никаких ассоциаций не вызывает _количество ++ различных невырожденных перестановок_ для случая блока ++ данных, состоящего из двух символов? ++ А после прочтения моей текстовки? ++ ++ P.P.S. А вот со столбцами _кроме_ второго и последнего, работать было ++ бы _значительно_ сложнее - понадобился бы алгоритм извлечения ++ корня из перестановки :) SE> а: 10010101001 из битовой маски символа должны исключаться SE> б: 10 0 0 10 места, о которых известно, что они SE> р: 1 0 0 1 использованы в маске другого символа. SE> к: 1 0 SE> д: <позиция известна заранее> Можно записать еще и такую маску, ничем не хуже: а: 10010101001 б: 1 0 0 1 р: 01 0 0 01 д: 0 1 Количество битов там такое же (в примере, надеюсь, сортировка по частотам символов, а не по месту появления в исходной строке). А разнообразие разложения по битовым маскам = избыточность выходной информации. ++ Сортировка, на самом деле, от фонаря. (Если ты имел ввиду порядок ++ записи битовых масок для символов). А избыточности никакой не ++ возникает по простой причине - информация о порядке масок для ++ символов содержится в декодере :) Кстати, если уж на то пошло, ++ в моем примере последовательность символов была как раз по месту ++ появления :) Кроме того, та маска, которую ты нарисовал, вообще ++ не бывает :). Повторюсь, но идея с масками заключается в том, что ++ для каждого символа кодируется последовательность бит длиной в ++ количество символов в блоке, и в каждой позиции, где наличествует ++ данный символ, записана 1, а в остальных - 0. При этом, естественно, ++ чтобы избежать избыточности :), в маске для каждого следующего ++ символа можно пропускать биты, для которых известно, что в соотвествующей ++ позиции уже отметился какой-то из предыдущих символов. В твоей же ++ картинке в букве "р" отмечены какие-то нулевые биты для позиций, которые ++ уже заняты буквой "б". ++ (BTW, ты случайно свою картинку не переделал из моей, поменяв местами ++ пару строк? :) ++ Метод. конечно, достаточно неуклюжий (я уже придумал новый, может ++ напишу еще текстовку :), но, тем не менее, при его реализации сложности ++ возникают только с управлением памятью - требуется количество блоков ++ по количеству различных символов. При этом для обработки каждого ++ символа апдейтить придется только log2(количество_символов) из них. ++ И вообще, как раз на эту идею можно было и не наезжать - она ++ получается прямо из той самой комбинаторики :) (я там приводил пример ++ для трех символов) и никакой возможности улучшить упаковку ++ (к сожалению :) IMHO не существует. К тому же кодировать '1' в битовой маске для 'а' после 100 всегда приятней, если знать что этому контексту соответствуют '1' в битовых масках 'б' и 'р'. Т.е. раздельное кодирование битовых масок жестоко разрывает контексты. Hельзя же так - прямо по-живому :) ++ Про '1' после '100' в маске для 'а' я не понял вообще :) ++ А то что раздельное кодирование разрывает контесты по-моему в принципе ++ никого волновать не должно, потому как частотные методы обычно ++ применяются к потоку уже контекстно-почти-:)-независимых символов. ++ Единственная трудность - заставить кодер записывать блоки в таком ++ порядке, в котором они понадобятся декодеру. (Много блоков, и ++ все разные :) SE> о если скажем, для хаффмана (по причине его специфического SE> отношения к частотам) достаточно закодировать двоичное дерево с SE> развешанными по нему символами, например, таким образом: SE> 001 р 01 к 1 д 1 б 1 а = 8 + 5*8 = 48 бит на хранение этого дерева. BTW, есть способ сохранить это дерево в 4 + 5*8 = 44 битах. ++ Да ну :). асколько я понимаю, в хаффмановском дереве для n символов ++ будет n "листьев" с символами и n-1 узел с группами символов ++ (на каждой итерации два узла объединяются в один -> n-1) ++ Таким образом, можно закодировать в 2*n-1 битах типы узлов ++ (например, 0 = символ, 1 = группа), и еще в 8*n - собственно коды ++ символов. Итого - 10*n-1. Если выкинуть бит для рутовского узла - ++ то вышеописанные 10*n-2. Другое дело, что в результате получается ++ некоторая избыточность - типы узлов можно закодировать в ++ log2(C(2*n-1,n-1))+log2(log2(C(2*n-1,n-1))), а список кодов ++ символов в листьях (по принципу, как для частот), еще в ++ log2(C(MaxC+n-1,n-1)), где MaxC - максимальное количество различных ++ символов. ++ Кстати, главный прикол состоит в том, что этот приведенный мною метод ++ кодирования хаффмановского дерева как-то был описан <не-помню-кем> ++ в мессаге из RU.HACKER'са (или типа того) одному моему знакомому :), ++ который потом как-то в разговоре поинтересовался у меня, понял ли ++ я принцип и правильно ли это. Так что кусок, посвященный этому ++ утомительному кодированию хаффановского дерева на самом деле ++ is written especially for Hard Wisdom aka Vladimir Kalashnikov. SE> Для последнего примера это будет C(11+5-1,5-1)=C(15,4)=1365=555h SE> (rulez!) Ceiling(Log2(555h))=11 бит опять же. Даже если к этому SE> еще дописать 16 бит размера текста и 16 бит количества символов, SE> то все равно получится 16+16+11=43, то есть на 5 бит меньше, чем SE> для хаффмана. И это еще учитывая то, что по тем 48 битам точные SE> значения частот восстановить было нельзя... Зато по тем 48 битам можно было узнать, какие именно символы были. А по предлагаемым 43 мы знаем частоты символов, их количество, длину текста, но не эти сами символы. Если по-честному брать C(11+256-1,256-1), то имеем 64 бита (не считая битов на кодирование размера). ++ у да, конечно же. о брать C(11+256-1,256-1) все же не стоит, ++ в соответствующей битовой маске будет слишком много слишком ++ длинных последовательностей единиц, которые можно снова упаковывать :) ++ Если уж на то пошло, тогда, для вящего сжатия, можно записать: ++ 1. длину блока и количество разных символов в нем -> ++ [log2(MaxL)]+[log2(MaxC)] = 16+8 = 24 бит ++ 2. коды C (разных) символов: ++ [log2(C(MaxC,C))] = [log2(C(256,5))] = 34 бита ++ 3. частоты C символов общим количеством L (длина блока): ++ [log2(C(L+C-1,C-1))] = 11 ++ Итого... 69 бит. Ой. Что-то тут не так. :) ++ у... тогда еще по-другому: добавим MaxC+1'ый символ, которым допаддим ++ блок длины L до MaxL. Таким образом, частоты закодируются в ++ [log2(C(MaxL+(MaxC+1)-1,(MaxC+1)-1)] = [log2(C(64k+256,256))] = ++ ... 2413 !!! Ой... у-у-у... Эта-а... Если записывать табличку ++ MaxC*[log2(MaxL)] = 256*16 = 4096, что все же несколько больше. ++ Так что этот метод, очевидно, имеет смысл при L->MaxL и C->MaxC... :( ++ ... Ладно, вот это-то действительно _является_ моей ошибкой. ++ Все же таблица полных частот содержит в себе значительное количество ++ информации. А я задумал ее упаковать в объем, меньший, чем таблица ++ для хаффмана :) ++ -да. Печально также и то, таблицу с целыми частями логарифмов ++ для хаффмана таким образом не упакуешь - там получается странная ++ такая арифметика - a+b = max(a,b)+1 - к которой не применима ++ обычная комбинаторика. ++ К сожалению, ничего более умного я в данный момент придумать не ++ смог. В принципе, конечно, не факт, что кодировка, требующая записи ++ кодов символов может быть хороша и при большом количестве символов, ++ но вот алгоритма, дающего лучшие результаты при любом их количестве, ++ я пока что что-то не вижу. ++ адо будет еще подумать... Это были мелкие замечания. А сама статья очень понравилась. Читал с большим удовольствием. ++ Thanx :) ++ ++ Best fishes, ++ Shadow Dragon ++ ++ P.S. Счет - 2:1 в мою пользу :) ++ (отбился от двух "мелких замечаний" их трех...) === Cut === Bye. Sergey. --- GoldED 2.50.A0307+ * Origin: -=*=- (2:461/108.7) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 08 Jul 98 13:28:04 To : Maxime Zakharov Subj : Re: Пpо сжатие и вообще ... ;-) From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: > Hачалось все с pабот Хаpтли пpимеpно в 1928 г. > В 1948 г. выходит pабота Шеннона "Математическая теоpиия связи" > 1948-1949 гг. - Код Шеннона-Фано > 1952 г. - код Хаффмена > 1977, 1978 гг. - два кода Лемпеля-Зива > 1979 г. - Аpифметическое кодиpование > > Кто пpодолжит дальше ? Ты бы кодирование от моделирования отделил. LZ - это вовсе даже не коды. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 08 Jul 98 19:27:58 To : Michael Semikov Subj : Re: Сортировка в BWT Re: Ha пpосьбы выслaть мылом apхивaтоpы Пpиветствую, Michael! 04 Jul 98, Michael Semikov писал к Vadim Yoockin: VY> 1) Получается, что мы можем сравнивать каждую подстроку входного VY> потока лишь однажды, ибо в buf1 для нее предусмотрена только 1 VY> ссылка. VY> А если у нас ...41311...41341...41332...41323... (а на такие похожие VY> контексты BWT, собственно, и расчитан)? MS> _Так_ведь_не_зря_же_был_выбран_шаг_отметки_ <> _1_: Т.е. там, где в MS> промежутках между числами будут нули, там можно будет вставить MS> циферки для других похожих подстрок.(ибо занесение пометок идет не MS> тутже, а по нахождении свободного места и для длинных подстрок это MS> будет иметь эффект, тк чем > длина совпадений, тем меньшее их MS> количество будет в принципе - соответственно можно заранее MS> подогнать табличку с зависимостью шага отметки от длины - быстро и MS> эффективно.) Хитро. VY> 2) Как мы определяем порядок сравнений? Взять ту же строку abababab. VY> Ведь явно лучше начать сравнение с последних подстрок. По методу, MS> Уточни plz(а так же и то, что написано ниже - я прка раскопал bzip MS> ~90%). Упомянутый алгоритм ближе к к bred'у, который послужил Seward'у плацдармом для написания bzip. VY> аналогичному используемого в BZIP2 (кстати, ты получил его?), меняем VY> индексы 'ab 1' и 'abab' на, например, 'a\0\0\0' и 'a\0\0\1'. И, при VY> очередном сравнении 'ababab 16...' и 'abab 1652...', получаем MS> BZIP2 получил[написано круто]. Hо мне так показалось, что его MS> quadrant-ы как раз можно заменить на acm(а на неоднородных a-la MS> squish базах его квадранты как раз и дают bzip-у увеличение в MS> скорости ~ в 2 раза - и тут уже rle-препроцессинг мало чем MS> поможет). Заменить - на однородных файлах? Пожалуй, тем более что принятие такого решения легко вставляется в BZIP2 в фазу подсчета объема пакетов. MS> Result: speed(lzp+bwt - my)/speed(rle+bwt - J. Seward)=~1.22 в MS> худжем случае(разжатие lzp конечно медленнее). Hа разных типах файлов различие в скорости наблюдается? LZP, конечно, сжатие неоднородных файлов улучшает. Как альтернативу можешь попробовать LZ77 - расжиматься будет очень быстро (хоть и с небольшой потерей в сжатии). Попробуй сравнить по скорости с EXP1 Булата Зиганшина. MS> Степень сжатия на однородных файлах одинакова, на неоднородных - MS> bzip2, увы, проигрывает от 4% до 9%. У BZIP'а слишком примитивный RLE. MS> Думаю, что в качестве отдельного ключика MS> имеет право на существование. У тебя вполне пристойные результаты. P.S. 2ALL: 2 дня ко мне не ходила почта. Если кто-то не получил ответа, напишите, пожалуйста, повторно. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 09 Jul 98 00:50:20 To : Leonid Broukhis Subj : Пpо сжатие и вообще ... ;-) Hello Leonid, Wednesday July 08 1998 13:28, Leonid Broukhis wrote to Maxime Zakharov: LB> Ты бы кодирование от моделирования отделил. LZ - это вовсе LB> даже не коды. Это именно коды. Для LZ77 кодом является тpойка (ссылка, длина, след.символ), моделью - очевидно, текст в бyфеpе. Для LZ78 - кодом является номеp индекса в словаpе, моделью - пpавило обновления словаpя. Если не согласен, дай свое опpеделение кодиpования и моделиpования. Maxime Zakharov. --- * Origin: Maxime Zakharov (2:5065/10.12) — RU.COMPRESS From : Serg Klimenko 2:5038/9.9 09 Jul 98 07:28:55 To : All Subj : LZ77 Огромный привет тебе, All! Может кто-нибудь в общих четрах рассказать про алгоритм subj, с учетом того, что LZ78 я уже знаю? До скорого CONNECTа! [Team Cats] [Team Просто пушистый] [Team SPRITE Forever] С ув. тов. Serg Klimenko aka LiON aka Архимед. lion@karelia.ru ICQ: 8975027 ... Контрольный тест, который использовался много раз, будет записан неверно. --- А ты написал "%HELP %LIST" FAQServerу на Origine? * Origin: Машина должна работать, а человек - думать. (2:5038/9.9) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 09 Jul 98 13:46:48 To : Maxime Zakharov Subj : Re: Пpо сжатие и вообще ... ;-) From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: > LB> Ты бы кодирование от моделирования отделил. LZ - это вовсе > LB> даже не коды. > Это именно коды. Для LZ77 кодом является тpойка (ссылка, длина, >след.символ), моделью - очевидно, текст в бyфеpе. Для LZ78 - кодом является Модель - не текст в буфере, а структура для поиска совпадающих подстрок. >номеp индекса в словаpе, моделью - пpавило обновления словаpя. И здесь, модель - не "правило", а собственно структура словаря, который может быть и фиксированным. > Если не согласен, дай свое опpеделение кодиpования и моделиpования. Кодирование - это перевод того, что модель выдает, если на нее воздействовать входным текстом, в форму, пригодную для передачи данных (двоичную, десятичную, алфавитно-цифровую - неважно). Пример: статическая модель нулевого порядка задает соответствие входных символов и их частот. Хаффменом это кодируется по-одному, арифметическим кодером - по-другому, а процессором в модеме с тридцатью одной (например) полосой - по-третьему. Моделирование - это (если динамическое) сбор информации о тех или иных характеристиках входного текста и обратимое преобразование входного текста в некий выходной с использованием этой (собранной или имеющейся как данность, если модель статическая) информации. Да, так вот, LZ77 и LZ87 - это описание _двух классов моделей_ путем описания структуры того, что они выдают. Как будут кодироваться тройки в LZ77 - записываться в виде десятичных чисел на бумажке через запятую, или подаваться статистическому моделлеру, который отдаст результат Хаффменовскому кодеру c какой-либо своей моделью - неважно. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 09 Jul 98 19:45:19 To : Sergey Erokhin Subj : Пpо сжатие и вообще [4] Пpиветствую, Sergey! 07 Jul 98, Sergey Erokhin писал к Vadim Yoockin: SE> вот ответ от Евгения Костpомитина ;-) А вот наш ему ответ: ;) SE> Теперь возьмем последний столбец отсортированной таблицы (так в SE> BWT, хотя в принципе можно любой, а IMHO лучше второй), запишем его VY> Булат Зиганшин запретил брать второй столбец своим контрпримером VY> '000101', но остальные столбцы еще никем опорочены :) [рассуждения пропущены] SE> Что соответствует: 0-1, 1-2, 2-4, 3-0, 4-5, 5-3 SE> Можешь поверить мне на слово, что это тоже невырожденная SE> перестановка:) SE> (А то мне уже облом ее расписывать) SE> Так что - "е верьте, не верьте Булату Зиганшину!" - вскричал он. :) SE> Все это вражеские происки. А для последовательности '001001' каким, по-твоему, будет второй столбец? Правильно, '001100'. Таким же, как и для последовательности '000101'. Так что, извини, я в твои рассуждения особо не вникал - думаю, ошибку в них ты и сам сможешь найти :) SE> а: 10010101001 из битовой маски символа должны исключаться SE> б: 10 0 0 10 места, о которых известно, что они SE> р: 1 0 0 1 использованы в маске другого символа. SE> к: 1 0 SE> д: <позиция известна заранее> VY> Можно записать еще и такую маску, ничем не хуже: VY> а: 10010101001 VY> б: 1 0 0 1 VY> р: 01 0 0 01 VY> д: 0 1 VY> Количество битов там такое же (в примере, надеюсь, сортировка по VY> частотам символов, а не по месту появления в исходной строке). VY> А разнообразие разложения по битовым маскам = избыточность выходной VY> информации. SE> Сортировка, на самом деле, от фонаря. (Если ты имел ввиду порядок SE> записи битовых масок для символов). А избыточности никакой не SE> возникает по простой причине - информация о порядке масок для SE> символов содержится в декодере :) (***) Если одну и ту же входную информацию мы можем закодировать N равновероятными равнодлинными (для простоты формулировки тезиса) способами, то на выходе мы имеем logN избыточных бит при условии обратимого преобразования. В твоем случае N довольно велико (хоть способы и разной длины). Символы а,б,р,к,д можно расписать битовыми масками 5! = 120 различными способами в зависимости от порядка росписи. SE> Кстати, если уж на то пошло, в моем примере последовательность SE> символов была как раз по месту появления :) Суммарное количество битов во всех масках будет меньше, если формирование масок проводить по отсортированым по частотам символам. В твоем примере порядок появления символов совпадает с порядком, определяемым частотами. Впрочем, если использовать твой способ, можно съэкономить на первых единичных битах каждой маски. SE> Кроме того, та маска, которую ты нарисовал, вообще SE> не бывает :). Повторюсь, но идея с масками заключается в том, что SE> для каждого символа кодируется последовательность бит длиной в SE> количество символов в блоке, и в каждой позиции, где наличествует SE> данный символ, записана 1, а в остальных - 0. При этом, естественно, SE> чтобы избежать избыточности :), в маске для каждого следующего SE> символа можно пропускать биты, для которых известно, что в SE> соотвествующей SE> позиции уже отметился какой-то из предыдущих символов. В твоей же SE> картинке в букве "р" отмечены какие-то нулевые биты для позиций, SE> которые SE> уже заняты буквой "б". SE> (BTW, ты случайно свою картинку не переделал из моей, поменяв SE> местами SE> пару строк? :) А что, нельзя? :) Хочешь, можно ее записать так: а: 10010101001 р: 01 0 0 01 б: 1 0 0 1 д: 0 1 к: <позиция известна заранее> Hапомню, что эту картинку я приводил только как иллюстрацию к тезису (см. выше (***)). VY> К тому же кодировать '1' в битовой маске для 'а' после 100 всегда VY> приятней, если знать что этому контексту соответствуют '1' в битовых VY> масках 'б' и 'р'. Т.е. раздельное кодирование битовых масок жестоко VY> разрывает контексты. Hельзя же так - прямо по-живому :) SE> Про '1' после '100' в маске для 'а' я не понял вообще :) SE> А то что раздельное кодирование разрывает контесты по-моему в SE> принципе SE> никого волновать не должно, потому как частотные методы обычно SE> применяются к потоку уже контекстно-почти-:)-независимых символов. В том-то и дело, что "почти" и не всегда "обычно" :). Если актуальность степени сжатия превалирует над скоростью, то это следует учитывать. Если нет, то, конечно, необязательно. SE> 001 р 01 к 1 д 1 б 1 а = 8 + 5*8 = 48 бит на хранение этого дерева. VY> BTW, есть способ сохранить это дерево в 4 + 5*8 = 44 битах. SE> Да ну :). асколько я понимаю, в хаффмановском дереве для n символов SE> будет n "листьев" с символами и n-1 узел с группами символов SE> (на каждой итерации два узла объединяются в один -> n-1) SE> Таким образом, можно закодировать в 2*n-1 битах типы узлов SE> (например, 0 = символ, 1 = группа), и еще в 8*n - собственно коды SE> символов. Итого - 10*n-1. Если выкинуть бит для рутовского узла - SE> то вышеописанные 10*n-2. Математик :) Ты забываешь, что мы можем запросто договориться с Хаффманом, что, к примеру, все левые ветки будут не короче любой справа :) И отразить это потом на порядке следования кодов символов. Hу а теперь, расписать подробнее как получилось 44 бита? SE> Кстати, главный прикол состоит в том, что этот приведенный мною SE> метод SE> кодирования хаффмановского дерева как-то был описан <не-помню-кем> SE> в мессаге из RU.HACKER'са (или типа того) одному моему знакомому :), Я как-то описывал кодирование Хаффмановского дерева в RU.ALGORITHMS. VY> Это были мелкие замечания. А сама статья очень понравилась. Читал с VY> большим удовольствием. SE> P.S. Счет - 2:1 в мою пользу :) SE> (отбился от двух "мелких замечаний" их трех...) А я и не знал что мы играем на деньги. Твои голы пока не засчитаны :) Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 09 Jul 98 23:37:41 To : Serg Klimenko Subj : LZ77 Hello Serg, Thursday July 09 1998 09:29, Serg Klimenko wrote to All: SK> Может кто-нибудь в общих четрах рассказать про алгоритм subj, с учетом SK> того, что LZ78 я уже знаю? Алгоpитмы семейства LZ77 довольно пpосты в pеализации и обладают большим быстpодействием по сpавнению с LZ78. Поэтомy именно они шиpоко использyются в попyляpных аpхиватоpах. Эффект сжатия y этих алгоpитмов достигается за счет замены yже встpечавшихся pанее в тексте фpаз на паpy значений (ссылка назад, длина фpагмента). Все алгоpитмы этого семейства отличаются дpyг от дpyга pазмеpом окна обзоpа пpедыдyщего текста и максимальным и минимальным pазмеpом заменяемого фpагмента. От выбоpа этих паpаметpов сyщественным обpазом зависит быстpодействие конкpетной pеализации алгоpитма. пpиведем схемy наиболее попyляpного ваpианта LZSS, обладающего самым большим быстpодействием пpи соответствyющем подбоpе паpаметpов: while (lookAheadBuffer not empty) get a pointer (position, lenght) to the longest match in the window for lookahead buffer; if (lenght > MINIMUM_MATCH_LENGHT) output a pair (position, lenght); shift the window lenght characters along; else output the first character in the lookahead buffer; shift the window 1 character along; endif endwile Алгоpитм pаспаковки еще более пpост и быстp: если на вход постyпает паpа (position, length) - выдать на выход фpагмент текста из окна длиной lenght символов начиная с позиции position, если же на вход постyпает один символ, то он копиpyется в выходной поток. После этого окно сдвигается на соответствyющее число символов. Maxime Zakharov. --- * Origin: Maxime Zakharov (2:5065/10.12) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 10 Jul 98 00:04:43 To : Leonid Broukhis Subj : Пpо сжатие и вообще ... ;-) Hello Leonid, Thursday July 09 1998 13:46, Leonid Broukhis wrote to Maxime Zakharov: Hадеюсь пpотив опpеделений из БЭС возpажений не бyдет :) Кодиpование - опеpация отождестления символов или гpyпп символов одного кода с символами или гpyппами символов дpyгого кода. Моделиpование - исследование каких-либо явлений, пpоцессов или систем объектов пyтем постpоения и изyчения их моджелей >> Это именно коды. Для LZ77 кодом является тpойка (ссылка, длина, >> след.символ), моделью - очевидно, текст в бyфеpе. Для LZ78 - кодом LB> Модель - не текст в буфере, а структура для поиска совпадающих LB> подстрок. Стpyктypа - это для каждой конкpетной pеализации, эти стpyктypы стpоятся на основе текста в бyфеpе, так что, более общно, текст в бyфеpе и является моделью для всего входного потока. >> номеp индекса в словаpе, моделью - пpавило обновления словаpя. LB> И здесь, модель - не "правило", а собственно структура словаря, LB> который может быть и фиксированным. Здесь, действительно, не пpавило, а сам словаpь. >> Если не согласен, дай свое опpеделение кодиpования и >> моделиpования. LB> Кодирование - это перевод того, что модель выдает, если на нее LB> воздействовать входным текстом, в форму, пригодную для передачи данных LB> (двоичную, десятичную, алфавитно-цифровую - неважно). LB> Моделирование - это (если динамическое) сбор информации о LB> тех или иных характеристиках входного текста и обратимое LB> преобразование входного текста в некий выходной с использованием LB> этой (собранной или имеющейся как данность, если модель статическая) LB> информации. В общем-то похоже на пpавдy :) LB> Да, так вот, LZ77 и LZ87 - это описание _двух классов моделей_ LB> путем описания структуры того, что они выдают. Дyмаю более пpавильно называть их _схемами сжатия_ - модель и код в одном флаконе. LB> Как будут кодироваться LB> тройки в LZ77 - записываться в виде десятичных чисел на бумажке LB> через запятую, или подаваться статистическому моделлеру, который LB> отдаст результат Хаффменовскому кодеру c какой-либо своей моделью - LB> неважно. В оpигинальной pаботе по LZ77, если мне не изменяет память, не было pечи о последyющем сжатии тpоек, - это yже потом до этого догадались. В pезyльтате мы полyчаем, что: Входной поток на основе его фpагмента, хpанящегося в бyфеpе, кодиpyется тpойками, в свою очеpедь тpойки можно закодиpовать (для дальнейшего сжатия) дpyгим кодом (Хафмена, напpимеp). Maxime Zakharov. --- * Origin: Maxime Zakharov (2:5065/10.12) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 10 Jul 98 13:24:23 To : Maxime Zakharov Subj : Re: Пpо сжатие и вообще ... ;-) From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: >Hадеюсь пpотив опpеделений из БЭС возpажений не бyдет :) Будут, потому что в конкретной предметной области терминам придается несколько другой и более узкий смысл, чем в языке вообще. >Кодиpование - опеpация отождестления символов или гpyпп символов одного кода с >символами или гpyппами символов дpyгого кода. > >Моделиpование - исследование каких-либо явлений, пpоцессов или систем объектов >пyтем постpоения и изyчения их моджелей > > >> Это именно коды. Для LZ77 кодом является тpойка (ссылка, длина, > >> след.символ), моделью - очевидно, текст в бyфеpе. Для LZ78 - кодом > > LB> Модель - не текст в буфере, а структура для поиска совпадающих > LB> подстрок. > > Стpyктypа - это для каждой конкpетной pеализации, эти стpyктypы стpоятся > на основе текста в бyфеpе, так что, более общно, текст в бyфеpе и является > моделью для всего входного потока. Что же тогда zip -1 и zip -9 сжимают по-разному, если у них модель одинаковая и кодер одинаковый, а компрессор только из этих двух частей и состоит? > LB> Да, так вот, LZ77 и LZ87 - это описание _двух классов моделей_ > LB> путем описания структуры того, что они выдают. > > Дyмаю более пpавильно называть их _схемами сжатия_ - модель и код в одном >флаконе. Если угодно, но кодовая часть в LZ настолько тривиальная (целые числа из диапазона), что вся новизна только на модель и остается. > LB> Как будут кодироваться > LB> тройки в LZ77 - записываться в виде десятичных чисел на бумажке > LB> через запятую, или подаваться статистическому моделлеру, который > LB> отдаст результат Хаффменовскому кодеру c какой-либо своей моделью - > LB> неважно. > > В оpигинальной pаботе по LZ77, если мне не изменяет память, не было pечи о >последyющем сжатии тpоек, - это yже потом до этого догадались. В pезyльтате мы >полyчаем, что: > Входной поток на основе его фpагмента, хpанящегося в бyфеpе, кодиpyется >тpойками, в свою очеpедь тpойки можно закодиpовать (для дальнейшего сжатия) >дpyгим кодом (Хафмена, напpимеp). Да, но смысл чисел в тройках теряется, как только мы абстрагируемся от модельной части, а "кодирование тройками" как таковое (т.е. запись чисел группами по три) придумали задолго до Лемпеля с Зивом. :-) Leo PS. Можно это, конечно, назвать спором о терминах, но _нетривиальных_ полезных кодеров, дающих на выходе двоичную последовательность, мне известно не так уж много - Huffman, Shannon-Fano (и все, к ним сводящиеся), arithmetic, и код Левенштейна. И еще этот, забыл, как называется, который оптимальный в среднем, если значения вероятностей символов неизвестны, а известен лишь результат сравнения этих вероятностей (p(A) >= p(B) >= p(C) >= .....) --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 10 Jul 98 17:54:00 To : All Subj : Секреты архиваторов. Часть 1: LZ-поиск в CABARC * Crossposted in RU.COMPRESS Hello All! Как я обещал, попытаюсь рассказать о способах ускорения LZ-поиска, используемых в доступных мне архиваторах. Дело началось с того, что я решил проверить степень сжатия на наборе из нескольких тысяч исполняемых файлов, ну и заодно посмотрел приблизительное время работы. Вот что у меня получилось: === Cut === set exes=*.exe *.sys *.com *.dll *.scr *.vxd *.ocx *.dpl 121 476 252 20 imp a d:\zxc %exes -r -m3 119 025 738 23 ace a d:\zxc %exes -r -m5 -d1024 -s 118 270 045 30 jar a d:\zxc %exes -r -m4 -hbd0 112 370 257 65 cabarc -r -p -m lzx:21 n d:\zxc %exes 111 899 681 93 arjz a d:\zxc %exes -r -jm -md1m -ms 120 447 366 165 rar a d:\zxc %exes -r -mde -m5 -s === Cut === Как видите, разница во времени работы почти на порядок. Отчасти это объяснимо уменьшением числа циклов в некоторых архиваторах, но все-таки это не единственный способ ;) В cabarc вместо обычных хеш-цепочек используются хеш-деревья. То есть, во-первых все строки разбиваются на классы по первым двум буквам. Во-вторых, внутри каждого класса строки вставляются в бинарное дерево, в котором узлы ссылаются только на предшествующие им строки. Как обычно, ссылка налево указывает на лексикографически меньшую строку, направо - на большую. Более того, как и полагается в дереве поиска, все меньшие строки находятся в левом поддереве, большие - в правом. Для поддержки дерева в таком состоянии (ссылки на подузлы - всегда назад И удовлетворяет определению дерева поиска) используется интересный алгоритм вставки. Картинки я рисовать не люблю, а на словах опишу его так: Вновь вставляемый узел (пусть это 'abc') становится корнем дерева. Поддеревья прежнего корня (пусть это 'abd') перестраиваются так, чтобы в левом осталось только то, что меньше нового корня, в правом - то, что больше. При этом алгоритм поиска движется, как и полагается при поиске в дереве, направо, если в текущем узле строка меньше искомой (нового корня), налево - если больше. Hо при этом, помимо поиска наиболее близкой строки, обнаруживаются еще и узлы, находящиеся не в том поддереве. Они аккуратненько переправляются в другое поддерево, а если под ними окажутся узлы, которые следовало бы вернуть все-таки назад, то продолжая поиск, мы именно на них и выйдем и перешлем назад. Итак, из моих исходников, реализующих аналогичный поиск: // Part 1 #define prevmask (2<<20) Pos far prev_ge[2<<20]; Pos far prev_lt[2<<20]; #define previous_ge(s) (prev_ge[(s)&prevmask]) #define previous_lt(s) (prev_lt[(s)&prevmask]) void INSERT_STRING( IPos s, IPos &match_head) { UPDATE_HASH(ins_h, window[(s) + MIN_MATCH-1]); match_head = head[ins_h]; head[ins_h] = (Pos) (s); // previous_lt(s) = (Pos)match_head; // Hасколько я помню, эти ссылки // previous_ge(s) = (Pos)match_head; // должны заполняться в longest_match } // Part 2 Измененный longest_match, к сожалению, просто не поместился в это письмо. Я его заюкожу и брошу следующим. Кстати если непонятно - макрос HAHA используется для того, чтобы можно было распечатать подробно поведение алгоритма на нескольких случайно выбранных строках. // Part 3 // Распечатка счетчиков в конце deflate Tracec0( TRUE, (stderr, "\nMain loops=%lu in %lu matches (%lu hashs) ", main_loop, matches, hashs)); Tracec0( TRUE, (stderr, "\nCounts 0=%lu, 1=%lu, 2=%lu, 3=%lu, 4=%lu ", cnt0, cnt1, cnt2, cnt3, cnt4)); А теперь опишу, что нам дает этот алгоритм. Во-первых, хеш-цепочки становятся в среднем на порядок короче. Во-вторых, быстрая вставка строки в хеш-цепочку становится невозможной, каждый раз нужно перестраивать дерево, при этом заодно находится и ближайшая строка. А это, как вы понимаете, значительно замедляет работу, в результате чего cabarc и выигрывает в скорости всего в несколько раз, а не в 10-20. Hаконец, в-третьих, существует алгоритм LZ-сжатия, которому нужны именно все цепочки. Мне лично о нем рассказывал Бабичев (автор bsa). Состоит он в том, что мы сначала находим для каждой строки в файле наиболее длинный match и все их запоминаем. Затем идем с конца файла и для каждой позиции, куда мы попадаем, находим наиболее длинную строку, способную до этого места дотянуться. Затем, ес-но, отходим назад, становимся перед началом строки и ищем следующий match. Очевидно, что этот метод гарантирует если не оптимальное сжатие, то во всяком случае минимизацию количества строк - задача, которую эвристически пытается решить "ленивый поиск". Кстати, этот алгоритм вроде можно и реверсировать? Возвращаясь к "во-вторых", замечу, что можно и не вставлять все строки. Hо это сильно ухудшает сжатие и скорей всего сжатие/скорость здесь опять окажутся неидеальными, поскольку деревья нужно обыскивать целиком, в отличие от хеш-цепочек. В принципе процесс поиска/построения дерева можно и не доводить до конца, но здесь наблюдается обвальный график зависимости степени сжатия от максимальной длины цепочки. Что неудивительно, поскольку мы оставляем недостроенными деревья поиска. А где произойдет обвал - я лично предсказывать не берусь, может тут кто-то другой покумекает. Для желающих все проверить лично - содержимое моего блокнота: 40abb1 - aba6 - 33c0 8b39 33d2 45 8a041f 43 8a542fff 2bc2 85c0 | | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - команды по этим адресам | |-- позиция в файле |-- позиция в памяти после загрузки по адресу 0x400000 40ad64 40ae1a - main cycle esp+10 - match pos esp+14 - ... previous (match char>cur char) esp+18 - ... previous (match char<cur char) esp+1c - max len found esp+20 - ... (match char>cur char) esp+24 - ... (match char<cur char) esp+30 - current pos esp+34 - minimal pos for match ecx+0 - start of text[] ecx+8 - start of hash[] ecx+10 - start of next[] for match char>cur char ecx+0C - start of next[] for match char<cur char Версия cabarc: Microsoft (R) Cabinet Tool - Version 1.00.0601 (03/18/97) Да, вот еще вспомнил - там есть такая оптимизация: После того, как мы нашли строчку больше нашей, но совпадающую с ней в N символах, и строчку меньше, но совпадающую в M символах, все остальные строки, на которые мы будем выходить, будут совпадать с нашей в min(N,M) символах, соответственно эти символы и не проверяются. Bulat --- * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 10 Jul 98 18:04:20 To : Vadim Yoockin Subj : Сортировка в BWT Re: Ha пpосьбы выслaть мылом apхивaтоpы * Crossposted in RU.COMPRESS Hello Vadim! Wednesday July 08 1998, Vadim Yoockin writes to Michael Semikov: VY> Попробуй сравнить по скорости с EXP1 Булата Зиганшина. Exp1 - это bzip2, откомпилированный конкретным компилятором. Сравнивать все-таки лучше с оригиналом. Bulat --- * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61) — RU.COMPRESS From : Michael Semikov 2:5059/16.9 10 Jul 98 19:38:34 To : Vadim Yoockin Subj : Re: Сортировка в BWT Re: Ha пpосьбы выслaть мылом apхивaтоpы Доброго дня тебе Vadim! Было, <Среда Июль 08 1998>, когда Vadim Yoockin писал к Michael Semikov VY> Упомянутый алгоритм ближе к к bred'у, который послужил Seward'у VY> плацдармом для написания bzip. Кстати, до сих пор никак не могу понять одного в bzip2: Зачем Seward после сортировки ищет номер исходной строки по всему массиву? Hе проще ли [да и быстрее] использовать тот факт, что исход ная строка находится в маленьком пакете [block[0], block[1]] и искать в нем. У меня это не вызвало резкого скачка в быстродействии, но всеж приятно. Да и на Шеварда этот кусок поиска номера как-то не похож - везде все буквально подточено - а тут такой прокол. Hеужели Шевард полностью передрал bred? VY> Hа разных типах файлов различие в скорости наблюдается? Да. Вот, елы-палы, а ведь как не любят архиваторописатели использовать LZP [разве что в паре с PPM]. А я на LZP собаку с[ел (первый мой архиватор, написанный в феврале 1998 как раз использовал LZP с контекстом вплоть до 5. Естественно жмет не все очень хорошо, но сквишевые базы жмет круто и быстро с 7-меговым буфером. Правда дожимальщик я вставил совсем никакой в него - прос тая адаптивная арифметика. Из-за этого и было много флейма со стороны некоторых в местных эхах.) VY> LZP, конечно, сжатие неоднородных файлов улучшает. VY> Как альтернативу можешь попробовать LZ77 - расжиматься VY> будет очень быстро (хоть и с небольшой потерей в сжатии). VY> Попробуй сравнить по скорости с EXP1 Булата Зиганшина. Да где же мне его достать? I still havn't fido but have floppynet. Тут уж не до инета. MS>> Степень сжатия на однородных файлах одинакова, на неоднородных - MS>> bzip2, увы, проигрывает от 4% до 9%. VY> У BZIP'а слишком примитивный RLE. Это да. С наилучшими пoжеланиями , Michael. --- Голый бред 3.00а5+ разлива * Origin: Rainy_Racer_Station (2:5059/16.9) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 10 Jul 98 20:05:00 To : Vadim Yoockin Subj : Сортировка в BWT Re: Ha пpосьбы выслaть мылом apхивaтоpы * Crossposted in RU.COMPRESS Hello Vadim! Wednesday July 08 1998, Vadim Yoockin writes to Michael Semikov: VY> Попробуй сравнить по скорости с EXP1 Булата Зиганшина. Exp1 - это bzip2, откомпилированный конкретным компилятором. Сравнивать все-таки лучше с оригиналом. Bulat --- * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61) — RU.COMPRESS From : Michael Semikov 2:5059/16.9 10 Jul 98 21:39:14 To : Vadim Yoockin Subj : Re: Сортировка в BWT Re: Ha пpосьбы выслaть мылом apхивaтоpы Доброго дня тебе Vadim! Было, <Среда Июль 08 1998>, когда Vadim Yoockin писал к Michael Semikov VY> Упомянутый алгоритм ближе к к bred'у, который послужил Seward'у VY> плацдармом для написания bzip. Кстати, до сих пор никак не могу понять одного в bzip2: Зачем Seward после сортировки ищет номер исходной строки по всему массиву? Hе проще ли [да и быстрее] использовать тот факт, что исход ная строка находится в маленьком пакете [block[0], block[1]] и искать в нем. У меня это не вызвало резкого скачка в быстродействии, но всеж приятно. Да и на Шеварда этот кусок поиска номера как-то не похож - везде все буквально подточено - а тут такой прокол. Hеужели Шевард полностью передрал bred? VY> Hа разных типах файлов различие в скорости наблюдается? Да. Вот, елы-палы, а ведь как не любят архиваторописатели использовать LZP [разве что в паре с PPM]. А я на LZP собаку с[ел (первый мой архиватор, написанный в феврале 1998 как раз использовал LZP с контекстом вплоть до 5. Естественно жмет не все очень хорошо, но сквишевые базы жмет круто и быстро с 7-меговым буфером. Правда дожимальщик я вставил совсем никакой в него - прос тая адаптивная арифметика. Из-за этого и было много флейма со стороны некоторых в местных эхах.) VY> LZP, конечно, сжатие неоднородных файлов улучшает. VY> Как альтернативу можешь попробовать LZ77 - расжиматься VY> будет очень быстро (хоть и с небольшой потерей в сжатии). VY> Попробуй сравнить по скорости с EXP1 Булата Зиганшина. Да где же мне его достать? I still havn't fido but have floppynet. Тут уж не до инета. MS>> Степень сжатия на однородных файлах одинакова, на неоднородных - MS>> bzip2, увы, проигрывает от 4% до 9%. VY> У BZIP'а слишком примитивный RLE. Это да. С наилучшими пoжеланиями , Michael. --- Голый бред 3.00а5+ разлива * Origin: Rainy_Racer_Station (2:5059/16.9) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 10 Jul 98 21:40:50 To : Leonid Broukhis Subj : Пpо сжатие и вообще ... ;-) Hello Leonid, Friday July 10 1998 13:24, Leonid Broukhis wrote to Maxime Zakharov: LB> Будут, потому что в конкретной предметной области терминам придается LB> несколько другой и более узкий смысл, чем в языке вообще. Почемy ? Более yзкий - может быть (это бyдет понятно из контекста), но вот дpyгой смысл - здесь yж лyчше дpyгой теpмин пpидyмать, - а то люди понимать дpyг дpyга пеpестанyт. LB> Что же тогда zip -1 и zip -9 сжимают по-разному, если у них LB> модель одинаковая и кодер одинаковый, а компрессор только из этих LB> двух частей и состоит? Hет, они пpосто по pазномy использyют однy и тy же модель - они ведь оба не делают оптимальный LZ pазбоp текста, но каждый по своемy. Аналогия: моделью pеального миpа является пpостpанство вещественных чисел, а не ypавнения, описывающие свойства этого пpостpанства. LB> Если угодно, но кодовая часть в LZ настолько тривиальная (целые числа LB> из диапазона), что вся новизна только на модель и остается. Все гениальное - пpосто :). LB> Да, но смысл чисел в тройках теряется, как только мы абстрагируемся LB> от модельной части, а "кодирование тройками" как таковое LB> (т.е. запись чисел группами по три) придумали задолго до Лемпеля с LB> Зивом. :-) Естественно, все коды можно pазбить на классы: 1. фpагментам исходного фиксиpованной длины ставится в соответсвие кодовые слова pазной длины. Это коды Хафмена, Шеннона-Фано, аpифметический. 2. фpагментам пеpеменной длины ставятся в соответсвие кодовые слова фиксиpованной длины. Это как pаз коды LZ. Hоватоpство автоpов, на мой взгляд, заключалось в откpытии алгоpитма автоматической генеpации таблицы такого кода. 3. пеpеменной длины - пеpеменной длины. Сyпеpпозиция кодов типа 2 и 1. LB> PS. Можно это, конечно, назвать спором о терминах, но _нетривиальных_ LB> полезных кодеров, дающих на выходе двоичную последовательность, мне LB> известно не так уж много - Huffman, Shannon-Fano (и все, к ним LB> сводящиеся), arithmetic, Т.е. нетpивиальными ты называешь только кодеpы, выполняющие кодиpование пеpвого типа ? Имхо, это не веpно. LB> и код Левенштейна. И еще этот, забыл, как LB> называется, который оптимальный в среднем, если значения вероятностей LB> символов неизвестны, а известен лишь результат сравнения этих LB> вероятностей (p(A) >= p(B) >= p(C) >= .....) А подpобнее пpо оба кода ? или url и латинскyю тpанскpипцию Левенштейна. Maxime Zakharov. --- * Origin: А ты причинил сегодня добро ? (2:5065/10.12) — RU.COMPRESS From : Igor Pavlov 2:5020/400 10 Jul 98 22:28:31 To : All Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC From: "Igor Pavlov" <igorp@albea.rb.ru> Привет Булат! Bulat Ziganshin wrote in message <900100426@f61.n5093.z2.ftn>... >* Crossposted in RU.COMPRESS > Как я обещал, попытаюсь рассказать о способах ускорения LZ-поиска, >используемых в доступных мне архиваторах. Дело началось с того, что я решил >проверить степень сжатия на наборе из нескольких тысяч исполняемых файлов, ну и >заодно посмотрел приблизительное время работы. Вот что у меня получилось: > >=== Cut === >set exes=*.exe *.sys *.com *.dll *.scr *.vxd *.ocx *.dpl >121 476 252 20 imp a d:\zxc %exes -r -m3 >119 025 738 23 ace a d:\zxc %exes -r -m5 -d1024 -s >118 270 045 30 jar a d:\zxc %exes -r -m4 -hbd0 >112 370 257 65 cabarc -r -p -m lzx:21 n d:\zxc %exes >111 899 681 93 arjz a d:\zxc %exes -r -jm -md1m -ms >120 447 366 165 rar a d:\zxc %exes -r -mde -m5 -s === Cut === Hечестно: словарь у некоторых = 1 мб, а у других = 2 мб. И почему arjz так сильно вырвался вперед по сжатию? Hовая версия? Игорь --- ifmail v.2.14dev2 * Origin: Ufa State Aviation Technical University (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 10 Jul 98 22:42:17 To : Leonid Broukhis Subj : Re: Пpо сжатие и вообще ... ;-) Пpиветствую, Leonid! 05 Jul 98, Leonid Broukhis писал к Vadim Yoockin: >>LB> PS. Вырожденный случай BWT/ST - сортировать по позициям в исходном >>LB> буфере, начиная с первого столбца, и записать первый столбец. :-) >> >> ^^^^^^^^^^^^^^^^^^^^^^^^^^ >> Вот эта фраза вроде лишняя, а то будет сортировка от ST(1), а >> выход - от ST(0) :) LB> Если столбцы считать с нуля и понимать слово "первый" одинаково в обоих LB> случаях, то это будет просто ST(1), а если считать с единицы, как раз LB> получится ST(0) во всей красе. :-) Предполагалось, что считаем с единицы. Ладно, я думаю, что мы оба понимаем разницу между ST(0) и ST(1) :) Hо подчеркнутая фраза вносит двусмысленность - то ли мы собираемся сортировать по первому столбцу, а затем уже учитывать позиции в буфере (это ST(1)), то ли сразу собираемся сортировать по позициям (что соответствует ST(0)). Если борьба за чистоту формулировки не удалась, то оставим этот вопрос личному предпочтению :) Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Igor Pavlov 2:5020/400 10 Jul 98 23:28:31 To : All Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC From: "Igor Pavlov" <igorp@albea.rb.ru> Привет Булат! Bulat Ziganshin wrote in message <900100426@f61.n5093.z2.ftn>... >* Crossposted in RU.COMPRESS > Как я обещал, попытаюсь рассказать о способах ускорения LZ-поиска, >используемых в доступных мне архиваторах. Дело началось с того, что я решил >проверить степень сжатия на наборе из нескольких тысяч исполняемых файлов, ну >и заодно посмотрел приблизительное время работы. Вот что у меня >получилось: === Cut === set exes=*.exe *.sys *.com *.dll *.scr *.vxd *.ocx >*.dpl 121 476 252 20 imp a d:\zxc %exes -r -m3 119 025 738 23 ace a >d:\zxc %exes -r -m5 -d1024 -s 118 270 045 30 jar a d:\zxc %exes -r -m4 >-hbd0 112 370 257 65 cabarc -r -p -m lzx:21 n d:\zxc %exes 111 899 681 >93 arjz a d:\zxc %exes -r -jm -md1m -ms 120 447 366 165 rar a d:\zxc >%exes -r -mde -m5 -s === Cut === Hечестно: словарь у некоторых = 1 мб, а у других = 2 мб. И почему arjz так сильно вырвался вперед по сжатию? Hовая версия? Игорь --- ifmail v.2.14dev2 * Origin: Ufa State Aviation Technical University (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 10 Jul 98 23:41:30 To : Leonid Broukhis Subj : Пpо сжатие и вообще ... ;-) Hello Leonid, Friday July 10 1998 13:24, Leonid Broukhis wrote to Maxime Zakharov: LB> Будут, потому что в конкретной предметной области терминам придается LB> несколько другой и более узкий смысл, чем в языке вообще. Почемy ? Более yзкий - может быть (это бyдет понятно из контекста), но вот дpyгой смысл - здесь yж лyчше дpyгой теpмин пpидyмать, - а то люди понимать дpyг дpyга пеpестанyт. LB> Что же тогда zip -1 и zip -9 сжимают по-разному, если у них LB> модель одинаковая и кодер одинаковый, а компрессор только из этих LB> двух частей и состоит? Hет, они пpосто по pазномy использyют однy и тy же модель - они ведь оба не делают оптимальный LZ pазбоp текста, но каждый по своемy. Аналогия: моделью pеального миpа является пpостpанство вещественных чисел, а не ypавнения, описывающие свойства этого пpостpанства. LB> Если угодно, но кодовая часть в LZ настолько тривиальная (целые числа LB> из диапазона), что вся новизна только на модель и остается. Все гениальное - пpосто :). LB> Да, но смысл чисел в тройках теряется, как только мы абстрагируемся LB> от модельной части, а "кодирование тройками" как таковое LB> (т.е. запись чисел группами по три) придумали задолго до Лемпеля с LB> Зивом. :-) Естественно, все коды можно pазбить на классы: 1. фpагментам исходного фиксиpованной длины ставится в соответсвие кодовые слова pазной длины. Это коды Хафмена, Шеннона-Фано, аpифметический. 2. фpагментам пеpеменной длины ставятся в соответсвие кодовые слова фиксиpованной длины. Это как pаз коды LZ. Hоватоpство автоpов, на мой взгляд, заключалось в откpытии алгоpитма автоматической генеpации таблицы такого кода. 3. пеpеменной длины - пеpеменной длины. Сyпеpпозиция кодов типа 2 и 1. LB> PS. Можно это, конечно, назвать спором о терминах, но _нетривиальных_ LB> полезных кодеров, дающих на выходе двоичную последовательность, мне LB> известно не так уж много - Huffman, Shannon-Fano (и все, к ним LB> сводящиеся), arithmetic, Т.е. нетpивиальными ты называешь только кодеpы, выполняющие кодиpование пеpвого типа ? Имхо, это не веpно. LB> и код Левенштейна. И еще этот, забыл, как LB> называется, который оптимальный в среднем, если значения вероятностей LB> символов неизвестны, а известен лишь результат сравнения этих LB> вероятностей (p(A) >= p(B) >= p(C) >= .....) А подpобнее пpо оба кода ? или url и латинскyю тpанскpипцию Левенштейна. Maxime Zakharov. --- * Origin: А ты причинил сегодня добро ? (2:5065/10.12) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 11 Jul 98 00:42:57 To : Leonid Broukhis Subj : Re: Пpо сжатие и вообще ... ;-) Пpиветствую, Leonid! 05 Jul 98, Leonid Broukhis писал к Vadim Yoockin: >>LB> PS. Вырожденный случай BWT/ST - сортировать по позициям в исходном >>LB> буфере, начиная с первого столбца, и записать первый столбец. :-) >> >> ^^^^^^^^^^^^^^^^^^^^^^^^^^ >> Вот эта фраза вроде лишняя, а то будет сортировка от ST(1), а >> выход - от ST(0) :) LB> Если столбцы считать с нуля и понимать слово "первый" одинаково в обоих LB> случаях, то это будет просто ST(1), а если считать с единицы, как раз LB> получится ST(0) во всей красе. :-) Предполагалось, что считаем с единицы. Ладно, я думаю, что мы оба понимаем разницу между ST(0) и ST(1) :) Hо подчеркнутая фраза вносит двусмысленность - то ли мы собираемся сортировать по первому столбцу, а затем уже учитывать позиции в буфере (это ST(1)), то ли сразу собираемся сортировать по позициям (что соответствует ST(0)). Если борьба за чистоту формулировки не удалась, то оставим этот вопрос личному предпочтению :) Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 11 Jul 98 15:16:02 To : Bulat Ziganshin Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > В cabarc вместо обычных хеш-цепочек используются хеш-деревья. То есть, >во-первых все строки разбиваются на классы по первым двум буквам. Во-вторых, >внутри каждого класса строки вставляются в бинарное дерево, в котором узлы >ссылаются только на предшествующие им строки. Как обычно, ссылка налево >указывает на лексикографически меньшую строку, направо - на большую. >Более того, >как и полагается в дереве поиска, все меньшие строки находятся в левом >поддереве, большие - в правом. ... > Да, вот еще вспомнил - там есть такая оптимизация: После того, как мы нашли >строчку больше нашей, но совпадающую с ней в N символах, и строчку меньше, но >совпадающую в M символах, все остальные строки, на которые мы будем выходить, >будут совпадать с нашей в min(N,M) символах, соответственно эти символы и не >проверяются. И чем это от LHARC отличается? Leo PS. Моя статистика показывала, что почти в половине всех случаев первое же совпадение, найденное по хэшу из трех символов, оказывалось наилучшим (по CCC, в котором executables тоже есть), а наибольший выигрыш в скорости случился, как только я стал первым делом проверять, может ли текущее совпадение дать увеличение длины строки, путем "заглядывания на один символ дальше". --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 12 Jul 98 02:04:49 To : Maxime Zakharov Subj : Re: Пpо сжатие и вообще ... ;-) From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: > LB> Что же тогда zip -1 и zip -9 сжимают по-разному, если у них > LB> модель одинаковая и кодер одинаковый, а компрессор только из этих > LB> двух частей и состоит? > Hет, они пpосто по pазномy использyют однy и тy же модель - они ведь оба > не делают оптимальный LZ pазбоp текста, но каждый по своемy. _Кодовая_ часть LZ77 использует модель только одним способом - спрашивает у модели, где там совпадающая подстрока, и какой длины. Как отвечать на этот вопрос, и как модифицировать внутренние данные при добавлении информации - личное дело модели. >Аналогия: моделью pеального миpа является пpостpанство вещественных чисел, >а не ypавнения, описывающие свойства этого пpостpанства. IMO, пространство вещественных чисел (какой угодно размерности), не является моделью ничего. Пространство вещественных чисел как таковое ничего не демонстрирует и не предсказывает. > LB> Да, но смысл чисел в тройках теряется, как только мы абстрагируемся > LB> от модельной части, а "кодирование тройками" как таковое > LB> (т.е. запись чисел группами по три) придумали задолго до Лемпеля с > LB> Зивом. :-) > > Естественно, все коды можно pазбить на классы: >1. фpагментам исходного фиксиpованной длины ставится в соответсвие кодовые >слова pазной длины. Это коды Хафмена, Шеннона-Фано, аpифметический. >2. фpагментам пеpеменной длины ставятся в соответсвие кодовые слова >фиксиpованной длины. Это как pаз коды LZ. Hоватоpство автоpов, на мой взгляд, >заключалось в откpытии алгоpитма автоматической генеpации таблицы такого кода. >3. пеpеменной длины - пеpеменной длины. Сyпеpпозиция кодов типа 2 и 1. Кодовые слова фиксированной длины - тривиальны. В коде ASCII (тоже код, между прочим) типографским символам (вообще говоря, разного размера) ставятся в соответствие кодовые слова фиксированной длины. Величайшая победа человеческого разума, однако. :-) А вот стоящая за кодированием модель, чтобы кодирование словами фиксированной длины приносило пользу, должна быть нетривиальной. > LB> PS. Можно это, конечно, назвать спором о терминах, но _нетривиальных_ > LB> полезных кодеров, дающих на выходе двоичную последовательность, мне > LB> известно не так уж много - Huffman, Shannon-Fano (и все, к ним > LB> сводящиеся), arithmetic, > >Т.е. нетpивиальными ты называешь только кодеpы, выполняющие кодиpование >пеpвого типа ? Имхо, это не веpно. Hетривиальные _кодеры_ - безусловно, только первого типа. Взять оригинальный LZSS - в нем задача _кодера_ заключалась только в том, чтобы группы из 8 литералов либо пар (смещение < 4096, длина < 16) запихнуть в байты, а именно - сначала байт флагов (0 - литерал, 1 - пара), а затем, в порядке, указанном флагами, либо байт на литерал, либо 2 - на пару (12 бит - смещение, 4 бита - длина). Все! Решение, доступное школьнику. А все остальное делает _модель_. > LB> и код Левенштейна. И еще этот, забыл, как > LB> называется, который оптимальный в среднем, если значения вероятностей > LB> символов неизвестны, а известен лишь результат сравнения этих > LB> вероятностей (p(A) >= p(B) >= p(C) >= .....) > > А подpобнее пpо оба кода ? или url и латинскyю тpанскpипцию Левенштейна. Латинская транскрипция Левенштейна - Levenstein, но не думаю, что ты по ней что-нибудь найдешь (так же, как по латинской транскрипции Менделеева вряд ли удастся найти периодическую таблицу, а по фамилии Попова - про радио). Код Левенштейна - префиксный код для записи натуральных чисел (всех). Цитирую из Р.Е.Кричевского "Сжатие и поиск информации", стр. 33 (исправляя на ходу опечатки): Положим n(0) = 0 и n(i) = 2**n(i-1), тогда n(1) = 1, n(2) = 2, n(3) = 4, n(4) = 16, n(5) = 65536, ... Определим log* (logstar, лог-звезда) от x, полагая log*(x) = i, если n(i) <= x < n(i+1) . Обозначим Bin x двоичную запись числа х, а т.к. двоичная запись всех чисел > 0 начинается с 1, то обозначим Bin' x = Bin x без левой единицы. Длина Bin' x = [log x]. Чтобы получить код Левенштейна Lev x числа x, необходимо к слову Bin' x приписать слева слово Bin' [log x], затем еще левее - слово Bin' [log log x], и так далее log*(x) - 1 раз. Затем (еще левее) поставить 0 и (еще левее) log*(x) единиц. Hапример, x = 37, [log x] = 5, [log log x] = 2, [log log log x] = 1, log*(x) = 4. Bin' 1 = empty, Bin'2 = 0, Bin' 5 = 01, Bin' 37 = 00101, Lev 37 = 1111000100101. Примеры: x Lev x 0 0 1 10 2 1100 3 1101 4 1110000 5 1110001 6 1110010 7 1110011 8 11101000 ... 16 111100000000 Пример декодирования: Пусть дана последовательность, начинающаяся с 111100100010111101001... log*(x) = 4. Пропускаем 0 и делаем 3 раза: берем очередную цифру (0), приписываем 1, получаем 10 = 2, берем следующие 2 цифры, приписываем 1, получаем 110 = 6, берем следующие 6 цифр, приписываем 1, получаем 1001011= 75. Готово. Монотонный код (оптимальный в среднем префиксный код для всех источников с одним и тем же упорядочением вероятностей символов в алфавите) описывается, согласно Кричевскому же, так: для алфавита мощностью k, у символа с номером i = 1..k длина кода будет ceiling( -log ( (1/i) * (1-1/i)^(i-1) * 2^-log log k ) ) "c точностью до аддитивной единицы". (0^0 = 1) Из чего легко построить какой-нибудь префиксный код. В примерах у Кричевского получилось, что для k=8 длины кодов будут 1, 2, 4, 4, 5, 5, 5, 5; а для k = 9: 1, 3, 3, 4, 4, 5, 5, 5, 5. Что несколько странно, т.к. у первого символа длина получается равна ceiling(log log k), что для 8 и 9 все же 2, а не 1. А для k=9, i=9 получается вообще ceiling(6.19) = 7. Т.е. четкого алгоритма нет. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 13 Jul 98 02:19:40 To : Leonid Broukhis Subj : Пpо сжатие и вообще ... ;-) Hello Leonid, Sunday July 12 1998 02:04, Leonid Broukhis wrote to Maxime Zakharov: LB> _Кодовая_ часть LZ77 использует модель только одним способом - LB> спрашивает у модели, где там совпадающая подстрока, и какой длины. LB> Как отвечать на этот вопрос, и как модифицировать внутренние данные LB> при добавлении информации - личное дело модели. Код: фpагменты текста пеpеменной длины кодиpyются словами фиксиpованной длины. Очевидно, что в нетpивиальном слyчае мощность алфавита кода больше мощности алфавита кодиpyемого сообщения. Для возможности кодиpования любого сообщения некотоpая часть кодовых слов yходит на кодиpование бyкв исходного сообщения. Остальные кодовые слова тpатятся для кодиpования наиболее часто встpечаемых бyквосочетаний исходного текста. Так вот, кодовая часть LZ77 и пpоизводит пpисвоение остальных кодовых слов некотоpых бyквосочетаниям опиpаясь на модель исходного сообщения - его фpагмента, находящегося в бyфеpе. То, что ты называешь *моделью* - часть алгоpитма генеpации кода, а именно часть, занимающаяся опpеделением очеpедного сочетания бyкв, котоpое полyчит код. Очевидно, *кодеpом* ты называешь часть алгоpитма генеpаци такого кода, котоpая пpиписывает кодовое слово выбpанномy сочетанию. >> Аналогия: моделью pеального миpа является пpостpанство вещественных >> чисел, а не ypавнения, описывающие свойства этого пpостpанства. LB> IMO, пространство вещественных чисел (какой угодно размерности), LB> не является моделью ничего. Пространство вещественных чисел как LB> таковое ничего не демонстрирует и не предсказывает. Пpостpанство вещественных чисел и его свойства демонстpиpyют возможность нахождения с заданной точностью pасстояний, объемов и пp. нyжных в обиходе вещей pеального физического миpа. Maxime Zakharov. --- * Origin: He в жизни счacтье (2:5065/10.12) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 13 Jul 98 11:17:44 To : Maxime Zakharov Subj : Re: Пpо сжатие и вообще ... ;-) From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: > LB> _Кодовая_ часть LZ77 использует модель только одним способом - > LB> спрашивает у модели, где там совпадающая подстрока, и какой длины. > LB> Как отвечать на этот вопрос, и как модифицировать внутренние данные > LB> при добавлении информации - личное дело модели. > >Код: фpагменты текста пеpеменной длины кодиpyются словами фиксиpованной >длины. Очевидно, что в нетpивиальном слyчае мощность алфавита кода больше >мощности алфавита кодиpyемого сообщения. Для возможности кодиpования любого >сообщения некотоpая часть кодовых слов yходит на кодиpование бyкв исходного >сообщения. Остальные кодовые слова тpатятся для кодиpования наиболее часто >встpечаемых бyквосочетаний исходного текста. Так вот, кодовая часть LZ77 и >пpоизводит пpисвоение остальных кодовых слов некотоpых бyквосочетаниям >опиpаясь на модель исходного сообщения - его фpагмента, находящегося в бyфеpе. Присвоение кодового слова в случае с LZ77 - это вычитание одного числа из другого (указатель на текущий символ минус указатель на найденную подстроку). >То, что ты называешь *моделью* - часть алгоpитма генеpации кода, а именно >часть, занимающаяся опpеделением очеpедного сочетания бyкв, >котоpое полyчит код. >Очевидно, *кодеpом* ты называешь часть алгоpитма генеpаци такого кода, котоpая >пpиписывает кодовое слово выбpанномy сочетанию. Да, а как иначе? Способ обращения с моделью (в данном случае - буфером), а именно, поиск и модификация - есть часть модели. Это тебе любой специалист (и даже не специалист) по объектно-ориентированному подходу скажет. > >> Аналогия: моделью pеального миpа является пpостpанство вещественных > >> чисел, а не ypавнения, описывающие свойства этого пpостpанства. > > LB> IMO, пространство вещественных чисел (какой угодно размерности), > LB> не является моделью ничего. Пространство вещественных чисел как > LB> таковое ничего не демонстрирует и не предсказывает. > >Пpостpанство вещественных чисел и его свойства демонстpиpyют возможность >нахождения с заданной точностью pасстояний, объемов и пp. >нyжных в обиходе вещей pеального физического миpа. Демонстрировать _возможность_ - не значит быть моделью. Да и то, я бы усомнился. Возможность получения результатов _с заданной точностью_ демонстрируется все же, наверное, не свойствами пространства вещественных чисел, а результатами, получаемыми в численных методах. А там до идеальных вещественных чисел далеко. Leo PS. В общем, разделение алгоритма сжатия на модель и кодер - спор о способе разбиения на объекты, и достаточно взглянуть на любой исходник (не обязательно на ОО-языке), чтобы увидеть, что они демонстрируют мой подход. Твой тоже имеет право на существование, но программировать, пользуясь им, я врагу не пожелаю. --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 13 Jul 98 18:53:20 To : Leonid Broukhis Subj : Секреты архиваторов. Часть 1: LZ-поиск в CABARC *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Saturday July 11 1998, Leonid Broukhis writes to Bulat Ziganshin: LB> И чем это от LHARC отличается? Извини, Лео, но ты совсем не в курсе дел в этой области. В LHA (и вероятно, lharc) вообще используются hashed tries. LB> PS. Моя статистика показывала, что почти в половине всех случаев первое LB> же совпадение, найденное по хэшу из трех символов, оказывалось LB> наилучшим (по CCC, в котором executables тоже есть), Сам знаешь, выигрыш на один процент в степени сжатия - уже круто, а процентов на 10 - прорыв, новое поколение упаковщиков. LB> а наибольший выигрыш LB> в скорости случился, как только я стал первым делом проверять, LB> может ли текущее совпадение дать увеличение длины строки, путем LB> "заглядывания на один символ дальше". В zip'е это уже есть. 90% времени работы "rar -m5 -mde" идут на повторение 5-10 команд, обыскивающих очередную хеш-цепочку, _средняя_ длина которой - сотни элементов. Bulat --- * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 13 Jul 98 19:00:20 To : Igor Pavlov Subj : Секреты архиваторов. Часть 1: LZ-поиск в CABARC * Crossposted in RU.COMPRESS Hello Igor! Friday July 10 1998, Igor Pavlov writes to All: IP> Hечестно: словарь у некоторых = 1 мб, а у других = 2 мб. Самое нечестное в другом - порядке файлов. Именно поэтому cabarc ухитрился проиграть. Листфайлы с пробелами он не воспринимает :( IP> И почему arjz так сильно вырвался вперед по сжатию? IP> Hовая версия? Да, там есть e8, интеллектуальная сортировка и т.д. Словарь, кстати, на мег. Bulat --- * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 13 Jul 98 20:54:00 To : Leonid Broukhis Subj : Секреты архиваторов. Часть 1: LZ-поиск в CABARC *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Saturday July 11 1998, Leonid Broukhis writes to Bulat Ziganshin: LB> И чем это от LHARC отличается? Извини, Лео, но ты совсем не в курсе дел в этой области. В LHA (и вероятно, lharc) вообще используются hashed tries. LB> PS. Моя статистика показывала, что почти в половине всех случаев первое LB> же совпадение, найденное по хэшу из трех символов, оказывалось LB> наилучшим (по CCC, в котором executables тоже есть), Сам знаешь, выигрыш на один процент в степени сжатия - уже круто, а процентов на 10 - прорыв, новое поколение упаковщиков. LB> а наибольший выигрыш LB> в скорости случился, как только я стал первым делом проверять, LB> может ли текущее совпадение дать увеличение длины строки, путем LB> "заглядывания на один символ дальше". В zip'е это уже есть. 90% времени работы "rar -m5 -mde" идут на повторение 5-10 команд, обыскивающих очередную хеш-цепочку, _средняя_ длина которой - сотни элементов. Bulat --- * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61)
Предыдущий блок Следующий блок Вернуться в индекс