ネット時代の情報センス

(1)

ネット時代の情報センス

基礎情報科学のトピックス

(2)

2

はじめに



計算理論概説



情報検索技術



データ圧縮技術



喜田のこれまでの研究



さいごに

(3)

コンピュータができること



きれいに整形した文書をプリンタを使って印字できる

 3D CG

をグリグリ動かして動

画を作ることができる



美しい音楽を奏でることができる



本を読むことができる



メールを遠くの友人に送ることができる



ある決まった手順にしたがっ

て，計算ができる

(4)

4

計算とは？

A. M. Turing

万能 Turing 機械と計算可能な関数族 A. Church and S. C. Kleene

λ 定義可能

K. Godel 帰納的関数

Church

の提唱

(1936)

「アルゴリズムをもつ関数と

帰納的関数とを同一視しよう」

(5)

5

計算可能性



コンピュータには（原理的に）計算できない問題がある

 （プログラムの）停止問題 (1936, Turing)

「あるプログラムがきちんと計算を終了して停止するかどうかを決定するようなプログラムは存在しない」

 Post の対応問題 (1946, Post)

「任意に与えた  = x1, x2, ・・・ , xk,  = y₁, y2, ・・・ , yk, に対して， x_i1 x_i2・・・ x_{i k}= y_i1 y₂・・・ y_{i k}

となる添え字の列が存在するかどうかを決定する問題は非可解である」

ENIAC(1946) > 世界最初のコンピュータ ABC(1942) > 計算可能性

(6)

6

アルゴリズムと計算量



計算可能　⇔　アルゴリズムが存在する

 入力長の多項式程度の時間で計算できる　→　 P 問題

 答えが与えられたら，入力長の多項式程度の時間で答えが正しいかどうかを検算できる　→　 NP 問題

 P  NP ?

問題

 まだ未解決

 真にむずかしい問題 → NP 完全問題

 NP 完全問題が P に含まれるかどうかが鍵



現実的には

NP

完全問題は効率よく解くことができない



実用的なアルゴリズム

 入力長に比例した時間で問題を解けることが望ましい

(7)

77

情報検索技術情報検索技術

氾濫する情報の渦から必要な情報をすばや

く取り出すには情報検索の技術が不可欠で

あるある

(8)

8

索引構造 vs 文字列照合

テキストデータ

索引構造作成エンジン索引構造作成エンジン

索引

項目検索用DB

索引

全文検索用DB

項目検索用エンジン

全文検索用エンジン

検索アプリ検索アプリ

索引構造を用いた検索

全文検索用DB

項目検索用エンジン全文検索用エン

ジン項目検索用エンジン全文検索用エンジン

検索アプリ検索アプリ

文字列照合を用いた検索

namazu とか

(9)

9

文字列照合アルゴリズム



文字列照合問題とは



文字列照合問題を解決するアルゴリズム



Knuth-Morris-Pratt 法 (1974)



Boyer-Moore 法 (1977)



Bit-parallel 手法 (1987)

テキスト

:

オモイコンダラシレンノミチヲイクガオトコノパターン

:

オトコ

O( _{テキストの長さ} + _{パターンの長さ} )

(10)

10

特殊な文字列照合問題



一般化文字列照合問題

(Generalized Pattern Matchin g)

 092-627-72XX ( X

は

0

～

9

の数字

)



＊＊えもん

(

＊は任意の文字

)



ミスマッチを許した文字列照合問題



パターン：ムーミン，誤りは一つまで許す正：「ユーミン」「ノーミン」「ムーラン」

誤：「ラーメン」「ローソン」「ノーシン」



近似文字列照合問題

NATO NATTO

KATO GTO

例

: ¹

NAGOYA

1

2

3

(11)

文字列照合の応用



キーワード検索



テキスト・データベース処理



データ整形



データ・マイニング



スペル・チェッカー



ゲノム情報処理

　　 etc…

(12)

12

余談：文字コード

 文字コード

 コンピュータは内部で文字を数値として認識している

例：「 Kyushu 」は「 4B 79 75 73 68 75 」のバイト (byte) 列

 ASCII コードと ISO646

 ASCII は文字コードの基本． 1963 年に誕生．アメリカの文字コード

 ISO646 は国際規格． ASCII を基本に各国独自で 12 文字を変更可能．

 日本の文字コード

 符号化文字集合： JIS X 0208 　（ 94×94 文字の表．２バイトで一文字）

 符号化方法： JIS(ISO-2022-JP), Shift-JIS, EUC

 Unicode と ISO10646

 世界中の文字を一つの文字コードで表現しよう！

 Unicode ：１６ビットで一文字　　 ISO10646 ：３１ビットで一文字

 UTF-8 ：無理やり ASCII の上位互換にしたコード

参考文献：「文字コードの世界」安岡孝一，安岡素子， ISBN4-501-53060-X

　　　　　　：「パソコンにおける日本語処理／文字コードハンドブック」川俣晶

(13)

1313

データ圧縮技術データ圧縮技術

大量のデータを効率よく保存するため，ある

いはネットワーク上での転送時間を短縮する

ためには，データ圧縮技術が不可欠である

(14)

14

符号化とデータ圧縮



符号化



情報（記号列）をデジタル化すること



データ圧縮



データ中の冗長な情報を取り除くことで，データのサイズを小さくすること



データ圧縮＝モデル化＋符号化

 「 abacabad 」を符号化すると何ビット必要？

(15)

情報量と効率のよい符号化



情報量



ビット数

= log₂

（出現確率）

 「 abacabad 」を符号化すると何ビット必要？

a: 1/2, b: 1/4, c: 1/8, d: 1/8 だから，

必要なビット数 = 1×4 + 2×2 + 3×1 + 3×1 = 14 ビット a: 0, b: 10, c: 110, d: 111

abacabad:= 0 10 0 110 0 10 0 111



効率のよい符号化



ベル研の

C. Shannon

と

MIT

の

R. M. Fano

による符号化



よりよい手法：

Huffman

符号化（最小冗長符号）

(16)

16

データ圧縮法あれこれ



データ圧縮法



適応的 Huffman 符号化



算術符号化



LZ77, LZ78, LZW （辞書ベース圧縮）



Burrows Wheeler 変換を用いた圧縮



データ圧縮プログラム



compress



gzip



LHArc



bzip2

(17)

1717

喜田のこれまでの研究喜田のこれまでの研究

データ圧縮技術と文字列照合技術の融合

(18)

18

研究の目的

起動実験「やります。僕が乗ります」「起動確率は0.00 00000001%」セントラルドグマ「初号機、完全に沈黙」せめて、人間らしく「僕はもうエヴァには乗りません」覚醒強迫観念「ダメなのね・・・もう」シンクロ率 400%「逃げちゃだめだ、逃げちゃだめだ・・・」アンビリカルケーブル断線「活動限界まで4分53秒」「私には他に何もないもの・・・」ヤシマ作戦決戦、第3新東京市「あんたバカァ」セカンドインパクト「私達は選ぶ余裕なんてないのよ。生き残るための手段をね」強羅絶対防衛線完璧なユニゾン「命令があればそうするわ」自己修復中ジェリコの壁人類補完計画「とれないや。血の匂い」

文書ファイル群





 ’









 ’





圧縮文書ファイル群

(19)

圧縮されたデータに対する文字列照合

圧縮テキスト

原テキス

ト

原テキスト

文字列照合機械普通の

圧縮テキストに対する文字列照合機械

展開

圧縮テキスト圧縮テキスト

(20)

20

研究の成果

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 を組込み AlphaStation XP1000

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

Genbank （ DNA 塩基配列） 17.1Mbyte

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

Genbank （ DNA 塩基配列） 17.1Mbyte

提案アルゴリズム (1998)

gunzip(LZ77) に KMP _を組込み

ビットパラレルによる高速化 (1999) 非圧縮テキストを KMP で照合

* compress はUNIX のLZW 圧縮の圧縮ツール

* gunzip はUNIXのLZ圧縮の復号ツール

(21)

21

新たな目標

文字列照合アルゴリズム文字列照合アルゴリズム

主記憶装置上

文字列照合アルゴリズム文字列照合アルゴリズム

圧縮文字列照合アルゴリズム圧縮文字列照合

アルゴリズム

主記憶装置上

復号

二次記憶装置上

主記憶装置上

転送転送

転送

新目標新目標

圧縮テキスト

目標目標

圧縮テキスト

(22)

22

最終的な成果

Medline （英文テキスト）

60.3Mbyte

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 で照合

非圧縮テキストを Agrep で照合 BPE 圧縮テキストに対する照合

* Agrep はWu&Manberが開発した検索ツール

* KMPは Knuth-Morris-Pratt 法

* BPEは Byte Pair Encoding 圧縮法

BPE 圧縮テキストに対する Boyer-Moore 型のアルゴリズムを用いた照合（ Shibata ら [2000] ）

(23)

23

余談：論文の衝突



第一次ショック (at CPM’99)

 T. Kida, et al., Shift-And Approach to Pattern Matching in LZW Compressed Text

 G. Navarro and M. Raffinot, A General Practical Approach to Pat tern Matching over Ziv-Liempel Compressed Text



第二次ショック (at CPM2000)

 Y. Shibata, et al., A Boyer-Moore type algorithm for compressed pattern matching

 G. Navarro and J. Tarhio, Boyer-Moore string matching over Ziv -Lempel compressed text

G. Navarro とその家族

(24)

2424

さいごにさいごに

(25)

現在取り組んでいること



半構造化データに対する文字列照合に関する研究

 大量の XML データに対し，タグ構造を見ながら検索できる．

 これまでの研究から，データ圧縮を用いて高速化できないか？

 半構造化データを高速に照合できるデータ圧縮法の開発．

<RDF:RDF>

<RDF:Description RDF:HREF=“ 基礎情報科学のトピックス.pp t”>

<DC:Creator> 喜田拓也</DC:Creator>

</RDF:Description>

</RDF:RDF>

<RDF:RDF>

<RDF:Description RDF:HREF=“ 基礎情報科学のトピックス .pp t”>

<DC:Creator> 喜田拓也 </DC:Creator>

</RDF:Description>

</RDF:RDF>

(26)

26

パターン言語



ヒューメイン・インタフェース



ユビキタス・コンピューティング



ネット時代の情報セン ス