字符串搜索算法可以快速匹配大量未缩短字符串中的缩写吗？

Question

我很难找到符合我的要求的字符串匹配算法。

我有一个非缩写形式的字符串非常大的数据库，需要与任意缩写匹配。字符之间没有字母的实际子字符串也应该匹配，并且分数越高。例如：如果要匹配的单词是“下载”，我搜索了“下”，“ownl”，然后“dl”，我会得到“down”的最高匹配分数，然后是“ownl” “然后是”dl“。

该算法将不得不优化的速度和大量的字符串进行搜索，并应允许我拉回匹配项目字符串列表（如果我已添加“下载”和“上传”到数据库，搜索“加载”应该返回两者）。记忆仍然很重要，但不如速度那么重要。

任何想法？我对这些算法做了大量的研究，但是我还没有发现任何这种算法甚至可以接触缩写，更不用说所有这些条件了！

Answer 1

我不知道Peter Norvig的spell checker是否可以用某种方式适应这个问题。

这是一个我尚未开始研究的领域，但它是如此优雅的解决方案，值得了解。