Поиск по нескольким ключевым словам (от 100 до 1000) (алгоритм поиска строк) в PHP

У меня есть эта проблема, которую нужно решить в моем PHP-проекте, где некоторые ключевые слова (от нескольких сотен до нескольких тысяч, длина может варьироваться) необходимо искать в строке длиной около 100-300 символов, иногда меньшей длины 30-50 символов. Я могу предварительно обработать ключевые слова для повторного использования для новых экземпляров строк поиска. Я новичок в PHP и не нашел способа сделать это в библиотеке PHP. Немного поискав, я нашел несколько хороших кандидатов в алгоритме Ахо Корасика, а затем это усовершенствование Сунь Ву и Уди Манбера, которое также известно как agrep (или является частью agrep): http://webglimpse.net/pubs/TR94-17.pdf

Есть также Rabin Karp, Suffix Trees и т. д., но они не выглядели вполне подходящими, так как первый был для ключевых слов фиксированной длины, а последний кажется довольно общим и потребует довольно много работы.

Может ли кто-нибудь сообщить мне, является ли самостоятельная реализация Agrep/Sun Wu-Manber в php хорошим способом решить эту проблему? Еще какие-то замечания?

РЕДАКТИРОВАТЬ: как я упоминал ниже в комментарии, существуют сотни или более различных ключевых слов для поиска, поэтому регулярное выражение не поможет. Так что ответ бесполезен.


php search keyword agrep string-algorithm
person aditya    schedule 12.07.2011    source источник
comment
Есть много способов сделать это, первый вопрос: откуда берутся слова?   -  person GodFather    schedule 12.07.2011
comment
ключевые слова являются фиксированным набором, строка для поиска будет отличаться для каждого выполнения поиска. Так что я могу сделать некоторую предварительную обработку ключевых слов.   -  person aditya    schedule 12.07.2011
comment
Что вы можете попробовать сделать, так это. Поместите ключевые слова в массив; затем выполните поиск компаратора клиентов в массиве. Ваша функция сравнения сравнит вашу доступную для поиска строку с отдельными ключевыми словами. Другим вариантом было бы подготовить одно большое регулярное выражение со всеми вашими ключевыми словами - это будет выглядеть так: /keyword1|keyword2|keyword3|.../ - конечно, вам нужно будет правильно экранировать специальные символы. Затем вы можете просто использовать preg_match(), чтобы увидеть, есть ли совпадение.   -  person Aleks G    schedule 12.07.2011
comment
Я согласен, если у вас есть фиксированный набор слов, вы можете использовать preg_match, но если у вас большой набор для поиска, возможно, это может быть немного медленным.   -  person GodFather    schedule 12.07.2011
comment
создание единого регулярного выражения для всех ключевых слов на самом деле похоже на алгоритм Ахо-Корасика, о котором я упоминал. Это будет нетривиально сделать стандартным алгоритмом, так как это несвязанные отдельные слова.   -  person aditya    schedule 12.07.2011
comment
Другой способ - поместить набор в базу данных в текстовое поле и реализовать полнотекстовый поиск, это будет быстрее, а результат может быть более точным.   -  person GodFather    schedule 12.07.2011

Ответы (2)


arrow_upward
1
arrow_downward

Я думаю, что вы можете решить эту проблему, используя метрику «расстояние Левенштейна».

Из Википедии;

В теории информации и информатике расстояние Левенштейна представляет собой строковую метрику для измерения величины различия между двумя последовательностями.

Кроме того, в PHP есть метод levenshtein(). Используйте свой список ключевых слов в качестве массива и строки для поиска в качестве входных данных и перебирайте свой массив и используйте levenshtein() на каждой итерации для сопоставления.

person edigu    schedule 15.06.2012

arrow_upward
0
arrow_downward

Начиная с PHP 5.5, PHP strtr использует алгоритм Ву-Манберса для сопоставления нескольких шаблонов. См. commit ccf15cf2 в репозитории PHP git. для получения подробной информации о реализации. Это довольно эффективно, по моему опыту.

Реализация алгоритма Aho-Corasick на чистом PHP доступна здесь: https://packagist.org/packages/wikimedia/aho-corasick

person Ori    schedule 15.06.2015