タグ別アーカイブ: Search Engine

検索エンジンを実装 (6)NOT演算

今回は集合演算のNOT演算ついて紹介します。この処理は、例として検索の際に「sky NOT rain」と指定すると、”sky”というキーワードを含むページから”rain”を含むページを除きます。

NOT演算処理の概要

NOT演算結果

上の図から、ある2つの語の転置インデックスリストをA, Bとします。ここで、リスト要素をそれぞれa, b(整数)とし演算結果を格納するリストをCとするとき、NOT演算は主に以下の処理内容を繰り返します。

  1. if a < b then 要素aをCの末尾に追加し、aにリストAの次の要素を代入
  2. if a = b then A, Bが指す次の要素をa, bに代入
  3. if a > b then bにリストBの次の要素を代入

ソースコード

今回はNOT演算処理を行う部分(メソッド)のみを示します。後で示す実行結果は、前のブログラムをベースにintersect()メソッドの挿入箇所を今回のものに置き換えたものです。

NOT演算の実行結果

おー、けっこうたのしくなってきましたねー。

検索エンジンを実装 (5)OR演算

前回がAND演算でしたので今回はOR演算ついて紹介します。今記事で紹介している演算アルゴリズムよりも高効率なものは存在するようですが、今回は割愛します。

OR演算処理の概要

OR演算結果

上の図から、ある2つの語の転置インデックスリストをA, Bとします。ここで、リスト要素をそれぞれa, b(整数)とし演算結果を格納するリストをCとするとき、OR演算は主に以下の処理内容を繰り返します。

  1. if a < b then 要素aをCの末尾に追加し、aにリストAの次の要素を代入
  2. if a = b then 要素aをCの末尾に追加し、A, Bが指す次の要素をa, bに代入
  3. if a > b then 要素bをCの末尾に追加し、bにリストBの次の要素を代入

ソースコード

今回はOR演算処理を行う部分(メソッド)のみを示します。後で示す実行結果は、前回ブログラムをベースにintersect(postsSet)の箇所を今回のものに置き換えたものです。

OR演算の実行結果

おー、なんだかもりあがってきましたねー。

話は変わりますが、最近よく実感していることの一つに、ソフトウェアの仕様が変更されると場合によっては設計を根本から変える必要があること。

そして、手がけているソフトウェアが今後アップグレードを繰り返していくと予測できるなら、現時点で取り組んでいる設計に費やす時間はほどほどに、ということです。OO分析設計を用いて保守性・拡張性を高めるのもいいけれど、その設計上での拡張が今後の仕様変更に耐えうるとは限りません。

勿論、最初の設計が肝心であることには変わりないですけれど。それでも留意。

検索エンジンを実装 (4)AND演算

AND演算処理の概要

AND演算結果

上の図から、ある2つの語の転置インデックスリストをA, Bとします。ここで、要素をそれぞれa, b(整数)とし演算結果を格納するリストをCとするとき、AND演算は主に以下の処理内容を繰り返します。

  1. if a < b then aの次の要素をaに代入
  2. if a = b then 要素aをCの末尾に追加しA, Bが指す要素を一つ進める

プログラムの主な処理内容

  1. 検索対象テキストを単語に分割。
  2. 単語を転置インデックスに登録。ここで、1単語あたりに格納する情報は、その単語の出現頻度とその文書ID。転置インデックスのデータ構造はTreeMapを使用しkeyに単語、valueはIndexRecordでputします。
  3. ユーザからの標準入力をパースしAND演算(Intersectメソッドで実現しています)。

以下に、ソースコードと実行結果を示します。

IndexRecord.java

1つのトークン(単語)に対するインデックス情報(docIDリストや出現頻度情報)

BooleanTest.java (AND演算のテストプログラム)

FreqComparator.java (ArrayList要素のソート用)

実行結果

おー、なんだか楽しくなってきましたね。

文字列の区切り方

今回は検索対象テキストを英文に絞ったため、テキスト中の空白文字で区切ることでトークンを抽出できました。対して、日本語テキストの場合は区切り記号等は無い為、n-gramか形態素辞書などを用いてトークンに区切ることで実現できます。日本語文の区切り方は色々ありますが、中でも簡単な方法は、文字種(英文字、記号、ひらがな、カタカナ、漢字)の違いを区切りの境界と捉える方法です。

余談ですが、ブラウザやエディタ等で文字の上でダブルクリックするとカーソル下の文字列が選択状態になりますが、その範囲を決定する際に上述の方法が応用されているようです。ソフトによってはトリプルクリックするとカーソル下の行全体が選択状態になります(使うと編集が楽です)。

検索エンジンを実装 (3)文書内の検索語を特定

今回実装したことは、

  • IndexRecordクラスにフィールド更新用のメソッドやハッシュフィールドを追加(今後改善の必要大)。
  • 検索語を含んでいるファイルをピックアップする(色々と無駄な部分あり)。

辺りです。

後述に現在の問題点とその解決案を考えてみましたが、先ずはソースコードと実行結果(デバッグプリント)を示します。

追記:こちらに→ 検索エンジンを実装 (4)AND演算 完成版を書きましたので、そちらをご覧ください。↓以下、黒歴史(>_<)↓

IndexRecord.java

Make2Gram.java

実行結果(コマンドライン引数部分は省略)

現在の問題点

IndexRecordクラス:ArrayList型ではフィールド(ファイルidと出現位置)の関係性を取りづらい。

解決案

IndexRecordクラスのフィールドにファイルidを主キーとして、その部分単語の全ての出現位置を求められるハッシュデータが必要かと考えました。

今回もうすうすは感じていましたが、データ構造を設計し間違えるとプログラム構造が煩雑になりやすいです。初めから仕様を明確にしておけばデータモデリングでミスることもなかったかな。

しばらくは、今後の実装機能の洗い出しとそれに対応できるクラス構造を考えてみようかな。また、N-gramに分割する処理部分は別クラスのインスタンスメソッドとしてまとめたほうが良いですね。並行してデザインパターンも復習しておこう。

検索エンジンを実装 (2)出現位置とその文書ID

id:d-kamiさんから改良版Make2Gram付きトラックバックを頂きました(連絡方法がわからんのでトラックバックで – マイペースなプログラミング日記)(はてなダイヤリーから移転前)。d-kamiさん、ありがとうございます。

上記のページにあるコードから、TreeMapやsubstringを用いたbigramの切り出し・カウント方法などを学ばせて頂きました。

さて、今回の実装その2は以下の機能を加えました。

  1. コマンドライン引数にディレクトリ名を指定して、そのディレクトリ以下のファイル全てを処理の対象とする。
  2. N-gram情報には文書IDと部分文字列の出現位置を格納するようにデータ構造の拡張。

続きを読む