Сервис Интернет Объявлений

 
30
Сентябрь
2012

Алгоритм поиска нечетких совпадений в PHP




Нечеткий поиск фраз в PHPВсем привет!
Сегодня речь пойдет о нечетких совпадениях в PHP.
В сети можно найти достаточно примеров поиска отдельных слов и сравнения целых текстов.
Но моя задача выглядит так: определить, принадлежит ли текст одной из Веб-страниц.
Или, наоборот: имеется Веб-страница и несколько текстов. Определить, какой текст расположен на этой Веб странице.

Самое неприятное: текст может иметь различные словоформы, длину и дополнительные слова.

Где это нужно? Да везде. В частности, при поиске возможного плагиата, при генерации Мета-тегов и т.д.

Таким образом, мы имеем дело с двумя задачами.

  • 1. Из множества текстов найти такие, которые могут содержать искомый фрагмент;
  • 2. Выбрать тот текст, который действительно с большой вероятностью содержит искомый фрагмент текста.

Я не буду приводить здесь PHP-код. Но дам наводку, как поступать. Учтите, в РНР я недавно.

Первым делом подготавливаем две строковые переменные: одну с искомым тестом, вторую — с текстом, где нужно будет искать. Удаляем из этих строк все символы, разметку и пробелы. Т.е. оставляем две строки, состоящие только из букв и цифр русского и английского языков.

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

Имея много текстов, и упаковав все это в один большой цикл, мы сможем получить несколько значений levenshtein(). Где значение меньше — тот текст и ближе к искомому. Но ,согласитесь, не факт, что текст окажется совпадающим.

Для окончательной проверки текстов на реальную похожесть воспользуемся PHP-функцией similar_text(), которая и покажет нам в процентах сходство текстов.
В зависимости от специфики текста, можно сказать, что тексты со схожестью 80% и выше можно считать одинаковыми.

При реализации этого алгоритма нужно учитывать, что levenshtein() не работает со строками длиннее 255 символов. Так что, продумайте этот момент и разбейте на подстроки, если это нужно.
Также учтите, что перебор может занять много времени. Сократить время перебора поможет увеличение шага сравнения строк. Но здесь Вы приносите в жертву точность.
Хотя, для нечеткого поиска и точность будет нечеткой.

П.С. А ВЫ знали, что дорожные блокираторы могут быть установлены на любой дороге и смогут задержать даже военную технику?

Posted in: На заметку

Читайте далее:

Trackback from your site.

Leave a comment

Security Code: