string - 一种字符串搜索算法，可以快速匹配大量未缩写字符串中的缩写？

Question

我在寻找适合我的要求的字符串匹配算法时遇到了很多麻烦。

我有一个非常大的未缩写形式的字符串数据库，需要与任意缩写匹配。作为实际子字符串且其字符之间没有字母的字符串也应该匹配，并且得分更高。

示例:如果要匹配的单词是“download”，我搜索“down”、“ownl”，然后搜索“dl”，则“down”的匹配分数最高，其次是“ownl”然后是“dl”。

该算法必须针对速度和要搜索的大量字符串进行优化，并且应该允许我拉回匹配项目字符串的列表(如果我将“下载”和“上传”都添加到数据库，搜索“load”应该返回两者)。内存仍然很重要，但不如速度重要。

有什么想法吗？我对其中一些算法进行了大量研究，但我还没有找到任何涉及缩写的算法，更不用说考虑所有这些条件了!

Answer 1

我想知道 Peter Norvig 的 spell checker 是否可以通过某种方式来解决这个问题。

这是一个我还没有开始解决的问题，但它是一个非常优雅的解决方案，值得了解。