Изменения

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

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

10 байт добавлено, 21:36, 2 ноября 2010
Описание алгоритма
== LZ78 ==
=== Описание алгоритма ===
В отличие от LZ77, работающего с уже полученными данными, LZ78 ориентируется на данные, которые только будут получены (LZ78 не использует «скользящее» окно, он хранит словарь из уже просмотренных фраз). Алгоритм считывает символы сообщения до тех пор, пока накапливаемая подстрока входит целиком в одну из фраз словаря. Как только эта строка перестанет соответствовать хотя бы одной фразе словаря, алгоритм генерирует код, состоящий из индекса строки в словаре, которая до последнего введенного символа содержала входную строку, и символа, нарушившего совпадение. Затем в словарь добавляется введенная подстрока. Если словарь уже заполнен, то из него предварительно удаляют менее всех используемую в сравнениях фразу. Если в конце алгоритма мы не находим мы не находим символ нарушивший совпадения то тогда мы выдаем код в виде <индекс строки в словаре- последний символбез последнего символа, последний символ>.
=== Пример "kabababababz" ===
96
правок

Навигация