php - 搜索字谜的最快方法是什么？

Question

我有一个包含 267,751 个单词的 MySQL 表。我试图找到找到字谜的最快方法，而不必为每次搜索都搜索整个表，这将非常低效。
为清楚起见:字谜是通过改变另一个单词的字母顺序组合在一起的单词。
我想出了一种方法，我创建了一个新列，其中所有单词中的字母按字母顺序排序。在进行搜索之前，我将搜索词中的字母按字母顺序排序，然后在新列中进行搜索。事实证明，对于精确的字谜(具有相同字母数的单词)，这种方法非常快。
问题不在于找到确切的字谜。但是要找到字谜，你可以少一个字母，少两个字母，少三个字母，一直到两个字母。突然有很多组合，平均搜索时间大约需要 0.5 秒，这很糟糕。
那里有很多字谜搜索引擎，所以这应该不难，但我想不出一个有效的方法来做到这一点。有没有人有任何想法？他们是怎么做到这么快的？
谢谢

Answer 1

第一步正如您所提到的，它简单且非常有效。
构建一个包含 2 个(或更多)列的表:

word VARCHAR(..),
sorted VARCHAR(..),
PRIMARY KEY(word),
INDEX(sorted)

sorted是 word 的字母，但排序。例如，使用“post”:

post -- opst
stop -- opst
pots -- opst
spot -- opst

也就是说，这将找到所有字谜:

SELECT GROUP_CONCAT(word) 
    FROM anagrams
    WHERE sorted = ?

当您提供已排序的字母时。
对于“老鼠”:

art -- art  -- Notice that the `word` == `sorted` in one case
rat -- art
tar -- art

第二步是骗子……
展开那个 sorted列成一个简单的 misspelled列删除一个字母:

opst -- pst
opst -- ost
opst -- opt
opst -- ops

这是一种发现以下类型拼写错误的技术:

一封信掉了

添加一封信

相邻的一对字母转置

在这种情况下，你需要说

WHERE misspell IN ('opst', 'pst', 'ost', 'opt', 'ops')

当然还有 INDEX(misspell)(细节留作练习。)
第三步更多的是相同的—— IN 中越来越短的字符串.
(同样，细节留作练习。)