На этом алгоритме с некоторыми модификациями работают такие известные архиваторы как RAR, ZIP, ZIP7 вот и я решил приобщится к прекрасному и немного поговнокодить над велосипедом.
LZ77 рассматривать не будем, а сразу займемся алгоритмом LZ78.
Основная понимание сжатие по словарю в случае LZ78 в следующем, идем по строке которая должна быть сжата, если строка есть в словаре, то увеличиваем длину сравниваемой строки на 1 до тех пор пока не найдем такую комбинацию символов которой нет в словаре, как только такая комбинация символов находится, добавляем в словарь сравниваемую фразу без последнего символа, а в исходящий поток записываем индекс этой строки и символ который отличается.
Пример алгоритма КОДИРОВАНИЯ строки "КАРЛ_КАРАЛ_КАР!":
1. Смотрим первый символ - К ищем его в словаре, а так как словарь пустой, то не находим и добавляем ее присваивая ему индекс 0, так как эта у этой фразы нет совпадения и она никуда не ссылается. В закодированные строку записываем 0К и получается строка 0K
2. Сдвигаем кодируемую фразу на 1 символ теперь у нас указатель указывает на вторую букву А, ищем ее в словаре, так как в словаре только буква К, то не находим и добавляем А с тем же индексом 0, так как она тоже никуда не ссылается. В закодированные строку записываем 0A и получается строка 0K0A
3. Сдвигаем кодируемую фразу на 1 символ теперь у нас указатель указывает на третью букву Р, ищем ее в словаре, так как в словаре буквы К и А, то не находим и добавляем Р с тем же индексом 0, так как она тоже никуда не ссылается. В закодированные строку записываем 0P и получается строка 0K0A0P
4. Сдвигаем кодируемую фразу на 1 символ теперь у нас указатель указывает на четвертую букву Л, ищем ее в словаре, так как в словаре буквы К, А, Р то не находим и добавляем Л с тем же индексом 0, так как она тоже никуда не ссылается. В закодированные строку записываем 0Л и получается строка 0K0A0P0Л
5. Сдвигаем кодируемую фразу на 1 символ теперь у нас указатель указывает на пятую букву _ , ищем ее в словаре, так как в словаре буквы К, А, Р, Л то не находим и добавляем _ с тем же индексом 0, так как она тоже никуда не ссылается. В закодированные строку записываем 0_ и получается строка 0K0A0P0Л0_
6. Сдвигаем кодируему фразу на 1 символ, теперь у нас указатель указывает на шестую букву К, ищем ее в словаре и находи в позиции 1, этот символ уже есть в словаре и добавлять его нет смысла, по этому нам необходимо посмотреть следующую букву в кодируемой строке. Которая оказывается А, теперь ищем уже фразу состоящую из 2х букв, КА, естественно ее не находим. В этом случае нам необходимо записать в словарь КА и поставить указатель на индекс буквы К, который является 1, так как эта фраза идет первой в словаре. Словарь выглядит в текущий момент следующим образом, 0К, 0А, 0Р, 0Л, 0_, 1КА. Далее необходимо записать в закодированную строку символ который вызвал различие между фразы из строки и фразы которая есть в словаре. Ну и индекс на тот символ который есть в словаре. Закодированная строка выглядит следующим образом на текущий момент: 0K0A0P0Л0_1А
7. Сдвигаем кодируемую фразу уже на 2 символа, так как мы в предыдущем шаге обработали уже 2 символа. Ищем текущий символ в строке, им является буква Р, находим ее в словаре в позиции 3, так как она есть, смотрим уже фразу из оригинальной строки в 2 символа, ей является фраза РА, действуем как в 6ом пункте. В словарь добавляем РА с индексом найденной ранее буквы Р. Словарь получается 0К, 0А, 0Р, 0Л, 0_, 1КА, 3РА. А закодированная строка: 0K0A0P0Л0_1А2А
8. Действуем также как в 7ом пункте, сдвигаем фразу на 2 обработанных символа. Ищем Л, Находим ее, смотрим следующий символ _, не находим фразу Л_ в словаре. Добавляем ее в словарь и получаем: 0К, 0А, 0Р, 0Л, 0_, 1КА, 3РА, 4Л_ В закодированную строка на текущий момент выглядит так: 0K0A0P0Л0_1А3А4_
9. Сдвигаем строку на 2 обработанны символа, смотрим на символ в текущей фразе, там лежит символ К, ищем в словаре и находим его под индексом 1, расширяем границы фразы на еденицу, фраза получается КА, ищем ее в словаре и снова находим, но уже под индексом 6, снова расширяем границу фразы на еденицу и теперь ищем уже с словаре КАР, вот тут и не находим ее. Значит в словарь нада записать КАР с предыдущем найденым индексом 6. Словарь на текущий момент выглядит так: 0К, 0А, 0Р, 0Л, 0_, 1КА,3РА, 4Л_, 6КАР. А в закодированную строку записываем 6Р и закодированная строка выглядит так: 0K0A0P0Л0_1А3А4_6Р
10. Сдвигаем строку на 3 обработанных символа, смотрим, на что в текущий момент показывает указатель, символ который обрабатывается "!". Ищем его в словаре и не находим, по этому необходимо его добавить с индексом 0, так как его нет. Словарь выглядит следующим образом:
0К, 0А, 0Р, 0Л, 0_, 1КА, 3РА, 4Л_, 6КАР, 0! А закодированная строка: 0K0A0P0Л0_1А3А4_6Р0!
На этом кодирование строки закончено, посмотрим на результат:
Оригинал: КАРЛ_КАРАЛ_КАР!
Пожатая : 0K0A0P0Л0_1А3А4_6Р0!
Как видно, компрессия тут получилась минусовая, пожатая строка больше чем не пожатая. Это как раз большой минус этого алгоритма, очень плохо жмет короткие строки и строки с большой энтропией. Но еслиб строка была большей длины и содержала много повторяющихся фраз, то сжатие было бы достаточно существенным.
А теперь алгоритм ДЕКОДИРОВАНИЯ строки 0K0A0P0Л0_1А3А4_6Р0!
1. Смотрим на индекс первого символа, который является 0. Так как мы знаем что индекс 0 никуда не ссылается, то просто добавлем в 1 позицию словаря К с индексом 0. В декодированную строку записываем К
2. Смотрим индекс второго символа, который также является 0. Добавляем в следующую позицию словаря фразу А с индексом 0. В декодированную строку записываем А. Получаем строку КА
3. Повторяем тоже самое для Р. В декодированную строку записываем Р. Получаем строку КАР
4. Повтоярем тоже самое для Л. В декодированную строку записываем Л. Получаем строку КАРЛ
5. Повторяем тоже самое для _. В декодированную строку записываем _. Получаем строку КАРЛ_
6. Смотрим на индекс фразы А в кодированной строке, там стоит цифра 1, это обозначает, что, надо посмотреть на 1 позицию в словаре. В 1 позиции словаря находится фраза К. Из этого делаем вывод, что нам необходимо склеить эти 2 фразы, одна из словаря, а вторая из закодированной строки. Получается КА. Эту фразу мы добавляем в словарь, не забывая поставить ей индекс 1, если присмотреться в текущий момент мы восстанавливаем исходный словарь, который использовали для кодирования строки. Также эту фразу прикрепляем к концу декодированной строки и получаем: КАРЛ_КА
7. Сдвигаемся на следующий индекс в закодированной строке, там находится 3А. Действуем также как в 6ом пункте. Смотрим в словаре что находится под индексом 3, это фраза Р. Складывая с фразой из кодированной строки получаем исходную РА. Добавляем ее в словарь в следующую позицию. И прикрепляем к концу раскодированной строки: КАРЛ_КАРА
8. Снова сдвигаемся на следующий индекс в закодированной строке, там находиться 4_. Действуем как 6 и 7 пункте. Добавляем в словарь Л_ и в конец строки Л_. Получается раскодированная строка КАРЛ_КАРАЛ_
9. Следующий символ и индекс - 6Р. Он указывает на 6ю позицию в словаре, где находится КА.
Склеиваем с символом из закодированной строки и получаем КАР. Добавляем на очередную позицию в словарь с индексом 6 и в конец раскодированной строки. Итого: КАРЛ_КАРАЛ_КАР
10. Смотрим в последний символ и его индекс - 0! Так как индекс 0, значит он никуда не ссылается, значит добавляем его на следующую позицию в словаре и и прибавляем к раскодированной строке. КАРЛ_КАРАЛ_КАР!
Ну вот и все, в принципе алгоритм очень простой, к тому же он применяется во многих архиваторах.
Например в одном из лучших на текущий момент архиваторе 7-Zip используется LZWA, LZW это один из подвидов алгоритма LZ, который использует предустановленный словарь алгоритм этого кодируется буквой W и плюс к тому же до кучи используется арифметическое сжатие получившейся строки которое кодируется буквой A.
Ну а теперь немного говнокода:
Процедура поиска в словаре.
findStr proc uses ecx edx edi string:DWORD, num:DWORD LOCAL count:DWORD ; счетчик mov count, 1h ; заносим в счетчик 1 nextserach: ; метка на следующую позицию словаря imul eax, count, sdict ; вычисляем необходимую позицию в словаре lea edi, myDict.string[eax] ; получаем ссылку на необходимую позицию .if BYTE PTR [edi] == 0 ; сравниваем, если 0 то словарь закончился jmp notfound ; выходим из поиска .endif mov esi, string ; заносим ссылку на фразу mov ecx, num ; длинну фразы inc count ; увеличиваем счетчик repe cmpsb ; сравниваем фразы jz found ; совпадают, прыгаем на found jmp nextserach ; следующий поиск found: .if BYTE PTR [edi] != 0 ; если не равно 0 jmp nextserach ; ищем дальше .endif mov eax, count ; иначе скидываем счетчик в еах jmp endsearch ; заканчиваем поиск notfound: mov eax, 1 ; ничего не нашли, записываем 1 в eax endsearch: ret findStr endp
Процедура добавления в словарь.
addDictStr proc uses ecx ebx edi esi string:DWORD, num:DWORD, lenght:DWORD mov ebx, num ; в ebx помещаем позицию найденной фразы в словаре mov eax, countDict ; в eax помещаем счетчик текущий позиций в словаре imul eax, eax, sdict ; вычисляем нахождение очередной позиции mov myDict.pos[eax], ebx ; заносим в структуру словаря позицию найденной фразы mov esi, string ; в esi ссылка на кодируемую строку lea edi, myDict.string[eax] ; в edi ссылка на структуру словаря xor ecx, ecx ; чистим на всякий случай ecx mov ecx, lenght ; заносим длинну фразы которая заносится в словарь rep movsb ; копируем mov BYTE PTR [edi], 0h ; заносим 0 в конец строки inc countDict ; увеличиваем позицию в словаре ret addDictStr endp
Сама процедура сжатия.
compress proc pSrcString:DWORD, lSrcString:DWORD, pDstString:DWORD, lDstString:DWORD LOCAL prevPos:DWORD ; переменная для запоминания предыдущей позиции mov prevPos, 1 ; заносим в перменную 1 mov edi, pSrcString ; в edi указатель на источник строки mov ebx, 1 ; в ebx заносим 1 xor ecx, ecx ; обнуляем ecx compnext: invoke findStr, edi, ebx ; вызываем поиск фразу в словаре .if eax == 1 ; если функция вернула 1, тоесть не нашла ничего invoke addDictStr, edi, prevPos, ebx ; добавляем в словарь фразу jmp strnotfound ; прыгаем, что ничего не нашли .endif mov prevPos,eax ; заносим в prevPos длинну строки inc ebx ; увеличиваем ebx на 1 jmp compnext ; прыгаем на поиск более длинной строки strnotfound: mov edx, pDstString ; в edx заносим указатель на строку получатель mov eax, prevPos ; в eax копируем позицию предыдущей найденной совпадающей фразы mov BYTE PTR [edx], al ; в шифрованную строку заносим позицию совпадающей фразы mov al, BYTE PTR [edi+ebx-1] ; в al копируем символ который вызвал несовпадение mov BYTE PTR [edx+1], al ; записываем в закодированную строку символ add pDstString, 2h ; увеличиваем указатель на строку приемник на 2 mov prevPos, 1 ; сбрасываем текущую позицию в словаре .if ecx >= lSrcString ; если ecx больше или равно длинне строки jmp compend ; компрессия закончена .endif add edi, ebx ; прибавляем к указателю на строку столько символов сколько обработали add ecx, ebx ; прибавляем к счетчику столько символов сколько обработали mov ebx, 1 ; увеличиваем ebx на 1 jmp compnext ; прыгаем на сжатие следующей строки compend: ret compress endp
Ну а теперь функции необходимые для разархивирования:
Процедура получения строки.
getStr proc uses ecx edi edx num:DWORD, codeStr:DWORD mov eax, num ; в eax заносим индекс в словаре из сжатой строки .if eax == 1 ; если индекс равен 1, то значит что совпадений нет mov eax, codeStr ; в eax заносится указатель на закодированную строку mov al, BYTE PTR [eax+1] ; в al заносится символ из закодированной строки mov BYTE PTR [buf], al ; в буфер заносится символ из al mov ebx, 1 ; в ebx заносим 1 jmp endGetStr ; закончили обработку по склеиванию строк .endif mov edi, offset buf ; в edi записываем указатель на буфер dec eax ; уменьшаем eax imul edx, eax, sdict ; вычисляем позицию в словаре xor ecx, ecx ; обнуляем ecx nextDictChr: mov al, myDict.string[edx+ecx] ; в al заносим символ в словаре mov BYTE PTR [edi+ecx], al ; переносим его в буфер inc ecx ; увеличиваем позицию в буфере и в словаре .if al == 0 ; если в al 0, то значит фраза в словаре закончилась mov eax, codeStr ; копируем в eax указатель на закодированную строку mov al, BYTE PTR [eax+1] ; в al заносим символ в закодированной строке mov BYTE PTR [edi+ecx-1], al ; переносим его в конец буфера mov ebx, ecx ; копируем счетчик в ebx jmp endGetStr ; закончили склеивать строки .endif jmp nextDictChr ; обрабатываем следующий символ в словаре endGetStr: ret getStr endp
Процедура записи буфера в раскодированную строку.
writeStr proc uses ecx edi esi pdstString:DWORD, pBuf:DWORD, num:DWORD mov ecx, num ; в ecx заносим колличество символов mov edi, pdstString ; в edi указатель на строку получатель mov esi, pBuf ; в esi указатель на буфер rep movsb ; копируем mov eax, edi ; возвращаем текущий указатель на строку получатель ret writeStr endp
Ну и наконец, процедура декомпрессии.
decompress proc pSrcString:DWORD, lSrcString:DWORD, pDstString:DWORD, lDstString:DWORD LOCAL curDstPos:DWORD ; локальная переменная для указателя на позицию в приемнике mov edi, pSrcString ; в edi строка источник xor ecx, ecx ; обнуляем ecx mov eax, pDstString ; в eax заносим указатель на строку приемник mov curDstPos, eax ; в локальную переменную заносим указатель на строку приемник nextcode: xor eax, eax ; обнуляем eax mov al, BYTE PTR [edi] ; в al заносим индекс в словаре из закодированной строки push eax ; сохраним eax в стеке invoke getStr, eax , edi ; добудем в буфер готовую строку pop eax ; восстановим eax из стека с индекосм lea esi, buf ; занесем в esi указатель на буфер invoke addDictStr, esi, eax, ebx ; добавляем строку в словарь invoke writeStr, curDstPos, esi, ebx ; записываем буфер в строку приемник mov curDstPos, eax ; запишем в локальной переменной текущий указатель на приемник add edi, 2 ; увеличиваем позицию в закодированной строке на 2 .if BYTE PTR [edi] == 0 ; сравниваем, если в индексе 0, то значит закодированная строка кончилась jmp decodeend ; прыгаем на окончание .endif jmp nextcode ; обрабаываем следующий символ в закодированной строке decodeend: ret decompress endp
Целиком код можно посмотреть как обычно на pastebin по вот этой ссылке -http://pastebin.com/g4HTszRs
Комментариев нет:
Отправить комментарий