计算一个单词与列表中其他单词的距离的最有效方法是什么？

Question

我正在努力通过使用Levensthein距离来纠正土耳其语单词。首先，我检测到错误的书面单词，并将其与包含所有土耳其语单词的列表进行比较。该列表包含约1.300.000字。我使用Levensthein距离将单词与列表中的单词进行比较。这是我的代码部分。

index_to_track_document_order = 1

log_text = ''

main_directory = "C:\\words.txt"

f= codecs.open(main_directory,mode="rb",encoding="utf-8")

f=f.readlines()

similarity = 0

text_to_find = 'aktarıları'

best_fit_word = ''

for line in f:

    word = word_tokenize( line, language= 'turkish')[0]

    root = word_tokenize( line, language= 'turkish')[1]

    new_similarity = textdistance.levenshtein.normalized_similarity(text_to_find , word) * 100

    if new_similarity > similarity:

        similarity = new_similarity

        best_fit_word = word

        if(similarity > 90):

            print(best_fit_word, str(similarity)) 

正如我所提到的，word.txt包含超过一百万条记录，因此我的代码需要5分钟以上才能完成。我如何优化代码，使其可以在更短的时间内完成。谢谢。

Answer 1

按长度索引您的字词。大多数相似的单词具有相同的长度，或一个或两个长度的apartart。一个单词（长度3）与单词（长度3）相似，但它不会与（长度11）非常相似，因此没有理由比较长度差异较大的两个单词的levensthein。因此，总的来说，您节省了大量的比较，因为您只比较了接近相似长度的单词。catcancaterpillar#creating a dictionary of words by lengthword_dict = {}for word in f:    word_length = len(word)    if word_length in word_dict:        word_dict[word_length].append(word)    else:        word_dict[word_length] = [word]#now lets compare words with nearly the same length as our text_to_findtarget_length = len(text_to_find)x = 2 #the length difference we'd like to look at wordsfor i in range (target_length-x, target_length+x):    if i in word_dict:        #loop through all the words of that given length.        for word in word_dict:            new_similarity = textdistance.levenshtein.normalized_similarity(text_to_find , word) * 100            if new_similarity > similarity:                similarity = new_similarity                best_fit_word = word                if(similarity > 90):                     print(best_fit_word, str(similarity)) 注意：的创建只需计算一次。如有必要，您可以将其保存为泡菜。word_dict另外，我没有测试代码，但一般的想法应该很清楚。人们甚至可以扩展这个想法，如果还没有找到最相似的词，可以动态地结束长度差异。

Answer 2

每次你说similarity = new similarity旧的“new_similarity”被保留，你只是把它复制到“相似性”。use 将返回一个生成器，该生成器不会将所有值存储在内存中，它们会动态生成值。yield