algorithm - 如何在不使用 Google 的情况下估算 "Did you mean?"？

Question

我知道这个问题的重复:

• How does the Google “Did you mean?” Algorithm work?
• How do you implement a “Did you mean”?
• ...以及许多其他人。

这些问题对算法实际如何工作很感兴趣。我的问题更像是:假设谷歌不存在或者这个功能不存在并且我们没有用户输入。如何实现该算法的近似版本？

为什么这很有趣？

好的。尝试在 Google 中输入“qualfy”，它会告诉您:

Did you mean: qualify

很公平。它对从数十亿用户收集的数据使用统计机器学习来做到这一点。但现在尝试在 Google 中输入“Trytoreconnectyou”，它会告诉您:

Did you mean: Try To Reconnect You

现在这是更有趣的部分。 Google 如何确定这一点？手头有一本字典并使用用户输入再次猜测最有可能的单词吗？它如何区分拼写错误的单词和句子？

现在考虑到大多数程序员无法访问数十亿用户的输入，我正在寻找实现该算法的最佳近似方法以及可用的资源(数据集、库等)。有什么建议吗？

Answer 1

假设你有一个单词字典(最坏情况下字典中出现的所有单词，最好情况下系统数据中出现的所有短语)并且你知道各种单词的相对频率换句话说，您应该能够通过 similarity of the word 的某种组合合理地猜测用户的意思。以及相似词的点击次数。权重显然需要一些试验和错误，但通常用户会更感兴趣一个流行的结果，这个结果在语言上与他们输入的字符串有点远，而不是在语言上更接近但只有一两个有效词在您的系统中点击。

第二种情况应该更直接一些。您找到所有以字符串开头的有效词(“T”无效，“Tr”无效，“Try”是一个词，“Tryt”不是一个词，等等)并且对于每个有效词，您重复剩余字符串的算法。假设您的字典已编入索引，这应该很快。如果您发现能够将长字符串分解为一组没有剩余字符的有效单词的结果，这就是您所推荐的。当然，如果你是谷歌，你可能会修改算法来寻找与实际单词相当接近拼写错误的子字符串，并且你有一些逻辑来处理可以通过足够宽松的拼写检查以多种方式读取字符串的情况(可能使用打破平局的结果数)。