知的情報処理 4. Search Engines

検索ツール
„
知的情報処理
4. Search Engines
9
9
9
9
9
9
櫻井彰人
慶應義塾大学理工学部
9
9
9
9
9
メタサーチ
„
次のようなものがある（きりがない、、、）
検索エンジン search engines
ディレクトリ search directories
メタサーチ meta search engines
画像検索 image search engines
辞書 dictionaries
類義語 thesauri
百科事典 encyclopaedias
地図 maps
ニュース news
ホテル・鉄道・航空機 reservations
グルメ、、、、
日本のサーチエンジン
（「メタ」は言葉の乱用だが）すっかり普通に
http://www1.neweb.ne.jp/wa/k-c/
日本のサーチエンジン
日本のサーチエンジン
2004/06/10現在 371リンク
http://shikariki.com/link.html
1
サーチエンジンの大きさ
一日当たりのサーチ数
Billions Of Textual Documents Indexed
December 1995-September 2003
GG: Google, ATW: AlltheWeb, INK: Inktomi,
TMA: teoma, AV: Altavista
http://searchenginewatch.com/reports/article.php/2156461
http://searchenginewatch.com/reports/article.php/2156481
サーチエンジンの歴史
サーチエンジン間の関係
http://www.bruceclay.com/searchenginechart.pdf
サーチ数シェア
主なサーチエンジン
„
„
„
„
„
„
Google
AltaVista
Yahoo
Alltheweb
MSN
DogPile
„
„
„
„
„
„
„
Share Of Searches: July 2005
Google: google.com や google image search 等
Yahoo: Altavista, AllTheWeb, Overture
MSN: MSN search
AOL: AOL search, Netscape search
Ask: Ask Jeeves, Excite, iWon, MyWay.com 等
„
„
„
„
„
All about Japna
All the Web
AltaVista
BIGLOBEサーチ
Excite
Fresheye
goo
Google
Infoseek
Lycos
MSN
Yahoo
http://searchenginewatch.com/img/comscore-us.gif
2
ところで、サーチエンジンとは何か?
„
„
„
„
„
„
„
ディレクトリ型とクローラー型とがある
クローラーまたはスパイダーと呼ばれるプログラム（複数の、
普通は、大量のサーバー上で動く）が
web 上を動き回って、サイトの索引をつくる
そのときには、web サイトのリンク情報を参考にする
ユーザは、キーワードを入力することにより、それにマッチし
た単語をもつサイトを見つけ出すことができる
すなわち、サーチエンジンは www をサーチするわけではな
い。予め作成してある索引（index）の上をサーチするのであ
る。
従って、最新の情報が見つかるわけではない
ディレクトリの方がよいこともある
„
„
„
„
„
„
というのも、ディレクトリは人間が作ったもので、プログラムが
作ったものではない。人間は意味・重要性がわかるが、プロ
グラムじゃあねえ.
ディレクトリは、”web全体” ではなく、人間が評価した結果を
反映している
もっとも、更新頻度が少なく、リンク切れが多発する。
web サイト先頭にいくにはいい
„
„
„
„
サーチエンジンは www をサーチするわけではない。
予め作成してある索引（index）の上をサーチするの
である。
ディレクトリの例
„
„
先ほどあげた中にもあるが、大きいものの一つは
Open Directory Project
… http://dmoz.org/
„
ある構造に従って整理されている。
… 自分の考えと大きく違うと、扱いにくい
… ぴったりとあうと、非常に使いやすい
うまくつくれば、ブラウズしやすいように集められる
図書館方式（秩序だったファイリング）は崩壊する、か？
Google の索引
何ページ持っているか
„
索引のサーチ or サーフィン
できるだけ多くのページの索引付けができれば、ユーザが必
要とするものを見つけやすくなる
もちろん、ごみの山から探し物を見つけ出そうということにな
ると、そう簡単な話ではなくなる
Google— 8+ Billion
Yahoo— 3+Billion
Teoma— 1 Billion
„
検索可能な web ページの約半分が索引付けされ
ているという
Source: Infopeople.org
3
サーチエンジンで探せないものは?
„
個人のデータベース
… 固定した
URL を持たない
アカデミック
サーチエンジンの技術
… 専門的なもの,
„
“Ask Jeeves” では、料金を払ったサイトしか索引
付けしていない
サーチエンジンの特徴
„
無編集 – コンテンツの登録は誰でもできる
„
„
„
電話番号簿, パンフレット, カタログ, 論文, ニュース,
天気予報,,, しかも一箇所に入れることができる
„
ユーザの期待:
“検索結果の先頭は、まさに探していたものであ
るべき”
… 多くは
ユーザも多種多様
（安くはない）料金を払う, プロのサーチャー
文献を探す研究者
… Web: ありとあらゆる目的をもったありとあらゆる人々
… 実際にそうなることはある。しかし、それは、ユーザが最
… オンラインカタログ:
も平均的で最も平凡な考えをもっているときに限られる.
スケール
… 一日あたり数億の検索;
何十億という文書
ディレクトリとサーチエンジン
„
語平均 (米国: 2000年8月)
1.7 (米国: ~1997年)
… かつては
… Lexis-Nexis:
„
Web サーチのクエリは一般に 短い:
… ~2.4
情報の種類は多種多様
„
„
質の問題あり; スパム的なものも
Web サーチのクエリ
ディレクトリ
… 手で選んだサイト
… ページに関するある記
述を対象とした検索
… 予め作成した分類に
従って構成されている
„
サーチエンジン
ランキングとは?
„
多くの変種あり
„
こういったものの組合せ:
… しばしば整理しようがない;
… すべてのサイトのすべ
てのページ
… ページ自身の内容に
関する検索
… クエリに対応して公正
される。通常は、重要
度や他の点数付け（ス
コア）によって構成さ
れる
細部は独自開発で流動的
… 情報検索タイプ
IR-style 重要度: 単語の頻度, 近さ, 場
所 (例えば, 表題), フォント, 等.
… 知名度
… リンク解析結果
„
ほとんどはこうした特徴をベクトル空間で表現した
ものを用いる. こんな風に:
… 各特徴の重みをベクトルにする
… 特徴数を乗ずる
4
重要度 relevance: IR 以上
„
ページの “人気度 popularity” (DirectHitがもと)
… 訪れる人が多いページ
Web サーチ アーキテ
クチャ
(一般に)
… クエリの結果、よく訪れるページ
„
リンクの “co-citation” (Googleがもと)
… 他のサイトにリンクされているサイトはどれか?
“authoritative sources” をみつける、も
ともとは、文献学・社会学の考察に基づく
… のちほど検討する
… 権威のある文献
標準的なサーチエンジンのアーキテクチャ
重複を省き,
文書を保管する
web の
クロール
文書Id
結果の
表示
サーバー
転置インデックスの作り方
„
„
転置インデックス
create an
inverted
index
ユーザ
クエリ
定期的に再構築する以外は、静的
文書をパースして、形態素解析し、
トークンを切り出す. 文書IDとともに
記録.
文書 1
文書2
Now is the time
for all good men
to come to the aid
of their country
It was a dark and
stormy night in
the country
manor. The time
was past midnight
転置
インデックス
Term
now
is
the
time
for
all
good
men
to
come
to
the
aid
of
their
country
it
was
a
dark
and
stormy
night
in
the
country
manor
the
time
was
past
midnight
Doc #
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
転置インデックス
の作り方
„
全文書から抜き出し
終わったら、辞書式
順序にソートし、転置
インデックスとする.
Term
now
is
the
time
for
all
good
men
to
come
to
the
aid
of
their
country
it
was
a
dark
and
stormy
night
in
the
country
manor
the
time
was
past
midnight
Doc #
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
Term
a
aid
all
and
come
country
country
dark
for
good
in
is
it
manor
men
midnight
night
now
of
past
stormy
the
the
the
the
their
time
time
to
to
was
was
Doc #
2
1
1
2
1
1
2
2
1
1
2
1
2
2
1
2
2
1
1
2
2
1
1
2
2
1
1
2
1
1
2
2
5
転置インデックス
の作り方
„
„
一文書内に繰り
返し現れるトーク
ンはまとめる.
文書内のトークン
の出現頻度を数
える.
Term
a
aid
all
and
come
country
country
dark
for
good
in
is
it
manor
men
midnight
night
now
of
past
stormy
the
the
the
the
their
time
time
to
to
was
was
Doc #
Term
a
aid
all
and
come
country
country
dark
for
good
in
is
it
manor
men
midnight
night
now
of
past
stormy
the
the
their
time
time
to
was
2
1
1
2
1
1
2
2
1
1
2
1
2
2
1
2
2
1
1
2
2
1
1
2
2
1
1
2
1
1
2
2
Doc #
Freq
2
1
1
2
1
1
2
2
1
1
2
1
2
2
1
2
2
1
1
2
2
1
2
1
1
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
2
2
転置インデックスの作り方
Term
a
aid
all
and
come
country
country
dark
for
good
in
is
it
manor
men
midnight
night
now
of
past
stormy
the
the
their
time
time
to
was
Doc #
Freq
2
1
1
2
1
1
2
2
1
1
2
1
2
2
1
2
2
1
1
2
2
1
2
1
1
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
2
2
辞書/語彙
Term
a
aid
all
and
come
country
dark
for
good
in
is
it
manor
men
midnight
night
now
of
past
stormy
the
their
time
to
was
Doc #
Tot Freq
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
2
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
1
2
2
2
Freq
2
1
1
2
1
1
2
2
1
1
2
1
2
2
1
2
2
1
1
2
2
1
2
1
1
2
1
2
„
最後に, 辞書/レキシコンと転記ファイルを作る
… 辞書 Dictionary または語彙 Lexicon ファイル
と
… 転記ファイル Postings
転置インデックス
転記ファイル
N docs
転置インデックスの作り方
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
2
2
„
„
„
„
個々の項目への高速な検索ができる
各項目につき、次のものがある:
… 文書ID
… 当該文書中の当該項目の出現頻度 (optional)
… 当該文書中の当該項目の出現場所 (optional)
これを用いると次のような論理クエリに答えられる:
„ 地域 -> d1, d2
„ 様式 -> d2
„ 地域 AND 様式 -> d2
統計的なランキングにも使用可能
Web サーチエンジン用には
„
„
„
„
web は大きすぎる。しかし、転置インデックスは用い
られる.
あるシステムでは、インデックスを異なるコンピュー
タに分割しておく。個々のコンピュータは異なる部分
を処理することになる.
あるシステムでは、データを異なるコンピュータ上で
重複させる; クエリを分散させる.
多くの場合、両方を行う.
この例では、ページ毎のデー
タは分割され複数のコンピュ
ータに分けて記憶されている
. さらに、分けられたものは、
複数のコンピュータに重複し
て記憶されている.
各行は一秒あたり120クエリ
が処理できる
各列は 7M ページが処理で
きる
より多くのクエリを処理する
には、行を追加すればよい.
Knut Magne Risvik は、
Overture → Yahoo →
Google
From description of the FAST search engine, by Knut Magne Risvik
http://www.infonortics.com/searchengines/sh00/risvik_files/frame.htm (no
longer available) しかし
http://research.yahoo.com/publication/OR-2003-015.pdf
6
CPU の直列的配置
„
コスト節約のための工夫:
… 質の高いしばしば参照されるページは多数重複させる
… 質の低いあまり参照されないページは少数の重複
Web クロール
… クエリは、質の高いページ（をもつコンピュータ）に
… 見つからなければ、他のコンピュータに
Web クローラー
„
„
Web クローリング アルゴリズム
いったいどうやって、webサーチエンジンは索引付
けするページをもってくるのか?
主たるアイデア:
„
より詳細には:
… キューに既知のサイトを置く
… キューが空になるまで、下記を繰り返す:
… 既知のサイトから開始
„
… このサイトがもつ情報を記録
„
キューの先頭にあるページを取り出す
このページが未処理であれば:
ページ上の情報を記録
ƒ 単語の位置、外へ出るリンク等
… 各リンクをキューにつける
… このページが処理済というしるしをつける
… 個々のサイトから、そこにあるリンクをたどる
…
… 新しいサイトの情報を記録
… 繰り返す
Web クローラーに関する問題
„
„
立ち入り禁止
… ファイル norobots.txt に立入禁止ディレクトリ表
… 新しさ: 頻繁に更新されるページをみつけ、高頻度に訪れる
必要がある.
重複, 仮想ホスト, ミラーリング等.
… ハッシュ関数でページを変換
レポート課題1
„
„
内容は、先々回示したとおり
締め切りは: 10/23 （来週の月曜日） 24:00
… 上記は
web による提出期限です
… 紙による提出は、その翌日の講義終了時です
„
「量」は、A4用紙１∼２枚を目安とする
… ハッシュ表上で新しいページと比較
„
„
他にも
… サーバーが動作していない; 誤った html; リンク切れ; ク
ローラーを騙す目的で、様々な単語が加えられること ...
Web クローリングをロバストに行うのは結構難しい
7
レポート課題2
„
課題：
… （先回示したように）翻訳を自動的に行うことは非常に難
しいことです。欠点を持ちつつもかなりなレベルに達して
います。そこで、機械翻訳に関する、以下のどちらかの課
題をといてください。ただし、翻訳する日本語原文は、新
聞記事・解説、小説、論文等、比較的よく推敲された文を
用いてください
„
„
複数の機械翻訳ソフトを用いて、その得手・不得手を比較してくだ
さい。
pre-edit/post-edit を駆使して、日本語→英語→日本語の翻訳が、
うまくいくようにしてください（なかなかうまくいきません）
翻訳例
インターネットを利用する上で、目的の情報が載っているウェブサイトを的確に探し当てられる
かどうかは大きな意味を持ちます。前回は検索の最も基礎的な理 屈とテクニックを書きました。
２回目の今週は、さらに一歩進んで、目的のページを短時間で効率的に見つける方法をいくつ
か紹介しましょう。ちょっとした工 夫で、情報は格段に見つけやすくなるのです。
When utilizing Internet, whether or not you can discover the web sight to which intended
information has been recorded precisely, it has important meaning. The last time the
most fundamental reason and technique of search were written. 2nd this week,
furthermore the one step advancing, it will introduce several method of finding the
intended page efficiently at brief. With the little device, markedly to find information it is to
become easy.
意図した網の視力が情報正確に記録された発見できるどうかインターネットを利用するとき、それは
重要な意味を有する。 最後調査の最も基本的な理由そして技術は書かれていた。 第2この週、なお
進む1つのステップそれは意図されていたページを効率的に見つける方法を報告書で複数もたらす。
小さい装置によって、著しく情報を見つけるためにそれは容易になることである。
日本語原文は, 「てくの生活入門」 ウェブ検索テクニック（下）
http://www.be.asahi.com/20061014/W16/20061004TBEH0022A.html
翻訳例
インターネットを利用する上で大切なことは、目的の情報が載っているウェブサイトを的確に探し
当てることです。前回、私は、検索のための最も基礎的な理屈と技術を書きました。今週は第２
回目ですから、私が高度な方法をいくつか紹介します。その方法を使えば、あなたは、効率的に
目的のページを見つけられます。ちょっとした工夫をすれば、私たちは容易に情報が見つけられ
ます。
課題２補足
„
締め切りは: 10/30 （再来週の月曜日） 24:00
… 上記は
web による提出期限です
… 紙による提出は、その翌日の講義終了時です
When utilizing Internet, important thing is to discover the web site to which intended
information has been recorded precisely. The last time, I wrote the most fundamental
reason and technology for searching. Because this week time it is 2nd, I introduce
several high-level method. If the method is used, you find the intended page efficiently. If
the little device is done, we find information easily.
„
「量」は、A4用紙2∼3枚を目安とする
インターネットを利用するとき、重要な事柄は意図したウェブサイトが情報正確に記録された発見する
ことである。 最後、私は捜索のために最も基本的な理由および技術を書いた。 この週の時間それが
第2であるので、私は複数高レベル方法をもたらす。 方法が使用されれば、意図されていたページを
効率的に見つける。 小さい装置が終った、私達は情報を容易に見つける。
レポート作成・提出上の注意
„
常識的な注意事項です。
… レポート作成は、各自、独自に行ってください。
… 基本的な操作方法は、相談して結構です。
… 他人の成果を用いる場合は、許された範囲内で、しかも、
原典を明記して引用してください。
… 読む人を説得するように、レポートは書いてください
„
提出方法
… web
経由で提出するとともに、印刷して提出してください
… 量については、特に規制しません。しかし、十分な量で、
しかも過分にならないようにしてください
8