Слияния Byte Pair Encoding (BPE)

Токенизаторы в стиле GPT используют Byte Pair Encoding: начните с отдельных символов и многократно объединяйте самую частую пару соседей в новый символ.

1. Разбейте каждое слово из words на символы. Повторяющиеся слова учитываются несколько раз.
2. Подсчитайте каждую пару соседних символов по всем словам.
3. Выберите самую частую пару. При равенстве выберите наименьшую пару, сравнивая (первый символ, второй символ) как строки.
4. Замените каждое вхождение этой пары слева направо объединённым символом и запишите объединённый символ.
5. Повторите num_merges раз или остановитесь раньше, если ни в одном слове больше нет двух символов.

Реализуйте bpe_merges(words, num_merges).

Входные данные

words: Обучающие слова (строчные буквы).

num_merges: Сколько слияний выучить.

Выходные данные

Верните объединённые символы в порядке их изучения.

Ограничения

1 ≤ число слов ≤ 1 000, 1 ≤ длина каждого слова ≤ 30

0 ≤ num_merges ≤ 200

Примеры

Ввод:
words = ["low", "lower", "lowest"]
num_merges = 2

Ожидаемый вывод:
expected = ["lo", "low"]

Ввод:
std::vector<std::string> words = {"low", "lower", "lowest"};
long long num_merges = 2;

Ожидаемый вывод:
std::vector<std::string> expected = {"lo", "low"};

Ввод:
string[] words = new string[] {"low", "lower", "lowest"};
long num_merges = 2;

Ожидаемый вывод:
string[] expected = new string[] {"lo", "low"};

Ввод:
words = ["aaa"]
num_merges = 3

Ожидаемый вывод:
expected = ["aa", "aaa"]

Ввод:
std::vector<std::string> words = {"aaa"};
long long num_merges = 3;

Ожидаемый вывод:
std::vector<std::string> expected = {"aa", "aaa"};

Ввод:
string[] words = new string[] {"aaa"};
long num_merges = 3;

Ожидаемый вывод:
string[] expected = new string[] {"aa", "aaa"};

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

• Sennrich, Haddow and Birch, Neural Machine Translation of Rare Words with Subword Units
• Hugging Face course, Byte-Pair Encoding tokenization