2文字の検索語が静かに0件になる — Expo アプリの日本語検索インデックスを実測で選び直す

bigram 転置索引は、成果よりも荷物のほうが重かった

次に、正攻法とされる転置索引を作ります。正規化済みキーを2文字ずつに割り、gram ごとに文書 ID の集合を持たせる形です。

function buildBigram(items) {
  const idx = Object.create(null);
  for (let i = 0; i < items.length; i++) {
    const k = norm(items[i].title + items[i].tags.join(""));
    for (let j = 0; j + 2 <= k.length; j++) {
      (idx[k.slice(j, j + 2)] ||= []).push(i);
    }
  }
  for (const g in idx) idx[g] = [...new Set(idx[g])];
  return idx;
}
 
function queryBigram(idx, keys, q) {
  const nq = norm(q);
  if (nq.length < 2) return null; // ← ここが後で問題になります
  const grams = [];
  for (let j = 0; j + 2 <= nq.length; j++) grams.push(nq.slice(j, j + 2));
 
  let cand = null;
  for (const g of grams) {
    const posting = idx[g];
    if (!posting) return [];
    if (cand === null) cand = posting;
    else {
      const s = new Set(posting);
      cand = cand.filter((x) => s.has(x));
    }
    if (cand.length === 0) return [];
  }
  // gram の並び順は保証されないので、最後に実文字列で確認する
  return cand.filter((i) => keys[i].includes(nq));
}

検索そのものは確かに速くなりました。20,000件で0.093ms、線形走査の8分の1です。問題はその外側にありました。

索引のサイズが、元のカタログとほぼ同じです。50,000件では97%。つまり検索を速くするために、配布物を約2倍にすることになります。ダウンロードサイズが App Store の表示に出る以上、これは軽い判断ではありません。

そして検証中に、線形走査との結果比較でずれが出ました。

MISMATCH 20000 滝  linear=708件  bigram=0件

nq.length < 2 で早期リターンしている箇所です。1文字のクエリは bigram を1つも作れないため、索引だけでは原理的に引けません。日本語では「猫」「桜」「月」「海」のような1文字が普通に打たれます。索引を入れた時点で、この層が丸ごと落ちていました。

ここまでは、まだ自分の実装の穴です。次が本題でした。

FTS5 の trigram は、2文字以下を例外なしで捨てる

「自前の索引が雑だったのだ」と考えて、SQLite の FTS5 に移しました。Expo なら expo-sqlite で使えますし、CJK に対して trigram トークナイザが用意されています。素性の確かな実装に任せるほうが安全だと考えたわけです。

# 20,000件を trigram トークナイザで格納し、plain テーブルと突き合わせる
c.execute("CREATE VIRTUAL TABLE s USING fts5(id UNINDEXED, k, tokenize='trigram')")
c.executemany("INSERT INTO s VALUES (?,?)", rows)
 
c.execute("CREATE TABLE plain(id TEXT, k TEXT)")
c.executemany("INSERT INTO plain VALUES (?,?)", rows)
 
for q in ["夜景", "猫", "桜", "星空の", "高解像度"]:
    m = c.execute("SELECT count(*) FROM s WHERE k MATCH ?", ('"' + q + '"',)).fetchone()[0]
    l = c.execute("SELECT count(*) FROM plain WHERE k LIKE ?", ('%' + q + '%',)).fetchone()[0]
    print(q, len(q), m, l)

出力です。

例外は投げません。警告も出ません。3文字未満のクエリは、trigram を1つも構成できないため、静かに空集合になります。仕様としては当然の帰結ですが、アプリの画面上では「該当なし」と区別がつきません。ユーザーから見れば「この壁紙アプリには猫がない」のです。

trigram という名前は「3文字単位で索引する」ことしか語っていません。「3文字未満は引けない」は、その裏側にある帰結です。英語で cat を引けば3文字ですから、英語圏の感覚では問題として立ち上がりません。日本語で「猫」は1文字。この非対称が、そのまま落とし穴になっていました。

もう一つ、デバッグ中に時間を溶かした挙動があります。FTS5 の仮想テーブルに対して LIKE を投げると、期待した部分一致になりません。

-- 仮想テーブルに対する LIKE：0 が返る
SELECT count(*) FROM s WHERE k LIKE '%猫%';        -- → 0
 
-- 同じデータを持つ通常テーブルに対する LIKE：正しい
SELECT count(*) FROM plain WHERE k LIKE '%猫%';    -- → 606

「MATCH が駄目なら LIKE でフォールバックすればよい」と考えて仮想テーブルにそのまま投げると、原因の切り分けが一段遠のきます。フォールバック先は、同じ内容を持つ通常テーブルとして別に用意する必要があります。

ハイブリッドにしたら、遅いほうの経路に引きずられた

素直な対処は、クエリ長で経路を分けることです。3文字以上は FTS5、2文字以下は通常テーブルへの LIKE。書いて測りました。

正しさは戻りました。ただ、この表を眺めていて手が止まりました。

同じ20,000件に対する JavaScript の線形走査は0.80msです。ハイブリッドの遅いほうの経路（4.7〜5.3ms）は、その6倍前後かかっています。速いほうの経路ですら、ヒット件数が増えると4.46msまで落ちます。

つまりこの規模では、SQLite を挟んだ全経路が、素朴な線形走査に負けていました。索引の理論上の優位は、20,000件という規模では実測に現れません。現れるどころか、シリアライズとブリッジ越えの固定費のほうが大きいのです。

FTS5 のデータベースファイルは20,000件で3.3MB、50,000件で9.4MBでした。挿入も20,000件で252ms、50,000件で628msかかります。この費用を払って得たものが「線形走査より遅い検索」だったことになります。

判断として整理すると、こうなります。

1. 検索の応答時間が実測でフレーム予算を割っていないなら、索引は入れない
2. 割っているなら、まずキー配列を平坦にする（それだけで1.4倍）
3. それでも割るなら、索引を検討する。ただし配布サイズがおよそ2倍になることを前提に置く
4. 索引を入れるなら、短いクエリの経路を設計の最初に決める。後付けにすると静かな0件が本番へ出る

本当のボトルネックは検索ではなく、起動時の正規化だった

ここまで検索の応答ばかり測ってきましたが、体感を支配していたのは別の場所でした。読み込み時に全件へ norm() を掛けるパスです。

20,000件で39.5ms。検索1回の0.80msに対して、実に49倍です。私は0.8msを0.09msに縮める作業に週末を使い、その手前にある39.5msを見ていませんでした。

しかもこれは JavaScript スレッドを占有します。実機の補正を掛ければ100ms以上、10万件規模なら起動が目に見えて重くなる水準です。

対処は単純でした。正規化をビルド時に済ませ、結果だけを配布します。

// scripts/build-search-keys.mjs — ビルド時に1回だけ走らせる
import fs from "node:fs";
 
const norm = (s) =>
  s
    .normalize("NFKC")
    .toLowerCase()
    .replace(/[ァ-ヶ]/g, (c) => String.fromCharCode(c.charCodeAt(0) - 0x60))
    .replace(/\s+/g, "");
 
const items = JSON.parse(fs.readFileSync("assets/catalog.json", "utf8"));
 
// 改行区切りの単一文字列として出す。id は行番号で対応させる
const keys = items.map((it) => norm(it.title + it.tags.join("")));
if (keys.some((k) => k.includes("\n"))) {
  throw new Error("正規化後のキーに改行が混入しています。区切り文字を見直してください");
}
fs.writeFileSync("assets/search-keys.txt", keys.join("\n"));
console.log(`wrote ${keys.length} keys / ${Buffer.byteLength(keys.join("\n"))} bytes`);

アプリ側は読み込んで split するだけです。

import { Asset } from "expo-asset";
import * as FileSystem from "expo-file-system";
 
let KEYS = null;
 
export async function loadSearchKeys() {
  if (KEYS) return KEYS;
  const asset = Asset.fromModule(require("../assets/search-keys.txt"));
  await asset.downloadAsync();
  const raw = await FileSystem.readAsStringAsync(asset.localUri);
  KEYS = raw.split("\n");
  return KEYS;
}
 
export function searchByKeys(nq) {
  const hits = [];
  for (let i = 0; i < KEYS.length; i++) {
    if (KEYS[i].indexOf(nq) >= 0) hits.push(i);
  }
  return hits;
}

JSON 配列ではなく改行連結にしたのは、実測で速く、かつ小さかったからです。20,000件で JSON.parse が1.6ms・1,118KB に対し、split は1.1ms・1,078KB。100,000件では7.5ms 対 3.9ms と、差が開きます。引用符とカンマの分だけ素直に軽くなる、という納得のいく結果でした。

改行を区切りに使う以上、キーに改行が混入したら全体がずれます。ビルドスクリプト側で必ず弾いてください。私は一度これを省いて、タグに改行が入った1件のせいで以降のインデックスが1つずれる状態を本番に出しました。検索結果の画像が全部となりの壁紙になるという、原因が分かるまで気持ちの悪い不具合でした。

私が最終的に採った構成

現在の壁紙アプリは、次の形に落ち着いています。カタログは約24,000件です。

1. ビルド時に正規化済みキーを生成し、改行連結のテキストとして同梱する
2. 起動時は split のみ。正規化関数はクエリ側でしか呼ばない
3. 検索は平坦な文字列配列に対する indexOf の線形走査。索引は持たない
4. クエリ側も同じ norm() を通す。ここを揃えないと表記ゆれの吸収が片側だけになる
5. 入力は debounce で間引く。走査そのものより、毎キーストロークで走らせることのほうが高くつく

FTS5 は外しました。件数が今の4倍を超え、実測でフレーム予算を割るようになったら戻す予定です。そのときは短いクエリ用の通常テーブルを最初から用意します。

私はこの、依存を1つ減らして手で読める構成を好みます。速さのためではなく、0件が返ってきたときに原因を10行の中から探せるからです。同じカタログを Google Play 側のビルドでも使っていますが、共有しているのは正規化関数とキー生成スクリプトだけで済んでいます。

判断の分かれ目を表にしておきます。手元の環境で測り直したうえで使ってください。

Rork や Expo でこの部分を生成させる場合、「検索機能を付けてください」だけでは、まず英語圏の前提が入ります。私は次のように仕様まで書いて渡すようにしました。

アプリ内検索を実装してください。要件は以下です。

- 検索対象は正規化済みのキー配列（assets/search-keys.txt を改行区切りで読む）
- 正規化: NFKC → 小文字化 → カタカナをひらがなへ → 空白除去。クエリ側にも同じ関数を適用
- 1文字のクエリでも必ず動作すること。n-gram 索引や FTS5 の trigram は使わないでください
- 入力は 200ms の debounce。前回の検索は AbortController 相当で打ち切る
- 0件のときは「該当なし」ではなく、タグ候補を3つ提示する画面にしてください

3行目を明示するようになったのは、今回の一件のあとです。生成されたコードが速いかどうかより、日本語で1文字が引けるかどうかを先に確かめるようになりました。

次の一歩

もし手元のアプリに検索があるなら、まず1文字のクエリを1つ打ってみてください。よく使われる被写体を1つ、ひらがな1文字でも構いません。件数が返ってくるか、0件になるか。それだけで、索引の設計が日本語を想定しているかが分かります。

そのうえで、検索の応答ではなく起動時の準備コストを測ってみてください。私の場合、縮める余地は検索側に0.7ms、起動側に38msありました。時間を使うべき場所は、測るまで分からないものです。

数字はすべて私自身の環境で実際に走らせて取ったものです。桁と比率は参考になるはずですが、絶対値はぜひご自身の端末で確かめてみてください。お読みいただきありがとうございました。