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 секунд для каждого поиска ближайшего слова!

4 Solutions collect form web for “Python: найдите ближайшую строку (из списка) в другую строку”

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

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

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

Существует удивительная статья с полным исходным кодом (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) 

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

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

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

может быть, куча может вам помочь.

у вас есть куча с именем 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) 
  • Удаление неразрывных пробелов из строк с использованием Python
  • Закрепление строк unicode в Python
  • ошибка «неверный литерал для int () с базой 10:« продолжает расти »
  • Когда использовать% r вместо% s в Python?
  • Разбирая пустую строку в Python, почему split () возвращает пустой список в то время как split ('\ n') возвращает ?
  • Чтение текстового файла и разбиение его на отдельные слова в python
  • Разделить строку и просто получить номер в python?
  • Форматирование множественных строк
  • Python - лучший язык программирования в мире.