Получить наиболее релевантное слово (проверка правописания) от 'enchant offer ()' в Python

Question

Я хочу получить наиболее релевантное слово из enchant suggest(). Есть ли лучший способ сделать это. Я чувствую, что моя функция неэффективна, когда дело доходит до проверки большого набора слов в диапазоне от 100 КБ и более.

Проблема с enchant suggest():

>>> import enchant
>>> d.suggest("prfomnc")
['prominence', 'performance', 'preform', 'Provence', 'preferment', 'proforma']

Моя функция для получения подходящего слова из набора предлагаемых слов:

import enchant, difflib

word="prfomnc"
dict,max = {},0
a = set(d.suggest(word))
for b in a:
    tmp = difflib.SequenceMatcher(None, word, b).ratio();
    dict[tmp] = b
    if tmp > max:
       max = tmp

print dict[max]

Result: performance

Изменено:

если я получаю несколько ключей, то есть значений difflib ratio(), я использую многоключевой словарь. Как объяснено здесь: http://code.activestate.com/recipes/440502-a-dictionary-with-multiple-values-for-each-key/

Answer 1

Нет волшебной пули, боюсь ... несколько предложений, однако.

Я предполагаю, что большую часть времени в логике тратится на Вызов difflib SequenceMatcher (). ratio () .В этом нет ничего удивительного, поскольку в этом методе используется вариация алгоритма Rattcliff-Obershelp , который относительно дорогой, с точки зрения использования процессора (но метрика, которую он производит, скорее "на высоте""чтобы найти близкие совпадения, и, вероятно, именно поэтому вам это нравится).

Чтобы быть уверенным, вы должны профилировать эту логику и подтвердить, что действительно SequenceMatcher () является горячей точкой .Может быть, Enchant.suggest () также немного медленный, но мы мало что могли бы сделать с точки зрения кода, чтобы улучшить это (с точки зрения конфигурации, может быть несколько вариантов, например, покончить с личным словарем для сохранения).двойной поиск и слияние и т. д.).

Предполагая, что SequenceMatcher () действительно является виновником, и предполагая, что вы хотите придерживаться показателя сходства Ratcliff-Obershelp в качестве способа выбора наилучшего соответствия,Вы можете сделать [некоторые из] следующих действий:

• вычислить только значение коэффициента SequenceMatcher для верхних (?) 5 элементов из Enchant.
  В конце концов, Enchant.предложить () возвращает свои предложения упорядоченным способом с его лучшими догадками в первую очередь;поэтому, несмотря на различную эвристику, в заказе Enchant также есть ценность, шансы найти совпадение с высоким рейтингом, вероятно, уменьшатся по мере продвижения по списку.Кроме того, даже несмотря на то, что мы можем проигнорировать несколько таких матчей с высоким рейтингом, протестировав только несколько лучших предложений Enchant, мы каким-то образом объединяем «мудрость», обнаруженную в эвристике Enchant, с этими значениями из метрики Ratcliff-Obershelp.
• прекратить вычисление коэффициента SequenceMatcher после того, как будет достигнут определенный порог
  Идея аналогична предыдущей: избегайте вызова SequenceMatcher, когда шансы на нахождение лучше становятся меньше (и как только мы получимПриличный, если не лучший выбор в руках)
• отфильтруйте некоторые слова из Enchant с вашей собственной логикой.
  Идея состоит в том, чтобы провести относительно быстрый / недорогой тест, который может подсказатьнам, что данное слово вряд ли получит хорошую оценку по отношению SequenceMatcher.Например, исключите слова, которые не имеют, по крайней мере, скажем, длину пользовательской строки минус два общих символа.
  Кстати, вы можете использовать некоторые функции [quicker] объекта SequenceMatcher, чтобы получить некоторые данные для эвристики фильтрации.
• используйте функцию SequenceMatcher * quick_ratio * () вместо
  , по крайней мере, в некоторых случаях.
• сохраняют только лучшее соответствие в строке, а нечем использование словаря
  Очевидно, имеет значение только верхний вариант выбора, поэтому, кроме целей тестирования, вам могут не понадобиться [относительно небольшие] накладные расходы на словарь.
• вы можете рассмотрите написание своего собственного метода Рэтклиффа-Обершелпа (или аналогичного) , в котором вводятся различные ранние выходы, когда вероятность достижения текущего максимального отношения мала.ОСТЕРЕГАЙТЕСЬ, вероятно, было бы трудно создать такой же эффективный метод, как язык C из difflib, вы заинтересованы в этом с помощью ранних выходов ...

HTH, удачи; -)

Answer 2

Вам не нужно оставлять dict, если вас интересуют только лучшие матчи

>>> word="prfomnc"
>>> best_words = []
>>> best_ratio = 0
>>> a = set(d.suggest(word))
>>> for b in a:
...   tmp = difflib.SequenceMatcher(None, word, b).ratio()
...   if tmp > best_ratio:
...     best_words = [b]
...     best_ratio = tmp
...   elif tmp == best_ratio:
...     best_words.append(b)
... 
>>> best_words
['performance']