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

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

Привет всем !

Вопрос простой и прямой: не пробовал ли кто-нибудь реализовать нечёткий поиск (например с заданным процентом подобия) ?

1. В принципе, алгоритмика известна, но я не математик.
Исходники есть на Java и Python ... Может быть тема поднималась где-то в архивах ClaMag ?

2. Конкретно меня сейчас интересует вопрос поиска подобных товаров (когда их названия записывают по-разному).
Например: Сосиска в тесте, булочка с сосиской, сосиська запечённая в тесте и т.д.

3. В Clarion есть MATCH(). Опция Match:Soundex (по звучанию) не локализована, поиск по маске - это иное ...

Я не спрашиваю о готовом решении (хотя это было бы круто), но хотя бы направление туда, где рыба есть.
Что бы не идти методом познания, на основе собственных ошибок. Заранее спасибо !

[finsoftrz]

Я давно пытался реализовать этот механизм для названий товаров и контрагентов. Именно в таком ключе, по проценту подобия. Делал алгоритм с разбиением на триады. Но, в целом, нормально не получилось, отлавливались только самые примитивные ситуации. В результате, просто отключил этот отчёт. Если удастся найти работающей решение, штука нужная и полезная.

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

Спасибо ! Понял. Попробую спросить на хабе, может СуперКарл поможет ...

[Ravenous]

Я делал на стороне БД (MSSQL, Oracle), в PostgreSQL есть pg_trgm тоже нормально работает.

[kreator]

Логика простая. Данные должны храниться сейчас хотя бы в "формате" SQL. А там много чего есть. Если там нет, то надо теребить разработчиков таких серверов. Поиск правильно осуществлять на стороне сервера.

[finsoftrz]

Я несколько не так на триграммы разбивал. Надо будет попробовать алгоритм, как описано в psql, с добавлением пробелов. Так то все просто должно быть.

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

алгоритм, как описано в psql

Ссылу почитать опять засекретите ?

[finsoftrz]

алгоритм, как описано в psql

Ссылу почитать опять засекретите ?

В сообщении от Ravenous.

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

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

[finsoftrz]

В начале ("Примечание") вроде все понятно написано. Не?

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

Ну не знаю. Наверно люди написавшие

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

понимают в этом. Можно попробовать сделать и посмотреть ...

[Ravenous]

Вот статья на которую опирался при написании своей реализации
https://blog.arbinada.com/ru/category/00020.html

Реализация pg_trgm
https://github.com/postgres/postgres/tr ... ib/pg_trgm

[finsoftrz]

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

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

form_r routine   !формирование отчета
  DATA
lor:queue queue, pre()
lor:idobj   long
lor:ind     long
lor:mass    string(3),dim(10000)
.
lor:symbols string(100)
lor:str     string(3)
lor:dl      long
lor:kolRep  long

lor:nameobjSel string(200)
lor:idobjSel   long
lor:indSel     long
lor:indMax     long
lor:massSel    string(3),dim(10000)
lor:massContr  long,dim(10000)

lor:i   long
lor:j   long
lor:k   long
lor:n   long

BasicProcess  BasicProcessType

  CODE

       lor:symbols='abcdefghijklmnopqrstuvwxyzабвгдеёжзийклмнопрстуфхцчшщъыьэюя0123456789'  !список анализируемых символов

       BasicProcess.Init(True,'Загрузка товаров',,,,,100,Records(tovar))
       set(tovar)
       loop
          next(tovar)
          if error()
             break
          .
          if ~BasicProcess.LoopStep()
             break
          .
          if tov:NoPost=1
             cycle
          .
          if tov:name=''
             cycle
          .

          tov:name=left(lower(tov:name))
          lor:nameobjSel=''
          lor:j=0
          loop lor:i=1 to len(clip(tov:name))
             if instring(tov:name[lor:i],clip(lor:symbols),1,1)>0
                lor:j+=1
                lor:nameobjSel[lor:j]=tov:name[lor:i]
             .
          .

          clear(lor:queue)
          lor:idobj=tov:id
          lor:dl=len(clip(lor:nameobjSel))

          lor:ind=0
          lor:k=1
          loop
             if lor:k>lor:dl
                break
             .
             lor:str=lor:nameobjSel[lor:k : lor:k+2]
             if lor:ind>9996
                break
             .
             lor:ind+=1
             lor:mass[lor:ind]='  ' & lor:str[1]
             lor:ind+=1
             lor:mass[lor:ind]=' ' & lor:str[1 : 2]
             lor:ind+=1
             lor:mass[lor:ind]=lor:str
             if lor:str[2 : 3]<>''
                lor:ind+=1
                lor:mass[lor:ind]=lor:str[2 : 3] & ' '
             .
             lor:k+=3
          .
          add(lor:queue)
       .

    BasicProcess.Kill()

    open(ProgressWindow)
    BasicProcess.Init(False,'Сопоставление',,?Progress:Thermometer,?Progress:Cancel,True,5,Records(lor:queue),?Progress:UserString)
    loop lor:i=1 to records(lor:queue)-1
       get(lor:queue,lor:i)
       if ~BasicProcess.LoopStep()
          break
       .

       lor:indSel=lor:ind
       lor:idobjSel=lor:idobj
       lor:massSel=lor:mass

       loop lor:j=lor:i+1 to records(lor:queue)
          get(lor:queue,lor:j)
          lor:kolRep=0
          lor:indMax=choose(lor:indSel>lor:ind,lor:indSel,lor:ind)
          clear(lor:massContr)
          loop lor:k=1 to lor:indSel
             loop lor:n=1 to lor:ind
                if lor:mass[lor:n]=lor:massSel[lor:k] and lor:massContr[lor:n]=0
                   lor:kolRep+=1
                   lor:massContr[lor:n]=1
                .
             .
          .
          lor:kolRep=lor:kolRep/lor:indMax*100
          if Loc:Proc<=lor:kolRep
             clear(Loc:Queue)
             Loc:IDObj1=lor:idobjSel
             Loc:IDObj2=lor:idobj
             Loc:ProcQ=lor:kolRep
             add(Loc:Queue)
          .
       .
    .

    free(lor:queue)
    BasicProcess.Kill()
    close(ProgressWindow)

[kreator]

Почему паштет №6 "Корона Балтики" не имеет дубликата? наверно есть ещё над чем работать.

[finsoftrz]

Почему паштет №6 "Корона Балтики" не имеет дубликата? наверно есть ещё над чем работать.

Не понял.