ネット時代の情報センス基礎情報科学のトピックス 1 はじめに      計算理論概説情報検索技術データ圧縮技術喜田のこれまでの研究さいごに 2 コンピュータができること       きれいに整形した文書をプリンタを使って印字できる 3D CGをグリグリ動かして動画を作ることができる美しい音楽を奏でることができる本を読むことができるメールを遠くの友人に送ることができるある決まった手順にしたがって，計算ができる 3 計算とは？ A. Church and S. C. Kleene λ定義可能 Church の提唱(1936) 「アルゴリズムをもつ関数と帰納的関数とを同一視しよう」 K. Godel 帰納的関数 A. M. Turing 万能Turing機械と計算可能な関数族 4 計算可能性  コンピュータには（原理的に）計算できない問題がある  （プログラムの）停止問題 (1936, Turing) 「あるプログラムがきちんと計算を終了して停止するかどうかを決定するようなプログラムは存在しない」  Postの対応問題 (1946, Post) 「任意に与えた  = x1, x2,・・・, xk,  = y1, y2,・・・, yk,に対して， xi1 xi2・・・ xi k = yi1 y2・・・ yi k となる添え字の列が存在するかどうかを決定する問題は非可解である」 ENIAC(1946) > 世界最初のコンピュータ ABC(1942) > 計算可能性 5 アルゴリズムと計算量  計算可能 ⇔ アルゴリズムが存在する    P  NP ? 問題      入力長の多項式程度の時間で計算できる → P問題答えが与えられたら，入力長の多項式程度の時間で答えが正しいかどうかを検算できる → NP問題まだ未解決真にむずかしい問題 → NP完全問題 NP完全問題が P に含まれるかどうかが鍵現実的には NP完全問題は効率よく解くことができない実用的なアルゴリズム  入力長に比例した時間で問題を解けることが望ましい 6 情報検索技術氾濫する情報の渦から必要な情報をすばやく取り出すには情報検索の技術が不可欠である 7 索引構造 vs 文字列照合索引構造を用いた検索 namazuとか索引構造作成エンジンテキストデータ索引項目検索用DB 索引全文検索用DB エ項ン目ジ検ン索用エ全ン文ジ検ン索用検索アプリ文字列照合を用いた検索テキストデータ全文検索用DB 全項エ文エ目ン検ン検ジジン索ン索用用検索アプリ 8 文字列照合アルゴリズム  文字列照合問題とはパターン: オトコテキスト: オモイコンダラシレンノミチヲイクガオトコノ  文字列照合問題を解決するアルゴリズム    Knuth-Morris-Pratt 法 (1974) Boyer-Moore 法 (1977) Bit-parallel手法 (1987) O( テキストの長さ + パターンの長さ ) 9 特殊な文字列照合問題  一般化文字列照合問題 (Generalized Pattern Matching)    ミスマッチを許した文字列照合問題   092-627-72XX ( X は 0～9 の数字 ) ＊＊えもん ( ＊は任意の文字 ) パターン：ムーミン，誤りは一つまで許す正：「ユーミン」「ノーミン」「ムーラン」誤：「ラーメン」「ローソン」「ノーシン」近似文字列照合問題例: NATO 1 1 NATTO 2 KATO GTO 3 NAGOYA 10 文字列照合の応用   キーワード検索テキスト・データベース処理     データ整形データ・マイニングスペル・チェッカーゲノム情報処理 etc… 11 余談：文字コード  文字コード   ASCIIコードと ISO646    ASCIIは文字コードの基本．1963年に誕生．アメリカの文字コード ISO646は国際規格．ASCIIを基本に各国独自で12文字を変更可能．日本の文字コード    コンピュータは内部で文字を数値として認識している例：「Kyushu」は「4B 79 75 73 68 75」のバイト(byte)列符号化文字集合： JIS X 0208 （94×94文字の表．２バイトで一文字）符号化方法： JIS(ISO-2022-JP), Shift-JIS, EUC Unicode と ISO10646    世界中の文字を一つの文字コードで表現しよう！ Unicode：１６ビットで一文字 ISO10646：３１ビットで一文字 UTF-8：無理やり ASCII の上位互換にしたコード参考文献：「文字コードの世界」安岡孝一，安岡素子，ISBN4-501-53060-X ：「パソコンにおける日本語処理／文字コードハンドブック」川俣晶 12 データ圧縮技術大量のデータを効率よく保存するため，あるいはネットワーク上での転送時間を短縮するためには，データ圧縮技術が不可欠である 13 符号化とデータ圧縮  符号化   情報（記号列）をデジタル化することデータ圧縮   データ中の冗長な情報を取り除くことで，データのサイズを小さくすることデータ圧縮＝モデル化＋符号化  「abacabad」を符号化すると何ビット必要？ 14 情報量と効率のよい符号化  情報量  ビット数 = 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:= 0 10 0 110 0 10 0 111 効率のよい符号化   ベル研のC. ShannonとMITのR. M. Fanoによる符号化よりよい手法：Huffman符号化（最小冗長符号） 15 データ圧縮法あれこれ  データ圧縮法      適応的Huffman符号化算術符号化 LZ77, LZ78, LZW（辞書ベース圧縮） Burrows Wheeler 変換を用いた圧縮データ圧縮プログラム     compress gzip LHArc bzip2 16 喜田のこれまでの研究データ圧縮技術と文字列照合技術の融合 17 研究の目的文書ファイル群起動実験「やります。僕が乗ります」「起動確率は 0.0000000001%」セントラルドグマ「初号機、完全に沈黙」せめて、人間らしく「僕はもうエヴァには乗りません」覚醒強迫観念「ダメなのね・・・もう」シンクロ率400%「逃げちゃだめだ、逃げちゃだめだ・・・」アンビリカルケーブル断線「活動限界まで4分53秒」「私には他に何もないもの・・・」ヤシマ作戦決戦、第3新東京市「あんたバカァ」セカンドインパクト「私達は選ぶ余裕なんてないのよ。生き残るための手段をね」強羅絶対防衛線完璧なユニゾン「命令があればそうするわ」自己修復中ジェリコの壁人類補完計画「とれないや。血の匂い」圧縮文書ファイル群 adoghqu3850pcxps; afdjaeqw09bjzpafq 05z90 rwDEVcx083nk;pzp 99OeDfja 18 圧縮されたデータに対する文字列照合普通の文字列照合機械展開圧縮テキスト圧縮テキスト原テキスト圧縮テキストに対する文字列照合機械 19 研究の成果 1.4 AlphaStation XP1000 (Alpha21264: 667MHz) Tru64 UNIX V4.0F CPU時間（秒） 1.2 Genbank（DNA塩基配列） 17.1Mbyte 1.0 0.8 compress(LZW)にKMPを組込み gunzip(LZ77)にKMPを組込み 0.6 提案アルゴリズム(1998) 0.4 ビットパラレルによる高速化(1999) 0.2 0 非圧縮テキストをKMPで照合 5 10 15 20 25 パタンの長さ 30 * compress はUNIXのLZW圧縮の圧縮ツール 20 * gunzip はUNIXのLZ圧縮の復号ツール新たな目標新目標テキストデータ転送二次記憶装置上目標文字列照合アルゴリズム主記憶装置上圧縮テキスト復号転送二次記憶装置上文字列照合アルゴリズム主記憶装置上主記憶装置上圧縮テキスト転送二次記憶装置上主記憶装置上圧縮文字列照合アルゴリズム 21 最終的な成果 0.8 AlphaStation XP1000 (Alpha21264: 667MHz) Tru64 UNIX V4.0F CPU時間（秒） 0.7 Medline（英文テキスト） 60.3Mbyte 0.6 0.5 非圧縮テキストをKMPで照合 0.4 BPE圧縮テキストに対する照合 0.3 非圧縮テキストをAgrepで照合 0.2 BPE圧縮テキストに対する Boyer-Moore型のアルゴリズムを用いた照合（Shibataら[2000]） 0.1 0.0 5 10 15 20 25 パタンの長さ 30 * BPEはByte Pair Encoding圧縮法 22 * KMPはKnuth-Morris-Pratt法 * AgrepはWu&Manberが開発した検索ツール余談：論文の衝突  第一次ショック (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 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 とその家族 23 さいごに 24 現在取り組んでいること  半構造化データに対する文字列照合に関する研究    大量のXMLデータに対し，タグ構造を見ながら検索できる．これまでの研究から，データ圧縮を用いて高速化できないか？半構造化データを高速に照合できるデータ圧縮法の開発． <RDF:RDF> <RDF:Description RDF:HREF=“基礎情報科学のトピックス.ppt”> <DC:Creator>喜田拓也</DC:Creator> </RDF:Description> </RDF:RDF> 25 最近気になる言葉     パターン言語ヒューメイン・インタフェースユビキタス・コンピューティングユニバーサル・デザイン 26