(57)【特許請求の範囲】
【請求項１】
複数の記号で構成される記号列に対し、記号の種類の出現順序の組み合わせを表した木構造を用いて当該記号列の出現確率を計算する記号列確率計算装置であって、
前記木構造の各節点に対応する複数のメモリセルから構成され、木構造のルート節点に対応するメモリセルは、記号列の集合（コーパス）に含まる記号の総数、及び、直属下位の各節点の記号の種類と該節点に対応するメモリセルのアドレスを格納し、木構造の途中の節点に対応する各メモリセルは、当該節点での記号あるいは記号列の出現頻度、及び、直属下位の各節点の記号の種類と該節点に対応するメモリセルのアドレスを格納し、木構造の最下位の節点に対応する各メモリセルは、当該節点での記号列の出現頻度を格納したメモリ部と、
入力された記号列について、先頭の記号から順番に該記号の種類をキーとして、前記メモリ部の前記ルート節点のメモリセルを起点に、直属下位の該記号の節点に対応するメモリセルを辿って、当該記号列に関与する出現頻度を読み出し、あらかじめ決められた計算式に、前記ルート節点のメモリセルに格納された記号の総数と共に前記読み出した出現頻度を代入して該記号列の出現確率を計算して出力する演算部と、
を具備することを特徴とする記号列確率計算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本明は、自然言語処理などに用いられる複合確率の計算に必要な、記号列の出現頻度を効率よく格納し、記号列の出現確率を計算する記号列確率計算装置に関する。
【０００２】
【従来の技術】
従来の確率格納方法を、記号列の確率の計算を例にとって説明する。１つ前の記号ｗt-1に続いて記号ｗtが出現する確率は、例えば次式の複合確率で計算できることが知られている（例えば、川端豪他「二項事後分布に基づくＮ-gram言語モデルのＢack-off平滑化」，信学技報，ＴＥＣＨＮＩＣＡＬ  ＲＥＰＯＲＴ  ＯＦ  ＩＥＩＣＥ，ＮＬＣ９５-５８，ＳＰ９５-９３（１９９５-１２）参照。
【０００３】
【数１】
0003838525.tif 000002
【０００４】
但し、Ｍは記号の種類数、Ｎは前もって収集した記号列の集合（以下、コーパスと呼ぶ）に含まれる記号の総数、ｃ（ｗt）は記号ｗtのコーパス中での出現頻度、ｃ（ｗt-1，ｗt）は記号列ｗt-1，ｗtのコーパス中での出現頻度、γは任意の定数である。
【０００５】
簡単のために、記号の種類をＡ，Ｂの２種類のみに限定した場合の、従来の確率格納方法の一例を図２に示す。確率を格納するための木構造は、節点２００〜２０６とそれをつなぐ枝２１０〜２１５から構成されている。最上位の節点２００をルートという。最下位の節点２０３〜２０６を葉という。葉２０３〜２０６は複合確率を計算するのに必要な記号の出現頻度を格納するためのメモリ２２０〜２３１を有する。但し、対応する記号の出現頻度が０のときは、メモリ削減のために葉そのものを省略する。
【０００６】
ここで、例えば記号Ａに続いて記号Ｂが出現する複合確率を計算するためには、ルート２００から節点２０１、葉２０４とたどって、該葉２０４のメモリ２２１，２２５，２２９に格納された値を用いて次のように複合確率を計算する。
【０００７】
【数２】
0003838525.tif 000003
【０００８】
但し、Ｎはコーパス中の記号の総数。記号の種類はＡ，ＢのみなのでＭ＝２、任意定数γ＝０．１と設定した。図２からわかるように、従来の確率格納方法は葉の数の３倍のメモリを必要とする。
【０００９】
【発明が解決しようとする課題】
従来の確率格納方法では、複合確率を計算するための記号列の出現頻度を格納するために木構造の葉の数の３倍のメモリを必要とし、記号の種類が増加するに伴い、膨大なメモリが必要になるという問題があった。
【００１０】
本発明の目的は、複合確率の計算に必要な記号列の出現頻度を、従来に比べて効率よく格納し、それによる記号列確率計算装置を提供することにある。
【００１１】
【課題を解決するための手段】
本発明は、複数の記号で構成される記号列に対し、記号の種類の出現順序の組み合わせを表した木構造を用いて当該記号列の出現確率を計算する記号列確率計算装置において、前記木構造の各節点に対応する複数のメモリセルから構成され、木構造のルート節点に対応するメモリセルは、記号列の集合（コーパス）に含まる記号の総数、及び、直属下位の各節点の記号の種類と該節点に対応するメモリセルのアドレスを格納し、木構造の途中の節点に対応する各メモリセルは、当該節点での記号あるいは記号列の出現頻度、及び、直属下位の各節点の記号の種類と該節点に対応するメモリセルのアドレスを格納し、木構造の最下位の節点に対応する各メモリセルは、当該節点での記号列の出現頻度を格納したメモリ部と、入力された記号列について、先頭の記号から順番に該記号の種類をキーとして、前記メモリ部の前記ルート節点のメモリセルを起点に、直属下位の該記号の節点に対応するメモリセルを辿って、当該記号列に関与する出現頻度を読み出し、あらかじめ決められた計算式に、前記ルート節点のメモリセルに格納された記号の総数と共に前記読み出した出現頻度を代入して該記号列の出現確率を計算して出力する演算部とを具備することを特徴とする。
【００１２】
【発明の実施の形態】
図１に、本発明による確率格納方法の一実施例の概念図を示す。図１でも、簡単のために記号の種類をＡ，Ｂの２種類のみに限定した場合を示す。確率を格納するための木構造、すなわち、記号列の出現順序の組み合わせを表わした木構造は、本例では節点１００〜１０６とそれをつなぐ枝１１０〜１１５から構成されている。最上位の節点１００をルートという。節点１００〜１０６は複合確率を計算するのに必要な記号の出現頻度を格納するためのメモリ１２０〜１２３を有する。なお、対応する記号の出現頻度が０の節点は省略される。
【００１３】
例えば、先行記号Ａに続いて後続記号Ｂが出現する複合確率を計算するためには、ルート１００から節点１０１、節点１０４とたどって、節点１０４のメモリ１２１に格納された値から確率の分子ｃ（Ａ，Ｂ）の値を、節点１０１のメモリ１２４に格納された値から確率の分母ｃ（Ａ）の値を得る。また、後続記号Ｂに対しても、同様にルート１００から節点１０２とたどり、節点１０２のメモリ１２５より確率の分子ｃ（Ｂ）の値を、ルート（最上位節点）１００のメモリ１２６より確率の分母としてＮの値を得る。これらメモリ１２１，１２４，１２５，１２６に格納された値を用いて、例えば先の（１）式より、次のように複合確率を計算する。
【００１４】
【数３】
0003838525.tif 000004
【００１５】
但し、Ｎはコーパス中の記号の総数。記号の種類はＡ，Ｂの２種類のみなので、Ｍ＝２、任意定数γ＝０．１と設定した。
【００１６】
図１の本発明による確率格納方法の実施例では、図２に示した従来の確率格納方法の例で必要であった１２個のメモリが７個に削減され、複合確率の計算に必要な記号列の出現頻度がより効率的に格納される。
【００１７】
図３に、図１の木構造に対応する具体的メモリ実装例を具備する本発明の記号列確率計算装置のブロック図を示す。演算部３１０は、記号入力端子３００より記号列を受け取り、メモリ部３３０に記憶されている内容を用いて、記号列の出現確率である複合確率を計算し、確率出力端子３２０に出力する。メモリ部３３０は複数のメモリセル３３１〜３３７から構成され、各メモリセルはアドレスで区別される。各メモリセル３３１〜３３７には、記号の種類とそれに対応する他のメモリセルのアドレス、及び、出現頻度の一部又は全部が格納される。
【００１８】
図３において、メモリ部３３０内の各メモリセルを示している矩形の左側に記された数字が、そのメモリセルのアドレス、矩形の中に記された記号は木構造の直属下位の記号の種類、数字は該記号に対応する他のメモリセルのアドレス、ｃ(  )は記号の出現頻度を記憶していることを表わしている。図１との対応は、メモリセル３３１，３３２，３３３が図１のメモリ１２６，１２４，１２５に該当し、メモリセル３３４，３３５，３３６，３３７が図１のメモリ１２０，１２１，１２２，１２３に該当する。
【００１９】
例えば、記号入力端子３００より記号列ＡＢが入力され、先行記号Ａに続いて後続記号Ｂが出現する複合確率を計算する場合、アドレス１０００のメモリセル３３１より、記号Ａに対応するアドレス１０１０に進み、メモリセル３３２において頻度ｃ（Ａ）を得る。また、このアドレス１０１０のメモリセル３３２より、記号Ｂに対応するアドレス１０４０に進み、メモリセル３３５において頻度ｃ（Ａ，Ｂ）を得る。また、後続記号Ｂに対しては、同様にアドレス１０００のメモリセル３３１より記号Ｂに対応するアドレス１０２０に進み、メモリセル３３３において頻度ｃ（Ｂ）を得る。さらに、アドレス１０００のメモリ３３１からはＮを得る。これらの値より、演算部３１０が（３）式の複合確率の値を計算し、確率出力端子３２０より出力する。
【００２０】
以上、実施例では、簡単のために記号の種類を２種類のみに限定したが、３種類以上に拡張可能であることは容易に類推できる。
【００２１】
【発明の効果】
以上説明したように、本発明を用いれば、複合確率の計算に必要な記号列の出現頻度を、より効率よくメモリに格納して、記号列の出現確率を計算することできる。
【図面の簡単な説明】
【図１】  本発明による確率格納方法の一実施例を示す概念図である。
【図２】  従来の確率格納方法の一例を示す概念図である。
【図３】  本発明の記号列確率計算装置としての構成例を示すブロック図である。
【符号の説明】
１００〜１０６  節点
１２０〜１２６  メモリ
３００  記号入力端末
３１０  演算部
３３０  メモリ部
３３１〜３３７  メモリセル
【図１】
0003838525.tif 000005
【図２】
0003838525.tif 000006
【図３】
0003838525.tif 000007