WhiteDog@Blog: JavaでPatriciaTrieで各種検索

前回からの続きで、今回は検索メソッドを実装してみます。実装するのはこの2つ。

common prefix search
predictive search

common prefix searchは、クエリ"東京国際フォーラム"が与えられた時に、"東"、"東京"、"東京国"、"東京国際フォーラム"をトライから列挙するという検索です(実際これらの単語はWikipedia日本語版にあります)。

上図で赤枠で示したノードをたどりながら、終端ノードを列挙していく処理になります。先頭からノードをたどり、ノードのラベルとクエリを比較し、ノードのラベルを比較し終えたら、終端ノードであれば列挙、そして子ノードから残りのクエリの比較を行う候補を探し、そのノードに対しても同じ処理をしていきます。一方向に辿っていくだけなので再帰は必要なく、単純なループで実現できます。コードを下記に示します。

01public Iterable<String> commonPrefixSearch(String query) {
02 List<String> ret = new ArrayList<String>(); // 結果配列
03 int cur = 0; // query内の照合位置
04 Node node = root;
05 while(node != null){
06  String letters = node.getLetters();
07  if(letters.length() > (query.length() - cur)) return ret; // 残りの文字列よりノードのラベルのほうが長ければマッチしないので終了
08  for(int i = 0; i < letters.length(); i++){
09   if(letters.charAt(i) != query.charAt(cur + i)) return ret;
10  }
11  if(node.isTerminated()){
12   ret.add(query.substring(0 , cur + letters.length()));
13  }
14  cur += letters.length();
15  if(query.length() == cur) return ret;
16  node = node.getChild(query.charAt(cur));
17 }
18 return ret;
19}

単純なwhileループで、着目するノード(変数node)を書き換えながら処理を行なっています。
predictive searchは、指定された文字列(prefix)を前方一致検索します。例えば"東京国"が指定されれば、"東京国"、"東京国税局"、"東京国際フォーラム"、"東京国際マラソン"が列挙されます。

上図赤枠のノードが列挙対象になります。まず指定されたprefixを含むノードを探し、見つかったノード以降のノードを全て列挙します。この列挙は部分木全部が対象になるので、再帰で実装するのが楽です(再帰が嫌な場合はQueue使ってもOK)。コードはこんな感じ。

01/**
02 * 部分木の列挙をする再帰関数。
03 */
04private static void enumLetters(Node node, String prefix, List<String> letters){
05 List<node> children = node.getChildren();
06 if(children == null) return;
07 for(Node child : children){
08  String text = prefix + child.getLetters();
09  if(child.isTerminated()) letters.add(text);
10  enumLetters(child, text, letters);
11 }
12}
13 
14public Iterable<String> predictiveSearch(String prefix) {
15 char[] prefixChars = prefix.toCharArray();
16 int cur = 0; // prefixChars内の照合位置
17 Node node = root;
18 while(node != null){
19  String letters = node.getLetters();
20  int n = Math.min(letters.length(), prefixChars.length - cur); // 共通部分の比較のためnは短い方に合わせる。
21  for(int i = 0; i < n; i++){
22   if(letters.charAt(i) != prefixChars[cur + i]){
23    return Collections.emptyList();
24   }
25  }
26  cur += n;
27  if(prefixChars.length == cur){ // prefixCharsの比較が終われば、あとは部分木の列挙
28   List<String> ret = new ArrayList<String>();
29   prefix += letters.substring(n);
30   if(node.isTerminated()) ret.add(prefix);
31   enumLetters(node, prefix, ret);
32   return ret;
33  }
34  // 比較がまだ終わって無ければ、子ノードを探して検索を継続
35  node = node.getChild(prefixChars[cur]);
36 }
37 return Collections.emptyList();
38}

WhiteDog@Blog

2012/04/13

JavaでPatriciaTrieで各種検索

0 件のコメント: