Python：查找与另一个字符串最接近的字符串（从列表中）

Question

假设我有一个string"Hello"和一个列表

words = ['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo','question', 'Hallo', 'format']

如何找到最接近"Hello"并且出现在列表words中的n words？

在这种情况下，我们将有['hello', 'hallo', 'Hallo', 'hi', 'format'...]

因此，策略是将列表中的单词从最近的单词排序到最远的单词。

我想过这样的事

word = 'Hello'
for i, item in enumerate(words):
    if lower(item) > lower(word):
      ...

但在大名单上却很慢。

更新difflib工作，但速度也很慢。（words list内有630000多个单词（已排序，每行一个）。因此，每次搜索最接近的单词，检查列表需要5到7秒！

Answer 1

有一篇很棒的文章有一个完整的源代码（21行）由彼得诺维格提供的拼写更正。

http://norvig.com/spell-correct.html

我们的想法是建立所有可能的文字编辑

hello - helo   - deletes    
hello - helol  - transpose    
hello - hallo  - replaces    
hello - heallo - inserts    


def edits1(word):
   splits     = [(word[:i], word[i:]) for i in range(len(word) + 1)]
   deletes    = [a + b[1:] for a, b in splits if b]
   transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1]
   replaces   = [a + c + b[1:] for a, b in splits for c in alphabet if b]
   inserts    = [a + c + b     for a, b in splits for c in alphabet]
   return set(deletes + transposes + replaces + inserts)

现在，在列表中查找这些编辑。

彼得的文章读得很好，值得一读。

Answer 2

使用^{}。

>>> words = ['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo', 'question', 'format']
>>> difflib.get_close_matches('Hello', words)
['hello', 'Hallo', 'hallo']

请查看文档，因为函数默认返回3个或更少的最接近匹配项。

Answer 3

创建单词的排序列表，并使用bisect module来标识排序列表中单词根据排序顺序适合的位置。根据这个位置，你可以给上下k个最近的邻居，找到2k个最近的单词。