作って理解するAjax --- No.4
予測・補完インタフェースを作成

2006.01.20

図1 クエリーとクエリーが出現した前後の文脈をいっしょに表示するインタフェースKIWCの例

[画像のクリックで拡大表示]

図2 リスト・アイテムをテキスト・ボックスの下に置いてマウスによって選択するインタフェースが一般的

[画像のクリックで拡大表示]

図3 テキスト・ボックスに何かを入力すると，次々と候補が補完される

[画像のクリックで拡大表示]

図4 郵便番号の一部を入力すると住所が補完され，候補から選択するだけで住所が入力できる

[画像のクリックで拡大表示]

この連載記事の目次へ

　日本語入力ほど面倒な操作はありません。ローマ字入力の場合，ひらがなを入力するためには複数のキーを組み合わせる必要があります。さらに漢字に変換するには，変換キーを何度か押して候補を選択しなければなりません。

　予測・補完インタフェースがあれば，このような面倒な操作から解放されます。ユーザーは「お」と入力するだけで，入力システム自身が過去の履歴や現在の文脈などを総合的に考慮し，「お」から始まる「おはようございます」「お元気ですか」といった候補をユーザーに提示します。ユーザーは候補から選択するだけでよく，キーストローク数を減らせます。

　このような予測・補完インタフェースはAjaxの格好のアプリケーションです。例えば，Google Suggestは，ユーザーが入力した部分的なクエリーから完全なクエリーを次々と予測・補完してくれます。Gmailでは，メール・アドレスの先頭の数文字を入力するだけで，該当アドレスをアドレス帳から検索して提示してくれます。

　今回は，Ajaxを使って予測・補完インタフェースを実現してみたいと思います。まず，汎用的な予測・補完を実現するAjaxプログラムを作ります。そして，その応用として郵便番号から住所を補完してみます。

KWICとの違い

　一見，前回のインクリメンタル検索とはまったく異なるインタフェースですが，多くの共通点があり，前回までのコードを少し改良するだけで実現できます。

　前回まで，インクリメンタル検索（KWIC）の実装を紹介しました。KWICは，クエリーとクエリーが出現した前後の文脈をいっしょに表示するインタフェースです。図1［拡大表示］がKIWCの例です。クエリーの右側に表示されるテキストは，クエリーに後続する文脈です。ユーザーは部分的なクエリーを入力するだけで，後続するテキストの内容を理解できます。後方文脈を表示するだけでなく，それらを入力の補完候補に使ってしまおうというのが今回の入力，補完インタフェースの基本的なアイデアです。

JavaScriptによるセレクト・ボックス

　予測・補完インタフェースは，ユーザーが候補を選択できるようなしくみが必要です。図2［拡大表示］のようにリスト・アイテムをテキスト・ボックスの下に置き，マウスによって選択するのが一般的です。

　HTMLフォームにはセレクト・ボックスを表現する<SELECT>タグがあります。しかし，<SELECT>は通常のテキスト入力ボックス（<input type="text">）と互換性がなく，テキスト入力を拡張する目的で使うことができません。さらに，補完候補や表示/非表示をユーザーの入力に応じて動的に変更しなければならないため，<SELECT>では不十分です。

　驚かれるかもしれませんが，Google Suggest といったAjaxによる予測・補完インタフェースの多くは，SELECTを使わずに<div>要素を動的に生成し，その中に候補を並べるという方法を使ってセレクト・ボックスを実現しています。さらに，onclick，mouseover，mouseoutイベントを適切に処理することで，マウスによる候補選択とハイライトを実現しています。

　JavaScriptを使って，この「擬似セレクト・ボックス」を実装するのは，残念ながら簡単ではありません。そこで，通常のテキスト入力ボックスを拡張して補完インタフェースを追加するラッパー関数（initCompletion）を用意しました。今回は，単純にこの関数を使って実装をしたいと思います。興味のある方は，initComplettionのソースを御覧下さい。

initCompletion(textbox)を呼ぶことで，引数に与えられた textboxに以下の二つのメソッドが新たに追加されます。

textbox.showCompletionItems(ary, func);

補完候補を表示します。

ary は表示する候補の配列, func は候補がマウスで選択された時に呼ばれるコールバック関数
textbox.clearCompletionItems()

補完候補を消去します。

　以下に initCompletion の具体例を示します。

// zip というid を持つテキストボックス
var textbox = document.getElementById('zip');

// textbox を拡張
initCompletion(textbox);

// 候補対象 (文字列の配列)
var ary = ["foo","bar"];

// 補完候補を表示
// 第一引数: 候補対象(文字列の配列)
// 第二引数: 選択された時に呼ばれる callback 関数, callback 関数の
//            引数は，選択された候補の番号
textbox.showCompletionItems(ary, function(n) { alert(ary[n]); });

// 補完候補を消去
textbox.clearCompletionItems()

クライアントの実装

　クライアント・サイドの実装は，第2回で紹介したpeekQuery関数を少し変更するだけです。具体的には，Ajaxのコールバック関数onreadystatechangeの中で補完候補のセレクト・ボックスを表示するようにします。showCompletionItemsの第2引数に，サーバーから受け取った補完対象をテキスト・ボックスにそのまま代入し，セレクト・ボックスを消去するようなコールバック関数を指定します。

　サーバーからのレスポンスは，改行で区切られたテキストと想定しています。各行が補完候補になります。

function peekQuery () {

  if (! xmlhttp) xmlhttp = createXmlHttpRequest();

  if (! xmlhttp || xmlhttp.readyState == 1 ||
      xmlhttp.readyState == 2 || xmlhttp.readyState == 3){
    return;
  }

  var textbox = document.getElementById('query');
  var query   = encodeURI(textbox.value);

  if (query == "") {
    textbox.clearCompletionItems();
  } else if (oldquery != query) {
    xmlhttp.open("GET", "complete.cgi?" + query, true);
    xmlhttp.onreadystatechange = function() {
      if (xmlhttp.readyState == 4 && xmlhttp.status == 200
      && xmlhttp.responseText != "") {
        var ary = xmlhttp.responseText.split(/\n/);
        textbox.showCompletionItems(ary,
                     function(n) {
          textbox.value = ary[n];
          textbox.clearCompletionItems();
          oldquery = encodeURI(textbox.value); } );
      }
    }
    xmlhttp.send(null)
  }

  oldquery = query;
}

　なお，完全なソースはこちらにあります。

Suffix Arrayの構築

　予測・補完インタフェースでは，完全な全文検索は必ずしも必要ではありません。むしろ，補完対象文字列からの前方一致検索だけで十分です。

ここでは，複数の補完対象文字列を改行で区切ったテキスト・ファイルを用意します。各行はユーザーに提示する補完文字列になります。例えば，製品名，人名，住所の一覧などが考えられるでしょう。Suffix Arrayはスケーラビリティがあるので，数十～数百Mバイトのデータを作成しても問題ありません。

　例として，フリーの形態素解析用辞書であるipadicから組織名だけを取り出した一覧を補完対象として使ってみます（実際のテキストはこちら）。

金沢美術工芸大
佐賀大学
早大
...

　各行の先頭から前方一致検索する場合，mksaryの-lオプションを使ってインデックスを作成します。デフォルトではテキスト中のすべての位置インデックス・ポイントを置きますが，-lを使うことで各行の先頭のみに限定できます。

% mksary -l -c utf-8 sample.txt

サーバーCGIの実装

　サーバーCGIは，補完候補を提供するだけでよいので，第3回で紹介したのものよりも簡単です。

　関数print_resultでは，前回と同様にsary_searcher_get_next_occurrence 使ってクエリーの出現位置を順に取得しています。さらに，出現位置から改行までの文字列を取り出して出力します。補完候補は，改行で区切られたテキストですから，改行までの文字列は，ユーザーが求める補完文字列になります。

void print_result(SarySearcher *searcher, const char *query)
{
  SaryText *text;
  int num_result = 0;

  sary_searcher_sort_occurrences(searcher);

  while ((text = sary_searcher_get_next_occurrence(searcher)) &&
         num_result++ < NUM_RESULT) {
    const char *eof   = sary_text_get_eof(text);
    const char *start = sary_text_get_cursor(text);

    for (; (start != eof && *start != '\r' && *start != '\n');  ++start) {
      switch (*start) {
      case '>': printf("&gt;");  break;
      case '<': printf("&lt;");  break;
      case '&': printf("&amp;"); break;
      default:  putchar(*start);
      }
    }
    printf("\n");
  }
}

　完全なソースはこちらにあります。実際には，エラー・メッセージを補完対象に入れないために，エラー処理を若干変更しています。

　ソースが出来上がったら，コンパイルして実行バイナリを作ります。環境によって方法が異なりますが，一般には次のコマンドでコンパイルします。詳しくは前回の記事をご覧下さい。

% gcc -Wall -O2 `glib-config --cflags` complete.c -o complete.cgi 
`glib-config --libs` -lsary -lpthread

動作確認

　次のような動作確認用のHTMLファイルを作成します。

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" >
<html><head></head>
<body>
<script type="text/javascript" charset="UTF-8" src="initcompletion.js"></script>
<script type="text/javascript" charset="UTF-8" src="complete.js"></script>
<form>
<input id="query" type="text" size="50">
</form>
</body>
</html>

　実際にページにアクセスしてテキスト・ボックスに何か入力してみましょう。次々と候補が補完されるでしょう（図3［拡大表示］）。

応用例：郵便番号から住所の補完

　インクリメンタル検索のソースをほんの少し修正するだけで予測・補完インタフェースが作成でることがわかりました。実際に郵便番号から住所を補完するアプリケーションを作って理解を深めたいと思います。

　まず，郵便番号とそれに対応する住所の一覧を作成します。郵政省のWebページからCSVファイルをダウンロードし，それを適当に加工したものを使います。各行が郵便番号と住所のペアになっています。郵便番号と住所の間にはスペースを挿入しておきます（以下のリスト参照。ソースはこちら）。

001-0000 北海道札幌市北区
001-0010 北海道札幌市北区北十条西
001-0011 北海道札幌市北区北十一条西
001-0012 北海道札幌市北区北十二条西
001-0013 北海道札幌市北区北十三条西
...

　次に，先ほどと同じようにSuffix Arrayのインデックスを作成します。

% sary  -c utf-8 -l zip.txt

　HTMLページには，入力覧を二つ用意します。郵便番号用と住所用の入力覧です。

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" >
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" >
<html>
<head></head>
<body>
<script type="text/javascript" charset="UTF-8" src="initcompletion.js"></script>
<script type="text/javascript" charset="UTF-8" src="zip.js"></script>
<form>
<table border=0>
<tr>
<td>郵便番号</td><td><input id="zip" type="text" size="9"></td>
</tr>
<tr><td>住所</td><td><input id="address" type="text" size="60"></td>
</tr>
</table>
</form>
</body>
</html>

　zip.jsでは，コールバック関数の中身を変更します。サーバからのレスポンスは，郵便番号と対応する住所をスペースでつないだ文字列です。コールバック関数の中で，文字列を郵便番号と住所に分解して，それぞれのテキスト・ボックスに入力します。

.. 中略
function peekQuery () {

  if (! xmlhttp) xmlhttp = createXmlHttpRequest();

  if (! xmlhttp || xmlhttp.readyState == 1 ||
      xmlhttp.readyState == 2 || xmlhttp.readyState == 3){
    return;
  }

  var textbox = document.getElementById('zip');
  var query   = encodeURI(textbox.value);

  if (query == "") {
    textbox.clearCompletionItems();
  } else if (oldquery != query) {
    xmlhttp.open("GET", "zip.cgi?" + query, true);
    xmlhttp.onreadystatechange = function() {
      if (xmlhttp.readyState == 4 && xmlhttp.status == 200
      && xmlhttp.responseText != "") {
        var ary = xmlhttp.responseText.split(/\n/);
        textbox.showCompletionItems(
                    ary,
                    function(n) {
          textbox.clearCompletionItems();
          var tmp = ary[n].split(/ /);
          document.getElementById('zip').value = tmp[0];
          document.getElementById('address').value = tmp[1];
          oldquery = encodeURI(textbox.value); } );
      }
    }
    xmlhttp.send(null)
  }

  oldquery = query;
}
.. 中略

　CGI（zip.c）も complete.cのインデックス・ファイルの指定を変更するだけで大きな変更はありません。コンパイルも同様です。

#define NUM_RESULT 10
#define INDEX "zip.txt" /* INDEX を変更 */

中略..

% gcc -Wall -O2 `glib-config --cflags` zip.c -o zip.cgi `glib-config --libs`
 -lsary -lpthread

　ページにアクセスして動作を確認してみましょう。郵便番号の一部を入力すると住所が補完され，候補から選択するだけで住所が入力できます（図4［拡大表示］）。

おわりに

　前回のKWICのサンプルを改良して予測・補完インタフェースを作成しました。 KWICと予測・補完インタフェースはまったく違うものに見えますが，内部で使われる技術はほぼ同じことがわかります。前回と今回紹介したSuffix Arrayは，テキスト処理と名の付くものならば，ほぼすべてに利用できる汎用的なアルゴリズムです。実際にSuffix Arrayは，今回のインタフェースだけでなく，形態素解析の辞書，予測入力付きのIMEなど，多くのアプリケーションで使われています。

　よりよいユーザビリティのためには，ローマ字入力のサポートも考えられます。MeCabやKakasiを使ってテキストにローマ字の読みを付与しておくことで，ローマ字入力もサポートできるようになるでしょう。

　次回が最終回の予定です。これまでの記事をまとめながら，Ajaxアプリケーションを作成するうえでの留意点を紹介したいと思います。お楽しみに。

この連載記事の目次へ