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

Кодирование пары байтов ^{[ 1 ]}^{[ 2 ]} (также известное как диграммное кодирование ) ^{[ 3 ]} — это алгоритм, впервые описанный в 1994 году Филипом Гейджем для кодирования строк текста в табличную форму для использования в дальнейшем моделировании. ^{[ 4 ]} Его модификация примечательна тем, что представляет собой большой токенизатор языковой модели с возможностью объединения как токенов, кодирующих отдельные символы (включая отдельные цифры или отдельные знаки препинания), так и токенов, кодирующих целые слова (даже самые длинные составные слова). ^{[ 5 ]}^{[ 6 ]}^{[ 7 ]} Эта модификация на первом этапе предполагает, что все уникальные символы представляют собой начальный набор односимвольных n-грамм (т.е. начальные «токены»). Затем последовательно наиболее частая пара соседних символов объединяется в новую, двухсимвольную n-грамму, и все экземпляры пары заменяются этим новым токеном. Это повторяется до тех пор, пока не будет получен словарь заданного размера. Обратите внимание, что новые слова всегда можно составить из окончательных словарных токенов и символов начального набора. ^{[ 8 ]}

Все уникальные токены, найденные в корпусе, перечислены в словаре токенов, размер которого в случае GPT-3.5 и GPT-4 равен 100256.

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

Оригинальный алгоритм

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

Пример

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

aaabdaaabac

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

ZabdZabac
Z=aa

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

ZYdZYac
Y=ab
Z=aa

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

XdXac
X=ZY
Y=ab
Z=aa

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

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

См. также

Ссылки

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

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

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

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

[4] «Кодирование пары байтов» . Архивировано из оригинала 26 марта 2016 г.

[5] Сеннрих, Рико; Береза, Александра; Хэддоу, Барри (31 августа 2015 г.). «Нейронный машинный перевод редких слов с подсловами». arXiv : 1508.07909 [ cs.CL ].

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

[7] "Google/предложение" . Google. 2021-03-02 . Проверено 02 марта 2021 г.

[2022Book_-8] Паас, Герхард; Гиссельбах, Свен (2022). «Предварительно обученные языковые модели» . Базовые модели обработки естественного языка . Искусственный интеллект: основы, теория и алгоритмы. стр. 19–78. дои : 10.1007/978-3-031-23190-2_2 . ISBN 9783031231902 . Проверено 3 августа 2023 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]