О различных подходах к исправлению опечаток написано уже более чем достаточно, поэтому в этой статье я не буду повторять уже известное, а покажу, как написать спеллчекер с нуля — простой, но вполне дееспособный. Всё, что для этого нужно — это список правильных слов и немного С++.
Список слов я взял здесь, но подойдёт и любой другой словарь. Хранить его будем в префиксном дереве (оно же Trie). Вот его несколько экзотическая, не вполне оптимальная, довольно опасная, но, пожалуй, самая лаконичная реализация:
struct trie_t: map<char, trie_t> { } Структура trie_t наследует все методы map. В ключах у этой map записываются буквы слов, а значениями являются снова структуры trie_t, которые наследуют… ну и так далее. Несколько медитативно, но для прототипа сойдёт.
Добавим в структуру вес узла, он пригодится в дальнейшем:
struct trie_t: map< char, trie_t > { size_t w; trie_t() : w(0) {} } Записывать слова в дерево будем с помощью такой функции:
trie_t & add( trie_t & t, const string & s ) { t.w++; return !s.empty() ? add( t[ s[0] ], s.substr(1) ) : t['$']; } Работает она так: берём первый символ слова, записываем в ключ мапы, получаем ссылку на соответствующее поддерево (при необходимости оно тут же и создаётся). Рекурсивно записываем остаток строки в это поддерево. Когда строка исчерпана, добавляем к последнему узлу «знак остановки» — ключ ‘$‘ с пустым поддеревом.
Прочитав слова из заданного файла, занесем их все в словарь:
trie_t glossary; ifstream fi( argv[1] ); string word; while( getline( fi, word ) ) add( glossary, word ); В результате в поле w каждого узла дерева будет записано количество слов, прошедших через этот узел.
Что со всем этим можно делать? Можно распечатать содержимое дерева, перебирая унаследованным итератором ключи и поддеревья каждого узла:
void print( const trie_t & t, const string & prefix = "" ) { for( map<char, trie_t>::const_iterator it = t.begin(); it != t.end(); ++it ) if ( it->first == '$' ) cout << prefix << endl; else print( it->second, prefix + it->first ); } Можно определить наличие или отсутствие заданного слова в дереве:
bool is_known( trie_t & t, const string & s ) { return !s.empty() ? is_known( t[ s[0] ], s.substr(1) ) : t.find('$') != t.end(); } В этой функции, хотя работает она и верно, краткости ради допущена ошибка. Исправлять её я не буду, так как такой «чёткий» поиск нам больше всё равно не пригодится.
Нечёткий поиск
Если представить дерево как некую многократно разветвляющуюся дорогу, то функция поиска слова — путник, идущий по этой дороге. Путнику дан маршрут (искомое слово), и в соответствии с ним он переходит от узла к узлу, зачеркивая пройденные буквы маршрута. Если буквы кончились, остаётся проверить, виден ли «знак остановки».
Теперь представим, что путник как бы одновременно отправляется во все стороны сразу. Каждый из его клонов на каждой развилке ведёт себя точно так же, и так до тех пор, пока в каждую из конечных остановок (то есть листьев дерева) кто-нибудь не придёт. Общее количество путников окажется равным количеству слов, записанных в дерево, и каждый из них пройдёт по своей индивидуальной траектории.
Пусть всем им изначально было задано одно и то же слово-маршрут. При каждом переходе каждый путник, как и раньше, зачеркивает по одной букве в своей копии маршрута. Но если реальное направление перехода не совпадает с зачёркнутой буквой, путник получает штраф. В результате в конце пути у каждого будет накоплена некоторая задолженность. Выстроим всех в ряд, отсортировав по возрастанию этой величины.
Если искомое слово присутствует в словаре, то один путник пройдёт весь путь без штрафов – в отсортированном списке он будет первым. Если слово в словаре отсутствует, то лидировать будет тот, кто прошёл путь с минимальным количеством нарушений.
Собственно, это почти весь алгоритм. Фокус в том, что путь, пройденный лидером, будет ближайшим исправлением заданного слова (или самим этим словом, если опечаток нет), а количество нарушений (отклонений от заданного маршрута) — количеством опечаток.
На старт
Правильнее, конечно, называть дорогу деревом, развилки — узлами, путников — гипотезами, а отклонения от маршрута — операциями редактирования. Но пусть остаются как есть, так как-то поживее. Введём структуру, хранящую все сведения о путнике:
struct rambler_t { string todo; string done; size_t cost; const trie_t * road; rambler_t( const string & t, const string & d, const size_t c, const trie_t * r ) : todo( t ), done( d ), cost( c ), road( r ) {} }; В полях хранится следующее:
todo— путь, который предстоит пройти. Вначале это тот самый маршрут путешествия, то есть исправляемое слово. В конце там остаётся пустая строка.done— пройденная часть пути. Вначале — пустая строка, в конце — перечень пройденных узлов, то есть исправленное слово.cost— сумма наложенных штрафов. На старте — ноль, на финише — как получится.road— местоположение путника. В начале — корень дерева, в конце — один из листьев.
Итак, путник стоит в исходной точке, можно отправляться:
rambler_t R( word, "", 0, &glossary ); Первый шаг
Все возможные направления можно перебрать с помощью итератора, уже пригодившегося при распечатке словаря:
for( map<char, trie_t>::const_iterator it = R.road->begin(); it != R.road->end(); ++it ) { char dest = it->first; // направление движения const trie_t * road = it->second; // следующее распутье // Место для шага вперёд } После совершения шага значения полей структуры изменятся следующим образом:
R.done = R.done + dest; R.todo = R.todo.substr(1); R.road = R.road[ dest ]; С оплатой за проезд возможны два варианта. Если выбранное направление совпадает с «генеральной линией», то переход бесплатен, иначе +1:
R.cost = R.cost + ( dest == todo[0] ? 0 : 1 ); Ок, первый шаг сделан. Правильнее сказать, сразу множество первых шагов — вместо одинокого странника появилась целая команда:
typedef vector<rambler_t> team_t; Осталось лишь повторять шаг за шагом, увеличивая коллектив до тех пор, пока каждый не достигнет своего пункта назначе… Стоп. Есть нюанс, и не один.
Описанный выше «поворот не туда», соответствующий замене буквы слова на другую букву — лишь одна из разновидностей опечаток. Существуют ещё как минимум две: удаление и вставка.
Удаление
Это ситуация «заплатил, но не поехал»: вычёркиваем первую букву из todo, самооштрафовываемся, но перехода не совершаем и ничего не добавляем в done.
R.done = R.done; R.todo = R.todo.substr(1); R.road = R.road; R.cost = R.cost + 1; В результате буква из todo просто теряется по пути, что равносильно её удалению.
Вставка
Тут, наоборот, «бег на месте»: перемещаемся вглубь дерева, добавляем букву в done, но не вычёркиваем ничего из todo.
R.done = R.done + dest; R.todo = R.todo; R.road = R.road[ dest ]; R.cost = R.cost + 1; Пройденная буква в done возникает вне плана, из ниоткуда, что равносильно её вставке.
Отцы и дети
Поскольку на каждом шаге имеет место некоторое распараллеливание миров увеличение численности объектов, будем не модифицировать параметры путника, а создавать новых по его образу и подобию. Следующая функция всё объединяет: получает на вход путника, заполняя на выходе два вектора путников в соответствии с заданным маршрутом, ключами узла дерева и описанными выше правилами.
В вектор team попадают те, кто ещё будет продолжать движение, а в finished — дошедшие до конца, то есть те, у кого todo опустошён, а текущий узел дерева содержит баксы отметку конца слова.
void step_forward( const rambler_t & R, team_t & team, team_t & finished ) { char next = R.todo[0]; // План const string & todo = next ? R.todo.substr(1) : ""; for( map<char, trie_t>::const_iterator it = R.road->begin(); it != R.road->end(); ++it ) { const trie_t * road = &it->second; // Поддерево char dest = it->first; // Ключ if ( next == dest ) team.push_back( rambler_t( todo, // Всё по плану R.done + dest, R.cost, road )); else { team.push_back( rambler_t( todo, // Замена R.done + dest, R.cost + 1, road )); team.push_back( rambler_t( R.todo, // Вставка R.done + dest, R.cost + 1, road )); if ( !next && dest == '$' ) finished.push_back( R ); // Приехали! } } if ( next ) team.push_back( rambler_t( todo, // Удаление R.done, R.cost + 1, R.road )); } Естественный отбор
И второй нюанс: лавинообразно порождая на каждом шагу новых и новых участников процесса, мы поступаем нерационально. Праздно шатающиеся по дереву толпы плохо управляемы, в большинстве своём бесполезны и только попусту жрут ресурсы. Введём ограничения и устроим им соревнование — пусть побегают.
Во-первых, назначим максимально допустимую сумму штрафов, и будем выкидывать всех, кто её превысил, слишком сильно отклонившись от заданного пути.
Во-вторых, будем сбрасывать с дистанции всех отстающих. Правда, возникает риск, что среди изгнанных аутсайдеров кто-то мог бы спринтерским рывком настигнуть лидеров в самом конце забега, но ради оптимизации придётся смириться.
Чтобы выявить отстающих, прикинем шансы каждого на успех, то есть на то, что остаток пути будет пройден без дисквалификации за превышение максимальной суммы. Шанс будем прикидывать так:
double ramb_chances( const rambler_t & a ) { return log( ( a.road->w + 1 ) * ( a.done.size() + 1 ) ) / ( 1 << a.cost ); } Зачем тут логарифм? Что за битовые сдвиги? Почему функция именно такая? Можно попробовать объяснить. Очевидно, что чем больше сумма уже полученных штрафов, тем меньше вероятность дойти до конца. И чем больше слов в поддереве, тем выше вероятность найти среди них хотя бы одно подходящее. А длина уже пройденного пути как бы свидетельствует о «выносливости».
Нужно признать, последнее совсем уж жестоко притянуто за уши. Но в любой эвристике главное — чтоб работала. Эта работает. И, так или иначе, мы близимся к завершению. Обозначим максимальную сумму штрафов как max_cost, максимальный размер команды как team_size.
Поставим первопроходца в начале всех дорог:
team_t walkers, leads; walkers.push_back( rambler_t( word, "", 0, &glossary ) ); Делаем шаг, генерируя следующее «поколение»:
team_t next_g; for( size_t i = 0; i < walkers.size(); ++i ) step_forward( walkers[i], next_g, leads ); В leads записываются завершившие свой путь, в next_g попадают ещё не дошедшие. Сортируем ещё не дошедших по убыванию их шансов дойти:
sort( next_g.begin(), next_g.end(), ramb_chance_cmp ); И повторяем всё это до тех пор, пока ещё есть кому двигаться дальше. Игнорируем тех, чьи штрафы превысили max_cost, и тех, кто не вошёл в team_size лучших:
while ( !walkers.empty() ) { team_t next_g; for( size_t i = 0; i < min( walkers.size(), team_size ); ++i ) if ( walkers[i].cost < max_cost ) step_forward( walkers[i], next_g, leads ); walkers.swap( next_g ); sort( walkers.begin(), walkers.end(), ramb_chance_cmp ); } Кстати, в leads могут оказаться по несколько структур с одинаковыми строками done. Догадаетесь, откуда они там?
Оставим только уникальные элементы:
sort( leads.begin(), leads.end(), ramb_done_cmp ); // сортируем по done leads.resize( distance( leads.begin(), unique( leads.begin(), leads.end(), ramb_uniq ) ) ); // убираем дубли sort( leads.begin(), leads.end(), ramb_chance_cmp ); // сортируем обратно Вот почти и всё.
Сложим всё вышеописанное в функцию spellcheck, передадим в неё наше слово, максимальный штраф и количество кандидатов. Можно употреблять:
while( getline( cin, word ) ) { team_t fixed = spellcheck( word, word.size()/2, 512 ); cout << word << endl; for( size_t i = 0; i < fixed.size(); ++i ) cout << '\t' << fixed[i].done << ' ' << fixed[i].cost << endl; cout << endl; } Ограничение в 512 кандидатов и максимальное отклонение в половину длины заданного слова я подобрал вручную. При таких параметрах производительность алгоритма примерно равна 10 словам в секунду, он справляется со словами корован, инцыклапедея, печмодан и жаднокластник, но не превращает хлеб в пиво.
Теперь совсем всё. Соберемся, запустимся. И вот пример работы нашего несложного, но эффективного механизма исправления опечаток:
нисложый несложный 2 нно эфентиыный эффективный 3 михонезм механизм 3 спровлени исправление 3 опечатог оператор 2 отпечаток 2 опечатка 2 Видно, что не все его результаты идеальны, но это поправимо.
Итоги пути
Уверен, многие узнали в описании одну из разновидностей информированного поиска — алгоритм А*, вернее, его вариацию — алгоритм А* с итеративным углублением и ограничением по памяти. Разумеется, описанный алгоритм является лишь первым, грубым приближением к тому, что реально используется в бою.
Что ещё должен уметь настоящий, боевой спеллчекер?
- В нашем эталонном словаре присутствуют только исходные формы слов, так что
мишки гаммион исправит намишка гамма, что неверно. Нужно иметь представление о морфологии, либо включить в словарь все формы слов. Первое лучше, но сложнее.
- Все слова равны. Это приводит к неточностям в выборе лучшей гипотезы:
перат перст 1 пират 1Проблема решится, если добавить сведения о частоте употребления слов.
- Все ошибки равны. Отсюда проистекают такие неуверенные результаты:
заец заем 1 заяц 1Исправляется путём градации штрафов в соответствии с вероятностью каждой возможной ошибки. Замена
янаеболее вероятна, чеммнац, поэтому более вероятензаяц.
- «Пунто свитчинг». Тут всё просто. Добавляем таблицу соответствия вида
q-й,w-ц,a-фи ещё один тип опечатки — смена раскладки. Готово.
- Склейка и расклейка слов. Это несколько сложнее. Необходимо научить «путников» прыгать из листовых узлов дерева в его корень и отдельно обрабатывать пробелы в их «маршрутах».
- Контекстные исправления. Одни и те же слова в разных ситуациях должны исправляться по-разному. Например,
пришла веспаисушите веспа,пиковый балетипроездной балет,футбольный мечиджедайский мяч. Для исправления таких опечаток нужны статистические данные и/или грамматические правила. Иными словами, модель языка. Вот это уже совсем другая история.
Побочные эффекты
Было бы неправильно напоследок не упомянуть о выходящих за рамки нашей задачи возможностях описанного подхода.
- Если отменить штрафы за добавление символов в конец заданного «маршрута», то получим решение задачи автодополнения.
- Если вставить в программу таблицы фонетического соответствия символов, получим систему распознавания транслита любой степени неоднозначности. Алгоритм найдёт наиболее вероятное слово.
ж → j, zh, g, dj j → й, ж, дж, х ...
- Переходы по дереву по правилам, заданным соответствием цифр и букв превратят спеллчекер в систему набора Т9:
2 → абвг ... 9 → ьэюя
- Стоимость ошибки, рассчитанная не на вероятностях опечаток, а исключительно на расстояниях между клавишами (вернее, их изображениями на сенсорном экране) служит основой системы «скользящего» ввода слов — Swype.
- Задача нечёткого поиска является частью систем распознавания речи, рукописных текстов… Впрочем, достаточно. Об этом написано уже действительно очень много.
Полный текст программы можно найти здесь. Программа несколько длиннее знаменитого наноспеллчекера Питера Норвига, но зато значительно превосходит его по своим возможностям, не уступая по производительности.
Спасибо за внимание!
Небесполезные ссылки
- Источник вдохновения: Online Spelling Correction for Query Completion
- Самый короткий в мире спеллчекер от Питера Норвига
- 1200 способов написать слово «одноклассники» — можно использовать для расчёта модели ошибок
- Альтернативные подходы: раз, два, три
ссылка на оригинал статьи http://habrahabr.ru/company/mailru/blog/178401/
Добавить комментарий