[UltraBloxX]

Я делаю чатбота. Мне нужен быстрый алгоритм нечёткого поиска строк в базе знаний.

[AleD]

Сообщение от UltraBloxX

Я делаю чатбота. Мне нужен быстрый алгоритм нечёткого поиска строк в базе знаний.

Самые рендомные генераторы - самые сложные, юзай лучше Radnom\RandomRange

[UltraBloxX]

Не, рендомный мне не нужен. У меня уже готовый бот есть, только алгоритм нечёткого сравнения фраз у него плохой.

[NIch]

Вот подгонял под себя, но думаю подойдет...

Код:

//*********************************************************
//Функция нечеткого сравнения строк
//------------------------------------------------------------------------------
//MaxMatching - максимальная длина подстроки (достаточно 3-4)
//strInputMatching - сравниваемая строка
//strInputStandart - строка-образец
// Сравнивание без учета регистра
// if IndistinctMatching(4, "поисковая строка", "оригинальная строка  - эталон") > 40 then ...
//------------------------------------------------------------------------------
function TParser.pMatching(StrInputA: WideString;StrInputB: WideString;lngLen: Integer) : TRetCount;
Var
    TempRet   : TRetCount;
    PosStrB   : Integer;
    PosStrA   : Integer;
    StrA      : WideString;
    StrB      : WideString;
    StrTempA  : WideString;
    StrTempB  : WideString;
begin
    StrA := String(StrInputA);
    StrB := String(StrInputB);
    For PosStrA:= 1 To Length(strA) - lngLen + 1 do
    begin
       StrTempA:= System.Copy(strA, PosStrA, lngLen);
       //PosStrB:= 1;
       For PosStrB:= 1 To Length(strB) - lngLen + 1 do
       begin
          StrTempB:= System.Copy(strB, PosStrB, lngLen);
          If SysUtils.AnsiCompareText(StrTempA,StrTempB) = 0 Then
          begin
             Inc(TempRet.lngCountLike);
             break;
          end;
       end;
       Inc(TempRet.lngSubRows);
    end; // PosStrA
    pMatching.lngCountLike:= TempRet.lngCountLike;
    pMatching.lngSubRows  := TempRet.lngSubRows;
end;
//------------------------------------------------------------------------------
function TParser.pIndistinctMatching(MaxMatching: Integer; strInputMatching: WideString; strInputStandart: WideString): Integer;
Var
    gret     : TRetCount;
    tret     : TRetCount;
    lngCurLen: Integer   ; //текущая длина подстроки
begin
    //если не передан какой-либо параметр, то выход
    If (MaxMatching = 0) Or (Length(strInputMatching) = 0) Or
       (Length(strInputStandart) = 0) Then
    begin
        pIndistinctMatching:= 0;
        exit;
    end;
    gret.lngCountLike:= 0;
    gret.lngSubRows  := 0;
    // Цикл прохода по длине сравниваемой фразы
    For lngCurLen:= 1 To MaxMatching do
    begin
        //Сравниваем строку A со строкой B
        tret:= pMatching(strInputMatching, strInputStandart, lngCurLen);
        gret.lngCountLike := gret.lngCountLike + tret.lngCountLike;
        gret.lngSubRows   := gret.lngSubRows + tret.lngSubRows;
        //Сравниваем строку B со строкой A
        tret:= pMatching(strInputStandart, strInputMatching, lngCurLen);
        gret.lngCountLike := gret.lngCountLike + tret.lngCountLike;
        gret.lngSubRows   := gret.lngSubRows + tret.lngSubRows;
    end;
    If gret.lngSubRows = 0 Then
    begin
        pIndistinctMatching:= 0;
        exit;
    end;
    pIndistinctMatching:= Trunc((gret.lngCountLike / gret.lngSubRows) * 100);
end;

[UltraBloxX]

Этот алгоритм я уже пробовал прикрутить - но при базе данных в 800 КБ и входного сообщения в 8 символов обработка идёт примерно 55 секунд, и с увеличением размера входного сообщения время обработки увеличивается в несколько раз.

[NIch]

Немного инфы...

Еще раз о нечетком сравнении строк
--------------------------------------------------------------------------------


Автор: Дмитрий Кузан

По мотивам обсуждения статьи Функция приблизительного (нечеткого) сравнения строк

Второй вариант поиска: compare1.zip (359 K)

Отличия от первого, по моим субъективным наблюдениям, в следующем:

1. Лучше находит похожие слова лежащие в одной плоскости
Соха - Сноха - совпадение 88 при том что в первом алгоритме составило 66 при длине фразы = 3
2. Хуже находит похожие (даже идентичные), но перевернутые слова
Тихий Дон - Дон Тихий - в первом способе совпадение 79 во втором 55 - очень существено.
Так что первый способ я рекомендовал для сравнения, например, полей двух баз данных.

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

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

Если вас это заинтересует то могу прислать в оригинале (написан он на C), но перевести в Pascal для людей которых это заинтересует, не составит труда.

И, напоследок, предлагаю вам архив с примерами алгоритмов анализа строк. К сожалению страницы указанные в архиве, как начальные, где можно найти информацию, не работают - поэтому высылаю слепок с сайта. Скачать stephen.zip (185 К)

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

3. ОБЗОР АЛГОРИТМОВ
3. 1 Сопоставления строк
3. 2 Расстояния между строками
3. 2.1 Обобщенные задачи
3. 3 Нечеткое сопоставление строк
3. 3.1 Специальные устройства
3. 4 Максимальная повторяющаяся подстрока
4. АЛГОРИТМЫ
4. 1 Поиск образцов
4. 1.1 Наивный подход
4. 1.2 Кнут-Моррис-Пратт
4. 1.3 Бойер-Мур
4. 1.4 Бойер-Мур-Хорспул
4. 1.5 Сандей: Быстрый поиск, Максимальный сдвиг, Оптимальное несовпадение
4. 1.6 Хьюм и Сандей. Улучшенные алгоритмы Бойера-Мура и Наименьшая цена
4. 1.7 Харрисон
4. 1.8 Карп-Рабин
4. 2 Расстояние между строками и самая длинная общая подпоследовательность
4. 2.1 Вагнер-Фишер
4. 2.2 Хиршберг
4. 2.3 Хант-Шиманский
4. 2.4 Машек-Патерсон
4. 2.5 Укконен
4. 2.6 Самая тяжелая общая подпоследовательность
4. 3 НЕЧЕТКОЕ СОПОСТАВЛЕНИЕ СТРОК
4. 3.1 k несовпадений - Ландау-Вишкин
4. 3.2 k различий - Ландау-Вишкин
4. 4 Самая длинная повторяющаяся подстрока
4. 4.1 Наивный подход
4. 4.2 Суффиксные деревья

[UltraBloxX]

Второй алгоритм при поиске тоже медленно работает...