技術

外字と訓点を compile-time hash で解く

Sakashita Yasunobu

Sakashita Yasunobu

— 3 min read
Share

aozora は青空文庫の外字参照 (※［＃「魚＋師」、第3水準1-94-37］ のような形) を約 14,000 件のテーブルで解決する。このテーブルを runtime の HashMap ではなく phf (perfect hash function) で持ち、コンパイル時に static 配列に焼き込んでいる。この記事はその選択の根拠と、JIS X 0213 → Unicode フォールバックの設計をまとめたもの。

handbook の対応章: Shift_JIS + 外字 resolver。

外字テーブルの形

外字エントリには 3 種類の解決結果があり、それぞれに対応する variant を GaijiEntry に持たせている。

static GAIJI_TABLE: phf::Map<&'static str, GaijiEntry> = phf_map! {
    "1-94-37" => GaijiEntry::JisX0213 { plane: 1, row: 94, cell: 37, codepoint: '⿰魚師' },
    "U+5F85"  => GaijiEntry::Direct   { codepoint: '待' },
    "魚＋師のつくり" => GaijiEntry::Description { fallback: "[魚+師]" },
    // … 約 14,000 件
};

phf は phf_codegen クレートでビルド時に最小完全ハッシュを計算してくれる。実体は static な配列 + ハッシュ関数で、

  • ルックアップは wyhash 1 ラウンド + 配列 1 添字 + strcmp 1 回
  • ベンチハーネス計測で 1 件あたり約 25 ns
  • collision のない perfect hash なので probe ループが無い
  • アロケーションが無い

候補 1: OnceLock<HashMap>

「初回アクセスで HashMap を構築して以降キャッシュする」のは Rust では一般的なパターン。これを 14,000 件の外字テーブルに適用すると、

  • 初回コスト: 14,000 件の HashMap<&str, GaijiEntry> 構築に約 5ms。これは小さい青空文庫作品のパース全体より長い
  • メモリ: load factor 余裕と RawTable メタデータで PHF 比 2–3 倍
  • 同期コスト: OnceLock は初期化後も毎回 atomic load が走る

外字解決は Phase 0 (sanitize) から Phase 1 (scan) の間で大量に呼ばれるホットパスなので、初期化コストもアトミック load も乗せたくない。

候補 2: JSON / TOML 等の外部アセット

「テーブルだけ別ファイルに分離して起動時にロード」も選択肢としてはある。これも採らなかった。

  • Document::new ごとにファイル I/O が走るとパース全体の時間予算を食う
  • 全バインディング (CLI、WASM、FFI、Python wheel) でアセットを別ファイル配布する必要が出てくる
  • リンカが「実際に参照されない外字」を dead code elimination できなくなる

なぜ PHF が向くか

外字テーブルは次の特性を全部満たしている。

  1. 大きい: 14,000 件は線形走査や Eytzinger 二分探索でも無視できない
  2. 静的: 内容はコンパイル時に確定する (青空文庫の仕様スナップショット由来)
  3. 完全に既知: 入力候補が全部書き出せるので、最小完全ハッシュが計算可能

これは PHF が想定している regime そのもの。ビルド時に phf_codegen が約 40 秒かけてハッシュ関数を構築し、生成物は static 配列として .rodata に置かれる。incremental ビルドではキャッシュされるので 2 回目以降は 0 秒。

解決の優先順序

外字参照の解決は 3 段階に分かれている。

pub fn resolve(reference: &str) -> Resolved {
    // 1. 直接 Unicode 指定 (U+XXXX)
    if let Some(c) = parse_unicode_form(reference) {
        return Resolved::Direct(c);
    }

    // 2. JIS X 0213 plane-row-cell triple
    if let Some(triple) = parse_jis_triple(reference) {
        if let Some(c) = JIS_TABLE.get(&triple) {
            return Resolved::Lookup(c);
        }
    }

    // 3. 名前ベースの記述 (curated subset)
    if let Some(fallback) = DESCRIPTION_TABLE.get(reference) {
        return Resolved::Fallback(fallback);
    }

    Resolved::Unknown
}

Direct が最優先なのは、原稿執筆者が明示的に Unicode codepoint を書いた場合に JIS テーブル側の解釈で上書きしてはならないため。Lookup が一般的なケース、Fallback は Unicode に対応する文字が存在しない約 120 字向けの説明文出力 (例: [魚+師])。どれにも当てはまらない参照は Unknown を返し、診断 W0006 が立つ。

アクセント分解 (おまけ)

古い青空文庫作品はアクセント付きラテン文字を ※［＃…］ ではなく独自の ASCII 表記で書いていた時期がある。

M[i!]cher  →  Micher
M[a!]ria   →  Maria
[ae]on     →  Aeon

仕様の全 114 件マッピングは Phase 0 (sanitize) で適用され、Phase 1 のトリガースキャンに到達する時点では Unicode 化済み。こちらはエントリ数が少ないので PHF ではなく Eytzinger 配置の sorted-set を使っている (このサイズ域では Eytzinger の方が PHF よりキャッシュ効率が出る)。

整理

外字テーブルに PHF を選んだ理由は、

  • テーブルが大きく (14,000 件)、静的で、完全に既知
  • ホットパスで呼ばれるので初期化コストやアトミック load を排除したい
  • 全バインディングが追加アセット無しで動く配布形態を保ちたい

ビルド時に 40 秒払うことで、runtime 側はゼロアロケーション・1 ハッシュ・1 strcmp の 25ns ルックアップになる。

実装は aozora-encoding クレートにある。handbook の encoding.md には Shift_JIS の encoding_rs 依存と JIS X 0213 plane-2 patch の話、それから decode chain 全体の図も載っている。

Read more

青空文庫のParser

青空文庫のParser

青空文庫のParserを作ってます。 GitHub - P4suta/aozora: Pure-functional Rust parser for 青空文庫記法 (Aozora Bunko notation): ルビ, 傍点, 縦中横, 外字, 返り点, indent containers, page breaks.Pure-functional Rust parser for 青空文庫記法 (Aozora Bunko notation): ルビ, 傍点, 縦中横, 外字, 返り点, indent containers, page breaks. - P4suta/aozoraGitHubP4suta Rustで作ってますが、配布物はcargoのほかにnpm/pypiでも入手できます Documentation * Playground — try it in

By Sakashita Yasunobu

イケイケなWinスクショアプリを作りました

パソコンのスクショってなんというか、地味というか、撮ってそのままだと何とものっぺりしていますよね。 特にWindowsだとMacっぽい丸っこい感じとかもなく、無骨だなあと。 ということで、それっぽくおしゃれな背景や角丸を付けておしゃれに撮影をしてくれるスクショアプリを作りました。 GitHubで公開しています。 GitHub - P4suta/Snaply: Snaply — a modern, clean-architecture Windows screenshot tool (WinUI 3 / .NET 10)Snaply — a modern, clean-architecture Windows screenshot tool (WinUI 3 / .NET 10) - P4suta/SnaplyGitHubP4suta ウィンドウ・領域選択・スクリーンのキャプチャができます。 タッチスクリーンなどにも対応しているはずです。 撮影をすると、クリップボードにコピーされ、フォルダーへの保存もされます。

By Sakashita Yasunobu
Find My Files

Find My Files

Windowsにおける爆速ファイル検索アプリの定番といえば、Everythingです。 voidtoolswebhost2 その高速さの理由は、NTFSの仕組みをうまく活用していることにあります。Windowsで一般的に使われているNTFSには、ファイル情報を管理するマスターファイルテーブル（MFT）と、ファイルシステムの変更履歴を記録するUSN Journalがあります。Everythingはこれらを利用することで、初回に高速にファイル一覧を構築し、その後はUSN Journalを監視してリアルタイムにインデックスを更新しています。そのため、数百万ファイル規模の環境でも非常に高速な検索を実現しています。 もちろん、単純にファイル名やパスを保持するだけでは、大量のメモリを消費してしまいます。また、数百万件ものファイルから一瞬で目的のものを見つけるためには、メモリ効率の高いデータ構造や高速な検索アルゴリズムなど、さまざまな工夫が必要になります。 このように、Everythingは見た目こそシンプルですが、中身はかなり高度なことをやっているソフトウェアです。 なお、Everyth

By Sakashita Yasunobu