Python:找到最接近的字符串(从列表中)到另一个字符串

Question

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

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

如何找到n words最接近"Hello"列表并出现在列表中的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

使用difflib.get_close_matches.

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

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

Answer 2

Peter Norvig提供了一篇关于拼写修正的完整源代码(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)

现在,在列表中查找每个编辑内容.

彼得的文章很精彩,值得一读.