Помогите написать алгоритм перебора

← →
leonidus © (2007-03-25 21:27) [0]

Господа, вот такая проблема. Написал на нейронных сетях простую OCR, распознает неплохо английские буквы, но вот незадача, некоторые буквы она путает, особенно часто это происходит с парами e-o, c-e и i-l. В общем ничего странного тут нет, эти буквы очень похожи по написанию, поэтому для постобработки я использую словарь английских слов с которым сравниваю полученное слово и если это слово в словаре есть то считаю что оно распознано верно (конечно это не всегда так, но в первом приближении этого достаточно). Так вот проблема заключается в том, чтобы из полученного слова сформировать список слов для проверки, например: распознавали слово "publication", распозналось оно как "publlcatlon", т.е. программа перепутала i и l. По хорошуму мне бы нудно было получить список слов для сравнения по словарю в виде:
publlcatlon
pubilcatlon
pubiicatlon
pubiication
pubilcation
publication
pubiicatlon

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

← →
Andy BitOff © (2007-03-25 22:29) [1]

Ну, уж если ты написал "на нейронных сетях простую OCR, распознает неплохо английские буквы", то с такой задачей у тебя вообще проблем не должно быть ;)

← →
Kolan © (2007-03-25 22:33) [2]

Нечеткое сравнение нужно использовать&#133

← →
Alx2 © (2007-03-25 22:34) [3]

>leonidus © (25.03.07 21:27)

Расстояние Левенштейна (расстояние редактирования) поможет.
Тогда хранить достаточно только эталон.
Т.е. после распознавания слова ищем ближайший к нему эталон и если таковой имеется не очень далеко - подменям :)

← →
TUser © (2007-03-25 22:35) [4]

Посмотри алгоритм Shift-And. Для твоего случая его надо модифицировать - вместо совпало/не совпало писать число несовпадений.

← →
Riply © (2007-03-25 22:56) [5]

Просвятите.
Что означает "написал на нейронных сетях" ?

← →
VirEx © (2007-03-25 23:05) [6]

после ОЦР распознования необходимо корректировать результаты на правильные слоги.
но исходники я бы посмотрел)

← →
Loginov Dmitry © (2007-03-25 23:12) [7]

> Что означает "написал на нейронных сетях"

Язык программирования счас такой модный наверное появился.

← →
leonidus © (2007-03-25 23:15) [8]

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

← →
Riply © (2007-03-25 23:16) [9]

> [7] Loginov Dmitry © (25.03.07 23:12)
>Язык программирования счас такой модный наверное появился.
Спасибо.
P.S. Совсем отстала от моды :(

← →
Alx2 © (2007-03-25 23:24) [10]

>leonidus © (25.03.07 23:15)

Про подстановки:
пусть различных, но внешне похожих букв M штук
Пусть они стоят на местах i1, i2 ... iN
Тогда берем N-разрядное число, в M-ричной системе счисления. И пускаем перебор от 0 до M^N-1, каждый раз увеличивая это число на единицу. Тогда цифры этого числа дадут все искомые комбинации.

← →
leonidus © (2007-03-26 00:00) [11]

>Alx2 а можно привет кода? просто фраза "M-ричной системе счисления" меня как-то напугала :)

>leonidus © (26.03.07 00:00) [11]

Ну вот, страхов-то. :)

Пример.
В троичной системе счисления выписываем все числа из четырех цифр.

procedure TForm1.Button132215Click(Sender: TObject); type TNumber = array of integer; function NumberToStr(const Number: TNumber): string; // Только для вывода в Memo var k: Integer; begin Result := ""; for k := 0 to Length(Number) - 1 do Result := IntToStr(Number[k]) + Result; end; function Increment(var Number: TNumber; Base: Integer): boolean; // Здесь Number - что увеличиваем. // Base - основание системы счисления, в какой это делаем // Функция возвратит ложь, если число нельзя увеличивать (во всяком // случае, без расширения разрядности ) var k: Integer; carrier: boolean; // Флаг переноса, указывающий, что при // увеличении очередного разряда-цифры осталось что-то "в уме" begin Carrier := true; k := 0; while (k < Length(Number)) and (Carrier) do begin inc(Number[k]); // Увеличиваем цифру. Carrier := Number[k] = Base; // Если она достигла местной "десятки" if Carrier then Number[k] := 0; // То превращаем ее в 0 inc(k); end; Result := not Carrier; end; var Number: TNumber; begin SetLength(Number, 4); // "ноль" из четырех цифр. Его б на самом деле обнулить... repeat Memo1.Lines.Add(NumberToStr(Number)); // В мемо кидаем запись числа until not Increment(Number, 3); // Затем его увеличиваем на 1 в системе по основанию 3. // Выходим из цикла, если не получилось увеличить. end;

> Loginov Dmitry © (25.03.07 23:12) [7]
> > Что означает "написал на нейронных сетях"
> Язык программирования счас такой модный наверное появился.

Не язык, а компонент!

Фига себе. Я тоже хочу такой компонент. А там LVQ-сеть реализована?
Правда качал что-то подобное с BaseGroup, но там LVQ не нашел :(

Как-то я видел текст (в каком-то журнале), распознанный какой-то версией какого-то известного распознавателя, в коором как раз только что внедрили систему подобной вот "коррекции". Было сильно забавно, т.к. большинство слов он упорно перековеркал на ему известные...

> Расстояние Левенштейна не катит, там бывают слова очень отличные от оригинала по написанию а внешне похожие.

Пример можешь дать? Реально - тебе надо ввести штрафы за несовпадения букв, разные для разных пар. Для эль и один - маленький штравы, для р и н - большой и т.д.

Помогите написать алгоритм перебора Найти похожие ветки