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



Другие статьи номера:

Inferno - Вступление от редактора.

Интервью - интервью с AIG - кодером из группы MKHG.

Sofтинка - ACE 0.888: отличия от 0.666

Sofтинка - макро-ассемблер отладчик ALASM 4.47: отличия от 4.44

For Coderz - Арифметическое кодирование.

Inferno - Авторы журнала.

Sofтинка - BGE 4 графический редактор для ZX.

События - The Compo 2: результаты голосования.

For Coderz - Декомпиляция программ - оживление старых прог.

Inferno - Ошибки в предыдущих номерах.

For Coderz - Маленькие программерские хитрости.

DIY - Схема моего электрофумигатора.

Gameland - о пройденных играх: Imperia 2, Hexagonal Filler, From Beyond.

Железо - устройство расширенной клавиатуры (58 клавиш).

Gamedev - Игровой цикл - цикл, внутри которого вызываются все подпрограммы игры.

Gameland - прохождение Lords of Time от Level 9.

For Coderz - Макросы ч.2 - облегчаем себе жизнь при программировании.

Inferno - Письма в редакцию.

Gameland - прохождение уровней игры Чёрный Ворон.

For Coderz - Описание модульной структуры программ.

Inferno - Об оболочке.

Sofтинка - преимущества упаковочного алгоритма Optimal LZH.

События - серпуховский фестиваль ParaDiGMus party 2003. Как это было.

События - серпуховский фестиваль ParaDiGMus party 2003. Afterparty.

Gameland - прохождение игры The Price of Magik от Level 9.

Железо - Описание блока памяти от принтера Robotron CM 6329.01 M. Часть 1.

Железо - Описание блока памяти от принтера Robotron CM 6329.01 M. Часть 2.

Реклама - реклама и объявления.

DIY - советы по ремонту часов, Dream Cast и джойстика.

Интервью - Интервью с Shaitan/Stars of Keladan: Interred Inferno.

Gameland - прохождение игры Snowball от Level 9.

Железо - Видеомагнитофон GoldStar RN800AW Art vision. История ремонта.

Железо - Видеомагнитофон GoldStar RN800AW Art vision. Советы по разборке и ремонту.

Интервью - интервью с музыкантом Visual^Extreme (Сергей Агапов).

Gamedev - о сборке игры Wolfenstein 2004. Часть 1.

Gamedev - о сборке игры Wolfenstein 2004. Часть 2.

For Coderz - Как получить на звуковом устройстве больше бит.


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Новости - новости из других городов: "- Спектрумом в нашем городе занимаются все меньше и меньше людей.Даже Хропов Вовка (IMP) продал свой Pentagon за 70$".
Компиляторы - Многие думают, что хорошую быстродействующую программу на 8-ми разрядной машине можно написать только в кодах процессора...
Реклама - пpиобpету pазличную инфоpмацию по "железу" ZX Spectrum.

В этот день...   19 июля