Info Guide
#06
03 декабря 2004 |
|
Sofтинка - преимущества упаковочного алгоритма Optimal LZH.
>> Игорь Павлов ведёт проект 7-zip, от него в конференции я >> узнал про алгоритм optimal lzh - когда выбирается >> действительно оптимальный способ подбора строк при уже >> существующем дереве кодов длин и расстояний. DB> ХАЧУ этот алгоритм. Держи! Этот алгоритм реально нужен каждому пакеру на спектруме. Я дол- жен был его реализовать для всех хрумов,хрустов и лазеркомпактов три-четыре года назад. Айяйяй в общем. Для "намертво" зашитых кодов, как это сделано в большинстве пакеров на спеке, этот алгоритм принесёт около, боюсь сказать, 2-20%. На пакерах типа RIP до примерно 1-10%. Это навскидку. Конечно, памяти много надо на паковку, тормозить будет серьёзно, но есть различные варианты - на куски какой длины разбить файл и прочее.Да хоть на PC можно паковать. --------хрум-------- Игорь Павлов писал в RU.COMPRESS в 1999 году. Алгоритм оптимального Lempel-Ziv-Huffman кодирования ---------------------------------------------------- 1) Поиск совпадений в словарю осуществляется для каждого смещения. При поиске дополнительно собираем информацию об оптимальных (по расстоянию) совпадениях с длинами от 2 до длины максимального совпадения. Offsets[] = Get_Longest_And_Other_Good_Matches(); // Offsets.Size = length of longest match. // Offsets[i] = back offset in dictionary for match with len=i. BYTE Get_Current_Literal(); // returns current byte 2) Всегда можем посчитать, сколько предположительно бит займёт любой вариант (match/literal) на основе информации о предыдущих huffman блоках: int Get_Match_Huffman_Price(int Length, int Offset); // Length = length of match // Offset = offset of match; // Result = number of bits for coding this match; int Get_Literal_Huffman_Price(BYTE Literal); // Result = number of bits for coding this Literal; 3) Cтроим оптимальную последовательность кодов на много ходов вперёд. Есть большой массив a[]: a[i] = { int Price; // Цена пути в битах,чтобы добраться до i-го байта. struct { int Prev; // Позиция,откуда мы прыгаем в текущую(=i) позицию // для Literal: Prev = i - 1 // для Match'а с длиной Length: Prev = i - Length int Offset; // Смещ. в буфере(словаре)назад в случае Мatch'а // для записи Мatch'а от Prev до i } } a) Для всех элементов a[] устанавливаем Price = бесконечность. b) for(int i=0; i < Big_Value; i++) { // Существуют некоторые условия досрочного вых. из этого цикла // Получаем массив Offsets[2..Longest_match_length] смещений в // буфере (словаре) назад, смотри 1). Offsets[] = Get_Longest_And_Other_Good_Matches(); for(int Len = 1; Len < Offsets[].Length; Len++) // Len=1 means Literal { // Определяем цену в битах рассматриваемого "прыжка" на Len // символов вперёд if (Len == 1) // it's a literal aPrice = Get_Literal_Huffman_Price(Get_Current_Literal()); else aPrice = Get_Match_Huffman_Price(Len, Offsets[Len]); // и вычисляем цену нового кандидата в a[i + Len]. aNewPrice = a[i].Price + aPrice; if (aNewPrice < a[i + Len].Price ) // Если выгодно старый путь (старая цена может быть даже // равна бесконечности,т.е.вообще ещё нет пути) заменить // новым, то меняем a[i + Len], чтобы он указывал на i { a[i + Len].Price = aNewPrice; a[i + Len].Prev = i; a[i + Len].Offset = Offsets[Len]; } } } c) Двигаясь по a[] от конца, собираем "оптимальные" match/literal последовательности и кодируем их. End. --------хрум-------- >> В общем, мое отношение смотри выше, но вот есть же другая >> интересная вещь - просто поддержать распаковку LZMA на >> спектруме. Правда, мне кажется, будет неудобно использовать >> распаковщик LZMA для программ на спектруме. DB> Но можно применить для журналов или больших справочников. DB> Например, Open Letters на одном диске ;) >> PS. Перечитал твоё письмо и понял, что исходники тебе >> прислали... DB> Там без поллитры не въедешь - 1021 файл, 3.4 мегабайта DB> исходников. Мусорка. Ну, поллитра не проблема :). Там и с поллитрой не въедешь. Ты не пробовал изучить просто декодер, тот, который в файле SRC7zipCompressLZMA_Clzmadecode.c, там всего 23 кб :).
Другие статьи номера:
Похожие статьи:
В этот день... 14 декабря