ネット時代の情報センス
情報検索技術のトピックス
(平成16年度版)
喜田拓也
(http://rd.cc.kyushu-u.ac.jp/~kida/)
横山光輝さんの誕生日
1
はじめに

ウェブ上で効率よく情報をさがす方法





喜田のこれまでの研究


検索エンジンについて
ロボット検索エンジンの仕組み
キーワードの選び方
その他のトピックス
データ圧縮と文字列照合
さいごに
2/33
検索エンジンとは
利用者
検索結果

ウェブ上から情報を探し
出すツール


電子メールの次のよく利用
されているサービス
インターネットユーザの
80%が利用している
問合せ
検索エンジン
サーバ
データの蓄積と索引化

検索エンジンの種類


巡回
ディレクトリ型
ロボット型
ページ情報
ウェブ
3/33
ディレクトリ型検索エンジン
(登録型、カテゴリー型)

人手で整理・登録(索引づけ)する

長所



適切なキーワードが分からなくても
検索できる。
検索結果とキーワードとの関係が強い。
短所

検索対象となるページが少ない。
例題:Yahoo! Japanで福岡のケーキ屋をさがそう
検索エンジン
4/33
ロボット型検索エンジン
(全文検索型、フリーワード型)

ロボットが自動的に情報を収集し、
サーバで自動的に索引づけをする

長所



検索対象となるページが多い。
ページに含まれているすべての語句が
検索対象になる。
短所

無関係なページも多数検索される。
例題:Googleで今日が誕生日の有名人をさがそう
検索エンジン
5/33
検索エンジンサービスの相互関係
(ディレクトリ型)
2003月1日現在(「検索にガンガンヒットするホームページの作り方」から引用)
6/33
検索エンジンサービスの相互関係
(ロボット型)
2003月1日現在
(「検索にガンガンヒットする
ホームページの作り方」から引用)
7/33
検索結果の並びの順番

Googleなどでは、検索結果の並びは検索語
(キーワード)に関連の深い順にならんでいる。

リンク・ポピュラリティー


リンク・レピュテーション


被リンク数が多ければ多いほどページの得点が高い。
リンク文字列=リンク先のページの説明
PageRank

点の高いページからのリンク
> 点の低いページからのリンク
8/33
キーワードの選び方
1.固有名詞は良いキーワード

今やっているドラマについて知りたい!

なるべく固有名詞を用いる。


「ドラマ一覧」・・・一般的な名詞
「2003年春ドラマ」・・・より具体的な名詞
9/33
キーワードの選び方
2.複数のキーワードを用いる

キーワードを一つでは、絞り込むのが難しい。

「ドラマ」・・・約 2,090,000 件ヒット!
(2003年4月16日現在)

複数個のキーワードを並べてみる。



「ドラマ 一覧」・・・ 約 216,000 件
「ドラマ 一覧 2003」・・・ 約 102,000 件
「ドラマ 一覧 2003 春」・・・ 約 9,980 件
10/33
キーワードの選び方
3.目的のページを想像する

見つけたいページに含まれていると
予想される語句をキーワードにする




「今やってるドラマの一覧」
→ 「2003年 春 ブラックジャックによろしく」
「J-Phoneとauの携帯電話はどちらのほうが、
人気が高い?」
→ 「携帯電話加入者数」
単語や語句の意味を知りたい
→「~とは」「~入門」
うちの近くのお店を知りたい
→郵便番号をキーワードに入れる
11/33
キーワードの選び方
4.同義語・類義語に注意する

「J-Phone」「Jフォン」「ジェイフォン」
「au」「エーユー」「KDDI」
「利用者」「加入者」
「さんま」「サンマ」「秋刀魚」

→キーワードアドバイス サービスを利用してみる



12/33
キーワードの選び方
5.ブーリアン演算子を用いる

And検索、Or検索、Not検索
クリーム
コロッケ
クリーム and コロッケ ・・・ クリームコロッケ
クリーム or コロッケ ・・・ ソフトクリーム、コロッケカレーなど
クリーム not コロッケ ・・・ コロッケとは関係ないクリーム
13/33
その他のトピックス

最新情報を探す



メタ検索エンジン




「最新」というキーワードでは最新の情報は得られない
フレッシュアイを使おう
Metcha Search (http://bach.scitec.kobe-u.ac.jp/metcha/)
検索デスク (www.searchdesk.com)
multifind (www.infofreako.com/factory/multifind/)
検索エンジンスパム


検索エンジンの精度を落とす原因となる
(検索エンジンから)厳しい罰則が与えられる
14/33
喜田のこれまでの研究
データ圧縮技術と文字列照合技術の融合
データ圧縮

符号化


情報(記号列)をデジタル化すること
→ 本質的に無駄な部分が含まれている!
データ圧縮

データ中の冗長な情報を取り除くことで、データのサイズを
小さくすること

データ圧縮法





適応的Huffman符号化
算術符号化
LZ77, LZ78, LZW(辞書ベース圧縮)
Burrows Wheeler 変換を用いた圧縮
文法変換に基づく圧縮
16/33
文字列照合

文字列照合(問題)とは
パターン: オトコ
テキスト: オモイコンダラシレンノミチヲイクガオトコノ

何の役に立つの?






キーワード検索
テキスト・データベース処理
データ整形
データ・マイニング
スペル・チェッカー
ゲノム情報処理
17/33
研究目的
文書ファイル群
「この世には不思議なことなど何もないのだよ、関口君」 京極
堂を変わり者の東の横綱とすると、榎木津は西の横綱だ。何
だか酷く男が羨ましくなつてしまつた。 「楠本君。せいぜい月
の光を浴びるがいいよ」「世界中の不幸と苦悩を纏めて背負っ
たような顔をして、そんなもの誰だって背負っているぞ!ちっと
も偉くない。心の暗闇だか何だか知らないが、心に光度(カン
デラ)や照度(ルクス)があるか。明るい暗いで善し悪しが決ま
るのは電灯くらいだ」「僕が落すのは憑物。犯人(ホシ)を落す
のは警察。原稿を落すのは関口君だ」「あなたが―蜘蛛だった
のですね。」「それが―絡新婦の理ですもの」
圧縮文書ファイル群
adoghqu3850pcxps;
afdjaeqw09bjzpafq
05z90
rwDEVcx083nk;pzp
99OeDfja
18/33
圧縮されたデータに対する文字列照合
普通の
文字列照合機械
展開
圧縮テキスト
圧縮テキスト
原テキスト
圧縮テキストに対する
文字列照合機械
19/33
この問題に対する3つの手法
「展開しながら」法
「展開してから」法
事情により差し替えてます・・・
目標1: これらより速い!
「展開しないで」法
20/33
研究の成果(その1)
CPU時間(秒)
1.4
1.2
AlphaStation XP1000
(Alpha21264: 667MHz)
Tru64 UNIX V4.0F
1.0
Genbank(DNA塩基配列)
17.1Mbyte
0.8
「展開しながら」法
0.6
compress(LZW)+KMP
gunzip(LZ77)+KMP
0.4
「展開しないで」法
0.2
T. Kidaら[1998]
0
ビットパラレルによる高速化[1999]
5
10
15 20 25
パタンの長さ
30
21/33
ディスク容量は
十分あるったい!
22/33
圧縮文字列照合する理由は?
容量は十分あるのに、テキストを
圧縮して保存しますか?
×
×
×
×
23/33
圧縮文字列照合する理由は?
当初の目標
新目標
展開時間
+
原テキスト上
の照合時間
>
圧縮テキスト上
の照合時間
24/33
研究の(凄い)成果
CPU時間(秒)
0.8
AlphaStation XP1000
(Alpha21264: 667MHz)
Tru64 UNIX V4.0F
0.7
Medline(英文テキスト)
60.3Mbyte
0.6
非圧縮テキストをKMPで照合
0.5
「展開しないで」法
0.4
BPE圧縮テキストに対する照合(KMP)
0.3
非圧縮テキストをAgrepで照合
0.2
「展開しないで」法
0.1
0.0
BPE圧縮テキストに対する照合(BM)
Shibata, et al. (2000)
5
10 15 20 25
パタンの長さ
30
25/33
さいごに
その後、取り組んだこと

データ圧縮による文字列近似度(編集距離)の計算の高速化
 二つのDNA配列の近似度をすばやく測ることができる!

半構造化データに対する文字列照合に関する研究(2002年)
 大量のXMLデータに対し、タグ構造を見ながら検索できる。
 これまでの研究から、データ圧縮を用いて高速化できないか?
 半構造化データを高速に照合できるデータ圧縮法の開発。
XMLデータ例
<作家>
<名前>京極夏彦</名前>
<ジャンル>ミステリー、妖怪</ジャンル>
<著作>
<タイトル>姑獲鳥の夏</タイトル>
<出版年>1994</出版年>
<出版社>講談社ノベルス</出版社>
</著作>
</作家>
27/33
今現在、論文執筆中

VLDCパタンと文字列との間にk文字のミスマッチ
を許した照合処理

Variable Length Don’t Care (VLDC) パタン:



*のための*入門
京都*殺人事件
*:0文字以上の任意の文字列にマッチ
k文字のミスマッチ


パタン: 機動戦士*ガンダム*
k=2


OK!: 機動戦士ガンダムZZ、機動戦士Vガンダム、
機動武闘伝Gガンダム
NG!: 新機動戦記ガンダムW、∀ガンダム
28/33
ダウンロード

ネット時代の情報センス