全文搜索:查找类似的软件名称

Question

我正在寻找一种全文搜索算法,可以找到类似的程序名称,例如"Mozilla Firefox"和"Firefox 3.5,或"Adobe Reader"和"Adobe Acrobat Reader v10".Levenshtein距离效率太低这种情况,因为拼写不会改变.

它必须使用串行扫描(而不是索引).

我需要最大的精度和最小的错误.你会推荐什么？

谢谢!

Answer 1

模式比较

我使用以下命令自动更正一些域名。

这个想法是查看小模式，例如 2 个字符序列。每次找到这样的序列时，比较序列的“分数”就会增加。最高分可能看起来很相似。

例如：Mozilla Firefox => ['mo', 'oz', 'zi', 'il', 'll', 'la', 'a', 'f', 'fi', 'ir', 're' , 'fo', 'ox']

结果：

• '火狐 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