ネット時代の情報センス 基礎情報科学のトピックス

はじめに 計算理論概説 情報検索技術 データ圧縮技術 喜田のこれまでの研究 さいごに

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

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

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

アルゴリズムと計算量 計算可能 ⇔ アルゴリズムが存在する P  NP ? 問題 現実的には NP完全問題は効率よく解くことができない 計算可能　⇔　アルゴリズムが存在する 入力長の多項式程度の時間で計算できる　→　P問題 答えが与えられたら，入力長の多項式程度の時間で答えが正しいかどうかを検算できる　→　NP問題 P  NP ? 問題 まだ未解決 真にむずかしい問題 → NP完全問題 NP完全問題が P に含まれるかどうかが鍵 現実的には NP完全問題は効率よく解くことができない 実用的なアルゴリズム 入力長に比例した時間で問題を解けることが望ましい

氾濫する情報の渦から必要な情報をすばやく取り出すには情報検索の技術が不可欠である 情報検索技術 氾濫する情報の渦から必要な情報をすばやく取り出すには情報検索の技術が不可欠である

索引構造 vs 文字列照合 索引構造を用いた検索 namazuとか 文字列照合を用いた検索 テキストデータ 索引構造作成エンジン 索引 項目検索用DB 全文検索用DB 項目検索用 エンジン 全文検索用 検索アプリ 索引構造を用いた検索 文字列照合を用いた検索 namazuとか

文字列照合アルゴリズム 文字列照合問題とは 文字列照合問題を解決するアルゴリズム O( テキストの長さ + パターンの長さ ) Knuth-Morris-Pratt 法 (1974) Boyer-Moore 法 (1977) Bit-parallel手法 (1987) パターン: オトコ テキスト: オモイコンダラシレンノミチヲイクガオトコノ O( テキストの長さ + パターンの長さ )

特殊な文字列照合問題 一般化文字列照合問題 (Generalized Pattern Matching) ミスマッチを許した文字列照合問題 092-627-72XX ( X は 0～9 の数字 ) ＊＊えもん ( ＊は任意の文字 ) ミスマッチを許した文字列照合問題 パターン：ムーミン，誤りは一つまで許す 正：「ユーミン」「ノーミン」「ムーラン」 誤：「ラーメン」「ローソン」「ノーシン」 近似文字列照合問題 NATO NATTO KATO GTO 例: NAGOYA 1 2 3

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

余談：文字コード 文字コード ASCIIコードと ISO646 日本の文字コード Unicode と ISO10646 コンピュータは内部で文字を数値として認識している 例：「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 　　　　　　：「パソコンにおける日本語処理／文字コードハンドブック」川俣晶

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

符号化とデータ圧縮 符号化 データ圧縮 情報（記号列）をデジタル化すること データ中の冗長な情報を取り除くことで，データのサイズを小さくすること データ圧縮＝モデル化＋符号化 「abacabad」を符号化すると何ビット必要？

情報量と効率のよい符号化 情報量 効率のよい符号化 ビット数 = 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符号化（最小冗長符号）

データ圧縮法あれこれ データ圧縮法 データ圧縮プログラム 適応的Huffman符号化 算術符号化 LZ77, LZ78, LZW（辞書ベース圧縮） Burrows Wheeler 変換を用いた圧縮 データ圧縮プログラム compress gzip LHArc bzip2

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

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

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

研究の成果 CPU時間（秒） 1.4 1.2 1.0 0.8 compress(LZW)にKMPを組込み 0.6 0.4 0.2 5 10 AlphaStation XP1000 (Alpha21264: 667MHz) Tru64 UNIX V4.0F Genbank（DNA塩基配列）17.1Mbyte 1.2 1.0 0.8 compress(LZW)にKMPを組込み CPU時間（秒） gunzip(LZ77)にKMPを組込み 0.6 ビットパラレルによる高速化(1999) 提案アルゴリズム(1998) 0.4 0.2 非圧縮テキストをKMPで照合 5 10 15 20 25 30 * compress はUNIXのLZW圧縮の圧縮ツール パタンの長さ * gunzip はUNIXのLZ圧縮の復号ツール

新たな目標 新目標 目標 復号 文字列照合 アルゴリズム 転送 文字列照合 アルゴリズム 転送 転送 圧縮文字列照合 アルゴリズム 二次記憶装置上 テキスト データ 主記憶装置上 文字列照合 アルゴリズム 転送 目標 主記憶装置上 二次記憶装置上 圧縮テキスト 文字列照合 アルゴリズム 復号 転送 主記憶装置上 二次記憶装置上 圧縮テキスト 転送 主記憶装置上 圧縮文字列照合 アルゴリズム

最終的な成果 0.0 0.3 0.4 0.5 0.8 0.1 0.2 0.6 0.7 AlphaStation XP1000 (Alpha21264: 667MHz) Tru64 UNIX V4.0F Medline（英文テキスト） 60.3Mbyte 非圧縮テキストをKMPで照合 CPU時間（秒） 非圧縮テキストをAgrepで照合 BPE圧縮テキストに対する Boyer-Moore型のアルゴリズム を用いた照合（Shibataら[2000]） BPE圧縮テキストに対する照合 * BPEはByte Pair Encoding圧縮法 5 10 15 20 25 30 * KMPはKnuth-Morris-Pratt法 パタンの長さ * AgrepはWu&Manberが開発した検索ツール

余談：論文の衝突 第一次ショック (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 とその家族

さいごに

現在取り組んでいること 半構造化データに対する文字列照合に関する研究 大量のXMLデータに対し，タグ構造を見ながら検索できる． これまでの研究から，データ圧縮を用いて高速化できないか？ 半構造化データを高速に照合できるデータ圧縮法の開発． <RDF:RDF> <RDF:Description RDF:HREF=“基礎情報科学のトピックス.ppt”> <DC:Creator>喜田 拓也</DC:Creator> </RDF:Description> </RDF:RDF>

最近気になる言葉 パターン言語 ヒューメイン・インタフェース ユビキタス・コンピューティング ユニバーサル・デザイン