文法に基づくコード

文法ベースコードまたは文法ベース圧縮は、圧縮対象の文字列に対して文脈自由文法（CFG）を構築するという考えに基づいた圧縮アルゴリズムです。例としては、普遍的なロスレスデータ圧縮アルゴリズムが挙げられます。^{[ 1 ]}データシーケンスを圧縮するには${\displaystyle x=x_{1}\cdots x_{n}}$文法に基づくコード変換${\displaystyle x}$文脈自由文法へ${\displaystyle G}$入力シーケンスに対する最小文法を見つける問題（最小文法問題）はNP困難であることが知られており^{[ 2 ]}、そのため理論的および実践的な観点から多くの文法変換アルゴリズムが提案されている。一般に、生成された文法は${\displaystyle G}$算術符号化などの統計的符号化器によってさらに圧縮されます。

文法に基づく符号のクラスは非常に広範です。これには、ブロック符号、マルチレベルパターンマッチング（MPM）アルゴリズム^{[ 3 ]} 、増分構文解析Lempel-Ziv符号のバリエーション^{[ 4 ]}、およびその他多くの新しい普遍的な可逆圧縮アルゴリズムが含まれます。文法に基づく符号は、有限アルファベットを持つ任意の定常的エルゴード的ソースのエントロピー率を漸近的に達成できるという意味で普遍的です。

以下の圧縮プログラムは、外部リンクから入手できます。

• Sequitur ^{[ 5 ]}は、入力テキストを順次 CFG に変換し、生成された CFG を算術コーダーでエンコードする古典的な文法圧縮アルゴリズムです。
• Re-Pair ^{[ 6 ]}は、最も頻繁に出現する要素を優先的に置換する戦略を用いた貪欲アルゴリズムです。圧縮性能は強力ですが、メインメモリの必要容量が非常に大きいという欠点があります。
• GLZA [ ^{7 ]は、繰り返しを含む、つまり還元可能な文法を構築する。}ここで、繰り返しを「明示的に記述する」ためのエントロピー符号化コストは、繰り返しを捉えるルールを作成してエントロピー符号化するコストよりも小さい。（一般に、圧縮最適化SLGは還元不可能ではなく、最小文法問題は実際のSLG圧縮問題とは異なる。）

• 辞書コーダー
• 文法帰納法
• 直線的な文法

• GLZAの議論と論文
• 文法に基づくコードの説明と例
• Sequiturコードは、 2008年10月13日にWayback Machineにアーカイブされました。
• 再ペアリングコード
• Re-Pairはゴンサロ・ナバロのバージョンのコードです。
• GrammarViz 2.0 - Sequitur、Re-Pair、および並列Re-PairのJava実装。