実験準備

英語の実データとして，ニューヨーク・タイムズのホームページより，閲覧数ランキ ング上位10個の記事を選択した．英文のテキストから品詞を得るため，形態素解析ツー

31

図 4.9: 英語の品詞系列の圧縮結果

ルとしてTreeTaggerを利用した[14]．また，日本語の場合には，NHKのホームページ

より，アクセスランキング上位10個の記事を選択した．そして形態素解析ツールには，

MeCabを用いた[9]．MeCabの出力のうち，品詞情報と細分類情報を利用した．

解析結果から得られる品詞系列をレンジコーダ，PPMに入力し符号化を行う．ここで，

どれだけの長さの文脈が寄与するかを見るために，PPMの最大文脈長kは1から5とし た．圧縮結果の比較は，以下の指標を用いる．

サイズ比=圧縮結果のファイルサイズ/品詞数

これは，テキストを構成する全単語の個数を圧縮後のファイルサイズで割ったもので ある．

4.5.2 実験結果

英語の結果を図4.9に，日本語の結果を図4.10に示す．エラーバーは標準偏差を示す．

英語·日本語両方において，最大文脈長に関係なくレンジコーダよりPPMが優れてい た．このことから，品詞の前後関係を利用して文法圧縮を行う利点はあると推測される．

図 4.10: 日本語の品詞系列の圧縮結果

33

第 5 ^章 まとめ

5.1 ^まとめ

 本論文では，PPMに構文解析を導入し，圧縮率の解析を行った．2種類の文法で実 験を行い，文脈によって発生確率を操作することで圧縮率を向上できることを示した．ま た，実データを形態素解析した品詞系列に対して圧縮を行い，日本語·英語において品詞 が文脈に依存していることを確認した．

5.2 今後の課題

今後は，実データに対する圧縮を行い検証を進めていくことが必要となる．自然言語処 理や，DNAの塩基配列に文法圧縮を適用し，有効性を示したい．自然言語などの実デー タでは，文法では記述されていない例外にも対処していくことが必要となる．そのため にも，例外処理を効率よく行うアルゴリズムの考案をが望まれる．

自然言語の前後の品詞に依存関係が見られたため，文脈を利用した文法圧縮の適用を 目指すことになる．ある言語を網羅する構文規則の構築がなされれば，文法を利用した 文脈圧縮により従来手法より高い圧縮率を達成することができるようになるだろう．

参考文献

[1] Timothy C. Bell, John G. Cleary, and Ian H. Witten. Text Compression. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1990.

[2] R.D. Cameron. Source encoding using syntactic information source models. Infor-mation Theory, IEEE Transactions on, Vol. 34, No. 4, pp. 843–850, July 1988.

[3] John G. Cleary, W.J. Teahan, and Ian H. Witten. Unbounded length contexts for ppm. In Data Compression Conference, 1995. DCC ’95. Proceedings, pp. 52–61, Mar 1995.

[4] John G. Cleary and I.H Witten. Data compression using adaptive coding and partial string matching. Communications, IEEE Transactions on, Vol. 32, No. 4, pp. 396–

402, Apr 1984.

[5] R.G. Gallager. Variations on a theme by huffman. Information Theory, IEEE Transactions on, Vol. 24, No. 6, pp. 668–674, Nov 1978.

[6] G.N.N.Martin, editor. Range encoding: an algorithm for removing redundancy from a digitised message. Video & Data Recording Conference, July 1979.

[7] Makoto Hiroi. Lightweight language. http:\\www.geocities.jp\m_hiroi\light\

index.html.

[8] Randford M.Neala & John G.Cleary I.H.Witten. Arithmetic coding for data com-pression. Communication of the ACM, Vol. 30, pp. 520–540, 1987.

[9] T. KUDO. Mecab : Yet another part-of-speech and morphological analyzer.

http://mecab.sourceforge.net/, 2005.

35

[10] Eric Lehman and Abhi Shelat. Approximation algorithms for grammar-based com-pression. In In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algo-rithms, pp. 205–212. ACM/SIAM, 2002.

[11] A. Moffat. Implementing the ppm data compression scheme. Communications, IEEE Transactions on, Vol. 38, No. 11, pp. 1917–1921, Nov 1990.

[12] Richard Clark Pasco. Source Coding Algorithms for Fast Data Compression. PhD thesis, Stanford University, Stanford, CA, USA, 1976.

[13] J. Rissanen and G. G. Langdon. Arithmetic coding. IBM J. Res. Dev., Vol. 23, No. 2, pp. 149–162, March 1979.

[14] Helmut Schmid. Probabilistic part-of-speech tagging using decision trees, 1994.

[15] J. Tarhio. On compression of parse trees. In String Processing and Information Retrieval, 2001. SPIRE 2001. Proceedings.Eighth International Symposium on, pp.

205–211, Nov 2001.

[16] 卓久丸山, 久美子田中（石井）, 正人武市. Ppm法を用いたかな漢字変換の学習モデ ル. 情報処理学会研究報告自然言語処理（NL）, Vol. 2001, No. 112, pp. 9–14, nov 2001.

[17] 亮洋宮木,比呂志坂本. 頻出文字列の近似数え上げに基づく省スペース文法圧縮の改

良(特集知識情報処理技術の最新動向および一般). 人工知能基本問題研究会, Vol. 95,

pp. 33–37, oct 2014.

[18] 裕之穴瀬, 和宏芥子, 崇石田, 茂一平澤. 文脈混合を考慮したppmアルゴリズム(フ レッシュマン, 一般). 電子情報通信学会技術研究報告. IT, 情報理論, Vol. 105, No.

191, pp. 35–40, jul 2005.

[19] 北 研二小田 裕樹. Ppm*言語モデルを用いた日本語単語分割. 情報処理学会論文誌, Vol. 41, No. 3, pp. 689–700, mar 2000.

[20] 幸司前田, 嘉将高畠, 靖生田部井. 文法圧縮を応用したハミング距離の短い文字列 列挙アルゴリズム (特集機械学習/知識発見の最新動向). 人工知能基本問題研究会, Vol. 94, pp. 21–25, jul 2014.

[21] 山崎芳男. 高能率符号化の動向. 日本音響学会誌,第47巻, 1991.