JP3361564B2 - 高速マッチング方法及び装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、高速マッチング方式に
関し、より詳細には、文字や音声の認識装置などのよう
に、辞書ベクトルと入力ベクトルとのマッチング計算を
行なうようにした高速マッチング方式に関する。

【０００２】

【従来の技術】図１６は、従来の認識装置におけるマッ
チング部のフローチャートを示す図である。一般的に、
入力特徴ベクトルが与えられた場合、大分類処理（step
１）、小分類処理（step２）、詳細分類処理（step３）
を経て認識結果（候補）が求められる。各分類処理には
別々のマッチング辞書と特徴ベクトルが用いられ、入力
ベクトルとのマッチング計算（採用されている認識手法
に依存する）を行ない、計算結果をソーティングして認
識候補を作成する。このように処理を分割している理由
は高速化のためである。一般的に、詳細識別用の認識辞
書は、高認識率の実現のため、より多次元のベクトルを
採用している。そのため、全認識対象カテゴリに対し
て、この詳細分類辞書のみでマッチング計算を行なった
場合、その計算量が莫大となり、速度の低下を生じる。
これを解決するため、従来手法では、より少ない次元数
の特徴ベクトルによる認識辞書（ただし、その認識性能
は低下する）を用いた分類処理により、認識性能が保証
できるまで候補数を減少させ、次の（より多次元辞書を
用いた）分類処理へ送るといった多段階処理により高速
性を実現していた。

【０００３】図１６の従来方式の例では、大分類から詳
細分類へ行くに従い、用いるベクトル次元数は増加す
る。この従来手法の例として、各処理で用いる辞書の１
カテゴリ当たりのベクトル次元数と、入力候補数、出力
候補数、計算量を以下の表１に示す。

【０００４】

【表１】

【０００５】この例は、対象カテゴリ数が５０００の認
識装置（日本語ＯＣＲなど）についてのものであり、詳
細分類辞書のみで計算した場合の計算量１２８００００
（＝２５６×５０００）を３９６８００に減少させてい
る（約１／３）。また従来法では、これと演算方法の簡
略化を組み合わせる方法も行なわれている。例えば、詳
細分類などではマッチング処理にユークリッド距離や類
似度など乗算を必要とする演算を用い、大分類などでは
絶対差などの演算を用いる方法である。一般的には乗算
よりも減算のほうが高速に実行できるため、大分類で高
価な演算を用いるよりも高速化が実現できる。

【０００６】

【発明が解決しようとする課題】前述のように、従来の
マッチング方式では、各分類部において必ず入力候補数
分のマッチング計算を行なう必要があり、劇的な高速化
とはならないという問題点が生じる。例えば、前記表１
の例で、仮に大分類処理で５０００カテゴリ全てに対し
ての計算は行なわず、ある手法により１０００カテゴリ
に対してのみ行なったとすれば、トータルの計算量は１
４０８００となり、約１桁の高速化となる。

【０００７】本発明は、このような実情に鑑みてなされ
たもので、辞書の各カテゴリベクトル間の距離関係が既
知であることを利用し、その距離関係を保存したフラグ
テーブルを各カテゴリ毎に予め求めておき、注目カテゴ
リとのマッチング計算で得られた距離（または類似度）
をもとに、フラグテーブルとの論理演算により、以降の
カテゴリに対して候補となる可能性があるものを決定
し、可能性があると判断されたカテゴリを次の注目カテ
ゴリとし、以降同様の処理を操り返すことにより、可能
性の高いカテゴリのみをマッチング計算することによ
り、高速化を図るようにした高速マッチング方式を提供
することを目的としている。

【０００８】

【課題を解決するための手段】本発明は、上記目的を達
成するために、（１）認識辞書内の辞書カテゴリ毎に設
定された辞書番号に対応し、各辞書カテゴリを１ビット
の情報として表した、すなわち辞書カテゴリ数分のビッ
ト情報を有するバイナリデータを１つのフラグテーブル
とし、辞書カテゴリ毎に、後記類似度合いをある数で分
割した個数だけのフラグテーブルを有するデータ構成に
おいて、予め、全辞書カテゴリのフラグテーブルの全ビ
ットを０に初期化しておき、１つのフラグテーブルと同
じ構成の認識結果フラグを有し、入力ベクトルに対して
認識辞書内の各辞書カテゴリベクトルとの類似度合いを
計算する後記計算手段前に、予め、認識結果フラグの全
ビットを０に初期化しておき、前記辞書カテゴリベクト
ルと照合すべき入力ベクトルに対して、認識辞書内の各
辞書カテゴリベクトルとの類似度合いを計算する計算手
段と、前記計算手段により求められた入力ベクトルと各
辞書カテゴリベクトルとの類似度合いを基にソーティン
グを行い、認識候補を作成する認識候補作成手段と、前
記認識候補に選ばれた各辞書カテゴリの辞書番号に対応
する認識結果フラグのビットを１とし、その他の、すな
わち前記認識候補に選ばれていない、各辞書カテゴリの
辞書番号に対応する認識結果フラグのビットを０とし
て、認識結果フラグを作成するフラグ作成手段と、認識
辞書内の全ての辞書カテゴリを順に走査し、各辞書カテ
ゴリベクトルと前記入力ベクトルに対して前記計算手段
で求めた類似度合いを基に、当該辞書カテゴリの有する
フラグテーブル内の前記類似度合いで選ばれる１つのフ
ラグテーブルを注目フラグテーブルとして決定する注目
フラグテーブル決定手段と、当該注目フラグテーブルと
前記認識結果フラグとの論理和を求めることでフラグテ
ーブルを作成するフラグテーブル作成手段とを有する事
を特徴とし、前記計算手段、認識候補作成手段、フラグ
作成手段、注目フラグテーブル決定手段、およびフラグ
テーブル作成手段を、入力ベクトルに対して実施するこ
とによりフラグテーブルを作成すること、 （２）前記（１）において、前記認識辞書は辞書カテゴ
リ毎に設定された辞書番号順に配置されており、ある辞
書番号の辞書カテゴリは、それより以前の、すなわち当
該辞書カテゴリより辞書番号が小さい全ての辞書カテゴ
リに対して、最も類似度合いが低い辞書カテゴリを選択
し順次並び替えを行う認識辞書並び替え手段を有し、予
め、前記認識辞書並び替え手段により並び替えられた認
識辞書を使用すること、 （３）認識辞書内の辞書カテゴリ毎に設定された辞書番
号に対応し、各辞書カテゴリを１ビットの情報として表
した、すなわち辞書カテゴリ数分のビット情報を有する
バイナリデータを１つのフラグテーブルとし、辞書カテ
ゴリ毎に、後記類似度合いをある数で分割した個数だけ
のフラグテーブルを有するデータ構成において、１つの
フラグテーブルと同じ構成の可能性フラグテーブルを有
し、入力データに対する各認識処理前に、予め、前記可
能性フラグテーブルの全ビットを１に初期化し、入力デ
ータに対して認識用の特徴ベクトルとなる入力ベクトル
を作成する特徴ベクトル作成手段と、入力ベクトルに対
して、認識辞書内の各辞書カテゴリベクトルとの類似度
合いを計算する計算手段と、前記可能性フラグテーブル
の各ビットを順に走査し、当該ビットが１であるかどう
かを判定する計算手段と、前記判定手段においてビット
が１である、すなわち、認識候補となる可能性があると
判断された、当該ビットに対応する辞書カテゴリに対し
て、前記入力ベクトルと辞書カテゴリベクトルとの類似
度合いを前記計算手段で計算し、得られた類似度合いを
基に当該辞書カテゴリの有するフラグテーブル内の前記
類似度合いで選ばれる１つのフラグテーブルを注目フラ
グテーブルとして決定する注目フラグテーブル決定手段
と、前記注目フラグテーブル決定手段により決定された
注目フラグテーブルと、前記可能性フラグテーブルとの
論理積を求め、結果を可能性フラグテーブルに格納する
ことにより可能性フラグテーブルの更新を行う更新手段
とを有することを特徴 とし、前記判定手段、計算手段、
注目フラグテーブル決定手段、更新手段を、可能性フラ
グテーブルの全ビットに対して、すなわち、全ての辞書
カテゴリに対して実施することにより、高速にマッチン
グ処理を行うこと、 （４）認識辞書内の辞書カテゴリ毎に設定された辞書番
号に対応し、各辞書カテゴリを１ビットの情報として表
した、すなわち辞書カテゴリ数分のビット情報を有する
バイナリデータを１つのフラグテーブルとし、辞書カテ
ゴリ毎に、後記類似度合いをある数で分割した個数だけ
のフラグテーブルを有するデータ構成において、予め、
全辞書カテゴリのフラグテーブルの全ビットを０に初期
化しておき、１つのフラグテーブルと同じ構成の認識結
果フラグを有し、入力ベクトルに対して認識辞書内の各
辞書カテゴリベクトルとの類似度合いを計算する後記計
算ステップ前に、予め、認識結果フラグの全ビットを０
に初期化しておき、前記辞書カテゴリベクトルと照合す
べき入力ベクトルに対して、認識辞書内の各辞書カテゴ
リベクトルとの類似度合いを計算する計算ステップと、
前記計算ステップにより求められた入力ベクトルと各辞
書カテゴリベクトルとの類似度合いを基にソーティング
を行い、認識候補を作成する認識候補作成ステップと、
前記認識候補に選ばれた各辞書カテゴリの辞書番号に対
応する認識結果フラグのビットを１とし、その他の、す
なわち前記認識候補に選ばれていない、各辞書カテゴリ
の辞書番号に対応する認識結果フラグのビットを０とし
て、認識結果フラグを作成するフラグ作成ステップと、
認識辞書内の全ての辞書カテゴリを順に走査し、各辞書
カテゴリベクトルと前記入力ベクトルに対して前記計算
ステップで求めた類似度合いを基に、当該辞書カテゴリ
の有するフラグテーブル内の前記類似度合いで選ばれる
１つのフラグテーブルを注目フラグテーブルとして決定
する注目フラグテーブル決定ステップと、当該注目フラ
グテーブルと前記認識結果フラグとの論理和を求めるこ
とでフラグテーブルを作成するフラグテーブル作成ステ
ップとを有する事を特徴とし、前記計算ステップ、認識
候補作成ステップ、フラグ作成ステップ、注目フラグテ
ーブル決定ステップ、およびフラグテーブル作成ステッ
プを、入力ベクトルに対して実施することによりフラグ
テーブルを作成すること、 （５）前記（４）において、前記認識辞書は辞書カテゴ
リ毎に設定された辞書番号順に配置されており、ある辞
書番号の辞書カテゴリは、それより以前の、すなわち当
該辞書カテゴリより辞書番号が小さい全ての辞書カテゴ
リに対して、最も類似度合いが低い辞書カテゴリを選択
し順次並び替えを行う認識辞書並び替えステップを有
し、予め、前記認識辞書並び替えステップにより並び替
えられた認識辞書を使用すること、 （６）認識辞書内の辞書カテゴリ毎に設定された辞書番
号に対応し、各辞書カテゴリを１ビットの情報として表
した、すなわち辞書カテゴリ数分のビット情報を有する
バイナリデータを１つのフラグテーブルとし、辞書カテ
ゴリ毎に、後記類似度合いをある数で分割した個数だけ
のフラグテーブルを有するデータ構成において、１つの
フラグテーブルと同じ構成の可能性フラグテーブルを有
し、入力データに対する各認識処理前に、予め、前記可
能性フラグテーブルの全ビットを１に初期化し、入力デ
ータに対して認識用の特徴ベクトルとなる入力ベクトル
を作成する特徴ベクトル作成ステップと、入力ベクトル
に対して、認識辞書内の各辞書カテゴリベクトルとの類
似度合いを計算する計算ステップと、前記可能性フラグ
テーブルの各ビットを順に走査し、当該ビットが１であ
るかどうかを判定する判定ステップと、前記判定ステッ
プにおいてビットが１である、すなわち、認識候補とな
る可能性があると判断された、当該ビットに対応する辞
書カテゴリに対して、前記入力ベクトルと辞書カテゴリ
ベクトルとの類似度合いを前記計算ステップで計算し、
得られた類似度合いを基に当該辞書カテゴリの有するフ
ラグテーブル内の前記類似度合いで選ばれる１つのフラ
グテーブルを注目フラグテーブルとして決定する注目フ
ラグテーブル決定ステップと、前記注目フラグテーブル
決定ステップにより決定された注目フラグテーブルと前
記可能性フラグテーブルとの論理積を求め、結果を可能
性フラグテーブルに格納することにより可能性フラグテ
ーブルの更新を行う更新ステップとを有することを特徴
とし、前記判定ステップ、計算ステップ、注目フラグテ
ーブル決定ステップ、更新ステップを、可能性フラグテ
ーブルの全ビットに対して、すなわち、全ての辞書カテ
ゴリに対して実施することにより、高速にマッチング処
理を行うこと、 を特徴としたものである。

【０００９】

【作用】本発明は、文字や音声の認識装置において、入
力されたパターン（文字や音声）と、予め備えてある認
識辞書とのマッチング処理を高速に行なうもので、高速
マッチング処理を実現するため、各辞書ベクトル間の距
離関係が既知であることを利用し、その距離関係を保存
したフラグテーブルを各辞書ベクトル毎に予め設定して
おき、入力ベクトルと注目カテゴリベクトルとのマッチ
ング結果（距離や類似度など）をもとにフラグテーブル
を用いた論理演算により、以降のカテゴリに対して、認
識候補としての可能性があるカテゴリ（可能性カテゴ
リ）のみを決定し、次の可能性カテゴリを注目カテゴリ
として、逐次、同様のマッチング処理およびフラグによ
る決定処理を操り返して高速に処理する。

【００１０】

【実施例】実施例について、図面を参照して以下に説明
する。なお、以下の説明においては、簡単なため、マッ
チング計算には通常のユークリッド距離を用いた場合に
ついて説明する。まず、図１２〜図１５に基づいて、視
覚的な方式について説明する。図１２は、辞書ベクトル
と入力ベクトルとの位置関係、図１３は従来方式の計算
例、図１４は本発明方式の第１カテゴリとの計算結果と
可能性カテゴリ、図１５は本発明方式の第２カテゴリと
の計算結果と可能性カテゴリを各々示している。以下、
順次説明する。

【００１１】図１２は、辞書の各カテゴリベクトルと入
力ベクトルとの位置関係を２次元平面上にプロットした
ものである（カテゴリベクトルは〇で、入力ベクトルは
◎で表示）。従来手法では、図１３のように、入力ベク
トルと全ての各カテゴリベクトルとの距離計算を行な
い、それらをソーティング（距離の小さいものから並べ
換えて）して認識候補を求める。なぜ全てのカテゴリベ
クトルに対して距離計算するかというと、それは入力ベ
クトルが未知であるため、各辞書ベクトルとの距離関係
が不明であるためである。しかし、入力ベクトルは未知
であっても、各カテゴリベクトル間の位置関係は既知で
ある。本発明の方式ではこのことを利用し、まず、図１
４に示すように、辞書の第１カテゴリとの距離計算結果
をもとに、可能性のあるカテゴリ（入力ベクトルが第１
カテゴリに近ければ近いカテゴリ、遠ければ遠いカテゴ
リ）を選び、それらのうち１つを第２カテゴリとする。
次に、図１５に示すように、この第２カテゴリとの距離
計算結果をもとに、まだマッチング計算を行なっていな
く、かつ第１カテゴリでの計算結果から可能性があると
判定されたものの中から、再び可能性のあるカテゴリを
決定する。以降、この処理を操り返すことにより、可能
性のあるカテゴリのみをマッチング処理し、高速にマッ
チング処理を行なう。図１４及び図１５は、本発明の方
式での第１カテゴリにより処理結果と、第２カテゴリに
よる処理結果である。可能性のあるカテゴリは図の斜線
カテゴリとなる。

【００１２】次に、本発明の高速マッチング方式に用い
るフラグテーブルの構成と作成方法について説明する。
フラグテーブルは辞書のカテゴリ番号に対応したバイナ
リーテーブルである。各ビットが辞書の各カテゴリに対
応し、ビット値が１ならば可能性があり、０ならば可能
性なしとして作成したテーブルである。

【００１３】

【表２】

【００１４】表２は、日本語ＯＣＲのフラグテーブルの
例である。このフラグテーブルからは、国、田、困、
口、団などのカテゴリが可能性のあるカテゴリとして選
択される。１つのフラグテーブルは認識対象カテゴリ−
ビット分の容量が必要となる。従って、そのメモリ容量
（バイト数）はカテゴリ数÷８で概算できる。例えば、
５０００カテゴリのものであれば、１つのフラグテーブ
ルは６２５バイトとなる。本発明ではまず、マッチング
計算により求められる距離を均等の範囲ごとにｍ個に分
割し、辞書の１カテゴリ当たり、その個数分（ｍ個）フ
ラグテーブルを用意する。最大距離を１０００、分割数
ｍを１０とした場合の、１カテゴリ当たりのフラグテー
ブル構成例を以下の表３に示す。

【００１５】

【表３】

【００１６】この最大距離は用いる特徴ベクトルの次元
数や正規化手法などにより異なってくる。また、分割数
ｍはより大きくとれば、各カテゴリ間の距離関係の最良
近似となるが、メモリ容量も増加するので、システムに
より随意に決定されるものである。あるシステムでは、
特徴ベクトルに対してある種の正規化処理を施こしてな
いものがある（かもしれない）。この場合論理的には、
最大距離の設定ができないが、実験により（頻度情報な
どをもとに）最大距離を設定し、それをｍ個に分割し、
ｍ＋１個の範囲として「最大距離以上」を設定すること
により、本発明の方式を適用することができる。

【００１７】次に、辞書カテゴリの並び換えについて説
明する。フラグテーブルを作成する前に、辞書カテゴリ
の並び換えを行なう。この理由は、本発明ではある注目
カテゴリと入力ベクトルとの距離により、以降の可能性
カテゴリの決定を行なうため、辞書カテゴリの並びで、
カテゴリ間の距離が近いベクトル（例えば０とｏなどの
類似文字）が連続している場合、可能性カテゴリ判定が
効果的に機能しないためである。これを解決するため、
本発明では、以前のカテゴリに対して最も遠いカテゴリ
ベクトルを順に並べていく方法で、辞書の各カテゴリベ
クトルを並び換える。

【００１８】図１は、本発明の高速マッチング方式の辞
書並び換えのブロック図で、図中、１は辞書並び換え処
理部、２は平均ベクトル作成部、３は最近傍カテゴリ決
定部、４はカテゴリベクトルコピー部、５はコピーフラ
グ制御部、６は辞書並び換え制御部、７は平均ベクトル
バッファ、８は入力辞書バッファ、９は結果辞書バッフ
ァ、１０は結果辞書カウンタ、１１は選択番号バッフ
ァ、１２は入力辞書カウンタ、１３は最大累積距離バッ
ファ、１４は累積距離バッファ、１５はカウンタ、１６
は距離バッファ、１７はカテゴリ選択制御部、１８はカ
テゴリ選択処理部である。

【００１９】図２（ａ),(ｂ）は、入力辞書及び結果辞
書の各々の構成図である。図３は辞書並び換えのフロー
チャートである。以下、各ステップに従って順に説明す
る。なおフローチャート中の記号の意味は、以下の表４
のとおりである。

【００２０】

【表４】

【００２１】step１：まず、入力辞書の全カテゴリック
ベクトルのコピーフラグ（既に結果辞書バッファへコピ
ーしたかを示すフラグ）を０クリアする。step２ ：入力辞書の全カテゴリベクトルで平均ベクトル
を求める。step３，４ ：平均ベクトルに最も近い入力辞書のカテゴ
リベクトルを求め（最近傍カテゴリ）、それを第１カテ
ゴリとして、結果バッファの第１番目にコピーする。こ
の時、第１カテゴリに選択された入力辞書カテゴリのコ
ピーフラグを１にする。step５ ：結果辞書カウンタを１に初期化する。step６ ：結果辞書カウンタの値が認識対象カテゴリ数で
あるかチェックする。もし、認識対象カテゴリ数であれ
ば辞書並び換え処理を終了する。

【００２２】step７：全てのコピーフラグが０（まだ、
結果辞書にコピーされていない）カテゴリの中で、既に
コピー済の結果辞書の各カテゴリに対して、最も遠いカ
テゴリを次カテゴリとして選択する（選択フローヘ）。step８ ：次カテゴリを結果辞書にコピーし、対応する入
力辞書のコピーフラグを１にする。step９ ：結果辞書カウンタをインクリメントする。 以降、同様の処理を全ての入力辞書カテゴリが、結果辞
書にコピーされるまで（結果辞書カウンタが認識対象カ
テゴリとなるまで）操り返す。

【００２３】図４は、カテゴリ選択のフローチャートで
ある。以下、各ステップに従って順に説明する。なお、
フローチャート中の記号の意味は、以下の表５のとおり
である。

【００２４】

【表５】

【００２５】step１，２：制御に必要な入力辞書カウン
タと最大累積距離バッファを０クリアする。step３，４ ：入力辞書カテゴリの中で、コピーフラグが
０のものを探す。step５〜１０ ：評価に用いる累積距離バッファを０クリ
アし、この入力カテゴリベクトルと、（既にコピー済み
の）結果辞書の各カテゴリ間で距離を計算し、求められ
た距離を累積距離バッファに加算していく。step１１〜１４ ：最大累積距離バッファとこの累積距離
バッファの内容を比較し、累積距離バッファの方が小さ
ければ、次の入力辞書カテゴリの走査へ移る。もし、累
積距離バッファの方が大きければ、その内容を最大累積
距離バッファへコピーし、選択番号バッファに現在の入
力辞書カテゴリ番号（入力辞書カウンタの内容）をコピ
ーする。 以降、同様の処理を全ての入力辞書カテゴリに対して行
ない、最終的に選択番号バッファに格納されている番号
が、次の結果辞書へコピーされるカテゴリ番号となる。

【００２６】次に、フラグテーブルの作成方法について
説明する。フラグテーブルは実験的に作成し、作成に用
いられる入力データは、辞書作成に用いられる大量で多
類の特徴ベクトルである。図５は、フラグテーブル作成
部のブロック図で、図中、２１はフラグテーブル作成処
理部、２２は距離計算部、２３はソーティング部、２４
は認識結果フラグ設定部、２５は注目フラグ決定部、２
６は注目フラグ更新部、２７はフラグテーブル作成制御
部、２８は入力特徴データバッファ部、２９は距離バッ
ファ、３０は認識結果（修補）バッファ、３１は認識結
果フラグバッファ、３２は認識結果バッファ、３３はカ
テゴリカウンタである。

【００２７】図６（ａ）〜（ｃ）は、認識結果フラグ、
認識辞書、フラグテーブル部の各々の構成図である。図
７は、フラグテーブル作成のフローチャートである。以
下、各ステップに従って順に説明する。なお、フロチャ
ート中の記号の意味は、以下の表６のとおりである。

【００２８】

【表６】

【００２９】step１：まず、辞書の全てのフラグテーブ
ルを０クリアする。step２〜４ ：入力データに対して、各辞書カテゴリベク
トルとの距離計算（この演算には採用される認識手法を
用いる）を行なった後、ソーティングにより認識候補を
作成する。この処理は通常のマッチング処理をそのまま
用いる。従って、ソーティングにより選ばれる候補数も
従来から採用している（あるいはその辞書により認識性
能が保証される）数を用いる。この時、各辞書べクトル
との距離は距離バッファに格納される。step５，６ ：ソーティング結果をもとに、認識候補とし
て選ばれた候補番号に対応するビットを１、認識候補外
を０として、認識結果フラグを作成する。この認識結果
フラグは、表２のフラグテーブルと同様の構成でカテゴ
リ数分のバイナリーデータである。

【００３０】step７，８：これらのデータ設定終了後、
各辞書カテゴリ毎にフラグテーブルの作成を行なう。ま
ず、順次辞書カテゴリを注目カテゴリとし、結果バッフ
ァに格納された距離をもとに１カテゴリ当たりの複数の
フラグテーブル（表３）の中から範囲に該当するフラグ
テーブルを決定し、それを注目フラグテーブルとする。 step９，１０ ：このフラグテーブルと認識結果フラグと
の論理和（ＯＲ）を求め、論理和結果をこの注目フラグ
テーブルの値として格納する（フラグテーブルの更新処
理：表７）。 以降、同様の処理を入力ベクトルがなくなるまで操り返
す。

【００３１】

【表７】

【００３２】この処理の結果、求められたフラグテーブ
ルは、あるカテゴリベクトルに対して、入力ベクトルと
の距離が求められた場合、最終的に候補として採用され
るべきカテゴリ位置のビットが１となったバイナリーデ
ータで、距離が小さい範囲のフラグテーブルは、そのカ
テゴリベクトルに近いカテゴリが１でその他は０とな
り、ある程度距離が大きい範囲のフラグテーブルは、そ
の距離に対応したカテゴリの位置が１となり、非常に近
いカテゴリや遠いカテゴリに対しては０となっている。
この情報は既知の辞書の各カテゴリベクトル間の距離関
係を保存したものであり、本発明の重要な要素は、この
情報に保存しつつ、学習ベクトル（フラグテーブル作成
に用いた特徴ベクトル）に対しては、認識性能の低下が
論理的に発生しないことである。従って、距離関係の保
存の他、学習ベクトルに対する認識性能も完全に保存さ
れている。

【００３３】次に、高速マッチング方法について説明す
る。図８は、高速マッチング処理のブロック図で、図
中、４１は距離計算部、４２はフラグテーブル判定部、
４３は高速マッチング制御部、４４は距離バッファ、４
５は可能性フラグテーブル、４６はカテゴリカウンタ、
４７は入力特徴ベクトル、４８は認識辞書、４９は注目
フラグテーブル番号バッファ、５０は先頭アドレスレジ
スタ、５１は終了アドレスレジスタ、５２はカウンタ、
５３は論理演算部、５４は更新制御部である。

【００３４】図９（ａ）〜（ｃ）は、可能性フラグテー
ブル、認識辞書、フラグテーブル部の各々の構成図であ
る。図１０は、高速マッチング処理のフローチャートで
ある。以下、各ステップに従って順に説明する。なおフ
ローチャート中の記号の意味は、次の表８のとおりであ
る。

【００３５】

【表８】

【００３６】step１，２：最初に可能性フラグテーブル
の全ビットを１にセットする。この司能性フラグテーブ
ルは、表２のフラグテーブルと同様の構成であり、各ビ
ット位置が辞書の各カテゴリ番号に対応している。カテ
ゴリカウンタを０に初期化する。step３，４ ：カテゴリカウンタで示される可能性フラグ
テーブルのビットが１か（そのカテゴリをマッチング計
算してよいか）どうかを判定する。もし０ならば、マッ
チング処理を行なわず、カデゴリカウンタのインクメン
トを行ない、次の辞書のカテゴリへ処理を進める。step５ ：可能性フラグテーブルのビットが１の場合、そ
の辞書カテゴリベクトルと入力ベクトルとの距離計算を
行なう。step６ ：求められた距離をもとに、その辞書カテゴリの
注目のフラグテーブルを決定する。

【００３７】step７：この注目フラグテーブルと可能性
フラグテーブルとの論理積（ＡＮＤ）を求め、その結果
を可能性フラグテーブルへコピーする（可能性フラグテ
ーブル更新処理：後述）。step８ ：カテゴリカウンタをインクリメントし、次の辞
書カテゴリへ処理を進める。 以降、同様の処理をカテゴリカウンタが認識対象カテゴ
リ数となるまで操り返す。以上の処理により、注目のカ
テゴリにより計算された距離をもとに、以降の可能性の
あるカテゴリの決定を遂次行ない、無駄なカテゴリとの
マッチング計算をパスすることにより、高速マッチング
処理を実現できる。

【００３８】最後に、可能性フラグの更新処理を説明す
る。可能性フラグは、注目フラグとの論理積（ＡＮＤ）
により遂時更新される。前述した、高速マッチング処理
動作においては、この論理積範囲はフラグの全て（認識
対象カテゴリビット数分）であってもかまわない。しか
し、更新された可能性フラグの必要範囲は、現カテゴリ
番号以降の範囲である。従って、更新処理の論理積（Ａ
ＮＤ）処理もその範囲のみで行なえばよいことになる。
この範囲を限定した更新処理の説明を行なう。フラグテ
ーブルは、バイナリーデータであるので、通常はカテゴ
リ数÷８で概算できるバイト数のデータである。論理演
算はバイト単位で行なえるので、更新処理の論理積（Ａ
ＮＤ）もバイト単位で行なう。このバイト単位の処理は
メモリアクセス長の問題であるので、システムにより１
６ビットまたは３２ビットなどのアクセスが可能の場
合、本発明と同様に処理できる。またアクセス幅が大き
くなるほど処理は高速となる。

【００３９】図１１は、可能性フラグテーブル更新のフ
ローチャートである。以下、各ステップに従って順に説
明する。なお、フローチャート中の記号の意味は、以下
の表９のとおりである。

【００４０】

【表９】

【００４１】step１：まず、現カテゴリ番号により、フ
ラグの先頭バイトアドレスを計算し（これはカテゴリ番
号÷８で求められる）、アドレスカウンタに代入する。step２〜５ ：アドレスカウンタで示される可能性フラグ
のバイトデータと注目フラグのバイトデータの論理積
（ＡＮＤ）演算を行ない、結果を可能性フラグに代入す
る。同様にアドレスカウンタが終了となるまで操り返
す。 この処理により、高速マッチング処理に必要な範囲のみ
の可能性フラグの更新が行なえる。

【００４２】次に、距離尺度以外のマッチング手法の適
用について説明する。本発明は、通常の絶対差距離やユ
ーリッド距離など、全ての距離尺度を用いたマッチング
手法を採用しているものに対して有効である。この他、
認識装置には類似度なる尺度も多く採用されている。類
似度（Ｓ）は以下の通りの数１の計算式で求められる。

【００４３】

【数１】

【００４４】これは単に２つのベクトルの内積値をそれ
ぞれのべクトルのノルムで正規化していることで、各ベ
クトルのノルムを１に正規化した次の数２の（２）式と
等価になる。

【００４５】

【数２】

【００４６】このベクトルを用いたユークリッド距離
（Ｄ）を考えると、以下の数３の（３）式となる。

【００４７】

【数３】

【００４８】結局、類似度とユークリッド距離とは等価
（裏表）な関係にある。従って、類似度法に対しても本
発明の適用は可能となる。

【００４９】このように、本発明は、高速マッチング処
理に使用するための、辞書の各カテゴリベクトルの距離
関係を保存したフラグテーブルの構成とその作成方法で
あり、以下の点を特徴としている。 （１）１つのフラグテーブルは辞書の各カテゴリ番号に
対応したバイナリーデータであり、フラグテーブルのビ
ット値が１の場合は、対応するカテゴリが候補となる可
能性あり（マッチング処理する必要あり）、ビット値が
０の場合は、対応するカテゴリ候補となる可能性なし
（マッチング処理の必要なし）と意味付けられたもので
ある。 （２）１カテゴリ当たりのフラグテーブルの構成は、認
識手法に用いられる尺度（距離など）の最大値をある分
割数で分割し、分割された各距離範囲に対応した意味付
けのフラグテーブルを、分割した個数個備えたもので構
成されており、入力ベクトルと注目カテゴリとのマッチ
ング計算結果（距離など）により、注目カテゴリの注目
フラグテーブルが１つ決定できる構成である。

【００５０】（３）本発明を効果的に動作させるため、
フラグテーブル作成前に、以前に決定された辞書の各カ
テゴリベクトルに対して、最も遠い関係にあるものから
順番に、辞書のカテゴリベクトルを並び換える操作を行
なう。 （４）辞書作成に用いた多種大量の特徴ベクトルを入力
データとし、採用されているマッチング手法と候補数を
もとに、それぞれマッチング処理とソーティング処理の
結果得られた認識結果候補と、辞書の各カテゴリベクト
ルとのマッチング結果（距離など）をもとに、各カテゴ
リの対応する注目フラグテーブルの更新処理を、入力特
徴ベクトルがなくなるまで操り返すことにより、各カテ
ゴリベクトルの距離関係を保存したフラグテーブルを作
成する方法である。

【００５１】また、辞書の各カテゴリベクトルの距離関
係を保存したフラグテーブルを用いて、高速にマッチン
グ処理する方法であり、以下の点を特徴としている。 （１）１つのフラグテーブルと同様の構成をした可能性
フラクテーブルを備え、マッチング処理前にそれの全ビ
ット値を１に初期化する。 （２）カテゴリカウンタで示されるカテゴリに対応した
可能性フラグビット値が１つであるか判定することによ
り、マッチング処理すべき注目カテゴリを決定する。 （３）入力ベクトルとその注目カテゴリに対して、採用
されているマッチング計算を行ない、計算結果（距離な
ど）をもとに、注目カテゴリ注目フラグテーブルを決定
する。

【００５２】（４）その注目フラグテーブルと可能性フ
ラグテーブルに対して、現カテゴリカウンタ以降のビッ
トデータに対してのみ、論理演算を用いて可能性フラグ
テーブルの更新を行なう。 （５）以降、カテゴリカウンタが認識対象カテゴリ数と
なるまで、同様の処理を操り返すことにより、可能性の
あるカテゴリベクトルとのみマッチング計算を行なうこ
とで、高速にマッチング処理を行なう。

【００５３】

【発明の効果】以上の説明から明らかなように、本発明
によると、以下のような効果である。すなわち、本発明
は文字や音声の認識装置において、入力されたパターン
（文字や音声）と、予め備えてある認識辞書とのマッチ
ング処理を高速に行なう方法である。本発明では高速マ
ッチング処理を実現するため、各辞書ベクトル間の距離
関係が既知であることを利用し、その距離関係を保存し
たフラグテーブルを各辞書ベクトル毎に予め設定してお
き、入力ベクトルと注目カテゴリベクトルとのマッチン
グ結果（距離や類似度など）をもとにフラグテーブルを
用いた論理演算により、以降カテゴリに対して、認識候
補としての可能性があるカテゴリ（可能性カテゴリ）の
みを決定し、次の可能性カテゴリを注目カテゴリとし
て、遂次、同様のマッチング処理およびフラグによる決
定処理を操り返し高速に処理することができる。

【図面の簡単な説明】

【図１】本発明による高速マッチング方式の辞書並び換
え処理部の一実施例を説明するための構成図である。

【図２】図１における入力辞書及び結果辞書の構成図で
ある。

【図３】本発明による高速マッチング方式の辞書並び換
え処理のフローチャートである。

【図４】本発明による高速マッチング方式のカテゴリ選
択処理のフローチャートである。

【図５】本発明による高速マッチング方式のフラグテー
ブル作成部の構成図である。

【図６】図５における認識結果フラグ，認識辞書，フラ
グテーブル部の構成図である。

【図７】本発明による高速マッチング方式のフラグテー
ブル作成処理のフローチャートである。

【図８】本発明による高速マッチング方式の高速マッチ
ング処理部の構成図である。

【図９】図８における可能性フラグテーブル，認識辞
書，フラグテーブル部の構成図である。

【図１０】本発明による高速マッチング方式の高速マッ
チング処理部のフローチャートである。

【図１１】本発明による高速マッチング方式の可能性フ
ラグテーブル更新処理のフローチャートである。

【図１２】本発明の辞書ベクトルと入力ベクトルとの位
置関係を示す図である。

【図１３】本発明を説明するための従来方式の計算例を
示す図である。

【図１４】本発明の第１カテゴリとの計算結果と可能性
カテゴリを示す図である。

【図１５】本発明の第２カテゴリとの計算結果と可能性
カテゴリを示す図である。

【図１６】従来のマッチング処理のフローチャートであ
る。

【符号の説明】

１…辞書並び換え処理部、２…平均ベクトル作成部、３
…最近傍カテゴリ決定部、４…カテゴリベクトルコピー
部、５…コピーフラグ制御部、６…辞書並び換え制御
部、７…平均ベクトルバッファ、８…入力辞書バッフ
ァ、９…結果辞書バッファ、１０…結果辞書カウンタ、
１１…選択番号バッファ、１２…入力辞書カウンタ、１
３…最大累積距離バッファ、１４…累積距離バッファ、
１５…カウンタ、１６…距離バッファ、１７…カテゴリ
選択制御部、１８…カテゴリ選択処理部。

───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06T 7/00 - 7/60 G06K 9/62 - 9/82 G10L 15/00 - 17/00 ＪＩＣＳＴファイル（ＪＯＩＳ)

Claims (6)

(57)【特許請求の範囲】
1. 【請求項１】 認識辞書内の辞書カテゴリ毎に設定され
   た辞書番号に対応し、各辞書カテゴリを１ビットの情報
   として表した、すなわち辞書カテゴリ数分のビット情報
   を有するバイナリデータを１つのフラグテーブルとし、 辞書カテゴリ毎に、後記類似度合いをある数で分割した
   個数だけのフラグテーブルを有するデータ構成におい
   て、予め、全辞書カテゴリのフラグテーブルの全ビット
   を０に初期化しておき、 １つのフラグテーブルと同じ構成の認識結果フラグを有
   し、入力ベクトルに対して認識辞書内の各辞書カテゴリ
   ベクトルとの類似度合いを計算する後記計算手段前に、
   予め、認識結果フラグの全ビットを０に初期化してお
   き、 前記辞書カテゴリベクトルと照合すべき入力ベクトルに
   対して、認識辞書内の各辞書カテゴリベクトルとの類似
   度合いを計算する計算手段と、 前記計算手段により求められた入力ベクトルと各辞書カ
   テゴリベクトルとの類似度合いを基にソーティングを行
   い、認識候補を作成する認識候補作成手段と、 前記認識候補に選ばれた各辞書カテゴリの辞書番号に対
   応する認識結果フラグのビットを１とし、その他の、す
   なわち前記認識候補に選ばれていない、各辞書カテゴリ
   の辞書番号に対応する認識結果フラグのビットを０とし
   て、認識結果フラグを作成するフラグ作成手段と、 認識辞書内の全ての辞書カテゴリを順に走査し、各辞書
   カテゴリベクトルと前記入力ベクトルに対して前記計算
   手段で求めた類似度合いを基に、当該辞書カテゴリの有
   するフラグテーブル内の前記類似度合いで選ばれる１つ
   のフラグテーブルを注目フラグテーブルとして決定する
   注目フラグテーブル決定手段と、 当該注目フラグテーブルと前記認識結果フラグとの論理
   和を求めることでフラグテーブルを作成するフラグテー
   ブル作成手段とを有する事を特徴とし、 前記計算手段、認識候補作成手段、フラグ作成手段、注
   目フラグテーブル決定手段、およびフラグテーブル作成
   手段を、入力ベクトルに対して実施することによりフラ
   グテーブルを作成するフラグテーブル作成装置。
2. 【請求項２】 前記認識辞書は辞書カテゴリ毎に設定さ
   れた辞書番号順に配置されており、ある辞書番号の辞書
   カテゴリは、それより以前の、すなわち当該 辞書カテゴ
   リより辞書番号が小さい全ての辞書カテゴリに対して、
   最も類似度合いが低い辞書カテゴリを選択し順次並び替
   えを行う認識辞書並び替え手段を有し、予め、前記認識
   辞書並び替え手段により並び替えられた認識辞書を使用
   することを特徴とした請求項１記載のフラグテーブル作
   成装置。
3. 【請求項３】 認識辞書内の辞書カテゴリ毎に設定され
   た辞書番号に対応し、各辞書カテゴリを１ビットの情報
   として表した、すなわち辞書カテゴリ数分のビット情報
   を有するバイナリデータを１つのフラグテーブルとし、 辞書カテゴリ毎に、後記類似度合いをある数で分割した
   個数だけのフラグテーブルを有するデータ構成におい
   て、 １つのフラグテーブルと同じ構成の可能性フラグテーブ
   ルを有し、入力データに対する各認識処理前に、予め、
   前記可能性フラグテーブルの全ビットを１に初期化し、 入力データに対して認識用の特徴ベクトルとなる入力ベ
   クトルを作成する特徴ベクトル作成手段と、 入力ベクトルに対して、認識辞書内の各辞書カテゴリベ
   クトルとの類似度合いを計算する計算手段と、 前記可能性フラグテーブルの各ビットを順に走査し、当
   該ビットが１であるかどうかを判定する計算手段と、 前記判定手段においてビットが１である、すなわち、認
   識候補となる可能性があると判断された、当該ビットに
   対応する辞書カテゴリに対して、前記入力ベクトルと辞
   書カテゴリベクトルとの類似度合いを前記計算手段で計
   算し、得られた類似度合いを基に当該辞書カテゴリの有
   するフラグテーブル内の前記類似度合いで選ばれる１つ
   のフラグテーブルを注目フラグテーブルとして決定する
   注目フラグテーブル決定手段と、 前記注目フラグテーブル決定手段により決定された注目
   フラグテーブルと、前記可能性フラグテーブルとの論理
   積を求め、結果を可能性フラグテーブルに格納すること
   により可能性フラグテーブルの更新を行う更新手段とを
   有することを特徴とし、 前記判定手段、計算手段、注目フラグテーブル決定手
   段、更新手段を、可能性フ ラグテーブルの全ビットに対
   して、すなわち、全ての辞書カテゴリに対して実施する
   ことにより、高速にマッチング処理を行う高速マッチン
   グ処理装置。
4. 【請求項４】 認識辞書内の辞書カテゴリ毎に設定され
   た辞書番号に対応し、各辞書カテゴリを１ビットの情報
   として表した、すなわち辞書カテゴリ数分のビット情報
   を有するバイナリデータを１つのフラグテーブルとし、 辞書カテゴリ毎に、後記類似度合いをある数で分割した
   個数だけのフラグテーブルを有するデータ構成におい
   て、予め、全辞書カテゴリのフラグテーブルの全ビット
   を０に初期化しておき、 １つのフラグテーブルと同じ構成の認識結果フラグを有
   し、入力ベクトルに対して認識辞書内の各辞書カテゴリ
   ベクトルとの類似度合いを計算する後記計算ステップ前
   に、予め、認識結果フラグの全ビットを０に初期化して
   おき、 前記辞書カテゴリベクトルと照合すべき入力ベクトルに
   対して、認識辞書内の各辞書カテゴリベクトルとの類似
   度合いを計算する計算ステップと、 前記計算ステップにより求められた入力ベクトルと各辞
   書カテゴリベクトルとの類似度合いを基にソーティング
   を行い、認識候補を作成する認識候補作成ステップと、 前記認識候補に選ばれた各辞書カテゴリの辞書番号に対
   応する認識結果フラグのビットを１とし、その他の、す
   なわち前記認識候補に選ばれていない、各辞書カテゴリ
   の辞書番号に対応する認識結果フラグのビットを０とし
   て、認識結果フラグを作成するフラグ作成ステップと、 認識辞書内の全ての辞書カテゴリを順に走査し、各辞書
   カテゴリベクトルと前記入力ベクトルに対して前記計算
   ステップで求めた類似度合いを基に、当該辞書カテゴリ
   の有するフラグテーブル内の前記類似度合いで選ばれる
   １つのフラグテーブルを注目フラグテーブルとして決定
   する注目フラグテーブル決定ステップと、当該注目フラ
   グテーブルと前記認識結果フラグとの論理和を求めるこ
   とでフラグテーブルを作成するフラグテーブル作成ステ
   ップとを有する事を特徴とし、 前記計算ステップ、認識候補作成ステップ、フラグ作成
   ステップ、注目フラグテーブル決定ステップ、およびフ
   ラグテーブル作成ステップを、入力ベクトルに対して実
   施することによりフラグテーブルを作成するフラグテー
   ブル作成方法。
5. 【請求項５】 前記認識辞書は辞書カテゴリ毎に設定さ
   れた辞書番号順に配置されており、ある辞書番号の辞書
   カテゴリは、それより以前の、すなわち当該辞書カテゴ
   リより辞書番号が小さい全ての辞書カテゴリに対して、
   最も類似度合いが低い辞書カテゴリを選択し順次並び替
   えを行う認識辞書並び替えステップを有し、予め、前記
   認識辞書並び替えステップにより並び替えられた認識辞
   書を使用することを特徴とした請求項４記載のフラグテ
   ーブル作成方法。
6. 【請求項６】 認識辞書内の辞書カテゴリ毎に設定され
   た辞書番号に対応し、各辞書カテゴリを１ビットの情報
   として表した、すなわち辞書カテゴリ数分のビット情報
   を有するバイナリデータを１つのフラグテーブルとし、 辞書カテゴリ毎に、後記類似度合いをある数で分割した
   個数だけのフラグテーブルを有するデータ構成におい
   て、 １つのフラグテーブルと同じ構成の可能性フラグテーブ
   ルを有し、入力データに対する各認識処理前に、予め、
   前記可能性フラグテーブルの全ビットを１に初期化し、 入力データに対して認識用の特徴ベクトルとなる入力ベ
   クトルを作成する特徴ベクトル作成ステップと、 入力ベクトルに対して、認識辞書内の各辞書カテゴリベ
   クトルとの類似度合いを計算する計算ステップと、 前記可能性フラグテーブルの各ビットを順に走査し、当
   該ビットが１であるかどうかを判定する判定ステップ
   と、 前記判定ステップにおいてビットが１である、すなわ
   ち、認識候補となる可能性があると判断された、当該ビ
   ットに対応する辞書カテゴリに対して、前記入力ベクト
   ルと辞書カテゴリベクトルとの類似度合いを前記計算ス
   テップで計算し、得られた類似度合いを基に当該辞書カ
   テゴリの有するフラグテーブル内の前記類似度合いで選
   ばれる１つのフラグテーブルを注目フラグテーブルとし
   て決定する注目フラグテーブル決定ステップと、 前記注目フラグテーブル決定ステップにより決定された
   注目フラグテーブルと前記可能性フラグテーブルとの論
   理積を求め、結果を可能性フラグテーブルに格納するこ
   とにより可能性フラグテーブルの更新を行う更新ステッ
   プとを有すること を特徴とし、 前記判定ステップ、計算ステップ、注目フラグテーブル
   決定ステップ、更新ステップを、可能性フラグテーブル
   の全ビットに対して、すなわち、全ての辞書カテゴリに
   対して実施することにより、高速にマッチング処理を行
   う高速マッチング処理方法。