Изменения

=== Описание алгоритма === В отличие от LZ77, работающего с уже полученными данными, Алгоритм LZ78 ориентируется на данные, которые только будут получены (LZ78 не использует скользящее окно, он хранит словарь из уже просмотренных фраз). Алгоритм считывает символы сообщения до тех пор, пока накапливаемая подстрока входит целиком в одну из фраз словаря. Как только эта строка перестанет соответствовать хотя бы одной фразе словаря, алгоритм генерирует код, состоящий из индекса строки в словаре, которая до последнего введенного символа содержала входную строку, и символа, нарушившего совпадение. Затем вносит все встреченные последовательности в словарь добавляется введенная подстрока. Если словарь уже заполненКаждый раз, то из него предварительно удаляют менее всех используемую в сравнениях фразу. Если в конце алгоритма мы не находим символкогда среди данных, нарушивший совпадениякоторые нужно сжать, то тогда мы выдаем код в виде <индекс строки в словаре без последнего символавстречается последовательность, последний символ>.программа обращается к словарю:

* если последовательность находится в словаре, то на выход подается код для этой записи * если последовательность - дополненная версия последовательности из словаря, то эта последовательность добавляется в словарь Например, если в словаре уже хранится последовательность ''ABC'', и программа встречает последовательность ''ABCA'', то на выход сначала подается код из словаря для ''ABC'', затем символ ''A'', а затем последовательность ''ABCA'' будет добавлена в словарь. Если потом встретится последовательность ''ABCAB'', на выход подастся код для ''ABCA'', символ ''B'', и в словарь добавится ''ABCAB''. Каждый раз, когда программа встречает последовательность из словаря, она выдает код и добавляет в словарь новую последовательность, которая на один байт длиннее.=== Пример <tex>kabababababz</tex> ===

!Содержимое словаряСообщение !Содержимое считываемой строкиКод !КОД Новая последовательность в словаре

|'' |<tex>k</tex> |<0,<tex>k</tex>> |- |<tex>k</tex> |<tex>a\ abracadabra</tex>

|<tex>k</tex>, <tex>a</tex> |<tex>b\ bracadabra</tex>

|<tex>k</tex>, <tex>ab\fbox{a}</tex>, <tex>bracadabra</tex> |<0,<tex>abr</tex>> |<2,<tex>b3.\ r</tex>>

|<tex>kabr\ acadabra</tex>, |<tex>a</tex>1, <tex>bc</tex>, <tex>\fbox{ab}</tex> |<tex>aba</tex> |<4,<tex>a.\ ac</tex>>

|<tex>k</tex>, <tex>a</tex>, <tex>abrac\fbox{b}adabra</tex>, |<tex>ab</tex>1, <tex>abad</tex> |<tex>ba</tex> |<3,<tex>a5.\ ad</tex>>

|<tex>kabracad\ abra</tex>, |<tex>a</tex>1, <tex>b</tex>, <tex>ab</tex>, <tex>\fbox{aba}</tex>, <tex>ba</tex> |<tex>abab</tex> |<5,<tex>b6.\ ab</tex>>

|<tex>kabracadab\ ra</tex> |<3, <tex>a</tex>, <tex>b</tex>, <tex>ab</tex>, <tex>aba</tex>, <tex>ba</tex>, <tex>abab</tex> |<tex>z</tex> |<0,<tex>z7.\ ra</tex>>