Как наиболее эффективно рассчитать расстояние слова от других слов в списке?

Question

Я работаю над исправлением слов Turki sh, используя расстояние Levensthein . Прежде всего, я обнаруживаю неправильно написанные слова и сравниваю их со списком, который содержит все слова Turki sh. Список содержит около 1 300 000 слов. Я использую расстояние Левенштейна, чтобы сравнить слова со словами в списке. Вот часть моего кода.

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

Индексируйте ваши слова по длине. Большинство похожих слов имеют одинаковую длину или одно или два длинных аппартамента. Слово cat (длина 3) аналогично слову can (длина 3), но оно не будет очень похоже на caterpillar (длина 11), поэтому нет смысла сравнивать левенство в два слова с большой разницей в длине. Таким образом, в целом вы сохраняете много сравнений, потому что вы сравниваете только слова примерно одинаковой длины.

#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_simility' сохраняется, вы просто копируете его в 'сходство'. Использование yield вернет генератор, который не хранит все значения в памяти, они генерируют значения на лету.