Вопрос по list, algorithm, python, string – Python: найти ближайшую строку (из списка) к другой строке

43

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

<code>words = ['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo','question', 'Hallo', 'format']
</code>

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

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

Таким образом, стратегия состоит в том, чтобы отсортировать слова списка от самого близкого слова до самого дальнего.

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

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

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

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

630 000 слов отсортированы? Они в файле, одно слово в строке? Peter Wood
отсортировано и по одному в строке да Laura
Может быть, вы ищете что-то вроде редактирования расстояния или расстояния Левинштейна? tripleee
Точно, это в значительной степени зависит от того, каково ваше определение ' Ближайший' является Gareth Latty
Как ты собираешься определить «ближайший»? В вашем примере кода вы используете лексикографическое сравнение, но ранжирование по критерию «эрмитаж» лучше подходит для слова «привет», чем «желе». Nick Johnson

Ваш Ответ

2   ответа
68

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

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

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

Разница Левенштейна также может быть использована. Есть хорошая реализация на pytho Pypi.python.org / PyPI / питон-Левенштейна Maksym Polshcha
Просто быстрый FYI:difflib.get_close_matches("Hallo", words, len(words), 0) даст все совпадения Niklas B.
@ Oleh, мне было интересно, знаете ли вы, есть ли альтернативаdifflib.get_close_matches которые возвращают индексы списка, а не строки. Я отправил другой вопрос здесь toto_tico
difflib работает, но тоже очень медленно. (список слов содержит 630000+ слов внутри). Поэтому проверка списка занимает от 5 до 7 секунд для каждого поиска ближайшего слова! Laura
@ Laura Есть разница между медлительностью и длительностью. 7 секунд может быть долгим, но не медленным. Peter Wood
21

предоставленная Питером Норвигом об исправлении орфографии.

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

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

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)

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

Статья Питера отлично читается и достойна прочтения.

Похожие вопросы