加速levenshtein查询

Question

我有一个约100万条记录的多用户数据库管理系统，其结构如下：

1. 后端(MySQL)
   • "DNames“表
     • “全名”字段
     • "ID“字段

2. 前端(MS Access)
   • "levenshtein“函数
   • "lev“查询
     • "lev_dist“字段(使用上述函数计算出的levenshtein距离，排序为asc)
     • “全名”字段
     • "ID“字段

- "srch" textbox in "result" form

我的问题是，当我在没有排序的情况下运行查询(即使用"srch“文本框)时，速度足够快，但是当我使用排序时，大约需要30到90秒才能完成(取决于pc规范)。我需要排序操作来查找"srch“文本框中的文本与数据库之间的前10位(最近的)匹配，那么如何加快这个过程呢？有没有办法让它达到最大5秒？这个过程可以在5台PC机上同时运行。我试过使用MySQL levenshtein 函数，但花了2分钟！

Answer 1

你愿意接受妥协吗？如果数据缓存在buffer_pool中，那么可以在1ms内找到“小”距离内的所有单词？

1. 建立一个大约500万到1000万行的表格(基于你的100万字)。它会有两列-- F( word )，word。
2. 查找F(word)以获得可能的单词列表。

F(字)是一组字符串--取“单词”并删除每个字母，加上原来的单词。例如：

word --> ord, wrd, wod, wor, word
letter --> etter, ltter, leter, lettr. lette, letter

(注意'leter‘发生了两次)

表和查询：

CREATE TABLE ricks_leven ()
    fword VARCHAR(22) NOT NULL,  -- F(word)
    word  VARCHAR(22) NOT NULL,  -- the desired word
    PRIMARY KEY(fword, word)
) ENGINE=InnoDB;

SELECT word, COUNT(*) AS ct
    FROM ricks_leven
    WHERE fword IN ('etter', 'ltter', 'leter', 'lettr'. 'lette', 'letter')
    GROUP BY word
    ORDER BY ct DESC
    LIMIT 10;

完美的匹配将自动排在输出的第一位。接下来可能会出现其他一些“可能”的拼写错误。我不知道Levenshtein距离是否以同样的方式命令结果。

这个算法涵盖了这些常见的排版，它们都有一个很小的Levenshtein距离：

• 任何一封信的下落，
• 相邻字母转位(distance=2，但很重要)，
• 在任何位置添加的字母。

在速度和完整性之间的折衷：

1. 用我的技巧。如果你得到了一些结果，那就退出。
2. 回到缓慢的Levenshtein搜索。