Definition：grammar-based compression
辞書型文法圧縮とは、与えられた文字列 $T \in \Sigma^*$ に対して、その生成を記述する文脈自由文法（特に直線的・一意生成的な文法）$G$ を構成し、$T$ を文法規則の集合として圧縮的に表現する手法である。ここで文法 $G = (V, \Sigma, R, S)$ は、非終端記号集合 $V$、終端記号集合 $\Sigma$、生成規則集合 $R$、開始記号 $S$ から構成され、$G$ がちょうど一つの文字列 $T$ のみを生成することが要求される。
辞書型文法圧縮は、形式言語理論においては「単一文字列生成文法（straight-line program, SLP）」の構築として定式化される。すなわち、文法 $G$ は曖昧性を持たず、以下のような制約を満たす：
\[\forall A \in V,\quad A \rightarrow \alpha,\quad \alpha \in (V \cup \Sigma)^+\]
かつ依存関係は非循環（非終端記号間の依存グラフが有向非巡回グラフ（DAG）をなす）であり、最終的に開始記号 $S$ からただ一つの文字列 $T$ が生成される：
\[L(G) = \{T\}\]
特に、各非終端が高々1つの生成規則を持つような構造は直線的文法（SLP）と呼ばれ、効率的な圧縮と復元を可能にする。標準的なSLPでは各規則の右辺は長さ2（すなわち $A \rightarrow BC$）に制限されるが、より一般の右辺長を許す拡張も研究されている。
辞書型文法圧縮の目的は、元の文字列長 $|T|$ に対して、文法サイズ $|G|$ を最小化することである。ここで文法サイズは通常、生成規則の総長として定義される：
\[|G| = \sum_{(A \rightarrow \alpha) \in R} |\alpha|\]
理想的には、
\[|G| \ll |T|\]
となるような文法を構成する。これは、文字列中の繰り返し構造や自己相似性を抽出し、それを非終端記号として再利用することで達成される。
代表的な構成法としては、頻出部分列や繰り返しパターンを検出し、それを新たな非終端に置換する操作を繰り返す手法がある。これは形式的には以下のような置換操作として表現できる：
\[T = \cdots u \cdots u \cdots \quad \Rightarrow \quad\begin{cases}A \rightarrow u \\T' = \cdots A \cdots A \cdots\end{cases}\]
ここで $u$ は2回以上出現する部分文字列であり、$A$ は新たに導入される非終端記号である。この操作により $|G|$ は $|u| - 1$ だけ削減される（出現回数に比例した削減が得られる場合もある）。
情報理論的には、辞書型文法圧縮は文字列のコルモゴロフ複雑性 $K(T)$ の近似を与える手法と解釈できる。すなわち、$T$ を生成する最短プログラム長に対応する：
\[K(T) = \min_{p:\, U(p)=T} |p|\]
ここで $U$ は万能チューリング機械である。コルモゴロフ複雑性は計算不可能であるため、文法圧縮はその計算可能な上界を与える近似手法として位置づけられる。
辞書型文法 $G$ は、このプログラムの近似表現として機能し、そのサイズ $|G|$ は $K(T)$ の上界を与える：
\[K(T) \le |G| + c\]
ここで $c$ は符号化方式に依存する定数である。また、頻出部分列を非終端として再利用することは、エントロピーの低い構造（冗長性）を明示的に抽出することに対応する。文法圧縮の圧縮率は $k$ 次経験エントロピー $H_k(T)$（$k \ge 0$）と関連づけられており、特にLZ系手法や文法圧縮は $k$ 次エントロピー界を達成可能であることが知られている（Gagie et al.、Navarro et al. らによる研究）。
最適な文法（最小文法問題、Smallest Grammar Problem）の構成はNP困難であることが知られている（Charikar et al., 2005）。そのため実用的には近似アルゴリズムが用いられる。現在知られている最良の近似比は $O(\log(|T| / |G_{\mathrm{opt}}|))$ である。
代表的なアルゴリズムには以下がある：
これらはいずれも、繰り返し構造を効率的に検出し、文法規則として抽出することを基本戦略としている。また、文法圧縮された表現上で直接的に文字列検索やランダムアクセスを行うアルゴリズムも研究されており、圧縮インデックスの基盤技術としても重要である。
minibpeは、辞書型文法圧縮の特殊な場合として理解できる。すなわち、生成規則が常に2項（バイナリ）である制約：
\[A \rightarrow BC \quad (B, C \in V \cup \Sigma)\]
のもとで、最頻出ペアを貪欲に選択するRe-Pair型アルゴリズムと同型である。BPE（Byte Pair Encoding）はもともとSennrich et al.（2016）によって機械翻訳のサブワード分割手法として提案されたが、その本質はRe-Pairと同一のアルゴリズムであり、文法圧縮の一形態として理解される。
したがって、minibpeは一般の文法圧縮の制限付きバージョンであり、構造の単純さと実装容易性の代わりに、最適性は保証されない。また、トークナイゼーションの文脈では圧縮率よりも語彙の意味的一貫性が重視されるため、純粋な文法圧縮とは目的関数が異なる点に注意が必要である。
辞書型文法圧縮の研究は、1970年代から1980年代にかけてのデータ圧縮理論の発展とともに始まった。特にZiv & Lempel（1977, 1978）によるLZ77・LZ78が辞書型圧縮法の基礎を築いた。これらはいずれも文法圧縮の特殊ケースとして統一的に理解できる。
1990年代には、より構造的な圧縮手法として文法圧縮が体系的に研究され、Sequitur（Nevill-Manning & Witten, 1997）やRe-Pair（Larsson & Moffat, 2000）などのアルゴリズムが提案された。2005年にはCharikar et al. により最小文法問題のNP困難性と近似アルゴリズムの理論的解析が与えられた。
その後、自然言語処理分野において、Byte Pair Encodingが Sennrich et al.（2016）によって再発見・応用され、GPTやBERTをはじめとする大規模言語モデルのトークナイゼーション技術として広く普及した。これにより、文法圧縮の思想はデータ圧縮の枠を超え、トークナイゼーション技術として再評価されるに至った。
Input: String $T \in \Sigma^*$, Target grammar size $K$
$\text{Initialize } S \rightarrow T$
$R = \{ S \rightarrow T \}$
$V = \{S\}$
for $k = 1$ to $K$ do
$\text{pairs} = \text{count adjacent pairs in all right-hand sides of } R$
if $\text{pairs} = \emptyset$ then break
$(x, y) = \arg\max_{(a,b)} \text{pairs}(a,b)$ // 最頻出ペアの選択
$\text{Create new nonterminal } A_k$
$V = V \cup \{A_k\}$
$R = R \cup \{ A_k \rightarrow xy \}$
$\text{for each rule } (B \rightarrow \alpha) \in R \text{ do}$
$\alpha = \text{Replace}(\alpha, xy \mapsto A_k)$
end for
end for
Decoding:
$\text{while nonterminals remain in } S \text{ do}$
$\text{replace } A \text{ with its right-hand side using } R$
end while
$\text{return resulting string } T$
Output: Grammar $G = (V, \Sigma, R, S)$ such that $L(G) = \{T\}$
import collections
class DictionaryCompressor:
def __init__(self):
self.rules = {}
self.next_nonterminal_id = 0
self.start_symbol = 'S'
def _generate_nonterminal(self):
nt = f"NT_{self.next_nonterminal_id}"
self.next_nonterminal_id += 1
return nt
def compress(self, text, K):
if not text: return {}, self.start_symbol
initial_rhs = list(text)
self.rules = {self.start_symbol: initial_rhs}
self.next_nonterminal_id = 0
for _ in range(K):
pair_counts = collections.defaultdict(int)
for rhs in self.rules.values():
for i in range(len(rhs) - 1):
pair = (rhs[i], rhs[i+1])
pair_counts[pair] += 1
eligible_pairs = {p: c for p, c in pair_counts.items() if c > 1}
if not eligible_pairs: break
most_frequent_pair = max(eligible_pairs, key=eligible_pairs.get)
x, y = most_frequent_pair
new_nt = self._generate_nonterminal()
self.rules[new_nt] = [x, y]
for nt in list(self.rules.keys()):
if nt == new_nt: continue
rhs = self.rules[nt]
new_rhs = []
i = 0
while i < len(rhs):
if i + 1 < len(rhs) and rhs[i] == x and rhs[i+1] == y:
new_rhs.append(new_nt)
i += 2
else:
new_rhs.append(rhs[i])
i += 1
self.rules[nt] = new_rhs
return self.rules, self.start_symbol
def decompress(self, compressed_rules, start_symbol):
if not compressed_rules or start_symbol not in compressed_rules: return ""
memo = {}
def expand(symbol):
if not symbol.startswith('NT_') and symbol != 'S': return [symbol]
if symbol in memo: return memo[symbol]
res = []
for s in compressed_rules[symbol]:
res.extend(expand(s))
memo[symbol] = res
return res
return "".join(expand(start_symbol))
Mathematics is the language with which God has written the universe.