Какой алгоритм использовать для нахождения повторяющихся слов в строке?

Question

[Aleksandr Govorukhin]

Здравствуйте, друзья!

Подскажите алгоритм для нахождения повторяющихся слов в строке.

P.S. для небольшого количества слов можно записать двойной цикл для сравнения, но такой подход является неэффективным для большого количества слов - он не подходит для одного миллиона слов и т.д.

Answer 1

[Виталий Пухов]

Задача поставлена странно, во первых ни в одном языке нет миллиона слов, а используется в среднем от 3 до 10 тыс. То есть задача для миллиона в корне неверна. В любом случае как минимум 1 проход потребуется в любом случае, я бы сделал так.
1. Создание dictionary слов и их количества
2. Проход по очереди всех слов
3. Поиск текущего слова в списке, если его там нет добавляем в список и количество выставляем в 1, если есть +1 к количеству

В итоге получаем 1 проход по всему тексту и обращение по индексу к dictionary, которое стоит относительно дешево, намного дешевле перебора всего списка.

Похожий подход применял для анализа текстов, в итоге для 20 книг ~500 стр каждая уходило около 3-5 секунд.
Для C# это выглядит так

Comments

[Aleksandr Govorukhin]

можно подробнее? Не разобрался

[Виталий Пухов]

Aleksandr Govorukhin: поподробнее нельзя, т.к. не указан язык, в каждом языке свои подходы для реализации этого, в C# я бы взял Dictionary в качестве списка, а разделение делал по ходу чтения текста встречая любые символы не являющиеся буквами

[Aleksandr Govorukhin]

Виталий Пухов: swift, ну сам алгоритм он должен быть идентичен, что значит Dictionary в C#?

[Виталий Пухов]

Aleksandr Govorukhin: в общем тоже что и в swift www.tutorialspoint.com/swift/swift_dictionaries.htm

[Aleksandr Govorukhin]

Виталий Пухов: все, понял, засовываем слова и их количества? Мы же ведь не знаем их количества

[Aleksandr Govorukhin]

Виталий Пухов: друг, мне нужен алгоритм, распиши

[Виталий Пухов]

Aleksandr Govorukhin: Добавил пример кода к ответу. В Swift почти без изменений может перейти

[Виталий Пухов]

Aleksandr Govorukhin: На миллион строк ушло около 3х секунд

[Aleksandr Govorukhin]

Виталий Пухов: спасибо

Answer 2

[mib]

Можно использовать наивный метод: в базе данных создать таблицу `table`: `word`|`count_words` (primary key `word`). Потом брать все слова по порядку, и добавлять в таблицу. Если такое слово уже есть - увеличивать его количество повторений на 1, примерно так:
INSERT INTO `table` (`word`) VALUES ('$new_word') ON DUPLICATE KEY UPDATE `count_words`=`count_words`+1;

В любом языке не так уж много слов, ну к примеру 50 000, а тескт может быть сколь угодно большим.

А потом сделать выборку, сортированную по количеству повторений.
То-же самое можно сделать без базы данных, при помощи хешей: слово переводить в транслит, и увеличивать счетчик соотв хеша.

Comments

[Виталий Пухов]

решение хорошее, но база имхо тут лишняя, т.к. будет слишком много потрачено времени на операции вставки или selectы из базы, в памяти это отработает в сотни раз быстрее

[Виталий Пухов]

MaxKorz: милион слов это в худшем случае сотня мегабайт памяти, и то если очень криво структуры построены

[mib]

в вопросе речь идет об алгоритме, который просто отличается от перебора цикла в цикле, не дано ни ось ни язык програмирования ни ограничения по времени/памяти и тд

Answer 3

[Армянское Радио]

Сразу нужны уточнения - помещается ли строка в RAM?

Если помещается - за первый проход можно найти концы всех слов (положения всех пробелов в строке).

Это получится список отрезков (начал и концов слов)

Этот список сортируем по длине слов.

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

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

Задача прекрасно подходит для параллельной обработки.

Comments

[Никита Воронцов]

Только сортировка займет O(n*log(n)), против O(n) для случая со словарем.

[Армянское Радио]

Никита Воронцов: А как вы думаете, словарь как-то иначе создается?

[Никита Воронцов]

Армянское Радио: разумеется, нет никакой связи между сортировкой и созданием словаря. Под словарем я имел ввиду хэш-таблицу кстати, поправляюсь.

[Никита Воронцов]

P.S. Если же вы имели ввиду, что создание словаря имеет сложность O(n*log(n)), то это только для случаев, когда словарь представлен списком и нужно каждый раз его проходить, чтобы определить, что инкрементить. В случае же константного времени доступа log(n) превращается в k и мы имеем O(n*k) -> O(n). Константное время доступа реализуется в хэш-таблицах.

[Армянское Радио]

Никита Воронцов: И как же по-вашему будет работать хэш-таблица, не использующая сортировку? Она строится так, чтобы в процессе построения сортировка сохранялась.

В моем алгоритме, можно использовать и такие структуры. Однако, проблема в том, что тогда будет труднее сделать решение параллельным.

[Никита Воронцов]

Армянское Радио: не понял, зачем строить хэш-таблицу так, чтобы сортировка сохранялась? В этом нет нужды и обычно это не реализовано в стандартных хэш-таблицах.

[Никита Воронцов]

Да и сделать его параллельным не сложно - просто разбиваешь список слов на подсписки и для каждого считаешь, потом таблицы сливаешь.

[Армянское Радио]

Никита Воронцов: Как вы собираетесь что-то "быстро" искать в несортированной хэш-таблице?

Хэши хранятся в самосортирующейся структуре данных, каком-либо дереве.

[Никита Воронцов]

Армянское Радио: *рука-лицо*... иди учи как работают хэш-таблицы.

[Армянское Радио]

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

Пока автор не обозначит масштаб трагедии, что-то обсуждать-смысла нет.

Answer 4

[Dimonchik]

я извиняюсь, а
(\w+) \1
чем не подходит?
слова идут не подряд?
тогда строку в массив, сорт и ..

Comments

[Aleksandr Govorukhin]

(\w+) \1 - что за запись? не понял просто.

[Dimonchik]

regexp, Python например

Answer 5

[uvelichitel]

Фильтр Блума

Answer 6

[SeptiM]

А префиксное дерево не подойдет? Я бы сначала убрал бы все знаки препинания, понизил регистры, а потом его построил. Можно в каждой вершине хранить число листьей в поддереве и находить за O(1/phi) все слова, которые встречаются хотя бы phi * n раз, где n -- число всех слов.