VPF::Нечеткое сравнение строк - Форум программистов

vlsaf

Дата 7.3.2010, 20:05 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 423
Регистрация: 9.5.2007

Репутация: нет
Всего: 1

Всем привет.

Нужен алгоритм нечеткого сравнения строк.
Может кто знает, где взять?

Алгоритм должен выдать число, на сколько две строки отличаются друг от друга.
опечатк и очепятка - мало чем отличаются
опечатка и опеч-ка уже больше отличаются
и т.д.

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

world

Дата 7.3.2010, 21:12 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 133
Регистрация: 2.10.2009
Где: Харьков

Репутация: нет
Всего: 12

Всё зависит от того, насколько длинна строка.
К примеру можно использовать алгоритм шинглов
http://blog.arseo.ru/shingly/
можно также использовать метод суффиксных деревьев(алгоритм Укконена)
http://wapedia.mobi/ru/%D0%A1%D1%83%D1%84%...%B5%D0%B2%D0%BE

--------------------

Say what you mean, and mean what you say. Robert Wilson Cody

vlsaf

Дата 7.3.2010, 23:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 423
Регистрация: 9.5.2007

Репутация: нет
Всего: 1

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

Нарыл тут http://www.delphikingdom.com/asp/viewitem.asp?catalogid=722

перевел на c#

Код


        //------------------------------------------------------------------------------
        //MaxMatching - максимальная длина подстроки (достаточно 3-4)
        //strInputMatching - сравниваемая строка
        //strInputStandart - строка-образец

        // Сравнивание без учета регистра
        // if IndistinctMatching(4, "поисковая строка", "оригинальная строка  - эталон") > 40 then ...

        struct RetCount
        {
            public long lngSubRows;
            public long lngCountLike;
        }

        RetCount Matching(string strInputA, string strInputB, int lngLen)
        {
            RetCount TempRet;
            int PosStrA;
            int PosStrB;
            string strTempA;
            string strTempB;
            TempRet.lngCountLike = 0;
            TempRet.lngSubRows = 0;

            for (PosStrA = 0; PosStrA <= strInputA.Length - lngLen; PosStrA++)
            {
                strTempA = strInputA.Substring(PosStrA, lngLen);
                for (PosStrB = 0; PosStrB <= strInputB.Length - lngLen; PosStrB++)
                {
                    strTempB = strInputB.Substring(PosStrB, lngLen);
                    if ((string.Compare(strTempA, strTempB) == 0))
                    {
                        TempRet.lngCountLike = (TempRet.lngCountLike + 1);
                        break;
                    }
                }
                TempRet.lngSubRows = (TempRet.lngSubRows + 1);
            }
            return TempRet;
        }

        private float IndistinctMatching(int MaxMatching, string strInputMatching, string strInputStandart)
        {
            RetCount gret;
            RetCount tret;
            int lngCurLen; //текущая длина подстроки

            //если не передан какой-либо параметр, то выход
            if (MaxMatching == 0 || strInputMatching.Length == 0 || strInputStandart.Length == 0) return 0;

            gret.lngCountLike = 0;
            gret.lngSubRows = 0;

            // Цикл прохода по длине сравниваемой фразы
            for (lngCurLen = 1; lngCurLen <= MaxMatching; lngCurLen++)
            {
                //Сравниваем строку A со строкой B
                tret = Matching(strInputMatching, strInputStandart, lngCurLen);
                gret.lngCountLike = gret.lngCountLike + tret.lngCountLike;
                gret.lngSubRows = gret.lngSubRows + tret.lngSubRows;

                //Сравниваем строку B со строкой A
                tret = Matching(strInputStandart, strInputMatching, lngCurLen);
                gret.lngCountLike = gret.lngCountLike + tret.lngCountLike;
                gret.lngSubRows = gret.lngSubRows + tret.lngSubRows;
            }

            if (gret.lngSubRows == 0) return 0;

            return (float)(gret.lngCountLike * 100.0 / gret.lngSubRows);

        }

Берите люди, пользуйтесь!!!

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Общие вопросы по .NET и C# \| Следующая тема »