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 . Это решение имеет два преимущества: первое - строки не создаются из слогов, встречающихся только один раз. Второе преимущество состоит в том, что мы не можем получить в декодере номер фразы, не взятой из словаря.
Рекомендации
- ^ http://www.cs.vsb.cz/dateso/2005/slides/slides6.pps
- ^ Саломон, Дэвид; Мотта, Джованни (18 января 2010 г.). Справочник по сжатию данных - Дэвид Саломон, Д. Брайант, Джованни Мотта - Google Книги . ISBN 9781848829039. Проверено 11 июля 2014 .