Python: найдите ближайшую строку (из списка) в другую строку

Скажем, у меня есть string "Hello" и список

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

Как я могу найти n words, которые наиболее близки к "Hello" и присутствуют в списке words?

В этом случае мы имели бы ['hello', 'hallo', 'Hallo', 'hi', 'format'...]

Итак, стратегия заключается в сортировке слов списка из ближайшего слова до самого дальнего.

Я подумал о чем-то вроде этого

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

но он очень медленный в больших списках.

UPDATE difflib работает, но он очень медленный. (words list содержит 630000+ слов внутри (отсортировано и по одному на строку)). Поэтому проверка списка занимает от 5 до 7 секунд для каждого поиска ближайшего слова!

Ответ 1

Используйте difflib.get_close_matches.

>>> words = ['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo', 'question', 'format']
>>> difflib.get_close_matches('Hello', words)
['hello', 'Hallo', 'hallo']

Пожалуйста, посмотрите документацию, потому что функция возвращает по умолчанию 3 или менее ближайших совпадения.

Ответ 2

Существует потрясающая статья с полным исходным кодом (21 строка), предоставленная Питером Норвигом для исправления орфографии.

http://norvig.com/spell-correct.html

Идея состоит в том, чтобы создать все возможные изменения вашего слова,

hello - helo   - deletes    
hello - helol  - transpose    
hello - hallo  - replaces    
hello - heallo - inserts    


def edits1(word):
   splits     = [(word[:i], word[i:]) for i in range(len(word) + 1)]
   deletes    = [a + b[1:] for a, b in splits if b]
   transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1]
   replaces   = [a + c + b[1:] for a, b in splits for c in alphabet if b]
   inserts    = [a + c + b     for a, b in splits for c in alphabet]
   return set(deletes + transposes + replaces + inserts)

Теперь просмотрите каждое из этих изменений в своем списке.

Статья Питера - отличное чтение и ценность.

Ответ 3

Создайте отсортированный список ваших слов и используйте bisect module, чтобы определить точку в отсортированном списке, в котором ваше слово будет соответствовать в соответствии с порядок сортировки. Основываясь на этой позиции, вы можете дать k ближайшим соседям выше и ниже, чтобы найти 2k самых близких слов.

Ответ 4

возможно heap может вам помочь.

у вас есть куча с именем Heap, которая до тех пор, пока размер не станет меньше n, вы вставляете слова в Heap с помощью функции close [показывает, что эта строка ближе, чем другая строка или нет).

этот метод может помочь вам, когда n невелик:)

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)