💻 computer science

Nearly Optimal Internal Dictionary Matching

本論文では、内部辞書照合問題に対して、異なるパターンの出現回数を数えるための初の $\tilde{O}(1)$ 時間の解法を含む、ほぼ最適なクエリおよび前処理時間を実現する $O(n)$ サイズのデータ構造である Basic Substring Structure (BASS) を導入する。

原著者： Jingbang Chen, Jiangqi Dai, Qiuyang Mang, Qingyu Shi, Tingqiang Xu

公開日 2026-07-02

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Jingbang Chen, Jiangqi Dai, Qiuyang Mang, Qingyu Shi, Tingqiang Xu

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

想像してみてください。あなたは、膨大な、終わりのない本（これを テキスト T と呼びます）を持っています。その本の中には、特別な単語やフレーズのリスト（辞書 D）が隠されており、それらはすべて本の中に存在しています。

この論文が解決する問題は、「ウォーリーをさがせ！」のようなゲームですが、少しひねりが加えられています。単に特定の単語を一つ見つけたいのではありません。あなたは、本の「どの部分」に対しても質問をしたいのです。例えば：

「ページ50から100までの間に、私の特別な単語は合計で何回出現しますか？」
「そのセクションには、何種類の異なる特別な単語が登場しますか？」
「それらが現れるすべての箇所をリストアップしてください。」

かつて、これらの質問に答えるには、特に辞書が本の中の何千もの小さな断片で構成されている場合、非常に時間がかかったり、膨大なメモリを必要としたりしました。この論文は、これらの質問にほぼ瞬時に答えることができる、極めて効率的な情報の整理方法を導入しています。

大きなアイデア：「基本部分文字列構造」 (BASS)

著者たちは、BASS と呼ばれる新しいツールを構築しました。BASSとは、本のあらゆる可能な断片をマッピングする、巨大で魔法のような 2Dグリッド またはスプレッドシートのようなものです。

グリッド: 行が「単語の開始位置」を表し、列が「単語の終了位置」を表すスプレッドシートを想像してください。このグリッドの各セルには、本の特定のテキストが入っています。
着色: セルに単にテキストを書き込むのではなく、著者たちはセルに「色」を付けました。もしあるテキストの断片があなたの特別な辞書の一部であるなら、そのセルには特別な色が塗られます。
ブロック: ここに魔法のトリックがあります。著者たちは、見た目は異なっていても、実際には同じように振る舞う多くのセルがあることに気づきました。彼らはこれらのセルを、「階段状」の形をした「ブロック」としてグループ化しました。一つの階段状ブロック内のすべてのセルは、同じ「個性」（本の中で全く同じ場所に現れるという性質）を共有しています。

この階段状のブロックへと本を整理することで、コンピュータはすべてのページをチェックする必要がなくなります。単に「階段」を見て、そこで何が起きているかを確認するだけでよいのです。

このツールで何ができるのか？

論文によれば、BASSを用いることで、以下の5種類の質問に対して、これまでにない速さと少ないメモリで答えることができます。

出現回数のカウント (Count): 「私の単語は、このセクションに何回出現しますか？」
- 改善点: 以前はこれには少し時間がかかっていました。今では、ほぼ一瞬です。著者らは、これがこの種の質問において可能な最速のスピードであることを証明しました。
ユニークな単語のカウント (CountDistinct): 「私のリストにある異なる単語は何種類出現しますか？」
- 画期的な進歩: これは難しい問題でした。以前は、推測するか、遅い手法を使う必要がありました。著者らはこれを完全に解決し、素早いセットアップの後、ほぼ瞬時（対数時間）に答えを出せるようにしました。
レポート (Report & ReportDistinct): 「単語がどこにあるのか正確に示してください。」
- 改善点: このツールは、コンピュータがそれらを出力できる最速のスピードで、場所をリストアップします。余計な待ち時間は発生しません。
存在確認 (Exists): 「このセクションに、私のリストにある単語は一つでもありますか？」
- 改善点: これは一瞬で回答されます。

仕組み（比喩による説明）

巨大な倉庫（本）の中で、特定の材料を探しているところを想像してください。

従来の方法: あなたはすべての通路を歩き、すべての棚をチェックし、アイテムを数えなければなりませんでした。もし異なるセクションについて知りたければ、再び倉庫全体を歩き直す必要がありました。
BASSによる方法: 著者たちは、倉庫の マップ を作成しました。
- 彼らは、ある通路には常に同じ配置の箱があることに気づきました。そこで、これらの通路を「スーパー通路（等価クラス／ブロック）」としてグループ化しました。
- 彼らは、これらのスーパー通路を繋ぐ ツリー（家系図のようなもの）を構築しました。ある場所の箱がどこにあるかを知っていれば、そのツリーが、実際にそこまで歩かなくても、関連する他の箱がどこにあるかを教えてくれます。
- また、倉庫を逆方向（通路の端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端からではなく、端から

技術要約：ほぼ最適化された内部辞書照合（Internal Dictionary Matching）

問題定義

本論文は、**内部辞書照合（Internal Dictionary Matching: IDM）**問題を取り扱う。この設定では、線形にソート可能なアルファベット上の長さ $n$ の大きなテキスト $T$ が事前に与えられる。辞書 $D$ は、 $T$ の部分文字列 $d$ 個で構成される。目標は、 $T$ と $D$ を前処理し、任意の $T[l, r]$ 内における $D$ のパターンの出現に関するクエリを効率的に回答することである。

本論文は、以下の5つの特定のクエリタイプに焦点を当てている：

Exists( $l, r$ ): $D$ のパターンが少なくとも1つ $T[l, r]$ 内に出現するかどうかを判定する。
Report( $l, r$ ): $T[l, r]$ 内における $D$ の全パターンのすべての出現を報告する。
ReportDistinct( $l, r$ ): $T[l, r]$ 内に出現する $D$ のすべての異なる（distinct）パターンを報告する。
Count( $l, r$ ): $T[l, r]$ 内におけるすべてのパターンの総出現回数をカウントする。
CountDistinct( $l, r$ ): $T[l, r]$ 内に出現する異なるパターンの数をカウントする。

この問題は、古典的な辞書照合および内部パターン照合（IPM）を一般化したものである。これは特に、「内部」辞書（例：すべての回文、平方、または非原始的部分文字列の辞書など、パターンの総長 $L$ がパターンの数 $d$ よりもはるかに大きい場合）において重要である。なぜなら、解の計算量は $L$ ではなく $n$ と $d$ に依存すべきだからである。

手法：基本部分文字列構造（Basic Substring Structure: BASS）

本論文の核心的な貢献は、**基本部分文字列構造（Basic Substring Structure: BASS）**と名付けられた、新しい $O(n)$ サイズのデータ構造の提案である。BASSは、2次元格子（グリッド）と等価類を用いて $T$ の部分文字列を整理する。

1. 格子と等価類

この構造は、すべての部分文字列 $T[l, r]$ を2次元格子上の点 $(l, r)$ にマッピングする。

等価類: 2つの部分文字列は、その「拡張（extension）」が同一である場合に等価とされる。部分文字列 $t$ の拡張 $ext(t) $とは、$ t $が部分文字列であり、かつ$ |occ(t)| = |occ(s)| $を満たす最長の文字列$ s$ のことである。この概念は、**コンパクト非巡回語グラフ（CDAWG）**のノードに対応する。
ブロック: 格子内において、各等価類は階段状の形状を持つ「ブロック」を形成する。ブロック $B$ は、パラメータである行の範囲 $[left_B, right_B]$ 、上端境界 $top_B$ 、および非減少な下端境界のシーケンス $b_{left_B}, \dots, b_{right_B}$ によって定義される。
性質: 本論文では、同一の等価類内にあるすべてのブロックは（平行移動を除いて）同じ形状を共有することを証明している。さらに、すべての異なるブロックの左端および上端の長さの総和は $O(n)$ である。

2. 木のマッピング

BASSは、ブロック間の関係を定式化するために、2つの修正された接尾辞木（suffix tree）を統合している：

PreTree( $T$ ): $T$ の接尾辞木。列を共有するブロック間の関係（祖先・子孫関係）を捉える。
SufTree( $T$ ): 逆文字列 $rev(T)$ の接尾辞木。行を共有するブロック間の関係を捉える。
これらの木により、構造は格子座標をノードに効率的にマッピングすることができ、部分文字列の等価類とそのブロック内での位置を $O(1)$ 時間で特定することを可能にする。

3. クエリ処理戦略

カウントクエリ: アルゴリズムは、カウント問題を2次元範囲カウント問題へと還元する。ブロックの境界に沿ってパターンの出現の部分和を格納し、静的な2次元範囲カウントデータ構造（ChanとPătraşcuの研究に基づく）を利用することで、クエリ時間を最適化している。
CountDistinct クエリ: これが最も複雑なクエリである。著者らは、この問題を2つの部分に分解している：
1. 全出現回数（ $A_1$ ）から、「キー位置」（ $T[l, r]$ の中で唯一回だけ出現する最短の接尾辞によって決定されるもの）における出現回数を差し引く。
2. 接尾辞のトライ（trie）の構造に基づき、重複してカウントされたパターン（ $A_2$ ）を差し引く。
  これを効率的に処理するため、論文では、クエリ範囲のシフトに伴う出現回数の変化を追跡するために Link-Cut Tree から派生したイベントセットを導入しており、永続データ構造を用いて $A_2$ の計算を可能にしている。

主な結果と貢献

本論文は、5つのクエリタイプすべてに対して、ほぼ最適なクエリ時間および前処理時間を達成するアルゴリズムを提示している。結果は以下にまとめられる（ここで $\tilde{O}$ は対数因子を省略している）：

クエリタイプ	前処理時間	クエリ時間	スペース
Exists	$O(n + d)$	$O(1)$	$O(n + d)$
Report	$O(n + d)$	$O(1 + x)$	$O(n + d)$
Count	$O(n + d\sqrt{\log n})$	$O(\frac{\log n}{\log \log n})$	$O(n + d)$
ReportDistinct	$O(n \log n + d)$	$O(1 + x)$	$O(n + d)$
CountDistinct	$O(n \log^2 n + d\sqrt{\log n})$	$O(\log n)$	$O(n \log^2 n + d)$

注： $x$ は出力の長さを表す。

特筆すべき改善点

CountDistinct: 本論文は、CountDistinct クエリを $\tilde{O}(1)$ 時間（具体的には $O(\log n)$ ）で回答し、 $\tilde{O}(n+d)$ の前処理を行う最初の手法を提供することで、先行研究 [16] の未解決問題を解決した。従来の最良の結果は、 $\tilde{O}(n^2/m + d)$ の前処理を必要とし、 $\tilde{O}(m)$ のクエリ時間を要していた。
Count: クエリ時間が $O(\frac{\log^2 n}{\log \log n})$ から $O(\frac{\log n}{\log \log n})$ に改善された。これは、2次元範囲カウントの低次限界に基づき、 $\tilde{O}(n)$ サイズのデータ構造において最適であると著者らが証明している。
ReportDistinct: クエリ時間が $O(\log n + x)$ から $O(1 + x)$ に改善された。
汎用的な適用可能性: 著者らは、BASSが 範囲最長共通部分文字列（Range Longest Common Substring: RLCS） 問題のような他の内部クエリ問題にも適用可能であることを示しており、従来の $O(\log n)$ クエリ時間を $O(1)$ クエリ時間に改善している。

意義と主張

本論文は、BASSがすべてのタイプの IDM クエリを、ほぼ最適なクエリおよび前処理時間で処理できる最初のデータ構造であると主張している。異なるクエリタイプに対して個別の手法を用いる従来の異なるアプローチとは異なり、BASSは統一されたフレームワークを提供する。

本研究の意義は以下の通りである：

最適性: 動的辞書マッチングの既知の条件付き下界（サブ多項式因子まで）に一致し、Count クエリについては無条件の最適性を証明している。
統一されたフレームワーク: CDAWG の概念と効率的な部分文字列クエリの間の架け橋となる、2次元格子構造へと等価類を整理することに成功した。この接続は、先行文献では十分に探索されていなかった。
大きな辞書の扱い: 計算量がパターンの総長 $L$ ではなくパターンの数 $d$ に依存するソリューションを提供しており、複雑な内部辞書（例：すべての回文や平方）に適している。

著者らは、動的辞書（パターンが追加または削除される設定）において、更新を $\tilde{O}(n^\alpha)$ 時間で処理し、CountDistinct クエリに $\tilde{O}(n^{1-\alpha})$ 時間で回答するアルゴリズムを構築できると述べており、これは当該設定における既知の条件付き下界と一致している。

大きなアイデア： 「基本部分文字列構造」 (BASS)