ネット時代の情報センス

ネット時代の情報センス
情報検索技術のトピックス
（平成１6年度版）
喜田拓也
(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
キーワードの選び方
１．固有名詞は良いキーワード

今やっているドラマについて知りたい！

なるべく固有名詞を用いる。


「ドラマ一覧」・・・一般的な名詞
「２００３年春ドラマ」・・・より具体的な名詞
9/33
キーワードの選び方
２．複数のキーワードを用いる

キーワードを一つでは、絞り込むのが難しい。

「ドラマ」・・・約 2,090,000 件ヒット！
(2003年4月16日現在)

複数個のキーワードを並べてみる。



「ドラマ一覧」・・・約 216,000 件
「ドラマ一覧２００3」・・・約 102,000 件
「ドラマ一覧２００３春」・・・約 9,980 件
10/33
キーワードの選び方
３．目的のページを想像する

見つけたいページに含まれていると
予想される語句をキーワードにする




「今やってるドラマの一覧」
→ 「200３年春ブラックジャックによろしく」
「J-Phoneとauの携帯電話はどちらのほうが、
人気が高い？」
→ 「携帯電話加入者数」
単語や語句の意味を知りたい
→「～とは」「～入門」
うちの近くのお店を知りたい
→郵便番号をキーワードに入れる
11/33
キーワードの選び方
４．同義語・類義語に注意する

「J-Phone」「Jフォン」「ジェイフォン」
「au」「エーユー」「KDDI」
「利用者」「加入者」
「さんま」「サンマ」「秋刀魚」

→キーワードアドバイスサービスを利用してみる



12/33
キーワードの選び方
５．ブーリアン演算子を用いる

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
この問題に対する３つの手法
「展開しながら」法
「展開してから」法
事情により差し替えてます・・・
目標１：これらより速い！
「展開しないで」法
20/33
研究の成果（その１）
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


ＯＫ！：機動戦士ガンダムZZ、機動戦士Vガンダム、
機動武闘伝Gガンダム
ＮＧ！：新機動戦記ガンダムW、∀ガンダム
28/33

Download Report