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

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

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

  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:indMax), но и триграммы тоже.
Т.е. при сопоставлении двух строк нужно всегда искать процент подобия более короткой триграммы в длинной.

[finsoftrz]

А для тупых и по русски можно перевести?

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

Я попробую ...
Есть задача нечёткого поиска - с ней разобрались, всё OK !

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

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

Рассмотрим классический пример.
--------------------------------------------
- Сравниваем 'word' и 'two words'.
- Триграммы: {" w"," wo","wor","ord","rd "} и {" t"," tw","two","wo "," w"," wo","wor","ord","rds","ds "}
- совпадают 4 триграммы {" w"," wo","wor","ord"} и правильный процент схожести 4 / 5 = 0.8
- Но для этого нужно всегда искать кол-во совпадений КОРОТКОЙ триграммы в ДЛИННОЙ и делить на кол-во триграмм в КОРОТКОЙ.

Независимо от того, в каком порядке идут записи для сравнения. А в алгоритме сравнение в порядке следования записей и всё.

P/S: И можно оптимизировать сам алгоритм, уменьшив кол-во проходов - но это уже другая история.

[finsoftrz]

Я не очень понимаю, что Вы имеете ввиду под короткая и длинная триграмма. Это слово, разбитое на триграммы или количество символов (кроме пробела) в каждой триграмме?
И если сравнивать "word" с "two words bla bla bla", то будет 80% схожести?

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

что Вы имеете ввиду под короткая и длинная триграмма

Длина - это кол-во триграмм на которые разбивается строка (G_Trigram.Index).
В Вашем примере это переменные lor:indSel / lor:ind

И если сравнивать "word" с "two words bla bla bla", то будет 80% схожести?

Да - это правильный результат. Независимо от кол-ва All(' bla').
Но для этого нужно всегда расчитывать кол-во триграмм "word" в триграммах "two words bla bla bla"
независимо от порядка следования записей и делить на кол-во триграмм в "word".

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

Хотя Вы тоже правы ...
Потому что если по моему способу сравнивать строки "Игорь Столяров" и "Игорь Столяров Ибн Хоттаб" -
то получится что они 100%, так как длинная строка содержит все триграммы короткой. Но это неправильно.

[finsoftrz]

Я понял. Это исключение, как жи, ши пиши с буквой и.

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

К сожалению, но Вы правы.
Порядок сравнения триграмм не имеет значения, а процент расчитывается делением на максимальное кол-во триграмм.

В принципе, все мои танцы с бубном, тоже дают правильный результат.
Но он полностью совпадает с результатом по Вашему более простому алгоритму расчёта ...

Поиск дубликатов с достоверностью 75%