Подход к генерации предложений, который я успешно использовал, но нигде не видел, описан где-либо, заключается в предварительном вычислении предложений (при создании словаря) с использованием «плохих» хеш-функций.
Идея состоит в том, чтобы взглянуть на типы орфографических ошибок, которые делают люди, и разработать хеш-функции, которые бы присваивали неправильное написание тому же сегменту, что и его правильное написание.
Например, распространенной ошибкой является использование неправильного гласного, например определенное вместо определенное . Таким образом, вы разрабатываете хеш-функцию, которая обрабатывает все гласные как одну и ту же букву. Самый простой способ сделать это - сначала «нормализовать» входное слово, а затем поместить нормализованный результат через обычную хеш-функцию. В этом примере нормализующая функция может сбрасывать все гласные, поэтому definite становится dfnt. Затем «нормализованное» слово хешируется с помощью типичной хеш-функции.
Вставьте все слова вашего словаря во вспомогательный индекс (хеш-таблицу), используя эту специальную хеш-функцию. Сегменты в этой таблице будут иметь длинные списки коллизий, потому что хеш-функция «плохая», но эти списки коллизий по сути являются предварительно вычисленными предложениями.
Теперь, когда вы найдете слово с орфографической ошибкой, вы просматриваете списки столкновений для корзины, на которую отображается орфографическая ошибка, во вспомогательных индексах. Та да: У вас есть список предложений! Все, что вам нужно сделать, это оценить слова на нем.
На практике вам понадобятся несколько вспомогательных индексов с другими хеш-функциями для обработки ошибок других типов, таких как транспонированные буквы, одно- или двухбуквенные буквы и даже упрощенный Soundex-подобный для обнаружения фонетических ошибок. На практике я обнаружил, что упрощенные произношения имеют большое значение и по сути устарели некоторые из них, предназначенные для поиска тривиальных опечаток.
Так что теперь вы просматриваете орфографические ошибки в каждом из вспомогательных индексов и объединяете списки столкновений перед ранжированием.
Помните, что списки столкновений содержат только слова из словаря. С подходами, которые пытаются генерировать альтернативные варианты написания (как в статье Питера Норвига), вы можете получить (десятки) тысяч кандидатов, которые вы сначала должны отфильтровать по словарю. С предварительно вычисленным подходом вы получаете, возможно, пару сотен кандидатов, и вы знаете, что все они написаны правильно, поэтому вы можете сразу перейти к ранжированию.
Обновление : с тех пор я нашел одно описание алгоритма, похожее на это, FAROO Distributed Search . Это все еще поиск с ограниченным расстоянием редактирования, но он очень быстрый, потому что этап предварительного вычисления работает как моя идея «плохих хэш-функций». FAROO просто использует ограниченную концепцию плохой хеш-функции.