假设我有一个字符串 "Hello" 和一个列表
words = ['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo','question', 'Hallo', 'format']
如何在列表words中找到与"Hello"最接近的n个单词？
在这种情况下，我们会有['hello'，'hallo'，'Hallo'，'hi'，'format'...]
因此，策略是将列表words按从最接近单词到最远的顺序排序。
我考虑了类似以下的代码：
word = 'Hello'
for i, item in enumerate(words):
if lower(item) > lower(word):
...
但是在大型列表中非常缓慢。
更新： difflib 可以使用，但在大型列表中也非常缓慢。(单词列表内含 630000+ 单词（已排序，每行一个））。因此，对于每个搜索最接近的单词，检查列表需要 5 到 7 秒钟！
>>> words = ['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo', 'question', 'format']
>>> difflib.get_close_matches('Hello', words)
['hello', 'Hallo', 'hallo']
difflib.get_close_matches("Hallo", words, len(words), 0) 可以列出所有匹配项 :) - Niklas B.difflib背后的算法吗？我很想了解它。 - MAC有一篇很棒的文章由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)
现在，在你的列表中查找每个编辑。
Peter的文章很棒，值得一读。
创建一个排序后的单词列表，并使用bisect模块来确定根据排序顺序单词应该放置在排序列表中的位置。基于该位置，您可以提供k个最近邻居以上和以下，以找到2k个最接近的单词。
我在查看这个答案，以获取最接近列表或可能替代项的匹配
difflib.get_close_matches
import re
from collections import Counter
def words(text): return re.findall(r'\w+', text.lower())
# WORDS = Counter(words(open('big.txt').read()))
class WordMatcher:
def __init__(self, big_text):
self.WORDS=Counter(words(big_text))
self.N = sum(self.WORDS.values())
def P(self, word):
"Probability of `word`."
return self.WORDS[word] / self.N
def correction(self, word):
"Most probable spelling correction for word."
return max(self.candidates(word), key=self.P)
def candidates(self, word):
"Generate possible spelling corrections for word."
return (self.known([word]) or self.known(self.edits1(word)) or self.known(self.edits2(word)) or [word])
def known(self, words):
"The subset of `words` that appear in the dictionary of WORDS."
return set(w for w in words if w in self.WORDS)
def edits1(self, word):
"All edits that are one edit away from `word`."
letters = 'abcdefghijklmnopqrstuvwxyz'
splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
deletes = [L + R[1:] for L, R in splits if R]
transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
replaces = [L + c + R[1:] for L, R in splits if R for c in letters]
inserts = [L + c + R for L, R in splits for c in letters]
return set(deletes + transposes + replaces + inserts)
def edits2(self, word):
"All edits that are two edits away from `word`."
return (e2 for e1 in self.edits1(word) for e2 in self.edits1(e1))
也许 堆 可以帮助你。
你有一个名为 Heap 的堆，直到它的大小小于 n，你使用函数 close [显示这个字符串是否比另一个字符串更接近] 将单词插入到 Heap 中。
当 n 很小时，这种方法可以帮助你 :)
Heap = []
for word in words:
if len(Heap)<n:
Heap.insert(word)
else
if close(word,Heap[0]): # it means Heap[0] is the nth farthest word until now
Heap.pop():
Heap.insert(word)