修飾キー省略入力について
iOS の日本語フリック入力などで実装されている「修飾キー省略入力」という機能について書きます。
次の記事に解説されています。
「しゆうてん」と入力すると、「充電」「終電」「重点」「終点」という候補を出してくれます。
普通なら、「充電」と入れる時には「し x ゆ x う て x ん」（x = 「小 ゛ ゜」キー）と 8回画面を押さないといけないところが、5回のフリックですみます。
隠し機能みたいなものですが、慣れると便利です。
失敗すると修正するのがやっかいなのですが、だんだんと感覚がつかめてきます。
この機能は単語に限らず、文章の変換時にも使えます。
たとえば、「しゆうてんかおわつた」と 10フリックで入力すると、「充電が終わった」という候補が一番に出てきます。
今回は、この機能の一つの実装方法（それが iOS で使われているものと同じかどうかはわかりませんが）について書きます。
これまでこの日記では、「日本語入力を支える技術」で紹介された、"trie" というデータ構造の二つの実装について解説しました。
情報系修士にもわかるダブル配列
LOUDS を普通のプログラマにもわかるように解説してみた （全12回）
trie を利用することにより、日本語の解析・入力などに必要な「共通接頭辞検索」ができます。
共通接頭辞検索を使うことにより、仮名列→漢字列への変換ができるのは、
可変次数 N-gram デコードのアルゴリズムや、N-gram かな漢字変換 （スライド）で紹介した通りです。
（独自のデコードアルゴリズムを使っていますが、最初の部分は bigram モデルです）
ここから、trie を使って、修飾キー省略入力を行う方法について書きます。
その前に、trie から普通に単語を検索する場合について考えます。
これは簡単で、たとえば「がっこう」で検索したい場合、次のようになります。
まず、"R" と書いた根のノードから、「が」のノードを探します。
それから、「っ」「こ」「う」と、次々にたどっていきます。
その途中で、単語になり得るノード（この図で太枠で示したもの）があったら、それに対するデータを拾います。
この例では、「がっこう」で共通接頭辞検索をすると、「が」と「がっこう」という候補が見つかることになります。
これを修飾キー省略入力に応用します。
「がっこう」ではなく、「かつこう」と入力される場合を考えます。
まず考えるのは、「修飾キーが省略された文字から、省略される前への文字へのテーブル」です。
具体的には、「か」と入力された時、それは「か」かもしれないけど「が」かもしれない、という情報を集めたものです。これは、「か→か、が」のように表せます。
修飾キーで変えられないものは、「な→な」のような形で持っておきます。
「つ」は、修飾キーを一回押すと「っ」になり、二回押すと「づ」になるので、これは「つ→つ、っ、づ」として表せます。ハ行も同様に、「は→は、ば、ぱ」のようになります。
このテーブルを使えば、"か つ こ う"という入力があると、それは"(か|が) (つ|っ|づ) (こ|ご) (ぅ|う)" という、2×3×2×2=24通りの可能性があるということがわかります（「ヴ」は考えないことにします）。
これらの可能性をすべて trie で検索します。検索方法は、普通の深さ優先探索を使います。すると、次のようになります。
深さ優先探索なので、まず左端の「か→つ→こ」のルートをたどります。その途中で「か」（「か」、「蚊」など）と「かつ」（「勝つ」など）「かつこ」（「克子」など）を拾います。
「かつこ」の下は行き止まりなので、「かつ」の次の子を探します。そうすると、「（か→つ→）ご→う」というルートがあり、ここで「かつごう」を拾います（「渇仰」という単語があるそうです）。
このようにして、「かつこう」に対する共通接頭辞検索をすると、「か」「が」「かつ」「かつこ」「かつごう」「かっこ」「かっこう」「がつ」「がっこう」という 9個の結果が得られます。「がっこう」に対する結果は 2個だったので、4.5倍になっています。
上のような図を見ると、「検索結果は長さに対して指数的に増えるのでは？」と思うのがプログラマの性だと思いますが、実際にはそういうことにはなりません。
なぜかというと、長くなればなるほど、単語の取り得る形の空間が広がっていくからです。
ここで、単語の取りうる形の空間ということについて、詳しく考えます。
日本語 1文字は、濁音などを含めると、大雑把にいって 100通りぐらいのパターンがあります。
そうすると、もし日本語の単語がこの中で自由に分布しているとすると、たとえば 4文字の単語の場合、それは 100^4=1億通りぐらいの空間の中にあるということになります。
ところで、上で「かつこう」に対して 24通りの検索をした時に、4文字の単語は「かつごう」「かっこう」「がっこう」という 3つも見つかりました。
もし自由に分布しているとすると、これはおかしな話です。まず前提として、人間の語彙はだいたい 5万語ぐらいということがあります。それほど使わない単語（「渇仰」のような）を収録した大型の辞書でも、項目数は10〜20万といったところです。ここでは、4文字の単語の数を 1万とします。 1億通りの中に1万語が均等に分布しているとすると、適当な4文字が単語になる可能性は 1/10000 ぐらいです。
「かつこう」という検索キーは「がっこう」から修飾キーを抜いたものなので、「がっこう」が見つかるのは当たり前なのですが、残りの 23 通りを探しただけで 1/10000 の確率のものが 2個も見つかるというのはおかしな話です。一部の人にだけわかるたとえをすると、麻雀を半荘 3回やっただけで字一色が 2回出るようなものです（参考: http://www2.odn.ne.jp/~cbm15900/html/y99.html）。
結論を言うと、単語はもう少し狭い空間に分布しています。特に漢字の音読みというものは、「ガイ」「ガツ」「ガン」と読む漢字はあっても、「ガア」「ガテ」「ガヨ」とか読む漢字はないというように、大きく偏っています。
漢字音のことを考えると、漢字単位で考えたほうがうまくいくのですが、日本語の語彙には和語や外来語もあるので、ここではあくまで仮名単位で考えます。そうすると、1文字あたりの平均パターンは、だいたい 20ぐらいでしょう。そうすると、20^4=16万通りの可能性の中から 1万語ということになるので、可能性はだいたい 6% です。23回の試行で 2回出てもおかしくないぐらいです。半荘 3回やって、混一色が 2回出る程度です。
ここで、100通りか 20通りかという数字は本質的ではないのですが、あまり実態とかけ離れた数字を使うのもアレなので大雑把に見積もってみました。
次に、6文字の単語の場合を考えます。1文字につき平均 20通りとすると、6文字では 20^6=6400万通りぐらいの空間があることになります。6文字の単語の数は、ここでは 4文字と同じ 1万語あるとします。そうすると、空間の中で単語の割合は 1/6400 ≒ 0.016% ぐらいです。
6文字になると、その分だけ修飾キー省略入力で検索するパスの数も増えます。しかし、それは 1文字につき高々 3通りです。可能な形の空間は 1文字につき 20通りぐらい増えることを考えると、単語が長くなるにつれ急速にスパースになっていくことになります。
たとえば、「共和国」という単語の読みから修飾キーを除いた「きようわこく」という検索キーで日本語辞書を検索する場合を考えます。すると、検索対象は "(き|ぎ) (よ|ょ) (う|ぅ) (わ|ゎ) (こ|ご) (く|ぐ)" で、パターン数は 2×2×2×2×2×2=64通りです。検索パターン数は増えているのですが、単語の割合が大きく下がっているため、たまたま別の単語とぶつかる確率はかなり低くなります。0.016% で当たるような試行が 63回なので、半荘 8回やって四喜和を出すようなものです。なかなか起こることではありません。現に、「きようわこく」に対する他の 6文字の候補はありません。
「きようわこく」で修飾キー省略検索をすると、次のようになります。
見つかるのは、「き（木 etc.）」「ぎ（偽）」「きよ（寄与）」「きょ（居）」「ぎょ（魚）」「きよう（起用）」「きょう（今日）」「ぎょう（行）」「きょうわ（共和）」「きょうわこく（共和国）」の 10個です。修飾キー省略入力でない場合は「き」「きょ」「きょう」「きょうわ」「きょうわこく」の 5個であることを考えると、2倍になっています。下の方に行くほど、急速に枝刈りがされていくのがわかります。
上で挙げた「しゆうてん」の例でも、この 5文字では「充電」「終電」「重点」「終点」の候補があるのに対し、「き」を足して「しゆうてんき」の 6文字にすると、候補は「充電器」のみになります。
まとめると、
単語の文字数が増えると、1文字あたり 20パターン程度、取りうる形の空間が広がる。それに対して、修飾キー省略による検索空間の増加は、1文字あたり 2パターン程度である。よって、文字数が増えれば増えるほど、修飾キー省略によって別候補が見つかる確率は低くなる。
ということです。
また、ある程度の長さからは、文字数が増えるに従って単語の数も減っていきます。6文字限定しりとりと 8文字限定しりとりをすると、後者のほうがずっと難しいことがわかると思います。
そういうわけで、修飾キー省略入力による検索結果の増加を考える場合、探索空間が指数的に増えることによる計算量の爆発は心配しなくても大丈夫ということです。
次に、修飾キー省略入力による検索結果を使って、文をデコードする場合を考えます。
bigram モデルの場合、計算量は（ある位置で始まる／終わるノードの数の平均）^2 です。
この「ある位置で始まる／終わるノードの数の平均」がどれくらい増えるのかは見積もりが難しいですが、上で見たように、長い文字列に対しては検索結果はほとんど増えません。ボリュームゾーンは漢字 1・2文字の漢語です。和語はもともと拗音が少なく、濁音も語頭には立ちにくいので、候補数はあまり増えません。漢語は、1文字のものは清音・濁音で 2パターンになり、2文字のものは前後の漢字の清濁で 4パターンになり得ます。「充電」「終電」「重点」「終点」はその一例です。しかし、こういうものは多くはありません。1つの位置ごとのノード数は、大雑把に 2〜3倍程度でしょう。すると、計算量はその 2乗で 4〜9倍程度ということになります。濁音になり得ない文字（ア行・ナ行など）が多い場合は、もっと少なくなります（「ぁ」「ぃ」等は少ないので、大雑把な見積もりをする時には無視できます）。
ここで、実際に「じゅうでんがおわった」を普通に bigram デコードする場合と、「しゆうてんかおわつた」を修飾キーが省略されたものとして bigram デコードする場合を比べてみます。同音のノードは、ここでは一つにまとめています。
「じゅうでんがおわった」の場合、ノードは次のようになります。
じ ゅ う で ん が お わ っ た ｜じ｜（字 etc.） ｜じ ゅ｜（寿） ｜じ ゅ う｜（十） ｜じ ゅ う で ん｜（充電） ｜う｜（鵜） ｜う で｜（腕） ｜で｜（で） ｜で ん｜（伝） ｜が｜（が、蛾） ｜が お｜（顔） ｜お｜（尾） ｜お わ っ た｜（終わった） ｜わ｜（輪） ｜わ っ た｜（割った） ｜た｜（多）
ノード数は 15、それぞれの位置での連接の合計は 12です。
「しゆうてんかおわつた」の場合、次のようになります。
し ゆ う て ん か お わ つ た ｜し｜（市） ｜じ｜（字） ｜じ ゅ｜（寿） ｜し ゆ う｜（私有） ｜し ゅ う｜（週 ｜じ ゅ う｜（十） ｜し ゅ う て ん｜（終点） ｜し ゅ う で ん｜（終電） ｜じ ゅ う て ん｜（重点） ｜じ ゅ う で ん｜（充電） ｜ゆ｜（湯） ｜ゆ う｜（夕） ｜う｜（鵜） ｜う て｜（打て） ｜う で｜（腕） ｜て｜（手） ｜で｜（で） ｜て ん｜（天） ｜で ん｜（伝） ｜て ん か｜（天下） ｜か｜（か、蚊） ｜が｜（が、蛾） ｜か お｜（顔） ｜が お｜（顔） ｜お｜（尾） ｜お わ っ た｜（終わった） ｜わ｜（輪） ｜わ っ た｜（割った） ｜つ｜（津） ｜つ た｜（ツタ） ｜た｜（多）
ノード数は 31、それぞれの位置での連接の合計は 71です（多いので数え間違いがあるかもしれませんが）。全体でのノード数は約 2倍、連接数は 約 6倍になっています（連接位置の問題などもあり、ノード数のぴったり 2乗になるわけではありません）。上で、連接数は多くて 4〜9倍と書きましたが、その範囲に収まっています（もちろん、これは多いものを選んだ例なので、平均的にはもっと少なくなります）。
ここで使ったような trie の検索方法は、Mozc で使われている rx の 1.1.2 で実装されています。rx_search_expand に文字展開用コールバック関数と付随データを渡すと、trie で 1文字検索するたびに、その文字と付随データへのポインタを引数としてコールバック関数が呼び出されるので、そこで文字を展開します。たとえば、'a' を 'a'/'e' と展開したければ、'a' を引数として呼び出された時に "ae(\0)"を返すようにします。
rx では、検索キー 1バイトごとにこの処理を行います。ですので、仮名 1文字を 1バイトとするような独自のエンコーディング方式を使うのがよいでしょう。たとえば、Unicode の基本ラテン領域と仮名の領域を入れ替えて、それを UTF-8 方式でマルチバイトにすれば、他の文字とぶつかる心配がなく、安全です。
