Полнотекстовый поиск: найти похожие названия программ

Question

Я ищу алгоритм полнотекстового поиска, который позволит находить похожие названия программ, например, «Mozilla Firefox» и «Firefox 3.5, или« Adobe Reader »и« Adobe Acrobat Reader v10 ». слишком неэффективно в этом случае, так как орфография не меняется.

Должно использоваться последовательное сканирование (не индексация).

Мне нужна максимальная точность и минимум ошибок. Что бы вы порекомендовали?

Спасибо!

Answer 1

Сравнение шаблонов

Я использовал следующее для автоматической коррекции некоторых доменных имен.

Идея состоит в том, чтобы посмотреть на маленькие шаблоны, например, 2 последовательности символов. Каждый раз, когда такая последовательность обнаруживается, «счет» увеличивается для сравниваемой последовательности. Самые высокие оценки, вероятно, будут выглядеть одинаково.

Ex: Mozilla Firefox => ['mo', 'oz', 'zi', 'il', 'll', 'la', 'a', 'f', 'fi', 'ir', 're', 'fo' , «бык»]

Результаты:

• 'Firefox 3.5' => 5,
• 'Adobe Reader' => 0,
• 'Adobe Acrobat Reader v10' => 1

Автоматическая классификация с использованием сжатия

Это не полнотекстовый.

Идея, выраженная в этого документа , состоит в том, чтобы сравнить сжатие объединения двух элементов с объединением сжатых элементов.

Пусть c будет функцией, которая возвращает размер сжатого элемента:

d = c (A) + c (B) - c (A + B)

Чем меньше d, тем ближе A и B.
Интересным свойством является то, что этот принцип не зависит от типа и может использоваться с двоичными файлами, такими как музыка, изображения, видео и т. Д.

Еще одна ссылка, более удобная для чтения, но по-французски.

Использование полнотекстовых функций SGDB

Я немного заржавел на SQL Server, но SQLite или MySQL предлагают полнотекстовый поиск.
Результаты включают значение ранга, которое можно рассматривать как показатель сходства.

В MySQL:

SELECT
  t.*,
  MATCH(my_field) AGAINST 'Mozilla Firefox' as relevance
FROM
  table t
WHERE
  MATCH(my_field) AGAINST 'Mozilla Firefox'
ORDER BY relevance DESC
LIMIT 100