Кодирование пар байтов

Кодирование пар байтов ^[1]^[2] или кодирование диграмм ^[3] - это простая форма сжатия данных, в которой наиболее распространенная пара последовательных байтов данных заменяется байтом, которого нет в этих данных. Таблица замен требуется для восстановления исходных данных. Алгоритм был впервые публично описан Филипом Гейджем в статье «Новый алгоритм сжатия данных» в журнале C Users Journal в феврале 1994 года . ^[4]

Вариант техники показал , чтобы быть полезным в нескольких обработки естественного языка (NLP) приложений, таких как Google «ы SentencePiece, ^[5] и OpenAI » ы GPT-3 . ^[6]

Пример кодировки пары байтов [ править ]

Предположим, что кодируемые данные

aaabdaaabac

Чаще всего встречается пара байтов «аа», поэтому она будет заменена байтом «Z», который не используется в данных. Теперь есть следующие данные и таблица замен:

ЗабдзабацZ = аа

Затем процесс повторяется с парой байтов «ab», заменяя ее на Y:

ZYdZYacY = abZ = аа

Единственная оставшаяся пара буквальных байтов встречается только один раз, и на этом кодирование может остановиться. Или процесс можно продолжить с рекурсивным кодированием пар байтов, заменив «ZY» на «X»:

XdXacX = ZYY = abZ = аа

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

Чтобы распаковать данные, просто выполните замены в обратном порядке.

См. Также [ править ]

Ссылки [ править ]

^ Гейдж, Филипп (1994). «Новый алгоритм сжатия данных» . C User Journal .
^ «Новый алгоритм сжатия данных» . Журнал доктора Добба . 1 февраля 1994 . Проверено 10 августа 2020 .
^ Виттен, Ян Х .; Моффат, Алистер; Белл, Тимоти С. (1994). Управление гигабайтами . Нью-Йорк: Ван Ностранд Рейнхольд. ISBN 978-0-442-01863-4.
^ "Кодирование пар байтов" . Архивировано из оригинала на 2016-03-26.
^ "Google / фраза" . Google. 2021-03-02 . Проверено 2 марта 2021 .
^ Браун, Том Б .; Манн, Бенджамин; Райдер, Ник; Суббия, Мелания; Каплан, Джаред; Дхаривал, Прафулла; Нилакантан, Арвинд; Шьям, Пранав; Састры, Гириш; Аскелл, Аманда; Агарвал, Сандхини (2020-06-04). «Языковые модели - немногие изучающие». arXiv : 2005.14165 [ cs.CL ].

[CUsersJ_Gage_1994-1] Гейдж, Филипп (1994). «Новый алгоритм сжатия данных» . C User Journal .

[2] «Новый алгоритм сжатия данных» . Журнал доктора Добба . 1 февраля 1994 . Проверено 10 августа 2020 .

[3] Виттен, Ян Х .; Моффат, Алистер; Белл, Тимоти С. (1994). Управление гигабайтами . Нью-Йорк: Ван Ностранд Рейнхольд. ISBN 978-0-442-01863-4.

[4] "Кодирование пар байтов" . Архивировано из оригинала на 2016-03-26.

[5] "Google / фраза" . Google. 2021-03-02 . Проверено 2 марта 2021 .

[6] Браун, Том Б .; Манн, Бенджамин; Райдер, Ник; Суббия, Мелания; Каплан, Джаред; Дхаривал, Прафулла; Нилакантан, Арвинд; Шьям, Пранав; Састры, Гириш; Аскелл, Аманда; Агарвал, Сандхини (2020-06-04). «Языковые модели - немногие изучающие». arXiv : 2005.14165 [ cs.CL ].

[1]