Нечеткий поиск в словаре с универсальным автоматом Левенштейна. Часть 2
В первой части статьи мы рассмотрели универсальный автомат Левенштейна — мощный инструмент для фильтрации слов, отстоящих от некоторого слова W на расстояние Левенштейна не более заданного. Теперь пришло время изучить способы применения этого инструмента для эффективного решения задачи нечеткого поиска в словаре.
Самый простой и самый очевидный алгоритм решения задачи нечеткого поиска в словаре с использованием автомата Левенштейна — алгоритм полного перебора. В этом случае для каждого слова в словаре выполняется оценка расстояния Левенштейна (Дамерау-Левенштейна) до поискового запроса. Пример реализации на С# можно посмотреть в первой части статьи.
Применение даже этого простого алгоритма дает выигрыш в производительности по сравнению с применением методов динамического программирования. Однако, существуют более эффективные алгоритмы.
Базовый алгоритм Шульца и Михова
Рассмотрим первый такой алгоритм — насколько мне известно, он был предложен Шульцом и Миховым (2002), поэтому я буду называть его базовым алгоритмом Шульца и Михова или просто базовым алгоритмом. Итак, пусть для предположительно искаженного слова W и порогового значения расстояния редактирования N задан детерминированный автомат Левенштейна AN (W). Пусть рассматриваемый словарь D также представлен в виде детерминированного конечного автомата AD, имеющего входной алфавит E. Состояния автоматов будем обозначать как q и qD соответственно, функции переходов как V и VD, а множество конечных состояний как F и FD. Предложенный Шульцом и Миховым алгоритм нечеткого поиска в словаре представляет собой стандартную процедуру поиска с возвратом и может быть описан следующим псевдокодом:
Алгоритм начинает работу с начальными состояниями автоматов. По мере подачи на вход новых символов, в стек помещаются последующие состояния если они не пусты. Если очередные состояния обоих автоматов являются конечными — обнаружено искомое слово.
Этот алгоритм можно еще представить себе как «пересечение» конечных автоматов. В результирующую выборку попадают только те слова, которые соответствуют конечным состояниям обоих автоматов. При этом рассматриваются только те префиксы, которые переводят оба автомата в непустое состояние.
Вычислительная сложность алгоритма зависит от размера словаря и расстояния редактирования N. Если N достигает размера самого длинного слова в словаре, то алгоритм сводится к полному перебору состояний автомата AD. Но при решении практических задач, как правило, используются малые значения N. В этом случае алгоритм рассматривает лишь очень небольшое подмножество состояний автомата AD. При N=0 алгоритм находит в словаре слово W за время O (|W|).
Стоит отметить, что описанный алгоритм обеспечивает отсутствие потерь при поиске. То есть 100% слов в словаре, отстоящих от W на расстояние не более N попадут в результирующую выборку.
Особенности программной реализации
Полагаю, вы уже знакомы с такой структурой данных как префиксное дерево. Префиксное дерево известно также как «нагруженное дерево» (или «бор», «луч», «Trie») и успешно используется для хранения словарей. На рисунке представлено префиксное дерево для словаря из четырех слов: «fast», «funny», «fully», «fuzzy».
Если вы не знакомы с префиксным деревом, то можете ознакомиться с публикациями, в которых эта структура рассмотрена подробно, например, здесь.
Почему я хочу использовать для хранения словаря префиксное дерево? Потому что префиксное дерево может быть рассмотрено как конечный автомат. Каждый узел дерева представляет собой состояние автомата. Начальным состоянием является корень дерева, а конечными состояниями — узлы, соответствующие словам. Для каждого узла и символа возможен только один переход — автомат является детерминированным.
Итак, рассматривая префиксное дерево как детерминированный конечный автомат и имея программную реализацию детерминированного автомата Левенштейна, нетрудно превратить псевдокод алгоритма в код на каком-либо языке программирования. Под спойлером пример на C#.
///
/// Find all words in dictionary such that Levenstein distance to typo less or equal to editDistance
///
/// Set of possible corrections
/// Garbled word.
/// Dictionary.
/// Edit distance.
IEnumerable GetCorrections(string typo, TrieNode dictionary, int editDistance) {
var corrections = new List ();
if (string.IsNullOrEmpty (typo.Trim())) {
return corrections;
}
//Create automaton
LevTAutomataImitation automaton = new LevTAutomataImitation (typo, editDistance);
//Init stack with start states
Stack stack = new Stack ();
stack.Push (new TypoCorrectorState () {
Node = dictionary,
AutomataState = 0,
AutomataOffset = 0,
});
//Traversing trie with standart backtracking procedure
while (stack.Count > 0) {
//State to process
TypoCorrectorState state = stack.Pop();
automaton.LoadState (state.AutomataState, state.AutomataOffset);
//Iterate over TrieNode children
foreach (char c in state.Node.children.Keys) {
//Evaluate state of Levenstein automaton for given letter
int vector = automaton.GetCharacteristicVector (c, state.AutomataOffset);
AutomataState nextState = automaton.GetNextState (vector);
//If next state is not empty state
if (nextState != null) {
TrieNode nextNode = state.Node.children [c];
//Push node and automaton state to the stack
stack.Push (new TypoCorrectorState () {
Node = nextNode,
AutomataState = nextState.State,
AutomataOffset = nextState.Offset
});
//Check if word with Levenstein distance <= n found
if (nextNode.IsWord && automaton.IsAcceptState (nextState.State, nextState.Offset)) {
corrections.Add (nextNode.Value);
}
}
}
}
return corrections;
}
Алгоритм FB-Trie
Идем дальше. В 2004 году Михов и Шульц предложили модификацию вышеописанного алгоритма, основная идея которой заключается в использовании прямого и обратного префиксного дерева в сочетании с разбиением поискового запроса W на две примерно равные части W1 и W2. Алгоритм известен под названием FB-Trie (от forward и backward trie).
Под обратным префиксным деревом следует понимать префиксное дерево, построенное по инверсиям всех слов словаря. Инверсией слова я называю просто слово записанное задом наперед.
Важный момент — в своей работе Михов и Шульц показали, что расстояние Дамерау-Левенштейна между инверсиями двух строк равно расстоянию между самими строками.
Работа алгоритма для N=1 основана на следующем утверждении: любую строку S, которая отстоит от строки W на расстояние Дамерау-Левенштейна d (S, W) <= 1, возможно разделить на две части S1 и S2 только так, чтобы выполнялось одно из трех взаимоисключающих условий:
а) d (S1, W1) = 0 и d (S2, W2) <= 1
б) d (S1, W1) <= 1 и d(S2, W2) = 0
в) d (S1, W1») = 0 и d (S2, W2») = 0
В пункте «в» строки W1» и W2» получаются из строк W1 и W2 путем замены последнего символа W1 на первый символ W2 и наоборот. Например, если W1=«FU», а W2=«ZZY», то W1»=«FZ», а W2»=«UZY».
Как можно быстро найти в словаре все слова, которые подходят под вариант «а»? Очень просто: найти в префиксном дереве узел с префиксом W1, затем обойти всех его наследников в соответствии с базовым алгоритмом Шульца и Михова и отобрать те, ключи которых отстоят от W2 на расстояние не более 1.
//May be for some S d(S1, W1) = 0 and d(S2, W2) <= 1?
TrieNode lnode = ForwardDictionary.GetNode (left);
if (lnode != null) {
corrections.AddRange(GetCorrections(right, lnode, 1));
}
Для варианта «б» пригодится обратное префиксное дерево: найдем в нем узел, соответствующий инвертированной строке W2, затем обойдем всех его наследников и отберем те, ключи которых отстоят от инвертированного W1 на расстояние не более 1 — опять же в соответствии с базовым алгоритмом.
//May be for some S d(S1, W1) = 1 and d(S2, W2) = 0?
TrieNode rnode = BackwardDictionary.GetNode (rright);
if (rnode != null) {
corrections.AddRange(GetCorrections(rleft, rnode, 1))));
}
Для варианта «в» необходимо просто поменять местами два символа в слове W на границе разбиения и проверить содержится ли в префиксном дереве полученное слово.
//May be there is a transposition in the middle?
char[] temp = typo.ToCharArray ();
char c = temp [llen - 1];
temp [llen - 1] = temp [llen];
temp [llen] = c;
TrieNode n = ForwardDictionary.GetWord (new string(temp));
if (n != null) {
corrections.Add (n.Key);
}
Чтобы решить задачу нечеткого поиска в словаре алгоритмом FB-Trie, необходимо просто найти три вышеперечисленных множества слов и объединить их.
Для N=2 потребуется рассмотреть на два случая больше:
а) d (S1, W1) = 0 и d (S2, W2) <= 2
б) 1 <= d(S1, W1) <= 2 и d(S2, W2) = 0
в) d (S1, W1) = 1 и d (S2, W2) = 1
И если последний символ строки S1 равен первому символу W2, а последний символ W1 равен первому символу S2, то возможны еще два случая:
г) d (S1, W1») = 0 и d (S2, W2») <= 1
д) d (S1, W1») <= 1 и d(S2, W2’) = 0
Первые два случая легко обнаруживаются по аналогии с вариантами «а» и «б» для N=1, но используется автомат Левенштейна для N=2.
Варианты «г» и «д» для N=2 повторяют варианты «а» и «б» для N=1, только вместо подстрок W1 и W2 используются W1» и W1».
Вариант «в» чуть-чуть сложнее. На первом шаге необходимо найти в прямом префиксном дереве все узлы, соответствующие префиксам, которые отстоят от W1 на расстояние не более 1 (базовый алгоритм). На втором шаге для каждого такого узла необходимо выполнить обход дочерних и отобрать те, которые соответствуют ключам, отстоящим от W2 на расстояние не более 1 (опять же базовый алгоритм).
Для N=3 потребуется рассмотреть уже семь случаев. Приводить их здесь не буду — можете посмотреть в оригинальной статье Михова и Шульца (2004). По аналогии можно продолжить для произвольного N, хотя необходимость в этом при решении практических задач вряд ли возникнет.
Оценки производительности
Любопытно, что время поиска с использованием алгоритма FB-Trie уменьшается по мере увеличения длины слова W.
Детальный анализ времени поиска с помощью алгоритма FB-Trie в сравнении с другими широко известными алгоритмами нечеткого поиска можно найти в работе Леонида Бойцова «Indexing Methods for Approximate Dictionary Searching: Comparative Analysis» (2011). В работе проведено обстоятельное сравнение времени поиска и объема потребляемой памяти для таких алгоритмов как:
- полный перебор;
- различные модификации метода n-грамм;
- различные модификации метода расширения выборки;
- хэширование по сигнатуре;
- FB-Trie и другие алгоритмы.
Я не буду повторять здесь все многочисленные цифры и графики, а ограничусь лишь общими выводами для естественных языков.
Итак, алгоритм FB-Trie обеспечивает разумный компромисс между производительностью и потреблением памяти. Если в вашей прикладной задаче необходимо поддерживать расстояние редактирования 2 и более, а словарь содержит более 500,000 слов — алгоритм FB-Trie рациональный выбор. Он обеспечит минимальное время поиска при разумном расходе памяти (порядка 300% от объема памяти, занимаемого лексиконом).
Если вы решили ограничиться расстоянием редактирования N=1, или у вас маленький словарь, то ряд алгоритмов может работать быстрее (например, Mor−Fraenkel method или FastSS), однако, будьте готовы к повышенному расходу памяти (до 20,000% от размера лексикона). Если вы располагаете десятками гигабайт ОЗУ для хранения нечеткого индекса, вы можете использовать эти методы и при больших размерах словаря.
Чтобы читатель мог решить насколько это много — 500,000 слов, приведу некоторые цифры по количеству слов русского языка (взято отсюда).
- Орфографический словарь Лопатина содержит 162,240 слов — размер файла лексикона 2 МБ.
- Перечень российских фамилий включает не менее 247,780 фамилий — размер файла лексикона 4,6 МБ.
- Полная акцентуированная парадигма русского языка по А.А. Зализняку — это 2,645,347 словоформ, размер файла лексикона около 35МБ.
А что если вы не имеете возможности хранить словарь в виде двух префиксных деревьев? Например, он представлен в виде сортированного списка. В этом случае использование автомата Левенштейна для нечеткого поиска возможно, но нецелесообразно. Возможно — потому что остаются различные модификации полного перебора (например, с отсечением по длине слова |W| плюс минус N). Нецелесообразно — потому что вы не получите выигрыша в производительности по сравнению с более простыми в реализации методами (например, алгоритмом расширения выборки).
Отмечу, что базовый алгоритм Шульца и Михова требует в два раза меньше памяти, чем алгоритм FB-Trie. Однако, за это придется заплатить увеличением времени поиска на порядок (оценка авторов алгоритма).
На этом рассмотрение алгоритмов нечеткого поиска в словаре с использованием автомата Левенштейна считаю законченным.
Да, полные исходные тексты Spellchecker-а на C# можно найти здесь. Наверное, моя реализация не оптимальна с точки зрения производительности, но поможет вам понять работу алгоритма FB-Trie и, возможно, пригодится при решении ваших прикладных задач.
Всем прочитавшим публикацию — огромное спасибо за проявленный интерес.
Ссылки
- Первая часть моей публикации
- Автомат Левенштейна и базовый алгоритм Шульца и Михова (2002)
- Поиск с возвратом
- Алгоритм FB-Trie в статье Михова и Шульца (2004)
- Сайт Леонида Бойцова, посвященный нечеткому поиску
- Хороший пост о нечетком поиске в словаре и тексте
- Пост на Хабре о префиксном дереве
- Алгоритм FastSS
- Исходные тексты к статье на С#
- Реализации на java: раз и два
- Набор словарей русского языка
