список замен

← →
kiberg (2008-04-02 13:22) [0]

Нужно сделать список замен для неправильного слова (очепятки):

Возможные очепятки:
1) поставлена лишняя буква
2) пропущена буква
3) поставлена неверная буква
4) две соседние буквы поменялись местами

Я создаю список возможных исправлений, а потом проверяю их в словаре. Найденные считаю верными.

У меня проблема в скорости работы алгоритма.
Если проверять один уровень вложенности ошибок, то впринципе все нормально 66n+31 варианта замен. Но если нужно проверить два уровня вложенности ошибок и слово длинное, то начинаются тормоза.

Как можно оптимизировать алгоритм?

← →
Johnmen © (2008-04-02 13:23) [1]

> Как можно оптимизировать алгоритм?

Какой алгоритм?

← →
Reindeer Moss Eater © (2008-04-02 13:24) [2]

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

← →
Дмитрий С (2008-04-02 13:26) [3]

А не проще словарь перебирать?

← →
Reindeer Moss Eater © (2008-04-02 13:27) [4]

словарь перебрать проще. только что это даст?

← →
Дмитрий С (2008-04-02 13:42) [5]

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

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

я напишу функцию, которая из "мама" сделает "папа"

← →
Дмитрий С (2008-04-02 13:46) [7]

> я напишу функцию, которая из "мама" сделает "папа"
>

А кто виноват, что ты не ту функцию напишешь =)))

← →
Reindeer Moss Eater © (2008-04-02 13:46) [8]

два раза пункт 3 - и вот мама стала папой.
будем менять?

← →
Дмитрий С (2008-04-02 13:48) [9]

слово МАМА и так в словаре должно быть, зачем чтото с ним делать?

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

Хорошо.
Сканируем словарь пр алфавиту и доходим в нем до "мама"
В тексте встречаем слово "папа" (до него в словаре еще не дошли)
и "папа" этой функцией превращается в "мама"

← →
Игорь Шевченко © (2008-04-02 14:08) [11]

Если в слове ХЛЕБ сделать четыре ошибки, получится ПИВО.

По сабжу - была нужда сравнивать русские фамилии, написанные латиницей.
Фамилия из словаря и фамилия исходная приводились к единому виду (удалялась часть букв, часть сочетаний букв преобразовывалась, и т.д.)
пребразованные сравнивались.
Для моих нужд хватало.

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

> Johnmen © (02.04.08 13:23) [1]
>
> > Как можно оптимизировать алгоритм?
>
> Какой алгоритм?

1) Беру неизвестное слов
2) Из него создаю возможный список исправелний, т.е. перебираю все варианты ошибок.
3) Проверяю есть ли в этом списке известные слова. Если да, то возвращаю эти слова и выхожу из алгоритма. Если нет, то для каждого слова из этого списка опять создаю новый список возможных исправлений
4) Проверяю есть ли в новом списке известные слова, если ни одного нет, то выход, если есть вывожу их.

← →
Kolan © (2008-04-02 14:21) [13]

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

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

1) Беру неизвестное слов
"рара" например

2) Из него создаю возможный список исправелний, т.е. перебираю все варианты ошибок.
мама, папа, пиво, ....

3) Проверяю есть ли в этом списке известные слова. Если да, то возвращаю эти слова и выхожу из алгоритма. Если нет, то для каждого слова из этого списка опять создаю новый список возможных исправлений4)
есть есть. причем до фига есть.

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

Есть, и не одно.

что дальше?

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

> kiberg (02.04.08 14:15) [12]

1.ХЛЕБ
|
2. ПЛЕБ, ХИЕБ, ХЛВБ, ХЛЕО, ПИВО
|
3. известное слово есть, это ПИВО. Выводим ПИВО, выходим.

Я правильно понял?

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

Неправильно. Пляшем от неузнанного слова.

← →
Johnmen © (2008-04-02 14:25) [17]

Неузнанное слово - ХЛЕБ.
Кстати, что значит "неузнанное"?

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

"хлеб" есть в словаре. оно "узнанное"

← →
Johnmen © (2008-04-02 14:27) [19]

Хорошо.
Пусть неузнанное слово - ХЛЁБ.

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

Тогда [14]

← →
kiberg (2008-04-02 14:29) [21]

> Kolan © (02.04.08 14:21) [13]
> Лучьше используй какой-нибудь алгоритм нечеткого сравнения
> строк.

> Reindeer Moss Eater © (02.04.08 14:22) [14]
> Есть, и не одно.
>
> что дальше?

Все, результат получен, вывожу на экран

> Johnmen © (02.04.08 14:22) [15]
>
> > kiberg (02.04.08 14:15) [12]
>
> 1.ХЛЕБ
> |
> 2. ПЛЕБ, ХИЕБ, ХЛВБ, ХЛЕО, ПИВО
> |
> 3. известное слово есть, это ПИВО. Выводим ПИВО, выходим.
>
>
> Я правильно понял?

Правильно так

1.ХЛИБ
|
2. ПЛИБ, ХИИБ, ХЛВБ, ХЛЕБ B т.д
|
3. известное слово есть, это ХЛЕБ. Выводим ХЛЕБ, выходим.

← →
Johnmen © (2008-04-02 14:29) [22]

[14] похоже на [15]

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

Все, результат получен, вывожу на экран

всех экранов федерации не хватит на такой результат

← →
Johnmen © (2008-04-02 14:31) [24]

> kiberg (02.04.08 14:29) [21]

По какому алшоритму сформировался волшебный список 2. ПЛИБ, ХИИБ, ХЛВБ, ХЛЕБ?
И что, если в этом списке будет ХЛЕВ?

← →
kiberg (2008-04-02 14:31) [25]

> Reindeer Moss Eater © (02.04.08 14:30) [23]
> Все, результат получен, вывожу на экран
>
> всех экранов федерации не хватит на такой результат

Да ладно!

У меня максимум получается штук десять.

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

И что, если в этом списке будет ХЛЕВ?

Там будут вообще все слова из словаря из четырех букв и даже наверное не только из четырех.

← →
Рамиль © (2008-04-02 14:35) [27]

> Пусть неузнанное слово - ХЛЁБ.

Получаем ХЛЕБ, есть в словаре, выходим.

← →
Mystic © (2008-04-02 14:35) [28]

> Проверяю есть ли в этом списке известные слова.

Вот тут подробнее. Список отсортирован? Поиск бинарный?

← →
Рамиль © (2008-04-02 14:35) [29]

> Рамиль © (02.04.08 14:35) [27]

Сорри, страницу не посмотрел.

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

У меня максимум получается штук десять.

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

← →
kiberg (2008-04-02 14:36) [31]

> Johnmen © (02.04.08 14:31) [24]
>
> > kiberg (02.04.08 14:29) [21]
>
> По какому алшоритму сформировался волшебный список 2. ПЛИБ,
> ХИИБ, ХЛВБ, ХЛЕБ?
> И что, если в этом списке будет ХЛЕВ?

1) удаляю одну букву из слова = n вариантов
2) добавляю одну букву алфавита в какое нибудь место слова = 32(n+1) варианта
3) меняю соседние буквы = n-1 вариант
4) заменяю какую-нибудь букву в слова на другую 32n варианта

если будет два или больше подходящих слова, то вывожу на экран

← →
Johnmen © (2008-04-02 14:36) [32]

> Рамиль © (02.04.08 14:35) [27]

Пора прочитать и осознать [14], [15] и [24].

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

1) удаляю одну букву из слова = n вариантов
2) добавляю одну букву алфавита в какое нибудь место слова = 32(n+1) варианта
3) меняю соседние буквы = n-1 вариант
4) заменяю какую-нибудь букву в слова на другую 32n варианта

если будет два или больше подходящих слова, то вывожу на экран

У тебя там будет не два и более слова, а весь словарь.

← →
kiberg (2008-04-02 14:38) [34]

> > Проверяю есть ли в этом списке известные слова.
>
> Вот тут подробнее. Список отсортирован? Поиск бинарный?

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

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

или почти весь. все зависит от лимита ошибок на слово.

← →
Johnmen © (2008-04-02 14:40) [36]

> kiberg (02.04.08 14:36) [31]

+
Как можно оптимизировать алгоритм?

Этот алгоритм надо выкинуть.

← →
kiberg (2008-04-02 14:41) [37]

> Reindeer Moss Eater © (02.04.08 14:38) [33]
> У тебя там будет не два и более слова, а весь словарь.

Как там может быть весь словарь. Возьмем, например, слово ХЛИБ. Сколько ты можешь сходу придумать правильных вариантов кроме как ХЛЕБ?

← →
kiberg (2008-04-02 14:42) [38]

> Reindeer Moss Eater © (02.04.08 14:39) [35]
> или почти весь. все зависит от лимита ошибок на слово.

Максимум две ошибки на слово, и то с ограничениями.

> Johnmen © (02.04.08 14:40) [36]
>
> > kiberg (02.04.08 14:36) [31]
>
> +
> Как можно оптимизировать алгоритм?
>
> Этот алгоритм надо выкинуть.

Предложи другой

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

все слова из словаря из четырех букв - раз
все слова на три буквы - ошибка с пропущеной буквой
все слова на пять букв - ошибка с лишней буквой.

а если учесть, что пропасть может не одна и лишних может быть не одна, то считай сам.

← →
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]
> а "прожевал" заменишь на "проживал" ?
>
> или нет?

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

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

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

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

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

← →
Johnmen © (2008-04-02 16:08) [70]

> 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]
>
> Я не про регистр.
> Я про слово ХЛЕВ, хотя д.б. ХЛЕБ, и про ПРОЖЕВАЛ, хотя д.
> б. ПОЖЕВАЛ.
> Так как здесь будет?

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

← →
Johnmen © (2008-04-02 16:28) [72]

> 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;

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

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

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

> пвио, пв (?)

"мой папа служит в ПВО: и морда - во, и жопа - во"

"а потому, что пьёт он ПИВО"

> [81] clickmaker © (02.04.08 17:21)
>
> > пвио, пв (?)
>
> "мой папа служит в ПВО: и морда - во, и жопа - во"

ЭТО НИРАЗУ НЕ СЛОВО РУССКОГО ИЗЫКА, ПОЭТОМУ ДАЖЕ ВОРД ИГНОРИРУЕТ

> [82] Johnmen © (02.04.08 17:28)
> "а потому, что пьёт он ПИВО"

вот поэтому и было предложено

> [80] VirEx © (02.04.08 17:09)

> ЭТО НИРАЗУ НЕ СЛОВО РУССКОГО ИЗЫКА, ПОЭТОМУ ДАЖЕ ВОРД ИГНОРИРУЕТ

А какого языка это слово? Сам я даже боюсь предположить...
И чт о за слово "ВОРД"? Игнорируем...

> Дмитрий С (02.04.2008 13:42:05) [5]

Из слова хлеб элементарно получается пиво, путем всего лишь четырех замен.

> Игорь Шевченко (02.04.2008 14:08:11) [11]

О и ты туда же.
Вообще то парень на ноблевку тянет, а получит шнобелевку..

> [87] Johnmen © (02.04.08 18:00)
>
> > VirEx © (02.04.08 17:51) [86]
> > это аббревиатура
>
> А аббревиатура - это трансглюкавые мымрики?

Да, потомучто ОБХСС, КГБ, ГИБДД и тому подобные мымрики могут нарушать абсолютно любые правила русского словообразования, потому как это не слова (еще раз повторяюсь)

> kiberg (02.04.2008 14:15:12) [12]

Тебе пример с хлебом привели, не понятно?

> kiberg (02.04.2008 14:49:40) [40]

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

> Johnmen (02.04.2008 15:00:46) [46]

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

> VirEx © (02.04.08 18:13) [90]
> Да, потомучто ОБХСС, КГБ, ГИБДД
> и тому подобные мымрики могут нарушать абсолютно любые правила
> русского словообразования, потому как это не слова (еще
> раз повторяюсь)

Это чё за логика такая интересная - "это не слова, потому что могут нарушать абсолютно любые правила русского словообразования"?
Правила спряжения не нарушают, к примеру.
Так что же это? Если не слова и не мымрики?

> [94] Johnmen © (02.04.08 22:59)
> Так что же это? Если не слова и не мымрики?

Это и есть мымрики. Если я увижу в словаре ГОУ ДОСН СДЮШОР, тогда это будет словами, а сокращение это и есть сокращение, аббревиатура - ничем кроме аббревиатуры не является.

Пиво - это понятие, которым именуется некий напиток неприятного мочевого цвета.
ПВЗ (ПиВоваренный Завод) - это сокращение, притом такое сокращение, в котором только одна из букв характеризует общее значение аббревиатуры - "Завод".

заглянем в вики:
Слово — центральная единица языка. Это основная номинативная и когнитивная единица языка, служащая для именования и сообщения о предметах, признаках, процессах и отношениях.

Пиво - единица языка, потомучто в русском языке оно означает предмет (жидкий мутный противный напиток).
ПВЗ - это солянка из единиц языка, в русском языке такого нет. Смысл этой аббревиатуры характеризует одно из слов в его "составе". Притом ПВЗ можно расшифровать как угодно, хоть ПеньковоВаленковый Завод.

> Правила спряжения не нарушают, к примеру.
Так ведь перед тем как утвердить аббревиатуру, немного мозгами шевелят, чтобы благозвучней было.
Что-то такой аббревиатуры я не видел: ЪХЙЬ

> Пиво - единица языка, потомучто в русском языке оно означает
> предмет (жидкий мутный противный напиток).

Сам ты противный

> VirEx © (03.04.08 17:30) [95]

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

ЗЫ
Википедию читаешь - это хорошо. Посмотри на досуге определение аббревиатуры.

> [97] Johnmen © (03.04.08 17:50)
>
> > VirEx © (03.04.08 17:30) [95]
>
> Ну с логикой ты не очень дружишь. Русский язык не очень
> знаешь. Пиво не любишь. Это мы увидели, спасибо.
> Но зачем постить здесь продукты жизнедеятельности личных
> мозговых извилин?
>
> ЗЫ
> Википедию читаешь - это хорошо. Посмотри на досуге определение
> аббревиатуры.

Логика:
Слово это слово, т.е. единица языка, значение название или определение чего-либо.
Набор букв из слов - это набор букв из слов. Не более. Как бы аббревиатура не "уважала" правила словообразования, она не станет словом, пока не войдет в язык в виде одного понятия, после чего начнет считаться словом.
Пример: эсэсовец - это слово, т.к. означает человека имеющего принадлежность к вооруженному формированию СС. А "СС" это аббревиатура, и означать она может что угодно:
СС (нем. Schutzstaffel, охранные отряды) — вооружённые формирования нацистов в 1923—1945 годах.
СС — система счисления
СС — название электровоза (Сурамский Советский)
СС - Советский Союз в сокращении КПСС
CC — сокращённое название организации и лицензий Creative Commons

Про вики:
Википедия и является "свободно редактируемым" сервисом, потомучто ошибкам предрасположен любой вбивающий туда текст.

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

> Как можно оптимизировать алгоритм?

Алгоритм не описан.
Я несколько раз делал нечто подобное через массив байт. обращаемся к строкам(исходной и из словаря) как массивам байт, при проверке вычитаем соответствующие элементы мыссивов. Результат проверяем через некоторые заданные условия(битовые маски?), нпример более 2 байт-разлиий или ограничить не верность первого символа (можно сильно ускорить индексацией словаря).

> [96] Игорь Шевченко © (03.04.08 17:43)
>
> > Пиво - единица языка, потомучто в русском языке оно означает
>
> > предмет (жидкий мутный противный напиток).
>
>
> Сам ты противный

Пиво вобще немецкое изобретение (я так думаю).
Наш выбор: квас и медовуха.

> Пиво вобще немецкое изобретение (я так думаю).

http://ru.wikipedia.org/wiki/%D0%9F%D0%B8%D0%B2%D0%BE
исторически немцы к происхождению пива не имеют отношения

> Пиво вобще немецкое изобретение (я так думаю).
> Наш выбор: квас и медовуха.

И шовинист к тому же

> [101] uniken1 © (03.04.08 19:31)
>
> > Пиво вобще немецкое изобретение (я так думаю).
>
> http://ru.wikipedia.org/wiki/%D0%9F%D0%B8%D0%B2%D0%BE
> исторически немцы к происхождению пива не имеют отношения

Там же:
Однако некоторые римские историки в начале нашей эры упоминали, что кельтские, германские и другие племена пили пиво.

Исходное

> Пиво вобще немецкое изобретение

> Однако некоторые римские историки в начале нашей эры упоминали,
> что кельтские, германские и другие племена пили пиво.

Теперь еще раз пречитай и сравни время германия 2-7 в.н.э и Египет 5-4 в. ДО.Н.Э.
С таким подходом, я только что изобрел Электиричество, я настолько суров...

> [104] uniken1 © (03.04.08 21:47)
> Исходное
>
> > Пиво вобще немецкое изобретение
>
>
>
> > Однако некоторые римские историки в начале нашей эры упоминали,
> > что кельтские, германские и другие племена пили пиво.
>
> Теперь еще раз пречитай и сравни время германия 2-7 в.н.э
> и Египет 5-4 в. ДО.Н.Э.
> С таким подходом, я только что изобрел Электиричество, я
> настолько суров...

"И вновь лампочка Ильича осветила его мрачную хижину".
Будь по твоему. Ты мое мнение изменил.

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