Народ накидайте ссылок на алгоритмы спеллчекинга (или коррекции типа гугловского "вы имели в виду...").
Коротко задача. Есть слово оно содержит ошибки, пропуски букв или лишние буквы вплоть до того, что 50% этого слова может быть мусором. Есть словарь. Необходимо по зашумленному слову восстановить эталон (или несколько наиболее похожих на зашумленное слово эталонов). Помехоустойчивые коды использовать нельзя по условию. Куда копать? И где лопата?
Здравствуйте, denisko, Вы писали:
D>Народ накидайте ссылок на алгоритмы спеллчекинга (или коррекции типа гугловского "вы имели в виду..."). D>Коротко задача. Есть слово оно содержит ошибки, пропуски букв или лишние буквы вплоть до того, что 50% этого слова может быть мусором. Есть словарь. Необходимо по зашумленному слову восстановить эталон (или несколько наиболее похожих на зашумленное слово эталонов). Помехоустойчивые коды использовать нельзя по условию. Куда копать? И где лопата?
Возможно, стоит посмотреть в сторону расстояния Левенштейна. Если перебор словаря по скорости будет недотягивать, можно анализ биграмм/триграмм каких-нибудь прикрутить.
Здравствуйте, denisko, Вы писали:
D>Народ накидайте ссылок на алгоритмы спеллчекинга (или коррекции типа гугловского "вы имели в виду..."). D>Коротко задача. Есть слово оно содержит ошибки, пропуски букв или лишние буквы вплоть до того, что 50% этого слова может быть мусором. Есть словарь. Необходимо по зашумленному слову восстановить эталон (или несколько наиболее похожих на зашумленное слово эталонов). Помехоустойчивые коды использовать нельзя по условию. Куда копать? И где лопата?
Есть два пути, которые, по сути, схожи. Представь, что у тебя есть n-мерное пространство, в котором разбросаны слова из твоего словаря.
Помехоустойчивые коды делают приблизительно следующее. Вокруг каждого слова рисуется шар. Условия такие:
* шары не пересекаются
* если в слове допустить k ошибок, каждая из которых будет одного из m допустимых типов ошибок (например, допустимой ошибкой машины при передаче/сохранении/чтении может быть инвертированный бит, допустимой же ошибкой при наборе человеком может быть неправильно набранная, пропущенная или лишняя буква), то ошибочное слово окажется внутри шара, центр которого в правильном слове.
Такие шары позволяют исправлять k ошибок. Разумеется, ценой этого служит тот факт, что шары не пересекаются, т.е. идет избыточное кодирование. Если шары НЕ заполняют все пространство, то остаток пространства обычно используется для выявления большего числа ошибок, восстановить которые невозможно.
Другой путь -- твой. Ты получил точку в пространстве, которая может не соответствовать ни одной точке. Вместо автоматического исправления неправильно набранного слова на центр шара, в котором оно оказалось, ты сортируешь все точки-слова из словаря по возрастанию расстояния до набранного слова. Таким образом, даже если слово есть в словаре, ты можешь предложить другие схожие варианты.
Я все это так описал, чтобы продемонстрировать, что между помехоустойчивыми кодами и твоей задачей большой разницы нет. Помехоустойчивые коды обычно кодируют n-битную информацию (любые комбинации бит возможны) с помощью большего числа бит с возможностью восстановления. В словарях же информация и так закодирована с избыточным использованием "битов", однако автоматическое восстановление не всегда возможно, т.к. часто есть правильные слова, отличающиеся всего на один символ.
Короче, сухой итог. Тебе надо ввести расстояние между словами. Например, расстояние Левенштейна -- минимальное число операций вставки, удаления или замены символа (т.е. учитываются эти три самые распространенные ошибки набора), которые необходимо сделать для превращения одного слова в другое. Проблема с этим расстоянием в том, что даже шары радиуса один будут пересекаться. Т.е. автоматическое восстановление вот так вот в лоб "без контекста" тут не выйдет. Вместо расстояния Левенштейна можешь придумать свое. Например, проблема расстояния Левенштейна в том, что оно не учитывает такие распространенные ошибки, как перемена мест слов или двойное слово. Т.е. два предложения, которые получены простой переменой мест слов, будут иметь большое расстояние. Если же тебе просто искать ошибки в словах и предлагать замены, то самое оно.
Поисковики, как я понимаю, работают несколько иначе. У них огромная база запросов. Поэтому если ты вводишь запрос "x y a", причем все три слова есть в словаре, но в базе такого запроса не было, либо был, но всего пару раз, зато запрос "x y z" встречался в сто раз чаще, то система вполне может спросить, а не это ли ты имел в виду, т.к. рядом с твоей "маленькой" точкой висит такая "жирная" точища.
Здравствуйте, denisko, Вы писали:
D>Коротко задача. Есть слово оно содержит ошибки, пропуски букв или лишние буквы ...
В природе есть старая добрая книжка "Машинное понимание текстов с ошибками" (Файн, Рубанов, 1991 год).
Там очень чётко изложен алгоритм (на основе поиска правых и левых совпадающих цепочек),
и даже приведена его реализация.
Кстати, очень забавно выглядят требования к программе, обусловленные тогдашним железом:
1) объём программы в рабочей памяти — не более 64 кБ
2) все необходимые для работы файлы (программа + данные) должны размещаться на одном
гибком диске, т.е. их суммарный объём не должен превышать 360 кБ
Вот ведь были времена!
Здравствуйте, andy1618, Вы писали:
A>Здравствуйте, denisko, Вы писали:
D>>Коротко задача. Есть слово оно содержит ошибки, пропуски букв или лишние буквы ...
A>В природе есть старая добрая книжка "Машинное понимание текстов с ошибками" (Файн, Рубанов, 1991 год). A>Там очень чётко изложен алгоритм (на основе поиска правых и левых совпадающих цепочек), A>и даже приведена его реализация.
A>Кстати, очень забавно выглядят требования к программе, обусловленные тогдашним железом: A>1) объём программы в рабочей памяти — не более 64 кБ A>2) все необходимые для работы файлы (программа + данные) должны размещаться на одном A>гибком диске, т.е. их суммарный объём не должен превышать 360 кБ A>Вот ведь были времена! A>
А откуда первое требование? Вроде как оно только для .com файлов было? да и второе -- могу соврать, но как я помню, были дискеты на 720 (двойной плотности?)... Впрочем, у меня уже каша в голове, могу врать по обоим пунктам.
Здравствуйте, vadimcher, Вы писали:
V>Поисковики, как я понимаю, работают несколько иначе. У них огромная база запросов. Поэтому если ты вводишь запрос "x y a", причем все три слова есть в словаре, но в базе такого запроса не было, либо был, но всего пару раз, зато запрос "x y z" встречался в сто раз чаще, то система вполне может спросить, а не это ли ты имел в виду, т.к. рядом с твоей "маленькой" точкой висит такая "жирная" точища.
Кстати, вот bing принято ругать, особенно теми, кто его не использует, но вот у них подобные алгоритмы часто работают там, где google тормозит. Например, если набрать "ford exploder", то google молча выдаст результаты для "ford explorer", даже жирным explorer выделит, мол, вы это искали, я так решил. Bing так же выдаст результаты для exploder и для explorer, но при этом явно напишет, что я включит результаты для обеих фраз, если не хотите explorer, нажмите данную ссылку. Т.е. в обоих случаях поисковик сообразил, что совсем рядом находится такая вот "жирная точка", но в первом случае результат автоматически перескочил в нее (вернее результат напоминает скорее смесь результатов обоих запросов), а в случае с бингом поисковик не забыл уточнить, что он выводит результаты обоих запросов.
Если же набрать "toyota exploder" (такой машины нет), то google выдаст только запросы на данную фразу (в основном про взорвавшиеся шины и машины, а также статьи про несуществующую машину Ford Exploder), в то время, как bing сообразит, что explorer относится к автомобильной тематике, и опять-таки спросит, включать ли toyota explorer в поиск. Ссылки при этом будут в основном на статьи, в которых упоминается (существующий в природе) Ford Explorer и какая-нибудь Toyota (например, сравнение их). Из поиска становится достаточно очевидно, что что-то здесь не так. Во-первых, не exploder, а explorer, во-вторых, это Ford, а не Toyota.
Примерно так работают поисковики. По-разному, но в одном направлении. Впрочем, я так думаю, между описанным исходным алгоритмом и реализацией, работающей на таких базах, какие есть у Google-а и Microsoft-а, огромная пропасть. Я так понимаю, у тебя задача проще.
Здравствуйте, denisko, Вы писали:
D>Народ накидайте ссылок на алгоритмы спеллчекинга (или коррекции типа гугловского "вы имели в виду..."). D>Коротко задача. Есть слово оно содержит ошибки, пропуски букв или лишние буквы вплоть до того, что 50% этого слова может быть мусором. Есть словарь. Необходимо по зашумленному слову восстановить эталон (или несколько наиболее похожих на зашумленное слово эталонов). Помехоустойчивые коды использовать нельзя по условию. Куда копать? И где лопата?
Здравствуйте, denisko, Вы писали:
D>Народ накидайте ссылок на алгоритмы спеллчекинга (или коррекции типа гугловского "вы имели в виду..."). D>Коротко задача. Есть слово оно содержит ошибки, пропуски букв или лишние буквы вплоть до того, что 50% этого слова может быть мусором. Есть словарь. Необходимо по зашумленному слову восстановить эталон (или несколько наиболее похожих на зашумленное слово эталонов). Помехоустойчивые коды использовать нельзя по условию. Куда копать? И где лопата?
Питер Норвиг
"How to write a spelling corrector" http://norvig.com/spell-correct.html
Алгоритм + реализации на разных языках.
Есть перевод статьи на русский.
Здравствуйте, Qbit86, Вы писали:
Q>Здравствуйте, denisko, Вы писали:
D>>Народ накидайте ссылок на алгоритмы спеллчекинга (или коррекции типа гугловского "вы имели в виду..."). D>>Коротко задача. Есть слово оно содержит ошибки, пропуски букв или лишние буквы вплоть до того, что 50% этого слова может быть мусором. Есть словарь. Необходимо по зашумленному слову восстановить эталон (или несколько наиболее похожих на зашумленное слово эталонов). Помехоустойчивые коды использовать нельзя по условию. Куда копать? И где лопата?
Q>Возможно, стоит посмотреть в сторону расстояния Левенштейна. Если перебор словаря по скорости будет недотягивать, можно анализ биграмм/триграмм каких-нибудь прикрутить.
Ок, спасибо. А есть методы остановить Левенштейна, если понятно что элементы никак не могут совпадать ?
Здравствуйте, denisko, Вы писали:
Q>>Возможно, стоит посмотреть в сторону расстояния Левенштейна. Если перебор словаря по скорости будет недотягивать, можно анализ биграмм/триграмм каких-нибудь прикрутить.
D>Ок, спасибо. А есть методы остановить Левенштейна, если понятно что элементы никак не могут совпадать ?
Да. Можно задаться порогом, скажем, считать расстояние 4 фейлом. В функции определения метрики по Левенштейну расстояние вычисляется в определённом смысле монотонно: на одном из шагов вычисляются три расстояния, и берётся минимум; если он превышает порог, то можно остановить рекурсивный спуск, ведь накопленное расстояние будет со временем только не убывать.
Но лучше это перепроверить, мало ли я не учёл чего.
Здравствуйте, Qbit86, Вы писали:
Q>Возможно, стоит посмотреть в сторону расстояния Левенштейна. Если перебор словаря по скорости будет недотягивать, можно анализ биграмм/триграмм каких-нибудь прикрутить.
Задачка по теме. На самом деле поиск легко и довольно неплохо оптимизируется.
V>Поисковики, как я понимаю, работают несколько иначе. У них огромная база запросов. Поэтому если ты вводишь запрос "x y a", причем все три слова есть в словаре, но в базе такого запроса не было, либо был, но всего пару раз, зато запрос "x y z" встречался в сто раз чаще, то система вполне может спросить, а не это ли ты имел в виду, т.к. рядом с твоей "маленькой" точкой висит такая "жирная" точища.
Не жирную, но таки упитанную точку можно организовать из частоты встреющегося слова.
06.07.2010 23:41, denisko пишет: > Народ накидайте ссылок на алгоритмы спеллчекинга (или коррекции типа гугловского "вы имели в виду..."). > Коротко задача. Есть слово оно содержит ошибки, пропуски букв или лишние буквы вплоть до того, что 50% этого слова может быть мусором. Есть словарь. Необходимо по зашумленному слову восстановить эталон (или несколько наиболее похожих на зашумленное слово эталонов). Помехоустойчивые коды использовать нельзя по условию. Куда копать? И где лопата?
Здравствуйте, vadimcher, Вы писали:
A>>Кстати, очень забавно выглядят требования к программе, обусловленные тогдашним железом: A>>1) объём программы в рабочей памяти — не более 64 кБ A>>2) все необходимые для работы файлы (программа + данные) должны размещаться на одном A>>гибком диске, т.е. их суммарный объём не должен превышать 360 кБ A>>Вот ведь были времена! A>>
V>А откуда первое требование? Вроде как оно только для .com файлов было?
Там логика примерно такая расписана: всего в системе 640 кБ (ох уж эта магическая цифра!),
из них мы, по скромности, имеем право занять порядка 10%
V>да и второе -- могу соврать, но как я помню, были дискеты на 720 (двойной плотности?)...
Да, всё правильно — одинарная плотность 360 кБ, двойная 720
Сейчас на такую дискету не войдёт даже одна фотка с цифрового фотика
Здравствуйте, denisko, Вы писали:
D>Народ накидайте ссылок на алгоритмы спеллчекинга (или коррекции типа гугловского "вы имели в виду..."). D>Коротко задача. Есть слово оно содержит ошибки, пропуски букв или лишние буквы вплоть до того, что 50% этого слова может быть мусором. Есть словарь. Необходимо по зашумленному слову восстановить эталон (или несколько наиболее похожих на зашумленное слово эталонов). Помехоустойчивые коды использовать нельзя по условию. Куда копать? И где лопата?
06.07.2010 23:41, denisko пишет: > Народ накидайте ссылок на алгоритмы спеллчекинга (или коррекции типа гугловского "вы имели в виду..."). > Коротко задача. Есть слово оно содержит ошибки, пропуски букв или лишние буквы вплоть до того, что 50% этого слова может быть мусором. Есть словарь. Необходимо по зашумленному слову восстановить эталон (или несколько наиболее похожих на зашумленное слово эталонов). Помехоустойчивые коды использовать нельзя по условию. Куда копать? И где лопата?
Теоретический базис тут уже подвели, попробую и я вставить свои пять копеек.
1. Готовые решения, например hunspell.sf.net. Если не заюзать, то хотя бы идеи утащить
2. Задачу можно формализовать примерно так — есть словарь, если слово, для которого надо найти N ближайших из словаря, либо ближайшие из словаря в какой-то окрестности (например все слова из словаря, для которых расстояние меньше 5).
При этом встает интересный вопрос — что такое расстояние между двумя словами. Расстояние определяет модель ошибок. Тут уже упоминали расстояние Левенштейна. Но просто редакторское расстояние достаточно грубо, можно использовать более точные модели ошибок. Например:
а) фонетическая. Считаем что ошибится в близких по произношению слогах проще. То есть у нас при расчете расстояния Левенштейна цена замены 'а'-'о' меньше чем 'а' — 'б'. Тут же можно учитывать близкие по написанию буквы и всякие безударные.
б) клавиатурная модель — считаем что ошибиться при наборе слова в буквах, расположенных близко на клавиатуре проще, чем расположенных далеко. Тут же можно учесть удвоение или наоборот пропуск двойных букв.
То есть при расчете редакторского расстояния цена замены 'д'-'ж' меньше чем 'д'-'т', цена вставки 'л' меньше чем например 'в' (потому что вероятность двойных 'л' больше).
в) транслит — считаем что слова 'privet' и 'привет' близки. Сходу не скажу, можно ли эту модель выразить в терминах расстояния Левенштейна (потому что в транслите могут быть замены одной буквы на несколько 'я'<->'ya', 'ч'<->'tsch' и т.д.)
Теперь насчет алгоритма, как имея словарь быстро найти все слова из словаря в какой-то окрестности. Я попробую описать алгоритм, основанный на модели ошибок, которая выражается в терминах расстояния Левенштейна (то есть у нас есть веса вставок-удалений для каждого символа, и цены замен символ-символ).
Давайте уложим все слова из словаря в trie.
mama
papa
В каждый момент времени состояние S описывается множеством состояний нашего trie с весом (оценка ошибки между словом из trie и данного слова). Фактически, мы эмулируем НКА, который является произведением нашего trie и модели ошибок (ну или что-то типа .
S_0 = {(0, 0)} -- первоначальное состояние
for c <- word: -- перебираем все буквы данного "зашумленного" слова
for (s, w) <- deletionEnclose(S_i): -- перебираем все пары текущего состояния S_i и также все достижимые состояния, в которые можно добраться путем удаления символов
for (c_1, s_1) <- links(s): -- перебираем все переходы из состояния s в s_1 по символу c_1
-- если есть переход trie(s, c) - то добавляем (s_1, w) в следующее состояние:
S_{i+1} += (s_1, w)
-- вставка символа
S_{i+1} += (s, w+insertion(c))
-- замена символа
S_{i+1} += (s_1, w+change(c_1, c))
deletionEnclose(S):
повторяем S = deletionEnclose'(S) до тех пор, пока добавляются новые состояния в S
deletionEnclose'(S):
for (s, w) <- S:
for (c_1, s_1) <- links(s): -- перебираем все переходы из s
-- удаление символа
S' += (s_1, w+deletion(с_1))
return S'
Здесь trie(s, c) — это функция перехода для нашего trie, insertion(c), deletion(c) — это стоимость замены/удаления символа c, change(с_1, c_2) — это стоимость замены c_1 на с_2 и links(s) — это все переходы из состояния s.
При этом операция S += (s, w) на самом деле либо добавляет пару (s, w) во множество S, если в S содержится пары (s, _), а если уже есть пара (s, w1) то она замещается (s, min(w, w1)).
После выполнения цикла нужно выкинуть из S_n все пары (s, _) с не финальными s, и отфильтровать по предельно-допустимому весу. И получим все слова из словаря, которые могут получиться из данного путем замен, добавлений и удалений символов.
Конечно, в таком варианте количество состояний в S будет резко возрастать, но так как нужны не все опечатки, а только те, что в некой окрестности, то можно в операции S += (s, w) проверять что w < threshold и добавлять такие пары. Это не даст разрастаться множеству S.
В общем примерно такая вот идея.
3. Можно пойти по другому пути (как у Норвига в статье) — по имеющемуся словарю сразу сгенерить все возможные опечатки в нужных окрестностях, и запихать их в тот же словатрь, но с весами. Тут можно использовать любую модель ошибок, и даже несколько моделей одновременно (в том числе и транслитную).
4. Хорошие модули исправления опечаток могут учитывать контекст, тогда точность подсказок поднимется. Можно построить {2,3}gram language model и при расчете веса ошибки учитывать и вес получающихся словосочетаний.
Здравствуйте, andy1618, Вы писали:
A>Там логика примерно такая расписана: всего в системе 640 кБ (ох уж эта магическая цифра!), A>из них мы, по скромности, имеем право занять порядка 10%
требования в 64k возникли потому что спелчекеры делали
1) для электронных пишущих машинок на которых стояли 8080/z80 и максимум 64k
2) для 8 битных ПК на которых стояло 64/128k
у меня был знакомый который писла для них, использовали n-граммы
A>Да, всё правильно — одинарная плотность 360 кБ, двойная 720 A>Сейчас на такую дискету не войдёт даже одна фотка с цифрового фотика
на XT фолповоды были на 360k на 286 и страше 720/1.2m
