Кодирование пар байтов или кодирование диграмм - это простая форма сжатия данных, в которой наиболее распространенная пара последовательных байтов данные заменены ed с байтом, которого нет в этих данных. Таблица замен требуется для восстановления исходных данных. Алгоритм был впервые публично описан Филипом Гейджем в статье «Новый алгоритм сжатия данных» в журнале C Users Journal в феврале 1994 года.
Один из вариантов этого метода оказался полезным в нескольких естественных приложения языковой обработки (NLP), такие как Google SentencePiece и OpenAI GPT-3.
Предположим, что кодируемые данные:
aaabdaaabac
Чаще всего встречается пара байтов «aa», поэтому она будет заменена байтом, который не используется в данных, «Z ". Теперь есть следующие данные и таблица замен:
ZabdZabac Z = aa
Затем процесс повторяется с парой байтов «ab», заменяя ее на Y:
ZYdZYac Y = ab Z = aa
Единственная оставшаяся пара буквальных байтов встречается только один раз, и на этом кодирование может остановиться. Или процесс можно продолжить с рекурсивным кодированием пар байтов, заменив «ZY» на «X»:
XdXac X = ZY Y = ab Z = aa
Эти данные не может быть дополнительно сжат с помощью кодирования пар байтов, потому что нет пар байтов, которые встречаются более одного раза.
Чтобы распаковать данные, просто выполните замены в обратном порядке.