Byte Pair Encoding - простой алгоритм кодирования, который позволяет сжать длину последовательностей за счёт расширения словаря (то есть можно выбирать разные соотношения длины последовательностей и размера словаря).
Этот алгоритм работает в два этапа:
обучение - построение правил замены символов
кодирование - применение построенных правил замены, чтобы сократить длину текста
Разберём упрощённый алгоритм обучения на примере токенизации "косил косой осой".
Найти самую частотную биграмму - по два употребления имеют "ко", "ос", "со" и "ой" - выбираем "ко".
Назначить выбранной биграмме номер. Мы вместо номеров будем использовать заглавные буквы. Назначили: "ко" -> А.
Обновить последовательность с учётом созданного правила подстановки "ко" -> А: "Асил Асой осой".
Повторяем шаги 1-3 для биграммы "со": подстановка "со" -> Б, последовательность "Асил АБй оБй"
Повторяем шаги 1-3 для биграммы "Бй": подстановка "Бй" -> В, последовательность "Асил АВ оВ".
Останавливаемся, когда сделаем заданное количество замен (то есть когда достигнем максимально допустимого размера словаря) или когда заменами не сможем дальше сжать тексты обучающей выборки.
В результате для этой последовательности мы получили словарь размера 10 (7 исходных символов и 3 подстановки) и уменьшили её длину с 16 до 10.
Когда мы кодируем текст, мы повторяем процедуру, жадно (то есть без возвратов и перебора) выбирая самые частотные биграммы и применяя подстановки, сохранённые на этапе обучения. Может так получиться, что две биграммы имеют одинаковую частоту - тогда применяйте правила подстановки в том порядке, в котором они добавлялись в словарь при обучении.
Примените полученные правила подстановки для кодирования текста "косой кокос".
Выберите вариант ответа, соответствующий результату.