第12回 索引の分散 | gihyo.jp
はじめに GoogleなどのWeb検索エンジンでは、2004年ごろには数10Tバイトの索引を数万台のサーバに分散させていたと言われています。これは、大量のデータを索引化したり大量のクエリを捌く必要がある際に、1台のマシンでは十分な速度が出ないことがあるためです。近年のハードウェアの進化はめまぐるしいですが、それでもハードウェアによるスケールアップには限界があるため、大規模な検索エンジンにおいて検索処理をスケールさせるには複数台のマシンの利用が不可欠となります。今回は、転置索引の複数のサーバへの分散方法について見ていきます。 複数台サーバにおける転置索引 複数のサーバを利用して検索処理を高速化させる方法には、索引のレプリケーション（replication）と索引の分散（distribution）の2つがあります。索引のレプリケーションとは、複数台のマシンに同じ転置索引（のコピー）を配置する方
第10回 動的な索引構築 | gihyo.jp
はじめに 今回からは、近年の話題や少し発展した話題について触れていく予定です。 第7回では、転置索引の静的な構築方法について触れました。今回は、索引に対して文書のインクリメンタルに追加していく方法について触れていきます。 動的な索引構築の必要性 第7回の復習になりますが、索引の構築方法には"静的"な方法と"動的"な方法が存在します。英語ではそれぞれ、Offline Index Construction、Online Index Constructionと呼ばれています[1]。 文書が頻繁に追加される場合や索引が大規模な場合、文書の追加の度に索引を作り直すことは非常に高コストとなり現実的ではありません。このような場合は、動的な構築方法により索引をインクリメンタルに更新していくことで対応することができます。情報が絶えず追加されている近年のWeb上では、とても重要な構築方法となります。 メモリ
第9回 検索エンジンの開発にあたって | gihyo.jp
はじめに 前回までで、検索エンジンの基本となる仕組みの大枠は説明しました。 今回は、復習を兼ねてこれまでの連載全体を見ていき、検索エンジンを作る上で説明が足りなかった部分を補足していこうと思います。本連載では実際のコードはあまり載せられませんが、ぜひこの際に簡単な検索エンジンを作ってみることをお勧めします。 全体の構成 第2回で紹介した検索エンジンの構成をもう一度見てみましょう。 図1 検索エンジンの構成 検索エンジンは索引とその索引を構築する部分、そしてその索引を検索する部分の3つに分けられることを説明しました。本連載では、索引に関しては第3～6回、構築方法に関しては第7回、そして検索方法に関しては前回の第8回でそれぞれ説明してきました。各項目をとても足早に説明してきましたが、一応全部の要素がカバーされていますので、これまでの知識を使って簡単な検索エンジンを作ることはできてしまいます。
第8回 転置索引における検索処理 | gihyo.jp
代表的な関連度指標には、コサイン類似度（cosine similarity）やOkapi BM25などがあります。具体的な計算式や詳細はここでは省略しますが、上記の値を組み合わせて、関連度を計算します[3]。 コサイン類似度は、文書とクエリをタームを次元としたベクトル空間にマップし、文書ベクトルとクエリベクトルの成す角度により、文書とクエリの関連度（類似度）を求めます（成す角度が小さければ関連度が高い）。またOkapi BM25は、文書がクエリに対して適合かどうかは確率的に決定されるという統計的な原理に基づき、文書とクエリの関連度を求めます。 検索時にこれらを計算するには、索引の構築時に上記の統計値を計算し保持しておく必要があります。実装にはさまざまな方法が考えられますが、たとえばfd,tはポスティングリストの中に埋め込んでおき[4]、ftやFtは辞書と一緒に保存しておくといった方
第7回 転置索引の構築 | gihyo.jp
はじめに これまで、転置索引の構造や具体的なデータ構造を見てきました。今回は、検索したいテキスト文書から、どのようにこの構造を構築するかを説明していきます。 ディスクベースの構築方法 第3回では、表を作成しそれを転置させることで転置索引を構築しました。実際にコンピュータに処理をさせる場合も、メモリ上の2次元配列で同様に構築することが可能となります。しかし、通常の転置索引は非常に疎な表となるため、この方法ではメモリを使いすぎてしまいます。また、リンクリストなどのメモリ上でのデータ構造を用いることにより、上記の方法と比較して少ないメモリ量で構築することもできます。 これらの方法はいずれも、対象とする文書集合を変換した転置索引が実メモリに収まる場合にのみ可能となる方法となります。しかし多くの場合、転置索引は実メモリよりも大きくなります。そのような場合はディスクを用いた構築方法が必要となり、効率的
第6回 日本語における転置索引 | gihyo.jp
はじめに 前回までの数回では、転置索引の論理的構造や実装のための具体的なデータ構造について見てきました。今まで特に触れてきませんでしたが、これらの説明はすべて英語の文書を対象としたものでした。 英語は単語の間に空白を置くため、文を空白で区切ることで単語を抽出することができます。しかし、日本語の文では各単語はつながっているため、日本語で転置索引を構築する場合は英語と同じように、文を単語や文字の並びに分けてあげる必要があります。今回は、その方法について説明します。 文を単語や文字の並びに分割する方法 日本語のように単語が空白で区切られていない文を単語に分割するには、大きく分けて以下の2つの方法があります[1]。 形態素解析による分割 N-gram（q-gram）による分割 以下では、それぞれについて説明していきます。 形態素解析による分割 形態素解析（Morphological Analys
第5回 転置索引の実装 | gihyo.jp
はじめに 前回、前々回と転置索引の論理的構造について見てきました。今回は、転置索引の具体的なデータ構造や実装について説明していきます。 辞書の実装 辞書は通常、単語に対応した情報を高速に取得するために、ハッシュや木構造などのデータ構造を取ります。現在は, 安定した性能や単語の順序関係を利用したいなどの理由で、木構造のデータ構造が使われることが多いと思います。最も単純な場合、2分探索木（Binary Search Tree）や2分探索（Binary Search）の実装が考えられます。 2分探索（木）による辞書の実装 では、辞書の具体的なデータ構造について、図を交えて解説していきましょう。 前回も触れましたが、辞書には単語とその単語に対応するポスティングリストの位置情報のペア（のリスト）が格納されています。単語で検索をするので、ペア自体は単語をキーとして並び換えられます。 たとえば, 前回の
第4回 転置索引の詳細 | gihyo.jp
前回は転置索引の概要を説明しました。今回は転置索引をもう少し詳しく見ていきます。 転置索引＝辞書＋転置リスト 転置索引は大きく分けて2つの部分から構成されています。文書に出現する単語のリストである「辞書」と、その辞書にある各単語がどの文書に出現するかを表したポスティングリストの集合の「転置リスト」からなります（図1）。ポスティングリストやポスティングに関しては前回簡単に説明しましたが、図を見て再度確認してください[1]。 図1 転置索引の構成 辞書は単語だけでなく、その単語に対応するポスティングリストの位置情報を含んでいます。よって、辞書を探索することで、該当する単語のポスティングリストを取り出すことが可能となります。 一方、ポスティングリストは、どの文書に出現するかを表すのに最低でも文書のID（数値）が必要となります。書籍の場合は、文書はページなのでページ番号が文書IDとなります。
検索エンジンはいかにして動くのか？：第3回 転置索引とは何か？｜gihyo.jp … 技術評論社
はじめに 前回までは、検索エンジンの概要を見てきました。今回からは、全文検索の中核となる索引構造について見ていきます。 第1回の復習になりますが、全文検索には主に2種類の方法がありました。検索したいデータに対して前処理をせず、検索時に文書を走査するgrep型と、あらかじめ索引を作っておいて検索時にその索引を利用する索引型です。今回から数回にわたり、索引型において最も普及している転置索引という索引構造について解説していきます。 転置索引とは さて、転置索引とは何なのでしょうか？ 身近な所で例にあげると、書籍（専門書など）の巻末にある索引は、本における転置索引といえます。巻末には通常、キーワード（単語）とそのキーワードが出てくるページが記載されています。キーワードはアイウエオ順やアルファベット順に並べられているので、探したいキーワードを簡単に見つけることができ、そのキーワードがどのページで言及
第2回 検索エンジンを形作るもの | gihyo.jp
はじめに 前回は、検索エンジンとはどういうもなのか？について簡単に触れました。今回は、システムとしての検索エンジンの概要を見ていきます。 検索エンジンの構成 検索エンジンは他のシステムと同様に、複数のコンポーネントから構成されています。ざっくり分けると以下のようなコンポーネントから構成されています（図1）。 索引構築部（Indexer, インデクサー） 検索部（Searcher, サーチャー） 索引（Index, インデックス） 図1 検索エンジンの構成 たった3つ？と思うかもしれませんが、これは大きな枠組みで分けているからです。もちろん、各コンポーネントは複数のサブコンポーネントから構成されていますので、実際はもう少し複雑になりますが、基本はこの構成となります。 次は、それぞれのコンポーネントで具体的に何を行っているかを見てみましょう。 各コンポーネントの概要 ●索引構築部（Inde
第1回 検索エンジンとは | gihyo.jp
はじめに 検索エンジンと聞くと、みなさんは何を思い浮かべるでしょうか？ GoogleやYahoo!などの検索ページを思い浮かべる方がほとんどだと思います。近年は、それら企業の努力によって検索エンジンというものが非常に身近になり、私たちの生活に欠かせないものとなりつつあります。 しかし、検索エンジンと一言で言っても、上記のような一般の方々へのUI（ユーザインターフェース）を指す場合もあれば、そのUIの裏側（バックエンド）にあるシステムを指す場合もあります。 本連載では、Google,Yahoo!などを代表とする検索エンジンの裏側のしくみに着目し、検索エンジンというシステムのアーキテクチャやその内部で使われているデータ構造やアルゴリズムを、近年の手法や研究事例などを交えて解説していきたいと思っています。 検索エンジンとは 検索エンジンには、さまざまな種類があります。GoogleのWeb検索のよ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
