15 分钟。
浅尝一下字典树和倒排索引。
elasticlunr 是一个可以在浏览器端和 node 运行的全文搜索库，索引的基本结构就是用字典树结构保存的倒排索引。
复习下字典树的结构，word 和 would 两个词在字典树里这样保存：
{
"w": {
"o": {
"u": {
"l": {
"d": {
"docs": ["would"]
}
}
},
"r": {
"d": {
"docs": ["word"]
}
}
}
}
}
应该很好理解。
倒排索引我个人比较愿意从朴素搜索方法讲起。
朴素搜索方法是指给 100 个文档，你想搜 word 这个单词，那就要把 100 个文档遍历一遍，用字符串查找算法找出这个单词。
再进一步就是普通索引，数据库那种。把文档内容排成一棵树然后查找。
但问题又来了，像数据库给字符串字段加的索引一样，前缀匹配或者后缀匹配都还算好办，但如果是包含匹配，效率就高不起来了。
这时候全文搜索技术的基础，倒排索引就出来了。
倒排索引用了一些 NLP 的方法，比如 NLP 中关于词的做法。但不需要前面看深度学习 NLP 方法中给单词做向量化表示。
倒排索引的结构是把待搜索的文本先拆分成一系列词，拆分成词之后，我们实际上就是对规模较小的常用词进行索引编制了。
最终得到的是类似这样的结构。
{
"word": ["doc1", "doc2", "doc3", "..."],
"would": ["doc1", "doc2", "doc3", "..."]
}
在搜索时，我们对搜索的内容同样分词处理（纯浏览器场景下，可能就不分词了，用户自己打空格。因为中文分词还需要词库，成本挺高的）。
然后逐个关键词去查询关联的文档，简单吧？
我们看看 elasticlunr 实际的结构是什么样的。
{
"documentStore": {
"save": true,
"docs": {
"....": {}
}
},
"fields": ["title", "body"],
"index": {
"title": {
"root": {
"docs": {
"docs": {},
"df": 0,
"o": {
"docs": {},
"df": 0,
"r": {},
"u": {}
}
},
"df": 0,
"w": {}
}
},
"body": {
"root": {
"docs": {
"docs": {},
"df": 0,
"o": {
"docs": {},
"df": 0,
"r": {},
"u": {}
}
},
"df": 0,
"w": {}
}
}
},
"lang": "Chinese",
"pipeline": [
/* ... */
],
"ref": "id",
"version": "0.9.5"
}
核心结构就是这个 index ，root 在内，下面的节点都有 docs 和 df 属性，docs 表示从 root 出发到这个节点组成的词关联的文档。
所以搜索功能实现就是把关键词放这里面查找。
// 搜索字典树里所有子项
// 其实不必要，会查出无关内容。比如查铁可能查到铁木真。
// 我只是测试一下这个查法，看下在实时反馈搜索结果的表现会不会好点。
function collect_related_docs_recursively(inverted_index_node) {
const result = [...Object.getOwnPropertyNames(inverted_index_node.docs)];
for (const key of Object.getOwnPropertyNames(inverted_index_node)) {
if (key === "docs" || key === "df") {
continue;
}
result.push(...collect_related_docs_recursively(inverted_index_node[key]));
}
return result;
}
// 搜索字典树嵌套倒排索引的结构，返回去重后的结果
function search_inverted_index(index, keywords) {
const results = [];
for (let k = 0; k < keywords.length; k++) {
const keyword = keywords[k];
var current = index;
// 把传入的关键词逐个字在字典树里查询下降，找到代表这个词的节点。
for (let i = 0; i < keyword.length; i++) {
const char = keyword[i];
current = current[char];
// 显然这个词不存在的话我们就没法查到文档了。
// 中文分词全文搜索 NLP 处理比英语麻烦的多，如果搜索的关键词是 广州地铁，那就搜不出广州的地铁。
// 如果搜索广州的地铁，也搜不出广州地铁。
if (current === undefined) {
break;
}
}
// 查到内容了，组织成渲染的数据
if (current && current.docs) {
const related_docs = collect_related_docs_recursively(current);
results.push(related_docs);
}
}
// 查询结果去重
const final_result = [];
for (let i = 0; i < results.length; i++) {
const result = results[i];
for (let r = 0; r < result.length; r++) {
const result_id = result[r];
if (final_result.indexOf(result_id) === -1) {
final_result.push(result_id);
}
}
}
return final_result;
}
// 加载索引并绑定搜索框
new Promise((resolve) => document.addEventListener("DOMContentLoaded", resolve))
.then(() => fetch("/search_index.zh.json"))
.then((response) => response.json())
.then((data) => {
const si = document.getElementById("search_input");
si.removeAttribute("disabled");
si.setAttribute("placeholder", "输入关键词以开始搜索...");
si.addEventListener("input", function (event) {
const keyword = event.target.value;
const search_result = document.getElementById("search-results");
if (keyword.trim().length === 0) {
search_result.innerHTML = "";
return;
}
const result = search_inverted_index(
data.index.body.root,
keyword.split(" ")
);
const html_results = [];
result
.map((id) => data.documentStore.docs[id])
.map((doc) => {
const item = document.createElement("li");
const link = document.createElement("a");
link.setAttribute("href", doc.id);
const link_title = document.createTextNode(doc.title);
link.appendChild(link_title);
item.appendChild(link);
html_results.push(item);
});
search_result.replaceChildren(...html_results);
});
});
ok 结束。
超时18分钟。