Преобразование «Переместить вперед»

Преобразование перемещения вперед (MTF) это кодирование данных — (обычно потока байтов ), предназначенное для повышения производительности энтропийного кодирования методов сжатия . При эффективной реализации он достаточно быстр, и его преимущества обычно оправдывают включение его в качестве дополнительного шага в алгоритм сжатия данных .

Этот алгоритм был впервые опубликован Борисом Рябко под названием «Стопка книг» в 1980 году. ^[1] Впоследствии он был заново открыт Дж. К. Бентли и др. в 1986 году, ^[2] как указано в пояснительной записке. ^[3]

Преобразование

Основная идея заключается в том, что каждый символ в данных заменяется его индексом в стеке «недавно использованных символов». Например, длинные последовательности одинаковых символов заменяются таким же количеством нулей, тогда как при появлении символа, который давно не использовался, он заменяется большим числом. Таким образом, в конце данные преобразуются в последовательность целых чисел; если данные демонстрируют множество локальных корреляций, то эти целые числа имеют тенденцию быть небольшими.

Дадим точное описание. Предположим для простоты, что символы в данных представляют собой байты .Каждое значение байта кодируется своим индексом в списке байтов, который меняется в ходе работы алгоритма. Изначально список упорядочен по значению байта (0, 1, 2, 3, ..., 255). Поэтому первый байт всегда кодируется собственным значением. Однако после кодирования байта это значение перемещается в начало списка, прежде чем перейти к следующему байту.

Пример прольет свет на то, как работает преобразование. Представьте, что вместо байтов мы кодируем значения в формате a–z. Мы хотим преобразовать следующую последовательность:

bananaaa

По соглашению изначально список имеет вид (abcdefghijklmnopqrstuvwxyz). Первая буква в последовательности — b, которая стоит под индексом 1 (список пронумерован от 0 до 25). Мы помещаем 1 в выходной поток:

Символ b перемещается в начало списка, создавая (bacdefghijklmnopqrstuvwxyz). Следующая буква — а, которая теперь появляется под индексом 1. Поэтому мы добавляем 1 к выходному потоку. У нас есть:

1,1

и мы перемещаем букву a обратно в начало списка. Продолжая таким же образом, мы обнаружим, что последовательность кодируется:

1,1,13,1,1,1,0,0

Итерация	Последовательность	Список
б анализ	1	(abcdefghijklmnopqrstuvwxyz)
б и посмотри	1,1	(bacdefghijklmnopqrstuvwxyz)
baдоступен anaaa	1,1,13	(abcdefghijklmnopqrstuvwxyz)
бан и неаа	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# Instead of always transmitting an "original" dictionary, it is simpler to just agree on an initial set.# Here we use the 256 possible values of a byte:common_dictionary = list(range(256))def encode(plain_text: str) -> list[int]:    # Change to bytes for 256.    plain_text = plain_text.encode("utf-8")    # Changing the common dictionary is a bad idea. Make a copy.    dictionary = common_dictionary.copy()    # Transformation    compressed_text = list()          # Regular array    rank = 0    # Read in each character    for c in plain_text:        rank = dictionary.index(c)    # Find the rank of the character in the dictionary [O(k)]        compressed_text.append(rank)  # Update the encoded text        # Update the dictionary [O(k)]        dictionary.pop(rank)        dictionary.insert(0, c)    return compressed_text            # Return the encoded text

Обратное действие восстановит исходный текст:

def decode(compressed_data: list[int]) -> str:    compressed_text = compressed_data    dictionary = common_dictionary.copy()    plain_text = []    # Read in each rank in the encoded text    for rank in compressed_text:        # Read the character of that rank from the dictionary        plain_text.append(dictionary[rank])        # Update the dictionary        e = dictionary.pop(rank)        dictionary.insert(0, e)    return bytes(plain_text).decode("utf-8")  # Return original string

Пример вывода:

>>> import mtfwiki>>> mtfwiki.encode("Wikipedia")[87, 105, 107, 1, 112, 104, 104, 3, 102]>>> mtfwiki.decode([119, 106, 108, 1, 113, 105, 105, 3, 103])'wikipedia'

В этом примере мы видим, как код MTF использует преимущества трех повторяющихся iво входном слове. Общий словарь здесь, однако, не идеален, поскольку он инициализируется более часто используемыми печатными символами ASCII , расположенными после малоиспользуемых управляющих кодов, вопреки замыслу кода MTF сохранять то, что обычно используется, в начале. Если повернуть словарь, чтобы поместить наиболее используемые символы на более ранние места, можно получить лучшую кодировку:

>>> import mtfwiki>>> block32 = lambda x : [x + i for i in range(32)]>>> # Sort the ASCII blocks: first lowercase, then uppercase, punctuation/number, and finally the control code and the non-ASCII stuff>>> mtfwiki.common_dictionary = block32(0x60) + block32(0x40) + block32(0x20) + block32(0x00) + list(range(128, 256))>>> mtfwiki.encode("Wikipedia")[55, 10, 12, 1, 17, 9, 9, 3, 7]

Использование в практических алгоритмах сжатия данных.

Преобразование MTF использует преимущества локальной корреляции частот для уменьшения энтропии сообщения. ^{[ нужны разъяснения ]} Действительно, недавно использованные буквы остаются в начале списка; если использование букв демонстрирует локальную корреляцию, это приведет к появлению большого количества маленьких чисел, таких как «0» и «1», в выходных данных.

Однако не все данные демонстрируют такой тип локальной корреляции, а для некоторых сообщений преобразование MTF может фактически увеличить энтропию.

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

Пример

В качестве примера представьте, что мы хотим сжать монолог Гамлета ( «Быть или не быть...» ). Мы можем вычислить размер этого сообщения как 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 .

Внешние ссылки

«Движение вперед» Артуро Сан Эметерио Кампос

[1] Рябко, Борис Яковлевич [на русском языке] (1980). «Сжатие данных средствами «книжной стопки» » (PDF) . Проблемы передачи информации . 16 (4): 265–269. Збл 0466.94007 .

[2] Бентли, Джон Луис ; Слитор, Дэниел Доминик Каплан ; Тарьян, Роберт Эндре ; Вэй, В.К. (1986). «Локально адаптивная схема сжатия данных» . Коммуникации АКМ . 29 (4): 320–330. CiteSeerX 10.1.1.69.807 . дои : 10.1145/5684.5688 . S2CID 5854590 .

[3] Рябко Борис ; Яковлевич Хорспул, Р. Найджел ; Кормак, Гордон Вилли (1987). «Комментарии к: «Локально адаптивная схема сжатия данных» Дж. Л. Бентли, Д. Д. Слиатора, Р. Э. Тарьяна и В. К. Вея» . Комм. АКМ . 30 (9): 792–794. дои : 10.1145/30401.315747 . S2CID 16138142 .

[4] Ривест, Рональд Линн (1976). «О самоорганизующейся эвристике последовательного поиска» . Коммуникации АКМ . 19 (2): 63–67. дои : 10.1145/359997.360000 . S2CID 498886 .

[1]

[2]

[3]

[4]