Labee Dev Toolboxの日本語コンテンツでは、DNS・メール認証・SSL/TLSに関する100件超の用語集を整備しています。記事中の専門用語を自動で用語集ページへリンクするremarkプラグインを実装していましたが、用語数が増えるにつれてビルド時間が気になり始め、正規表現ベースからAho-Corasickアルゴリズムに切り替えました。
labee.dev用語解説 | Labee Dev Toolboxドメイン管理・メール認証・DNS・SSL に関する用語をわかりやすく解説します。
最初の実装 — 巨大な正規表現
当初の実装では、すべてのtriggerパターンを | で結合した1本の正規表現を構築していました。
function buildRegex(terms: GlossaryTerm[]) {
const parts: string[] = []
const triggerMap = new Map<string, TriggerEntry>()
for (const { trigger, termId } of entries) {
const escaped = escapeRegex(trigger)
const pattern = containsNonAscii(trigger) ? escaped : `\\b${escaped}\\b`
const groupName = `t${parts.length}`
parts.push(`(?<${groupName}>${pattern})`)
triggerMap.set(groupName, { termId, pattern: trigger })
}
return { regex: new RegExp(parts.join('|'), 'g'), triggerMap }
}100件超の用語に対してtriggerは倍近く存在するため、生成される正規表現は (?<t0>\bAPI Gateway\b)|(?<t1>\bSPF\b)|(?<t2>\bDNS\b)|... のような巨大なパターンになります。日本語を含むtriggerには \b を付けず、英語のみのtriggerには単語境界を付ける、という分岐もこの段階で処理していました。
マッチ後は match.groups を走査して、どの名前付きグループがマッチしたかを特定する必要がありました。正規表現が返すのは「何番目の選択肢がマッチしたか」ではなく、名前付きグループの一覧なので、全グループを順に確認する走査が毎回発生します。
for (let match = regex.exec(text); match !== null; match = regex.exec(text)) {
for (const [groupName, value] of Object.entries(match.groups)) {
if (value !== undefined) {
entry = triggerMap.get(groupName)
break
}
}
}何が遅かったのか
正規表現エンジンが exec() を呼ぶと、テキストの現在位置から | で区切られたすべての選択肢を先頭から順番に試行します。最初の選択肢がマッチしなければ2番目、それもダメなら3番目、という流れです。約200個の選択肢があれば、テキストの各文字位置で最大200回の比較が走ることになります。exec() はマッチを1つ見つけると停止しますが、テキスト全体を走査するにはループで何度も exec() を呼ぶ必要があり、その都度同じ試行が繰り返されます。
加えて、英語のtriggerには \b（単語境界）を付けていたため、バックトラッキングが発生するケースがありました。\b はゼロ幅アサーションですが、各選択肢の先頭と末尾で文字クラスの判定を行う分、選択肢数に比例してオーバーヘッドが増えます。マッチのたびに match.groups オブジェクトを生成・走査するコストも積み重なります。名前付きグループが200個あるオブジェクトを毎回生成し、どのグループが undefined でないかを線形探索するのは、マッチ数が多いほど無視できない負荷です。
テキスト長 n、trigger数 m としたとき、計算量は最悪 O(n × m²) です。用語が50件程度のときは気になりませんでしたが、100件超に達したあたりでビルド全体への影響が見えてきました。
なぜ形態素解析を使わなかったのか
「日本語の自動リンクなら形態素解析（MeCab、kuromoji等）を使うべきでは」と思うかもしれません。採用しなかった理由は、この機能の設計思想にあります。
用語集のfrontmatterには triggers フィールドがあり、自動リンクの対象パターンをコンテンツ作成者が手動で定義しています。
---
title: 'SPF redirect 修飾子（Modifier）'
triggers: ['SPF redirect 修飾子', 'SPF redirect修飾子']
---形態素解析は「文を分割して品詞を判定し、活用形を原形に戻す」ための技術です。一方、この機能が解決したいのは「事前に定義された固定パターンをテキスト中から高速に検出する」ことです。固定パターンのマルチマッチングには、形態素解析よりもAho-Corasickが適しています。
ビルド時の依存も増えません。MeCabは辞書ファイルの配置が必要で、Cloudflare WorkersのCI環境では扱いが面倒です。Aho-CorasickならTypeScriptだけで完結するため、外部バイナリやWasm辞書を持ち込む必要がありません。
Aho-Corasickへの移行
Aho-Corasickアルゴリズムは、すべてのtriggerパターンからトライ木を構築し、failure linkを計算することで、テキストを1回走査するだけですべてのマッチを検出します。計算量は O(n + m + z)（n: テキスト長、m: パターン長の合計、z: マッチ数）です。
failure linkは、現在の状態からマッチが続かなくなったときに「次に試すべき状態」を指すポインタです。具体的には、今までマッチした文字列の接尾辞のうち、トライ木上で最も長くマッチするノードへ遷移します。これにより、テキストの位置を巻き戻すことなく、重複する可能性のあるパターンを漏れなく検出できます。
function buildAutomaton(terms: GlossaryTerm[]): Automaton {
// （entries の構築・ソート部分は省略）
const nodes: AutomatonNode[] = [createAutomatonNode()]
// トライ木の構築
for (const [priority, { trigger, termId }] of entries.entries()) {
let state = 0
for (const ch of trigger) {
const nextState = nodes[state].next.get(ch)
if (nextState !== undefined) {
state = nextState
continue
}
const newState = nodes.length
nodes.push(createAutomatonNode())
nodes[state].next.set(ch, newState)
state = newState
}
nodes[state].outputs.push({
termId, pattern: trigger, priority,
requiresWordBoundary: !containsNonAscii(trigger),
})
}
// BFSでfailure linkを計算
const queue: number[] = []
for (const nextState of nodes[0].next.values()) {
queue.push(nextState)
}
for (let i = 0; i < queue.length; i++) {
const state = queue[i]
for (const [ch, nextState] of nodes[state].next) {
queue.push(nextState)
let failState = nodes[state].fail
while (failState !== 0 && !nodes[failState].next.has(ch)) {
failState = nodes[failState].fail
}
const fallback = nodes[failState].next.get(ch)
nodes[nextState].fail = fallback ?? 0
nodes[nextState].outputs.push(...nodes[nodes[nextState].fail].outputs)
}
}
return { nodes }
}トライ木の構築では、既存ノードがあれば get() で取得してそのまま遷移し、なければ新しいノードを末尾に追加してから遷移します。failure linkの計算では、親ノードのfailure linkを辿りながら while ループで遷移先を探し、見つかったノードを fallback として保存します。テキストの走査は状態遷移のみで、バックトラッキングは発生しません。
日本語と英語で異なるマッチング
日本語と英語では単語境界の扱いが異なります。英語の「DNS」が「DNSMASQ」にマッチしてはいけませんが、日本語の「ドメインネームシステム」は文中の部分文字列としてマッチして問題ありません。
function containsNonAscii(s: string): boolean {
return /[^\u0000-\u007F]/.test(s)
}ASCII文字のみで構成されるtriggerには requiresWordBoundary: true を設定し、マッチ後に前後の文字が英数字でないことを確認します。日本語を含むtriggerは部分文字列マッチです。
「SSL/TLS」と「SSL」が両方triggerに登録されている場合、より長いパターンが優先されます。triggerの登録時に長さ順でソートし、priority値を割り当てています。
初出のみリンクする
各用語は文書内で最初に出現した箇所のみリンクします。Wikipediaの編集方針やMDNのスタイルガイドと同じ考え方です。
すべての出現箇所をリンクにすると視覚的なノイズになりますし、スクリーンリーダーが重複リンクを読み上げるアクセシビリティの問題もあります。同一ページ内の重複リンクについて、検索エンジンが最初のアンカーテキストを優先して参照する場合があるとされており、SEO的にも初出リンクで十分です。
用語集ページ自身への自己参照も防止しています。DMARCの用語ページ内で「DMARC」がリンクになるのは不自然です。
CSSでの視覚的な区別
用語リンクは点線の下線で表示し、通常のリンク（実線）と区別しています。色にはデザイントークンの --jp-accent を使い、サイト全体のアクセントカラーと統一しています。ホバーすると data-short 属性に格納した shortDescription がツールチップとして表示されます。JavaScriptは不要で、CSSの ::after 疑似要素だけで実現しています。ツールチップは left: 50% と transform: translateX(-50%) でリンクの中央に配置し、pointer-events: none でマウス操作を妨げないようにしています。
.jp-glossary-link {
color: var(--jp-accent);
text-decoration: underline dotted;
text-decoration-color: var(--jp-accent);
text-underline-offset: 2px;
position: relative;
cursor: pointer;
transition: color var(--jp-duration-base);
}
.jp-glossary-link:hover {
color: var(--jp-accent-hover);
}
.jp-glossary-link:hover::after {
content: attr(data-short);
position: absolute;
left: 50%;
transform: translateX(-50%);
bottom: calc(100% + 6px);
width: max-content;
max-width: 280px;
padding: 6px 10px;
border-radius: var(--jp-radius-md);
background: var(--jp-text);
color: var(--jp-surface);
font-size: var(--jp-text-sm);
line-height: var(--jp-leading-relaxed);
white-space: normal;
pointer-events: none;
z-index: 10;
}正規表現からAho-Corasickへの変更は機能的には同じです。テストケースもそのまま通りました。変わったのは計算量だけですが、100件超の用語を抱えるビルドでは体感できる差でした。