Googleの様に検索を高速で行うための方法について、わかり易く教えてください。

・方法というのは、アルゴリズム、システム、プログラムなどなどについてです。
・インデックスで云々ということは何となく知ってはいるのですが
 それが何で早くなるのか?また高速化する方法はそれ以外にあるのかが?です。

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2012/07/28 10:39:42
  • 終了:2012/08/02 08:59:33

ベストアンサー

id:a-kuma3 No.2

a-kuma3回答回数4624ベストアンサー獲得回数19592012/07/28 14:47:02

ポイント425pt

まず、インデックスの話。

分厚い百科事典を想像してください。
ある言葉について調べようとします。
一ページ目からめくって、その言葉が出てくるかどうかを見ていくと、とても大変です。

索引から探しましょうか。
索引は、アイウエオ順になっているので、最初から順番に見ていかなくても、大体の位置が分かります。
単語を見つけました。
見出しだけではなく、その言葉を内容に含んでいるページも載っています。
探すページを絞り込むことができたので、後は、そのページを順番に見ていくだけです。

検索処理でのインデックスも、概ね、このようなことをやってます。



次に、インデックス以外の高速化の話。
やり方はいろいろありますが、一番大事なのは、分散処理です。

今度は、一冊だけじゃなく、十巻セットくらいの百科事典を想像しましょうか。
索引を使って、どこにありそうなのかを調べるところまでは一緒です。
索引から、一冊だけではなく、複数の巻にあることが分かりました。
ずいぶん絞り込まれているので、同じように順番に調べて行けば良いのですが、もっと早く探す方法はないでしょうか?

おや、弟くんが暇そうにしていますね。
彼にも手伝ってもらいましょう。
同時に二人で調べれば、半分の時間で探せそうです。

実際の検索処理では、複数の検索処理を大量にこなさなくちゃいけないので、こんなに単純ではありませんが、原理は分かりやすいですよね。

他1件のコメントを見る
id:a-kuma3

「インデックスをどう作るか」という面では、それ用のアルゴリズムが研究されてます。
例えば、形態素解析 とか。

2012/07/28 15:53:36
id:tsuka115

なるほど~ なかなか難しそうなお話ですね

2012/07/29 03:04:41

その他の回答(5件)

id:Cherenkov No.1

Cherenkov回答回数1503ベストアンサー獲得回数4932012/07/28 11:39:46

ポイント10pt

これらの本にわかりやすく書いてあると思います。


id:tsuka115

どーもです。

細かい情報は書籍で調べようかと思ってましたので助かります。
ただ、今回は、とりあえず概念的なイントロ部分を教えて欲しかったんです。
例えばその概念をベースに、わかりにくい部分を書籍を立ち読みしてみて、
わかりやすそうなのを買えますので。

2012/07/28 15:02:50
id:a-kuma3 No.2

a-kuma3回答回数4624ベストアンサー獲得回数19592012/07/28 14:47:02ここでベストアンサー

ポイント425pt

まず、インデックスの話。

分厚い百科事典を想像してください。
ある言葉について調べようとします。
一ページ目からめくって、その言葉が出てくるかどうかを見ていくと、とても大変です。

索引から探しましょうか。
索引は、アイウエオ順になっているので、最初から順番に見ていかなくても、大体の位置が分かります。
単語を見つけました。
見出しだけではなく、その言葉を内容に含んでいるページも載っています。
探すページを絞り込むことができたので、後は、そのページを順番に見ていくだけです。

検索処理でのインデックスも、概ね、このようなことをやってます。



次に、インデックス以外の高速化の話。
やり方はいろいろありますが、一番大事なのは、分散処理です。

今度は、一冊だけじゃなく、十巻セットくらいの百科事典を想像しましょうか。
索引を使って、どこにありそうなのかを調べるところまでは一緒です。
索引から、一冊だけではなく、複数の巻にあることが分かりました。
ずいぶん絞り込まれているので、同じように順番に調べて行けば良いのですが、もっと早く探す方法はないでしょうか?

おや、弟くんが暇そうにしていますね。
彼にも手伝ってもらいましょう。
同時に二人で調べれば、半分の時間で探せそうです。

実際の検索処理では、複数の検索処理を大量にこなさなくちゃいけないので、こんなに単純ではありませんが、原理は分かりやすいですよね。

他1件のコメントを見る
id:a-kuma3

「インデックスをどう作るか」という面では、それ用のアルゴリズムが研究されてます。
例えば、形態素解析 とか。

2012/07/28 15:53:36
id:tsuka115

なるほど~ なかなか難しそうなお話ですね

2012/07/29 03:04:41
id:kitiko No.3

kitiko回答回数463ベストアンサー獲得回数422012/07/28 15:11:38

ポイント5pt

googleアルゴリズムは、最近こんなものを取り入れたようですね。

検索結果の表示順位を決定するアルゴリズムにサイトの応答速度を取り入れると発表した。
Googleの検索アルゴリズムは、検索語との関連性や被リンク数など、

さまざまな要素に基づいてランキングを決定している。

Googleはサイトの応答速度がユーザーにとって非常に重要と考えることから、

この要素をアルゴリズムに加味することにしたという。


つまりあまりに重いサイトは検索から除外するというアルゴリズムを導入したということです。

http://netsupman.com/affili/296.html

id:tsuka115

どーもです。

これはどちらかというと検索の高速化の方法というより、SEO関連のお話ですね。
しかし、そんな情報があるとは知りませんでした。
遅いサーバーは使うなってことですか・・・

2012/07/28 15:19:41
id:oil999 No.4

oil999回答回数1728ベストアンサー獲得回数3202012/07/28 20:10:20

ポイント20pt

インデックス作成型全文検索という仕組みで行います。

まず、処理の対象となるコンテンツを単語に分解します。
そして分解した単語をインデックスと呼ばれるデータベースに登録していきます。

あとは、単語をキーにしてデータベースを検索していきます。

この2段階の処理に対しては、さまざまなシステムが出回っています。
古典的なシステムとしてはNamazuがあります。
http://www.namazu.org/

id:tsuka115

どーもです

Namazuは使ったこと有りますが、内容は良くわかってませんでした。
要はデータベースで検索すると早いということだと思いますが
なぜデータベースにすると早くなるのでしょう?
そういうもんだと理解するしか無いんでしょうか?

2012/07/29 03:08:34
id:oil999

データベースは、キー(全文検索の場合はインデックスにしている「単語」)を高速に検索するという仕組みを内蔵しているからです。

2012/07/29 16:45:34
id:Artisan No.5

Artisan回答回数12ベストアンサー獲得回数32012/07/28 23:46:43

ポイント20pt

検索エンジンはさまざまなアプローチがあり、また様々な技術の寄せ集めですのでどうしても解説を行おうとすると下記URLのように総華的になりがちかと思います(勉強に時間がかかる)。また、Googleのようなとしてしまうと少し技術的に特徴があるので、初学者はますます混乱してしまうかもしれません。

連載:検索エンジンはいかにして動くのか?|gihyo.jp … 技術評論社
連載:検索エンジンを作る|gihyo.jp … 技術評論社
ASCII.jp:Googleはなぜ的確に探せるのか?

私は専門家ではないのですが、

・転置インデックス
・Suffix Array

に絞って調べるのがよいとおもいます。これらアルゴリズムで索引さえ作れば、ごくごく簡単な検索エンジンくらいは作れるのではないかと思います。(ただ、このアルゴリズムは恐らくGoogle使ってないんだけどね…)

また調べれば分かると思いますが、転置インデックスで検索エンジンを作ろう的なブログエントリもあるので是非とも参考にしてみてください。

検索エンジンを利用したいだけならば、Apache Solrを始めとする優れたオープンソース・ソフトウェアがあるので参考にしてみてください。

id:tsuka115

どーもです

なるほど、なかなか奥が深いのがわかりました。

特に今すぐ何か作ろうとかそういうのではないんですが、ふとした疑問で
そのカラクリを少しでも知っていれば将来何かの時に役立つかも知れない
という理由で質問してます。

2012/07/29 03:17:48
id:pretaroe No.6

pretaroe回答回数531ベストアンサー獲得回数752012/07/29 00:59:39

ポイント20pt

ご存じのとおり、
データの検索(データベース)という概念でなくて
文書検索(全文検索)という概念です。

ただ、全文検索なんですが
grepとかのようなイメージで毎回全文をなめるのは時間がかかりすぎるということで
インデックスがあるわけです。

インデックスがあると
データをなめる量がへるからという単純な面があるので
それで早くなります。


インデックスがあると、データベースの概念で扱うことも可能になります。

以前は、データベースは全文検索を苦手としてきましたが、
ある程度はできるように、なってきています。
http://oracletech.jp/products/pickup/000257.html


インデックス手法としては、ORACLEは
B*TREE 索引 を使ってるようです。

id:tsuka115

どーもです

かなり難しい話ですね。自分は専門家じゃないので良くわからないです。
要はデータベースのインデックスを使うと早くなるってことなんでしょうか?

例えば 「この内容で登録する」 という文章を例にした場合
「内容」とか「登録」とかで検索するより「内容」を0、「登録」を1という
インデックスにすれば、文字数が減って検索が早くなるようなことなんでしょうか?

2012/07/29 03:27:36

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません