文法ベースのコード

アメリカ独立宣言の2 番目の文の直線文法(開始記号 ß を使用) 。青い文字はそれぞれ非終端記号を表し、文のgzip圧縮から取得されました。

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

例と特徴

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

実用的なアルゴリズム

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

Sequitur ^[5]は、入力テキストをCFGに順次変換し、生成されたCFGを算術符号化器で符号化する古典的な文法圧縮アルゴリズムである。
Re-Pair ^[6]は、最も頻出するものを優先する戦略を採用した貪欲アルゴリズムです。圧縮性能は強力ですが、メインメモリの必要スペースが非常に大きくなります。
GLZA ^[7]は、簡約可能な、つまり繰り返しを含む可能性のある文法を構築します。この場合、繰り返しを「綴る」エントロピー符号化コストは、繰り返しを捕捉するための規則を作成してエントロピー符号化するコストよりも低くなります。(一般に、圧縮に最適なSLGは簡約可能ではなく、最小文法問題は実際のSLG圧縮問題とは異なります。)

参照

参考文献

^ Kieffer, JC; Yang, E.-H. (2000)、「文法ベースのコード: ユニバーサルロスレスソースコードの新しいクラス」、IEEE Trans. Inf. Theory、46 (3): 737–754、doi :10.1109/18.841160
^ チャリカー、M.リーマン、E.リュー、D.パニグラヒー、R.プラバラカン、M.サハイ、A. Shelat, A. (2005)、「最小の文法問題」、IEEE Trans。情報理論、51 (7): 2554–2576、土井:10.1109/tit.2005.850116、S2CID 6900082
^ Kieffer, JC; Yang, E.-H.; Nelson, G.; Cosman, P. (2000)、「マルチレベルパターンマッチングによるユニバーサルロスレス圧縮」、IEEE Trans. Inf. Theory、46 (4): 1227–1245、doi :10.1109/18.850665、S2CID 8191526
^ Ziv, J.; Lempel, A. (1978)、「可変レートコーディングによる個々のシーケンスの圧縮」、IEEE Trans. Inf. Theory、24 (5): 530–536、doi :10.1109/TIT.1978.1055934、hdl : 10338.dmlcz/142945
^ Nevill-Manning, CG; Witten, IH (1997)、「シーケンスの階層構造の識別：線形時間アルゴリズム」、Journal of Artificial Intelligence Research、7 (4): 67–82、arXiv : cs/9709102、doi :10.1613/jair.374、hdl :10289/1186、S2CID 2957960
^ Larsson, NJ; Moffat, A. (2000)、「オフライン辞書ベース圧縮」(PDF)、IEEE 論文集、88 (11): 1722–1732、doi :10.1109/5.892708
^ Conrad, Kennon J.; Wilson, Paul R. ( 2016). 「文法的な Ziv-Lempel 圧縮: LZ クラスの解凍速度で PPM クラスのテキスト圧縮率を実現する」2016 データ圧縮会議 (DCC)。p. 586。doi : 10.1109 /DCC.2016.119。ISBN 978-1-5090-1853-6. S2CID 3116024。

外部リンク

GLZAの議論と論文
文法ベースのコード例の説明
Sequitur コード 2008-10-13 にWayback Machineでアーカイブ
コードの再ペアリング
Re-Pair は Gonzalo Navarro のバージョンをコーディングします。
GrammarViz 2.0 - Java での Sequitur、Re-Pair、および並列 Re-Pair の実装。

[1] Kieffer, JC; Yang, E.-H. (2000)、「文法ベースのコード: ユニバーサルロスレスソースコードの新しいクラス」、IEEE Trans. Inf. Theory、46 (3): 737–754、doi :10.1109/18.841160

[2] チャリカー、M.リーマン、E.リュー、D.パニグラヒー、R.プラバラカン、M.サハイ、A. Shelat, A. (2005)、「最小の文法問題」、IEEE Trans。情報理論、51 (7): 2554–2576、土井:10.1109/tit.2005.850116、S2CID 6900082

[3] Kieffer, JC; Yang, E.-H.; Nelson, G.; Cosman, P. (2000)、「マルチレベルパターンマッチングによるユニバーサルロスレス圧縮」、IEEE Trans. Inf. Theory、46 (4): 1227–1245、doi :10.1109/18.850665、S2CID 8191526

[4] Ziv, J.; Lempel, A. (1978)、「可変レートコーディングによる個々のシーケンスの圧縮」、IEEE Trans. Inf. Theory、24 (5): 530–536、doi :10.1109/TIT.1978.1055934、hdl : 10338.dmlcz/142945

[5] Nevill-Manning, CG; Witten, IH (1997)、「シーケンスの階層構造の識別：線形時間アルゴリズム」、Journal of Artificial Intelligence Research、7 (4): 67–82、arXiv : cs/9709102、doi :10.1613/jair.374、hdl :10289/1186、S2CID 2957960

[6] Larsson, NJ; Moffat, A. (2000)、「オフライン辞書ベース圧縮」(PDF)、IEEE 論文集、88 (11): 1722–1732、doi :10.1109/5.892708

[7] ^ Conrad, Kennon J.; Wilson, Paul R. ( 2016). 「文法的な Ziv-Lempel 圧縮: LZ クラスの解凍速度で PPM クラスのテキスト圧縮率を実現する」2016 データ圧縮会議 (DCC)。p. 586。doi : 10.1109 /DCC.2016.119。ISBN 978-1-5090-1853-6. S2CID 3116024。

文法ベースのコード

例と特徴

実用的なアルゴリズム

参照

参考文献

外部リンク

関連するトピック

Straight-line grammar

アメリカ独立宣言の2 番目の文の

非終端記号

gzip