список замен

← →
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]

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

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

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

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

← →
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 варианта

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

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

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

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

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

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

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

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

> 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]
>
> +
> Как можно оптимизировать алгоритм?
>
> Этот алгоритм надо выкинуть.

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

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

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

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

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

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

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