Alex Rivera | Logout

Python: find closest string (from a list) to another string

Asked 2012-04-04T20:22:33.813
111

Let's say I have a string "Hello" and a list

words = ['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo','question', 'Hallo', 'format']

How can I find the n words that are the closest to "Hello" and present in the list words ?

In this case, we would have ['hello', 'hallo', 'Hallo', 'hi', 'format'...]

So the strategy is to sort the list words from the closest word to the furthest.

I thought about something like this

word = 'Hello'
for i, item in enumerate(words):
    if lower(item) > lower(word):
      ...

but it's very slow in large lists.

UPDATE difflib works but it's very slow also. (words list has 630000+ words inside (sorted and one per line)). So checking the list takes 5 to 7 seconds for every search for closest word!

Edit
Report

1 Answer

-4

maybe heap can help you .

you have a heap named Heap that until it's size is less than n , you insert words into the Heap using function close [shows this string is closer than another string or not] .

this method can help you when n is small :)

Heap = []
for word in words:
    if len(Heap)<n:
       Heap.insert(word)
    else
       if close(word,Heap[0]): # it means Heap[0] is the nth farthest word until now
             Heap.pop():
             Heap.insert(word)
answered 2012-04-05T08:38:12.660

Your Answer