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();
}

JavaでPatriciaTrieを実装してみた

書籍「日本語入力を支える技術」を読んでテンション上がったので、Javaでパトリシアトライを実装してみました(本当はビットベクタを実装したかったけどとりあえずダブル配列からやろうと思ってそれでも挫折してPatriciaTrieから入門した次第)。また、このエントリで紹介するコードはパトリシアトライの説明用で、全然最適化が行われていないので、メモリ効率も速度も良くないです。そのあたりを最適化したコードは、別のエントリで紹介する予定です。

(↓※アソシエイトIDあり)

ちなみにPatriciaはPractical Algorithm to Retrieve Information Coded in Alphanumericの略らしい(参考: wikipedia:基数木)。構造は至ってシンプルで、いろいろと実装例があります。

• Algorithms with Python: トライ (trie) とパトリシア (patricia tree)
• PATRICIA in Java
• 404 Blog Not Found: Patricia Trie (Radix Trie) を JavaScript で

wikipediaのパトリシアトライの説明から図を借りると、その構造はこんな感じ:

ちょっとわかりにくいので、形を変えてみると:

空間効率的には、上図右側の各文字列の灰色で示した部分が他の文字列と共有されるので、かなりデータ量は小さくて済みます(wikipedia日本語タイトルデータで50%程度の効率化)。また、検索効率は、検索したい文字列を先頭から順に探して行くだけなので、最悪O(k)で済みます(kは文字列長)。実際は子ノードの探索方法によっては検索速度に影響が出るけど、それはまた後で。

構造がわかったところで、それを表現するクラスを定義します。

public class Node{
 // コンストラクタ、getter、setterは割愛
 private String letters;
 private List<node> children;
 private boolean terminated;
}

各ノードで保持する文字列は変数lettersに、子ノードは変数childrenに格納します。加えて、そのノードで文字列が終わっているかどうかを保持する変数terminatedを設けます。これは、例えば上図の文字列に加え、"rom"や"rubic"が加わった場合、ツリーの途中で文字列が終わることになるので、それに対応するため。上図に、文字列の終端という概念を加えて、あとツリーの途中で文字列が終わるケースを示すために"rom"と"rubic"も挿入されたとして、終端のノード(terminated==true)を太枠で表すと、下図のようになります。

終端については、終端文字列を設けて('$'とか)、それを終端となるノードにぶら下げるのが一般的のようなんですが、コードをシンプルにしたかったので、上記実装にしました(実際はいくつか工夫の余地はあり、今できるだけメモリを使わない方法をトライ中なんですが、それは完成した後に詳しく書く予定)。

さて、まずはある文字列がトライに含まれるかどうかを判定する、containsメソッドを実装してみます。考え方としては、

1. 自ノードに文字列が設定されている場合、検索文字列との比較を行う。
2. 自ノードの文字列だけでは比較が終わらない場合、子ノードを探す。
3. 子ノードが見つかった場合、子ノードに対して同じ操作を行う

という感じで、検索対象文字列の先頭から、ノード内の文字列との比較を行い、どんどん子ノードに降りて行きます。コードは下記。

boolean contains(String word){
 int rest = word.length();
 int n = letters.length();
 if(n > rest) return false; // 自ノードの文字列のほうが長ければ比較失敗。
 for(int i = 0; i < n; i++){
  if(letters.charAt(i) != word.charAt(i)) return false;
 }
 if(n == rest) return terminated; // 文字列が同じであれば、終端かどうかを返す。
 word = word.substring(n); // 比較済み文字列を捨てる。
 if(children != null){
  char c = word.charAt(0); // 子ノードを探す。(*1)
  for(Node n : children){
   if(n.letters.charAt(0) == c){
    return n.contains(word); // 見つかれば、containsを呼び出す。
   }
  }
 }
 return false;
}

自ノードの文字列(letters)、子ノード(children)の順で処理を行なっています。子ノードの検索(*1)は線形探索していて、当然遅いので、実用で使うには、頻度順に並べるとか、childrenはソートしておいて2分探索を使うとか、ハッシュを使うとかする必要がありますが、今は割愛。データ量が膨大になる場合は、各ノードでハッシュを持つとメモリ消費が問題になる可能性があるので、2分探索か頻度順が現実的かと思います(そのぶん構築コストは高いけど)。実際wikipediaの日本語タイトルを挿入してみると、線形探索と2分探索では、処理にかかる時間の桁が違いました(50万件の検索で線形探索1762ms, 2分探索201ms)。

ちなみに2分探索だと、コードは下記のようになります。

boolean contains(String word){
 int rest = word.length();
 int n = letters.length();
 if(n > rest) return false; // 自ノードの文字列のほうが長ければ比較失敗。
 for(int i = 0; i < n; i++){
  if(letters.charAt(i) != word.charAt(i)) return false;
 }
 if(n == rest) return terminated; // 文字列が同じであれば、終端かどうかを返す。
 word = word.substring(n); // 比較済み文字列を捨てる。
 if(children != null){
  char c = word.charAt(0); // 2分探索で子ノードを探す
  int end = children.size();
  int start = 0;
  while(start < end){
   int i = (start + end) / 2;
   Node child = children.get(i);
   int d = c - child.getLetters().charAt(0);
   if(d == 0){
    return child.contains(word);
   }
   if(d < 0){
    end = i;
   } else if(start == i){
    break;
   } else{
    start = i;
   }
  }
 }
 return false;
}

次に要素の挿入です。おおまかに以下の流れで実装しました。

1. ノード内の文字列(thisLetters)か比較対象の文字列(letters)の短い方の文字数分比較
2. 全て比較成功
   1. thisLettersとlettersの長さが同じであれば、ノードを終端にして(terminated = true)終了(a)
   2. thisLettersの方が長ければ、ノードを分割して終了(b)
   3. lettersの方が長ければ、比較済み文字列を捨てる
   4. 新しいlettersの先頭文字とマッチする先頭文字を持つ子ノードを探す
   5. 存在すれば、その子ノードに対してinsertChildを呼び出して終了(c)
   6. 存在しなければ、新しい子ノードを作成して追加し終了(d)
3. 途中で比較が止まった場合、その位置でノードを分割し、lettersの残りも子ノードとして追加する。(e)

コードは下記のようになります。

public void insertChild(String letters){
   int n = Math.min(letters.length(), this.letters.length());
   int i = 0;
   while(i < n && (letters.charAt(i) == this.letters.charAt(i))) i++;
   if(i == n){
    if(letters.length() == this.letters.length()){
     terminated = true; // (a)
     return;
    }
    if(letters.length() < this.letters.length()){
     Node node = new Node( // (b)
       this.letters.substring(letters.length())
       , this.children, this.terminated);
     this.letters = letters;
     this.children = new ArrayList<Node>(1);
     this.children.add(node);
     ((ArrayList<Node>)this.children).trimToSize();
     this.terminated = true;
     return;
    }
    letters = letters.substring(i);
    int index = 0;
    for(Node child : children){
     int c = letters.charAt(0) - child.letters.charAt(0);
     if(c < 0) break;
     if(c == 0){
      child.insertChild(letters); // (c)
      return;
     }
     index++;
    }
    this.children.add(index, new Node(letters)); // (d)
    ((ArrayList<Node>)this.children).trimToSize();
    return;
   }
   String newLetter1 = this.letters.substring(0, i); // (e)
   String newLetter2 = this.letters.substring(i);
   String newLetter3 = letters.substring(i);
   List<Node> newChildren = new ArrayList<Node>(2);
   if(newLetter2.charAt(0) < newLetter3.charAt(0)){
    newChildren.add(new Node(newLetter2, this.children, this.terminated));
    newChildren.add(new Node(newLetter3));
   } else{
    newChildren.add(new Node(newLetter3));
    newChildren.add(new Node(newLetter2, this.children, this.terminated));
   }
   this.letters = newLetter1;
   this.terminated = false;
   this.children = newChildren;
  }

なお、子ノードは全て昇順でソートされるようにして、探索は線型探索を使っています(ここも2分探索にすれば高速化できる)。また、メモリ利用量を抑えるため、子ノードの配列は正味のサイズだけ確保するようにしています(その分メモリリアロケーションが増えて速度は落ちているはず)。

ちなみに、上記のコードでは、VMの最大メモリ容量が128MBだと、Wikipedia日本語タイトル(127万件)はメモリに載りません(180MB程度必要です。ちなみにlettersをchar[]に、childrenをArrayListではなくNode[]に変えれば載ります)。ですが、まぁ一応機能はするので、次はTrieの特徴であるcommon prefix searchを実装してみます。

Slim3 JSON機能の説明(非公式)

(2/7更新)
(2/26更新)
(12/22更新 @Jsonはフィールド直接指定になりました)

Slim3 JSON機能のドキュメントを書き始めました。まだ非公式なものですが、ひと通り書き終わったら公式へのマージを提案する予定です。でも、公式は英語なんですよね。どうしたものか。まぁ、いきなり下手な英語で書くより、まずは日本語でちゃんと書いたほうが良いはず。

というわけで、下記ドキュメントの草案です。若干改行が変ですが、evernoteに書きなぐってexportしたものを貼っつけてるためだと思います。これにあとJSON入出力のカスタマイズ方法を書いて一段落とする予定です。(書きました!)

概要

　Slim3のJSON機能は、モデル(@org.slim3.datastore.Modelアノテーションが付加されたクラス)のJSON変換機能を提供します。JSON変換は、org.slim3.datastore.ModelMeta<M>に定義される以下のメソッドを呼び出すことにより行われます。

モデルのJSON文字列への変換:

• String modelToJson(Object model);
• String modelToJson(Object model, int maxDepth);
• String modelsToJson(Object[] models);
• String modelsToJson(Object[] models, int maxDepth);

JSON文字列のモデルへの変換:

• M jsonToModel(String json);
• M jsonToModel(String json, int maxDepth);
• M[] jsonToModels(String json);
• M[] jsonToModels(String json, int maxDepth);

　例えばTestModelというモデルに対してJSON変換機能を使用するコードは、次のようになります。

TestModel m = new TestModel();
m.setValue(1);
String json = TestModelMeta.get().modelToJson(m);
System.out.println(json); // {"value": 1}
TestModel m2 = TestModelMeta.get().jsonToModel(json);
Assert.assertEquals(m.getValue(), m2.getValue());

JSON変換の制御

　フィールドにJSONアノテーション(@org.slim3.datastore.json.JSON)を指定することで、JSON変換の振る舞いを変更できます。以下にJSONアノテーションで指定できるパラメータを示します。

パラメータ名	型	デフォルト	説明
ignore	boolean	false	このアトリビュートを無視します。JSON出力に含まれず、JSON入力時にも読み込まれません。
ignoreNull	boolean	true	アトリビュートがnullの場合、何も出力しません。falseの場合は、"null"が出力されます。
alias	String	空文字列	アトリビュートのJSON文字列内での名前を指定します。
coder	Class<? extends JsonCoder>	Default.class	JSON入出力を行うJsonCoderのクラスを指定します。ここに独自のクラスを指定することで、JSON入出力のカスタマイズを行うことができます(後述)。

　例えばプロパティを無視したり、エイリアスを設定したりする場合、以下のように記述します。

@Model
class TestModel{
  ...
  @Json(ignore=true)
  private String ignoredValue;
  @Json(alise="foo")
  private String bar;
}

対応する値型

　Slim3のJSON変換機能は、以下の値型に対応します。また、後述するカスタマイズを行えば、これ以外の型に対応したり、入出力方法を変更する事ができます。

Javaクラス	JSON表現	例
java.lang.String, com.google.appengine.api.datastore.Text	文字列。cipher=trueの場合、JSON内では暗号化されます。	"text":"hello"
byte[], com.google.appengine.api.datastore.ShortBlob, com.google.appengine.api.datastore.Blob	バイト列のBase64文字列。	"blob":"mMB4qZAgtBKJq0d1LBGTCA=="
boolean, java.lang.Boolean	ブール値(true or false)。	"value":true
short, java.lang.Short, int, java.lang.Integer, long, java.lang.Long	整数。	"value":100
float, java.lang.Float, double, java.lang.Double	小数。	"value":1.0
java.util.Date	整数(Date.getTime()が返す値)。	"value":10233400
java.lang.Enum	文字列(Enum.name()が返す値)。	"value":"MONDAY"
com.google.appengine.api.users.User	ネストしたJSON文字列(User.getEmail()等の値をJSONエンコード)。	"user":{"authDomain":"authDomain","email":"user@test.com"}
com.google.appengine.api.datastore.Key	文字列(KeyFactory.keyToString(Key)の実行結果)。	"key":"aglzbGltMy1nZW5yCwsSBHRlc3QY6AcM"
com.google.appengine.api.datastore.Category	文字列(Category.getCategory()の値)。	"category":"partOfSpeech"
com.google.appengine.api.datastore.Email	文字列(Email.getEmail()の値)。	"mail":"user@domain.tld"
com.google.appengine.api.datastore.GeoPt	ネストしたJSON文字列(GeoPt.getLatitude()及びGeoPt.getLongitude()の値をJSONエンコード)。	"geopt":{"latitude":10.0,"longitude":10.0}
com.google.appengine.api.datastore.IMHandle	ネストしたJSON文字列(IMHandle.getAddress()及びIMHandle.getProtocol()の値をJSONエンコード)。	"handle":{"address":"handle","protocol":"xmpp"}
com.google.appengine.api.datastore.Link	文字列(Link.getValue()の値)。	"link":"linkValue"
com.google.appengine.api.datastore.PhoneNumber	文字列(PhoneNumber.getNumber()の値)。	"phone":"000-000-000"
com.google.appengine.api.datastore.PostalAddress	文字列(PostalAddress.getAddress()の値)。	"address":"Tokyo, Japan"
com.google.appengine.api.datastore.Rating	整数(Rating.getRating()の値)。	"rating":100
com.google.appengine.api.blobstore.BlobKey	文字列(BlobKey.getKeyString()の値)。	"blobkey":"Q3PqkweYlb4iWpp0BVw"
org.slim3.datastore.ModelRef<M>	文字列(モデルのkeyに対してKeyFactory.keyToString(key)した結果)。	"ref":{"key":"lskfo2ijalefkwejfwlke",value:100}

　また上記サポートする型のコレクションにも対応しています。対応するコレクションクラスはjava.util.List, java.util.Set, java.util.SortedSetで、JSON文字列からモデルを作成する際は、それぞれjava.util.ArrayList、java.util.HashSet、java.util.TreeSetをnewして要素を追加したものがセットされます。

ModelRef<M>の展開

　デフォルトではJSONアノテーションのcoderパラメータにorg.slim3.datastore.json.Defaultが指定されたものとして扱われ、このクラスは、ModelRefを参照先のモデルのキーに変換します。参照先のモデルの内容を展開したい場合、org.slim3.datastore.json.Expandedを指定して下さい。このクラスは、参照先のモデルの内容を展開し、そのモデルがさらにModelRefを持っている場合も展開します。展開のネストの深さは、modelToJsonメソッドやjsonToModelメソッドの、maxDepth引数で制限できます。

　以下にコード例を示します。

@Model
class TestModel{
  ...
  @Json(coder=Expanded.class)
  private ModelRef<TestModel> ref = new ModelRef<TestModel>(TestModel.class);
}
...
TestModel m = new TestModel();
TestModelMeta.get().modelToJson(m, 3);  // 3階層まで展開

JSON入出力のカスタマイズ

　JSONアノテーションのcoderパラメータにJSON入出力を行うクラスを指定することにより、JSON変換の振る舞いを変更することができます。デフォルトではorg.slim3.datastore.json.Defaultが指定されており、slim3が対応するデータ型のJSON入出力が行われます。slim3ではもう一つ、org.slim3.datastore.json.Expandedが用意されていて、これをModelRef<M>型のフィールドに対して使用すると、ModelRef<M>が参照しているオブジェクトも展開します。

　slim3が対応していないデータ型を使う場合や入出力方法を変更したい場合は、org.slim3.datastore.json.Defaultから継承したクラスを作成し、encode/decodeメソッドをオーバーライドして下さい。

　下記にjava.awt.Pointの入出力をサポートするクラスの例を示します。

class CustomCoder extends org.slim3.datastore.json.Default{
  public void encode(JsonWriter writer, Object value){
    if(value instanceof java.awt.Point){
      java.awt.Point pt = (java.awt.Point)value;
      writer.beginObject();
      writer.writeValueProperty("x", pt.x);
      writer.writeValueProperty("y", pt.y);
      writer.endObject();
    } else{
      super.encode(writer, value);
  }
  public <T> T decode(JsonReader reader, T defaultValue, Class<T> clazz){
    if(java.awt.Point.isAssignableFrom(clazz)){
      try{
        int x = Integer.parseInt(reader.readProperty("x");
        int y = Integer.parseInt(reader.readProperty("y");
        return clazz.cast(new Point(x, y));
      } catch(NumberFormatException e){
      }
    }
    return defaultValue;
  }
}

　java.awt.PointクラスのフィールドをJSON入出力の対象にするには、上記のCustomCoderをcoderパラメータに指定します。

import java.awt.Point;

@Model
class TestModel{
  public Key getKey(){
    return key;
  }

  public void setKey(Key key){
    this.key = key;
  }

  public Point getPoint(){
    return point;
  }

  public void setPoint(Point point){
    this.point = point;
  }

  @Attribute(primariKey=true)
  private Key key;

  @Attribute(persistent=false)
  @Json(coder=CustomCoder.class)
  private Point point;

}

　上記のように指定すると、java.awt.Point型のpointフィールドのJSON入出力がおこなえるようになります。

TestModel m = new TestModel();
m.setPoint(new Point(10, 20));
String json = TestModelMeta.get().modelToJson(m); // {"point":{"x":10,"y":20}}
TestModel m2 = TestModelMeta.get().jsonToModel(json);
Assert.assertEquals(m.x, m2.x);
Assert.assertEquals(m.y, m2.y); 

AppEngine Java で絵文字入りメールを送信する

Google AppEngineで絵文字メールを送る方法を紹介します。AppEngineでは送信メールのエンコーディングを指定できない( issueへのリンク)ため、絵文字を送ることはできないと思っていたんですが、 @tmurakamiさんに、送る方法を教えてもらいました。ただし、今のところこの方法で動作確認が出来ているのは、auのW62T, W63H, W64Kのみです。また、AppEngineの振る舞いに依存しているため、今後も動くかどうかの保証はありません。また、メールをWebメール等に転送している場合、Webメール側(au oneとgmailで確認されています)ではメール全体が(絵文字部分だけでなく)正常に表示されないようです(ヘッダにあるエンコーディング情報とメールボディのエンコーディングが違うので無理も無いですが)。

方法は至ってシンプルで、JISエンコード済みのテキストを無理やりStringに入れるというものです。例えばスマイルマーク(ucs: ☺, au: )であれば、auでの文字コードは0x7656なので、以下のようにします。

String text = new String(
   new byte[]{0x1b, '$', 'B', 0x76, 0x56, 0x1b, '(', 'B'}
   , "ISO8859-1");

0x1b, '$', 'B'はJIS漢字を開始するエスケープシーケンス、0x1b, '(', 'B'はアスキー文字を開始するエスケープシーケンスです。こうやって作った文字列を、メールの本文に設定します。

MailService.Message m = new MailService.Message();
 m.setTextBody(text);
 // set sender, recipients and subject
 MailServiceFactory.getMailService().send(m);

ここでは触れませんが、JavaMailApiでは、ByteArrayDataSourceを使うと送れるそうです。

AppEngineはメールを送信する際、含まれているキャラクタを見て、エンコーディングを決定します。日本語が含まれていればISO2022JPを選択しますし、中国語であればBig5、UTF8になる場合もあります。上記のように制御コードが混じっていると、ISO8859-1として、そのまま送信するようです。そして実機ではエンコーディングを無視してISO2022JPとして表示するため、絵文字が表示できる、という仕組みです。ただしこのAppEngineの振る舞いは規定されているものではないので、今後も動き続ける保証はありません。

pos2witではこの方法を使って、絵文字の送信機能を実装しました(今のところauのみ)。ダッシュボードから有効にできるので、au携帯でお使いの方は是非試してみてください。また、今後他社の携帯も調査して、可能であれば対応する予定です。

JSON変換機能、slim3にマージ中

以前のエントリで書いたslim3モデルのJSON変換機能ですが、slim3のコミッターになってマージ中です！

ロードマップはこんな感じ。

1st step (完了).
・modelToJsonメソッドの追加。基礎的な仕組みの実装。
・short, int, long, float, double及びそれらのラッパークラスのJSON出力実装。
・StringのJSON出力実装(cipher=trueを考慮)。
・ラッパークラスとStringのList, Set, SortedSetのJSON出力実装。

2nd step (完了).
・AppEngine固有の型(Blob, Category, Email, GeoPt, IMHandle, Link,
PhoneNumber, PostalAddress, Rating, ShortBlob, Text, UserのJSON出力実装。
・Date, EnumのJSON出力実装。
・上記の型のList, Set, SortedSetのJSON出力実装。

3rd step以降.
・リファクタリング
・ModelRef対応。
・シリアライズ対応(おそらくシリアライズしてBase64)
・アノテーションによる制御の検討(フィールド名のエイリアスとか、JSON変換時は無視するとか)
・jsonToModelメソッド追加(と上記の型の対応)。

実装の途中経過は、適宜slim3のDiscussion Groupでお知らせしてます。

slim3を改造して、モデルのJSON変換機能を追加する

Google App Engine for Java用のフレームワークと言えばslim3です。シンプルで非常に使いやすいフレームワークですが、その特徴はアノテーションプロセッサとして実装されている、Metaクラスジェネレータ(slim3-gen)にも当てはまります。拡張性が考慮されていて、簡単に機能を拡張することが出来るようになっていて、実際にアノテーションの情報を元にソースを生成するサンプルも公開されています(リポジトリの、slim3-gen-extention-sample)。

そのサンプルを参考に、slim3-genが生成するメタクラスにjson変換を行うメソッドを追加する拡張、slim3-gen-jsonicを作ってみたので、紹介します。

使い方

1. slim3-gen-jsonicのバイナリを、ここからダウンロードして下さい(現在最新版はslim3-gen-jsonic-1.0.5.jar)。
   
2. 次に、jsonicのバイナリをjsonicのサイトからダウンロードして下さい(現在最新版はjsonic-1.2.4.jar)。

slim3と使う場合と同様にプロジェクトを作成、セットアップし(slim3のスタートガイド参照)、jsonicのjarをビルドパスに追加、slim3-genのjar(現在最新はslim3-gen-1.0.5.jar)の代わりにslim3-gen-jsonicのjarを使用すると、モデルごとに生成されるメタクラスに以下のメソッドが追加されます。

• public String modelToJson(Object model)
  
• public ModelClass jsonToModel(String json)

ModelClassは、各モデルのクラスに置き換わります。

modelToJsonでモデルをJSON文字列に変換し、jsonToModelでその逆、JSON文字列をモデルに変換します。jsonToModelは、内部でJSONICを使っています。使い方は簡単、Metaクラスからこれらのメソッドを呼び出すだけです。

public void test(){
  TestModelMeta m = TestModelMeta.get();
  TestModel model = new TestModel();
  String json = m.modelToJson(model); // model -> JSON
  TestModel model2 = m.jsonToModel(json); // JSON -> model
}

対応している型

現在、以下の型に対応しています。

• String(cipher=trueの場合、JSON出力時に暗号化されます), List<String>, Set<String>, SortedSet<String>
  
• short, Short, List<Short>, Set<Short>, SortedSet<Short>
  
• int, Integer, List<Integer>, Set<Integer>, SortedSet<Integer>
  
• long, Long, List<Long>, Set<Long>, SortedSet<Long>
  
• float, Float, List<Float>, Set<Float>, SortedSet<Float>
  
• double, Double, List<Double>, Set<Double>, SortedSet<Double>
  

ソースからのビルド

EclipseとGoogle Plugin for Eclipse、Subversionクライアント(Subclipse or subversive)が必要です。

まず、slim3のリポジトリから、slim3とslim3-genをチェックアウトします。

次に、slim3-gen-jsonicのリポジトリから、slim3-gen-jsonic、slim3-gen-jsonic-testをチェックアウトします。

slim3-gen-jsonicに含まれているbuild.xmlを使ってビルドすると、slim3-gen-jsonicプロジェクトのtargetディレクトリに、jarファイルが生成されます(slim3-genの全クラスもこのjarに含まれています)。

slim3-gen-jsonic-testプロジェクトは、slim3プロジェクトを参照し、slim3-gen-jsonicプロジェクトが生成するjarをannotation processorとして参照しるので、このプロジェクト内にモデルクラスを作成すると、JSON変換機能を簡単に試せます。また、メタクラスはsrc_generatedディレクトリ内に生成されるようになっているので、実際にどんなメソッドが生成されているか確認できます。

jsonic単体と比べた利点

今のところ持っている機能だと、文字列の暗号化対応以外、jsonicそのものを使っても同じ効果が得られます。slim3-genに統合する形で機能を追加していく利点としては、

• リフレクションを使わないので速い(但しある程度大きなモデルでも、数十ミリ秒の差でしょう)
  
• App Engine固有の型に対応しやすい(固有の型には今後対応していく予定です)
  

というところが挙げられます。まぁ、あまり大きな利点は無いですし、DatastoreのモデルとJSONとしてクライアントに返すデータのモデルが同じものとも限らない(むしろ別々に設計したほうがよさそう)ですが、Metaを使ってモデルを手軽に変換できるだけでも便利なのではないかと思います。

pos2wit - メールでTwitterを利用できる無料サービス

趣味でpos2witの開発を始めて、気づけばもう1年が経ちました。当初予定していたよりも多くの機能が実装できて、かなり便利に使えるツールになってきました。このスマートフォン全盛の時代、あえてガラケーのみで勝負する人のためのサービスです :-)

pos2witはメールでTwitterを利用出来るサービスです。特に携帯電話のメール機能に最適化してあり、携帯電話のメール機能を使って、Twitterの機能を一通り使うことが出来ます。写真の添付や他のユーザが投稿した写真のサムネイル取得にも対応しています。

ガラケーしか持っていない人、特にメール無料プランを契約している人に最適です(私もガラケーでメール無料プランです!)。通勤途中や休憩時間の暇つぶしなど、ちょっとした時間に是非ご活用ください!

注意事項: pos2witはGoogle App Engine上で動作しており、Twitterにアクセスします。そのため、App EngineのメンテナンスやTwitterのAPI制限に影響され、機能が正常に使えないことがあります。多くの機能は失敗することは殆どありませんが、検索については、TwitterのAPI制限のため、一定時間使えない状態になっていることがあります。そのため、検索結果の受信には、数分から数時間かかることがあります。

ユーザ登録

ユーザ登録は、PCからの登録(oAuth)と、メール経由の登録(xAuth)の2種類に対応しています。

PCから登録する場合、www.pos2wit.comにある、"Signin with Twitter"と書かれたボタンをクリックしてください。Twitterアカウントへのアクセスを許可する画面が表示されます。"許可する"を選ぶと、ユーザ登録が完了しますので、利用するメールアドレスを登録してください。登録後送られる確認メールに返信すると、メールが登録され、pos2witが利用出来るようになります。

メール経由で登録する場合、1行目にTwitterのIDを、2行目にパスワードを書いたメールを、reg@pos2wit.com に送信してください。ユーザ登録とメール登録が一度に行われ、pos2witが利用出来るようになります。(このとき送られたID, パスワードは、Twitterへのアクセス情報の取得にのみ使われ、取得後破棄されます。pos2wit登録後にパスワードを変更しても、動作に問題はありません。)

※迷惑メールフィルタを利用されている場合、pos2wit.comから送信されるメールを受信できるように設定しておいてください。

投稿機能

内容にTwitterに投稿したいツイートを記入して p@pos2wit.com にメールを送ると、Twitterに書き込むことが出来ます(件名は無視されます)。この際、写真が添付されていると、TwitPicに写真が投稿され、URLがツイートの末尾に付加されます。投稿先の画像サービスは、PCから pos2wit にログインした際に表示される、ダッシュボード画面で変更できます。

また、画像を投稿する際に、回転や反転などのフィルターを適用できます。件名にrlで左回転、rrで右回転を行ないます(このエントリ末尾に詳細)。

タイムライン取得

h@pos2wit.com に空メールを送ると、ホームタイムラインが取得できます。メールの受信可能サイズ制限のため、通常取得できるツイートは10〜20件程度です。sh@pos2wit.com に空メールを送ると、装飾のほとんどない、簡易フォーマットでホームタイムラインが取得できます。この場合、40〜50件程度のツイートが取得できます。

ユーザのタイムラインやステータス、お気に入り、リツイート、返信、ハッシュタグの検索、画像のサムネイル取得、イベント概要(ATND, TweetVite)取得、グルーポン概要取得など、ホームタイムラインの結果には様々な操作を行うためのメールアドレスへのリンクが貼られます。これはツイートの内容を解析することで実現されていて、短縮URLも展開して解析しています。

発表(App Engine Java Night Kansai #3)

先月京都リサーチパークで行われたAJNK3で発表しました! ustと資料はこちらからどうぞ(途中までだけど)

• http://www.ustream.tv/recorded/10234795
  
• 資料
  

また、AJNK3では、slim3のひがやすをさん、teamsteamのpirosukeさんも発表されています。

• ひがやすをさんのust
  
• AJNKの資料一覧
  

各種機能の詳細

画像投稿先として対応しているサービス

• twitpic
  
• twitgoo
  
• plixi
  
• yfrog
  
• img.ly
  
• picasa
  

画像投稿時のフィルタ(件名に記入)

• rl - 左回転(90℃)
  
• rr - 右回転(90℃)
  
• rp - 半回転(180℃)
  
• fh - 上下反転
  
• fv - 左右反転
  
• ifh - 自動輝度調整
  
• sNN - 縮小(例: s30 - 30%に縮小)
  

サムネイル取得に対応しているサービス

• twitpic
  
• twitgoo
  
• plixi
  
• yfrog
  
• flickr
  
• brizzly
  
• owly
  
• 携帯百景
  
• mobypic
  

Twitter4J 2.1.2を改造してGoogle AppEngineからTwitPicにOAuthEchoで画像を投稿する。

Twitter4J2.1.2では(執筆時はまだ開発中)、画像の投稿機能が提供されます。現在実装されているのは、YFrogへの投稿機能(OAuthEcho, Basic認証)とTwitPicへの投稿機能(Basic認証のみ)です。
pos2witではTwitPicへのOAuthEchoによる投稿を行いたかったので、できるように改造してみました。

まず、Twitter4Jのサイトから、バージョン2.1.2をダウンロードして展開して下さい。この中に含まれる、twitter-core内のソースを改造しますので、このソースが改造できる環境を整えて下さい(僕はEclipse上にプロジェクトを作成し、ソースをコピーしました。)。環境を整えてコンパイルすると、twitter4j.internal.logging内のいくつかのソースでコンパイルエラーが起こります。参照しているクラスがないためで、ここは何も考えずにCommonsLogging, Log4J, SLF4J関連のソースを削除します(それぞれLoggerとLoggerFactoryがあるのでそれらを削除)。

次にgithubのtwitter4j.utilから、ImageUpload.javaをダウンロードし、twitter4j.util内にコピーします。このファイル内で、画像投稿機能が実装されています。
コピーするとコンパイルエラーが出るので、まずはこれを潰します。

twitter4j.http.OAuthAuthorizationに、次のメソッドを追加します(これはgit内のソースには実装されています)。

    public List<HttpParameter> generateOAuthSignatureHttpParams (String method, String url) {
        long timestamp = System.currentTimeMillis() / 1000;
        long nonce = timestamp + RAND.nextInt();
        
        List<HttpParameter> oauthHeaderParams = new ArrayList<HttpParameter>(5);
        oauthHeaderParams.add(new HttpParameter("oauth_consumer_key", consumerKey));
        oauthHeaderParams.add(OAUTH_SIGNATURE_METHOD);
        oauthHeaderParams.add(new HttpParameter("oauth_timestamp", timestamp));
        oauthHeaderParams.add(new HttpParameter("oauth_nonce", nonce));
        oauthHeaderParams.add(new HttpParameter("oauth_version", "1.0"));
        if (null != oauthToken) {
            oauthHeaderParams.add(new HttpParameter("oauth_token", oauthToken.getToken()));
        }
        
        List<HttpParameter> signatureBaseParams = new ArrayList<HttpParameter> (oauthHeaderParams.size());
        signatureBaseParams.addAll(oauthHeaderParams);
        parseGetParameters (url, signatureBaseParams);
        
        StringBuffer base = new StringBuffer (method).append("&")
                .append(encode(constructRequestURL(url))).append("&");
        base.append(encode (normalizeRequestParameters(signatureBaseParams)));

        String oauthBaseString = base.toString();
        String signature = generateSignature (oauthBaseString, oauthToken);

        oauthHeaderParams.add (new HttpParameter("oauth_signature", signature));
        
        return oauthHeaderParams;
    }

次に、ImageUpload.java内にTwitPic用のOAuth Echo対応ImageUploadを実装します。
同ファイル内に、下記のソースをコピーします。下記ソースは、同ファイル内のYFrogOAuthUploaderをコピーしてTwitPic用に修正したものです。

// import部分
import java.io.InputStream;
import java.io.UnsupportedEncodingException;
import java.net.URLEncoder;
import twitter4j.conf.Configuration;
import twitter4j.conf.ConfigurationContext;
import twitter4j.internal.org.json.JSONException;
import twitter4j.internal.org.json.JSONObject;

// TwitPicOAuthUploader
    public static class TwitPicOAuthUploader extends ImageUpload {
     private String apiKey;
        private OAuthAuthorization auth;

        // uses the secure upload URL, not the one specified in the YFrog FAQ
        private static final String TWITPIC_UPLOAD_URL = "http://api.twitpic.com/2/upload.json";
        private static final String TWITTER_VERIFY_CREDENTIALS = "https://api.twitter.com/1/account/verify_credentials.json";

        public TwitPicOAuthUploader(String apiKey, OAuthAuthorization auth) {
            this.apiKey = apiKey;
            this.auth = auth;
        }

        public String upload(File image) throws TwitterException{
         throw new UnsupportedOperationException();  // AppEngineではFileInputStreamが使えない。
        }

        public String upload(String message, String fileName, InputStream fileBody) throws TwitterException {
            // step 1 - generate verification URL
//            String signedVerifyCredentialsURL = generateSignedVerifyCredentialsURL();

            // step 2 - generate HTTP parameters
            HttpParameter[] params = {
                    new HttpParameter("key", apiKey)
                 , new HttpParameter("message", message, true)
                    , new HttpParameter("media", fileName, fileBody)
                    };

            // step 3 - upload the file
            Configuration config = ConfigurationContext.getInstance();
            config.getRequestHeaders().put("X-Auth-Service-Provider", TWITTER_VERIFY_CREDENTIALS);
            StringBuilder b = new StringBuilder();
            b.append("OAuth realm=\"http://api.twitter.com/\"");
            for(HttpParameter p : auth.generateOAuthSignatureHttpParams("GET", TWITTER_VERIFY_CREDENTIALS)){
             if(p.getName().equals("oauth_signature")){
                    try {
                        b.append(", ").append(p.getName()).append("=\"").append(
                                URLEncoder.encode(p.getValue(), "ISO8859_1")
                                ).append("\"");
                    } catch (UnsupportedEncodingException e) {
                        throw new TwitterException(e);
                    }
             } else{
                    b.append(", ").append(p.getName()).append("=\"").append(p.getValue()).append("\"");
                }
            }
            config.getRequestHeaders().put("X-Verify-Credentials-Authorization", b.toString());
            System.out.println("X-Auth-Service-Provider: " + TWITTER_VERIFY_CREDENTIALS);
            System.out.println("X-Verify-Credentials-Authorization: " + b.toString());
            HttpClientWrapper client = new HttpClientWrapper(config);
            HttpResponse httpResponse = client.post(TWITPIC_UPLOAD_URL, params);

            // step 4 - check the response
            int statusCode = httpResponse.getStatusCode();
            if (statusCode != 200) {
                throw new TwitterException("Twitpic image upload returned invalid status code", httpResponse);
            }

            try{
             String response = httpResponse.asString();
             return new JSONObject(response).getString("url");
            } catch(JSONException e){
                throw new TwitterException("Unknown Twitpic response", httpResponse);
            }
        }
    }

上記のソースをペーストすると、twitter4j.internal.http.HttpParameterに必要なメソッドが無いためにコンパイルエラーが発生します。下記のフィールド及びメソッドを、HttpParameterクラスに追加して下さい。

    // フィールドを追加
    private boolean noUrlEncode = false;
    private InputStream fileBody = null;
    ...

    // コンストラクタを追加
    public HttpParameter(String name, String value, boolean noUrlEncode) {
        this.name = name;
        this.value = value;
        this.noUrlEncode = noUrlEncode;
    }

    public HttpParameter(String name, String fileName, InputStream fileBody) {
        this.name = name;
        this.file = new File(fileName);
        this.fileBody = fileBody;
    }
    ...

    // メソッドを追加
    public boolean isUrlEncodeUnnecessary(){
     return this.urlEncodeUnnecessary;
    }

    public boolean hasFileBody(){
     return null != fileBody;
    }

    public InputStream getFileBody(){
     return fileBody;
    }

これでコンパイルエラー自体は消えますが、追加されたパラメータに対応してリクエスト作成機能を修正する必要があります。リクエスト作成機能はtwitter4j.internal.http.HttpClientImpl.java内にあるので、下記のように改造します(赤字が改造部分)。

                                // 241行目あたり
                                if(param.isFile()){
                                    write(out, boundary + "\r\n");
                                    write(out, "Content-Disposition: form-data; name=\"" + param.getName() + "\"; filename=\"" + param.getFile().getName() + "\"\r\n");
                                    write(out, "Content-Type: " + param.getContentType() + "\r\n\r\n");
                                    BufferedInputStream in = new BufferedInputStream(
                                      param.hasFileBody() ? param.getFileBody() : new FileInputStream(param.getFile())
                                      );
                                    int buff = 0;
                                    ...

                                // 258行目あたり
                                    logger.debug(param.getValue());
                                    if(param.isUrlEncodeUnnecessary()){
                                     out.write(param.getValue().getBytes("UTF-8"));
                                    } else{
                                     out.write(encode(param.getValue()).getBytes("UTF-8"));
                                    }
                                    write(out, "\r\n");
                                    ...

この修正が必要なのは、

• オリジナルのコードではFileInputStreamを使っているが、これはAppEngineでは使えない。
  
• オリジナルのコードでは常にパラメータをURLEncodeしているが、メッセージをURLEncodeするとTwitPicで復元されない(URLEncodeされた状態で記録される)

という問題に対処するためです。

これでTwitPicに画像を投稿できるようになります。サンプルコードはこんな感じ。投稿にはTwitPicのAPIKEYが必要なので、ここからアプリケーションを登録し、APIKEYを入手して下さい。

 public void test() throws Exception{
  String apiKey = TwitPicのAPI KEY;
  Twitter t = new TwitterFactory().getOAuthAuthorizedInstance(new AccessToken(
    Twitterユーザのaccess_token
    , Twitterユーザのaccess_token_secret
    ));
  OAuthAuthorization auth = (OAuthAuthorization)t.getAuthorization();
  String message = "投稿するメッセージ。";
  String url = new ImageUpload.TwitpicOAuthUploader(apiKey, auth).upload(
    message, "duke.jpg", getClass().getResourceAsStream("duke-on-gae.jpg")
    );
  // twitterには、別途投稿する必要がある(uploadでは写真がTwitPicに投稿されるのみ)。
  t.updateStatus(message + " " + url);
 }

だいぶ汚い改造になってしまいましたが、とりあえず投稿することはできるようになりました。もう少し整理して、Twitter4Jにうまく取り込んでもらえるよう働きかける予定です。

AJDT2.1.0 Released

AJDT2.1.0がリリースされました。リリースノートに書かれている変更点をざくっと紹介します。主にITD(Inter Type Definition)関連の機能が強化されました。

• ITD-Aware Search
  アスペクトによる定義の追加を考慮したJava Searchが正しく行われるようになりました(例: ITD定義、String Person.getName()に対して参照の検索を行うと、ITDされたメソッドを使用しているコードがヒットする)。
  


• ITD rename refactoring
  名前変更のリファクタリング機能がITDに対応しました。アスペクトのITDでの名称変更(例: String Person.getName()をString Person.getFirstName()に)を行うと、影響を受ける定義(例: Personの派生クラスでのgetNameメソッド(オーバーライド))も名称変更されます。
  


• ITD-aware renaming of getters and setters
  フィールドの名称変更を行う際に、ITDによって実装されていたそのフィールドのgetter及びsetterの名称変更も行えるようになりました。nameをfirstNameに変更した場合に、ITDで実装されたgetNameがgetFirstNameに、setNameがsetFirstNameに変更されませす。(但し、Personの派生クラスでgetNameをオーバーライドしていた場合、そのメソッドは変更されません(あくまでgetter/setterのみ)。個人的にはこれも変更されて欲しいところ。常に@Override付けといた方が良さそうですね。)
  


• Pull-out refactoring
  フィールドやメソッドを、ITDとして特定のアスペクトに移動するリファクタリング。パッケージエクスプローラでフィールドやメソッドを選んで右クリック -> Refactory -> Pull Out ITD... と選択すると、既存のアスペクトに切り出せます。
  


• Aspect-aware type renaming
  クラス名の変更を行う際に、それを参照しているアスペクト内での定義(ITD)も適切に変更されるようになりました。
  


• @Test and Intertype declarations
  ITDによって@Testが付加されたメソッドを追加した場合、そのクラスをテストすると、@Testが付加されたメソッドもテストの対象になります。
  


• AspectJ-aware PDE Build (Helios only)
  AspectJをPDEに統合したビルドが提供されるようになったそうです。AspectJに依存したプラグインを作る際に、Javaプラグインと同じウィザード等を使えるようになりました。詳しくはこちら。
  


• Modernize the build server
  ビルドサーバーをモダンなものに変えたそうです。詳しくはこちら。
  


• AspectJ 1.6.9
  最新のAspectJ 1.6.9がバンドルされています。readmeはこちら。
  


• Bug Fixes
  その他、いくつかのバグが修正されています。
  

最初ITDがサポートされるようになった頃は、IDE上はコンパイルエラーになっていましたが、バージョンを重ねるにつれて洗練され、遂にリファクタリングまで正常に動くようになりました。今回の機能強化で、ITDされたメソッド・フィールドも元からクラスに定義されていたものとほぼ同じように扱われるようになり、心おきなく使えるようになったのではないでしょうか。