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

我有一组文档，每个文档都用一组可以包含空格的标签进行注释。用户提供一组可能拼错的标签，我想找到匹配标签数量最多的文档（可选择加权）。如何在JavaScript中搜索最接近的标记集匹配？

有几千个文档和标签，但每个文档至多有100个标签。

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

我的想法是使用multiset和模糊索引来创建文档的反向索引，该索引可以找到拼写错误的标签的正确拼写，这些拼写是在node.js中的预处理步骤中创建的，并且序列化为JSON文件。在搜索步骤中，我想先为查询集的每个项目查询模糊索引以获得最有可能的正确标签，并且如果存在查询反向索引并将结果集添加到袋子（编号集）。在完成所有输入标签后，袋子的内容按降序排列，应提供最佳匹配文档。

我的问题

这似乎是一个常见的问题，有没有已经为它的实现，我可以重用？我看着lunr.js和fuse.js，但他们似乎有不同的重点。
1. 这是一个明智的方法来解决这个问题吗？你看到任何明显的改进？
2. 将模糊步与反向索引分开还是有办法将它们组合起来更好吗？

来源

2017-10-07 Konrad Höffner

您应该能够达到你想要使用什么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几个特点：

如果一个文档字段是一个数组，那么Lunr假定这些元素已经被标记了，这将允许您索引包含空格的标签，例如“foo ba r“将被视为单个标签（如果这是您想要的，则不清楚该问题）
支持模糊搜索，此处使用查询字符串格式。波浪号后面的数字是最大编辑距离，还有一些更详细的documentation。

结果将根据哪个文档与查询最匹配进行排序，简而言之，包含更多匹配标签的文档将排名更高。

将模糊步与反向索引分开还是有办法将它们组合起来更好吗？

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

根据您的使用情况，可以将两者结合起来，只要您要存储的数据很简单，例如有趣的方法就是有限状态转换器。一个整数（认为文档ID）。有一篇优秀的文章谈论这个数据结构，它类似于Lunr中使用的数据结构 - http://blog.burntsushi.net/transducers/

来源

2017-10-12 20:42:04

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

回答

相关问题