时间戳

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

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

问题描述

我正在使用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 分钟才能完成。我如何优化代码以便它可以在更短的时间内完成。谢谢你。

标签： pythonnlplevenshtein-distance

解决方案

按长度索引您的单词。大多数相似的词具有相同的长度，或者有一个或两个长度。一个词cat（长度3）和词（长度3）相似can，但不会和caterpillar（长度11）很相似，所以没有理由去比较长度相差很大的两个词的levensthein。所以总的来说，你节省了很多比较，因为你只比较长度接近的单词。

#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只需要计算一次。如有必要，您可以将其保存为泡菜。

另外，我没有测试代码，但大体思路应该很清楚。如果还没有找到最相似的词，甚至可以扩展这一想法以动态扩展长度差异。

推荐阅读