2012/04/19

パトリシアトライのサイズ比較

 記事が前後しますが。気になったのでちょっと調べてみました。トライの内部形式をchar[]からbyte[]にすることでどれくらいインパクトがあるのか。byte[]にする際、UTF-8、Shift-JIS、EUC、JIS(ISO2022JP)でどのような違いがあるのか。

以下の表にまとめます。

トライのノード文字配列数
エンコーディング(内部形式)サイズサイズ全体サイズ
ISO-2022-JP(byte[])1,763,96758,210,9111,764,14241,189,910123,904,937
UTF-8(byte[])1,736,91057,318,0301,737,08340,404,315123,095,316
Shift_JIS(byte[])1,639,06454,089,1121,639,22935,103,790112,335,651
EUC_JP(byte[])1,633,86553,917,5451,634,03135,089,059112,013,060
UTF-16(char[])1,513,46948,431,0081,515,34635,043,030103,472,496
UTF-16(char[])+フィールド最適化(*1)1,513,469(*3)39,664,136(*4)1,515,33834,688,31291,774,563
UTF-16(char[])+フィールド最適化(*1)+多層トライ(*2)1,995,303(*3)55,082,824(*4)483,714(*5)10,345,546(*5)82,870,660

*1 - 子ノードを持たない/1つだけ/2つ以上、終端である/ないの組み合わせでそれぞれ最適なフィールドを持つノードクラスを使用する。
*2 - ラベルを逆順に持つ圧縮用トライを用意(参考: 多層トライの実験結果 - やた@はてな日記)。本来のトライのノードもその圧縮用トライのノードをフィールドに持つものを使用。
*3 - 全ノードの合計数。
*4 - 全ノードの合計サイズ。
*5 - 文字配列は圧縮用トライ内のもの。本来のトライには文字配列を持たない。

いずれもWikipedia日本語タイトル127.3万件を格納した結果です。フィールド最適化+多層トライのデータでは、圧縮用トライのノードや文字配列のサイズも加算されています。

こうして見てみると、多層トライがいかに圧縮率が高いかと、オブジェクト数の増減がいかにインパクトがあるかがわかります。せっかく多層トライで圧縮したメモリサイズ(24MB)も、ノードオブジェクト数の増加でその効果は半減しています。

結論: Javaではオブジェクト数大事

多層トライの実装はGitHubで公開してます。org.trie4j.trie.patricia.multilayer.MultilayerPatriciaTrieがフィールド最適化と多層トライの実装で、全タイトル挿入後のデータ、挿入してからpack(), morePack()を呼び出した後のデータが表の下2つです。packで多層トライでの圧縮、morePackで多層トライのノードのフィールド最適化を行います(morePack遅いです)。

下記にVisualVMでの主要なオブジェクトのスナップショットを。まずはUTF-16のフィールド最適化のみ。

次にフィールド最適化+多層トライ(もフィールド最適化)。

サイズをオブジェクト数で割るとわかるけど、1オブジェクトで24とか32バイト消費してます。フィールド最適化を行わない場合、40バイト消費することもあります(64bit環境で。32bitなら半分になります。)

結論: Javaではオブジェクト数大事(2回目)

しかしこの画像の小ささ何とかならんかな。

2012/04/13

Trie4J - Java Patricia Trie Implementation

ちょこちょことまとめているパトリシアトライのJava実装ですが、現状のソースをGitHubにあげました。

https://github.com/takawitter/trie4j

記事では簡単のためラベルをString, 子ノードをList<String>で管理しているものを紹介していますが、この実装では
  • ラベルをchar[]、子ノードをNode[]で管理する、org.trie4j.patricia.simple.PatriciaTrie
  • ノードの状態(終端かどうか、子ノードを持つかどうかなど)に応じてクラスを変更し、かつ多層トライによるサイズ圧縮に対応する、org.trie4j.patricia.multilayer.MultilayerPatriciaTrie
の2つが含まれています(もう一つありますが、あまり効果無いのでそのうち消します)。 詳しい解説はまた後ほど(predictive search書けてから)。

JavaでPatriciaTrieで各種検索

前回からの続きで、今回は検索メソッドを実装してみます。実装するのはこの2つ。
  • common prefix search
  • predictive search
common prefix searchは、クエリ"東京国際フォーラム"が与えられた時に、"東"、"東京"、"東京国"、"東京国際フォーラム"をトライから列挙するという検索です(実際これらの単語はWikipedia日本語版にあります)。
上図で赤枠で示したノードをたどりながら、終端ノードを列挙していく処理になります。先頭からノードをたどり、ノードのラベルとクエリを比較し、ノードのラベルを比較し終えたら、終端ノードであれば列挙、そして子ノードから残りのクエリの比較を行う候補を探し、そのノードに対しても同じ処理をしていきます。一方向に辿っていくだけなので再帰は必要なく、単純なループで実現できます。コードを下記に示します。
public Iterable<String> commonPrefixSearch(String query) {
 List<String> ret = new ArrayList<String>(); // 結果配列
 int cur = 0; // query内の照合位置
 Node node = root;
 while(node != null){
  String letters = node.getLetters();
  if(letters.length() > (query.length() - cur)) return ret; // 残りの文字列よりノードのラベルのほうが長ければマッチしないので終了
  for(int i = 0; i < letters.length(); i++){
   if(letters.charAt(i) != query.charAt(cur + i)) return ret;
  }
  if(node.isTerminated()){
   ret.add(query.substring(0 , cur + letters.length()));
  }
  cur += letters.length();
  if(query.length() == cur) return ret;
  node = node.getChild(query.charAt(cur));
 }
 return ret;
}
単純なwhileループで、着目するノード(変数node)を書き換えながら処理を行なっています。
predictive searchは、指定された文字列(prefix)を前方一致検索します。例えば"東京国"が指定されれば、"東京国"、"東京国税局"、"東京国際フォーラム"、"東京国際マラソン"が列挙されます。
上図赤枠のノードが列挙対象になります。まず指定されたprefixを含むノードを探し、見つかったノード以降のノードを全て列挙します。この列挙は部分木全部が対象になるので、再帰で実装するのが楽です(再帰が嫌な場合はQueue使ってもOK)。コードはこんな感じ。
/**
 * 部分木の列挙をする再帰関数。
 */
private static void enumLetters(Node node, String prefix, List<String> letters){
 List<node> children = node.getChildren();
 if(children == null) return;
 for(Node child : children){
  String text = prefix + child.getLetters();
  if(child.isTerminated()) letters.add(text);
  enumLetters(child, text, letters);
 }
}

public Iterable<String> predictiveSearch(String prefix) {
 char[] prefixChars = prefix.toCharArray();
 int cur = 0; // prefixChars内の照合位置
 Node node = root;
 while(node != null){
  String letters = node.getLetters();
  int n = Math.min(letters.length(), prefixChars.length - cur); // 共通部分の比較のためnは短い方に合わせる。
  for(int i = 0; i < n; i++){
   if(letters.charAt(i) != prefixChars[cur + i]){
    return Collections.emptyList();
   }
  }
  cur += n;
  if(prefixChars.length == cur){ // prefixCharsの比較が終われば、あとは部分木の列挙
   List<String> ret = new ArrayList<String>();
   prefix += letters.substring(n);
   if(node.isTerminated()) ret.add(prefix);
   enumLetters(node, prefix, ret);
   return ret;
  }
  // 比較がまだ終わって無ければ、子ノードを探して検索を継続
  node = node.getChild(prefixChars[cur]);
 }
 return Collections.emptyList();
}