Остаток слов текста¶
Остаток слов текста — число слов, оставшихся в тексте после выполнения определённого условия: удаления заданного подмножества слов, сокращения до заданной длины, отсечения по позиции и т. д. Понятие используется в лингвистике, информатике, теории алгоритмов и при решении олимпиадных задач по программированию, где требуется вывести часть строки, не удовлетворяющую заданному критерию.
¶Определение и постановка задачи
Пусть дан текст (строка) $T$, состоящий из $N$ слов, и задано некоторое правило $R$, по которому каждому слову присваивается признак «удаляется» или «сохраняется». Остаток слов текста — это подстрока $T'$, содержащая только слова, не подлежащие удалению, с сохранением их исходного порядка.
Формально: если $T = w_1, w_2, \dots, w_N$, а $S \subseteq \{1, \dots, N\}$ — множество индексов слов, подлежащих удалению, то остаток — это последовательность $w_i$ для всех $i \notin S$.
Типичные варианты постановки:
- удалить все слова, начинающиеся с гласной;
- оставить только слова длиной более $k$ символов;
- удалить слова, входящие в заданный словарь стоп-слов;
- оставить слова, встречающиеся не более одного раза;
- вывести слова, стоящие после первого вхождения заданного слова.
¶Алгоритмы вычисления
¶Линейный проход
Наиболее распространённый способ — однократный обход массива слов с проверкой условия для каждого слова и записью подходящих в выходной буфер. Сложность по времени $O(N)$, по памяти $O(M)$, где $M$ — число слов в остатке.
`` result = [] for word in words: if not should_remove(word): result.append(word) ``
¶Схема «два указателя»
При необходимости удаления на месте (in-place) используется два индекса: $i$ — позиция чтения, $j$ — позиция записи. Слово $w_i$ копируется на позицию $j$ только если оно сохраняется, после чего $j$ увеличивается. Такой подход позволяет ограничить дополнительную память $O(1)$.
¶Стек и очередь
Если условие зависит от соседних слов (например, «удалить слово, если оно совпадает с предыдущим»), удобно использовать стек: каждое новое слово сравнивается с вершиной, при совпадении вершина снимается, иначе слово кладётся в стек. Итоговый остаток — содержимое стека в обратном порядке.
¶Сложность и оптимизация
| Подход | Время | Память |
|---|---|---|
| Линейный проход | $O(N)$ | $O(M)$ |
| Два указателя (in-place) | $O(N)$ | $O(1)$ |
| Стек | $O(N)$ | $O(M)$ |
| Сортировка + уникализация | $O(N \log N)$ | $O(N)$ |
При работе с большими текстами (миллионы слов) определяющее значение имеет локальность доступа к памяти и использование буферизованного ввода-вывода. В языках с неизменяемыми строками (Java, Python) копирование неизбежно, поэтому предпочтительнее собирать результат в списке и объединять в конце.
¶Применение
¶Обработка естественного языка
В задачах очистки текста от «шума» (служебных слов, повторов, артефактов парсинга) остаток слов текста — основной выходной объект. Стоп-слова удаляются перед построением частотных словарей и векторных представлений.
¶Поиск и индексация
Полнотекстовые поисковые системы хранят нормализованные остатки документов — последовательности лемм без служебных элементов. От качества очистки зависит релевантность выдачи.
¶Олимпиадное программирование
Задачи вида «остаток слова» встречаются на олимпиадах по информатике (Всероссийская олимпиада школьников, этапы РобоСотрудничества и т. д.). Типовой пример: «Дана строка из $N$ слов. Удалите все слова, содержащие букву 'а', и выведите остаток». Ограничения по времени обычно составляют 1–2 секунды, что допускает линейные решения.
¶Компиляторы и интерпретаторы
На этапе лексического анализа исходный код разбивается на токены; часть из них (комментарии, директивы препроцессора) отбрасывается. Остаток — поток токенов, передаваемый в синтаксический анализатор.
¶Частные случаи
- Остаток числа — разность делимого и произведения делителя на частное от деления (остаток от деления). Связь с текстовой задачей — в алгоритмах хеширования строк, где остаток от деления хеша на размер таблицы определяет позицию слова.
- Остаток строки после удаления подстроки — частный случай, когда условие задано не на уровне слова, а на уровне символов.
- Остаток массива после сдвига — при циклическом сдвиге массива на $k$ позиций остаток — это подмассив, начинающийся с позиции $k$.
¶См. также
- Стоп-слово
- Токенизация
- Алгоритм «два указателя»
- Остаток от деления
¶Источники
- Кнут Д. «Искусство программирования», том 1: основные алгоритмы
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ»
- Сборники задач по информатике для олимпиад школьников
- Ресурсы по обработке естественного языка (NLP): учебные материалы по токенизации и нормализации текста
