ネット時代の情報センス

(1)

1

ネット時代の情報センス

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

（平成１５年度版）

(http://kushida.cc.kyushu-u.ac.jp/~kida/)

喜田拓也

警視庁創設記念日

(2)

はじめに



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



デジタル・データとは？



データ圧縮技術



情報検索技術



喜田のこれまでの研究



さいごに

(3)

3/33

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



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



3D CG をグリグリ動かして動

画を作ることができる



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



本を読むことができる



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



ある決まった手順にしたがって，計算ができる

こんなことしかできません・・・

計算手順 → アルゴリズム計算手順 → アルゴリズム

(4)

コンピュータの動作

//=====================================

=// Pattern matching program with ACmac hine

//#include "main.h"

//--- -// メインルーチン

//void main(int argc, char *argv[]) { if(argc < 2) {

fputs("Usage: ac pattern1[,pattern 2,..] [text1 text2 ...] \n", stderr);

exit(EXIT_FAILURE);

}

CACmachine ac;

// パターンの分別処理 string patterns(argv[1]);

プログラム

計算手順（アルゴリズム）をコンピュータが分かる形式で書いたもの

プログラムとデータを入力

コンピュータプログラムに従って計算計算結果を表示

(5)

5/33

計算とは？

A. M. Turing

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

λ 定義可能

K. Godel 帰納的関数

Church の提唱 (1936)

「アルゴリズム（計算手順）が

存在する関数と帰納的関数とを

同一視しよう」

(6)

計算可能性



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

 （プログラムの）停止問題 (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) > 計算可能性

いっぱい

（関数）

(7)

7/33

計算量による限界

コンピュータが計算できる問題

NP 問題

答えが与えられとき、それが正しいかどうかは入力長の多項式程度の時間で検算できる

入力長の多項式倍の時間で計算できる

P 問題

それを解決するアルゴリズム（計算手順）がある問題

（整数の素因数分解、カーナビの行き先検索など）

（整数の四則演算、文字列探索など）

(8)

デジタルデータデジタルデータ

「全ての情報（文字、画像、動画、音声）

は数値の集まりである」

村井純（「インターネット：

村井純（「インターネット： SFCSFC （俺たち）が世（俺たち）が世界を創る」）

界を創る」）

(9)

9/33

コンピュータ内部での文字や絵や音声の表現

 コンピュータは ON と OFF （0 と 1 ）の区別しかない

 すべての情報は 0 と 1の列（つまり整数）を使って表現される

この世には不思議なことなど何もないのだよ、関口君

・・・

画像

音楽・音声

文字列

0101110100101010 0101001010100101 0000000111111101 0101010101111011 10000101111010…

2 進表現の単位

1 bit : 0 か1 ひとつ 1 byte: 8bit

16進数は？

(10)

文字列の表現について

 文字コード

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

例：（ASCII コードの場合）「 Kyushu」は「 4B 79 75 73 68 75 」の byte列

 ASCII コードと ISO646

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

 1byte で一つの文字を表す

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

 日本の文字コード

 符号化文字集合： JIS X 0208 　（ 94×94文字の表． 2byteで一文字）

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

 Unicode と ISO10646

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

 Unicode ：2byteで一文字　　 ISO10646 ：4byte で一文字

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

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

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

漢字の種類は約５万漢字の種類

は約５万

西洋文化圏の人にとっては無駄が多い西洋文化圏の

人にとっては無駄が多い

(11)

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

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

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

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

(12)

符号化とデータ圧縮



符号化



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

　→　本質的に無駄な部分が含まれている！



データ圧縮



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



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

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

→ ASCII コードだと 8byte (64bit)

→ 日本語の全角文字だと 16byte (128bit)

→ ISO10646 だと 32byte (256bit)

(13)

13/33

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



情報量



本質的に必要な bit 数 = 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 符号化（最小冗長符号）

全部で 23bit (3byte弱)

(14)

データ圧縮法あれこれ



データ圧縮法



適応的 Huffman 符号化



算術符号化



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



Burrows Wheeler 変換を用いた圧縮



データ圧縮プログラム



compress



gzip



LHArc



bzip2

(15)

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

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

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

あるある

(16)

文字列照合アルゴリズム



文字列照合問題とは



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



Knuth-Morris-Pratt 法 (1974)



Boyer-Moore 法 (1977)



Bit-parallel 手法 (1987)

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

O(

テキストの長さ

+

パターンの長さ

) O(

_{テキストの長さ}

+

_{パターンの長さ}

)

O(

テキストの長さ

×

パターンの長さ

) O(

_{テキストの長さ}

×

_{パターンの長さ}

)

普通に探すと…

速い！

(17)

17/33

文字列照合の応用



キーワード検索



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



データ整形



データ・マイニング



スペル・チェッカー



ゲノム情報処理

　　 etc…

(18)

実際の応用例



富士通株式会社「瞬索」



http://software.fujitsu.com/jp/shunsaku/index.html

テキストデータ

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

索引

項目検索用DB

索引

全文検索用DB

項目検索用エンジン

全文検索用エンジン

検索アプリ検索アプリ

索引構造を用いた検索

テキストデータ

全文検索用DB

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

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

検索アプリ検索アプリ

文字列照合を用いた検索

(19)

19/33

「瞬索」の事例

官民雇用情報検索システム

「しごと情報ネット」

(http://www.job-net.jp/)

大学情報検索システム

「大学入試センターハートシステム」

(http://www.heart.dnc.ac.jp/)

(20)

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

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

(21)

21/33

研究目的

「この世には不思議なことなど何もないのだよ、関口君」京極堂を変わり者の東の横綱とすると、榎木津は西の横綱だ。何だか酷く男が羨ましくなつてしまつた。

「楠本君。せいぜい月の光を浴びるがいいよ」「世界中の不幸と苦悩を纏めて背負ったような顔をして、そんなもの誰だって背負っているぞ！ちっとも偉くない。心の暗闇だか何だか知らないが、心に光度（カンデラ）や照度（ルクス）があるか。明るい暗いで善し悪しが決まるのは電灯くらいだ」「僕が落すのは憑物。犯人（ホシ）

を落すのは警察。原稿を落すのは関口君だ」「あなたが

―蜘蛛だったのですね。」「それが―絡新婦の理ですもの」

「この世には不思議なことなど何もないのだよ、関口君」京極堂を変わり者の東の横綱とすると、榎木津は西の横綱だ。何だか酷く男が羨ましくなつてしまつた。

「楠本君。せいぜい月の光を浴びるがいいよ」「世界中の不幸と苦悩を纏めて背負ったような顔をして、そんなもの誰だって背負っているぞ！ちっとも偉くない。心の暗闇だか何だか知らないが、心に光度（カンデラ）や照度（ルクス）があるか。明るい暗いで善し悪しが決まるのは電灯くらいだ」「僕が落すのは憑物。犯人（ホシ）

を落すのは警察。原稿を落すのは関口君だ」「あなたが

―蜘蛛だったのですね。」「それが―絡新婦の理ですもの」

文書ファイル群

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

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

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

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



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

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

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

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



圧縮文書ファイル群

(22)

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

圧縮テキスト

原テキス

ト

原テキスト

展開

文字列照合機械普通の

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

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

(23)

23/33

「展開しないで」法

「展開してから」法

「展開しながら」法

この問題に対する３つの手法

目標１：　これらより速い！

目標１：　これらより速い！事情により差し替えてます・・・

(24)

研究の成果（その１）

0 0.2 0.4 0.6 0.8 1.0 1.2 1.4

5 10 15 20 25 30

パタンの長さ

C P U 時間

（秒）

compress(LZW)+KMP

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

Genbank （ DNA 塩基配列）

17.1Mbyte

Genbank （ DNA 塩基配列）

17.1Mbyte

T. Kida ら [1998]

gunzip(LZ77)+KMP

ビットパラレルによる高速化 [1999]

「展開しながら」

「展開しながら」法法

「展開しないで」法

(25)

25/33

ディスク容量は十分あるったい！

ディスク容量は

十分あるったい！

(26)

×

容量は十分あるのに、テキストを圧縮して保存しますか？

圧縮文字列照合する理由は？

(27)

27/33

展開時間展開時間

＋

^{原テキスト上}^{原テキスト上}_{の照合時間}_{の照合時間}

＞

^{圧縮テキスト上}^{圧縮テキスト上}_{の照合時間}_{の照合時間}

圧縮文字列照合する理由は？

当初の目標

当初の目標新目標新目標

(28)

研究の（凄い）成果

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

C P U 時間

（秒）

非圧縮テキストを KMP で照合

BPE 圧縮テキストに対する照合 (KMP)

「展開しないで」法

非圧縮テキストを Agrep で照合

BPE 圧縮テキストに対する照合 (BM) Shibata, et al. (2000)

「展開しないで」法

(29)

29/33

余談：論文の衝突



第一次ショック (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 とその家族

(30)

さいごにさいごに

(31)

31/33

現在取り組んでいること



データ圧縮による文字列近似度（編集距離）の計算の高速化

 二つの DNA 配列の近似度をすばやく測ることができる！



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

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

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

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

<作家>

<名前>京極夏彦</名前>

<ジャンル>ミステリー、妖怪</ジャンル>

<著作>

<タイトル>姑獲鳥の夏</タイトル>

<出版年>1994</出版年>

<出版社>講談社ノベルス</出版社>

</著作>

</作家>

<作家>

<名前 >京極夏彦</ 名前>

<ジャンル>ミステリー、妖怪</ジャンル>

<著作 >

<タイトル>姑獲鳥の夏</タイトル >

<出版年>1994</出版年 >

<出版社>講談社ノベルス</ 出版社>

</著作>

</ 作家>

XML データ例

(32)

いま興味のあること etc.



電子図書館

(Digital library)



e ラーニング

(e-Learning)



情報リテラシー

(Information literacy)



ユニバーサル・デザイン

(Universal design)



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

(Humane interface)

ネット時代の情報セン ス