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

Clarion, Clarion 7

Модератор: Дед Пахом

Правила форума
При написании вопроса или обсуждении проблемы, не забывайте указывать версию Clarion который Вы используете.
А так же пользуйтесь спец. тегами при вставке исходников!!!
kreator
✯ Ветеран ✯
Сообщения: 5047
Зарегистрирован: 28 Май 2009, 15:54
Откуда: Москва
Благодарил (а): 7 раз
Поблагодарили: 23 раза

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

Сообщение kreator »

Да, я не прав. Невнимателен.
We are hard at work… for you. :)
Аватара пользователя
Игорь Столяров
Ветеран движения
Сообщения: 7515
Зарегистрирован: 07 Июль 2005, 10:19
Откуда: г. Ростов-на-ДоМу
Благодарил (а): 18 раз
Поблагодарили: 53 раза

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

Сообщение Игорь Столяров »

finsoftrz писал(а): 07 Июнь 2024, 15:18 Накидал тест алгоритма на коленке.
Спасибо ! Алгоритм рассыпания строк на триграммы - понятен. :)
В принципе, алгоритм поиска подстроки в списке будет намного проще, чем реализованное у Вас полное сопоставление всех строк.
За теми кто отстал - не возвращаться. (С) Кодекс
Аватара пользователя
finsoftrz
✯ Ветеран ✯
Сообщения: 4753
Зарегистрирован: 06 Ноябрь 2014, 12:48
Благодарил (а): 10 раз
Поблагодарили: 38 раз

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

Сообщение finsoftrz »

Не очень понял, про что речь. Алгоритм с разбиением на триграммы для поиска дубликатов в специальном отчете. Раньше у меня был самодельный алгоритм, там я тоже разбивал на триграммы, но не добавлял пробелы, поэтому не работало как надо. Если речь про поиск записей в LIST, то он там не используется.
C6/C11, ШВС, tps/btrieve.
Аватара пользователя
Игорь Столяров
Ветеран движения
Сообщения: 7515
Зарегистрирован: 07 Июль 2005, 10:19
Откуда: г. Ростов-на-ДоМу
Благодарил (а): 18 раз
Поблагодарили: 53 раза

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

Сообщение Игорь Столяров »

finsoftrz писал(а): 11 Июнь 2024, 7:58 Не очень понял, про что речь.
С алгоритмом всё отлично, задача другая.
Например, есть строка для поиска "Трансформатор BT101" и нужно найти товары с подобием в наименовании 80%.
За теми кто отстал - не возвращаться. (С) Кодекс
Аватара пользователя
finsoftrz
✯ Ветеран ✯
Сообщения: 4753
Зарегистрирован: 06 Ноябрь 2014, 12:48
Благодарил (а): 10 раз
Поблагодарили: 38 раз

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

Сообщение finsoftrz »

Для поиска я ставлю задачу иначе. Есть строка для поиска "тран 101",надо найти все товары, в названии которых одновременно есть подстроки "тран" и "101", не важно, в каком порядке. Для пользователя такой поиск очень удобен. Он обычно помнит только некоторые якорные фразы, может их не задумываясь ввести в сокращённо виде.
C6/C11, ШВС, tps/btrieve.
Аватара пользователя
Игорь Столяров
Ветеран движения
Сообщения: 7515
Зарегистрирован: 07 Июль 2005, 10:19
Откуда: г. Ростов-на-ДоМу
Благодарил (а): 18 раз
Поблагодарили: 53 раза

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

Сообщение Игорь Столяров »

finsoftrz писал(а): 11 Июнь 2024, 9:21 Для пользователя такой поиск очень удобен
Да, Вы расказывали, про хитрый поиск по фрагментам.
В принципе, это два последовательных поиска (или одновременный поиск по двум полям) через InString().

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

Если продолжать электротехническую тему, то при ошибке в наименовании "Трнсформатор",
обычный (или хитрый) запрос по "тран" ничего не находит ... :(
За теми кто отстал - не возвращаться. (С) Кодекс
Аватара пользователя
finsoftrz
✯ Ветеран ✯
Сообщения: 4753
Зарегистрирован: 06 Ноябрь 2014, 12:48
Благодарил (а): 10 раз
Поблагодарили: 38 раз

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

Сообщение finsoftrz »

Игорь Столяров писал(а): 11 Июнь 2024, 9:57
finsoftrz писал(а): 11 Июнь 2024, 9:21 Если продолжать электротехническую тему, то при ошибке в наименовании "Трнсформатор",
обычный (или хитрый) запрос по "тран" ничего не находит ... :(
А на 80% найдет? :-)
C6/C11, ШВС, tps/btrieve.
Аватара пользователя
Игорь Столяров
Ветеран движения
Сообщения: 7515
Зарегистрирован: 07 Июль 2005, 10:19
Откуда: г. Ростов-на-ДоМу
Благодарил (а): 18 раз
Поблагодарили: 53 раза

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

Сообщение Игорь Столяров »

finsoftrz писал(а): 11 Июнь 2024, 12:55 А на 80% найдет?
Ваша реализация алгоритма (с благодарностью) взята за основу и далее пробуем. :)
За теми кто отстал - не возвращаться. (С) Кодекс
Аватара пользователя
Игорь Столяров
Ветеран движения
Сообщения: 7515
Зарегистрирован: 07 Июль 2005, 10:19
Откуда: г. Ростов-на-ДоМу
Благодарил (а): 18 раз
Поблагодарили: 53 раза

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

Сообщение Игорь Столяров »

Проконсультировался по сабжу у питонистов - сразу назвали 10 вариантов (платных и бесплатных).
И сказали что ещё их куча - но нужно посмотреть. И наворотов с опциями там тьма ... Везучки ! :(
За теми кто отстал - не возвращаться. (С) Кодекс
Аватара пользователя
Игорь Столяров
Ветеран движения
Сообщения: 7515
Зарегистрирован: 07 Июль 2005, 10:19
Откуда: г. Ростов-на-ДоМу
Благодарил (а): 18 раз
Поблагодарили: 53 раза

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

Сообщение Игорь Столяров »

finsoftrz писал(а): 07 Июнь 2024, 15:18 Накидал тест алгоритма на коленке
Если позволите обсудить реализацию, то есть вопросы ...
Начать наверно лучше с формирования наборов триграмм.

Если взять простой тест из примера, то предложенный алгоритм разбивает слово "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
✯ Ветеран ✯
Сообщения: 4753
Зарегистрирован: 06 Ноябрь 2014, 12:48
Благодарил (а): 10 раз
Поблагодарили: 38 раз

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

Сообщение finsoftrz »

А с каким процентом соответствия определяется подобие строк "Word" и "Word (ext)"?
C6/C11, ШВС, tps/btrieve.
Аватара пользователя
Игорь Столяров
Ветеран движения
Сообщения: 7515
Зарегистрирован: 07 Июль 2005, 10:19
Откуда: г. Ростов-на-ДоМу
Благодарил (а): 18 раз
Поблагодарили: 53 раза

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

Сообщение Игорь Столяров »

finsoftrz писал(а): 14 Июнь 2024, 10:05 А с каким процентом соответствия определяется подобие строк "Word" и "Word (ext)"?
Есстессно 100% (проверил), хотя здесь и так сразу видно, что в "Word (ext)" есть все триграммы "Word".
А тестовые "Word" и "two words" показывает штатные 80%. Но это поиск, а не сопоставление наименований.

Я знаю - что Вы оцениваете схожесть при сравнении по строке с максимальным кол-вом триграмм.
Но ... с алгоритмом сравнения триграмм я ещё работаю. :)
Потому, что нужно разобраться с различием при поиске типа: "la" / "lala" в "lalaland" и т.д. :shock:
За теми кто отстал - не возвращаться. (С) Кодекс
Аватара пользователя
finsoftrz
✯ Ветеран ✯
Сообщения: 4753
Зарегистрирован: 06 Ноябрь 2014, 12:48
Благодарил (а): 10 раз
Поблагодарили: 38 раз

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

Сообщение finsoftrz »

Да, тут вопрос в критерии. Ваш алгоритм с сохранением разбивки по словам выглядит более правильно.
C6/C11, ШВС, tps/btrieve.
Аватара пользователя
Игорь Столяров
Ветеран движения
Сообщения: 7515
Зарегистрирован: 07 Июль 2005, 10:19
Откуда: г. Ростов-на-ДоМу
Благодарил (а): 18 раз
Поблагодарили: 53 раза

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

Сообщение Игорь Столяров »

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

Безымянный.jpg

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

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

! Неточный поиск значения 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)  ! Возвращаем процент схожести  
За теми кто отстал - не возвращаться. (С) Кодекс
Аватара пользователя
Игорь Столяров
Ветеран движения
Сообщения: 7515
Зарегистрирован: 07 Июль 2005, 10:19
Откуда: г. Ростов-на-ДоМу
Благодарил (а): 18 раз
Поблагодарили: 53 раза

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

Сообщение Игорь Столяров »

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

1.jpg

2.jpg
За теми кто отстал - не возвращаться. (С) Кодекс
Ответить