LZW 圧縮テキストに対する 高速文字列照合アルゴリズム 喜田 拓也 竹田 正幸 篠原 歩 九州大学大学院システム情報科学研究科 喜田 拓也 竹田 正幸 篠原 歩 九州大学大学院システム情報科学研究科 九州大学大学院システム情報科学研究科の喜田です。 それでは「LZW圧縮テキストに対する高速文字列照合アルゴリズム」について説明をさせていただきます。

はじめに 文字列照合問題 (Pattern Matching Problem) ヲトコ ヲモイコンダラシレンノミチヲイクガヲトコノ・・・ パターン : ヲトコ テキスト : ヲモイコンダラシレンノミチヲイクガヲトコノ・・・ Knuth-Morris-Pratt 法 (1974) Boyer-Moore 法 (1977) Aho-Corasick 法 (1975) ここでタイトルにある文字列照合問題とは、 このようにパターンとテキストと呼ばれる二つの文字列が与えられたとき、 テキスト中からパターンを発見する問題のことをいいます。 この問題を解くためアルゴリズムは、既に数多く提案されています。 これらはどれもテキストの長さとパターンの長さの和に比例した時間で 問題を解決することができます。 Uratani-Takeda 法 (1992) O( テキストの長さ + パターンの長さ ) ・・・

目的 文書ファイル群 起動実験「やります。 僕が乗ります」「起動確率は0.0000000001%」 セントラルドグマ「初号機、完全に沈黙」せめて、人間らしく「僕はもうエヴァには乗りません」覚醒 強迫観念「ダメなのね・・・もう」シンクロ率400%「逃げちゃだめだ、逃げちゃだめだ・・・」アンビリカルケーブル断線「活動限界まで4分53秒」「私には他に何もないもの・・・」ヤシマ作戦 決戦、第3新東京市「あんたバカァ」セカンドインパクト「私達は選ぶ余裕なんてないのよ。生き残るための手段をね」強羅絶対防衛線 完璧なユニゾン「命令があればそうするわ」自己修復中 ジェリコの壁 人類補完計画「とれないや。血の匂い」「帰れ！」ディラックの海 「駄目です。停止信号受け付けません」「歌はいいねぇ。リリスの生み出した文化 この文字列照合の身近な例は検索です。 つまり大量の文書ファイル、たとえばメールや論文などの中から、 ある単語を含む文書を見つけたい場合、文字列照合を行います。 しかしながらこのような大量の文書は、しばしば、 圧縮して保存することがあります。

目的 圧縮文書ファイル群 aldoghqu3850pcxps;lafdjaeqw09bjzpafq05^@62:vzZIAPF’(90rwDEVcx0832nkvl;pzp99OPF:eDfja この状態では、単純に文字列照合を行うことができません。 一般的に、このような圧縮文書ファイルに対して文字列照合を行う場合、 一旦もとのファイルに展開した後、文字列照合を行うという方法がとられますが、手間がかかります。 そこで何とか圧縮文書ファイルのまま文字列照合を行なおう、 というのが研究の目的です。

Previous studies year researcher compression method 1988 Eliam-Tsoreff and Vishkin run-length 1992 Amir, Landau, and Vishkin two-dimensional 1995 Farach and Thorup LZ77 1996 Amir, Benson and Farach LZW 1997 Karpinski, et al. straight-line programs 1998 Kida, Takeda, Shinohara, Miyazaki, Arikawa Amir and Benson Gasieniec, et al. Miyazaki, Takeda, Shinohara これまでに多くの研究者が、この問題に取り組んできました。 特に自分は、LZW圧縮法と呼ばれる圧縮法で圧縮されたテキストファイル に対する文字列照合問題に取り組みました。 まずは、このLZW圧縮法について簡単に説明します。

Lempel-Ziv-Welch 圧縮法 (Unix の compress コマンド、 GIF形式の画像圧縮など) a b ab ab ba b c aba bc abab テキスト: 圧縮されたテキスト: 1 2 3 4 5 6 9 11 b a c 1 2 3 4 5 6 7 9 8 12 10 11 O(辞書木の大きさ) LZW圧縮法は、UnixのCompressコマンドやGIF形式の画像圧縮などに 利用されている、非常にポピュラーな圧縮法の一つです。 詳細な圧縮の手順は述べませんが、テキストを先頭から読み込んでゆき、 このような辞書木を構築します。 辞書木の各ノードは文字列に対応しており、 テキストの文字列に対応するノードの番号を圧縮テキストとして掃き出します。 たとえば aba だと 6 という具合になります。 圧縮テキストからも同一の辞書木を構築することができます。 その際、テキストを展開する必要がなく、辞書木を構築するだけならば、 圧縮テキストの長さに比例した時間で辞書木を構築することができます。 O( 圧縮テキストの長さ ) 辞書木: D

アルゴリズムの概要 (KMP法による文字列照合の場合) パターン : ヲトコ テキスト : ヲモイコンダラシレンノミチヲイクガヲトコノ・・・ 1 2 3 探索の状態 ヲ ト コ 1. テキストから文字を読み込む。 本題に入ります。 普通のテキストの場合、KMP法で文字列照合を場合を例にとると、 このようにテキストから一文字読み込み、パターンと一致していれば状態を 次の段階に遷移させ、違っていたら戻るという処理を繰り返します。 双六と同様最後の状態に到達したらパターンが発見というわけです。 しかしLZW圧縮されたテキストの場合、文字の代わりに整数を読み取ります。 その整数は辞書木に示された文字列に対応しているので、したがって、 その文字列に対応した状態遷移を行なうようにアルゴリズムを拡張します。 2. 状態を更新する。 3. パターンが出現したかどうかを判断する。 4. 「1.」へ戻る。

アルゴリズムの概要 (LZW圧縮されたテキスト上の文字列照合の場合) パターン : ヲトコ テキスト : ヲモイコンダラシレンノミチヲイクガヲトコノ・・・ 1 2 3 探索の状態 ヲ ト コ 1. 圧縮テキストから数字（文字列）を読み込む。 つまり、この例で今状態 １ にあるとき、文字列「トコ」を現す整数を受け取った ならば、状態を 3 に更新するわけです。 文字列照合の流れはこのようになります。 しかしそれだけでは、ひとつ問題が生じます。 2. 辞書木と状態を更新する。 3. パターンが出現したかどうかを判断する。 4. 「1.」へ戻る。

アルゴリズムの概要 (LZW圧縮されたテキスト上の文字列照合の場合) 1 2 3 探索の状態 ヲ ト コ ・・・ ヲト コノドコンジヨウ ・・・ 状態: 2 状態: 0 パターンの出現を検知する関数が必要 Output( 現在の状態, 圧縮テキストの整数一個 ) 今この例で、状態 ２ にあるとき、次に「コ」に対応する整数がきたならば、 パターンが出現したと分かりますが、もし「コノドコンジョウ」に対応する整数が 入力された場合、次の状態は ３ を飛ばして 0 になります。 すなわちこのような飛び飛びの状態遷移では、パターンの出現を見逃して しまう可能性があるわけです。 したがって、状態と整数からパターンの出現を見極める関数を別個に用意 する必要があります。 単純にテーブルを使ってこの関数を表現することもできますが、 定義域が大きいのでテーブルのサイズが問題になります。 今回われわれが提示したアルゴリズムでは辞書木の大きさのオーダーのテーブルを用意することで、この関数を実現することができました。 O(とりうる状態の個数×辞書木の大きさ) O(辞書木の大きさ)

実験の結果 5 10 15 20 25 30 テキストを一時ファイルに展開後検索 CPU time (s) テキストを展開しながら検索 T. Kida, M. Takeda, A Shinohara, M.miyazaki, and S. Arikawa. Multiple pattern matching in LZW compressed text. In J. A. Atorer and M. Cohn eds., Proceedings of Data Compression Conference ’98, pp. 103-112. IEEE Computer Society, March 1998 5 10 15 20 25 30 テキストを一時ファイルに展開後検索 CPU time (s) テキストを展開しながら検索 テキストを展開せずに検索 われわれは、既にこのアプローチが実際的にも有効であることを示しました。 この表はDataCompressionConference９８という学会で発表したときのものです。 このときは Aho-Corasick 照合機械をベースに、圧縮テキスト上の文字列照合 アルゴリズムを構築しました。 今回の論文ではアルゴリズムの更なる高速化を図るために Shift-And 法と 呼ばれる文字列照合の方法をベースにしています。 5 10 15 20 25 Occurrence rate ( % ) (number of pattern occurrences / original text length)

Shift-And 法 (Abrahamson 1987, Wu-Manber 1992) aabac パターン:= マスクビット テキスト:= aabaacaabacab abc a b c 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 この Shift-And 法は比較的新しい文字列照合方法です。 まず、このようにパターン長のビットベクトルで照合の状態を表します。 また使用されている文字について、このようなマスクビットを用意します。 1が立っている個所は、この文字がパターンに現れている位置を示します。 状態遷移についてですが、3列目から4列目への遷移を例にとると、 まずビットベクトルをシフトさせます。一番上には1が入ります。 それからテキストの文字に対応するマスクビットとのアンドをとります。 その答えが次の状態となります。 1が立っているビットは、パターンの何ビット目までテキストと一致しているかを示しています。 したがってこの位置のビットが1であればパターンが発見されたと分かります。 この Shift-And 法は、実際に高速な文字列照合です。 また様々な拡張を比較的施し易いという特徴も持っています。 これをLZW圧縮テキスト上で文字列照合ができるように拡張しました。 その詳細は論文のほうをご覧下さい。 O( テキスト長 ) で照合可能 &

実験の結果（テキスト約 6.5Mb, 圧縮時約 3.4Mb） (Shift-And 法を利用したアルゴリズム) CPU時間(s) パターンの出現回数（出現 / テキスト長） (%) 0.5 1.0 2.0 3.0 1.5 2.5 3.5 4.0 0.000 0.001 0.014 0.066 0.151 0.498 1.460 Kida, et al. 1998 今回のアルゴリズム 実験の結果です。 こちらは前回の Aho-Corasick 法をベースにしたアルゴリズムです。 縦軸が時間で、横軸がパターンの出現回数です。 今回のアルゴリズムが前回より更に高速であることが示されました。 Sun SPARCstation20

まとめ 今後の課題 提案アルゴリズムの計算量 O(圧縮テキストの長さ+パターンの長さ+出現回数) 時間 O( 辞書木の大きさ ) 領域 展開後検索を行うよりも約 1.5 倍高速である。 またAho-Corasick法を利用したアルゴリズムより 1.3 倍高速である。 一般化した文字列照合問題やミスマッチを許した文字列照合も扱うことができる。 近似(文字の挿入・削除・置換を許す)文字列照合への対応 今後の課題 まとめです。 提案アルゴリズムは、展開後検索を行うよりも約 1.5 倍高速で、 Aho-Corasick法を利用した前回のアルゴリズムより 1.3 倍高速です。 また、一般化した文字列照合問題やミスマッチを許した文字列照合も 扱うことができます。 今後の課題は、近似文字列照合への対応です。 近似文字列照合とはパターンとのエディット・ディスタンス（編集距離）が k 以下の文字列を検索することです。 NATTO 1 例: NATO 2 GTO NAGOYA 1 KATO 3

一般化された文字列照合問題 Σ を文字の有限集合, Δ= { X ⊆Σ| X ≠φ} とする。 パターン P = X1 ... Xm (Xi ∈Δ) と テキスト T = T [1 : n] が与えられたとき、 T [ j : j+m-1 ] ⊆ P となるような j を求めよ。 一般化された文字列照合問題とは、 数式を交えて書くとこのようになります。 つまりパターンとしてこのような正規表現に制限を加えたような パターン文字列を照合する問題です。 (a+b)cde(f+g+h)i 例: 092-627-72XX ( X は 0～9 の数字 ) ＊＊えもん ( ＊は任意の文字 )

ミスマッチを許した文字列照合 パターン文字列のうち、 k 個以下の文字が置き換わった文字列もパターンと一致するとみなした検索。 例: Pattern : ムーミン, k = 1 とした場合 正 誤 ミスマッチを許した文字列照合とは、たとえばこの例のように、 パターンと k 個以下の文字が入れ替わった文字列もパターンに含む問題です。 ユーミン ラーメン ノーミン ローソン ムーラン ノーシン