список замен

← →
kiberg (2008-04-02 14:49) [40]

> Reindeer Moss Eater © (02.04.08 14:43) [39]
> все слова из словаря из четырех букв - раз
> все слова на три буквы - ошибка с пропущеной буквой
> все слова на пять букв - ошибка с лишней буквой.
>
> а если учесть, что пропасть может не одна и лишних может
> быть не одна, то считай сам.

Как можно сделав всего две ошибки в слове получить все слова из 3, 4 и 5 букв? При том, что проверив только на возможность одной ошибки получаем правильный вариант, т.е. две ошибки сразу же не рассматриваются.

← →
Reindeer Moss Eater © (2008-04-02 14:51) [41]

а ты заранее заложился на то, что может быть допущена только определенная комбинация двух ошибок?

← →
Johnmen © (2008-04-02 14:52) [42]

> kiberg (02.04.08 14:42) [38]
> Предложи другой

Это надо думать. А мне лень :))

← →
kiberg (2008-04-02 14:56) [43]

> Reindeer Moss Eater © (02.04.08 14:51) [41]
> а ты заранее заложился на то, что может быть допущена только
> определенная комбинация двух ошибок?

Любая комбинация двух ошибок.

← →
Johnmen © (2008-04-02 14:57) [44]

Кстати, а такие случаи - УГРОЗА/УГРО ЗА/У,ГРОЗА - как?
Являются ли пробел и запятая "буквами"?

← →
Reindeer Moss Eater © (2008-04-02 14:58) [45]

ну ок.
как ты будешь проверять такую комбинацию:
- любые две буквы возможно переставлены местами
- возможно пропущена одна буква.

← →
Johnmen © (2008-04-02 15:00) [46]

> kiberg (02.04.08 14:56) [43]
> Любая комбинация двух ошибок.

Слово ХОРОМ. Это что? ХРОМ или ХОРОМЫ? Или оставим его в покое, ибо правильное?

← →
Mystic © (2008-04-02 15:02) [47]

> Список замен не отсортирован, я его перебираю весь. Словарь
> хеширован.

Интуитивно кажется, что это не самое лучшее решение. Во-первых, когда ты сгенерируешь все возможные "ошибки", то в этом списке будет очень много слов, которые будут начинаться так же, как и исходное слово. Так что возможно более быстрым будет такой вариант:

(1) Отсортировать замены
(2) Разбить список замен на два. В первый список должны войти слова, у которых первые три буквы совпадают с тем, что встречается в слове. Во второй список все остальные слова
(3) Потом пройтись по всем словам, что начинаются с первых трех букв. И искать эти слова в списках замены
(4) А по остальным словам просто искать по словарю.

← →
kiberg (2008-04-02 15:02) [48]

> Johnmen © (02.04.08 14:57) [44]
> Кстати, а такие случаи - УГРОЗА/УГРО ЗА/У,ГРОЗА - как?
> Являются ли пробел и запятая "буквами"?

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

← →
MBo © (2008-04-02 15:04) [49]

1. Почитать о дистанции редактирования (edit distance) - ДП-алгоритм
2. Найти в инете описание алгоритма, используемого в Google ("возможно, вы имели в виду ...")

← →
Reindeer Moss Eater © (2008-04-02 15:05) [50]

длинное слово (скажем букв 12) с уже упомянутой комбинацией
сколько будет вариантов интерпретации?

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

сколько вариантов?

← →
Mystic © (2008-04-02 15:07) [51]

Или даже лучше будет для пункта (3) устроить что-то вроде сортировки слиянием: идти по обеим отсортированным спискам. Переходить на следующее слово в том списке, которое меньше. Итого получаем линейный проход по всем словам

← →
kiberg (2008-04-02 15:08) [52]

> Reindeer Moss Eater © (02.04.08 14:58) [45]
> ну ок.
> как ты будешь проверять такую комбинацию:
> - любые две буквы возможно переставлены местами
> - возможно пропущена одна буква.

Могут поменяться только две соседние буквы. Этот вариант все равно проверится правильно.

> Johnmen © (02.04.08 15:00) [46]
> Слово ХОРОМ. Это что? ХРОМ или ХОРОМЫ? Или оставим его в
> покое, ибо правильное?

Такое слово оставим в покое - оно есть в словаре.

← →
Reindeer Moss Eater © (2008-04-02 15:10) [53]

Могут поменяться только две соседние буквы. Этот вариант все равно проверится правильно.

У нас по твоим же условиям могут быть две любые ошибки.

Я сначала теряю букву, потом меняю местами в том же месте две буквы.

← →
Reindeer Moss Eater © (2008-04-02 15:12) [54]

Или наоборот. Меняю местами, потом теряю одну поменявшую свое место.

← →
Eraser © (2008-04-02 15:12) [55]

> Kolan © (02.04.08 14:21) [13]

+1

вот простейший пример http://www.delphikingdom.com/asp/viewitem.asp?catalogid=722
для простых задач вполне достаточно.

← →
kiberg (2008-04-02 15:13) [56]

> Mystic © (02.04.08 15:02) [47]

Надо попробовать. Какие еще есть идеи?

> MBo © (02.04.08 15:04) [49]
> 1. Почитать о дистанции редактирования (edit distance) -
> ДП-алгоритм
> 2. Найти в инете описание алгоритма, используемого в Google
> ("возможно, вы имели в виду ...")

Про алгоритм Google читал, я так понял у них то же самое что и у меня, только они еще учитывают частоту встречаемости слов.

> Reindeer Moss Eater © (02.04.08 15:05) [50]
> длинное слово (скажем букв 12) с уже упомянутой комбинацией
> сколько будет вариантов интерпретации?
>
> любые две соседние могут быть переставлены.
> после чего одна из переставленных опущена.
> или наоборот.
> опущена, а потом переставлены не соседние в исходном слове.
>
>
> сколько вариантов?

677329

← →
Johnmen © (2008-04-02 15:15) [57]

> kiberg (02.04.08 15:08) [52]
> Такое слово оставим в покое - оно есть в словаре.

Т.е. в словаре будут все склонения/спряжения/... - все известные словоформы???

ЗЫ
Скажи, это задача учебная или рабочая?

← →
Reindeer Moss Eater © (2008-04-02 15:16) [58]

677329

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

← →
kiberg (2008-04-02 15:25) [59]

> Eraser © (02.04.08 15:12) [55]
>
> > Kolan © (02.04.08 14:21) [13]
>
> +1
>
> вот простейший пример http://www.delphikingdom.com/asp/viewitem.
> asp?catalogid=722
> для простых задач вполне достаточно.

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

> Johnmen © (02.04.08 15:15) [57]
>
> > kiberg (02.04.08 15:08) [52]
> > Такое слово оставим в покое - оно есть в словаре.
>
> Т.е. в словаре будут все склонения/спряжения/... - все известные
> словоформы???
>
> ЗЫ
> Скажи, это задача учебная или рабочая?

Это рабочая задача. Для одной возможно ошибки она успешно решена. Даже когда учитывается две ошибки и слово не очень длинное до 5 символов, то тормозов не заметно, но для слова из 20 символов задержка 6 сек.

← →
Mystic © (2008-04-02 15:27) [60]

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

← →
Reindeer Moss Eater © (2008-04-02 15:34) [61]

Если задача рабочая, то значит есть характерные опечатки. Точнее слова - кандидаты на то, что в них вероятно будут опечатки. Я бы просто завел пополняемый словарь таких слов с регулярками для их узнавания. Это было бы намного эффективнее бесполезного перебора всех возможных вариантов совершения опечаток в неузнанных словах.

← →
kiberg (2008-04-02 15:37) [62]

> Mystic © (02.04.08 15:27) [60]
> Еще идея схожая с [47], только индексировать не только начало
> слова, но и конец. Правда в русском языке слова часто оканчиваются
> одинаково, так что толку с этого индекса будет немного.
> Но можно попытаться прикрутить индексы по словам, начинающихся
> со второй букве, с третьей и т. п. Потом по этим индексам
> брать списки со словаря и вычислять количество несоответствий.
>

Спасибо, попробую.

> Reindeer Moss Eater © (02.04.08 15:34) [61]
> Если задача рабочая, то значит есть характерные опечатки.
> Точнее слова - кандидаты на то, что в них вероятно будут
> опечатки. Я бы просто завел пополняемый словарь таких слов
> с регулярками для их узнавания. Это было бы намного эффективнее
> бесполезного перебора всех возможных вариантов совершения
> опечаток в неузнанных словах.

Такой механизм уже есть. Пользователи хотят исправления любых случайных ошибок :(

← →
Reindeer Moss Eater © (2008-04-02 15:38) [63]

любых? или любых двух? :)

← →
kiberg (2008-04-02 15:41) [64]

> Reindeer Moss Eater © (02.04.08 15:38) [63]
> любых? или любых двух? :)

Я думаю, если у меня не получится для двух сделать, то они согласятся и на одну :)

← →
Johnmen © (2008-04-02 15:46) [65]

> kiberg

Такая фраза
"Откусив хлеВа краюху, он пРожевал её немного, подумал, и пошёл повесился"
Здесь есть ошибки?

← →
kiberg (2008-04-02 15:52) [66]

> Johnmen © (02.04.08 15:46) [65]
>
> > kiberg
>
> Такая фраза
> "Откусив хлеВа краюху, он пРожевал её немного, подумал,
> и пошёл повесился"
> Здесь есть ошибки?

Регистр я учитываю, и замены для таких ошибок уже реализованы.

← →
Reindeer Moss Eater © (2008-04-02 15:54) [67]

а "прожевал" заменишь на "проживал" ?

или нет?

← →
kiberg (2008-04-02 16:00) [68]

> Reindeer Moss Eater © (02.04.08 15:54) [67]
> а "прожевал" заменишь на "проживал" ?
>
> или нет?

Нет, заменю на "прожевал".

значит и ошибочное "проживал" на "прожевал" тоже не заменишь.
хотя всего одна элементарная ошибка.

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

к тому же нет никакого ограничения на количество опечаток.

> kiberg (02.04.08 15:52) [66]

Я не про регистр.
Я про слово ХЛЕВ, хотя д.б. ХЛЕБ, и про ПРОЖЕВАЛ, хотя д.б. ПОЖЕВАЛ.
Так как здесь будет?

← →
kiberg (2008-04-02 16:15) [71]

> Johnmen © (02.04.08 16:08) [70]
>
> > kiberg (02.04.08 15:52) [66]
>
> Я не про регистр.
> Я про слово ХЛЕВ, хотя д.б. ХЛЕБ, и про ПРОЖЕВАЛ, хотя д.
> б. ПОЖЕВАЛ.
> Так как здесь будет?

Грамматические ошибки не проверяются, только орфографические.

> kiberg (02.04.08 16:15) [71]
> Грамматические ошибки не проверяются, только орфографические.

Т.е. если опечатка порождает легитимную словоформу, то ошибки нет, не смотря на то, что написана получается полная ерунда?

← →
kiberg (2008-04-02 16:30) [73]

> Johnmen © (02.04.08 16:28) [72]
> Т.е. если опечатка порождает легитимную словоформу, то ошибки
> нет, не смотря на то, что написана получается полная ерунда?

ага

ага

программирование ради программирования.

Словарь - это последнее дело.
Сравнивай возможность правильного/неправильного сочетания букв, как это делает пунтосвичер.
пиво, сочетания пи, ив и во
пвио, пв (?)

мсяо

← →
kiberg (2008-04-02 16:43) [77]

> Reindeer Moss Eater © (02.04.08 16:33) [74]
> ага
>
> программирование ради программирования.

Нет. Проверка грамматики там не очень нужна, и пользователи ее слава богу не требуют.

> VirEx © (02.04.08 16:38) [75]
> Словарь - это последнее дело.
> Сравнивай возможность правильного/неправильного сочетания
> букв, как это делает пунтосвичер.
> пиво, сочетания пи, ив и во
> пвио, пв (?)

О! А, об это по подробнее, пожалуйста.

> программирование ради программирования.

Ну почему? Решение, которое поймает 90% опечаток и то хлеб. А полностью задача неразрешима, даже человек не всегда догадается, где опечатка, а где нет. А телепатических аппаратов еще не изобрели.

отчасти потому, что решая задачу в конкртеной области решили написать "универсальный решатель задач"

> О! А, об это по подробнее, пожалуйста.

Лучше проверять такие сочетания в слогах, а то бывают такие словечки, что язык сломаешь.
Была здесь раньше такая тема:
Gydvin © (09.07.07 17:49)
Нигде случайно не попадался словарь переносов русского языка? В текстовом формате самое оно.
Очень нужно.

Предлагал такой код:
function WordToSlog(str:string;words_iskl:TStrings):string; function UpString(str:string):string; var i:integer; begin result:=str; for i:=1 to length(Result) do case Result[i] of "а".."я": Dec(Result[i], 32); end; end; //ищет в строке str с позиции index комбинацию из всех комбинаций согласной s и гласной g function slog(str:string; index:integer; s,g:array of string):boolean; //проверяет, гласная ли буква function IsGlasn(c:char;g:array of string):boolean; var i:integer; begin result:=false; for i:=low(g) to high(g) do if c=g[i] then begin result:=true; exit; end; end; var i,y:integer; s_,l_:string; begin result:=false; for i:=low(s) to high(s) do for y:=low(g) to high(g) do begin s_:=UpString((s[i]+g[y])); l_:=UpString(copy(str,index,2)); if s_=l_ then {если перед слогом стоит гласная, то} {if IsGlasn(str[index-1],g) then} begin result:=true; exit; end; end; end; //проверяет, по индексу в строке, стоит ли предлог, и передает через len его длину function IsPredlog(str:string; index:integer; p:array of string; var len:integer):boolean; var i:integer; begin result:=false; for i:=low(p) to high(p) do if copy(str,index,length(p[i]))=p[i] then begin len:=length(p[i]); result:=true; exit; end; end; //ищет корень, точно такой же поиск как поиск предлога function IsKoren(str:string; index:integer; c:array of string; var len:integer):boolean; begin result:=IsPredlog(str,index,c,len); end; //количество слогов function GetSlogCount(str:string; s,g:array of string):integer; var i:integer; begin result:=0; for i:=1 to length(str) do if slog(str,i,s,g) then inc(result); end; //вставляет стоку substr в искомую str в позицию index procedure InsStr(var str:string; substr:string; index:integer); begin if index=0 then exit; str:=copy(str,1,index)+substr+copy(str,index+length(substr),length(str)) end; const //а б в г д е ё ж з и к л м н о п р с т у ф х ц ч щ ь ъ э ю я s : array[1..19] of string =("б","в","г","д","ж","з","к","л","м","н","п","р","с","т","ф","х","ц","ч","щ"); //согласные g : array[1..10] of string =("а","е","ё","и","о","у","э","ю","я","ы");//гласные p : array[1..3] of string =("пре","пере","под"); //предлоги c : array[1..3] of string =("прав","нос","воскл");//корни var i,y,z:integer; begin result:=str; for i:=0 to words_iskl.Count-1 do if UpString(str)=UpString(words_iskl[i]) then exit; //если меньше одного слога то не переносится if GetSlogCount(str,s,g)<2 then exit; i:=1;y:=0; while i<length(str) do begin z:=0; if IsPredlog(str,i,p,z) then inc(i,z) else //предлоги не переносим if IsKoren(str,i,c,z) then inc(i,z) else //также как и корни if slog(str,i,s,g) then begin inc(y); if y>1 then //избавляемся от просто --> п-рос-то InsStr(str,"-",i-1); inc(i); end; inc(i); end; result:=str; end;

результат работы:
Москва Москва
Идиот Идиот
Лохотрон Лохотрон
Квазимодо Ква-зи-мо-до
Параллелепипед Па-рал-ле-ле-пи-пед
Изобретатель Изоб-ре-та-тель
слово сло-во
мангал ман-гал
трапеция тра-пе-ция
караганда ка-ра-ган-да
переносимый переноси-мый
эксгибиционист эксги-би-цио-нист
неправдоподобный неправдоподоб-ный
восклицание восклица-ние
абстракция абстрак-ция
странный стран-ный

икслючения:
Азия
узнаю
фойе
Москва
Лохотрон

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

список замен Найти похожие ветки