levenshtein替代方案

Question

我有一大堆查询并使用levenshtein计算拼写错误,现在levenshtein导致mysql占用完整的cpu时间.我的查询是UNION语句中的全文搜索+ levenshtein.sql1是我当前的查询,sql2只是全文搜索,这是快速的,并没有使用太多的CPU时间,最后一个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 个候选上计算 levensthein，这比为所有对计算 levensthein 更快。

Solr/Lucene 等专门的全文搜索引擎内置了这个功能。

PostgreSQL 有 pg_trgm contrib 模块 (http://www.postgresql.org/docs/9.0/static/pgtrgm.html)，它的作用就像一个魅力。

您甚至可以使用全文索引在 MySQL 中模拟这一点，但您必须从所有文档中收集单词，将它们转换为 ngram，在它们上创建全文索引，然后将它们全部合并以进行快速查找。这会给冗余、同步带来各种麻烦……不值得你花时间。