App Engineでテキスト部分一致検索を紹介してみようと思います。 とりあえず新しい発見があったので、あまり効率的でない「接尾辞の列挙」という方法で実現してみます。 なお、サンプルコードは全てSlim3 Datastoreとデータストア低レベルAPIを利用して書かれています。

今回のエントリの内容は開発サーバ(1.2.6)で正しく動かないようです。試してみる方は、デプロイすることをお勧めします。

前方一致検索

App Engineのデータストア上で検索を行う場合、インデックスの「レンジスキャン」という方法で目的のエンティティが探し出されます。 これは、データストア上にソートされたインデックスエントリの開始位置と終了位置を指定して、その範囲全体を抜き出すイメージです。

これをうまく利用すると、テキストの「前方一致検索」が実現できます。 テキストはUnicodeの辞書式順序でソートされていて、"abc"という文字列は:

• "ab" より大きい
• "abb" より大きい
• "abc" と同じ
• "abd" より小さい
• "ac" より小さい

という関係になります。 厳密には正しくありませんが、末尾にヌル文字(\u0000)を埋めて、検索対象と同じ文字数にそろえてやるとわかりやすいかもしれません。さらにそれらを文字コードであらわすと、次のようになります。

• \u0061 \u0062 \u0000 (ab) より大きい
• \u0061 \u0062 \u0062 (abb) より大きい
• \u0061 \u0062 \u0063 (abc) と同じ
• \u0061 \u0062 \u0064 (abd) より小さい
• \u0061 \u0063 \u0000 (ac) より小さい

この特性を利用すると、「"ab"から始まる文字列」というものを先のレンジスキャンで検出することができます。"ab"から始まる文字列は、インデックス上では「"ab"以上, "ac"未満」という範囲です。これを簡略化して「"ab"以上, "ab\uFFFF"以下」として取り扱っているケースも見かけますが、これは文字列中に\uFFFFが出現しない限りは正しく動作します。

しかし、この方法ではテキストを「前方一致検索」することしかできません。たとえば、「"abcdefg"に"cde"という文字列が含まれているか」といった「部分一致」が必要なケースには適用できません。 今回はそんな「部分一致検索」をApp Engineで行う際の、プリミティブな解決方法について紹介してみようと思います。

リストプロパティ

さて、接尾辞の紹介に入る前にApp Engineのデータストアクエリを活用する上で、(個人的に)重要と思われるリストプロパティについて説明します。

リストプロパティはエンティティの中でjava.util.List型, java.util.Set型など、スカラでない値を持つプロパティのことです。 リストプロパティはデータストアインデックスの作られ方が少しほかのプロパティと異なっていて、個々の要素が展開された状態でインデックスが作成されます。

このインデックスに対して検索を行うと、「いずれかの要素が該当する」という種類の検索が実現できます。うまく利用すれば1:Nの関係を表すことができます。 たとえば、データストア上にブログのエントリを保存しておいて、それをタグで検索する場合を考えてみます。

まず、下記のようにSlim3 Datastoreでエンティティの定義をします。このとき、java.util.Setでtagsというプロパティを定義しているため、リストプロパティになります。

@Model
public class BlogEntry {

    @Attribute(primaryKey = true)
    private Key internalKey;

    // エントリに付けられたタグ一覧
    private Set<String> tags;

    // ... 以下アクセサ
}

これに対し、"appengine"というタグが付いたエントリを探してみます。

BlogEntryMeta e = new BlogEntryMeta();
List<BlogEntry> appengines = Datastore.query(e)
    .filter(e.tags.contains("appengine"))
    .asList();

びっくりするくらい簡単でした。 Slim3 Datastoreと低レベルAPIを組み合わせる場合、次のように書けます。

BlogEntryMeta e = new BlogEntryMeta();
DatastoreService ds = DatastoreServiceFactory.getDatastoreService();
Query query = new Query(e.getKind())
    .addFilter(e.tags.getName(), FilterOperator.EQUAL, "appengine");
Iterable<Entity> iterable = ds.prepare(query).asIterable();

低レベルAPIでは、FilterOperator.EQUALという比較を行います。 これはリストプロパティの各要素が、インデックス上で展開されていて、それに対して同値比較を行う(完全一致検索)というのが実際の処理であるためです。 このあたりを完全に理解するために、一度は低レベルAPIを使ってみるのもいいかもしれません。

誤解していたこと

先ほどのブログエントリの例では、タグ名をテキストの「完全一致」で検索していました。 もし、リストプロパティに対して「前方一致」検索を行う場合、複数の要素がマッチする場合があります。

たとえば、先ほどのBlogEntryの例で、あるエントリのtagsに対して"appengine/py", "appengine/java"という2つのタグが設定されていることを考えてみます。 これに対して「"appengine"から始まるタグを含む」という前方一致検索を行う場合、同一のエントリに対して"appengine"から始まるタグ"appengine/py", "appengine/java"が含まれていますので、このエントリが2重にヒットすることになります。

これをやるとクエリを実行した際に重複するエントリが返ってくると誤解していたのですが、低レベルAPIを使ってもちゃんと重複が除去(distinctのような感じ)されて返ってきました。なので下記のように書けます。

String tag = "appengine";
BlogEntryMeta e = new BlogEntryMeta();
Query query = new Query(e.getKind())
    .addFilter(e.tags.getName(), FilterOperator.GREATER_THAN_OR_EQUAL,
        tag) // 開始位置
    .addFilter(e.tags.getName(), FilterOperator.LESS_THAN_OR_EQUAL,
        tag + '\uFFFF') // 終了位置
    ;

DatastoreService ds = DatastoreServiceFactory.getDatastoreService();
Iterable<Entity> result =  ds.prepare(query).asIterable();

手元のSlim3 Datastoreのバージョン(slim3-blank-EA1-SNAPSHOT-11142009.zipに同梱のもの)ではCollectionAttributeMetaというクラスの制限で上記のクエリが書けないようです。 もしかすると使っちゃいけないクエリかもしれませんので、もうちょっと調査してみます(App Engine上では正しく動いているように見えますが、少なくとも開発サーバでは変な動きをしました)。

コメントにいただいたように、最新のSlim3 (slim3-EA1-20091123.073844-6.jar) ではStringコレクション型のメタプロパティにstartsWith()メソッドが追加されました。試してみたところ、上記の低レベルAPIで書いてたプログラムは下記のように書きなおせます。簡単ですね。

String tag = "appengine";
BlogEntryMeta e = new BlogEntryMeta();
List<BlogEntry> entries = Datastore.query(e)
    .filter(e.tags.startsWith(tag))
    .asList();
for (BlogEntry entry : entries) {
    // ...
}

接尾辞の列挙

前置きが長くなってしまいましたが、ここまでのポイントは3点です。

1. App Engineのデータストアで文字列を検索する場合、前方一致検索ができる
2. リストプロパティを利用すると、「いずれかの要素が該当する」という検索ができる
3. リストプロパティでも前方一致検索ができる(やや不安)

上記の規則を組み合わせると、「テキストを前方一致検索しかできないなら、前方から1文字ずつ削ったリストを用意してやる」という方法でテキストの部分一致検索を実現できます。 今回の「接尾辞」というのは「文字列の前方を削った残り」のことを表していて、その「接尾辞の列挙」は「前方から1文字ずつ削った全ての文字列をリストアップ」することを表しています。

たとえば、"appengine"という文字列を前方から1文字ずつ削っていくと、次のようになります。

1. appengine (0文字)
2. appengine (1文字)
3. appengine (2文字)
4. appengine (3文字)
5. appengine (4文字)
6. appengine (5文字)
7. appengine (6文字)
8. appengine (7文字)
9. appengine (8文字)
10. appengine (9文字)

上記の文字列を全てリストプロパティに投入(結果が0文字になるものは除外してもよさそう)し、そのプロパティに対して前方一致検索をかけてやると、元の文字列の部分一致検索を実現できます。 たとえば、"eng"という文字列を前方一致検索すると、appengineにヒットします。

簡単にモデルを定義してみると、だいたい以下のような感じです。

@Model
public class SuffixEnumeration {

    @Attribute(primaryKey = true)
    private Key internalKey;
    private Set<String> array; // 接尾辞の列挙

    public SuffixEnumeration() {}

    public SuffixEnumeration(String text) {
        // 接尾辞配列を作成する
        this.array = new TreeSet<String>();
        for (int i = 0, n = text.length(); i < n; i++) {
            array.add(text.substring(i));
        }
        // キーを作成する
        this.internalKey = internalKeyOf(text);
    }

    // 対象のテキストそのものをキーに含める
    public static Key internalKeyOf(String text) {
        return Datastore.createKey(SuffixEnumeration.class, text);
    }

    // キーから対象のテキストを取り出す
    public static String getTextFrom(Key internalKey) {
        return internalKey.getName();
    }

    // ... 以下アクセサ
}

検索は低レベルAPIで行うため、ちょっと読みにくくなってます。 Slim3 Datastoreを使うとこんな感じで書けます。

SuffixEnumerationMeta e = new SuffixEnumerationMeta();
List<Key> keys = Datastore.query(e)
    .filter(e.array.startsWith(word))
    .asKeyList();
for (Key key : keys) {
    // キーから検索結果を取り出す
    String found = SuffixEnumeration.getTextFrom(key);
    // ...
}

ただし、この方法を利用する場合、検索対象の文字数に対して二乗のオーダーで接尾辞の文字数が必要になります。インデックスが大きくなりすぎる気がしますが、20文字くらいのテキストだったら何とかなりそうな数です。

その他

この他にも、N-gramや形態素の利用など、様々なテキスト検索の技術が存在します。それぞれに利害得失がありますので、App Engineでテキスト検索を行う場合には、適切な技術を選択することが必要になります。

今回の例では、「タグの部分一致検索」など、検索対象の文字列が十分に短く、形態素解析やN-gramでは精度に難があるケースなどに利用できそうです。しかし、AND検索を行うことができない点や、データストアの検索で非常に貴重なinequality filterを利用してしまう点などが悩みどころです。