検索エンジンを実装 (6)NOT演算
· 約3分
今回は集合演算のNOT演算ついて紹介します。この処理は、例として検索の際に「sky NOT rain」と指定すると、"sky"というキーワードを含むページから"rain"を含むページを除きます。
NOT演算処理の概要
上の図から、ある2つの語の転置インデックスリストをA, Bとします。ここで、リスト要素をそれぞれa, b(整数)とし演算結果を格納するリストをCとするとき、NOT演算は主に以下の処理内容を繰り返します。
- if a < b then 要素aをCの末尾に追加し、aにリストAの次の要素を代入
- if a = b then A, Bが指す次の要素をa, bに代入
- if a > b then bにリストBの次の要素を代入
ソースコード
今回はNOT演算処理を行う部分(メソッド)のみを示します。後で示す実行結果は、前のブログラムをベースにintersect()メソッドの挿入箇所を今回のものに置き換えたものです。
import java.util.ArrayList;
/**
* 検索エンジンのNOT演算
*/
public class BooleanRetrieval {
/**
* NOT演算処理
* @param postsSet 全ての検索語の転置インデックスリスト
* @return 演算後の転置インデックスリスト
*/
public static ArrayList<integer> subtract(ArrayList<arrayList<integer>> postsSet) {
ArrayList<integer> result; // 最終演算結果
if (postsSet == null) return null;
int len = postsSet.size();
if (len == 0) return null;
else if (len == 1) return postsSet.get(0);
result = postsSet.get(0);
for (int i = 1; i < len; i++) {
result = subtract(result, postsSet.get(i));
}
return result;
}
public static ArrayList<integer> subtract(ArrayList<integer> p1, ArrayList<integer> p2) {
ArrayList<integer> answer = new ArrayList<integer>(); // 2語の演算結果
int len1 = p1.size();
int len2 = p2.size();
int i=0, j=0;
while (i<len1 && j<len2) {
int diff = p1.get(i) - p2.get(j);
if (diff == 0) {
i++; j++;
} else if (diff < 0) {
answer.add(p1.get(i));
i++;
} else {
j++;
}
}
while (i<len1) { answer.add(p1.get(i++)); }
while (j<len2) { answer.add(p2.get(j++)); }
return answer;
}
}
単語 freq, docID
15 : 1, [2]
5 : 1, [2]
After : 1, [1]
As : 1, [1]
I : 3, [0, 1, 2]
＜中略＞
that : 1, [2]
the : 3, [0, 1, 2]
think : 3, [0, 1, 2]
this : 1, [2]
time : 2, [0, 2]
to : 2, [0, 1]
touch : 1, [1]
tremendously : 1, [1]
uncertainty : 1, [1]
use : 1, [2]
vigorous : 1, [1]
wanna : 1, [1]
well : 1, [1]
what : 1, [0]
when : 1, [1]
where : 1, [0]
why : 1, [1]
with : 1, [1]
検索語: the think
結果 :文書中に存在しません。
検索語: the use
結果 :文書ID [0, 1]に存在します。
検索語: the to
結果 :文書ID [2]に存在します。
検索語: quit
おー、けっこうたのしくなってきましたねー。
