-
Notifications
You must be signed in to change notification settings - Fork 3
/
optimal_lzh.txt
131 lines (104 loc) · 4.36 KB
/
optimal_lzh.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
Оптимальный LZH
From : [email protected]
>>Игорь Павлов ведёт проект 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>исходников. Мусорка.
Ну, поллитра не проблема :). Там и с поллитрой не въедешь.
Ты не пробовал изучить просто декодер, тот, который в файле
\SRC\7zip\Compress\LZMA_C\lzmadecode.c, там всего 23 кб :).