альтернатива Левенштейна - PullRequest
Новая
       2

альтернатива Левенштейна

6 голосов
/ 29 января 2011

У меня большой набор запросов, и я использую levenshtein для вычисления опечаток, теперь levenshtein заставляет mysql занимать все время процессора. Мой запрос - полнотекстовый поиск + levenshtein в операторе UNION. sql1 - мой текущий запрос, sql2 - только полнотекстовый поиск, который быстр и не использует слишком много процессорного времени, последний - левентайновый, который достигнет своего пика!

У кого-нибудь из вас есть альтернативный способ получить опечатки? Пожалуйста, не отвечайте на нормализованные данные, я об этом думал, но это не применимо к моим данным, так как я не могу предварительно выполнить сопоставления / вычисления и создать отдельную таблицу с индексами. 

            $sql1 = "(SELECT * FROM ci_sanctions_properties WHERE prop_type='LASTNAME' AND prop_value!='' AND MATCH(prop_value) AGAINST ('+usama bin laden' IN BOOLEAN MODE)) UNION (SELECT s.* FROM (SELECT levenshtein(prop_value, 'usama bin laden') AS dist, sanction_id, prop_type, prop_value FROM ci_sanctions_properties WHERE prop_type='LASTNAME' AND prop_value!='') s WHERE dist < 3) ORDER BY sanction_id";

        $sql2 = "SELECT * FROM ci_sanctions_properties WHERE prop_type='LASTNAME' AND prop_value!='' AND MATCH(prop_value) AGAINST ('+usama bin laden' IN BOOLEAN MODE) ORDER BY sanction_id";

        $sql3 = "SELECT s.* FROM (SELECT levenshtein(prop_value, 'usama bin laden') AS dist, sanction_id, prop_type, prop_value FROM ci_sanctions_properties WHERE prop_type='LASTNAME' AND prop_value!='') s WHERE dist < 3";

1 Ответ

4 голосов
/ 06 февраля 2011

Если вы привязаны только к MySQL, решение не из легких.

Обычно это решается с помощью специализированной индексации ngram для быстрой фильтрации поиска кандидатов, а затем вычисляется levensthein только для примерно 10-50 кандидатов, что быстрее, чем вычисление levensthein для всех пар.

Специализированные полнотекстовые поисковые системыкак в Solr / Lucene это встроено.

PostgreSQL имеет модуль pg_trgm contrib (http://www.postgresql.org/docs/9.0/static/pgtrgm.html), который работает как шарм.

Вы можете даже смоделировать это в MySQL, используя полнотекстовое индексирование, но у вас естьчтобы собирать слова из всех ваших документов, конвертируйте их в ngrams, создавайте полнотекстовые индексы на них и собирайте их все вместе для быстрого поиска. Это приводит к всевозможным проблемам с избыточностью, синхронизацией ... не стоит вашего времени.

...