情報検索技術のトピックス （平成１6年度版） 喜田拓也 (http://rd.cc.kyushu-u.ac.jp/~kida/) ネット時代の情報センス 情報検索技術のトピックス （平成１6年度版） 喜田拓也 (http://rd.cc.kyushu-u.ac.jp/~kida/) 横山光輝さんの誕生日

はじめに ウェブ上で効率よく情報をさがす方法 喜田のこれまでの研究 さいごに 検索エンジンについて ロボット検索エンジンの仕組み キーワードの選び方 その他のトピックス 喜田のこれまでの研究 データ圧縮と文字列照合 さいごに

検索エンジンとは ウェブ上から情報を探し出すツール 検索エンジンの種類 検索エンジン サーバ 電子メールの次のよく利用されているサービス 利用者 検索結果 ウェブ上から情報を探し出すツール 電子メールの次のよく利用されているサービス インターネットユーザの80％が利用している 検索エンジンの種類 ディレクトリ型 ロボット型 問合せ 検索エンジン サーバ データの蓄積と索引化 検索エンジンで調べられるのはウェブ上の一部のHPであることをいう。 →抜けがあるということ→「最新情報を得るには」の説明につながる。 巡回 ページ情報 ウェブ

ディレクトリ型検索エンジン （登録型、カテゴリー型） 人手で整理・登録（索引づけ）する 長所 適切なキーワードが分からなくても 検索できる。 検索結果とキーワードとの関係が強い。 短所 検索対象となるページが少ない。 現在では、Yahooもページ検索ができるようになっているし、Googleもカテゴリー型の検索ができるようになっている。 ただし、使い勝手や機能の豊富さ、結果の精度という点を考えると、ディレクトリ型（カテゴリー型）の検索ではYahooに、ロボット型検索ではGoogleに軍配があがる。 例題：Yahoo! Japanで福岡のケーキ屋をさがそう 検索エンジン

ロボット型検索エンジン （全文検索型、フリーワード型） ロボットが自動的に情報を収集し、 サーバで自動的に索引づけをする 長所 検索対象となるページが多い。 ページに含まれているすべての語句が 検索対象になる。 短所 無関係なページも多数検索される。 例題：Googleで今日が誕生日の有名人をさがそう 検索エンジン

検索エンジンサービスの相互関係 （ディレクトリ型） 2003月1日現在（「検索にガンガンヒットするホームページの作り方」から引用）

検索エンジンサービスの相互関係 （ロボット型） 2003月1日現在 （「検索にガンガンヒットする ホームページの作り方」から引用）

検索結果の並びの順番 Googleなどでは、検索結果の並びは検索語（キーワード）に関連の深い順にならんでいる。 リンク・ポピュラリティー 被リンク数が多ければ多いほどページの得点が高い。 リンク・レピュテーション リンク文字列＝リンク先のページの説明 PageRank 点の高いページからのリンク ＞　点の低いページからのリンク

キーワードの選び方 １．固有名詞は良いキーワード 今やっているドラマについて知りたい！ なるべく固有名詞を用いる。 「ドラマ一覧」・・・一般的な名詞 「２００３年春ドラマ」・・・より具体的な名詞

キーワードの選び方 ２．複数のキーワードを用いる キーワードを一つでは、絞り込むのが難しい。 「ドラマ」・・・約 2,090,000 件ヒット！ (2003年4月16日現在) 複数個のキーワードを並べてみる。 「ドラマ　一覧」・・・ 約 216,000 件 「ドラマ　一覧　２００3」・・・ 約 102,000 件 「ドラマ　一覧　２００３ 春」・・・ 約 9,980 件

キーワードの選び方 ３．目的のページを想像する 見つけたいページに含まれていると 予想される語句をキーワードにする 「今やってるドラマの一覧」 → 「200３年　春　ブラックジャックによろしく」 「J-Phoneとauの携帯電話はどちらのほうが、 人気が高い？」 → 「携帯電話加入者数」 単語や語句の意味を知りたい →「～とは」「～入門」 うちの近くのお店を知りたい →郵便番号をキーワードに入れる

キーワードの選び方 ４．同義語・類義語に注意する 「J-Phone」「Jフォン」「ジェイフォン」 「au」「エーユー」「KDDI」 「利用者」「加入者」 「さんま」「サンマ」「秋刀魚」 →キーワードアドバイス サービスを利用してみる

キーワードの選び方 ５．ブーリアン演算子を用いる And検索、Or検索、Not検索 クリーム コロッケ クリーム and コロッケ ・・・　クリームコロッケ クリーム or コロッケ 　・・・　ソフトクリーム、コロッケカレーなど クリーム not コロッケ ・・・　コロッケとは関係ないクリーム

その他のトピックス 最新情報を探す メタ検索エンジン 検索エンジンスパム 「最新」というキーワードでは最新の情報は得られない フレッシュアイを使おう メタ検索エンジン Metcha Search (http://bach.scitec.kobe-u.ac.jp/metcha/) 検索デスク (www.searchdesk.com) multifind (www.infofreako.com/factory/multifind/) 検索エンジンスパム 検索エンジンの精度を落とす原因となる （検索エンジンから）厳しい罰則が与えられる

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

データ圧縮 符号化 データ圧縮 データ圧縮法 情報（記号列）をデジタル化すること → 本質的に無駄な部分が含まれている！ 情報（記号列）をデジタル化すること 　→　本質的に無駄な部分が含まれている！ データ圧縮 データ中の冗長な情報を取り除くことで、データのサイズを 小さくすること データ圧縮法 適応的Huffman符号化 算術符号化 LZ77, LZ78, LZW（辞書ベース圧縮） Burrows Wheeler 変換を用いた圧縮 文法変換に基づく圧縮

文字列照合 文字列照合（問題）とは 何の役に立つの？ パターン: オトコ テキスト: オモイコンダラシレンノミチヲイクガオトコノ キーワード検索 テキスト・データベース処理 データ整形 データ・マイニング スペル・チェッカー ゲノム情報処理 パターン: オトコ テキスト: オモイコンダラシレンノミチヲイクガオトコノ

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

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

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

研究の成果（その１） 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 パタンの長さ

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

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

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

研究の（凄い）成果 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 パタンの長さ

さいごに

その後、取り組んだこと データ圧縮による文字列近似度（編集距離）の計算の高速化 半構造化データに対する文字列照合に関する研究（2002年） 二つのDNA配列の近似度をすばやく測ることができる！ 半構造化データに対する文字列照合に関する研究（2002年） 大量のXMLデータに対し、タグ構造を見ながら検索できる。 これまでの研究から、データ圧縮を用いて高速化できないか？ 半構造化データを高速に照合できるデータ圧縮法の開発。 <作家> <名前>京極夏彦</名前> <ジャンル>ミステリー、妖怪</ジャンル> <著作> <タイトル>姑獲鳥の夏</タイトル> <出版年>1994</出版年> <出版社>講談社ノベルス</出版社> </著作> </作家> XMLデータ例

今現在、論文執筆中 VLDCパタンと文字列との間にk文字のミスマッチを許した照合処理 Variable Length Don’t Care (VLDC) パタン： ＊のための＊入門 京都＊殺人事件 k文字のミスマッチ パタン：　機動戦士＊ガンダム＊ k = 2 ＯＫ！：　機動戦士ガンダムZZ、機動戦士Vガンダム、 　　　　機動武闘伝Gガンダム ＮＧ！：　新機動戦記ガンダムW、∀ガンダム ＊：0文字以上の任意の文字列にマッチ