Преобразование «Переместить вперед»
 | Эта статья нуждается в дополнительных ссылок для проверки . ( май 2011 г. ) |
Преобразование перемещения вперед (MTF) — это кодирование данных ) , (обычно потока байтов предназначенное для повышения производительности энтропийного кодирования методов сжатия . При эффективной реализации он достаточно быстр, и его преимущества обычно оправдывают включение его в качестве дополнительного шага в алгоритм сжатия данных .
Этот алгоритм был впервые опубликован Борисом Рябко под названием «Стопка книг» в 1980 году. [1] Впоследствии он был заново открыт Дж. К. Бентли и др. в 1986 году, [2] как указано в пояснительной записке. [3]
Преобразование [ править ]
Основная идея заключается в том, что каждый символ в данных заменяется его индексом в стеке «недавно использованных символов». Например, длинные последовательности одинаковых символов заменяются таким же количеством нулей, тогда как при появлении символа, который давно не использовался, он заменяется большим числом. Таким образом, в конце данные преобразуются в последовательность целых чисел; если данные демонстрируют множество локальных корреляций, то эти целые числа имеют тенденцию быть небольшими.
Дадим точное описание. Предположим для простоты, что символы в данных представляют собой байты . Каждое значение байта кодируется своим индексом в списке байтов, который меняется в ходе работы алгоритма. Изначально список упорядочен по значению байта (0, 1, 2, 3, ..., 255). Поэтому первый байт всегда кодируется собственным значением. Однако после кодирования байта это значение перемещается в начало списка, прежде чем перейти к следующему байту.
Пример прольет свет на то, как работает преобразование. Представьте, что вместо байтов мы кодируем значения в формате a–z. Мы хотим преобразовать следующую последовательность:
бананаа
По соглашению изначально список имеет вид (abcdefghijklmnopqrstuvwxyz). Первая буква в последовательности — b, которая стоит под индексом 1 (список пронумерован от 0 до 25). Мы помещаем 1 в выходной поток:
1
Символ b перемещается в начало списка, создавая (bacdefghijklmnopqrstuvwxyz). Следующая буква — а, которая теперь появляется под индексом 1. Поэтому мы добавляем 1 к выходному потоку. У нас есть:
1,1
и мы перемещаем букву a обратно в начало списка. Продолжая таким же образом, мы обнаружим, что последовательность кодируется:
1,1,13,1,1,1,0,0
| Итерация | Последовательность | Список |
|---|---|---|
| б ананааа | 1 | (АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЫЭЮЯ) |
| б а нанааа | 1,1 | (bacdefghijklmnopqrstuvwxyz) |
| ба н анааа | 1,1,13 | (АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЫЭЮЯ) |
| запретить нааа | 1,1,13,1 | (nabcdefghijklmopqrstuvwxyz) |
| бана н ааа | 1,1,13,1,1 | (anbcdefghijklmopqrstuvwxyz) |
| банан а аа | 1,1,13,1,1,1 | (nabcdefghijklmopqrstuvwxyz) |
| банан а | 1,1,13,1,1,1,0 | (anbcdefghijklmopqrstuvwxyz) |
| банана а | 1,1,13,1,1,1,0,0 | (anbcdefghijklmopqrstuvwxyz) |
| Финал | 1,1,13,1,1,1,0,0 | (anbcdefghijklmopqrstuvwxyz) |
Легко видеть, что преобразование обратимо. Просто сохраните тот же список и декодируйте, заменяя каждый индекс в закодированном потоке буквой с этим индексом в списке. Обратите внимание на разницу между этим методом и методом кодирования: индекс в списке используется напрямую, а не ищет каждое значение для его индекса.
т.е. вы начинаете заново с (abcdefghijklmnopqrstuvwxyz). Вы берете «1» закодированного блока и ищете его в списке, в результате чего получается «b». Затем переместите букву «b» вперед, что приведет к (bacdef...). Затем возьмите следующую «1», найдите ее в списке, в результате получится «а», переместите «а» вперед... и т. д.
Реализация [ править ]
Детали реализации важны для производительности, особенно для декодирования. не дает явного преимущества Для кодирования использование связанного списка , поэтому использование массива для хранения списка допустимо, с производительностью в худшем случае ) , где O (nk n — длина данных, подлежащих кодированию, а k — количество значений (обычно константа для данной реализации).
Типичная производительность выше, поскольку часто используемые символы с большей вероятностью окажутся впереди и будут вызывать более ранние попадания. В этом же заключается идея самоорганизующегося списка Move-to-front .
Однако для декодирования мы можем использовать специализированные структуры данных, чтобы значительно повысить производительность. [ нужен пример ]
Питон [ править ]
Это возможная реализация алгоритма перемещения вперед в Python .
# mtfwiki.py
# Вместо того, чтобы всегда передавать «оригинальный» словарь, проще просто согласовать начальный набор.
# Здесь мы используем 256 возможных значений байта:
common_dictionary = list ( range ( 256 ))
def encode ( Plain_text : str ) -> list [ int ]:
# Переход на байты для 256.
Plain_text = Plain_text . encode ( "utf-8" )
# Изменение общего словаря — плохая идея. Сделать копию.
словарь = общий_словарь . copy ()
# Преобразование
compressed_text = list () # Обычный массив
Rank = 0
# Считывание каждого
символа c в Plain_text :
Rank = словарь . index ( c ) # Находим ранг символа в словаре [O(k)]
compressed_text . append ( rank ) # Обновляем закодированный текст
# Обновляем словарь [O(k)]
dictionary . поп ( ранговый )
словарь . Insert ( 0 , c )
return compressed_text # Возвращает закодированный текст
Обратное действие восстановит исходный текст:
def decode ( сжатые_данные : список [ int ]) -> str :
сжатый_текст = сжатых_данных
словарь = общий_словарь . copy ()
Plain_text = []
# Чтение каждого ранга закодированного текста
для ранга в сжатом_тексте :
# Чтение символа этого ранга из словаря
Plain_text . добавьте ( словарь [ ранг ])
# Обновите словарь
e = словарь . поп ( ранговый )
словарь . Insert ( 0 , e )
возвращает байты ( plain_text ) . decode ( "utf-8" ) # Возвращаем исходную строку
Пример вывода:
>>> импортировать mtfwiki
>>> mtfwiki . encode ( «Википедия» )
[87, 105, 107, 1, 112, 104, 104, 3, 102]
>>> mtfwiki . декодировать ([ 119 , 106 , 108 , 1 , 113 , 105 , 105 , 3 , 103 ])
'википедия'
В этом примере мы видим, как код MTF использует преимущества трех повторяющихся iво входном слове. Общий словарь здесь, однако, не идеален, поскольку он инициализируется более часто используемыми печатными символами ASCII , расположенными после малоиспользуемых управляющих кодов, вопреки замыслу кода MTF сохранять то, что обычно используется, в начале. Если повернуть словарь, чтобы поместить наиболее используемые символы на более ранние места, можно получить лучшую кодировку:
>>> import mtfwiki
>>> block32 = лямбда x : [ x + i для i в диапазоне ( 32 )]
>>> # Сортировка блоков ASCII: сначала строчные буквы, затем прописные буквы, знаки препинания/цифры и, наконец, управляющий код и не-ASCII-материалы
>>> mtfwiki . common_dictionary = блок32 ( 0x60 ) + блок32 ( 0x40 ) + блок32 ( 0x20 ) + блок32 ( 0x00 ) + список ( диапазон ( 128 , 256 ))
>>> mtfwiki . кодировать ( «Википедия» )
[55, 10, 12, 1, 17, 9, 9, 3, 7]
практических алгоритмах сжатия данных Использование в
Преобразование MTF использует преимущества локальной корреляции частот для уменьшения энтропии сообщения. [ нужны разъяснения ] Действительно, недавно использованные буквы остаются в начале списка; если использование букв демонстрирует локальную корреляцию, это приведет к появлению большого количества маленьких чисел, таких как «0» и «1», в выходных данных.
Однако не все данные демонстрируют такой тип локальной корреляции, а для некоторых сообщений преобразование MTF может фактически увеличить энтропию.
Важным применением преобразования MTF является сжатие на основе преобразования Берроуза-Уиллера . Преобразование Берроуза-Уиллера очень хорошо подходит для создания последовательности, которая демонстрирует локальную частотную корреляцию из текста и некоторых других специальных классов данных. Сжатие значительно выигрывает от того, что за преобразованием Берроуза-Уиллера следует преобразование MTF перед последним этапом энтропийного кодирования.
Пример [ править ]
 | Следующий раздел может сбить с толку или быть неясным для читателей . В частности, какой метод используется для получения этих чисел? ( февраль 2011 г. ) |
В качестве примера представьте, что мы хотим сжать монолог Гамлета ( «Быть или не быть...» ). Мы можем вычислить размер этого сообщения как 7033 бита. Наивно мы могли бы попытаться применить преобразование MTF напрямую. В результате получается сообщение длиной 7807 бит (больше исходного). Причина в том, что текст на английском языке, как правило, не демонстрирует высокий уровень локальной частотной корреляции. Однако если мы сначала применим преобразование Берроуза-Уиллера, а затем преобразование MTF, мы получим сообщение длиной 6187 бит. Обратите внимание, что преобразование Берроуза – Уиллера не уменьшает энтропию сообщения; он только переупорядочивает байты таким образом, чтобы сделать преобразование MTF более эффективным.
Одна из проблем с базовым преобразованием MTF заключается в том, что оно вносит одни и те же изменения для любого символа, независимо от частоты, что может привести к уменьшению сжатия, поскольку символы, которые встречаются редко, могут привести к увеличению значений часто встречающихся символов. По этой причине были разработаны различные изменения и альтернативы. Одно из распространенных изменений — сделать так, чтобы символы выше определенной точки могли перемещаться только до определенного порога. Другой вариант — создать некий алгоритм, который подсчитывает локальную частоту каждого символа и использует эти значения для выбора порядка символов в любой момент. Многие из этих преобразований по-прежнему оставляют ноль для повторяющихся символов, поскольку они часто являются наиболее распространенными в данных после преобразования Берроуза Уилера.
Переместить связанный список на передний план [ править ]
- Термин «Переместить на передний план» (MTF) также используется в несколько другом контексте, как тип динамического связанного списка . В списке MTF каждый элемент перемещается вперед при доступе к нему. [4] Это гарантирует, что со временем доступ к наиболее часто используемым элементам станет проще.
Ссылки [ править ]
- ^ Рябко, Борис Яковлевич ( 1980 ). «Сжатие данных средствами «книжной стопки» » (PDF) . Проблемы передачи информации . 16 (4): 265–269. Збл 0466.94007 .
- ^ Бентли, Джон Луис ; Слитор, Дэниел Доминик Каплан ; Тарьян, Роберт Эндре ; Вэй, В.К. (1986). «Локально адаптивная схема сжатия данных» . Коммуникации АКМ . 29 (4): 320–330. CiteSeerX 10.1.1.69.807 . дои : 10.1145/5684.5688 . S2CID 5854590 .
- ^ Рябко Борис ; Яковлевич Хорспул, Р. Найджел ; Кормак, Гордон Вилли (1987). «Комментарии к: «Локально адаптивная схема сжатия данных» Дж. Л. Бентли, Д. Д. Слиатора, Р. Э. Тарьяна и В. К. Вея» . Комм. АКМ . 30 (9): 792–794. дои : 10.1145/30401.315747 . S2CID 16138142 .
- ^ Ривест, Рональд Линн (1976). «О самоорганизующейся эвристике последовательного поиска» . Коммуникации АКМ . 19 (2): 63–67. дои : 10.1145/359997.360000 . S2CID 498886 .
Внешние ссылки [ править ]
сжатия данных Методы | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| без потерь |
| ||||||||
| с потерями |
| ||||||||
| Аудио |
| ||||||||
| Изображение |
| ||||||||
| видео |
| ||||||||
| Теория | |||||||||
| Сообщество | |||||||||
| Люди | |||||||||
