yasuokaの日記： キラキラネームの読み方と非決定性有限オートマトン

1月19日の日記で私(安岡孝一)がつけたコメントに対して、どうして非決定性有限オートマトンなのか、という御質問をいただいた。私個人としては、正直もう飽きてきているのだが、まあ、今後のこともあるので、とりあえず山西良典・大泉順平・西原陽子・福本淳一『人名の言語的特徴の分析に基づくキラキラネーム判定』(日本感性工学会論文誌、2015年10月9日)の図1「漢字の音訓読みと人名の読み方の部分一致判定アルゴリズム」を見てみよう。

1. i=0とする．j=0とする．start=0とする．
2. 漢字c_i の読み方に部分一致する最大の系列(p_start, ・・・, p_j )を探すまでj=j+1とする．
3. i==C_Numberc かつj==PC_Numberp であれば，部分一致と判定して，終了する．i==C_Numberc またはj==PC_Numberp であれば，部分一致しないと判定して，終了する．それ以外の場合は，手順4.へ行く．
4. start=j+1とする．i=i+1とする．j=j+1とする．2.へ戻る．

このアルゴリズムで、たとえば「太一(たいち:男)」を判定してみよう。c₀ =太、c₁ =一、p₀ =た、p₁ =い、p₂ =ち、である。この論文中には「PC_Numberp 」なる値は定義されていないので、さてどうしたものかと悩むが、アルゴリズムの意図を汲む限りでは、C_Numberc =1、PC_Numberp =2、なのだろう。常用漢字表における「太」の音訓は「タイ・タ・ふとい・ふとる」なので、c₀ (太)の読み方に部分一致する最大の系列はp₀p₁ (たい)となる。次に、「一」の音訓は「イチ・イツ・ひと・ひとつ」なので、c₁ (一)の読み方とp₂ (ち)は少なくとも前方一致しない。この結果、図1のアルゴリズムは「太一(たいち:男)」を「部分一致しないと判定」すると考えられる。

このバグに対し、私なら、常用漢字表の音訓で非決定性有限オートマトンを構成し、その非決定性有限オートマトンが名前の読みを受理するかどうか判定すればいい、と考える。たとえば「太一」に対しては、以下の遷移表で示されるような、λ遷移(入力文字なしの遷移)を許す非決定性有限オートマトン(初期状態A、受理状態Z)を構成することになる。

A―た→B　B―い→C
A―た→D
A―ふ→E　E―と→F　F―い→G
A―ふ→H　H―と→I　I―る→J
B―λ→K　C―λ→K　D―λ→K　E―λ→K　F―λ→K　G―λ→K　H―λ→K　I―λ→K　J―λ→K
K―い→L　L―ち→M
K―い→N　N―つ→O
K―ひ→P　P―と→Q
K―ひ→R　R―と→S　S―つ→T
L―λ→Z　M―λ→Z　N―λ→Z　O―λ→Z　P―λ→Z　Q―λ→Z　R―λ→Z　S―λ→Z　T―λ→Z

λ遷移を取り除いて、さらに決定性有限オートマトンに変換すると、たとえば以下の遷移表になるだろう(初期状態A、受理状態C・L・R・S・T)。

A―た→B　 A―ふ→E　 B―い→C　 B―ひ→R　 C―い→L　 C―ち→T　 C―つ→T　 C―ひ→R　 E―と→F　 E―ひ→R　 F―い→C　 F―ひ→R　 F―る→J　 J―い→L　 J―ひ→R　 L―ち→T　 L―つ→T　 R―と→S　 S―つ→T

あるいは、決定性有限オートマトンに変換するのではなく、元の非決定性有限オートマトンと等価な正規表現を構成して、egrepに食わせるのでもかまわない。

^(た(い)?|た|ふ(と(い)?)?|ふ(と(る)?)?)(い(ち)?|い(つ)?|ひ(と)?|ひ(と(つ)?)?)$

ちょっと冗長だが、機械的に構成しても問題なく動作する。この正規表現は、egrep内部では、もちろん、非決定性有限オートマトンに変換される。つまり、曖昧な文字列一致判定においては、非決定性有限オートマトンが最も簡便で有利であり、ヘタに他のアルゴリズムを準備したところで、この論文のようにバグってしまうということだ。