Все задачи
Средне Решено: 0 Процент решений: 0%

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

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

Чему вы научитесь

  • Считать пары соседних символов
  • Многократно сливать самую частую пару
  • Понять, как устроены токенизаторы в стиле GPT

Условие

Токенизаторы в стиле 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

Примеры

Пример 1
Ввод:
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"};

Пояснение

Пары: "l o" и "o w" встречаются по 3 раза; при равенстве побеждает "l o" ("l" < "o"), что даёт "lo". Затем "lo w" встречается 3 раза и даёт "low". Результат: ["lo", "low"].

Пример 2
Ввод:
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"};

Пояснение

"aaa" содержит пару "a a" дважды. Слияние слева направо даёт "aa" + "a". Затем "aa a" сливается в "aaa", и в слове остаётся один символ, поэтому третьему слиянию нечего делать. Результат: ["aa", "aaa"].

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

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

Подсказка 2

Используйте подсчёт пар и детерминированное разрешение ничьих, сравнивая пару как две строки, а затем обновляйте каждое слово слева направо.

Подсказка 3

Следите за словами, которые сжимаются до одного символа; когда нигде больше нет соседней пары, остановитесь, даже если слияния ещё остались.

Ожидаемая сложность

O(num_merges * total_symbols) по времени, O(total_symbols) по дополнительной памяти

Ссылки

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

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.