圧縮率に有意性が見られなかった原因の考察

まず，構文木を保持することで圧縮率が悪化した原因としては，構文木にしたことで 文脈から単語そのものの情報が消えてしまったということが挙げられる．

全く文法規則を削除していない図4.1を例に説明すると，動詞が“jumped”のとき，主 語として用いられる名詞は限られ，“fox”や“dog”を主語とする場合はあっても，“pen”を 主語とする場合はほとんどないと考えられる．しかしながら，本手法では「“jumped”は 動詞の過去形の一種」，「その前には名詞節が来る」という出現情報のみで符号化を行って いるため，この結びつきを完全に無視してしまっている．同様のことが主語である“fox”

など他の単語にも言える．

また，本手法では“The quick brown fox”と“The brown fox”は全くの別扱いになる などの点でも，構文木にすることはむしろ効率が悪いと言える．ただし単語のみを符号 化した場合は，文の構造情報が削除されている分，ある程度圧縮率が向上したと考えら れる．

次に7zipのPPMdに圧縮率で大きく差を開けられた原因としては，PPMdのアルゴリ ズムが深く関わっている．PPMdはPPMを改良した圧縮アルゴリズムで，高速化・省メ モリ化を実現している．この副次的な効果として，通常のPPMでは実現が実質不可能 な，32文字までの長い文脈での出現頻度情報を基に符号化が可能となっている．それだ け長い範囲で出現頻度を求めることができるのであれば，前後の単語の繋がりの情報も 符号化に反映できるため，圧縮率が非常に高くなったと考えられる．

120 140 160 180 200 220

1 10 100 1000

圧 縮 後 の サ イ ズ (KB)

規則の最⼩出現回数の閾値 (個)

全体サイズ メインサイズのみ

(a) l =∞でmを変化させたときのメインサイズと合計サイズ比較

120 140 160 180 200 220

1 10 100 1000

圧 縮 後 の サ イ ズ (KB)

規則の最⼩出現回数の閾値 (個)

l=∞

l=2 l=1

(b) lが∞,2,1の場合にmを変化させたときの合計サイズ比較 図 5.4: 自然言語文に対するTreePPMの圧縮サイズ比較

... S S S S S S S S S S S S S S S S ... DT

⊔The JJ

⊔quick JJ

⊔brown NN

⊔fox

⊔

j u

m p

e d

IN

⊔over DT

⊔the JJ

⊔lazy NN

⊔dog . .

図 5.5: 葉までの最小距離1に制約した場合の構文木の例

第 6 ^章 まとめ

 本研究では文脈自由言語の文字列にエラーが含まれる場合でも，構文解析器のアルゴ リズムを修正することにより高速に構文木を生成し，かつ圧縮率の低下を抑えることに 成功した．また，自然言語文に対して構文木を生成する既存研究の成果を利用して，圧 縮率を高めることが可能かどうか検討を行った．

本研究の提案手法では自然言語文に対して圧縮率を向上させることはできなかったが，

圧縮率を向上するための次のアプローチの方向性を示すことができた．

今後の課題としては，品詞以外にも意味による細かい分類を行うことや，隣接してい ないが構文木から関係が深いと考えられる単語同士の関係も文脈に含めることで圧縮率 を向上させることが挙げられる．

また，多くのファイルで実験に使用していたPPMのアルゴリズムよりも7zipなどで 用いられているPPMdの方が高い圧縮率を出していることから，TreePPMにて使用す るPPMのアルゴリズムをPPMdに置き換えた実験を行うことも，今後の課題である．

参考文献

[1] R.D. Cameron. Source encoding using syntactic information source models. In IEEE Transactions on Information Theory ( Volume: 34, Issue: 4, Jul 1988 ), pp.

843–850, 1988.

[2] Cisco. Cisco visual networking index：全世界のモバイルデータトラフィックの予測、

2015 〜 2020 年アップデート, 2016. https://www.cisco.com/web/JP/solution/

isp/ipngn/literature/pdf/white_paper_c11-520862.pdf.

[3] Jay Earley. An efficient context-free parsing algorithm. In Communications of the ACM, pp. 94–102, 1970.

[4] Google. Brotli. https://github.com/google/brotli.

[5] Google. The need for mobile speed — better user experiences, greater publisher rev-enue, 2016. https://storage.googleapis.com/doubleclick-prod/documents/

The_Need_for_Mobile_Speed_-_FINAL.pdf.

[6] The Stanford Natural Language Processing Group. Stanford parser. http://nlp.

stanford.edu/software/lex-parser.html.

[7] Marcus Hutter. 50’000 prize for compressing human knowledge. http://prize.

hutter1.net/.

[8] Timothy Clinton Bell Ian H. Witten, Alistair Moffat. Managing Gigabytes: Com-pressing and Indexing Documents and Images, Second Edition (The Morgan Kauf-mann Series in Multimedia Information and Systems), pp. 51–65. 1999.

[9] En-Hui Yang Jean-Claude Kieffer. Grammar-based codes: a new class of universal lossless source codes. In IEEE Transactions on Information Theory, pp. 737–754, 2000.

[10] Ian H. Witten John Gerald Cleary. Data compression using adaptive coding and partial string matching. In IEEE Transactions on Communications, pp. 396–402, 1984.

[11] G. Nigel N. Martin. Range encoding: An algorithm for removing redundancy from a digitized message. In Video and Data Recording Conference, 1979.

[12] Paul Tarau. Earley parser. http://www.cse.unt.edu/~tarau/teaching/NLP/

Earley%20parser.pdf.

[13] Jorma Tarhio. On compression of parse trees. In String Processing and Information Retrieval, 2001, pp. 205–211, 2001.