Spell correction when a "word" can consist of multiple words

ThePortakal 0
Viewed 24

I have a set

cities = {'london', 'paris', 'tokyo', 'new york', 'new york city', 'san francisco'}

and a string

user_input = 'london new yorQ Sity berlin pariX'

How can I return a list

result = ['london', 'new york city', 'berlin', 'paris']

The typos are at most 2 edit distance away from the original city name. If the cities had 1-word length, then this would be an easy problem. How can I do this when cities have multiple words?

Note that the algorithm specifically chose new york city instead of new york.

edit-distance levenshtein-distance python
1 Answers
def editDistance(str1, str2, m, n):
    if m == 0:
        return n
    if n == 0:
        return m
 
    if str1[m-1] == str2[n-1]:
        return editDistance(str1, str2, m-1, n-1)
 
    return 1 + min(editDistance(str1, str2, m, n-1),   
                   editDistance(str1, str2, m-1, n),    
                   editDistance(str1, str2, m-1, n-1)   
                   )
 
cities = ['london', 'paris', 'tokyo', 'new york', 'new york city', 'san francisco']
user_input = 'london new yorQ Sity berlin pariX'
user_input_list = user_input.split()


def f1(user_input_list,cities3):
    ans=[]
    current=''
    for ui in user_input_list:
        t=1
        for city in cities3:
   
            if(editDistance(ui, city, len(ui), len(city))<=2 or editDistance(current, city, len(current), len(city))<=2):
                ans.append(city)
                current=''
                t=0
        else:
                if(t==1):
                    current=current.strip()+" "+ui.strip()
               
               
    return ans

def f2(cities1,cities2):
    for c1 in cities1:
     for c2 in cities1:
        if((c2 in c1) and c1!=c2):
            if(len(c1)>len(c2)):
                cities2.remove(c2)
            else:
                cities2.remove(c1)
    return cities2
    

org_cities= f2(cities+[],cities+[])
print(f1(user_input_list, org_cities))

This will give you the expected answer.Berlin not in the user_input answer(reference for edit distance code :https://www.geeksforgeeks.org/edit-distance-dp-5/):

['london', 'new york city', 'paris']
YJR0
Related