static_search 设计

静态发布模式把整个应用作为文件提供，不需要服务器或 SQLite。此时搜索在浏览器中基于预先计算的索引运行。本页描述该索引及其查询算法，推导排名的含义和代价，并解释 MoonBit static_search 包在其中的角色。static_search API 列出了 MoonBit 函数。

三个部分协同工作：

部分	语言	职责
src/static_search	MoonBit (JS)	版本标记和小写规范化。
scripts/export_static_json.py	Python	从 SQLite 数据库写出索引和其他静态文件。
frontend/src/static-search.worker.ts	TypeScript	把索引加载到 Web Worker 中并回答查询。

设计目标

静态站点上的搜索必须接受与动态站点相同的查询形式（原生表达式语言、序列化的查询 AST 和简单表单字段），在页面渲染时保持响应，并且只需要 GitHub Pages 这类静态托管能提供的文件。

数学背景

数据布局

export_static_json.py 在 public/data/ 下写出以下文件：

文件	内容
manifest.json	schema_version、generated_at、package_count、data_mode = "static" 以及每个 feed 的大小。
feeds/top.json, feeds/hot.json, feeds/rising.json	三个 feed，按动态站点的 SQL 排序预先计算。
search/search-index.json	搜索索引：{ "items": [...] }，每个包一条记录。
search/packages.json	同样的包，附带展示用字段（关键词、版本数、乘数）。
packages/<owner>--<package>.json	详情页数据：包、最近 20 个版本、依赖方。

搜索索引的记录是一个扁平对象。除了包摘要的展示字段（名称、所有者、描述、版本、各计数和分数快照字段）之外，它还保存预先计算的搜索键：

键	值
normalized_owner, normalized_package, normalized_description, normalized_license, normalized_repository	该字段去除首尾空白并转为小写（缺失时为 ""）。
normalized_keywords	每个关键词，去除首尾空白并转为小写。
normalized_full_text	完整名称、所有者、包名、描述和关键词中非空的部分，用单个空格连接。
repository_present, license_present	去除首尾空白后该字段是否非空。
latest_created_at	发布时间戳；其前四个字符给出年份。

所以该索引是一个正排索引：由 $N$ 条记录组成的数组，每条记录有 $F$ 个固定字段，按 full_name 排序。没有倒排索引，也没有分词。在导出时转为小写，意味着查询时只需规范化查询词，而不必规范化每条记录。

作为布尔公式的查询

每个查询都会先由 lib/query.ts 中的 deriveQueryAst 转换成查询 AST，优先级如下：序列化的 ast 参数，否则是原生 expr，否则是用 AND 连接的旧式表单字段。AST 是关于项谓词的公式：

$$\varphi ::= t \mid \lnot\varphi \mid \varphi_1 \land \dots \land \varphi_k \mid \varphi_1 \lor \dots \lor \varphi_k ,$$

一个项 $t = (f, \mathit{op}, v)$ 在记录 $p$ 上的求值为

字段 $f$	$p \models t$ 的条件
text, owner, package, description, license, repository	$\nu(v)$ 是规范化字段的子串（$\nu$ = 去除首尾空白并转小写）；空查询词总是匹配。
keyword	$\nu(v)$ 是至少一个规范化关键词的子串。
rank, momentum	标签与 $v$ 完全相等。
score, dependents, recent_dependents, downloads, year	>= 时为 $x \ge v$，<= 时为 $x \le v$，其他情况为 $x = v$；$v$ 不是数字时为假。
has_repository, has_license	标志等于 v == "true"。

结果集为 $\{\, p : p \models \varphi \,\}$，通过短路的 every 和 some 递归求值。不含任何非空项的 AST 匹配所有记录。

相关度

当有查询且没有显式指定排序时，worker 按相关度计数排列结果。记 $L(\varphi)$ 为 AST 的项叶子构成的多重集，

$$\operatorname{rel}(p) = \bigl|\{\, t \in L(\varphi) : p \models t \,\}\bigr| ,$$

其中忽略否定：NOT 之下的叶子在其未取反的项匹配时计数。并列时先按分数（降序），再按 full_name（升序，使用 localeCompare）排序。

有两个推论值得推导，因为它们解释了用户看到的结果。

合取不会改变顺序。 设 $\varphi = t_1 \land \dots \land t_k$，其中各项都为正项。每个结果都满足所有 $t_i$，所以对所有结果 $\operatorname{rel}(p) = k$，顺序就是分数顺序。只有当公式含有 OR 或 NOT 时相关度才起作用。

析取按覆盖度排序。 对于 $\varphi = t_1 \lor \dots \lor t_k$，$\operatorname{rel}(p)$ 是 $p$ 满足的备选项个数，所以匹配所有备选项的包排在最前。对于取反的叶子 $\lnot t$，每个结果都有 $p \not\models t$，因此该叶子贡献 $0$。

因此相关度是一种协调级匹配¹1 协调级匹配按文档包含的查询词数量为文档排序；它是最简单的排序检索模型，早于 tf–idf 加权（Salton 与 McGill，Introduction to Modern Information Retrieval，1983）。 ，而不是文本统计量：它忽略词频、字段长度以及词的稀有程度。

排序方式与并列处理

其他排序键为 score、growth、downloads、dependents、recent、updated（发布年份）和 name。每次比较为

$$c(a, b) = s \cdot \bigl(\operatorname{key}(a) - \operatorname{key}(b) \;\Vert\; \operatorname{cmp}(a.\mathit{name}, b.\mathit{name})\bigr),$$

其中 $x \Vert y$ 表示”$x$ 非零时取 $x$，否则取 $y$“，降序时 $s = -1$，升序时 $s = +1$。name 默认升序，其他键默认降序。由于 $s$ 乘在整个表达式上，降序排序也会反转并列项的名称顺序。完整名称是唯一的，因此并列总能被打破，同样的索引和查询总是给出同样的顺序。

设计决策

扫描正排索引，而不是构建倒排索引

问题。 浏览器需要在没有数据库的情况下回答子串、数值和布尔查询。

选项。 携带编译为 WebAssembly 的 SQLite 及其 FTS5 索引；在导出时构建倒排索引（词 → 包）；扫描记录数组。

选择。 线性扫描。注册表只有几千个包，所以一次查询只涉及几千条短记录，对 worker 来说开销很小。子串匹配（pars 能找到 parser）和数值过滤不需要分词器和倒排表，索引也保持为一个导出脚本几行代码就能写出的普通 JSON 文件。WebAssembly 数据库会给每次访问增加大量下载。

在 Web Worker 中运行搜索

问题。 在主线程上解析整个索引并排序会阻塞渲染。

选择。 worker 只加载一次 search-index.json 并把记录保存在内存中；查询是带 id 的消息，每个回复都只解决具有相同 id 的请求，因此并发查询不会混淆。URL 以清单中的 generated_at 作为版本参数，新的清单会终止并重启 worker，因此过期的索引永远不会与新的 feed 混用。

导出时一次性规范化

问题。 不区分大小写的匹配需要两边都是小写文本。

选择。 Python 在导出时把记录转为小写（str.strip().lower()）；worker 只把查询词转为小写（trim().toLowerCase()）。两者都使用 Unicode 默认大小写映射，因此对于普通的包元数据，两边结果一致。MoonBit 的 normalize_text 通过同一个 JavaScript 函数实现转小写这一步，使为静态站点编译的 MoonBit 代码与 worker 的规范化方式完全相同。

把版本标记放在 MoonBit 中

runtime_version 为编译后的 JavaScript 模块提供固定标识。静态构建（scripts/build_static_site.mjs）在 next build 之前编译该包，因此破坏该模块的 MoonBit 修改会让静态构建失败。

正确性与不变量

与动态站点的一致性

worker 和服务器使用 lib/query.ts 中相同的函数解码 ast 和 expr，因此一个查询在两种模式下表示同一个公式。项的语义则有意不同：

• 文本项（text、owner、package、keyword、description）在静态站点中是子串测试，所以 pars 也会找到 sparse。服务器则把它们交给 SQLite FTS5，后者匹配词元前缀（pars*）。license 和 repository 在两种模式下都是子串测试。
• 服务器会以 HTTP 400 拒绝运算符与字段不匹配的项（例如 rank>=A）；worker 则照常求值，对标签和数字使用相等比较，对文本使用子串测试。
• 有查询且未显式指定排序时，静态站点按上述协调计数排序。服务器则按分数排列 AST 查询，并用 FTS5 bm25 为旧式文本查询排序。
• updated 在静态站点中按年份排序，在服务器上按完整时间戳排序。
• 静态站点的降序排序中，并列项按名称降序打破；服务器则先按分数降序、再按名称升序打破并列。

复杂度

设 $N$ 为记录数，$L$ 为查询的项叶子数，$\ell$ 为最长规范化字段的长度。一次项测试对数值和标签项的代价为 $O(\ell)$，对子串测试至多为 $O(\ell\,|v|)$。于是

$$\begin{aligned} T_{\text{load}} &= O(\text{size of the JSON}) = O(N F \ell), \\ T_{\text{filter}} &= O(N \cdot L \cdot \ell |v|), \\ T_{\text{sort}} &= O(N \log N) \text{ comparisons}. \end{aligned}$$

对键排序而言，一次比较的代价为 $O(1)$；对相关度排序则为 $O(L \ell |v|)$，因为比较器每次都为两条记录重新计算 $\operatorname{rel}$ 而不缓存。因此相关度排序为 $O(N \log N \cdot L \ell |v|)$，项测试次数比过滤多出 $\log N$ 倍。常驻索引的内存为 $O(N F \ell)$。所有结果都会返回；静态模式没有数量限制。

被否决的方案

• WebAssembly 中的 SQLite 能让静态和动态结果完全一致，但每次访问都要付出大量下载和一个 WebAssembly 运行时的代价。
• 客户端全文检索库（带 tf–idf 或 BM25 的倒排索引）对自由文本的排序会更好，但为保持一致需要一个与 FTS5 分词器一致的分词器，而且会失去子串匹配。
• 按所有者或首字母拆分索引可以减小首次下载量，但会让跨分片的 OR 查询需要获取许多文件。

边界

• 静态搜索不分词、不做词干提取、不按文本统计量排序，也不做拼写纠正。
• 它返回所有匹配项；分页和数量限制留给界面处理。
• MoonBit 包不实现索引或查询求值；它们位于 Python 和 TypeScript 中。
• 在此版本中，worker 并不导入 MoonBit 模块；它的 TypeScript 规范化还会去除查询词的首尾空白，而 normalize_text 不会。
• 数据的新鲜度取决于最近一次导出；没有增量更新。

Footnotes

1. 协调级匹配按文档包含的查询词数量为文档排序；它是最简单的排序检索模型，早于 tf–idf 加权（Salton 与 McGill，Introduction to Modern Information Retrieval，1983）。 ↩