时间戳

首页 > 解决方案 > 加速 levenshtein 查询

mysql - 加速 levenshtein 查询

问题描述

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

  1. 后端（MySQL）
    • “DNames”表
      • “全名”字段
      • “身份证”字段
  2. 前端（MS 访问）
    • "levenshtein"函数
    • “列夫”查询
      • “lev_dist” 字段（使用上面的函数计算的 levenshtein 距离，按 asc 排序）
      • “全名”字段
      • “身份证”字段
    • “结果”形式的“srch”文本框

我的问题是，当我运行查询（即使用“srch”文本框）而不进行排序时，它的速度足够快，但是当我使用排序时，大约需要 30 到 90 秒才能完成（取决于电脑规格）。我需要排序操作来找到“srch”文本框中的文本与数据库之间的前 10 个（最接近的）匹配项，那么如何加快处理速度？有没有办法让它达到最大 5 秒？此过程可以同时从 5 台 PC 上运行。我尝试使用 MySQL levenshtein函数，但花了 2 分钟！

标签： mysqldatabasems-accesslevenshtein-distance

解决方案

你会接受妥协吗？在大约 1 毫秒内找到“小”距离内的所有单词（如果数据缓存在 buffer_pool 中）？

  1. 建立一个大约有 5M-10M 行的表格（基于你的 1M 'words'）。它将有两列——F(word)，word。
  2. 查找 F(word) 以获取可能的单词列表。

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

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

（注意“字母”出现两次）

表和查询：

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 距离：

  • 任何一个字母的下降，
  • 相邻字母转置（距离=2，但很重要），
  • 在任何位置添加的字母。

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

  1. 用我的技术。如果你得到一些结果，然后退出。
  2. 回到缓慢的 Levenshtein 搜索。

推荐阅读