言語モデル圧縮装置、言語モデルのアクセス装置、言語モデル圧縮方法、言語モデルのアクセス方法、言語モデル圧縮プログラム、言語モデルのアクセスプログラム
【課題】学習結果としてのｎ−ｇｒａｍ言語モデルのデータ量を抑制し、効率的にアクセス可能な技術を提供する。
【解決手段】言語モデルの圧縮装置１は、言語モデル記憶部５にｎ−ｇｒａｍ言語モデルを記憶する。データ構造変換部３は、言語モデル記憶部５に記憶されたｎ−ｇｒａｍ言語モデルのデータ配列中、（ｎ＋１）−ｇｒａｍの最初の位置を示すポインタを固定バイト表現に変換し、変換データ記憶部６に記憶させる。ポインタ表現の圧縮部４は、変換データ記憶部６に記憶されたｎ−ｇｒａｍ言語モデルの木構造に仮想的なルートノードを設けることでトライ（ｔｒｉｅ）と擬制し、前記ポインタをＬＯＵＤＳ表現に圧縮変換する。ここで圧縮変換されたデータを圧縮データ記憶部７に記憶させる。この記憶部７は、主に計算機の記憶装置（ＲＡＭ）を用いる。
【解決手段】言語モデルの圧縮装置１は、言語モデル記憶部５にｎ−ｇｒａｍ言語モデルを記憶する。データ構造変換部３は、言語モデル記憶部５に記憶されたｎ−ｇｒａｍ言語モデルのデータ配列中、（ｎ＋１）−ｇｒａｍの最初の位置を示すポインタを固定バイト表現に変換し、変換データ記憶部６に記憶させる。ポインタ表現の圧縮部４は、変換データ記憶部６に記憶されたｎ−ｇｒａｍ言語モデルの木構造に仮想的なルートノードを設けることでトライ（ｔｒｉｅ）と擬制し、前記ポインタをＬＯＵＤＳ表現に圧縮変換する。ここで圧縮変換されたデータを圧縮データ記憶部７に記憶させる。この記憶部７は、主に計算機の記憶装置（ＲＡＭ）を用いる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、単語をｎ文字単位で分割し、それぞれの単語列とその出現頻度（確率）を求めたｎ−ｇｒａｍ言語モデルを圧縮するための技術、および効率的にｎ−ｇｒａｍ言語モデルにアクセスするための技術に関する。
【背景技術】
【０００２】
周知のように、音声認識や統計的機械翻訳などの分野では、非特許文献１に示すように、出力される言語(単語列)の尤もらしさをモデル化するために、単語ｎ個からなる単語列(ｎ−ｇｒａｍと呼ぶ)に対する条件付確率（式１）が広く用いられている。
【０００３】
【数１】
【０００４】
単語列（式２）の尤もらしさ（式３）は、式１の条件付確率を用いて、式４のように近似的に求めることができる。
【０００５】
【数２】
【０００６】
【数３】
【０００７】
【数４】
【０００８】
このような式１の条件付確率を与えるモデルは、ｎ−ｇｒａｍ言語モデルと呼ばれている。「ｎ」の大きさとしては、音声認識では「３〜４」の値を、統計的機械翻訳では「４〜５」の値を用いることが多い。式１の条件付確率は、式５のように、再帰的に計算される。また、式２は、単語ｗ1，ｗ2，・・・，ｗnを省略標記したものである。
【０００９】
【数５】
【００１０】
このような統計モデルを計算機（コンピュータ）で利用するためには、まず、学習データに現れる単語列（式２）に応じて、式６の平滑された確率、式７のバックオフ係数などの情報を格納すること、さらに単語列（式２）を入力として、前記各情報に効率的にアクセスできることが必要となる。
【００１１】
【数６】
【００１２】
【数７】
【００１３】
そして、音声認識や統計的機械翻訳などｎ−ｇｒａｍのアプリケーションの性能を高めるためには、非特許文献２に示すように、大量の学習データを用いてこれらのパラメータを学習することはもとより、学習データを増やすことで、そこに現れる正しい単語列（式２）のバリエーション(ｎ−ｇｒａｍのバリエーション)を多数保持することが有効と知られている。
【００１４】
また、ｎ−ｇｒａｍ言語モデルは、非特許文献３に示すように、木構造（データ構造）で表現できることが知られている。さらに木構造の一種であるトライ（ｔｒｉｅ）をコンパクトに表現する手法として、非特許文献４．５に示すように、ＬＯＵＤＳ（Ｌｅｖｅｌ−Ｏｒｄｅｒ Ｕｎａｒｙ Ｄｅｇｒｅｅ Ｓｅｑｕｅｎｃｅ）が知られている。ここでトライとは、１つのルートノードを持つ順序付き木構造の一種であり、プレフィックス木（Ｐｒｅｆｉｘ Ｔｒｅｅ）とも呼ばれている。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】Ｓ． Ｍ． Ｋａｔｚ， “Ｅｓｔｉｍａｔｉｏｎ ｏｆ Ｐｒｏｂａｂｉｌｉｔｉｅｓ ｆｒｏｍ Ｓｐａｒｓｅ Ｄａｔａ ｆｏｒ ｔｈｅ Ｌａｎｇｕａｇｅ Ｍｏｄｅｌ Ｃｏｍｐｏｎｅｎｔ ｏｆ ａ Ｓｐｅｅｃｈ Ｒｅｃｏｇｎｉｚｅｒ，” ＩＥＥＥ ＴＲＡＮＳＡＣＴＩＯＮＳ ＯＮ ＡＣＯＵＳＴＩＣ， ＳＰＥＥＣＨ， ＡＮＤ ＳＩＧＮＡＬ ＰＲＯＣＥＳＳＩＮＧ， ＶＯＬ．ＡＳＳＰ−３５，ＮＯ．３，ＭＡＲＣＨ １９８７，ｐｐ． ４００−４０１
【非特許文献２】Ｔ． Ｂｒａｎｔｓ， Ａ． Ｃ． Ｐｏｐａｔ， Ｐ． Ｘｕ， Ｆ． Ｊ． Ｏｃｈ， ａｎｄ Ｊ． Ｄｅａｎ， Ｌａｒｇｅ Ｌａｎｇｕａｇｅ Ｍｏｄｅｌｓ ｉｎ Ｍａｃｈｉｎｅ Ｔｒａｎｓｌａｔｉｏｎ， Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００７ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｍｐｉｒｉｃａｌ Ｍｅｔｈｏｄｓ ｉｎ Ｎａｔｕｒａｌ Ｌａｎｇｕａｇｅ Ｐｒｏｃｅｓｓｉｎｇ ａｎｄ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｌａｎｇｕａｇｅ Ｌｅａｒｎｉｎｇ （ＥＭＮＬＰ−ＣｏＮＬＬ）， ｐｐ． ８５８−−８６７， ２００７．
【非特許文献３】Ｂ． Ｒａｊ ａｎｄ Ｅ．Ｗ．Ｄ． Ｗｈｉｔｔａｋｅｒ． ”ＬＯＳＳＬＥＳＳ ＣＯＭＰＲＥＳＳＩＯＮ ＯＦ ＬＡＮＧＵＡＧＥ ＭＯＤＥＬ ＳＴＲＵＣＴＵＲＥ ＡＮＤ ＷＯＲＤ ＩＤＥＮＴＩＦＩＥＲＳ” Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＣＡＳＳＰ， ｖｏｌｕｍｅ １， ｐａｇｅｓ Ｉ≡３８８≡Ｉ≡３９１ ｖｏｌ．１， Ａｐｒｉｌ ２００３．
【非特許文献４】Ｏ’Ｎｅｉｌ Ｄｅｌｐｒａｔｔ， Ｎａｉｌａ Ｒａｈｍａｎ， ａｎｄ Ｒａｊｅｅｖ Ｒａｍａｎ． ”Ｅｎｇｉｎｅｅｒｉｎｇ ｔｈｅ ＬＯＵＤＳ Ｓｕｃｃｉｎｃｔ Ｔｒｅｅ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ” Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｅｘｐｅｒｉｍｅｎｔａｌ Ａｌｇｏｒｉｔｈｍｓ， ｐａｇｅｓ １３４≡１４５， ２００６．
【非特許文献５】Ｇｕｙ Ｊａｃｏｂｓｏｎ． ”Ｓｐａｃｅ−ｅｆｆｉｃｉｅｎｔ Ｓｔａｔｉｃ Ｔｒｅｅｓ ａｎｄ Ｇｒａｐｈｓ” Ｉｎ ３０ｔｈ Ａｎｎｕａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｆｏｕｎｄａｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ｐａｇｅｓ ５４９≡５５４， Ｎｏｖ １９８９．
【非特許文献６】Ｄｏｎｇ Ｋｙｕｅ Ｋｉｍ， Ｊｏｏｎｇ Ｃｈａｅ Ｎａ， Ｊｉ Ｅｕｎ Ｋｉｍ， ａｎｄ Ｋｕｎｓｏｏ Ｐａｒｋ． ”Ｅｆｆｉｃｉｅｎｔ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｒａｎｋ ａｎｄ ｓｅｌｅｃｔ ｆｕｎｃｔｉｏｎｓ ｆｏｒ ｓｕｃｃｉｎｃｔ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ” Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｅｘｐｅｒｉｍｅｎｔａｌ Ａｌｇｏｒｉｔｈｍｓ， ｐａｇｅｓ ３１５≡３２７， ２００５．
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかしながら、大量のデータで学習したｎ−ｇｒａｍ言語モデルは、非常に多種多様なｎ−ｇｒａｍを格納するため、モデル表現が巨大になってしまう。特に、ｎ−ｇｒａｍ言語モデルを使う際には効率的なアクセスが要求されるため、それを考慮したデータ構造は大きなものとなり易い。
【００１７】
その一方で効率的なアクセスを実現するためには、ｎ−ｇｒａｍ言語モデルを主記憶装置（ＲＡＭ）に格納することが好ましいが、現代の計算機（コンピュータ）をもってしても主記憶装置の記憶容量には限界がある。例えば、全Ｗｅｂデータで学習した巨大なｎ−ｇｒａｍを、従来法で表現すると４０ＧＢ以上の容量が必要となるため、一部の非常に高価な計算機を除いて主記憶装置に保持することは困難である。
【００１８】
また、ｎ−ｇｒａｍ言語モデルの木構造の表現は、ルートノードが存在しない（あるいは１つではない）。トライ構造をコンパクトに表現する方法は知られているが、ｎ−ｇｒａｍ言語モデルのデータ構造はトライではないため、トライ構造をコンパクトに表現する方法をｎ−ｇｒａｍ言語モデルの表現に応用するには、さらなる工夫が必要である。
【００１９】
本発明は、上述のような従来技術の問題点を解決するためになされたものであり、ｎ−ｇｒａｍ言語モデルのデータ量を抑制し、効率的にアクセス可能な技術を提供することを解決課題とする。
【課題を解決するための手段】
【００２０】
そこで、本発明は、自然言語処理システムなどで用いられるｎ−ｇｒａｍ言語モデルのデータ構造をトライ（木構造）に変換し、トライをコンパクトに表現するＬＯＵＤＳという手法によって、より少ないビット列で表現する。さらに、ｎ−ｇｒａｍの特性を考慮して、この手法を改良する。
【００２１】
本発明に係る言語モデル圧縮装置の一態様は、仮想的なルートノードを設けて、ｎ−ｇｒａｍ言語モデルの構造をトライ構造に変換するデータ構造変換手段と、前記データ構造変換手段にて変換されたトライ構造をＬＯＵＤＳ（Ｌｅｖｅｌ−Ｏｒｄｅｒ Ｕｎａｒｙ Ｄｅｇｒｅｅ Ｓｅｑｕｅｎｃｅ）表現に圧縮変換する圧縮手段と、を備える。
【００２２】
本発明に係る言語モデルの他の態様は、ｎ−ｇｒａｍ言語モデルの最高次数の最初のノードの位置（ノードＩＤ）を記憶装置に記憶し、ｎ−ｇｒａｍ言語モデルの構造を表すポインタ表現を、最高次数のｎ−ｇｒａｍを削除した表現に変換するデータ構造変換手段を、備える。ここでは１−ｇｒａｍの個数Ｎ1を記憶装置に記憶し、前記データ構造変換手段にて変換したｎ−ｇｒａｍ言語モデルの構造を、スーパーノード（トライ構造のルートノードを指す仮想的なルートノード）および最高次数のｎ−ｇｒａｍに対応したビットをもたないように拡張したＬＯＵＤＳ表現に圧縮変換する圧縮手段を、さらに備えてもよい。
【００２３】
本発明に係る言語モデルのアクセス装置の一態様は、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式８により算出して出力する第１のアクセス手段と、
入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式９により算出して出力する第２のアクセス手段と、を備える。
【００２４】
【数８】
【００２５】
【数９】
【００２６】
本発明に係る言語モデルのアクセス装置の他の態様は、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式１０により算出して出力する第１のアクセス手段と、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式１１により算出して出力する第２のアクセス手段と、を備える。
【００２７】
【数１０】
【００２８】
【数１１】
【００２９】
本発明に係る言語モデル圧縮方法の一態様は、データ構造変換手段が、仮想的なルートノードを設けて、ｎ−ｇｒａｍ言語モデルの構造をトライ構造に変換するデータ構造変換ステップと、圧縮手段が、前記データ構造変換ステップにて変換されたトライ構造をＬＯＵＤＳ（Ｌｅｖｅｌ−Ｏｒｄｅｒ Ｕｎａｒｙ Ｄｅｇｒｅｅ Ｓｅｑｕｅｎｃｅ）表現に圧縮変換する圧縮ステップと、を有する。
【００３０】
本発明に係る言語モデル圧縮方法の他の態様は、データ構造変換手段が、前記ｎ−ｇｒａｍ言語モデルの最高次数の最初のノードの位置（ノードＩＤ）を記憶装置に記憶し、ｎ−ｇｒａｍ言語モデルの構造を表すポインタ表現を、最高次数のｎ−ｇｒａｍを削除した表現に変換するデータ構造変換ステップを、有する。ここでは圧縮手段が、１−ｇｒａｍの個数Ｎ1を記憶装置に記憶させ、前記データ構造変換手段にて変換したｎ−ｇｒａｍ言語モデルの構造を、スーパーノード（トライ構造のルートノードを指す仮想的なルートノード）および最高次数のｎ−ｇｒａｍに対応したビットをもたないように拡張したＬＯＵＤＳ表現に圧縮変換する圧縮ステップを、さらに有してもよい。
【００３１】
本発明に係る言語モデルのアクセス方法の一態様は、第１のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式８により算出して出力するステップと、第２のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式９により算出して出力するステップと、を有する。
【００３２】
【数８】
【００３３】
【数９】
【００３４】
本発明に係る言語モデルのアクセス方法の他の態様は、第１のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式１０により算出して出力するステップと、第２のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式１１により算出して出力するステップと、を有する。
【００３５】
【数１０】
【００３６】
【数１１】
【００３７】
なお、本発明は、前記各装置としてコンピュータを機能させるためのプログラムの態様としてもよい。このプログラムは記録媒体に記録した態様で配布・提供することができる。
【発明の効果】
【００３８】
本発明によれば、ｎ−ｇｒａｍ言語モデルの構造を規定するポインタ表現のデータ量が抑制される。このことにより巨大なｎ−ｇｒａｍ言語モデルであっても、ポインタ表現のすべてもしくは大部分を、アクセスの遅いハードディスクドライブ装置に代わって，アクセスの高速なメモリ（ＲＡＭ）上に保持することが可能となる。本発明により巨大なｎ−ｇｒａｍ言語モデルを用いた機械翻訳や音声認識などにあたって、効率的にｎ−ｇｒａｍ言語モデルにアクセスすることが可能となり、処理の高速化に貢献する。
【図面の簡単な説明】
【００３９】
【図１】本発明の実施形態に係る言語モデル圧縮装置および言語モデルのアクセス装置の構成図。
【図２】同 言語モデル記憶部に記憶されたｎ−ｇｒａｍ言語モデルのデータ構造図。
【図３】同 データ構造変換部の変換後におけるｎ−ｇｒａｍ言語モデルのデータ構造図。
【図４】トライ構造に基づくポインタ表現を示す図。
【図５】ｎ−ｇｒａｍ構造に基づくポインタ表現を示す図。
【図６】トライ構造の構造図。
【図７】ｎ−ｇｒａｍの構造図。
【発明を実施するための形態】
【００４０】
以下、本発明の実施形態に係る言語モデル圧縮装置および言語モデルのアクセス装置を説明する。この両装置は、音声認識装置や機械翻訳機などの自然言語処理システムにおいてコンビネーションとして利用される。ここでは前記圧縮装置は、ｎ−ｇｒａｍの学習装置により生成されたｎ−ｇｒａｍ言語モデルのデータ量を抑制する一方、前記アクセス装置は音声認識や統計的機械翻訳にあたって前記圧縮装置でデータ容量を抑制されたｎ−ｇｒａｍ言語モデルにアクセスする。
【００４１】
具体的には前記各装置は、コンピュータにより構成され、通常のコンピュータのハードウェアリソース、例えばＣＰＵ，メモリ（ＲＡＭ）などの主記憶装置，ハードディスクドライブ装置などを備えている。
【００４２】
このハードウェアリソースとソフトウェアリソース（ＯＳ，アプリケーションなど）との協働の結果、図１に示すように、前記圧縮装置１は、データ構造変換部３，ポインタ表現の圧縮部４，言語モデル記憶部５，変換データ記憶部６，圧縮データ記憶部７を実装する一方、前記アクセス装置２は、ｎ−ｇｒａｍアクセス部（ｆｉｒｓｔ＿ｃｈｉｌｄ）８，ｎ−ｇｒａｍアクセス部（ｐａｒｅｎｔ）９を実装する。なお、前記両装置１．２は、必ずしも複数のコンピュータで構成する必要はなく、単一のコンピュータで構成してもよい。
【００４３】
概略を説明すれば、前記各記憶部５〜７は、前記ハードディスクドライブ装置あるいは前記主記憶装置に構築されている。このうち前記言語モデル記憶部５は、大量の学習用データ（例えばＷｅｂデータなど）に基づく学習結果として生成された言語モデルを格納する。ここで格納される言語モデルは、通常の「ｎ−ｇｒａｍ言語モデルのデータ構造」形式で表現されているものとする。
【００４４】
前記データ構造変換部３は、矢印Ａに示すように、前記言語モデル記憶部５の言語モデルを入力とし、ポインタの固定バイト表現されたｎ−ｇｒａｍ言語モデルのデータ構造に変換する（データ変換ステップ）。この変換後のデータは、矢印Ｂに示すように、前記変換データ記憶部６に蓄積される。
【００４５】
前記ポインタ表現の圧縮部４は、矢印Ｃに示すように、前記変換データ記憶部６の蓄積データを入力とし、該蓄積データにポインタ配列をコンパクトに表現する処理を加え、データ量を圧縮する（ポインタ表現の圧縮ステップ）。すなわち、ポインタのＬＯＵＤＳ表現されたｎ−ｇｒａｍ言語モデルのデータ構造に圧縮変換し、矢印Ｄに示すように、前記圧縮データ記憶部７に記憶させる。
【００４６】
前記アクセス装置２は、図示省略の入力手段を通じて与えられた単語列（ｎ−ｇｒａｍ）を入力とし、矢印Ｅ．Ｆに示すように、前記圧縮データ記憶部７の記憶データ、即ち圧縮表現されたｎ−ｇｒａｍ言語モデルのポインタにアクセスする（アクセスステップ）。具体的には、前記アクセス部８は、矢印Ｇに示すように、ｎ−ｇｒａｍ（単語列）の位置を入力とし、前記圧縮データ記憶部７を参照して、矢印Ｈに示すように、（ｎ＋１）−ｇｒａｍの位置を出力する。一方、前記アクセス部９は、矢印Ｉに示すように、ｎ−ｇｒａｍ（単語列）の位置を入力とし、前記圧縮データ記憶部７を参照して、矢印Ｊに示すように、（ｎ−１）−ｇｒａｍの位置を出力する。以下、前記両装置１．２の各機能ブロック３〜９の詳細を説明する。
【００４７】
≪言語モデル圧縮装置１≫
（１）データ構造変換部３
まず、前記言語モデル記憶部５の格納データ、即ちｎ−ｇｒａｍのデータ構造を説明する。このｎ−ｇｒａｍは、図２のデータ構造で表現され（非特許文献２参照）、「１−ｇｒａｍ， ２−ｇｒａｍ， ３−ｇｒａｍ， …」は、それぞれ前記言語モデル記憶部５の別テーブルで表現される。
【００４８】
このｎ−ｇｒａｍのテーブルの各列は、単語ｗnの単語ＩＤ（ｗｏｒｄ ｉｄ）、式６の平滑化された確率値（ｐｒｏｂａｂｉｌｉｔｙ）、式７のバックオフ係数（ｂａｃｋ−ｏｆｆ）、（Ｘ＋１）−ｇｒａｍの最初の位置を示すポインタ（ｐｏｉｎｔｅｒ）を有している（Ｘは１≦Ｘ≦ｎの整数）。各テーブルは、このような四つ組の配列として表現される。ポインタとしては、この配列のインデックスを用いることができる。例えば４バイト整数によってポインタを実現できる。
【００４９】
ここでＸ−ｇｒａｍ（Ｘは１≦Ｘ≦ｎの整数）のポインタの指す先の連続した領域には、式１２の履歴を共有する（Ｘ＋１）−ｇｒａｍが、ｗx+1の単語ＩＤ順にソートされて格納される。
【００５０】
【数１２】
【００５１】
この領域の終わりの境界は、Ｘ−ｇｒａｍの次のエントリのポインタが指す先で規定される。あるＸ−ｇｒａｍを探すには、それを構成する単語毎にバイナリ探索が実施されるため、合計Ｘ回のバイナリ探索が行われる。単語ＩＤを１−ｇｒａｍテーブルの各行の位置で定義することで、図２に示すように、１−ｇｒａｍの単語ＩＤの列は省略することができる。
【００５２】
前記データ構造変換部３は、前記言語モデル記憶部５に格納されている図２のデータ構造を変換し、図３に示すように、単語ＩＤ、平滑化された確率値、バックオフ係数、ポインタの各々を別々の配列で表し、前記変換データ記憶部６に格納する。ここでは１−ｇｒａｍの後ろに２−ｇｒａｍの情報を、２−ｇｒａｍの後に３−ｇｒａｍの情報を連結し、該連結処理を順次に実施する。なお、オーダの境界(２−ｇｒａｍ，３−ｇｒａｍ，…の開始位置)を、別途主記憶装置に記憶し、各オーダの情報にアクセスできるようにする。
【００５３】
ポインタ配列としては、図４のトライ（ｔｒｉｅ）構造に基づく表現（第１形態）と、図５のｎ−ｇｒａｍ構造に基づく表現（第２形態）のいずれかを使用する。なお、図４．５は、それぞれ図６．７の木構造に対応したポインタ構造を表す。配列の要素となるポインタは、固定バイト（例えば４バイト）整数で表現されているものとする。
【００５４】
なお、第２形態においては、ｎ−ｇｒａｍ言語モデルの最高次数の最初のエントリの位置を記憶しておき、第1形態のポインタ配列ではそれ以降に格納されていた最高次数のｎ−ｇｒａｍのポインタを第２形態では格納しないものとする。ただし、最高次数ｎ−ｇｒａｍの情報を格納しないのは、ポインタ配列だけであり、その他の単語ＩＤ（ｗｏｒｄ ｉｄ）、平滑化された式６の確率値（ｐｒｏｂａｂｉｌｉｔｙ）、式７のバックオフ係数（ｂａｃｋ−ｏｆｆ）については、最高次数ｎ−ｇｒａｍの情報も格納する。
【００５５】
（２）ポインタ表現の圧縮部４
前記圧縮部４は、前記変換データ記憶部６を参照して、前記データ構造変換部３で変換した各配列のうち、ポインタを示す配列をコンパクトに表現して、前記変換データ記憶部６に格納する。以下、各形態の具体的内容を説明する。
【００５６】
＜第１形態＞
まず、前記圧縮部４における第１形態について説明する。トライ（ｔｒｉｅ）とは、木構造の一種であり、１つルートノードを持つ木構造で表される。図２に示したｎ−ｇｒａｍのデータ構造は、ルートノードが１つではないためトライではないが、ここでは仮想的なルートノードを設けることにより、ｎ−ｇｒａｍのデータ構造をトライに擬制して、コンパクトなトライ表現法であるＬＯＵＤＳ（非特許文献４．５参照）を応用し、ポインタ配列を圧縮する。
【００５７】
詳細を説明すれば、ＬＯＵＤＳによる表現では、ルートノードから始まり、「１−ｇｒａｍ，２−ｇｒａｍ，…」の階層順で左から右、即ち幅優先の順序で、ノードにノードＩＤが割り当てられる。ここではｄ個（ｄ≧０）の子供（子ノード）を有するノード（親ノード）は、「１d０」のビット列で表現される（「１d」は、「１」がｄ個ならんでいるビット列を表している。）。仮想的なルートノードを指すさらなる仮想的なノードとしてスーパールートノードを設ける。スーパールートノードの子供はルートノード一つであるから、スーパールートノードは「１０」で表される。
【００５８】
図６はトライ構造の一例を示している。このトライ構造例のＬＯＵＤＳビット列によるポインタ表現を表１に示す。
【００５９】
【表１】
【００６０】
前記トライ構造例によれば、ルートノード「０」は、４つの子供を持つことから、４つの「１」と終わりを表す１つの「０」とで表されている。ここでＭ個のノードを有するトライは、（Ｍ＋１）個の「０」と，Ｍ個の「１」とで表されるため、合計２Ｍ＋１ビットで表現される．
Ｘ−ｇｒａｍの個数をＮxと表し、式１３を用いれば、ｎ−ｇｒａｍ言語モデルでは式１４が成立する。したがって、ｎ−ｇｒａｍ言語モデルは、式１５のビット数でポインタが表現される。ここで圧縮表現されたポインタが前記圧縮データ記憶部７に記憶される。
【００６１】
【数１３】
【００６２】
【数１４】
【００６３】
【数１５】
【００６４】
以上のように圧縮表現されたｎ−ｇｒａｍ言語モデルにアクセスするためには、ＬＯＵＤＳビット列上に、ビット列中のｉ番目の「１」の位置を返す「ｓｅｌｅｃｔ1（ｉ）」という操作を定義する。ここでビットの位置は、表１に示すように、「０」から始まっているものとする。同様にビット列中のｉ番目の「０」の位置を返す操作として「ｓｅｌｅｃｔ0（ｉ）」を定義できる。
【００６５】
「ｓｅｌｅｃｔb（ｉ）（ｂ＝０ ｏｒ １）」は、非特許文献６などの手法を用いて、効率的に実現することができる。この操作を用いることで、ノードｘ（ノードＩＤ＝「ｘ」のノード）に対して親ノードＩＤを返す関数「ｐａｒｅｎｔ（ｘ）」や、ノードｘに対して最初の子供のＩＤを返す関数「ｆｉｒｓｔ＿ｃｈｉｌｄ（ｘ）」が式８．式９で実現される。
【００６６】
【数８】
【００６７】
【数９】
【００６８】
例えば、ノード９の親ノードは、「ｐａｒｅｎｔ（９）＝ｓｅｌｅｃｔ（９＋１）−９−１＝１２−９−１＝２」から、ノード２と求められる。また、ノード９の最初の子ノードは、「ｆｉｒｓｔ＿ｃｈｉｌｄ（９）＝ｓｅｌｅｃｔ0（９＋１）−９＝２３−９＝１４」となり，ノード１４であると求まる。
【００６９】
ただし、「ｆｉｒｓｔ＿ｃｈｉｌｄ（ｘ）」が、０以上のノードＩＤを返すからといってノードｘが、子ノードを有することが保証されるとは限らない。ノードｘが子ノードを有する必要十分条件は、「ｆｉｒｓｔ＿ｃｈｉｌｄ（ｘ）≠ｆｉｒｓｔ＿ｃｈｉｌｄ（ｘ＋１）」である。またノードｘに係る子ノードのＩＤの範囲は、［ｆｉｒｓｔ＿ｃｈｉｌｄ（ｘ），ｆｉｒｓｔ＿ｃｈｉｌｄ（ｘ＋１））で求まる。前記ｎ−ｇｒａｍアクセス装置２では、以上の関数を利用してｎ−ｇｒａｍ言語モデルへのアクセスを行う。
【００７０】
＜第２形態＞
つぎに前記圧縮部４における第２形態を説明する。ここでは第１形態で用いたＬＯＵＤＳを、ｎ−ｇｒａｍの特性を利用して、さらにコンパクトに表現できるように拡張処理されている。
【００７１】
すなわち、図２および図３に示すように、ｎ−ｇｒａｍの場合はルートノードに格納する情報は存在しない。したがって、ルートノードを削除し、仮想的なスーパールートノードが直接１−ｇｒａｍの各ノードを指すようにする。ここではノードＩＤは、１−ｇｒａｍの最初のノードが「０」となるように番号付けるものとする。これで旧ルートノードの２ビットが削減される。
【００７２】
また、ｎ−ｇｒａｍの場合、１〜ｎまでの階層をもつ構造をしており、最下層にある最高次数ｎのノードは子ノードを有していない。ここでＸ−ｇｒａｍのノードの個数をＮxとすると、ｎ−ｇｒａｍの最高次数のノード数はＮnであり、Ｎn個の「０」が冗長である。そこで、最高次数の最初のノードＩＤを前記主記憶装置に記憶しておき、ｎ−ｇｒａｍ言語モデルにアクセスする際には該ノードＩＤ以外は子ノードを有しないと判定することとする。これにより、Ｎn個の「０」、即ちＮnビットを消去することができる。
【００７３】
さらに、スーパールートノードは、式１６で表されるが、１−ｇｒａｍの個数Ｎ1を記憶しておくことで、これは取り去ることができる。このように前記各ノードが存在しないものとして木構造を生成し、ビットを割り当てる。これでＮ1＋１ビットが削減できる。これにより、第２形態における圧縮表現されたポインタは、スーパーノードに対応したビットと最高次数のｎ−ｇｒａｍに対応したビットをもたない表現（拡張したＬＯＵＤＳ表現）となる。この圧縮変換されたポインタを、前記圧縮データ記憶部７に記憶する。
【００７４】
【数１６】
【００７５】
第２形態において圧縮表現されたｎ−ｇｒａｍ言語モデルにアクセスするためには、第１形態の式８．式９を、式１０．式１１に書き換える。
【００７６】
【数１０】
【００７７】
【数１１】
【００７８】
ただし、最高次数の最初のノードＩＤをＹとすると、「ｘ≧Ｙ」のときは、「ｓｅｌｅｃｔ1（ｘ）＝ｓｅｌｅｃｔ1（Ｙ−１）、ｓｅｌｅｃｔ0（ｘ）＝ｓｅｌｅｃｔ0（Ｙ−１）＋ｘ−Ｙ＋１」とする。
【００７９】
図７に、トライ構造を刈り込みｎ−ｇｒａｍに最適化した構造を示す。この構造に最適化したＬＯＵＤＳビット列を表２に示す。
【００８０】
【表２】
【００８１】
図７および表２のノード８は、図６中のノード９に対応している。ここではＮ1＝４であるため、「ｐａｒｅｎｔ（８）＝ｓｅｌｅｃｔ１（８＋１−４）＋４−８＝５＋４−８＝１」から、ノード８の親ノードはノード１と求められる。また、「ｆｉｒｓｔ＿ｃｈｉｌｄ（８）＝ｓｅｌｅｃｔ0（８）＋４＋１−８＝１６＋４＋１−８＝１３」から、ノード８の最初の子ノードはノード１３と求められる。
【００８２】
ここでｎ−ｇｒａｍ言語モデルを第１形態に基づき圧縮した場合には式１５のビットでポインタ表現されていた。ここから２＋Ｎn＋Ｎ1＋１ビットが削減されるため、第２形態の圧縮によれば、ｎ−ｇｒａｍ言語モデルは式１７のビット数でポインタが表現され、さらにデータ量を抑制することができる。
【００８３】
【数１７】
【００８４】
≪ｎ−ｇｒａｍアクセス装置２≫
前記アクセス装置２は、前記入力手段を通じて与えられた単語列（式２）を入力として、前記圧縮データ記憶部７を参照する。ここでは前記圧縮装置１により圧縮表現されたｎ−ｇｒａｍモデルのポインタを辿ることにより、平滑化された確率（式６）およびバックオフ係数（式７）などへアクセスし、これらの値を出力する。
【００８５】
具体的には、前記アクセス部（ｆｉｒｓｔ＿ｃｈｉｌｄ）８は、「ｗ1，．．．，ｗn」のｎ−ｇｒａｍの位置を入力として、「ｗ1，．．．，ｗn，ｗn+1」という「（ｎ＋１）−ｇｒａｍ」のうち，「ｗn+1」の単語ＩＤが一番小さいものの位置を前記入力手段に返信する。このとき前記圧縮データ記憶部７の記憶データが、トライ構造に基づくポインタ表現（第１形態の圧縮結果）であれば、式９によって算出する一方、ｎ−ｇｒａｍ構造に基づくポインタ表現（第２形態の圧縮結果）であれば、式１１によって算出する。
【００８６】
また、前記アクセス部（ｐａｒｅｎｔ）９は、「ｗ1，．．．，ｗn-1，ｗn」のｎ−ｇｒａｍの位置を入力として、「ｗ1，．．．，ｗn-1」の（ｎ−１）−ｇｒａｍの位置を前記入力手段に返信する。このとき前記圧縮データ記憶部７の記憶データが、トライ構造に基づくポインタ表現（第１形態の圧縮結果）であれば、式８によって算出する一方、ｎ−ｇｒａｍ構造に基づくポインタ表現（第２形態の圧縮結果）であれば、式１０によって算出する。なお、式８〜式１１はプログラムなどに定義されているものとする。
【００８７】
このように前記両装置１．２によれば、ｎ−ｇｒａｍ言語モデルのポインタ配列のデータ量が抑制されるため、高価な計算機（コンピュータ）を使用することなく、汎用的な計算機の主記憶装置にポインタ配列の大部分を記憶でき、前記圧縮データ記憶部７をいわゆるオンメモリデータベースとして利用可能にする。
【００８８】
したがって、前記アクセス部８．９のポインタへのアクセス速度が向上し、ｎ−ｇｒａｍを用いた機械翻訳や音声認識などに際して、効率的にｎ−ｇｒａｍモデルにアクセス可能となる。加えて、頻繁に利用するｎ−ｇｒａｍ言語モデルの確率（式６）およびバックオフ係数（式７）などを記憶バッファなどにキャッシュしておけば、さらに処理を高速化することができる。
【００８９】
≪実験例≫
前記圧縮装置１の有効性を確認するために発明者達の実施したｎ−ｇｒａｍの圧縮実験を説明する。この実験には、表３に示すように、「Ｅｎｇｌｉｓｈ Ｇｉｇａｗｏｒｄ ３ｒｄ Ｅｄｉｔｉｏｎ」を用いて学習した「Ｅｎｇｌｉｓｈ Ｇｉｇａｗｏｒｄ ５−ｇｒａｍ」と、ＬＤＣから公開されている「Ｅｎｇｌｉｓｈ Ｗｅｂ １Ｔ ５−ｇｒａｍ」と、ＧＳＫから公開されている「Ｊａｐａｎｅｓｅ Ｗｅｂ １Ｔ ７−ｇｒａｍ」とを用いた。
【００９０】
【表３】
【００９１】
表３中の”ｃｏｕｎｔ ｓｉｚｅ （ｇｉｚｐ）”は、前記実験に用いた各ｎ−ｇｒａｍの大きさ（サイズ）を示している。ここではｎ−ｇｒａｍの頻度を格納したＡＳＣＩＩテキストファイルを、ｇｚｉｐで圧縮した結果のサイズを表している。
【００９２】
【表４】
【００９３】
表４は、前記実験におけるポインタ配列の圧縮結果を示している。表４中の”４−ｂｙｔｅ Ｐｏｉｎｔｅｒ”は、「ｎ−ｇｒａｍ言語モデルのデータ構造（ポインタ固定バイト表現）」のポインタを４バイト整数で表現したときのポインタ配列を表している（前記データ変換部３で求めたポインタ配列に相当する）。
【００９４】
また、”提案法”は、このポインタ配列をｎ−ｇｒａｍに最適化したＬＯＵＤＳビット列で表現した結果（第２形態の圧縮結果）を示している。この”提案法”によれば、表４の各列に示すように、ポインタを４バイト整数で表現する一般的な表現方法が約１／１０に圧縮されている。これによりポインタ配列のデータ量が効果的に低減されることが明らかとなった。
【００９５】
≪プログラムなど≫
本発明は、前記両装置１．２を構成する各部３〜９の一部もしくは全部として、コンピュータを機能させるプログラムとして構成することもできる。この場合には、前記データ変換ステップ、前記ポインタ表現の圧縮ステップ、アクセスステップの全ステップあるいは一部のステップをコンピュータに実行させる。
【００９６】
このプログラムは、Ｗｅｂサイトや電子メールなどネットワークを通じて提供することができる。また、前記プログラムは、ＣＤ−ＲＯＭ，ＤＶＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷ，ＤＶＤ−Ｒ，ＤＶＤ−ＲＷ，ＭＯ，ＨＤＤ，Ｂｌｕ−ｒａｙ Ｄｉｓｋ（登録商標）などの記録媒体に記録して、保存・配布することも可能である。この記録媒体は、記録媒体駆動装置を利用して読み出され、そのプログラムコード自体が前記実施形態の処理を実現するので、該記録媒体も本発明を構成する。
【符号の説明】
【００９７】
１…言語モデル圧縮装置
２…言語モデルのアクセス装置
３…データ構造変換部（データ構造変換手段）
４…ポインタ表現の圧縮部（ポインタ表現の圧縮手段）
５…言語モデル記憶部
６…変換データ記憶部
７…圧縮データ記憶部
８…ｎ−ｇｒａｍアクセス部「ｆｉｒｓｔ＿ｃｈｉｌｄ」（第２のアクセス手段）
９…ｎ−ｇｒａｍアクセス部「ｐａｒｅｎｔ」（第１のアクセス手段）
【技術分野】
【０００１】
本発明は、単語をｎ文字単位で分割し、それぞれの単語列とその出現頻度（確率）を求めたｎ−ｇｒａｍ言語モデルを圧縮するための技術、および効率的にｎ−ｇｒａｍ言語モデルにアクセスするための技術に関する。
【背景技術】
【０００２】
周知のように、音声認識や統計的機械翻訳などの分野では、非特許文献１に示すように、出力される言語(単語列)の尤もらしさをモデル化するために、単語ｎ個からなる単語列(ｎ−ｇｒａｍと呼ぶ)に対する条件付確率（式１）が広く用いられている。
【０００３】
【数１】
【０００４】
単語列（式２）の尤もらしさ（式３）は、式１の条件付確率を用いて、式４のように近似的に求めることができる。
【０００５】
【数２】
【０００６】
【数３】
【０００７】
【数４】
【０００８】
このような式１の条件付確率を与えるモデルは、ｎ−ｇｒａｍ言語モデルと呼ばれている。「ｎ」の大きさとしては、音声認識では「３〜４」の値を、統計的機械翻訳では「４〜５」の値を用いることが多い。式１の条件付確率は、式５のように、再帰的に計算される。また、式２は、単語ｗ1，ｗ2，・・・，ｗnを省略標記したものである。
【０００９】
【数５】
【００１０】
このような統計モデルを計算機（コンピュータ）で利用するためには、まず、学習データに現れる単語列（式２）に応じて、式６の平滑された確率、式７のバックオフ係数などの情報を格納すること、さらに単語列（式２）を入力として、前記各情報に効率的にアクセスできることが必要となる。
【００１１】
【数６】
【００１２】
【数７】
【００１３】
そして、音声認識や統計的機械翻訳などｎ−ｇｒａｍのアプリケーションの性能を高めるためには、非特許文献２に示すように、大量の学習データを用いてこれらのパラメータを学習することはもとより、学習データを増やすことで、そこに現れる正しい単語列（式２）のバリエーション(ｎ−ｇｒａｍのバリエーション)を多数保持することが有効と知られている。
【００１４】
また、ｎ−ｇｒａｍ言語モデルは、非特許文献３に示すように、木構造（データ構造）で表現できることが知られている。さらに木構造の一種であるトライ（ｔｒｉｅ）をコンパクトに表現する手法として、非特許文献４．５に示すように、ＬＯＵＤＳ（Ｌｅｖｅｌ−Ｏｒｄｅｒ Ｕｎａｒｙ Ｄｅｇｒｅｅ Ｓｅｑｕｅｎｃｅ）が知られている。ここでトライとは、１つのルートノードを持つ順序付き木構造の一種であり、プレフィックス木（Ｐｒｅｆｉｘ Ｔｒｅｅ）とも呼ばれている。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】Ｓ． Ｍ． Ｋａｔｚ， “Ｅｓｔｉｍａｔｉｏｎ ｏｆ Ｐｒｏｂａｂｉｌｉｔｉｅｓ ｆｒｏｍ Ｓｐａｒｓｅ Ｄａｔａ ｆｏｒ ｔｈｅ Ｌａｎｇｕａｇｅ Ｍｏｄｅｌ Ｃｏｍｐｏｎｅｎｔ ｏｆ ａ Ｓｐｅｅｃｈ Ｒｅｃｏｇｎｉｚｅｒ，” ＩＥＥＥ ＴＲＡＮＳＡＣＴＩＯＮＳ ＯＮ ＡＣＯＵＳＴＩＣ， ＳＰＥＥＣＨ， ＡＮＤ ＳＩＧＮＡＬ ＰＲＯＣＥＳＳＩＮＧ， ＶＯＬ．ＡＳＳＰ−３５，ＮＯ．３，ＭＡＲＣＨ １９８７，ｐｐ． ４００−４０１
【非特許文献２】Ｔ． Ｂｒａｎｔｓ， Ａ． Ｃ． Ｐｏｐａｔ， Ｐ． Ｘｕ， Ｆ． Ｊ． Ｏｃｈ， ａｎｄ Ｊ． Ｄｅａｎ， Ｌａｒｇｅ Ｌａｎｇｕａｇｅ Ｍｏｄｅｌｓ ｉｎ Ｍａｃｈｉｎｅ Ｔｒａｎｓｌａｔｉｏｎ， Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００７ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｍｐｉｒｉｃａｌ Ｍｅｔｈｏｄｓ ｉｎ Ｎａｔｕｒａｌ Ｌａｎｇｕａｇｅ Ｐｒｏｃｅｓｓｉｎｇ ａｎｄ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｌａｎｇｕａｇｅ Ｌｅａｒｎｉｎｇ （ＥＭＮＬＰ−ＣｏＮＬＬ）， ｐｐ． ８５８−−８６７， ２００７．
【非特許文献３】Ｂ． Ｒａｊ ａｎｄ Ｅ．Ｗ．Ｄ． Ｗｈｉｔｔａｋｅｒ． ”ＬＯＳＳＬＥＳＳ ＣＯＭＰＲＥＳＳＩＯＮ ＯＦ ＬＡＮＧＵＡＧＥ ＭＯＤＥＬ ＳＴＲＵＣＴＵＲＥ ＡＮＤ ＷＯＲＤ ＩＤＥＮＴＩＦＩＥＲＳ” Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＣＡＳＳＰ， ｖｏｌｕｍｅ １， ｐａｇｅｓ Ｉ≡３８８≡Ｉ≡３９１ ｖｏｌ．１， Ａｐｒｉｌ ２００３．
【非特許文献４】Ｏ’Ｎｅｉｌ Ｄｅｌｐｒａｔｔ， Ｎａｉｌａ Ｒａｈｍａｎ， ａｎｄ Ｒａｊｅｅｖ Ｒａｍａｎ． ”Ｅｎｇｉｎｅｅｒｉｎｇ ｔｈｅ ＬＯＵＤＳ Ｓｕｃｃｉｎｃｔ Ｔｒｅｅ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ” Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｅｘｐｅｒｉｍｅｎｔａｌ Ａｌｇｏｒｉｔｈｍｓ， ｐａｇｅｓ １３４≡１４５， ２００６．
【非特許文献５】Ｇｕｙ Ｊａｃｏｂｓｏｎ． ”Ｓｐａｃｅ−ｅｆｆｉｃｉｅｎｔ Ｓｔａｔｉｃ Ｔｒｅｅｓ ａｎｄ Ｇｒａｐｈｓ” Ｉｎ ３０ｔｈ Ａｎｎｕａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｆｏｕｎｄａｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ｐａｇｅｓ ５４９≡５５４， Ｎｏｖ １９８９．
【非特許文献６】Ｄｏｎｇ Ｋｙｕｅ Ｋｉｍ， Ｊｏｏｎｇ Ｃｈａｅ Ｎａ， Ｊｉ Ｅｕｎ Ｋｉｍ， ａｎｄ Ｋｕｎｓｏｏ Ｐａｒｋ． ”Ｅｆｆｉｃｉｅｎｔ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｒａｎｋ ａｎｄ ｓｅｌｅｃｔ ｆｕｎｃｔｉｏｎｓ ｆｏｒ ｓｕｃｃｉｎｃｔ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ” Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｅｘｐｅｒｉｍｅｎｔａｌ Ａｌｇｏｒｉｔｈｍｓ， ｐａｇｅｓ ３１５≡３２７， ２００５．
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかしながら、大量のデータで学習したｎ−ｇｒａｍ言語モデルは、非常に多種多様なｎ−ｇｒａｍを格納するため、モデル表現が巨大になってしまう。特に、ｎ−ｇｒａｍ言語モデルを使う際には効率的なアクセスが要求されるため、それを考慮したデータ構造は大きなものとなり易い。
【００１７】
その一方で効率的なアクセスを実現するためには、ｎ−ｇｒａｍ言語モデルを主記憶装置（ＲＡＭ）に格納することが好ましいが、現代の計算機（コンピュータ）をもってしても主記憶装置の記憶容量には限界がある。例えば、全Ｗｅｂデータで学習した巨大なｎ−ｇｒａｍを、従来法で表現すると４０ＧＢ以上の容量が必要となるため、一部の非常に高価な計算機を除いて主記憶装置に保持することは困難である。
【００１８】
また、ｎ−ｇｒａｍ言語モデルの木構造の表現は、ルートノードが存在しない（あるいは１つではない）。トライ構造をコンパクトに表現する方法は知られているが、ｎ−ｇｒａｍ言語モデルのデータ構造はトライではないため、トライ構造をコンパクトに表現する方法をｎ−ｇｒａｍ言語モデルの表現に応用するには、さらなる工夫が必要である。
【００１９】
本発明は、上述のような従来技術の問題点を解決するためになされたものであり、ｎ−ｇｒａｍ言語モデルのデータ量を抑制し、効率的にアクセス可能な技術を提供することを解決課題とする。
【課題を解決するための手段】
【００２０】
そこで、本発明は、自然言語処理システムなどで用いられるｎ−ｇｒａｍ言語モデルのデータ構造をトライ（木構造）に変換し、トライをコンパクトに表現するＬＯＵＤＳという手法によって、より少ないビット列で表現する。さらに、ｎ−ｇｒａｍの特性を考慮して、この手法を改良する。
【００２１】
本発明に係る言語モデル圧縮装置の一態様は、仮想的なルートノードを設けて、ｎ−ｇｒａｍ言語モデルの構造をトライ構造に変換するデータ構造変換手段と、前記データ構造変換手段にて変換されたトライ構造をＬＯＵＤＳ（Ｌｅｖｅｌ−Ｏｒｄｅｒ Ｕｎａｒｙ Ｄｅｇｒｅｅ Ｓｅｑｕｅｎｃｅ）表現に圧縮変換する圧縮手段と、を備える。
【００２２】
本発明に係る言語モデルの他の態様は、ｎ−ｇｒａｍ言語モデルの最高次数の最初のノードの位置（ノードＩＤ）を記憶装置に記憶し、ｎ−ｇｒａｍ言語モデルの構造を表すポインタ表現を、最高次数のｎ−ｇｒａｍを削除した表現に変換するデータ構造変換手段を、備える。ここでは１−ｇｒａｍの個数Ｎ1を記憶装置に記憶し、前記データ構造変換手段にて変換したｎ−ｇｒａｍ言語モデルの構造を、スーパーノード（トライ構造のルートノードを指す仮想的なルートノード）および最高次数のｎ−ｇｒａｍに対応したビットをもたないように拡張したＬＯＵＤＳ表現に圧縮変換する圧縮手段を、さらに備えてもよい。
【００２３】
本発明に係る言語モデルのアクセス装置の一態様は、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式８により算出して出力する第１のアクセス手段と、
入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式９により算出して出力する第２のアクセス手段と、を備える。
【００２４】
【数８】
【００２５】
【数９】
【００２６】
本発明に係る言語モデルのアクセス装置の他の態様は、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式１０により算出して出力する第１のアクセス手段と、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式１１により算出して出力する第２のアクセス手段と、を備える。
【００２７】
【数１０】
【００２８】
【数１１】
【００２９】
本発明に係る言語モデル圧縮方法の一態様は、データ構造変換手段が、仮想的なルートノードを設けて、ｎ−ｇｒａｍ言語モデルの構造をトライ構造に変換するデータ構造変換ステップと、圧縮手段が、前記データ構造変換ステップにて変換されたトライ構造をＬＯＵＤＳ（Ｌｅｖｅｌ−Ｏｒｄｅｒ Ｕｎａｒｙ Ｄｅｇｒｅｅ Ｓｅｑｕｅｎｃｅ）表現に圧縮変換する圧縮ステップと、を有する。
【００３０】
本発明に係る言語モデル圧縮方法の他の態様は、データ構造変換手段が、前記ｎ−ｇｒａｍ言語モデルの最高次数の最初のノードの位置（ノードＩＤ）を記憶装置に記憶し、ｎ−ｇｒａｍ言語モデルの構造を表すポインタ表現を、最高次数のｎ−ｇｒａｍを削除した表現に変換するデータ構造変換ステップを、有する。ここでは圧縮手段が、１−ｇｒａｍの個数Ｎ1を記憶装置に記憶させ、前記データ構造変換手段にて変換したｎ−ｇｒａｍ言語モデルの構造を、スーパーノード（トライ構造のルートノードを指す仮想的なルートノード）および最高次数のｎ−ｇｒａｍに対応したビットをもたないように拡張したＬＯＵＤＳ表現に圧縮変換する圧縮ステップを、さらに有してもよい。
【００３１】
本発明に係る言語モデルのアクセス方法の一態様は、第１のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式８により算出して出力するステップと、第２のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式９により算出して出力するステップと、を有する。
【００３２】
【数８】
【００３３】
【数９】
【００３４】
本発明に係る言語モデルのアクセス方法の他の態様は、第１のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式１０により算出して出力するステップと、第２のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式１１により算出して出力するステップと、を有する。
【００３５】
【数１０】
【００３６】
【数１１】
【００３７】
なお、本発明は、前記各装置としてコンピュータを機能させるためのプログラムの態様としてもよい。このプログラムは記録媒体に記録した態様で配布・提供することができる。
【発明の効果】
【００３８】
本発明によれば、ｎ−ｇｒａｍ言語モデルの構造を規定するポインタ表現のデータ量が抑制される。このことにより巨大なｎ−ｇｒａｍ言語モデルであっても、ポインタ表現のすべてもしくは大部分を、アクセスの遅いハードディスクドライブ装置に代わって，アクセスの高速なメモリ（ＲＡＭ）上に保持することが可能となる。本発明により巨大なｎ−ｇｒａｍ言語モデルを用いた機械翻訳や音声認識などにあたって、効率的にｎ−ｇｒａｍ言語モデルにアクセスすることが可能となり、処理の高速化に貢献する。
【図面の簡単な説明】
【００３９】
【図１】本発明の実施形態に係る言語モデル圧縮装置および言語モデルのアクセス装置の構成図。
【図２】同 言語モデル記憶部に記憶されたｎ−ｇｒａｍ言語モデルのデータ構造図。
【図３】同 データ構造変換部の変換後におけるｎ−ｇｒａｍ言語モデルのデータ構造図。
【図４】トライ構造に基づくポインタ表現を示す図。
【図５】ｎ−ｇｒａｍ構造に基づくポインタ表現を示す図。
【図６】トライ構造の構造図。
【図７】ｎ−ｇｒａｍの構造図。
【発明を実施するための形態】
【００４０】
以下、本発明の実施形態に係る言語モデル圧縮装置および言語モデルのアクセス装置を説明する。この両装置は、音声認識装置や機械翻訳機などの自然言語処理システムにおいてコンビネーションとして利用される。ここでは前記圧縮装置は、ｎ−ｇｒａｍの学習装置により生成されたｎ−ｇｒａｍ言語モデルのデータ量を抑制する一方、前記アクセス装置は音声認識や統計的機械翻訳にあたって前記圧縮装置でデータ容量を抑制されたｎ−ｇｒａｍ言語モデルにアクセスする。
【００４１】
具体的には前記各装置は、コンピュータにより構成され、通常のコンピュータのハードウェアリソース、例えばＣＰＵ，メモリ（ＲＡＭ）などの主記憶装置，ハードディスクドライブ装置などを備えている。
【００４２】
このハードウェアリソースとソフトウェアリソース（ＯＳ，アプリケーションなど）との協働の結果、図１に示すように、前記圧縮装置１は、データ構造変換部３，ポインタ表現の圧縮部４，言語モデル記憶部５，変換データ記憶部６，圧縮データ記憶部７を実装する一方、前記アクセス装置２は、ｎ−ｇｒａｍアクセス部（ｆｉｒｓｔ＿ｃｈｉｌｄ）８，ｎ−ｇｒａｍアクセス部（ｐａｒｅｎｔ）９を実装する。なお、前記両装置１．２は、必ずしも複数のコンピュータで構成する必要はなく、単一のコンピュータで構成してもよい。
【００４３】
概略を説明すれば、前記各記憶部５〜７は、前記ハードディスクドライブ装置あるいは前記主記憶装置に構築されている。このうち前記言語モデル記憶部５は、大量の学習用データ（例えばＷｅｂデータなど）に基づく学習結果として生成された言語モデルを格納する。ここで格納される言語モデルは、通常の「ｎ−ｇｒａｍ言語モデルのデータ構造」形式で表現されているものとする。
【００４４】
前記データ構造変換部３は、矢印Ａに示すように、前記言語モデル記憶部５の言語モデルを入力とし、ポインタの固定バイト表現されたｎ−ｇｒａｍ言語モデルのデータ構造に変換する（データ変換ステップ）。この変換後のデータは、矢印Ｂに示すように、前記変換データ記憶部６に蓄積される。
【００４５】
前記ポインタ表現の圧縮部４は、矢印Ｃに示すように、前記変換データ記憶部６の蓄積データを入力とし、該蓄積データにポインタ配列をコンパクトに表現する処理を加え、データ量を圧縮する（ポインタ表現の圧縮ステップ）。すなわち、ポインタのＬＯＵＤＳ表現されたｎ−ｇｒａｍ言語モデルのデータ構造に圧縮変換し、矢印Ｄに示すように、前記圧縮データ記憶部７に記憶させる。
【００４６】
前記アクセス装置２は、図示省略の入力手段を通じて与えられた単語列（ｎ−ｇｒａｍ）を入力とし、矢印Ｅ．Ｆに示すように、前記圧縮データ記憶部７の記憶データ、即ち圧縮表現されたｎ−ｇｒａｍ言語モデルのポインタにアクセスする（アクセスステップ）。具体的には、前記アクセス部８は、矢印Ｇに示すように、ｎ−ｇｒａｍ（単語列）の位置を入力とし、前記圧縮データ記憶部７を参照して、矢印Ｈに示すように、（ｎ＋１）−ｇｒａｍの位置を出力する。一方、前記アクセス部９は、矢印Ｉに示すように、ｎ−ｇｒａｍ（単語列）の位置を入力とし、前記圧縮データ記憶部７を参照して、矢印Ｊに示すように、（ｎ−１）−ｇｒａｍの位置を出力する。以下、前記両装置１．２の各機能ブロック３〜９の詳細を説明する。
【００４７】
≪言語モデル圧縮装置１≫
（１）データ構造変換部３
まず、前記言語モデル記憶部５の格納データ、即ちｎ−ｇｒａｍのデータ構造を説明する。このｎ−ｇｒａｍは、図２のデータ構造で表現され（非特許文献２参照）、「１−ｇｒａｍ， ２−ｇｒａｍ， ３−ｇｒａｍ， …」は、それぞれ前記言語モデル記憶部５の別テーブルで表現される。
【００４８】
このｎ−ｇｒａｍのテーブルの各列は、単語ｗnの単語ＩＤ（ｗｏｒｄ ｉｄ）、式６の平滑化された確率値（ｐｒｏｂａｂｉｌｉｔｙ）、式７のバックオフ係数（ｂａｃｋ−ｏｆｆ）、（Ｘ＋１）−ｇｒａｍの最初の位置を示すポインタ（ｐｏｉｎｔｅｒ）を有している（Ｘは１≦Ｘ≦ｎの整数）。各テーブルは、このような四つ組の配列として表現される。ポインタとしては、この配列のインデックスを用いることができる。例えば４バイト整数によってポインタを実現できる。
【００４９】
ここでＸ−ｇｒａｍ（Ｘは１≦Ｘ≦ｎの整数）のポインタの指す先の連続した領域には、式１２の履歴を共有する（Ｘ＋１）−ｇｒａｍが、ｗx+1の単語ＩＤ順にソートされて格納される。
【００５０】
【数１２】
【００５１】
この領域の終わりの境界は、Ｘ−ｇｒａｍの次のエントリのポインタが指す先で規定される。あるＸ−ｇｒａｍを探すには、それを構成する単語毎にバイナリ探索が実施されるため、合計Ｘ回のバイナリ探索が行われる。単語ＩＤを１−ｇｒａｍテーブルの各行の位置で定義することで、図２に示すように、１−ｇｒａｍの単語ＩＤの列は省略することができる。
【００５２】
前記データ構造変換部３は、前記言語モデル記憶部５に格納されている図２のデータ構造を変換し、図３に示すように、単語ＩＤ、平滑化された確率値、バックオフ係数、ポインタの各々を別々の配列で表し、前記変換データ記憶部６に格納する。ここでは１−ｇｒａｍの後ろに２−ｇｒａｍの情報を、２−ｇｒａｍの後に３−ｇｒａｍの情報を連結し、該連結処理を順次に実施する。なお、オーダの境界(２−ｇｒａｍ，３−ｇｒａｍ，…の開始位置)を、別途主記憶装置に記憶し、各オーダの情報にアクセスできるようにする。
【００５３】
ポインタ配列としては、図４のトライ（ｔｒｉｅ）構造に基づく表現（第１形態）と、図５のｎ−ｇｒａｍ構造に基づく表現（第２形態）のいずれかを使用する。なお、図４．５は、それぞれ図６．７の木構造に対応したポインタ構造を表す。配列の要素となるポインタは、固定バイト（例えば４バイト）整数で表現されているものとする。
【００５４】
なお、第２形態においては、ｎ−ｇｒａｍ言語モデルの最高次数の最初のエントリの位置を記憶しておき、第1形態のポインタ配列ではそれ以降に格納されていた最高次数のｎ−ｇｒａｍのポインタを第２形態では格納しないものとする。ただし、最高次数ｎ−ｇｒａｍの情報を格納しないのは、ポインタ配列だけであり、その他の単語ＩＤ（ｗｏｒｄ ｉｄ）、平滑化された式６の確率値（ｐｒｏｂａｂｉｌｉｔｙ）、式７のバックオフ係数（ｂａｃｋ−ｏｆｆ）については、最高次数ｎ−ｇｒａｍの情報も格納する。
【００５５】
（２）ポインタ表現の圧縮部４
前記圧縮部４は、前記変換データ記憶部６を参照して、前記データ構造変換部３で変換した各配列のうち、ポインタを示す配列をコンパクトに表現して、前記変換データ記憶部６に格納する。以下、各形態の具体的内容を説明する。
【００５６】
＜第１形態＞
まず、前記圧縮部４における第１形態について説明する。トライ（ｔｒｉｅ）とは、木構造の一種であり、１つルートノードを持つ木構造で表される。図２に示したｎ−ｇｒａｍのデータ構造は、ルートノードが１つではないためトライではないが、ここでは仮想的なルートノードを設けることにより、ｎ−ｇｒａｍのデータ構造をトライに擬制して、コンパクトなトライ表現法であるＬＯＵＤＳ（非特許文献４．５参照）を応用し、ポインタ配列を圧縮する。
【００５７】
詳細を説明すれば、ＬＯＵＤＳによる表現では、ルートノードから始まり、「１−ｇｒａｍ，２−ｇｒａｍ，…」の階層順で左から右、即ち幅優先の順序で、ノードにノードＩＤが割り当てられる。ここではｄ個（ｄ≧０）の子供（子ノード）を有するノード（親ノード）は、「１d０」のビット列で表現される（「１d」は、「１」がｄ個ならんでいるビット列を表している。）。仮想的なルートノードを指すさらなる仮想的なノードとしてスーパールートノードを設ける。スーパールートノードの子供はルートノード一つであるから、スーパールートノードは「１０」で表される。
【００５８】
図６はトライ構造の一例を示している。このトライ構造例のＬＯＵＤＳビット列によるポインタ表現を表１に示す。
【００５９】
【表１】
【００６０】
前記トライ構造例によれば、ルートノード「０」は、４つの子供を持つことから、４つの「１」と終わりを表す１つの「０」とで表されている。ここでＭ個のノードを有するトライは、（Ｍ＋１）個の「０」と，Ｍ個の「１」とで表されるため、合計２Ｍ＋１ビットで表現される．
Ｘ−ｇｒａｍの個数をＮxと表し、式１３を用いれば、ｎ−ｇｒａｍ言語モデルでは式１４が成立する。したがって、ｎ−ｇｒａｍ言語モデルは、式１５のビット数でポインタが表現される。ここで圧縮表現されたポインタが前記圧縮データ記憶部７に記憶される。
【００６１】
【数１３】
【００６２】
【数１４】
【００６３】
【数１５】
【００６４】
以上のように圧縮表現されたｎ−ｇｒａｍ言語モデルにアクセスするためには、ＬＯＵＤＳビット列上に、ビット列中のｉ番目の「１」の位置を返す「ｓｅｌｅｃｔ1（ｉ）」という操作を定義する。ここでビットの位置は、表１に示すように、「０」から始まっているものとする。同様にビット列中のｉ番目の「０」の位置を返す操作として「ｓｅｌｅｃｔ0（ｉ）」を定義できる。
【００６５】
「ｓｅｌｅｃｔb（ｉ）（ｂ＝０ ｏｒ １）」は、非特許文献６などの手法を用いて、効率的に実現することができる。この操作を用いることで、ノードｘ（ノードＩＤ＝「ｘ」のノード）に対して親ノードＩＤを返す関数「ｐａｒｅｎｔ（ｘ）」や、ノードｘに対して最初の子供のＩＤを返す関数「ｆｉｒｓｔ＿ｃｈｉｌｄ（ｘ）」が式８．式９で実現される。
【００６６】
【数８】
【００６７】
【数９】
【００６８】
例えば、ノード９の親ノードは、「ｐａｒｅｎｔ（９）＝ｓｅｌｅｃｔ（９＋１）−９−１＝１２−９−１＝２」から、ノード２と求められる。また、ノード９の最初の子ノードは、「ｆｉｒｓｔ＿ｃｈｉｌｄ（９）＝ｓｅｌｅｃｔ0（９＋１）−９＝２３−９＝１４」となり，ノード１４であると求まる。
【００６９】
ただし、「ｆｉｒｓｔ＿ｃｈｉｌｄ（ｘ）」が、０以上のノードＩＤを返すからといってノードｘが、子ノードを有することが保証されるとは限らない。ノードｘが子ノードを有する必要十分条件は、「ｆｉｒｓｔ＿ｃｈｉｌｄ（ｘ）≠ｆｉｒｓｔ＿ｃｈｉｌｄ（ｘ＋１）」である。またノードｘに係る子ノードのＩＤの範囲は、［ｆｉｒｓｔ＿ｃｈｉｌｄ（ｘ），ｆｉｒｓｔ＿ｃｈｉｌｄ（ｘ＋１））で求まる。前記ｎ−ｇｒａｍアクセス装置２では、以上の関数を利用してｎ−ｇｒａｍ言語モデルへのアクセスを行う。
【００７０】
＜第２形態＞
つぎに前記圧縮部４における第２形態を説明する。ここでは第１形態で用いたＬＯＵＤＳを、ｎ−ｇｒａｍの特性を利用して、さらにコンパクトに表現できるように拡張処理されている。
【００７１】
すなわち、図２および図３に示すように、ｎ−ｇｒａｍの場合はルートノードに格納する情報は存在しない。したがって、ルートノードを削除し、仮想的なスーパールートノードが直接１−ｇｒａｍの各ノードを指すようにする。ここではノードＩＤは、１−ｇｒａｍの最初のノードが「０」となるように番号付けるものとする。これで旧ルートノードの２ビットが削減される。
【００７２】
また、ｎ−ｇｒａｍの場合、１〜ｎまでの階層をもつ構造をしており、最下層にある最高次数ｎのノードは子ノードを有していない。ここでＸ−ｇｒａｍのノードの個数をＮxとすると、ｎ−ｇｒａｍの最高次数のノード数はＮnであり、Ｎn個の「０」が冗長である。そこで、最高次数の最初のノードＩＤを前記主記憶装置に記憶しておき、ｎ−ｇｒａｍ言語モデルにアクセスする際には該ノードＩＤ以外は子ノードを有しないと判定することとする。これにより、Ｎn個の「０」、即ちＮnビットを消去することができる。
【００７３】
さらに、スーパールートノードは、式１６で表されるが、１−ｇｒａｍの個数Ｎ1を記憶しておくことで、これは取り去ることができる。このように前記各ノードが存在しないものとして木構造を生成し、ビットを割り当てる。これでＮ1＋１ビットが削減できる。これにより、第２形態における圧縮表現されたポインタは、スーパーノードに対応したビットと最高次数のｎ−ｇｒａｍに対応したビットをもたない表現（拡張したＬＯＵＤＳ表現）となる。この圧縮変換されたポインタを、前記圧縮データ記憶部７に記憶する。
【００７４】
【数１６】
【００７５】
第２形態において圧縮表現されたｎ−ｇｒａｍ言語モデルにアクセスするためには、第１形態の式８．式９を、式１０．式１１に書き換える。
【００７６】
【数１０】
【００７７】
【数１１】
【００７８】
ただし、最高次数の最初のノードＩＤをＹとすると、「ｘ≧Ｙ」のときは、「ｓｅｌｅｃｔ1（ｘ）＝ｓｅｌｅｃｔ1（Ｙ−１）、ｓｅｌｅｃｔ0（ｘ）＝ｓｅｌｅｃｔ0（Ｙ−１）＋ｘ−Ｙ＋１」とする。
【００７９】
図７に、トライ構造を刈り込みｎ−ｇｒａｍに最適化した構造を示す。この構造に最適化したＬＯＵＤＳビット列を表２に示す。
【００８０】
【表２】
【００８１】
図７および表２のノード８は、図６中のノード９に対応している。ここではＮ1＝４であるため、「ｐａｒｅｎｔ（８）＝ｓｅｌｅｃｔ１（８＋１−４）＋４−８＝５＋４−８＝１」から、ノード８の親ノードはノード１と求められる。また、「ｆｉｒｓｔ＿ｃｈｉｌｄ（８）＝ｓｅｌｅｃｔ0（８）＋４＋１−８＝１６＋４＋１−８＝１３」から、ノード８の最初の子ノードはノード１３と求められる。
【００８２】
ここでｎ−ｇｒａｍ言語モデルを第１形態に基づき圧縮した場合には式１５のビットでポインタ表現されていた。ここから２＋Ｎn＋Ｎ1＋１ビットが削減されるため、第２形態の圧縮によれば、ｎ−ｇｒａｍ言語モデルは式１７のビット数でポインタが表現され、さらにデータ量を抑制することができる。
【００８３】
【数１７】
【００８４】
≪ｎ−ｇｒａｍアクセス装置２≫
前記アクセス装置２は、前記入力手段を通じて与えられた単語列（式２）を入力として、前記圧縮データ記憶部７を参照する。ここでは前記圧縮装置１により圧縮表現されたｎ−ｇｒａｍモデルのポインタを辿ることにより、平滑化された確率（式６）およびバックオフ係数（式７）などへアクセスし、これらの値を出力する。
【００８５】
具体的には、前記アクセス部（ｆｉｒｓｔ＿ｃｈｉｌｄ）８は、「ｗ1，．．．，ｗn」のｎ−ｇｒａｍの位置を入力として、「ｗ1，．．．，ｗn，ｗn+1」という「（ｎ＋１）−ｇｒａｍ」のうち，「ｗn+1」の単語ＩＤが一番小さいものの位置を前記入力手段に返信する。このとき前記圧縮データ記憶部７の記憶データが、トライ構造に基づくポインタ表現（第１形態の圧縮結果）であれば、式９によって算出する一方、ｎ−ｇｒａｍ構造に基づくポインタ表現（第２形態の圧縮結果）であれば、式１１によって算出する。
【００８６】
また、前記アクセス部（ｐａｒｅｎｔ）９は、「ｗ1，．．．，ｗn-1，ｗn」のｎ−ｇｒａｍの位置を入力として、「ｗ1，．．．，ｗn-1」の（ｎ−１）−ｇｒａｍの位置を前記入力手段に返信する。このとき前記圧縮データ記憶部７の記憶データが、トライ構造に基づくポインタ表現（第１形態の圧縮結果）であれば、式８によって算出する一方、ｎ−ｇｒａｍ構造に基づくポインタ表現（第２形態の圧縮結果）であれば、式１０によって算出する。なお、式８〜式１１はプログラムなどに定義されているものとする。
【００８７】
このように前記両装置１．２によれば、ｎ−ｇｒａｍ言語モデルのポインタ配列のデータ量が抑制されるため、高価な計算機（コンピュータ）を使用することなく、汎用的な計算機の主記憶装置にポインタ配列の大部分を記憶でき、前記圧縮データ記憶部７をいわゆるオンメモリデータベースとして利用可能にする。
【００８８】
したがって、前記アクセス部８．９のポインタへのアクセス速度が向上し、ｎ−ｇｒａｍを用いた機械翻訳や音声認識などに際して、効率的にｎ−ｇｒａｍモデルにアクセス可能となる。加えて、頻繁に利用するｎ−ｇｒａｍ言語モデルの確率（式６）およびバックオフ係数（式７）などを記憶バッファなどにキャッシュしておけば、さらに処理を高速化することができる。
【００８９】
≪実験例≫
前記圧縮装置１の有効性を確認するために発明者達の実施したｎ−ｇｒａｍの圧縮実験を説明する。この実験には、表３に示すように、「Ｅｎｇｌｉｓｈ Ｇｉｇａｗｏｒｄ ３ｒｄ Ｅｄｉｔｉｏｎ」を用いて学習した「Ｅｎｇｌｉｓｈ Ｇｉｇａｗｏｒｄ ５−ｇｒａｍ」と、ＬＤＣから公開されている「Ｅｎｇｌｉｓｈ Ｗｅｂ １Ｔ ５−ｇｒａｍ」と、ＧＳＫから公開されている「Ｊａｐａｎｅｓｅ Ｗｅｂ １Ｔ ７−ｇｒａｍ」とを用いた。
【００９０】
【表３】
【００９１】
表３中の”ｃｏｕｎｔ ｓｉｚｅ （ｇｉｚｐ）”は、前記実験に用いた各ｎ−ｇｒａｍの大きさ（サイズ）を示している。ここではｎ−ｇｒａｍの頻度を格納したＡＳＣＩＩテキストファイルを、ｇｚｉｐで圧縮した結果のサイズを表している。
【００９２】
【表４】
【００９３】
表４は、前記実験におけるポインタ配列の圧縮結果を示している。表４中の”４−ｂｙｔｅ Ｐｏｉｎｔｅｒ”は、「ｎ−ｇｒａｍ言語モデルのデータ構造（ポインタ固定バイト表現）」のポインタを４バイト整数で表現したときのポインタ配列を表している（前記データ変換部３で求めたポインタ配列に相当する）。
【００９４】
また、”提案法”は、このポインタ配列をｎ−ｇｒａｍに最適化したＬＯＵＤＳビット列で表現した結果（第２形態の圧縮結果）を示している。この”提案法”によれば、表４の各列に示すように、ポインタを４バイト整数で表現する一般的な表現方法が約１／１０に圧縮されている。これによりポインタ配列のデータ量が効果的に低減されることが明らかとなった。
【００９５】
≪プログラムなど≫
本発明は、前記両装置１．２を構成する各部３〜９の一部もしくは全部として、コンピュータを機能させるプログラムとして構成することもできる。この場合には、前記データ変換ステップ、前記ポインタ表現の圧縮ステップ、アクセスステップの全ステップあるいは一部のステップをコンピュータに実行させる。
【００９６】
このプログラムは、Ｗｅｂサイトや電子メールなどネットワークを通じて提供することができる。また、前記プログラムは、ＣＤ−ＲＯＭ，ＤＶＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷ，ＤＶＤ−Ｒ，ＤＶＤ−ＲＷ，ＭＯ，ＨＤＤ，Ｂｌｕ−ｒａｙ Ｄｉｓｋ（登録商標）などの記録媒体に記録して、保存・配布することも可能である。この記録媒体は、記録媒体駆動装置を利用して読み出され、そのプログラムコード自体が前記実施形態の処理を実現するので、該記録媒体も本発明を構成する。
【符号の説明】
【００９７】
１…言語モデル圧縮装置
２…言語モデルのアクセス装置
３…データ構造変換部（データ構造変換手段）
４…ポインタ表現の圧縮部（ポインタ表現の圧縮手段）
５…言語モデル記憶部
６…変換データ記憶部
７…圧縮データ記憶部
８…ｎ−ｇｒａｍアクセス部「ｆｉｒｓｔ＿ｃｈｉｌｄ」（第２のアクセス手段）
９…ｎ−ｇｒａｍアクセス部「ｐａｒｅｎｔ」（第１のアクセス手段）
【特許請求の範囲】
【請求項１】
ｎ個の連続する単語からなる単語列の出現頻度から求めたｎ−ｇｒａｍ言語モデルのモデル表現を圧縮する装置であって、
仮想的なルートノードを設けて、前記ｎ−ｇｒａｍ言語モデルの構造をトライ構造に変換するデータ構造変換手段と、
前記データ構造変換手段にて変換されたトライ構造をＬＯＵＤＳ（Ｌｅｖｅｌ−Ｏｒｄｅｒ Ｕｎａｒｙ Ｄｅｇｒｅｅ Ｓｅｑｕｅｎｃｅ）表現に圧縮変換する圧縮手段と、
を備えることを特徴とする言語モデル圧縮装置。
【請求項２】
ｎ個の連続する単語からなる単語列の出現頻度から求めたｎ−ｇｒａｍ言語モデルのモデル表現を圧縮する装置であって、
前記ｎ−ｇｒａｍ言語モデルの最高次数の最初のノードの位置（ノードＩＤ）を記憶装置に記憶し、ｎ−ｇｒａｍ言語モデルの構造を表すポインタ表現を、最高次数のｎ−ｇｒａｍを削除した表現に変換するデータ構造変換手段を、
備えることを特徴とする言語モデル圧縮装置。
【請求項３】
請求項２記載の言語モデル圧縮装置において、
１−ｇｒａｍの個数Ｎ1を記憶装置に記憶し、前記データ構造変換手段にて変換したｎ−ｇｒａｍ言語モデルの構造を、スーパーノード（トライ構造のルートノードを指す仮想的なルートノード）および最高次数のｎ−ｇｒａｍに対応したビットをもたないように拡張したＬＯＵＤＳ表現に圧縮変換する圧縮手段を、
さらに備えることを特徴とする言語モデル圧縮装置。
【請求項４】
請求項１記載の言語モデル圧縮装置にて圧縮変換された前記ポインタを記憶する記憶手段を参照して、ｎ−ｇｒａｍ言語モデルにアクセスする装置であって、
入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式８により算出して出力する第１のアクセス手段と、
【数８】
入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式９により算出して出力する第２のアクセス手段と、
【数９】
を備えることを特徴とする言語モデルのアクセス装置。
【請求項５】
請求項３に記載の言語モデル圧縮装置にて圧縮変換された前記ポインタを記憶する記憶手段を参照して、ｎ−ｇｒａｍ言語モデルにアクセスする装置であって、
入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式１０により算出して出力する第１のアクセス手段と、
【数１０】
入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式１１により算出して出力する第２のアクセス手段と、
【数１１】
を備えること特徴とする言語モデルのアクセス装置。
【請求項６】
ｎ個の連続する単語からなる単語列の出現頻度から求めたｎ−ｇｒａｍ言語モデルのモデル表現を圧縮する方法であって、
データ構造変換手段が、仮想的なルートノードを設けて、前記ｎ−ｇｒａｍ言語モデルの構造をトライ構造に変換するデータ構造変換ステップと、
圧縮手段が、前記データ構造変換ステップにて変換されたトライ構造をＬＯＵＤＳ（Ｌｅｖｅｌ−Ｏｒｄｅｒ Ｕｎａｒｙ Ｄｅｇｒｅｅ Ｓｅｑｕｅｎｃｅ）表現に圧縮変換する圧縮ステップと、
を有することを特徴とする言語モデル圧縮方法。
【請求項７】
ｎ個の連続する単語からなる単語列の出現頻度から求めたｎ−ｇｒａｍ言語モデルのモデル表現を圧縮する方法であって、
データ構造変換手段が、前記ｎ−ｇｒａｍ言語モデルの最高次数の最初のノードの位置（ノードＩＤ）を記憶装置に記憶し、ｎ−ｇｒａｍ言語モデルの構造を表すポインタ表現を、最高次数のｎ−ｇｒａｍを削除した表現に変換するデータ構造変換ステップを、
有することを特徴とする言語モデル圧縮方法。
【請求項８】
請求項７記載の言語モデル圧縮方法において、
圧縮手段が、１−ｇｒａｍの個数Ｎ1を記憶装置に記憶させ、前記データ構造変換手段にて変換したｎ−ｇｒａｍ言語モデルの構造を、スーパーノード（トライ構造のルートノードを指す仮想的なルートノード）および最高次数のｎ−ｇｒａｍに対応したビットをもたないように拡張したＬＯＵＤＳ表現に圧縮変換する圧縮ステップを、
さらに有することを特徴とする言語モデル圧縮方法。
【請求項９】
請求項６記載の言語モデル圧縮方法にて圧縮変換された前記ポインタを記憶する記憶手段を参照して、ｎ−ｇｒａｍ言語モデルにアクセスする方法であって、
第１のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式８により算出して出力するステップと、
【数８】
第２のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式９により算出して出力するステップと、
【数９】
を有することを特徴とする言語モデルのアクセス方法。
【請求項１０】
請求項８に記載の言語モデル圧縮方法にて圧縮変換された前記ポインタを記憶する記憶手段を参照して、ｎ−ｇｒａｍ言語モデルにアクセスする方法であって、
第１のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式１０により算出して出力するステップと、
【数１０】
第２のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式１１により算出して出力するステップと、
【数１１】
を有すること特徴とする言語モデルのアクセス方法。
【請求項１１】
請求項１〜３のいずれか１項に記載の言語モデルの圧縮装置を構成する各手段として、コンピュータを機能させるための言語モデル圧縮プログラム。
【請求項１２】
請求項４または５のいずれか１項に記載の言語モデルのアクセス装置を構成する各手段として、コンピュータを機能させるための言語モデルのアクセスプログラム。
【請求項１】
ｎ個の連続する単語からなる単語列の出現頻度から求めたｎ−ｇｒａｍ言語モデルのモデル表現を圧縮する装置であって、
仮想的なルートノードを設けて、前記ｎ−ｇｒａｍ言語モデルの構造をトライ構造に変換するデータ構造変換手段と、
前記データ構造変換手段にて変換されたトライ構造をＬＯＵＤＳ（Ｌｅｖｅｌ−Ｏｒｄｅｒ Ｕｎａｒｙ Ｄｅｇｒｅｅ Ｓｅｑｕｅｎｃｅ）表現に圧縮変換する圧縮手段と、
を備えることを特徴とする言語モデル圧縮装置。
【請求項２】
ｎ個の連続する単語からなる単語列の出現頻度から求めたｎ−ｇｒａｍ言語モデルのモデル表現を圧縮する装置であって、
前記ｎ−ｇｒａｍ言語モデルの最高次数の最初のノードの位置（ノードＩＤ）を記憶装置に記憶し、ｎ−ｇｒａｍ言語モデルの構造を表すポインタ表現を、最高次数のｎ−ｇｒａｍを削除した表現に変換するデータ構造変換手段を、
備えることを特徴とする言語モデル圧縮装置。
【請求項３】
請求項２記載の言語モデル圧縮装置において、
１−ｇｒａｍの個数Ｎ1を記憶装置に記憶し、前記データ構造変換手段にて変換したｎ−ｇｒａｍ言語モデルの構造を、スーパーノード（トライ構造のルートノードを指す仮想的なルートノード）および最高次数のｎ−ｇｒａｍに対応したビットをもたないように拡張したＬＯＵＤＳ表現に圧縮変換する圧縮手段を、
さらに備えることを特徴とする言語モデル圧縮装置。
【請求項４】
請求項１記載の言語モデル圧縮装置にて圧縮変換された前記ポインタを記憶する記憶手段を参照して、ｎ−ｇｒａｍ言語モデルにアクセスする装置であって、
入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式８により算出して出力する第１のアクセス手段と、
【数８】
入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式９により算出して出力する第２のアクセス手段と、
【数９】
を備えることを特徴とする言語モデルのアクセス装置。
【請求項５】
請求項３に記載の言語モデル圧縮装置にて圧縮変換された前記ポインタを記憶する記憶手段を参照して、ｎ−ｇｒａｍ言語モデルにアクセスする装置であって、
入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式１０により算出して出力する第１のアクセス手段と、
【数１０】
入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式１１により算出して出力する第２のアクセス手段と、
【数１１】
を備えること特徴とする言語モデルのアクセス装置。
【請求項６】
ｎ個の連続する単語からなる単語列の出現頻度から求めたｎ−ｇｒａｍ言語モデルのモデル表現を圧縮する方法であって、
データ構造変換手段が、仮想的なルートノードを設けて、前記ｎ−ｇｒａｍ言語モデルの構造をトライ構造に変換するデータ構造変換ステップと、
圧縮手段が、前記データ構造変換ステップにて変換されたトライ構造をＬＯＵＤＳ（Ｌｅｖｅｌ−Ｏｒｄｅｒ Ｕｎａｒｙ Ｄｅｇｒｅｅ Ｓｅｑｕｅｎｃｅ）表現に圧縮変換する圧縮ステップと、
を有することを特徴とする言語モデル圧縮方法。
【請求項７】
ｎ個の連続する単語からなる単語列の出現頻度から求めたｎ−ｇｒａｍ言語モデルのモデル表現を圧縮する方法であって、
データ構造変換手段が、前記ｎ−ｇｒａｍ言語モデルの最高次数の最初のノードの位置（ノードＩＤ）を記憶装置に記憶し、ｎ−ｇｒａｍ言語モデルの構造を表すポインタ表現を、最高次数のｎ−ｇｒａｍを削除した表現に変換するデータ構造変換ステップを、
有することを特徴とする言語モデル圧縮方法。
【請求項８】
請求項７記載の言語モデル圧縮方法において、
圧縮手段が、１−ｇｒａｍの個数Ｎ1を記憶装置に記憶させ、前記データ構造変換手段にて変換したｎ−ｇｒａｍ言語モデルの構造を、スーパーノード（トライ構造のルートノードを指す仮想的なルートノード）および最高次数のｎ−ｇｒａｍに対応したビットをもたないように拡張したＬＯＵＤＳ表現に圧縮変換する圧縮ステップを、
さらに有することを特徴とする言語モデル圧縮方法。
【請求項９】
請求項６記載の言語モデル圧縮方法にて圧縮変換された前記ポインタを記憶する記憶手段を参照して、ｎ−ｇｒａｍ言語モデルにアクセスする方法であって、
第１のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式８により算出して出力するステップと、
【数８】
第２のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式９により算出して出力するステップと、
【数９】
を有することを特徴とする言語モデルのアクセス方法。
【請求項１０】
請求項８に記載の言語モデル圧縮方法にて圧縮変換された前記ポインタを記憶する記憶手段を参照して、ｎ−ｇｒａｍ言語モデルにアクセスする方法であって、
第１のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、親ノード「（ｎ−１）−ｇｒａｍ」（ｐａｒｅｎｔ）の位置を、式１０により算出して出力するステップと、
【数１０】
第２のアクセス手段が、入力された単語列のｎ−ｇｒａｍの位置ｘに対して、子ノード「（ｎ＋１）−ｇｒａｍ」のうち単語ＩＤの最も小さい子ノード（ｆｉｒｓｔ＿ｃｈｉｌｄ）の位置を、式１１により算出して出力するステップと、
【数１１】
を有すること特徴とする言語モデルのアクセス方法。
【請求項１１】
請求項１〜３のいずれか１項に記載の言語モデルの圧縮装置を構成する各手段として、コンピュータを機能させるための言語モデル圧縮プログラム。
【請求項１２】
請求項４または５のいずれか１項に記載の言語モデルのアクセス装置を構成する各手段として、コンピュータを機能させるための言語モデルのアクセスプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１１−３３８０６（Ｐ２０１１−３３８０６Ａ）
【公開日】平成２３年２月１７日（２０１１．２．１７）
【国際特許分類】
【出願番号】特願２００９−１７９６２５（Ｐ２００９−１７９６２５）
【出願日】平成２１年７月３１日（２００９．７．３１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年２月１７日（２０１１．２．１７）
【国際特許分類】
【出願日】平成２１年７月３１日（２００９．７．３１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]