Изменения

Перейти к: навигация, поиск

Алгоритмы LZ77 и LZ78

626 байт добавлено, 05:15, 15 ноября 2011
Нет описания правки
* последний символ буфера.
В конце итерации алгоритм сдвигает окно на длину равную длине буфера+1.
=== Пример "<tex>kabababababz" </tex> ===
{| border="1"
!Содержимое окна (длина равна 4)
!Содержимое буфера
!КОД
|-
|''<tex>kabababababz</tex> |<tex>k</tex> |<0,0,<tex>k</tex>>
|-
|k<tex>kabababababz</tex> |<tex>a</tex> |<0,0,<tex>a</tex>>
|-
|ka<tex>kabababababz</tex> |<tex>b</tex> |<0,0,<tex>b</tex>>
|-
|k<tex>k\fbox{ab}ababababz</tex> |<tex>aba</tex> |<2,2,<tex>a</tex>>
|-
|kaba<tex>kaba\fbox{bababab}abz</tex> |<tex>bababz</tex> |<2,5,<tex>z</tex>>
|}
В отличие от LZ77, работающего с уже полученными данными, LZ78 ориентируется на данные, которые только будут получены (LZ78 не использует скользящее окно, он хранит словарь из уже просмотренных фраз). Алгоритм считывает символы сообщения до тех пор, пока накапливаемая подстрока входит целиком в одну из фраз словаря. Как только эта строка перестанет соответствовать хотя бы одной фразе словаря, алгоритм генерирует код, состоящий из индекса строки в словаре, которая до последнего введенного символа содержала входную строку, и символа, нарушившего совпадение. Затем в словарь добавляется введенная подстрока. Если словарь уже заполнен, то из него предварительно удаляют менее всех используемую в сравнениях фразу. Если в конце алгоритма мы не находим символ, нарушивший совпадения, то тогда мы выдаем код в виде <индекс строки в словаре без последнего символа, последний символ>.
=== Пример "<tex>kabababababz" </tex> ===
{| border="1"
!Содержимое словаря
|-
|''
|<tex>k</tex> |<0,<tex>k</tex>>
|-
|<tex>k </tex> |<tex>a</tex> |<0,<tex>a</tex>>
|-
|<tex>k</tex>, <tex>a</tex> |<tex>b</tex> |<0,<tex>b</tex>>
|-
|<tex>k</tex>,<tex>\fbox{a}</tex>, <tex>b</tex> |<tex>ab</tex> |<2,<tex>b</tex>>
|-
|<tex>k</tex>, <tex>a</tex>, <tex>b</tex>,<tex>\fbox{ab}</tex> |<tex>aba</tex> |<4,<tex>a</tex>>
|-
|<tex>k</tex>, <tex>a</tex>,<tex>\fbox{b}</tex>,<tex>ab</tex>, <tex>aba</tex> |<tex>ba</tex> |<3,а<tex>a</tex>>
|-
|<tex>k</tex>, <tex>a</tex>, <tex>b</tex>, <tex>ab</tex>,<tex>\fbox{aba}</tex>,<tex>ba</tex> |<tex>abab</tex> |<5,<tex>b</tex>>
|-
|<tex>k</tex>, <tex>a</tex>, <tex>b</tex>, <tex>ab</tex>, <tex>aba</tex>, <tex>ba</tex>, <tex>abab</tex> |<tex>z</tex> |<0,<tex>z</tex>>
|}
Анонимный участник

Навигация