講義「情報知識ネットワーク特論」

(1)

講義「情報知識ネットワーク特論」

～情報検索とパターン照合

第6回圧縮テキスト上のパターン照合

情報理工学専攻情報知識ネットワーク研究室喜田拓也

2018/11/22 講義資料

(2)

今日の内容

データ圧縮について本研究の動機と目標

LZW

圧縮テキストに対する照合

Byte Pair Encoding

法

(BPE

法

)

二つのパラダイムシフト

2

(3)

①「展開してから」法

圧縮データをいったん展開してからパターン照合する

②「展開しながら」法

圧縮データを展開しながら，並行してパターン照合を行う

③「展開しないで」法

圧縮データを展開しないで，直接にパターン照合を行う

目標（その１）：圧縮データを展開せずに①や②より速く照合する！

〇〇〇〇マンがとれる策は？

(4)

メモリの小さい端末でも，できるだけ多くのデータを詰め込みたい！

大量のログを小さくして保存し，必要なときに高速に取り出したい！

とにかく検索は高速に行いたいが索引データ構造は作りたくない！

メール

文書ファイルスケジュールメモ

電子書籍・電子辞書データベース

※写真はSHARP SHF33

と

Apple iPhone 6s

・・・

本研究の応用例

(5)

圧縮されたテキストに対する照合の難しさ

ハードディスクやメモリの容量が十分に大きくなってきた今日，

コンピュータを個人的に利用する範疇において「容量を減らすためにテキストデータを圧縮して保存する」ということはほとんどないでしょう． Windowsにはフォルダごとに圧縮をかけて容量を小さくする機能がありますが，私はこの機能を使ったことがありません．画像や音声データのようなマルチメディア・

データならば圧縮して保存するのが当然ですが，テキストデータを圧縮することは百害あって一利なしと思われるでしょう．しかし，例えば大量のログファイルや過去のメールデータ

文書ファイル群圧縮文書ファイル群

011110000111100111111101011010 001010101001111010001011100110 101111011000111011111101001101 011111001101001110011011000001 111110101101011111111100000101

1.

符号語の開始位置がわからない

2.

文字列の表現がユニークでない

(6)

データ圧縮について

可逆圧縮

（

lossless compression

）

非可逆圧縮

（

lossy compression

）

LZ77

Sequitur LZ78

LZW BPE

JPEG

MPEG

MP3

映像や音声の圧縮に用いられる

エントロピー符号

ハフマン符号

算術符号化非ユニバーサル符号

lengthRun-

BWT

ユニバーサル符号

辞書式文法圧縮ソート型

PPM

統計型

※参考文献：Managing Gigabytes: Compressing and Indexing Documents and Images, I. H. Witten, A. Moffat, T. C. Bell, Morgan Kaufmann Pub, 1999.

(7)

a b ab ab ba b c aba bc abab 1 2 4 4 5 2 3 6 9 ¹¹

テキスト

𝑇𝑇:

圧縮テキスト

𝐸𝐸(𝑇𝑇):

LZ78

のバリエーションの一つ

UNIX

の

compress

や

GIF

形式の画像圧縮などに使われている

T. A. Welch: A technique for high performance data compression, IEEE Comput., Vol.17, pp.8-19, 1984.

辞書木に登録されている文字列の集合を

𝐷𝐷

とすると

𝐷𝐷 = {a,b,c,ab,ba,bc,ca, aba,abb,bab,bca, abab}

．

0

1 2 3

a b c

4

b

5

a

9

c

10

a

6

a

7

b

8

b

12

a

11

b ^D_{|𝐷𝐷| =}

^{は適応的に構築される}

_𝑂𝑂(

_{圧縮テキスト長}

₎

0

1 2 3

4 5 9 10

6 7 8 12

11

a b c

b a c a

a b b a

b

辞書木

Lempel-Ziv-Welch (LZW)圧縮法

(8)

復習： Aho-Corasick 照合機械の動作

パターン集合

Π = {aba,ababb,abca,bb}

に対する

AC

照合機械

0

a

1 2 3 4 5

6 7

8 9

b a b b

c a

b b

_{bb}

{abca}

{aba} {ababb,bb}

: goto

関数

: failure

関数

{ } : output

関数

a b a b a b b a

0 1 2 3 4 3 4 5 1

Output

：

aba aba bb

ababb

テキスト：

状態：

Σ ∖{a,b}

(9)

Kida et al .[1998] アルゴリズムのアイデア

LZW圧縮テキスト上で，AC照合機械の動作をシミュレートしたい

1 2 3 4 3 4 5 1

圧縮テキスト：

0

a

1 2 3 4 5

6 7

8 9

b a b b

c a

b b

_{bb}

{abca}

{aba} {ababb,bb}

a b a b a b b a

0 1 2

Output

：

aba aba bb

ababb

テキスト：

状態：

1 2 4 4 5

4 4 1

T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa: Multiple pattern matching in LZW compressed text, Proc. Data Compression Conference, pp. 103-112, IEEE Computer Society, Mar. 1998.

Σ ∖{a,b}

: goto

関数

: failure

関数

{ } : output

関数

(10)

アルゴリズムの核となる二つの関数

このような飛ばし読み遷移をうまくシミュレートできないか？

関数 Jump

𝑞𝑞, 𝑢𝑢

：

文字列

𝑢𝑢

に対応する遷移の連続を

𝑂𝑂(1)

時間で模倣する定義域は

𝑄𝑄 × 𝐷𝐷

AC照合機械の状態を返す関数 Output

𝑞𝑞, 𝑢𝑢

：

状態

𝑞𝑞

に対応する文字列と

𝑢𝑢

を連結した文字列中に現れるパターンの出現位置を

𝑂𝑂(𝑟𝑟)

時間で報告する

定義域は

𝑄𝑄 × 𝐷𝐷

パターンの集合を返す

単純には

𝑂𝑂(𝑚𝑚|𝐷𝐷|)

領域が必要と考えられる

𝑂𝑂(𝑚𝑚² + |𝐷𝐷|)

領域で実現！

単純には

𝑂𝑂(𝑚𝑚|𝐷𝐷|)

領域が必要と考えられる

𝑂𝑂(𝑚𝑚² + |𝐷𝐷|)

領域

で実現！

(11)

関数 Jump の計算量

𝛿𝛿(𝑞𝑞, 𝑢𝑢), 𝛿𝛿(𝜀𝜀, 𝑢𝑢),

uがあるパターンの部分文字列のとき

それ以外のとき

Jump 𝑞𝑞, 𝑢𝑢 =

𝑂𝑂(𝑚𝑚³)

領域

𝑂𝑂(|𝐷𝐷|)

領域

Ancestor 𝑁𝑁₁^′ 𝑞𝑞, 𝑢𝑢^′ , 𝑢𝑢^′

－

𝑢𝑢 , 𝛿𝛿 𝜀𝜀, 𝑢𝑢 ,

𝑢𝑢

があるパターンの部分文字列のときそれ以外のとき

Jump(𝑞𝑞, 𝑢𝑢) =

𝑂𝑂(𝑚𝑚²)

領域

^‡

領域

𝛿𝛿(𝑞𝑞, 𝑢𝑢)

を

AC

照合機械の（拡張された）状態遷移関数

^†

とすると

† つまり

𝛿𝛿(𝑞𝑞,𝑢𝑢)

は，状態

𝑞𝑞

から文字列

𝑢𝑢

を読み込んだとき，

goto

と

failure

で遷移した先の状態を返す関数

‡

𝑢𝑢𝑢

は

𝑃𝑃

に対する

generalized suffix trie

上で，

𝑢𝑢

の先祖で最も近い

explicit

なノードに対応する文字列

(12)

関数 Output の計算量

�𝑢𝑢

：

𝑢𝑢

の接頭辞で，かつパターンの接尾辞である最長の文字列

𝑞𝑞 𝑢𝑢

𝑝𝑝₁

𝑝𝑝₂

�𝑢𝑢 𝑝𝑝₁

𝑝𝑝₂

領域

状態

𝑞𝑞

は，あるパターンの

prefix

に対応することに注意

𝐴𝐴 𝑢𝑢 = 𝑖𝑖, 𝑝𝑝 𝑝𝑝 ∈ Π, �𝑢𝑢 < 𝑖𝑖 < 𝑢𝑢 , 𝑝𝑝 < 𝑖𝑖,

and 𝑢𝑢 𝑖𝑖 − 𝑝𝑝 + 1. . 𝑖𝑖 = 𝑝𝑝}

Output 𝑞𝑞, 𝑢𝑢 = Output 𝑞𝑞, �𝑢𝑢 ∪ 𝐴𝐴(𝑢𝑢)

(13)

Kida, et al .[1998] アルゴリズムの擬似コード

PMonLZW(E(T)=u₁u₂…u_n, Π:

パターン集合

)

1 Construct AC machine and generalized suffix trie for Π;

2 Initialize the dictionary trie for E(T);

3 Preprocess Jump(q,u) and Output(q,u)

for any q and u∈{

あるパターン

π∈Π

の

factor}

4 l ← 0;

5 q ← q₀;

6 for i ← 1…n do

7 for each

〈

d ,π

〉∈

Output(q, u_i) do

8 report pattern π occurs at position l+d;

9 q ← Jump(q, u_i);

10 l ← l + |u_i|;

11 Update the dictionary trie;

/*

ノード

𝑢𝑢_𝑖𝑖+1

に対する文字列が

𝐷𝐷

に登録される

*/

12 Update variables for Jump(q, u_i+1) and Output(q, u_i+1);

/* 𝛿𝛿 𝜀𝜀,𝑢𝑢_𝑖𝑖+1

や

𝐴𝐴 𝑢𝑢_𝑖𝑖+1 ,𝑢𝑢_𝑖𝑖+1^′ , |𝑢𝑢_𝑖𝑖+1|

等が親ノードを用いて計算される

*/

13 end of for 14 end of for

(14)

目標の達成！

0 0.2 0.4 0.6 0.8 1.0 1.2 1.4

5 10 15 20 25 30

パタンの長さ

CPU

時間（秒）

AlphaStation XP1000 (Alpha21264: 667MHz) Tru64 UNIX V4.0F

Genbank

（

DNA

塩基配列）

17.1Mbyte

compress(LZW)+KMP

Kida+[1998]

（

AC

マシン拡張）

gunzip(LZ77)+KMP

Kida+[1999]

（

Shift-And

法の拡張）

「展開しながら」法

「展開しないで」法

(15)

新たな目標

もし・・・

元のテキスト上での照合時間

圧縮テキスト上の照合時間

＞

新たな目標！（目標その2）

容量は十分あるのに，

テキストを圧縮して

保存しますか？

(16)

目標達成への道のりは遠い・・・

0 0.2 0.4 0.6 0.8 1.0 1.2 1.4

5 10 15 20 25 30

パタンの長さ

CPU

時間（秒）

compress(LZW)+KMP

Kida+[1998]

（

AC

マシン拡張）

gunzip(LZ77)+KMP

Kida+[1999]

（

Shift-And

法の拡張）

「展開しながら」法

「展開しないで」法

非圧縮テキストを

KMP

で照合こちらのほうが圧倒的に早い

Genbank

（

DNA

塩基配列）

17.1Mbyte

(17)

Byte Pair Encoding(BPE) 圧縮法

置換後の文字列：

テキスト：

a b a b c d e b d e f a b d e a b c

G G c H b H f G H G c

G I H b H f G H I

G G c d e b d e f G d e G c

G H I

9文字

GH I

a bd e G c

辞書

→

→ 18文字

サイズ：２５６

= 1 byte

分

(18)

目標２の達成

Medline

（英文テキスト）

60.3Mbyte

5 10 15 20 25 30

パタンの長さ

0.0 0.3 0.4 0.5 0.8

0.1 0.2 0.6 0.7

CPU

時間（秒）

非圧縮テキストを

KMP

で照合

BPE

圧縮上での照合（

KMP

拡張）

「展開しないで」法

非圧縮テキストを

Agrep

で照合

BPE

圧縮上での照合（

BM

拡張）

Shibata+[2000]

「展開しないで」法

前の図では一番早かった

(19)

BPE

圧縮テキスト

LZSS

圧縮テキスト

LZW

圧縮テキスト

非圧縮テキスト

LZSS

専用

BPE

専用

LZW

専用

GOAL

GOAL GOAL

1 3 4

2

圧縮率は低い圧縮率はまあまあ圧縮率は高い

でも文字列照合には適している

普通の

GOAL

以上の話をまとめると…

(20)

第１のパラダイムシフト

各データ圧縮法にして

パターン照合アルゴリズムを開発する

データ圧縮法をうまく選べばパターン照合を高速化できる！

パターン照合に適した新しいデータ圧縮法を

開発する！

(21)

パターン照合向けデータ圧縮法

Dense coding系

[ETDC] Nieves R. Brisaboa, Eva Lorenzo Iglesias, Gonzalo Navarro, and Jose R.

Parama: An efficient compression code for text databases, In

ECIR2003

, pp. 468- 481, 2003.

[SCDC] Nieves R. Brisaboa, Antonio Farina, Gonzalo Navarro, and Maria F. Esteller:

(s, c)-dense coding: An optimized compression code for natural language text databases, In

SPIRE2003

, pp. 122-136, 2003.

[FibC] Shmuel Tomi Klein and Miri Kopel Ben-Nissan: Using fibonacci compression codes as alternatives to dense codes, In

DCC2008

, pp. 472-481, 2008.

[SVVC] Nieves R. Brisaboa, Antonio Farina, Juan-Ramon Lopez, Gonzalo Navarro, and Eduardo R. Lopez: A new searchable variable-to-variable compressor, In

DCC2010

, pp. 199-208, 2010.

VF符号系（文法変換による圧縮含む）

[BPEX] Shirou Maruyama, Yohei Tanaka, Hiroshi Sakamoto, and Masayuki Takeda:

Context-sensitive grammar transform: Compression and pattern matching, In

SPIRE2008

, LNCS5280, pp. 27-38, Nov. 2008.

[DynC] Shmuel T. Klein and Dana Shapira: Improved variable-to-fixed length codes, In

SPIRE2008

, pp. 39-50, 2009.

[STVF] Takashi Uemura, Satoshi Yoshida, Takuya Kida, Tatsuya Asai, and Seishi

Okamoto: Training parse trees for efficient VF coding, In

SPIRE2010

, pp. 179-184,

2010.

(22)

第２のパラダイムシフト

保存コストや転送コストを低減するために

データ圧縮技術を用いる

データを圧縮することで

文字列照合を高速化できる！

圧縮技術を応用して

様々な処理の困難さの壁を

打ち破る

(23)

圧縮技術でブレイクスルー

長大な二つの文字列どうしの類似度を《圧縮技術で》高速化する

M. Crochemore, G. M. Landau, and M. Ziv-Ukelson, “A Sub-quadratic Sequence Alignment Algorithm for Unrestricted Cost Matrices”,

Proceeding of 13th

Symposium on Discrete Algorithm

, pp.679-688, 2002

巨大なグラフ構造を《圧縮技術で》オンメモリに載せて処理する中野眞一（群馬大学）「クエリサポート付きグラフ圧縮」

極大平面グラフを

2𝑚𝑚 + 𝑜𝑜(𝑛𝑛)

bitで，かつクエリサポート XMLに対する問い合わせを《圧縮技術で》高速化する

舞田哲哉，坂本比呂志（九州工業大学）

(24)

第６回まとめ

•

データ圧縮されたテキスト上でのパターン照合

目的：圧縮されたテキストデータに対して効率よくパターン照合したい問題：圧縮されたデータは，中身が簡単には分からない

目標

1

：「展開してから照合」よりも高速なパターン照合を行う

• LZW

圧縮テキストに対する照合

KMP(AC)

の遷移を

LZW

上で模倣ビットパラレル手法による高速化

•

圧縮によるパターン照合の高速化という視点

BPE

圧縮：圧縮率は低いが，パターン照合を高速化する

目標

2

：元のテキストに対してパターン照合するよりも高速に照合

•

講義「情報知識ネットワーク特論」