static_search の設計

静的公開モードは、サーバーも SQLite も使わずにアプリケーション全体をファイルとして配信します。このとき検索はブラウザー内で事前計算済みのインデックスに対して動きます。このページではそのインデックスとクエリアルゴリズムを説明し、順位付けの意味とコストを導き、その中での MoonBit の static_search パッケージの役割を説明します。MoonBit の関数は static_search API にあります。

3 つの部品が連携して動きます。

部品	言語	役割
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"、各フィードの件数。
feeds/top.json, feeds/hot.json, feeds/rising.json	3 つのフィード。動的サイトの SQL の並び順で事前計算したもの。
search/search-index.json	検索インデックス: { "items": [...] }。パッケージごとに 1 レコード。
search/packages.json	同じパッケージに表示用のフィールド（キーワード、バージョン数、乗数）を加えたもの。
packages/<owner>--<package>.json	詳細ページのデータ: パッケージ、直近 20 バージョン、被依存パッケージ。

検索インデックスのレコードはフラットなオブジェクトです。パッケージ概要の表示用フィールド（名前、オーナー、説明、バージョン、各カウント、スコアスナップショットのフィールド）に加えて、事前計算した検索キーを持ちます。

キー	値
normalized_owner, normalized_package, normalized_description, normalized_license, normalized_repository	前後の空白を除いて小文字にしたフィールド（欠落時は ""）。
normalized_keywords	各キーワードを、前後の空白を除いて小文字にしたもの。
normalized_full_text	フルネーム、オーナー、パッケージ名、説明、キーワードのうち空でない部分を、1 つの空白で連結したもの。
repository_present, license_present	前後の空白を除いたフィールドが空でないかどうか。
latest_created_at	リリースのタイムスタンプ。先頭 4 文字が年になります。

つまりこのインデックスは順インデックスです。$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)$ が正規化したキーワードの少なくとも 1 つの部分文字列である。
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 で再帰的に評価されます。空でない項を 1 つも含まない AST はすべてのレコードに一致します。

関連度

クエリがあり明示的な並び順の指定がないとき、ワーカーは関連度のカウントで結果を並べます。AST の項の葉の多重集合を $L(\varphi)$ とすると、

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

です。ここで否定は無視されます。NOT の下にある葉は、否定を外した項が一致するときに数えられます。同順位はスコア（降順）、次に full_name（昇順、localeCompare による）で決まります。

ユーザーが目にする結果を説明するので、2 つの帰結を導いておきます。

連言では順序が変わらない。 $\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$ が 0 でなければ $x$、そうでなければ $y$」を表し、降順なら $s = -1$、昇順なら $+1$ です。既定の順序は name が昇順、ほかのキーが降順です。$s$ が式全体に掛かるため、降順の並べ替えでは同順位の名前順も逆になります。フルネームは一意なので同順位は必ず解決され、同じインデックスとクエリからは同じ順序が得られます。

設計上の判断

転置インデックスを作らず順インデックスを走査する

課題。 ブラウザーはデータベースなしで、部分文字列、数値、ブール演算のクエリに答える必要があります。

選択肢。 WebAssembly にコンパイルした SQLite を FTS5 インデックスとともに配布する、エクスポート時に転置インデックス（語 → パッケージ）を作る、レコードの配列を走査する。

採用。 線形走査です。レジストリには数千のパッケージしかないので、1 回のクエリが触れるのは数千の短いレコードで、ワーカーにとっては軽い処理です。部分文字列照合（pars で parser が見つかる）と数値フィルターにはトークナイザーもポスティングリストも不要で、インデックスはエクスポートスクリプトが数行で書けるただの JSON ファイルのままです。WebAssembly のデータベースは訪問のたびに大きなダウンロードを追加します。

検索を Web Worker で実行する

課題。 メインスレッドでインデックス全体を解析して並べ替えると描画が止まります。

採用。 ワーカーは search-index.json を一度だけ読み込み、レコードをメモリに保持します。クエリは id 付きのメッセージで、各応答は同じ id の要求だけを解決するため、同時に出したクエリが混同されることはありません。URL にはマニフェストの generated_at がバージョンパラメーターとして付き、新しいマニフェストが来るとワーカーを終了して再起動するので、古いインデックスが新しいフィードと混ざることはありません。

エクスポート時に一度だけ正規化する

課題。 大文字と小文字を区別しない照合には、両側とも小文字のテキストが必要です。

採用。 Python がエクスポート時にレコードを小文字化し（str.strip().lower()）、ワーカーは検索語だけを小文字化します（trim().toLowerCase()）。どちらも Unicode の既定の大文字小文字マッピングを使うので、通常のパッケージのメタデータでは両者は一致します。MoonBit の normalize_text は同じ JavaScript 関数で小文字化を実装しているので、静的サイト向けにコンパイルした MoonBit コードはワーカーとまったく同じようにテキストを正規化します。

バージョンタグを MoonBit に置く

runtime_version はコンパイル済み JavaScript モジュールに固定の識別子を与えます。静的ビルド（scripts/build_static_site.mjs）は next build の前にこのパッケージをコンパイルするので、モジュールを壊す MoonBit の変更があれば静的ビルドが止まります。

正しさと不変条件

動的サイトとの一致

ワーカーとサーバーは ast と expr を lib/query.ts の同じ関数でデコードするので、クエリはどちらのモードでも同じ論理式を意味します。項の意味は意図的に異なります。

• テキストの項（text、owner、package、keyword、description）は静的サイトでは部分文字列の判定なので、pars で sparse も見つかります。サーバーはこれらを SQLite FTS5 に渡し、FTS5 はトークンの前方一致（pars*）で照合します。license と repository はどちらのモードでも部分文字列の判定です。
• サーバーは演算子がフィールドに合わない項（たとえば rank>=A）を HTTP 400 で拒否しますが、ワーカーはそのまま評価し、ラベルと数値には等価比較、テキストには部分文字列の判定を使います。
• クエリがあり明示的な並び順の指定がないとき、静的サイトは上の協調カウントで並べます。サーバーは AST クエリをスコア順に並べ、従来のテキストクエリは FTS5 の bm25 で順位付けします。
• updated は静的サイトでは年で、サーバーでは完全なタイムスタンプで並べます。
• 静的サイトの降順の並べ替えでは同順位を名前の降順で決めますが、サーバーはスコアの降順、次に名前の昇順で決めます。

計算量

$N$ をレコード数、$L$ をクエリの項の葉の数、$\ell$ を正規化したフィールドの最大長とします。1 回の項の判定にかかるコストは、数値とラベルの項で $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}$$

です。比較 1 回のコストは、キーによる並べ替えでは $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 にあります。
• このリリースではワーカーは MoonBit モジュールをインポートしていません。その TypeScript の正規化は検索語の前後の空白も除去しますが、normalize_text は除去しません。
• データの鮮度は最後のエクスポートの時点までで、差分更新はありません。

Footnotes

1. 協調レベル照合は、文書に含まれるクエリ語の数で文書を順位付けします。最も単純な順位付き検索モデルで、tf–idf による重み付けより前からあります（Salton と McGill、Introduction to Modern Information Retrieval、1983 年）。 ↩