(57)【要約】【課題】  ノード情報の記憶に要するデータ量が削減された木構造のデータベースを生成するデータベース作成装置および方法を提供する。【解決手段】  ノード番号付与部（１０３）は、木構造の上位層から下位層に向けて、階層ごとに、親ノードのノード番号順に各ノードに連番のノード番号を付与する。その後、子ノード相対番号付与部（１０４）は、各ノードに、当該ノード番号とその子ノードのノード番号との相対値を示す子ノード相対番号を付与する。【選択図】  図１Ｂ
2006178013.tif 000002
【特許請求の範囲】
【請求項１】
木構造のデータベースを作成するデータベース作成装置であって、
木構造の上位層から下位層に向けて、階層ごとに、親ノードのノード番号順に各ノードに連番のノード番号を付与するノード番号付与手段と、
各ノードに、当該ノード番号とその子ノードのノード番号との相対値を示す子ノード相対番号を付与する子ノード相対番号付与手段と、
を有することを特徴とするデータベース作成装置。
【請求項２】
前記子ノード相対番号付与手段は、各ノードに、当該ノード番号とその子ノードのうちの特定の１個の子ノードのノード番号との相対値を示す１個の子ノード相対番号のみを付与することを特徴とする請求項１に記載のデータベース作成装置。
【請求項３】
作成するデータベースの木構造のリーフ数に基づいて、前記子ノード相対番号のデータ型を決定するデータ型決定手段を更に有することを特徴とする請求項１または２に記載のデータベース作成装置。
【請求項４】
前記データ型決定手段は、データサイズの異なる複数のデータ型の中から、作成するデータベースの木構造のリーフ数を格納可能な最小データサイズのデータ型を選択することを特徴とする請求項３に記載のデータベース作成装置。
【請求項５】
請求項１から４までのいずれかに記載のデータベース作成装置によって作成された木構造のデータベースを用いてデータ検索を行うデータ検索装置。
【請求項６】
請求項１から４までのいずれかに記載のデータベース作成装置によって作成された木構造のデータベースを認識辞書として用いて音声認識を行う音声認識装置。
【請求項７】
コンピュータにより木構造のデータベースを作成するデータベース作成方法であって、
木構造の上位層から下位層に向けて、階層ごとに、親ノードのノード番号順に各ノードに対し連番のノード番号を生成させ、これらのノード番号をメモリに記憶させるステップと、
ノード毎に、当該ノード番号とその子ノードのノード番号との相対値を示す子ノード相対番号を生成させ、この子ノード相対番号をメモリに記憶させるステップと、
を有することを特徴とするデータベース作成方法。
【請求項８】
コンピュータ実行可能なプログラムであって、木構造のデータベースを作成するために、
木構造の上位層から下位層に向けて、階層ごとに、親ノードのノード番号順に各ノードに対し連番のノード番号を生成させ、これらのノード番号をメモリに記憶させるためのコードと、
ノード毎に、当該ノード番号とその子ノードのノード番号との相対値を示す子ノード相対番号を生成させ、この子ノード相対番号をメモリに記憶させるためのコードと、
を有することを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、木構造のデータベースを作成する装置および方法に関する。
【背景技術】
【０００２】
音声認識や言語解析においては、単語の情報を高速に探索するために、音素や音素列をノードとする木構造の辞書が用いられる。たとえば音声認識では、入力音声の特徴を抽出し、認識辞書に記述された単語と音響モデルに従い、各単語を構成する音響モデルの出力確率を求め、Viterbi探索などの探索手法を用いて、単語あるいは単語を構成する各音素の各状態の尤度を探索し、音声認識を行う。特開２０００−２９３１９１号公報（特許文献１）は、入力音声の各時間区間で単語の各音素の尤度計算の演算量を減らすため、木構造辞書を用いて単語で共有できる部分の尤度計算回数を減らす技術を開示している。
【０００３】
図９に音声認識で用いられる従来の木構造辞書の一例を示す。同図において、９０１が単語の音素や音素列によるノードである。このノードが複数の単語間で共通されることで木構造が構成される。９０２はノード間の親子関係を結ぶリンクである。９０３はノードの識別子となるノード番号である。９０４は木構造辞書に格納されるデータである。木構造の先頭のノード（ルートノード）から終端のノード（リーフノード）まで辿ると、そのノードに含まれる音素系列が単語を表し、その単語のデータ９０４がリーフノードから取得できる。
【０００４】
音声認識における尤度計算は、基本的に各ノードの音素に対して行う必要がある。しかし、木構造辞書の場合には、先述のとおり複数の単語間でノードが共有されるから、そのような共有されたノードの音素についての尤度計算も共有することが可能である。たとえば同図において、ノード番号２の“ｋ”における尤度計算は、単語“川野”、“木村”、“木元”、“木島”の４単語で共有できる。このため、木構造辞書を採用せずにそれぞれの単語について尤度計算する場合は４回計算しなければならないところを１回の計算で済ませることができ、高速化することができる。
【０００５】
木構造辞書を構成するには、各ノード９０１に、当該ノードから遷移する子ノードの情報をもたせる必要がある。図１０に木構造辞書の各ノードが有するノード情報を示す図で、代表例として、図９のノード１４およびノード１７のノード情報の例を示す。図示のように、ノード情報には、「音素数」、「音素」、「子ノード数」、「子ノード番号」、「データ数」、「データ番号」の情報が含まれる。ここで、「音素数」および「音素」は各ノードにおける尤度計算を行うために必要な情報である。「子ノード数」および「子ノード番号」の情報はノードを遷移していくために必要な情報である。「データ数」は当該ノードにリンクするデータの数、すなわち、全く同じ音素列の語数、を示している。なお、これが０であれば、当該ノードはリーフノードではないことがわかる。また、「データ番号」は単語終端を表すリーフノードからその単語の情報を取得するために必要な情報である。
【０００６】
【特許文献１】特開２０００−２９３１９１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、木構造辞書のハードウェアへの実装に際しては、ノード情報の記憶容量が問題になる。すなわち、木構造辞書の登録単語数が多くなるほどノード数も多くなり、ノード情報の記憶に要するデータ量が増大する。そのため、ノード情報の記憶容量の低減を図ることが要請されている。
【課題を解決するための手段】
【０００８】
本発明の一側面に係るデータベース作成装置は、例えば、木構造のデータベースを作成するデータベース作成装置であって、木構造の上位層から下位層に向けて、階層ごとに、親ノードのノード番号順に各ノードに連番のノード番号を付与するノード番号付与手段と、各ノードに、当該ノード番号とその子ノードのノード番号との相対値を示す子ノード相対番号を付与する子ノード相対番号付与手段とを有する。
【発明の効果】
【０００９】
本発明によれば、木構造データベースのノード情報の記憶に要するデータ量を低減することができる。
【発明を実施するための最良の形態】
【００１０】
前述のように、木構造辞書のハードウェアへの実装に際しては、ノード情報の記憶容量の低減を図ることが要請されている。
【００１１】
そこで、先に示した図１０のノード情報のデータサイズについて、個々に検討してみる。
【００１２】
まず、「データ番号」の記憶に要するデータサイズは、登録単語数から容易に予測することができる。たとえば１００単語音声認識のタスクであれば、「データ番号」を格納するために必要なデータ型は１byteで十分であろう。「データ数」は、先述のとおり全く同じ音素列の語数を示すものであり、その語数に制限を設けることで記憶に必要なデータサイズを決定できる。「音素数」もまた、単語の音素長を制限することでその記憶に必要なデータサイズを決定できる。また、「子ノード数」は、どれだけそのノードから遷移が拡がっても木構造はリーフの数より拡がることはないため、「データ番号」と同様に、記憶に要するデータサイズを決定できる。逆にいえば、これらの情報のデータサイズは概ね、木構造辞書を用いるアプリケーションに求められている性能に依存して決まるものである。
【００１３】
一方、「子ノード番号」は数が多い上に、同一単語数や音素セットでも単語の部分共有の度合いや単語長によって変わり得るため、ノード番号を保持するのに必要なデータサイズを登録単語や音素数から単純に予測することは難しい。そのため従来は、「子ノード番号」の記憶には、冗長性を盛り込んで、比較的大きなデータサイズが設定されていた。
【００１４】
本発明は、このような「子ノード番号」のデータサイズの冗長性に着目して、この冗長性を小さくする処理を導入することにより、ノード情報のデータサイズの削減を図る。
【００１５】
以下、図面を参照して本発明の好適な実施形態について詳細に説明する。
【００１６】
図１Ａは、本発明のデータベース作成装置の機能を実現するコンピュータシステムの構成例を示す図である。
【００１７】
図示のコンピュータシステムは、装置全体の制御をつかさどるＣＰＵ１、ブートプログラムや固定的なデータ等を記憶しているＲＯＭ２、主記憶装置として機能するＲＡＭ３をはじめ、以下の構成を備える。
【００１８】
ＨＤＤ４はハードディスク装置であって、ここにＯＳ１０のほか、データベース作成プログラム１１、データベース作成プログラム１１の実行によって生成されるデータベースとしての木構造辞書１０５、木構造辞書１０５のリーフノードにリンクされる単語のリストなどを含んだデータ１０１が格納される。
【００１９】
また、ＶＲＡＭ５は表示しようとするイメージデータを展開するメモリであり、ここにイメージデータ等を展開することで表示装置の一例としてのＣＲＴ６に表示させることができる。７および８はそれぞれ、各種入力操作を行うためのキーボードおよびマウスで、ＣＰＵ１に割り込み信号を伝えるキーボードコントローラ７ａおよびマウスコントローラ８ｂに接続されている。
【００２０】
データベース作成プログラム１１は、キーボード７あるいはマウス８からの特定の指示イベントに応じてＲＡＭ３にロードされ、ＣＰＵ１によって実行される。これによってこのコンピュータシステムはデータベース作成装置として機能することになる。
【００２１】
図１Ｂは、本実施形態におけるデータベース作成装置の機能構成を示すブロック図である。上記のとおり、本実施形態におけるデータベース作成装置はデータベース作成プログラム１１の実行によって実現されるものであるが、そのデータベース作成プログラム１１は以下のモジュール構成を有する。
【００２２】
１０２は、データ１０１を取得し、データ間で音素など共通する箇所にノードを作成し、木構造を生成する木構造生成部である。１０３は、木構造の各ノードに番号を付与するノード番号付与部である。１０４は、ノードから遷移し得る子ノードの情報を、ノード番号の相対値としてノードに付与する子ノード相対番号付与部である。これらの処理の結果として、木構造辞書１０５が生成され、ＨＤＤ４に格納されることになる。
【００２３】
図２は、本実施形態におけるデータベース作成装置によるデータベース作成処理を示すフローチャート、図３は、このデータベース作成処理によってノード番号が付与されて作成される木構造辞書の一例を示す図である。以下、図２、図３を参照して、本実施形態におけるデータベース作成処理を詳しく説明する。
【００２４】
まず、ステップＳ２０１において、ノード番号付与部１０３は、ルートノードに番号０を付与し、番号０に基づく場所（例えば配列の０番目）にルートノードのノード情報を格納する。
【００２５】
次に、ステップＳ２０２において、ルートノードの子ノードを第一階層としてリストアップする。図３の例ではルートから遷移し得る“a”、“k”、“y”のノードである。
【００２６】
これらに対し、ステップＳ２０３で、ノード番号付与部１０３が、親ノードの番号順にノード番号を付与し、それぞれのノード情報をノード番号に基づく場所に格納する。第一階層では親ノードは全てノード０なので、付与の順番は任意となる。
【００２７】
次に、ステップＳ２０４で、子ノード相対番号付与部１０４が、それぞれの子ノードとその親ノードとの相対番号を、親ノードのノード情報に登録する。
【００２８】
これで第一階層のノード登録は終了し、ステップＳ２０５でそれぞれのノードのさらに子ノードを第二階層としてリストアップする。
【００２９】
次に、ステップＳ２０６で子ノードが無ければ終了し、子ノードがある場合にはステップＳ２０３に戻る。図３においては“a”に２つ、“k”に３つ、“y”に２つの子ノードがあるため、ステップＳ１０３に戻り、親ノードの番号順に、“a”、“k”、“y”の子ノードの順番で番号を付与する。これらの操作を子ノードが無くなる階層まで続けると、図３のように各ノードにノード番号が振られ、各ノード情報に子ノードの相対番号が付与される。
【００３０】
図４に、各ノードが保持するノード情報の一例として、ノード８のノード情報を示す。図示のように、ノード情報には、ノードに含まれる「音素数」、ノードに含まれる「音素」、「子ノード数」、「子ノード相対番号」、「データ数」、「データ番号」が含まれる。図３のノード番号８のノード“a m a”は、ノード１６、１７を子ノードとするため、「子ノード相対番号」は自分の番号８を差し引いた８、９となる。各階層で木構造はどんなに拡がっても木構造のリーフの数以上には拡がらないため、「子ノード相対番号」は、どんなに大きくとも木構造のリーフノードの数、すなわち音素列の異なるデータ数に制限されることになる。これにより、ノード情報の記憶に要するデータ量を削減することができる。
【００３１】
あるいは、「子ノード相対番号」については、次のようにデータを保持するようにしてもよい。
【００３２】
ノード番号付与部１０３は、親ノードの番号順に子ノードの番号を連番で付与する。したがって、同一の親ノードを持つ子ノードの番号は連番となる。例えば、図３のノード番号８“a m a”の子ノードの番号は、連番の１６、１７である。そうすると、子ノードの数さえ既知であれば、特定位置の１個の子ノードの番号だけを「開始子ノード相対番号」として保持しておくだけで、その他の子ノードの番号も復元できることになる。図５は、この考えに基づき、子ノードの番号を全て記憶するのではなく、「開始子ノード相対番号」を記憶するようにした例を示している。具体的には、「子ノード数」は２、「開始子ノード相対番号」は８、と記述されている。この情報を基に、子ノード１６が復元されるのみならず、その連番として子ノード１７も復元される。これにより、ノード情報の記憶に要するデータ量を更に削減することができる。
【００３３】
以上説明したデータベース作成処理の特徴は、子ノードを特定する情報を親ノードからの相対値で保持することにより、子ノード番号情報の大きさの最大値をリーフノード数に制限した点にある。このため、ノード情報の記憶に要するデータ量を削減できる。具体的には、従来は「子ノード番号」（図１０を参照）については２byteのデータ型の変数によって表現する必要があったところ、本実施形態の「子ノード相対番号」については１byteのデータ型の変数で表現できる余地が生まれることになる。
【００３４】
もっとも、子ノード相対番号の記憶に必要なデータ量は、アプリケーションによって木構造辞書の規模が異なるので、一律に決められるものではない。そこで、以下で説明する別の実施形態では、子ノード相対番号のデータ型を複数用意しておき、木構造辞書を作成する際に読み込んだ語数から動的（ダイナミック）にデータ型を決定する処理を追加的に導入する。
【００３５】
図６は、本実施形態におけるデータベース作成処理の変形例を示すフローチャートである。このフローチャートは、基本的には図２のフローチャートと同様のものであるが、ステップＳ２０１の前処理としてステップＳ６０１およびＳ６０２が追加されている。
【００３６】
まずステップＳ６０１において、木構造辞書１０５に登録する、音素列の異なる語数（リーフ数）を調べる。次に、ステップＳ６０２において、データサイズの異なる複数のデータ型から、ステップＳ６０１で調べた音素列の異なる語数の値を格納できる最小データサイズのデータ型を選択する。
【００３７】
その後、前述のようなステップＳ２０１以降の処理を行うのであるが、ノード情報における子ノード相対番号は、ステップＳ６０２で選択されたデータ型の変数で定義される。このように、登録する単語数に応じて、子ノード相対番号を表す最適なデータ型が設定される。
【００３８】
図７は、ノード情報として用意された複数の構造体の例で、Ｃ言語で記述されたものである。図示のように、ノード情報に係る構造体は、子ノード数と開始子ノード相対番号（図５を参照）をメンバーに含み、３種類の構造体で相異なるデータ型が宣言されている。具体的には、NodeInfo1構造体では、子ノード数を表す変数childNumおよび開始子ノード相対番号を表す変数childStartのデータ型としてそれぞれ、unsigned char（すなわち、１byte）が宣言されている。また、NodeInfo2構造体では、子ノード数を表す変数childNumおよび開始子ノード相対番号を表す変数childStartのデータ型としてそれぞれ、unsigned short（すなわち、２byte）が宣言されている。そして、NodeInfo3構造体では、子ノード数を表す変数childNumおよび開始子ノード相対番号を表す変数childStartのデータ型としてそれぞれ、unsigned int（実行されるコンピュータに依存するが、ここでは４byteとする。）が宣言されている。
【００３９】
以上のようなtypedef宣言がされている場合、ステップＳ６０２では、ステップＳ６０１で調べた音素列の異なる語数が１byteに収まる数であったときはNodeInfo1構造体が選択され、１Byteには収まらないが２byteに収まる数であったときはNodeInfo2構造体が選択され、２byteでも収まらず４byte必要なときにはNodeInfo3構造体が選択される。
【００４０】
以上のような処理によれば、木構造辞書を用いるアプリケーションによって、「子ノード相対番号」あるいは「開始子ノード相対番号」のデータ型がダイナミックに決定され、その結果、ノード情報のデータ量の最適化が図られる。
【００４１】
以上、本発明の実施形態を説明したが、木構造は上述の実施形態に限定されるものではない。例えば、先頭音素ごとに木構造を別々に保持しても良い。また、音声認識で広く用いられる３つ組音素であるトライフォンの列によって木構造を構成しても良い。
【００４２】
図８は、図３と同じデータをトライフォンを用いて木構造辞書にした例を示している。トライフォンを用いた場合と音素を用いた場合では、共通化できる箇所が異なるために木構造の形も変わる。特に、ルートから繋がる第一階層のノードは、前から接続し得る単語の語尾の音素数分、展開する必要がある。同様に、リーフノードは、後ろに接続し得る単語の語頭の音素数分、展開する必要がある。同図において、これらは“＊”で表されている。このため、ここでは１トライフォンでノードを作る。
【００４３】
また、上述の実施形態は、木構造辞書を単語リストなどのデータ１０１から木構造生成部１０２によって木構造を生成し、その際にノード番号付与部１０３がノード番号を、子ノード相対番号付与部１０４がノード情報内の子ノード相対番号を付与するものであった。しかし、本発明はこれに限るものではなく、既に木構造ができている木構造辞書を入力としても適用できる。従来の木構造辞書を入力し、ノード番号付与部１０３が階層ごとに、親ノードの番号順にノード番号を付与し、子ノード相対番号付与部１０４が子ノード相対番号をノード情報に付与することで、データベースの音素の異なる語数を把握してデータ型を決定することによって木構造辞書のデータサイズを削減することができる。なお、この場合は、データ１０１、木構造生成部１０２は必要ない。
【００４４】
上述の実施形態におけるデータベース作成装置によって作成された木構造辞書を用いて、データ検索処理が実現されることは明らかであろう。このデータ検索処理においては、木構造辞書の、音素列の異なる語数から子ノード相対番号が格納されているデータ型を判別し、子ノード相対番号から子ノードの番号を復元して子ノードに遷移し、探索を行う。
【００４５】
また、音声処理に係わる当業者であれば理解するであろうが、以上説明したような共通音素列をノードとする木構造辞書を認識辞書として用いて音声認識処理を実現することが可能であることも明らかである。
【００４６】
さらに本発明は、共通音素列をノードとする木構造辞書に限定されるものではなく、木構造を持つ全てのデータベースに対して適用可能であることはいうまでもない。
【００４７】
以上説明した本発明の実施形態によれば、各ノードから遷移する子ノードを相対番号で管理する。この相対番号は木構造辞書のリーフの数に制限されることが保証されているため、リーフ数から相対番号に必要なデータ型を判定できる。これにより、リーフ数に応じてスケーラブルにデータ型を変更して小型化できる。
【００４８】
（他の実施形態）
以上、本発明の実施形態を詳述したが、本発明は、複数の機器から構成されるシステムに適用してもよいし、また、一つの機器からなる装置に適用してもよい。
【００４９】
なお、本発明は、前述した実施形態の機能を実現するソフトウェアのプログラムを、システムあるいは装置に直接あるいは遠隔から供給し、そのシステムあるいは装置のコンピュータがその供給されたプログラムコードを読み出して実行することによっても達成される。その場合、プログラムの機能を有していれば、その形態はプログラムである必要はない。
【００５０】
従って、本発明の機能処理をコンピュータで実現するために、そのコンピュータにインストールされるプログラムコード自体およびそのプログラムを格納した記憶媒体も本発明を構成することになる。つまり、本発明の特許請求の範囲には、本発明の機能処理を実現するためのコンピュータプログラム自体、およびそのプログラムを格納した記憶媒体も含まれる。
【００５１】
その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータ等、プログラムの形態を問わない。
【００５２】
プログラムを供給するための記憶媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＤＶＤ（ＤＶＤ−ＲＯＭ、ＤＶＤ−Ｒ）などがある。
【００５３】
その他、プログラムの供給方法としては、クライアントコンピュータのブラウザを用いてインターネットのホームページに接続し、そのホームページから本発明のコンピュータプログラムそのもの、もしくは圧縮され自動インストール機能を含むファイルをハードディスク等の記憶媒体にダウンロードすることによっても供給できる。また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるホームページからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバも、本発明のクレームに含まれるものである。
【００５４】
また、本発明のプログラムを暗号化してＣＤ−ＲＯＭ等の記憶媒体に格納してユーザに配布し、所定の条件をクリアしたユーザに対し、インターネットを介してホームページから暗号化を解く鍵情報をダウンロードさせ、その鍵情報を使用することにより暗号化されたプログラムを実行してコンピュータにインストールさせて実現することも可能である。
【００５５】
また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現される他、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどが、実際の処理の一部または全部を行い、その処理によっても前述した実施形態の機能が実現され得る。
【００５６】
さらに、記憶媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によっても前述した実施形態の機能が実現される。
【図面の簡単な説明】
【００５７】
【図１Ａ】図１Ａは、本発明のデータベース作成装置を実現するコンピュータシステムの構成例を示すブロック図である。
【図１Ｂ】図１Ｂは、本発明の実施形態におけるデータベース作成装置の機能構成を示すブロック図である。
【図２】図２は、本発明の実施形態におけるデータベース作成処理を示すフローチャートである。
【図３】図３は、本発明によってノード番号が付与されて作成される木構造辞書の一例を示す図である。
【図４】図４は、本発明の実施形態におけるノード情報の例を示す図である。
【図５】図５は、本発明の別の実施形態におけるノード情報を示す図である。
【図６】図６は、本発明の別の実施形態におけるデータベース作成処理を示すフローチャートである。
【図７】図７は、本発明の別の実施形態におけるノード情報を格納するための構造体の記述例を示す図である。
【図８】図８は、本発明の別の実施形態における木構造辞書の一例を示す図である。
【図９】図９は、従来の木構造データベースの一例を示す図である。
【図１０】図１０は、従来のノード情報の例を表す図である。
【図１Ａ】
2006178013.tif 000003
【図１Ｂ】
2006178013.tif 000004
【図２】
2006178013.tif 000005
【図３】
2006178013.tif 000006
【図４】
2006178013.tif 000007
【図５】
2006178013.tif 000008
【図６】
2006178013.tif 000009
【図７】
2006178013.tif 000010
【図８】
2006178013.tif 000011
【図９】
2006178013.tif 000012
【図１０】
2006178013.tif 000013