>> Игорь Павлов ведёт проект 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 кб :).
