What is the most efficient way to calculate the distance of a word with the other words in a list?

user_3852357 0
Viewed 206

I am working on correcting Turkish words by using Levensthein distance. First of all I detect wrong written words and compare them with a list that contains all Turkish words. The list contains about 1.300.000 words. I use Levensthein distance to compare word with the words in the list. Here is the part of my code.

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))

As I mentioned, word.txt contains more than a million records and so that my code takes more than 5 minutes to complete. How I can optimize the code so that it can complete in a shorter time. Thank you.

levenshtein-distance nlp python
2 Answers

Index your words by length. Most similar words are of the same length, or one or two lengthes appart. A word cat(length 3) is similar to the word can(length 3), but it won't be very similar to caterpillar(length 11), so there is no reason to compare the levensthein of the two words with a big difference in length. So in total, you save lot of comparisons, because you only compare words of near similar lengths.

#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))

Note: The creation of word_dict needs to be calculated only once. You can save it as a pickle if necessary.

Also, I did not test the code, but the general idea should be clear. One could even extend the idea to exend the length difference dynamically, if there was not yet found the most similar word.

user_47641240

Every time you say

similarity = new similarity

the old 'new_similarity' is kept, you are simply copying it to 'similarity'. Using yield will return a generator which does not store all the values in memory, they generate the values on the fly.

user_116185770
Related