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

Question

我正在努力通过使用Levensthein距离来纠正土耳其语单词。首先，我检测到错误的书面单词，并将其与包含所有土耳其语单词的列表进行比较。该列表包含约1.300.000字。我使用Levensthein距离将单词与列表中的单词进行比较。这是我的代码部分。index_to_track_document_order = 1log_text = ''main_directory = "C:\\words.txt"f= codecs.open(main_directory,mode="rb",encoding="utf-8")f=f.readlines()similarity = 0text_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 length

word_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_find

target_length = len(text_to_find)

x = 2 #the length difference we'd like to look at words

for 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