検索エンジン (照合とランキング) 平成24年11月30日 アルゴリズム論 9回目 マッチング→ランキング ランク付け されたページ マッチしたページ 検索要求発行 ロンドン バス 時刻表 マッチング ランキング ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ウェブ検索には、マッチングとランキングの2段階がある。第1(マッチング)段階終了後は、 マッチした数干~数百万ものページが残される。第2(ランキング)段階では、これらが関連性 の高さ順にソートされる。 Webページ番号だけから成る索引(インデックス)ファイル 1 the cat sat on the mat 2 a cat dog mat on sat stood the while the dog stood on the mat 3 1 2 1 1 1 2 1 3 3 3 2 2 3 3 2 3 3 1,2,3のWebページから成るWWW フレーズ検索“cat sat“を実現できるか? the cat stood while a dog sat Webページ番号+単語位置情報から成る 索引(インデックス)ファイル 1 the cat sat on 1 2 3 4 the mat 5 6 2 the 1 on 4 dog stood 2 3 the mat 5 6 3 the cat stood 1 2 3 while a dog sat 5 6 7 4 (ページ番号-位置情報) a cat dog mat on sat stood the while 3-5 (ページ番号3の5番目) 1-2 3-2 2-2 3-6 1-6 2-6 1-4 2-4 1-3 3-7 2-3 3-3 1-1 1-5 2-1 2-5 3-1 3-4 マラリアに関連するWebページ 1 2 By far the most common cause of malaria is being bitten by an infected mosquito, but there are also other ways to contract the disease. Our cause was not helped by the poor health of the troops, many of whom were suffering from malaria and other tropical diseases. also 1-19 ・・・ cause 1-6 2-2 ・・・ malaria 1-8 2-19 ・・・ whom 2-15 マラリアを引き起こす原因について説明しているページはどっち? →コンピュータに判断させる方法は? →文章の意味を理解させる人工知能を作る →もっと簡単は方法は? →索引ファイルだけを使う方法がある(精度は落ちるかもしれない) タイトルと本文を持つWebページ ブラウザー表示 1 2 my cat 3 my dog the dog stood on the mat the cat sat on the mat my pets the cat stood while a dog sat HTMLライクな表示:<>メタワード,タグ 1 <title> my cat </title> <body> the cat sat on the mat </body> 2 <title> my dog </title> <body> the dog stood on the mat </body> 3 <title> my pets </title> <body> the cat stood while a dog sat </body> タグと文字を含んだインデックスファイル タイトルにdogを含むページを検索したい a cat dog mat my on pets sat stood the while </body> < <body> ti </title> tl <title> 3-10 1-3 1-7 3-7 2-3 2-7 3-11 1-11 2-11 1-2 2-2 3-2 1-9 2-9 3-3 1-8 3-12 2-8 3-8 1-6 1-10 2-6 2-10 3-6 3-9 1-12 2-12 3-13 1-5 2-5 3-5 1-4 2-4 3-4 < 1-1 2-1 3-1 ti e dog: 2-3 2-7tl< 3-11 eti E <title>: n1-1 2-1 3-1 tl Ee d </title>: >1-4 2-4 3-4 n dE >n Webページランキング (Googleの基本的アイデア) ハイパーリンクトリック アーニーのスクランブル エッグレシピ バートのスクランブル エッグレシピ ボウルで4個の卵と 塩胡椒少々を混ぜる・・・ まず大さじ1杯のバターを 溶かす・・・ アーニーのレシピ はよい 私はバートのレシピが 本当に気に入った バートのレシピは すばらしい バートのレシピは とてもいい パートのページを参照しているリンクが3つ アーニーのページを参照しているリンクが1つ →バートのページ評価>アーニーのページ評価 オーソリティトリック アーニーのスクランブル エッグレシピ バートのスクランブル エッグレシピ ボウルで4個の卵と 塩胡椒少々を混ぜる・・・ まず大さじ1杯のバターを 溶かす・・・ ジョン・マコーミックの ホームページ アリス・ウォーターズの ホームページ 私は一度アーニーのレシピ を試してみたが、決して悪い ものではなかった。 バートのレシピは、間違いなく 最良のレシピの1つだ。 ジョン・マコーミック:コンピュータ科学者 アリス・ウォーターズ:有名なシェフ →バートのページ評価>アーニーのページ評価 でも,コンピュータはどちらが権威をもつページなのか分からない オーソリティトリックの近似計算 アーニーのスクランブル エッグレシピ バートのスクランブル エッグレシピ ボウルで4個の卵と 塩胡椒少々を混ぜる・・・ まず大さじ1杯のバターを 溶かす・・・ 2 ジョン・マコーミックの ホームページ 私は一度アーニーのレシピ を試してみたが、決して悪い ものではなかった。 1 1 100 アリス・ウォーターズの ホームページ バートのレシピは、間違いなく 最良のレシピの1つだ。 100 2 1 1 1 1 ・・・100pages・・・ 1 1 1 1 循環参照問題 A C B D E ハイパーリンクの循環参照の例.A、B、Eページは、Aからスタートして、B、続いてEに移動し, 最後に出発点であるAに戻ってこれてしまうので循環参照を形成している。 A C 1 B 2 A 2 D 1 E 2 C 1 B 4 4 D 1 E 循環参照によって起きる問題。 A、B、Eのスコアはいつも修正が必要になり、無限に大きくなっていってしまう。 4 ランダムサーファーモデル B C A 濃い色:サーファーが訪れたページ 破線の矢印:ランダムな再スタート サーファーは、Aからスタートし、2回のランダムな再スタートをはさんで, ランダムにハイパーリンクを選択している。 D ランダムサーファーモデルの シミュレーション B 109 1000回 (訪問回数) 16 74 55 58 13 C 46 55 32 17 21 A 118 126 101 15 144 D B 100万回 (訪問割合) 10% 7% 4% 2% 5% 4% 2% C 4% 4% 2% 2% A 13% 14% 10% 2% 15% D サーファーオーソリティ(1) アーニーのスクランブル エッグレシピ バートのスクランブル エッグレシピ 1% 28% ジョン・マコーミックの ホームページ アリス・ウォーターズの ホームページ 1% 0.4% 0.4% 0.4% 32% 0.4% 0.4% 0.4% ・・・100pages・・・ 0.4% 0.4% 0.4% 0.4% サーファーオーソリティ(2) A B 33% C 31% D 3% E 3% 30%
© Copyright 2025 ExpyDoc