LZWL - LZWL

LZWL является слоговым вариантом символьного LZW алгоритм сжатия[1][2] которая умеет работать со слогами, полученными всеми алгоритмами разложения на слоги. Алгоритм можно использовать и для слов.

Алгоритм

Алгоритм LZWL может работать со слогами, полученными по всем алгоритмам декомпозиции на слоги. Этот алгоритм можно использовать и для слов.

На этапе инициализации словарь заполняется всеми символами алфавита. На каждом следующем шаге ищется максимальная строка S, который взят из словаря и соответствует префиксу еще не закодированной части ввода. Номер фразы S отправляется на выход. В словарь добавлена ​​новая фраза. Эта фраза создается путем конкатенации строки S и следующего за ней символа. S в файле. Фактическая позиция ввода сдвигается вперед на длину S.Декодирование требует решения только в одной ситуации. Мы можем получить номер фразы, которой нет в словаре. В этом случае мы можем создать эту фразу путем соединения последней добавленной фразы с ее первым символом.

Версия на основе слогов работает над алфавитом из слогов. На этапе инициализации мы добавляем в словарь пустой слог и маленькие слоги из базы данных частых слогов. Поиск строки S и кодирование его номера аналогично символьной версии, за исключением того, что строка S представляет собой строку слогов. Номер фразы S кодируется на выходе. Струна S может быть пустым слогом.

Если S это пустой слог, то мы должны получить из файла один слог с именем K и кодировать K методами кодирования новых слогов. Слог K добавлен в словарь. Позиция в файле сдвигается вперед на длину S. В случае, когда S - пустой слог, позиция ввода сдвигается вперед на длину K.

При добавлении фразы в словарь есть отличие от символьной версии. Фраза из следующего шага будет называться S1. Если S и S1 - непустые слоги, тогда мы добавляем новую фразу в словарь. Новая фраза создается путем соединения S1 с первым слогом слова S. У этого решения есть два преимущества. Во-первых, строки не создаются из слогов, встречающихся только один раз. Второе преимущество состоит в том, что мы не можем получить в декодере номер фразы не из словаря.

Рекомендации

  1. ^ http://www.cs.vsb.cz/dateso/2005/slides/slides6.pps
  2. ^ Саломон, Дэвид; Мотта, Джованни (18 января 2010 г.). Справочник по сжатию данных - Дэвид Саломон, Д. Брайант, Джованни Мотта - Google Книги. ISBN  9781848829039. Получено 2014-07-11.

внешняя ссылка