---
title: "100件超の用語を正規表現でマッチングしていたら遅くなったのでAho-Corasickに変えた"
description: "Astroのremarkプラグインで実装した用語自動リンク機能を、正規表現ベースからAho-Corasickアルゴリズムに変更した経緯を解説します。なぜ形態素解析を使わなかったのか、日本語と英語の混在テキストでの単語境界の扱いについても紹介します。"
category: "Web"
tags: ["Astro","remark","TypeScript","Aho-Corasick","パフォーマンス"]
publishedAt: "2026-04-17"
lastmod: "2026-07-22"
---

Labee Dev Toolboxの日本語コンテンツでは、DNS・メール認証・SSL/TLSに関する**100件超**の用語集を整備しています。記事中の専門用語を自動で用語集ページへリンクする[remark](https://github.com/remarkjs/remark)プラグインを実装していましたが、用語数が増えるにつれてビルド時間が気になり始め、正規表現ベースから[Aho-Corasick](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm)アルゴリズムに切り替えました。

::card[https://labee.dev/jp/glossary]

## 最初は巨大な正規表現1本で書いていた

当初の実装では、すべてのtriggerパターンを `|` で結合した1本の正規表現を構築していました。

```typescript
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` を走査して、どの名前付きグループがマッチしたかを特定する必要がありました。正規表現が返すのは「何番目の選択肢がマッチしたか」ではなく、名前付きグループの一覧なので、全グループを順に確認する走査が毎回発生します。

```typescript
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](https://taku910.github.io/mecab/)、[kuromoji](https://github.com/atilika/kuromoji)等）を使うべきでは」と思うかもしれません。採用しなかった理由は、この機能の設計思想にあります。

用語集のfrontmatterには `triggers` フィールドがあり、自動リンクの対象パターンをコンテンツ作成者が手動で定義しています。

```yaml
---
title: 'SPF redirect 修飾子（Modifier）'
triggers: ['SPF redirect 修飾子', 'SPF redirect修飾子']
---
```

形態素解析は「文を分割して品詞を判定し、活用形を原形に戻す」ための技術です。一方、この機能が解決したいのは「事前に定義された固定パターンをテキスト中から高速に検出する」ことです。固定パターンのマルチマッチングには、形態素解析よりもAho-Corasickが適しています。

ビルド時の依存も増えません。MeCabは辞書ファイルの配置が必要で、[Cloudflare Workers](https://developers.cloudflare.com/workers/)のCI環境では扱いが面倒です。Aho-CorasickならTypeScriptだけで完結するため、外部バイナリやWasm辞書を持ち込む必要がありません。

## Aho-Corasickへの移行

Aho-Corasickアルゴリズムは、すべてのtriggerパターンからトライ木を構築し、failure linkを計算することで、テキストを1回走査するだけですべてのマッチを検出します。計算量は **O(n + m + z)**（n: テキスト長、m: パターン長の合計、z: マッチ数）です。

![正規表現ではテキストの各文字位置で約200個の選択肢を先頭から順に試し直すため、計算量がO(n×m²)になる。Aho-Corasickはトライ木とfailure linkを先に作っておき、状態遷移だけで左から右へ1回なぞるので、位置の巻き戻しが起きずO(n+m+z)で済む](/images/posts/astro-glossary-autolink/scan-comparison.svg)

failure linkは、現在の状態からマッチが続かなくなったときに「次に試すべき状態」を指すポインタです。具体的には、今までマッチした文字列の接尾辞のうち、トライ木上で最も長くマッチするノードへ遷移します。これにより、テキストの位置を巻き戻すことなく、重複する可能性のあるパターンを漏れなく検出できます。

```typescript
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」にマッチしてはいけませんが、日本語の「ドメインネームシステム」は文中の部分文字列としてマッチして問題ありません。

```typescript
function containsNonAscii(s: string): boolean {
  return /[^\u0000-\u007F]/.test(s)
}
```

ASCII文字のみで構成されるtriggerには `requiresWordBoundary: true` を設定し、マッチ後に前後の文字が英数字でないことを確認します。日本語を含むtriggerは部分文字列マッチです。

「SSL/TLS」と「SSL」が両方triggerに登録されている場合、より長いパターンが優先されます。triggerの登録時に長さ順でソートし、priority値を割り当てています。

## 初出のみリンクする

各用語は文書内で最初に出現した箇所のみリンクします。[Wikipediaの編集方針](https://en.wikipedia.org/wiki/Wikipedia:Manual_of_Style/Linking)や[MDNのスタイルガイド](https://developer.mozilla.org/en-US/docs/MDN/Writing_guidelines/Writing_style_guide)と同じ考え方です。

すべての出現箇所をリンクにすると視覚的なノイズになりますし、スクリーンリーダーが重複リンクを読み上げるアクセシビリティの問題もあります。同一ページ内の重複リンクについて、検索エンジンが最初のアンカーテキストを優先して参照する場合があるとされており、SEO的にも初出リンクで十分です。

用語集ページ自身への自己参照も防止しています。DMARCの用語ページ内で「DMARC」がリンクになるのは不自然です。

## CSSでの視覚的な区別

用語リンクは点線の下線で表示し、通常のリンク（実線）と区別しています。色にはデザイントークンの `--jp-accent` を使い、サイト全体のアクセントカラーと統一しています。ホバーすると `data-short` 属性に格納した `shortDescription` がツールチップとして表示されます。JavaScriptは不要で、CSSの `::after` 疑似要素だけで実現しています。ツールチップは `left: 50%` と `transform: translateX(-50%)` でリンクの中央に配置し、`pointer-events: none` でマウス操作を妨げないようにしています。

```css
.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件超の用語を抱えるビルドでは体感できる差でした。