Нечёткий поиск

[kreator]

Да, я не прав. Невнимателен.

[Игорь Столяров]

Накидал тест алгоритма на коленке.

Спасибо ! Алгоритм рассыпания строк на триграммы - понятен.
В принципе, алгоритм поиска подстроки в списке будет намного проще, чем реализованное у Вас полное сопоставление всех строк.

[finsoftrz]

Не очень понял, про что речь. Алгоритм с разбиением на триграммы для поиска дубликатов в специальном отчете. Раньше у меня был самодельный алгоритм, там я тоже разбивал на триграммы, но не добавлял пробелы, поэтому не работало как надо. Если речь про поиск записей в LIST, то он там не используется.

[Игорь Столяров]

Не очень понял, про что речь.

С алгоритмом всё отлично, задача другая.
Например, есть строка для поиска "Трансформатор BT101" и нужно найти товары с подобием в наименовании 80%.

[finsoftrz]

Для поиска я ставлю задачу иначе. Есть строка для поиска "тран 101",надо найти все товары, в названии которых одновременно есть подстроки "тран" и "101", не важно, в каком порядке. Для пользователя такой поиск очень удобен. Он обычно помнит только некоторые якорные фразы, может их не задумываясь ввести в сокращённо виде.

[Игорь Столяров]

Для пользователя такой поиск очень удобен

Да, Вы расказывали, про хитрый поиск по фрагментам.
В принципе, это два последовательных поиска (или одновременный поиск по двум полям) через InString().

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

Если продолжать электротехническую тему, то при ошибке в наименовании "Трнсформатор",
обычный (или хитрый) запрос по "тран" ничего не находит ...

[finsoftrz]

Если продолжать электротехническую тему, то при ошибке в наименовании "Трнсформатор",
обычный (или хитрый) запрос по "тран" ничего не находит ...

А на 80% найдет?

[Игорь Столяров]

А на 80% найдет?

Ваша реализация алгоритма (с благодарностью) взята за основу и далее пробуем.

[Игорь Столяров]

Проконсультировался по сабжу у питонистов - сразу назвали 10 вариантов (платных и бесплатных).
И сказали что ещё их куча - но нужно посмотреть. И наворотов с опциями там тьма ... Везучки !

[Игорь Столяров]

Накидал тест алгоритма на коленке

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

Если взять простой тест из примера, то предложенный алгоритм разбивает слово "word"
на 7 триграмм вместо 5 и вообще не попадает со строками из нескольких слов.

Я попробовал сделать реализацию разбиения строки на триграммы на основании Вашей.
Вот такой вариант проходит все тесты и я в нём не вижу проблем ...

Код: Выделить всё

! Трансформация строки в набор триграмм для нечёткого поиска
StringToTrigram  Procedure(String sField_,*G_Trigram gTrigram)

!G_Trigram  Group,Type
!Object       Long
!Index        Long
!Mass         String(3),Dim(1000)
!           end

eSymbols  Equate('ABCDEFGHIJKLMNOPQRSTUVWXYZАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ0123456789')
cData     CString(Len(sField_) * 2 + 1)
lCount    Long,Auto
lMax      Long(Maximum(gTrigram.Mass,1)) ! Ограничение по размеру массива триграмм 
lFlag     Byte(True)

  Code
  Clear(gTrigram)                        ! Сбросить значение триграммы
  sField_ = Clip(Left(Upper(sField_)))   ! Нормализация исходной строки
  
  Loop lCount = 1 to Len(Clip(sField_))                                         
    If sField_[lCount] = ' ' and lFlag   ! Слово внутри строки начинается с 2-х пробелов 
       lFlag = False                     ! Убираем повторение пробелов внутри строки
       cData = cData & '  '
                                         ! Только алфавитно-цифровые символы 
    elsIf InString(sField_[lCount],eSymbols,1,1)
       cData = cData & sField_[lCount]
       lFlag = True
    end   
  end
  
  ! Строка начинается с 2-х пробелов и заканчивается 1-им пробелом
  If Clip(cData) <> '' then cData = '  ' & Clip(cData) & ' '.
  
  ! Ну и, собственно, теперь разбиение строки на триграммы    
  Loop lCount = 1 to Len(cData) - 2
                   ! Контроль ограничение по размеру массива триграмм
    If lCount > lMax then Break.     
                   ! Триграмма не может заканчиваться на два пробела
    If cData[(lCount+1):(lCount+2)] <> '  '    
       gTrigram.Index += 1
       gTrigram.Mass[gTrigram.Index] = cData[(lCount):(lCount+2)] ! = Sub(cData,lCount,3)
    end   
  end

[finsoftrz]

А с каким процентом соответствия определяется подобие строк "Word" и "Word (ext)"?

[Игорь Столяров]

А с каким процентом соответствия определяется подобие строк "Word" и "Word (ext)"?

Есстессно 100% (проверил), хотя здесь и так сразу видно, что в "Word (ext)" есть все триграммы "Word".
А тестовые "Word" и "two words" показывает штатные 80%. Но это поиск, а не сопоставление наименований.

Я знаю - что Вы оцениваете схожесть при сравнении по строке с максимальным кол-вом триграмм.
Но ... с алгоритмом сравнения триграмм я ещё работаю.
Потому, что нужно разобраться с различием при поиске типа: "la" / "lala" в "lalaland" и т.д.

[finsoftrz]

Да, тут вопрос в критерии. Ваш алгоритм с сохранением разбивки по словам выглядит более правильно.

[Игорь Столяров]

Ещё раз огромное спасибо всем за помощь !
В принципе, цель достигнута. Далее уже будем совершенствоваться в реальных условиях.

Алгоритм поиска по триграммам практически без изменений,
только нужно блокировать повторы нахождения одного значения в строке:

Код: Выделить всё

! Неточный поиск значения tFind_ в строке tStr_ по триграммам
FindTrigram  Procedure(*G_Trigram tStr_,*G_Trigram tFind_)

lIndex1   Long,Auto
lIndex2   Long,Auto
lReplay   Long(0)
aFlag     Byte(False),Dim(MaxDimTrigram)  ! Признак нахождения триграммы в строке
 
  Code  
  Loop lIndex1 = 1 to tFind_.Index
    Loop lIndex2 = 1 to tStr_.Index
      If tStr_.Mass[lIndex2] = tFind_.Mass[lIndex1] and Not aFlag[lIndex2]
         aFlag[lIndex2] = True
         lReplay += 1
         Break   ! Иначе проблема !!! Проверка: lala -> lalaland = 120% :(  
      end
    end
  end  
  
  Return Round((lReplay * 100) / tFind_.Index,1)  ! Возвращаем процент схожести  

[Игорь Столяров]

Для товаров работа алгоритма нечёткого поиска по триграммам ещё наглядней.
Вариант поиска по запросу из нескольких слов (на разных языках и оба с ошибкой).