|
|
| Строка 1: |
Строка 1: |
| − | == LZ78 ==
| |
| − | === Описание алгоритма ===
| |
| − | Алгоритм LZ78 делает, все встретили их последовательность в словаре. Каждый раз данных, чтобы сжать последовательность найден, программа ссылается на словарь:
| |
| − | · Если последовательность находится в словаре, то файл продукции хранится кодекс для этого отчета;
| |
| − | · Если последовательность - расширенная версия последовательности из словаря, то это добавлено к столу.
| |
| − | Например, если программа была сжатой последовательностью ABC в словаре и видит последовательность ABCA, это будет сначала похоронено в кодексе продукции из словаря для ABC, тогда характер A, тогда последовательность, ABCA будет добавлен к словарю. Если, однако, она позже встречает ABCAB, он показывает кодекс для ABCA, то кодекс для символа B и ABCAB добавляет к словарю. Каждый раз, когда программа сталкивается с последовательностью в словаре, она дает кодекс и добавляет новый отчет, который один байт длиной. Таким образом, каждый раз повторяя последовательность байтов, словарь вырос бы, чтобы включать продолжение этой последовательности. Обратите внимание на то, что программа должна встретить с последовательностью ABCABC по крайней мере 6 раз (число писем) прежде, чем словарь будет создан отчет, содержащий всю последовательность.
| |
| − | Алгоритм LZ78 вносит все встреченные им последовательности в
| |
| | | | |
| − | словарь. Всякий раз, когда среди данных, которые надо сжать, встречается
| |
| − |
| |
| − | последовательность, программа обращается к словарю:
| |
| − |
| |
| − | · если последовательность находится в словаре, то в выходной файл
| |
| − |
| |
| − | заносится код для этой записи;
| |
| − |
| |
| − | · если последовательность представляет собой расширенный вариант
| |
| − |
| |
| − | последовательности из словаря, то она добавляется в таблицу.
| |
| − |
| |
| − | Например, если программа сжатия уже имеет последовательность ABC в
| |
| − |
| |
| − | словаре и увидит последовательность ABCA, то она вначале занесет в
| |
| − |
| |
| − | выходной файл код из словаря для ABC, затем для символа A, после чего
| |
| − |
| |
| − | последовательность ABCA будет добавлена в словарь. Если же она позже
| |
| − |
| |
| − | встретит ABCAB, то выведет код для ABCA, затем код для символа B и
| |
| − |
| |
| − | добавит ABCAB в словарь. Каждый раз, когда программа встречает
| |
| − |
| |
| − | последовательность из словаря, она выдает код и добавляет новую запись,
| |
| − |
| |
| − | которая на один байт длиннее. Таким образом, каждый раз при повторении
| |
| − |
| |
| − | последовательности байтов, словарь должен будет расти, чтобы включить
| |
| − |
| |
| − | продолжение этой последовательности. Обратите внимание на то, что
| |
| − |
| |
| − | программа должна встретиться с последовательностью ABCABC по крайней
| |
| − |
| |
| − | мере 6 раз (по числу букв), прежде чем в словаре будет создана запись,
| |
| − |
| |
| − | содержащая всю последовательность.
| |
| − | В отличие от 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>>
| |
| − | |}
| |
