javascript - 如何在 JavaScript 中搜索最接近的标签集匹配？

Question

我有一组文档，每个文档都用一组标签进行注释，其中可能包含空格。用户提供了一组可能拼写错误的标签，我想找到具有最多匹配标签(可选加权)的文档。

有数千个文档和标签，但每个文档最多 100 个标签。

我正在寻找一种轻量级且高性能的解决方案，其中搜索应该完全在客户端使用 JavaScript 进行，但可以使用 node.js 对索引进行一些预处理。

我的想法是使用多重集创建文档标签的反向索引，以及查找拼写错误标签的正确拼写的模糊索引，这些索引是在 Node.js 的预处理步骤中创建的，并序列化为 JSON 文件。在搜索步骤中，我想首先查询查询集的每一项，查询模糊索引以获取最有可能的正确标签，如果存在则查询反向索引并将结果集添加到包(编号集)中。对所有输入标签执行此操作后，按降序排序的包内容应提供最佳匹配文档。

我的问题

1. 这似乎是一个常见问题，是否已经有一个可以重用的实现？我查看了 lunr.js 和 fusion.js，但它们似乎有不同的重点。
2. 这是解决问题的明智方法吗？您看到任何明显的改进吗？
3. 将模糊步骤与倒排索引分开更好还是有办法将它们结合起来？

Answer 1

您应该能够使用 Lunr 实现您想要的目标，这是一个简化的示例(和 jsfiddle ):

var documents = [{
  id: 1, tags: ["foo", "bar"],
 },{
  id: 2, tags: ["hurp", "durp"]
}]

var idx = lunr(function (builder) {
  builder.ref('id')
  builder.field('tags')

  documents.forEach(function (doc) {
    builder.add(doc)
  })
})

console.log(idx.search("fob~1"))
console.log(idx.search("hurd~2"))

这利用了 Lunr 中的几个功能:

1. 如果文档字段是一个数组，那么 Lunr 假设元素已经被标记化，这将允许您按原样索引包含空格的标签，即“foo bar”将被视为单个标签(如果这是你想要什么，问题并不清楚)
2. 支持模糊搜索，这里使用查询字符串格式。波浪号后面的数字是最大编辑距离，还有一些documentation这涉及到细节。

结果将按照与查询最匹配的文档进行排序，简单来说，包含更多匹配标签的文档排名会更高。

Is it better to keep the fuzzy step separate from the inverted index or is there a way to combine them?

一如既往，这取决于情况。 Lunr 维护两个数据结构，一个倒排索引和一个图。该图用于进行通配符和模糊匹配。它保留单独的数据结构，以便于存储倒排索引中与匹配无关的术语的额外信息。

根据您的用例，可以将两者结合起来，一种有趣的方法是有限状态传感器，只要您想要存储的数据很简单，例如一个整数(想想文档 ID)。有一篇很棒的文章讨论了这种数据结构，它类似于 Lunr - http://blog.burntsushi.net/transducers/ 中使用的数据结构。