検索エンジンを実装 (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か形態素辞書などを用いてトークンに区切ることで実現できます。日本語文の区切り方は色々ありますが、中でも簡単な方法は、文字種(英文字、記号、ひらがな、カタカナ、漢字)の違いを区切りの境界と捉える方法です。

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

関連記事 (Related Articles):


コメントを残す