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

Токенизатор слов и словарь

Разбейте текст на слова в нижнем регистре и постройте словарь, отсортированный по частоте, — первый шаг любой языковой модели.

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

  • Разбивать текст на токены-слова в нижнем регистре
  • Считать частоты слов
  • Сортировать словарь по частоте, затем по алфавиту

Условие

Языковые модели работают с токенами, а не с сырым текстом. Простой токенизатор переводит текст в нижний регистр и считает словом каждую последовательность букв a-z и цифр 0-9; всё остальное (пробелы, знаки препинания, другие символы) разделяет слова.

Постройте словарь: различные слова, отсортированные по частоте (самое частое первым), при равенстве — по алфавиту. Позиция слова в этом списке — его идентификатор токена.

Реализуйте build_vocabulary(text).

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

text: Произвольный текст.

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

Верните словарь в виде списка слов. Если в тексте нет слов, верните пустой список.

Ограничения

0 ≤ длина text ≤ 100 000

Примеры

Пример 1
Ввод:
text = "The cat sat on the mat. The end!"

Ожидаемый вывод:
expected = ["the", "cat", "end", "mat", "on", "sat"]
Ввод:
std::string text = "The cat sat on the mat. The end!";

Ожидаемый вывод:
std::vector<std::string> expected = {"the", "cat", "end", "mat", "on", "sat"};
Ввод:
string text = "The cat sat on the mat. The end!";

Ожидаемый вывод:
string[] expected = new string[] {"the", "cat", "end", "mat", "on", "sat"};

Пояснение

В нижнем регистре слова такие: the, cat, sat, on, the, mat, the, end. "the" встречается 3 раза; остальные — по одному разу и сортируются по алфавиту: ["the", "cat", "end", "mat", "on", "sat"].

Пример 2
Ввод:
text = "AI, ai and A.I. (2024)"

Ожидаемый вывод:
expected = ["ai", "2024", "a", "and", "i"]
Ввод:
std::string text = "AI, ai and A.I. (2024)";

Ожидаемый вывод:
std::vector<std::string> expected = {"ai", "2024", "a", "and", "i"};
Ввод:
string text = "AI, ai and A.I. (2024)";

Ожидаемый вывод:
string[] expected = new string[] {"ai", "2024", "a", "and", "i"};

Пояснение

Слова: ai, ai, and, a, i, 2024. "ai" встречается дважды; остальные — по одному разу, по алфавиту, цифры перед буквами: ["ai", "2024", "a", "and", "i"].

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

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

Подсказка 1

Сначала выделите только последовательности букв и цифр в нижнем регистре и игнорируйте все остальные символы.

Подсказка 2

Посчитайте, как часто встречается каждое слово, затем отсортируйте по убыванию частоты и по алфавиту при равенстве.

Подсказка 3

Если в тексте нет ни одного допустимого слова, верните пустой список, а не singleton или null.

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

O(n log k) по времени, O(k) по дополнительной памяти

Ссылки

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

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

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

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

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

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