algorithm - 自动完成算法的新功能

Question

我在面试中遇到了这个问题。很容易实现一个基本的自动完成系统(https://www.futurice.com/blog/data-structures-for-fast-autocomplete/)从前缀字符串中获取字符串列表。现在我们要添加一些新功能。

例如，用户输入:lun pla 输出:lunch plan(多词自动完成)

用户输入:pla 输出:午餐计划

用户输入:unc 输出:lunch(自动完成单词的一部分)

如何实现这些功能？

Answer 1

您可以尝试以下(基本)方法，稍后我会给出扩展建议:

• 加载接受词的字典
• 建立一个BK-Tree从这些词中使用 Levenshtein-Damerau distance作为基础指标
• 在空白字符上拆分输入序列以获取单词
• 对于每个词，检查它是否是一个被接受的词。如果在 BK 树中找不到最近的(在可接受的距离内)单词

现在进行改进:

• 正如您所指出的，有时将两个词组合在一起会更有意义
• 为此使用 Google word2Phrase 算法。您可以找到 C++ 版本 here .
• 使用更聪明的方法来查找单词边界。像 HMM(隐马尔可夫模型)这样的随机方法可能会有用(以避免日期、时间、缩写等被拆分)
• 使用更智能的错误度量。您可以考虑常见的拼写错误、键盘布局错误(对于习惯于输入 qwerty 的人来说，有一些非常具体的错误会突然出现 azerty)等
• 尝试确定单词 part-of-speech type . (形容词、名词、动词等)。通过这样做，您可以更好地完成任务。