Толерантный автокомплит

04 August 2012 algorithms

Автокомплит вещь удобная. Он позволяет экономить время на наборе текста, когда множество значений поля закрыто. Хороший автокомплит отличается следующими качествами:

Вот о последнем качестве autocomplete алгоритмов я и хочу сегодня поговорить.

Если вы хотите создать приложение толерантное к вводимой пользователем информации, то исправление опечаток в том или ином виде должно быть. Человек может опечататься в первой букве, может попросту не знать как правильно пишется слово. Поэтому, не очень хорошо что первая же неверно введенная пользователем буква приведет к тому что он не сможет выбрать правильный вариант.

Я значительную часть рабочего дня провожу в IntelliJ IDEA. Отличная среда, пожалуй лучшая. А еще, я использую guava, хорошая библиотека. И есть там такой метод Closeables.closeQuietly(), который закрывает Closeable объект подавляя все исключения. Так вот, когда вы пишете имя метода которого нет в текущем классе, IDEA автоматически предлагает вам сделать static import подходящего метода из других классов.

IntelliJ IDEA static import

Прекрасная фича, которая не работает если вы опечатались. А я ну никак не могу запомнить как правильно пишется слово “quietly”.

IntelliJ IDEA static import reject

В этом случае IDE “фейлит” и предлагает мне создать новый метод. Примерно то же самое происходит и с автодополнением. Стоит мне ввести хотя бы один не тот символ, как тут же “No suggestions”. Я считаю, IDEA могла бы быть гораздо более толерантна к девелоперу на этапе ввода кода. Это же не какой-нибудь там NetBeans :)

Этой же проблемой страдает большое количество продуктов.

Mac OS X Help Search

Встроенный в Mac OS X поиск по позиция системного меню

Mac OS X Spotlight Search

Mac OS X Spotlight

Money

Money — ПО для учета персональных финансов

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

Конечно, разработка первоклассного spellchecker’а дело не простое. Оно требует обучения не тривиальных статистических моделей. Но есть несколько простых подходов, которые позволяют в большинстве приложений сделать автокомплит достаточно толерантным, чтобы пользователи были счастливы в 80% случаев.

Подход №1: Редакционное расстояние

Самое простое решение заключается в том чтобы сортировать все позиции словаря по возрастанию редакционного расстояния и показывать только первые несколько позиций. В качестве редакционного расстояния можно взять расстояние Левенштейна. Расстояние Левенштейна – это минимальное количество операций вставок/удаления/изменения символов необходимое для того чтобы преобразовать исходную строку в целевую.

Список слов близких к слову “пазор” и их редакционные расстояния: позор → 1, позер → 2, дозор → 2, помор → 2, побор → 2, подзор → 2, покер → 3, покос → 3.

Существует статистика что в пределах расстояния Левенштейна 2 находится более 90% опечаток, так что можно показывать только их, чтобы избежать совсем уж неадекватных исправлений.

Достоинства

Недостатки

В целом, решение на основании расстояния Левенштейна будет вполне сносно работать в первом приближении. Его очень просто реализовать, что делает данный подход отличным кандидатом на роль прототипа.

Подход №2: Коэффициент Жаккара и K-gram индекс

Альтернативный подход заключается в том чтобы использовать коэффициент Жаккара как метрику расстояния между строками. Коэффициент Жаккара (Jaccard index) это индекс сходства двух множеств который определяется как отношение мощности пересечения этих множеств к мощности их объединения.

Sets

При коэффициенте Жаккара равном 1 множества равны, при 0 не имеют ни одного общего элемента. Эту метрику можно использовать для оценки близости вводимых пользователем слов к словам из нашего словаря по которому мы делаем autocomplete.

Но для того чтобы иметь возможность расчитать коэффициент Жаккара для двух строк нам надо преобразовать их в множества. Самый простой вариант, разбить строку на символы. Но обычно берут не символы строки, а k-граммы строки (также известны как n-граммы). K-грамма – это непрерывная уникальная последовательность из k символов строки. Дублирующие k-граммы пропускают. Например, в слове “клоун” 3 триграммы (k = 3): “кло”, “лоу” и “оун”. На практике, k выбирают равным в диапазоне от двух до четырех, в зависимости от характера данных.

Cформировав из строк множество k-грамм, мы можем расчитать коэффициент Жаккара между этими строками. Например, триграммный коэффициент Жаккара для пары “corolla” и “corola” будет выше, чем для пары “corona” и “corola”. В первом случае совпадают три триграммы: “cor”, “oro” и “rol”, а во втором случае только две: “cor” и “oro”.

В контексте алгоритма автодополнения, для того чтобы иметь возможность быстро подбирать кандидатов на пользователский запрос, необходимо построить k-gram индекс по словарю автодополнения. K-gram индекс это инвертированный индекс из k-граммы в слова содержащие эту k-грамму. K-gram индекс позволяет быстро находить элементы с наиболее высоким коэффициентом Жаккара предварительно проиндексировав их.

Биграммный индекс (k = 2) для слов: “топор”, “компот” и “оптом” выглядит следующим образом:

  • то → оптом, топор
  • оп → оптом, топор
  • по → компот, топор
  • ор → топор
  • ко → компот
  • ом → компот, оптом
  • мп → компот
  • от → компот
  • пт → оптом

Имея k-gramm индекс алгоритм автодополнения сводится к следующим шагам:

  1. разбить на k-граммы строку введенную пользователем;
  2. для каждой k-граммы получить список слов в которых она встречается (posting list);
  3. сделать merge posting list’ов с подсчетом какое количество раз каждое слово встречается в них. По факту это количество совпавших k-грамм между строкой пользователя и позицией словаря.
  4. отсортировать этот список по убыванию количества совпавших k-грамм;
  5. вернуть первые N позиций пользователю.

Достоинства

Недостатки

Tips & tricks

Некоторые замечания которые могут быть полезны, если вы захотите имплементировать толерантный автокомплит.

В заключениe

Мы рассмотрели два основных инструмента которые позволяют находить и исправлять опечатки. Они могут быть использованы как в чистом виде, так и в составе более сложных стратегий автодополнения. Надеюсь, эта информация даст вам общее представление о том как сделать более толерантное к опечаткам автодополнение.