Russian Qt Forum
Март 28, 2024, 19:11 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1]   Вниз
  Печать  
Автор Тема: [РЕШЕНО]Нечеткое сравнение строк  (Прочитано 11749 раз)
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++ не нашел.
« Последнее редактирование: Февраль 23, 2010, 21:07 от Vitto74 » Записан
BlackTass
Гость
« Ответ #1 : Февраль 19, 2010, 23:29 »

я бы порекомендовал поискать что-нибудь по морфологии. Ваш алгоритм никак не привязан к особенностям языка. Если же надо сделать просто нечеткое сравнение двух неважно-каких строковых данных, то имхо какой-нибудь soundex или подобные алгоритмы вполне подойдут.
Записан
Vitto74
Гость
« Ответ #2 : Февраль 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;
}
Записан
Vitto74
Гость
« Ответ #3 : Февраль 20, 2010, 13:22 »

Я смотрел в сторону морфологического разбора, но не хочу привязывать программу к русскому языку. Это будет универсальная оболочка для электронных учебников.
Записан
BlackTass
Гость
« Ответ #4 : Февраль 21, 2010, 19:40 »

Я смотрел в сторону морфологического разбора, но не хочу привязывать программу к русскому языку. Это будет универсальная оболочка для электронных учебников.
что мешает задавать параметры морфо-разбора через некие конфиги (то есть чтобы подключить язык нужно будет просто переписать настройки разбора на нужные) ? Проблемы (и то решаемые) будут только с иероглифической группой языков (кстати в вашем алгоритме также будут проблемы) и с полисинтетической группой. Корневые, флективные и агглютинирующие в принципе (с небольшими погрешностями) можно объединить в один разбор, но с разными параметрами.
Записан
Vitto74
Гость
« Ответ #5 : Февраль 21, 2010, 22:26 »

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


Страница сгенерирована за 0.067 секунд. Запросов: 21.