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

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

3 голосов
/ 12 июля 2011

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

Есть также Рабин Карп, Суффикс-деревья и т. Д., Но они выглядели не совсем подходящими, так как первый был для ключевых слов фиксированной длины, а второй кажется довольно общим и потребует довольно много работы.

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

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

Ответы [ 2 ]

1 голос
/ 15 июня 2012

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

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

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

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

0 голосов
/ 15 июня 2015

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

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

...