基礎情報科学のトピックス （平成１５年度版） 喜田拓也 (

Presentation on theme: "基礎情報科学のトピックス （平成１５年度版） 喜田拓也 ("— Presentation transcript:

1 基礎情報科学のトピックス （平成１５年度版） 喜田拓也 (http://kushida.cc.kyushu-u.ac.jp/~kida/)
ネット時代の情報センス 基礎情報科学のトピックス （平成１５年度版） 喜田拓也 ( 警視庁創設記念日

2 はじめに コンピュータができること デジタル・データとは？ データ圧縮技術 情報検索技術 喜田のこれまでの研究 さいごに

3 コンピュータができること きれいに整形した文書をプリンタを使って印字できる 3D CGをグリグリ動かして動画を作ることができる
美しい音楽を奏でることができる 本を読むことができる メールを遠くの友人に送ることができる ある決まった手順にしたがって，計算ができる こんなことしかできません・・・ 計算手順 → アルゴリズム

4 コンピュータの動作 コンピュータ プログラム 計算結果を表示 プログラムに従って計算 プログラムと データを入力
//====================================== // Pattern matching program with ACmachine // #include "main.h" // // メインルーチン void main(int argc, char *argv[]) { if(argc < 2) { fputs("Usage: ac pattern1[,pattern2,..] [text1 text2 ...] \n", stderr); exit(EXIT_FAILURE); } CACmachine ac; // パターンの分別処理 string patterns(argv[1]); コンピュータ プログラムに従って計算 プログラムと データを入力 プログラム 計算手順（アルゴリズム）をコンピュータが分かる形式で書いたもの

5 計算とは？ Church の提唱(1936) 「アルゴリズム（計算手順）が 存在する関数と帰納的関数とを 同一視しよう」
A. Church and S. C. Kleene λ定義可能 Church の提唱(1936) 「アルゴリズム（計算手順）が 存在する関数と帰納的関数とを 同一視しよう」 K. Godel 帰納的関数 A. M. Turing 万能Turing機械と 計算可能な関数族

6 計算可能性 コンピュータには（原理的に）計算できない問題がある
いっぱい コンピュータには（原理的に）計算できない問題がある （プログラムの）停止問題 (1936, Turing) 「あるプログラムがきちんと計算を終了して停止するかどうかを決定するようなプログラムは存在しない」 Postの対応問題 (1946, Post) 「任意に与えた  = x1, x2,・・・, xk,  = y1, y2,・・・, yk,に対して， xi1 xi2・・・ xi k = yi1 y2・・・ yi k となる添え字の列が存在するかどうかを決定する問題は非可解である」 （関数） ENIAC(1946) > 世界最初のコンピュータ ABC(1942) > 計算可能性

7 計算量による限界 コンピュータが計算できる問題 NP問題 P問題 それを解決するアルゴリズム（計算手順）がある問題
答えが与えられとき、それが正しいかどうかは入力長の多項式程度の時間で検算できる （整数の素因数分解、カーナビの行き先検索など） P問題 入力長の多項式倍の時間で計算できる （整数の四則演算、文字列探索など）

8 「全ての情報（文字、画像、動画、音声）は数値の集まりである」 村井 純（「インターネット：SFC（俺たち）が世界を創る」）
デジタルデータ 「全ての情報（文字、画像、動画、音声）は数値の集まりである」 村井 純（「インターネット：SFC（俺たち）が世界を創る」）

9 コンピュータ内部での 文字や絵や音声の表現
コンピュータはONとOFF（0と1）の区別しかない すべての情報は 0 と 1の列（つまり整数）を使って表現される 画像 … 音楽・音声 この世には不思議なことなど何もないのだよ、関口君 ・・・ 2進表現の単位 1 bit : 0か1ひとつ 1 byte: 8bit 文字列 16進数は？

10 文字列の表現について 文字コード ASCIIコードと ISO646 日本の文字コード Unicode と ISO10646
コンピュータは内部で文字を数値として認識している 例： （ASCIIコードの場合）「Kyushu」は「4B 」の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 の上位互換にしたコード 漢字の種類は約５万 西洋文化圏の人にとっては無駄が多い 参考文献：「文字コードの世界」安岡孝一，安岡素子，ISBN X 　　　　　　：「パソコンにおける日本語処理／文字コードハンドブック」川俣晶

11 大量のデータを効率よく保存するため，あるいはネットワーク上での転送時間を短縮するためには，データ圧縮技術が不可欠である

12 符号化とデータ圧縮 符号化 データ圧縮 情報（記号列）をデジタル化すること → 本質的に無駄な部分が含まれている！
情報（記号列）をデジタル化すること 　→　本質的に無駄な部分が含まれている！ データ圧縮 データ中の冗長な情報を取り除くことで、データのサイズを小さくすること データ圧縮 ＝ モデル化＋符号化 「abacabad」を符号化すると何ビット必要？ → ASCIIコードだと 8byte (64bit) → 日本語の全角文字だと 16byte (128bit) → ISO10646だと 32byte (256bit)

13 情報量と効率のよい符号化 情報量 効率のよい符号化 本質的に必要なbit数 = log2（出現確率）
「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:= 効率のよい符号化 ベル研の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( テキストの長さ + パターンの長さ ) 速い！

17 文字列照合の応用 キーワード検索 テキスト・データベース処理 データ整形 データ・マイニング スペル・チェッカー ゲノム情報処理 　　etc…

18 実際の応用例 富士通株式会社「瞬索」 http://software.fujitsu.com/jp/shunsaku/index.html
テキストデータ 索引構造作成エンジン 索引 項目検索用DB 全文検索用DB 項目検索用 エンジン 全文検索用 検索アプリ 索引構造を用いた検索 文字列照合を用いた検索

19 「瞬索」の事例 官民雇用情報検索システム 「しごと情報ネット」 (http://www.job-net.jp/)
大学情報検索システム 「大学入試センターハートシステム」 (

20 喜田のこれまでの研究 データ圧縮技術と文字列照合技術の融合

21 研究目的 文書ファイル群 圧縮文書ファイル群
「この世には不思議なことなど何もないのだよ、関口君」 京極堂を変わり者の東の横綱とすると、榎木津は西の横綱だ。何だか酷く男が羨ましくなつてしまつた。 「楠本君。せいぜい月の光を浴びるがいいよ」「世界中の不幸と苦悩を纏めて背負ったような顔をして、そんなもの誰だって背負っているぞ！ちっとも偉くない。心の暗闇だか何だか知らないが、心に光度（カンデラ）や照度（ルクス）があるか。明るい暗いで善し悪しが決まるのは電灯くらいだ」「僕が落すのは憑物。犯人（ホシ）を落すのは警察。原稿を落すのは関口君だ」「あなたが―蜘蛛だったのですね。」「それが―絡新婦の理ですもの」

22 圧縮されたデータに対する文字列照合 原テキスト 展開 圧縮テキスト 圧縮テキスト 普通の 文字列照合機械 圧縮テキストに対する

23 この問題に対する３つの手法 「展開しながら」法 「展開してから」法 「展開しないで」法 目標１： これらより速い！
目標１：　これらより速い！ 「展開しないで」法 事情により差し替えてます・・・

24 研究の成果（その１） CPU時間（秒） 「展開しながら」法 「展開しないで」法 1.4 1.2 1.0 0.8
AlphaStation XP1000 (Alpha21264: 667MHz) Tru64 UNIX V4.0F Genbank（DNA塩基配列）17.1Mbyte 1.2 1.0 0.8 「展開しながら」法 CPU時間（秒） compress(LZW)+KMP 0.6 gunzip(LZ77)+KMP 0.4 「展開しないで」法 0.2 T. Kidaら[1998] ビットパラレルによる高速化[1999] 5 10 15 20 25 30 パタンの長さ

25 ディスク容量は 十分あるったい！ しかし，最近はディスクの値段も安くなってきており， 十分なディスクがあると仮定してください．

26 容量は十分あるのに、テキストを圧縮して保存しますか？
圧縮文字列照合する理由は？ 容量は十分あるのに、テキストを圧縮して保存しますか？ NO! × そのような場合，わざわざテキストを圧縮して保存するでしょうか？ おそらく，みなさんは圧縮しないだろうと思います．

27 圧縮文字列照合する理由は？ YES! ＞ ＋ 当初の目標 新目標 展開時間 原テキスト上 の照合時間 圧縮テキスト上 の照合時間
しかし，もしこのように圧縮テキスト上での照合時間が原テキスト上での照合時間より高速に することができればどうでしょうか？ もし，この目標が達成されれば，おそらくみなさんはテキストを圧縮して保存するようになると思います． なぜなら，圧縮によって文字列処理を高速化できるからです． この目標を目標２と呼びます．

28 研究の（凄い）成果 CPU時間（秒） 「展開しないで」法 「展開しないで」法 0.0 0.3 0.4 0.5 0.8 0.1 0.2 0.6
AlphaStation XP1000 (Alpha21264: 667MHz) Tru64 UNIX V4.0F Medline（英文テキスト） 60.3Mbyte 0.0 0.3 0.4 0.5 0.8 0.1 0.2 0.6 0.7 非圧縮テキストをKMPで照合 BPE圧縮テキストに対する照合(KMP) 「展開しないで」法 CPU時間（秒） 非圧縮テキストをAgrepで照合 BPE圧縮テキストに対する照合(BM) Shibata, et al. (2000) 「展開しないで」法 5 10 15 20 25 30 パタンの長さ

29 余談：論文の衝突 第一次ショック (at CPM’99) 第二次ショック (at CPM2000)
T. Kida, et al., Shift-And Approach to Pattern Matching in LZW Compressed Text G. Navarro and M. Raffinot, A General Practical Approach to Pattern 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 現在取り組んでいること データ圧縮による文字列近似度（編集距離）の計算の高速化 半構造化データに対する文字列照合に関する研究
二つのDNA配列の近似度をすばやく測ることができる！ 半構造化データに対する文字列照合に関する研究 大量のXMLデータに対し，タグ構造を見ながら検索できる． これまでの研究から，データ圧縮を用いて高速化できないか？ 半構造化データを高速に照合できるデータ圧縮法の開発． <作家> <名前>京極夏彦</名前> <ジャンル>ミステリー、妖怪</ジャンル> <著作> <タイトル>姑獲鳥の夏</タイトル> <出版年>1994</出版年> <出版社>講談社ノベルス</出版社> </著作> </作家> XMLデータ例

32 いま興味のあること etc. 電子図書館 (Digital library) eラーニング (e-Learning)
情報リテラシー (Information literacy) ユニバーサル・デザイン (Universal design) ヒューメイン・インタフェース (Humane interface)