Печать страницы - [РЕШЕНО]Нечеткое сравнение строк

Название: [РЕШЕНО]Нечеткое сравнение строк
Отправлено: Vitto74 от Февраль 19, 2010, 22:51

Дорого времени суток. При создании электронного учебника встала потребность организовать поиск по глоссарию (только по заголовкам). Для этого я решил использовать алгоритм нечеткого сравнения строк, взятый отсюда http://www.delphikingdom.com/asp/viewitem.asp?catalogid=722
После перевода получилось следующее:

Код:

struct retCount{
    int lngSubRows;
    int lngCountLike;
};

retCount Matching(QString InputA,
                  QString InputB,
                  int lngLen)
{
    retCount TempRet;
    int PosStrB;
    int PosStrA;
    QString StrA;
    QString StrB;
    QString StrTempA;
    QString StrTempB;
    QString StrInputA = InputA.toLower();
    QString StrInputB = InputB.toLower();

    StrA = StrInputA;
    StrB = StrInputB;

    for ( PosStrA = 1; PosStrA <= (StrA.length() - lngLen + 1); ++PosStrA){
       StrTempA = StrA.mid(PosStrA, lngLen);
       PosStrB = 1;
       for (PosStrB = 1; PosStrB <= (StrB.length() - lngLen + 1); ++PosStrB){
          StrTempB = StrB.mid(PosStrB, lngLen);
          if (StrTempA == StrTempB){
             TempRet.lngCountLike++;
             break;
          }
       }
       TempRet.lngSubRows++;
    }
    return TempRet;
}

int IndistinctMatching(QString InputMatching,
                       QString InputStandart,
                       int MaxMatching = 4)
{
    QString strInputMatching = InputMatching.toLower();
    QString strInputStandart = InputStandart.toLower();
    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;
    }
    //избыточность сделал для удобства отладки
    float rez = ((float)gret.lngCountLike/(float)gret.lngSubRows);
    rez = rez*100;
    return (int)rez;
}

Но эта функция жутко глючит: на одинаковых параметрах несколько раз выдавала разные результаты. Более того функция должна выдавать процент совпадения, а она выдает числа не меньше 100, а иногда и несколько тысяч.
Вставив код во Lazarus получил более вменяемые. но тоже не верные результаты.
Жду предложений.
PS облазил гугл, но функцию на C++ не нашел.

Название: Re: Нечеткое сравнение строк
Отправлено: BlackTass от Февраль 19, 2010, 23:29

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

Название: Re: Нечеткое сравнение строк
Отправлено: Vitto74 от Февраль 20, 2010, 13:20

Причины глюков найдены! Два дня не мог понять причину глюков, а главное - почему на одних данных выдает разные результаты!
Я забыл инициализировать переменные - в pascal они инициализируются нулями автоматически, а в C++ нет.
Вот код исправленных функций

Код:

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

Сравнивание без учета регистра
if (IndistinctMatching(4, "поисковая строка", "оригинальная строка  - эталон") > 40) ...
*/
struct retCount{
    int lngSubRows;
    int lngCountLike;
};

retCount Matching(QString InputA,
                  QString InputB,
                  int lngLen)
{
    retCount TempRet;
        TempRet.lngCountLike = 0;
        TempRet.lngSubRows = 0;
    int PosStrB = 0;
    int PosStrA = 0;
    QString StrTempA = "";
    QString StrTempB = "";
    QString StrInputA = InputA.toLower();
    QString StrInputB = InputB.toLower();

    QString StrA = StrInputA;
    QString StrB = StrInputB;

    for ( PosStrA = 1; PosStrA <= (StrA.length() - lngLen + 1); ++PosStrA){
       StrTempA = StrA.mid(PosStrA, lngLen);
       PosStrB = 1;
       for (PosStrB = 1; PosStrB <= (StrB.length() - lngLen + 1); ++PosStrB){
          StrTempB = StrB.mid(PosStrB, lngLen);
          if (StrTempA == StrTempB){
             TempRet.lngCountLike++;
             break;
          }
       }
       TempRet.lngSubRows++;
    }
    return TempRet;
}

int IndistinctMatching(QString InputMatching,
                       QString InputStandart,
                       int MaxMatching = 4)
{
    QString strInputMatching = InputMatching.toLower();
    QString strInputStandart = InputStandart.toLower();
    retCount gret;
        gret.lngCountLike = 0;
        gret.lngSubRows = 0;
    retCount tret;
        tret.lngCountLike = 0;
        tret.lngSubRows = 0;
    int lngCurLen = 0; //текущая длина подстроки
    //если не передан какой-либо параметр, то выход
    if ((MaxMatching == 0) || (strInputMatching.length() == 0) || (strInputStandart.length() == 0)){
        return 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;
    }
    float rez = ((float)gret.lngCountLike/(float)gret.lngSubRows);
    rez = rez*100;
    return (int)rez;
}

Название: Re: Нечеткое сравнение строк
Отправлено: Vitto74 от Февраль 20, 2010, 13:22

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

Название: Re: Нечеткое сравнение строк
Отправлено: BlackTass от Февраль 21, 2010, 19:40

Цитата: Vitto74 от Февраль 20, 2010, 13:22

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

Название: Re: Нечеткое сравнение строк
Отправлено: Vitto74 от Февраль 21, 2010, 22:26

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

Russian Qt Forum

Программирование => Алгоритмы => Тема начата: Vitto74 от Февраль 19, 2010, 22:51