Поиск слов в тексте по словарю?

Question

[Ivan Dronov]

Есть словарь 2-3 (Aня, Cаша, Александра, Алекс) тысячи имен и произвольный текст 2-3к символов
Существуют ли самый оптимальный способ поиска точных вхождений имен в этом произвольном тексте.Понятно что можно рекурсивным перебором, но словарь может состоять из 10-100 тысяч имен. Возможно есть какие либо библиотеки или инструменты для этого?

Comments

[Ninazu]

Что дальше нужно сделать? Заменить слова в тексе? Вернуть список?

[posters]

Вы вместе какой-то курс проходите что ли? Уж очень мне этот вопрос ваш напомнил, словно перед вами стоит одна задача, но методы ее реализации вы выбрали разные)
Как посчитать одинаковые значения в массиве php?

[Ivan Dronov]

Ninazu, Да заменить ссылкой или вернуть список найденных слов. Это мелочи

[Ninazu]

Avi Shum Это не мелочи, от этого зависит реализация)

Если заменить. То можно использовать str_replace или preg_replace, если нужно регистронезависимую замену произвести. Он принимает два массива на поиск и на замену. Думаю обьяснять, как из словаря, сделять второй список с заменой и так понятно.

Если поиск совпадений, то разбиваем текст на слова, которые становятся ключём массива, для ислючения неуникальных значений, второй массив ключей представляет из себя словарь. Дальше смотрим какой массив меньше, проходимся по нему и проверяем на array_key_exists

Но это если оперативки хватает.

[Ivan Dronov]

Ninazu, я же написал выше что рекурсия и прочие костыли меня не особо интересует. Ниже человек привел отличный Алгоритм Ахо — Корасик. С помощью алгоритма можно легко масштабироваться, я скинул ссылку на репозиторий в котором есть реализация на C. Все это можно скомпилировать и подключить и вызывать как нативную функцию (гайд прилагается).

Answer 1

[uvelichitel]

Алгоритм Ахо — Корасик

Comments

[Ivan Dronov]

Спасибо! то что нужно https://github.com/ph4r05/php_aho_corasick

[Владимир Олохтонов]

Немного расскажу про этот классический алгоритм для интересующихся, кстати отличный пример против тезиса "алгоритмы не нужны" :)

Самое интересное:
Время поиска O(T + #occurences), затраты памяти O(P*S), где T - длина текста по которому мы ищем, P - общая длина паттернов, S - размер алфавита.

Как это вообще возможно?
Алгоритм строит префиксное дерево на паттернах, а потом поверх него строит конечный автомат, позволяющий быстро выписывать терминальные вершины и поддерживать аналог оптимальной точки отката из алгоритма КМП.

На русской вики есть прекрасная статья про этот алгоритм:
https://ru.m.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3...

Answer 2

[Дмитрий Шицков]

Думаю с задачей отлично справятся системы полнотекстового поиска - sphynx, elasticsearch.
Но, возможно, это пушка для воробья

Answer 3

[АртемЪ]

Существуют ли самый оптимальный способ

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

Answer 4

[Александр Алексеев]

Простая задача. Словарь имён конвертируем в нижний регистр и загружаем в хэш-таблицу или бинарное дерево поиска. Далее пробегаем по тексту, выделяем слова, копируем их в буфер, преобразуя буквы верхнего регистра в нижний, и ищем слово в хеш-таблице(или дереве поиска). Быстрее только за счёт низкоуровневых оптимизаций или я не правильно понял задачу.

Comments

[Ivan Dronov]

Как вариант, но как написали выше Алгоритм Ахо — Корасик более уместен для конкретной задачи