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 кб :).