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

Question

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

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

            $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";

Answer 1

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

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

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

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

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