moshimore Knowledge

アプリ開発・紹介とメモ書き、日々の日記。

検索エンジン自作入門 - 検索エンジンはいかにして動くのか(4)

f:id:moshimore:20181127212033p:plain
転置インデックスの実装方法は分かってきました。
次は構築方法について検討していきます。

前回のエントリーの続きになります。
内容が通じない場合があるので、先にこちらをご覧ください。
knowledge.moshimore.jp

転置インデックスを構築する

メモリを用いた転置インデックスの構築

メモリー上で転置インデックスを作成するには大量のメモリーを使用する可能性があります。
その改良方法としては、リンクリストを用いて実装する方法があり、なるべく少ないメモリー量で構築していきます。

二次記憶を用いた転置インデックスの構築

  • ソートに基づくインデックス構築

単語とポスティングのペアを二次記憶に書き出しておきます。
そのペアを単語の辞書順にソートすることでインデックスを構築する方法です。

  • マージに基づくインデックス構築

メモリー上に部分的な転置インデックスを構築して二次記憶に書き出しておきます。
最終的に書き出した転置インデックスをマージすることでインデックスを構築する方法です。

静的なインデックス構築と動的なインデックス構築

これまでのインデックス構築は、固定のデータをバッチ処理にて扱うもので「静的な構築方法(offline index construction)」と呼びます。
それに対して、ネットニュースの検索など変動していくデータを常に扱うものを「動的な構築方法(online index construction/dynamic indexing)」と呼びます。

検索したい文書を用意する

データを集める

検索エンジンにて扱う、検索データはどこに用意されているのでしょうか。
検索対象が個人のパソコン内やファイルサーバー、メール検索などだとしたら既に用意されています。
しかし、対象がウェブ検索であったり、特定のサービス内のデータを外部から取りに行くとしたら、そのための仕組みも構築しなくてはいけません。

データを整形する

集めたデータは、そのまま扱えるデータの場合と扱えないデータがあります。
例えば、HTMLファイルだとしたら、文章検索には必要でないHTMLタグを排除する必要がありますし、WORDやPDFファイルだとしたら内部のファイル構造も確認しなくてはいけません。

書籍の内容は、以下のエントリーで紹介しています。
knowledge.moshimore.jp

以上、検索エンジン自作入門 - 検索エンジンはいかにして動くのか(4)でした。