JPH09245045A - 鍵検索方法および装置 - Google Patents

Abstract

(57)【要約】 【課題】鍵が、木構造を構築する指標となる属性とは別
に、グループに分類されていたり、順序関係を持つ属性
を持っている場合に、そのグループ情報や属性の範囲を
もとに探索の範囲を限定して、効率のよい探索を実現す
る。 【解決手段】グループ毎にそのグループに対応するラベ
ルを用意することとし、木構造を構築する際に木構造の
各ノード又は各アークに対して、そのノード又はアーク
より末端方向に存在する葉に対応するすべての鍵のグル
ープに対応するラベルを付与しておくように構成する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、辞書やデータベー
ス検索その他の鍵検索の方法および装置に関する。特
に、各鍵が木構造を構築する指標となる属性とは別に、
グループに分類されていたり、順序関係を持つ属性を持
っている場合に、そのグループ情報や属性の範囲をもと
に探索の範囲を限定して、効率のよい探索を実現する鍵
探索方式に関する。

【０００２】

【従来の技術】２進木、Ｂ−ｔｒｅｅ、トライ（Ｔｒｉ
ｅ）などの木構造を利用して高速に鍵探索をする技術が
ある。これらの技術は例えば、渋谷政昭、山本毅雄共著
「岩波講座情報科学１１データ管理算法」に記載されて
いる。また、特開平３−１２２７６６号公報におけるそ
の背景技術に記載されている。

【０００３】これらの技術では、あらかじめ検索対象と
なる鍵をある属性の順序関係によって木構造としてまと
めておく。鍵を探索するときには、根ノードから検索す
る鍵に従って葉の方向へ枝をたどり、目的となる鍵に対
応する葉があれば検索している鍵が鍵として登録されて
いることを示し、対応する葉がなければ検索している鍵
が鍵として登録されていないことを示す。鍵として登録
されている場合には、必要に応じて葉にのっている鍵に
関する情報を読みだして目的を達成する。

【０００４】

【発明が解決しようとする課題】検索しようとする鍵が
木構造を構成する指標となる属性とは別の属性を持ち、
その属性がグループに分類されていて、目的とする鍵の
属するグループが限定されている状況がある。例えば単
語辞書において、表記や読みに基づいて木構造を構成し
ておき、その単語の品詞という属性を持っている場合で
ある。この場合、名詞という限定された条件下で検索を
することが上記状況の一例である。

【０００５】また、鍵が木構造を構築するときの属性と
は別の順序関係を持つ属性を持っていて、検索の対象と
なる属性の順序関係の範囲が限定されている状況なども
ある。例えば、上記の単語辞書において、各単語が重要
度という数字で表現される属性を持っている場合であ
る。この場合、ある重要度以上の単語を検索するという
ような状況がこれに相当する。

【０００６】これらの状況において、従来の木構造を利
用した検索ではたとえ対象となる属性が限定されていて
も、検索に成功してその鍵の属性を読みだした後でない
と、属性が条件を満たしているか否かが判定できない。
従って、探索の条件が限定されていても、それを利用し
て探索範囲を絞り込むことができないので、条件を満た
さない鍵しか属していない枝をも探索する無駄が生じて
しまう。これは、探索時間を増大させる原因となる。

【０００７】一方、上記の無駄を避けるためにグループ
毎に別の木を作成して、該当するグループの木だけを検
索する方法が考えられる。しかし、検索の対象としてい
るグループが複数ある場合には該当する木をすべて検索
する必要が生じる。この場合には枝をたどるときの条件
判定において、同じ判定を何度も行う必要が生じてしま
う。特に、グループを全く特定しない一般的な場合にお
いては、複数あるすべての木を探索する必要が生じてし
まう。従って、探索効率が低下するのは避けられない。

【０００８】また、鍵がグループに分類されていなくて
も、数字などの順序関係を持つ属性を保持している場合
においては上記と同様の問題が発生する。

【０００９】本発明の目的は、グループを指定した場合
でも指定しない場合でも、無駄な探索や複数の木を探索
することのない探索効率を改善させた鍵探索方法を提供
することにある。

【００１０】

【課題を解決するための手段】本発明は、グループ毎に
そのグループに対応するラベルを用意することとし、木
構造を構築する際に木構造の各ノード又は各アークに対
して、そのノード又はアークより末端方向に存在する葉
に対応するすべての鍵のグループに対応するラベルを付
与しておくようにする。鍵を探索するときには、探索の
条件に応じて、付与されたラベルを参照することにより
さらに末端の方向へ探索を進めてるかどうかを判断する
ことができるので、無駄な探索を避けることが可能とな
る。

【００１１】同様に、鍵が数字などの順序関係を持つ属
性を有している場合においても、木構造の各ノード又は
各アークに、そのノード又はアークより末端方向に存在
する葉に対応するすべての鍵の属性の範囲を記述してお
く。鍵の探索時にその属性の範囲を利用して、範囲外の
枝はたどらないようにすることにより、無駄な探索を避
けることが可能となる。

【００１２】特に、検索する鍵が複数ある場合や、ある
グループに属するすべての鍵を拾い出す場合など、木構
造を広く探索するときに非常に有効となる。

【００１３】ただし、上記方法であっても、ラベルの照
合に時間を要するようでは、無駄な探索時間を省略でき
る利点が減少してしまうことになる。そこで、さらに上
記方法に加えて、ラベルの表現方法を２進数表現とし
て、属性の各グループ及びその上位グループに割り当て
る表現を利用することにより、ラベル同士の照合を２進
数の各桁毎の論理演算で可能としたので、高性能を損な
わずに無駄な探索を省略することが可能になっている。

【００１４】本発明によれば、木を構築及び拡張する
際、その各ノードもしくはアークに、それよりも末端に
近いノードにある全ての葉に対応する鍵の属するグルー
プ情報をラベルとして付与する。鍵の探索時には、対象
となる鍵のグループが与えられると、木構造の根からノ
ード又はアークに付加されたラベルを参照し、対象とな
るグループがそれよりも末端に存在するかどうか確認す
る。対象となるグループが存在するならば探索を進め
て、存在しないならば探索を終了させる。このように、
探索対象の属性が限定されたときにおいて、無駄な探索
をせずにグループ分けされた鍵を探索することが可能と
なる。

【００１５】

【発明の実施の形態】本発明の第１の実施の形態として
の鍵探索方法を図１乃至図３を用いて説明する。本実施
の形態は、例えば品詞予測が可能な構文解析を行うとき
などに、品詞が限定された状況における形態素辞書の検
索に本発明を適用したものである。

【００１６】本実施の形態では、辞書を仮名表記の単位
のトライによって表現する。トライ上に構築される鍵は
辞書に含まれる形態素の読みであり、鍵の所属するグル
ープはその形態素の品詞である。品詞は文中に同時に予
想される頻度の多さに応じて３２個にクラスタリングさ
れている。３２桁の２進数表現の各桁にこの３２個のク
ラスタ（グループ）を割り当てておく。

【００１７】そして、この数字の各桁が１であるか０で
あるかによって対応するグループに属する品詞を持つ形
態素が、それより端末に存在するか否かの指標とする。
複数のグループにまたがった状態は、対応する複数の桁
が１となりその他の桁がすべて０になることで表現され
る。この品詞のグループを表現した数字をこれ以後ラベ
ルと呼ぶ。

【００１８】図１に本実施の形態における鍵探索方法で
利用するトライの概念図を示す。図中左側が根ノード１
である。根ノード１には対応する読みと、根ノードを葉
とする形態素は存在しない。根ノード１には、このトラ
イにのっているすべての形態素の品詞を表現するラベル
４が付与されている。本実施の形態では、３２個のグル
ープに分類された品詞を３２桁の２進数に対応させて表
現したラベルが、さらに１６進数で表現されている。従
って、図中ｆｆｆｆｆｆｆｆで示したラベル４は３２個
すべてのグループに属する形態素がこのトライにのって
いることを表現している。各ノード２にそれよりも末端
にある形態素の属するグループを示すラベル４が付与さ
れている。

【００１９】本実施の形態における鍵探索方法では、そ
のノードより、子のノード及びその子のノードまたさら
にその子のノードといったように、すべてのノードを葉
とする形態素の所属するグループをラベルとして表現し
ている。従ってそのノードを葉としてのっている形態素
のグループが、それより子のノードにはのっていないグ
ループはそのノードには表現しない。すなわち、子のノ
ードを持たない最も右側のノードにはラベル４として０
が付与されている。

【００２０】トライにのっている形態素は、対応するノ
ードに辞書の項目を指すポインタ５として付与されてい
る。対応する辞書項目に、その形態素に対する必要な情
報が書き込まれている。本実施の形態においては、同じ
読みの形態素、すなわち、同じノードを葉としている形
態素は、辞書項目の同音の形態素で、アドレスへのポイ
ンタを付与することで表現する。同音の形態素がない場
合、及び同音を持つ最も末尾の形態素には、同音の形態
素を表すポインタとしてｎｕｌｌを記述しておく。

【００２１】本実施の形態における鍵探索方法を図２を
用いて説明する。構文解析によって次にある品詞群がく
ることが予想されているときに、文字列を使って形態素
の辞書引きをするような状況を例とする。

【００２２】まず、検索しようとする形態素の品詞から
その品詞に対応する参照ラベルを作成する（ステップＳ
１０１）。この際、複数のグループにまたがった品詞が
予測された場合には、それぞれの品詞のグループに対応
する桁すべてが１になり、そうでない桁がすべて０にな
っているラベルを作成することになる。

【００２３】次に、木構造の根ノードを参照して以下に
示す手順で検索作業に入る（ステップＳ１０２）。

【００２４】ノードにあるラベルと参照ラベルとを照合
するため、ノードのラベルと、検索条件のラベルとで２
進数表現の各桁毎の論理積演算を行う（ステップＳ１０
３）。演算結果が０になれば、検索しようとしている条
件とそのノードより子のノードにある鍵に、共通の品詞
がないことを表す（ステップＳ１０４）。従って、検索
を進める意味がなく、対応する形態素が辞書に存在しな
いことを意味する。従ってこの場合には、その結果を出
力して（ステップＳ１１０）探索を終了する。

【００２５】ステップＳ１０４で論理積演算の結果が０
にならない場合は、品詞として条件を満たす形態素が存
在することを意味するので探索を進め、検索対象となっ
ている文字列が最後の文字に到達しているか判断する
（ステップＳ１０５）。まだ、文字列が継続している場
合には、文字を１つ読み進め、その読みに対応する子の
ノードが存在するか調べる（ステップＳ１０６）。対応
する子のノードが無い場合は、その読みに対応する形態
素が存在しないことを意味しており、探索を終了する。
対応する子のノードがある場合にはそのノードに進む
（ステップＳ１０６、Ｓ１０７）。これが、形態素に対
応する葉のノードとなっている場合にはそこまでの文字
列が、その形態素である可能性があるので対応する辞書
項目を読み込む（ステップＳ１０８）。辞書項目を読み
込んだ結果として、探索していた品詞に含まれるもので
有れば、検索の結果として取り出す。さらに、文字列が
継続している場合には、さらに長い読みの形態素とさら
に一致する可能性があるので探索を継続する。また、次
のノードが葉のノードとなっていない場合にも探索を継
続する。

【００２６】上記の探索は、木構造の枝がたどれなくな
るか、文字列が終了するまで継続する。探索が終了した
ら、照合に成功した形態素があればそれを結果として出
力し、なければ探索に失敗したとして結果を出力して
（ステップＳ１１０）、１回の探索を終了する。

【００２７】上記の探索を行うときに利用する図１に示
すようなラベル付トライを作成する処理の流れを以下に
示す。ラベル付トライは、ラベルのない通常のトライを
作成した後、トライにのっている形態素を参照しながら
ラベルを付けていくことも可能である。しかしここでは
トライを作成しながらラベルを付加していく手順を示
す。根ノードだけの他に何もない状態のトライから、辞
書項目となる形態素を一つずつ追加登録する形態をと
る。この方法によれば新たに形態素を追加登録するとき
にも、簡単に追加が可能であるという利点を有している
方法である。

【００２８】一つの形態素を追加する処理の流れを図３
のフローチャートを用いて説明する。まず、追加しよう
とする形態素の品詞に基づいて参照ラベルを作成する
（ステップＳ２０１）。トライの根ノードを参照して以
下の作業を繰り返す（ステップＳ２０２）。ノードのラ
ベルと、登録しようとする形態素のラベルの２進数表現
の各桁毎の論理和演算を行う。演算結果をそれまでのノ
ードのラベルに上書きする（ステップＳ２０３）。次
に、形態素の次の読みに従って、子のノードをたどる
（ステップＳ２０４）。もし、たどるべきノードが無い
場合は、読みに対応するノードを追加する（ステップＳ
２０７）。あらかじめノードがあった場合にしても、追
加した場合にしても、形態素の読みの終わりまできたな
らば（ステップＳ２０８）、そのノードを葉ノードとし
て辞書項目に書き込み（ステップＳ２０９）、一つの形
態素の追加作業を終了する。ステップＳ２０８でまだ読
みが続く場合には、そのノードに対してラベルの書き換
えをして（ステップＳ２０３）、読みの末尾に到達する
まで上記作業を継続する。

【００２９】上記の形態素を追加する作業を辞書に登録
するすべての形態素について行えば、ラベル付トライが
完成する。

【００３０】上述では品詞というグループによるラベル
付けの例を示したが、順序関係を持つ属性に対しても適
用できる。例えば、重要度を数字で表した単語のトライ
に対して、その重要度を属性としてラベル付けすること
も考えられる。この場合は、ある数値より大きい重要度
の単語などという条件のもとで探索を行うことになる。
そして、前述の鍵探索において、ラベルの論理積演算の
部分が重要度のラベルの大小比較演算に代わる以外は同
様の流れで探索することができる。

【００３１】また、木の構築においては、ラベルの論理
和による書き換え部分が大小比較により小さい方の値を
上書きするようにすればよい。

【００３２】以上示したように、木構造を構築する鍵と
は別の属性を利用した、辞書検索の効率化されたラベル
付き木構造が実現される。

【００３３】本発明の第２の実施の形態として音声認識
に適用した例を図４乃至図７を用いて説明する。図４に
音声認識装置の構成を示す。音韻認識手段１０によって
入力された音声を信号処理、音韻認識処理を経て、音節
単位のグラフ表現（以下音節グラフという）に出力す
る。図５に認識結果の音節グラフの例を示す。言語処理
手段２０において、このグラフ表現を入力として辞書３
０と文法４０と言語統計情報５０を利用しながら音声認
識結果を出力する。ここでは、本発明の鍵探索を利用し
た辞書検索の流れについて説明する。

【００３４】本実施の形態において文法４０は、品詞を
終端記号として記述した文脈自由文法をＬＲ表に構築し
ておく。このＬＲ表を用いてＬＲパージングを行う。こ
のＬＲ表を用いることで、ある構文解析状態のときに次
にくることのできる品詞を予測することができる。この
ときに同時に予測されやすい品詞と、予測されにくい品
詞とにより品詞を３２個にグループ分けしておく。この
グループを３２桁の２進数に対応させて表現し、鍵探索
時のラベルとする。これとは別に、受理できる構文に従
えば、発話の先頭にくることができる品詞が決まるの
で、それをあらかじめ表にしておく。また、この表に含
まれる品詞のすべてのグループのビット毎の論理和をと
ったラベル表現も計算しておく。

【００３５】辞書３０は、前述の実施の形態と同様に、
仮名表記の単位のトライによって表現する。トライ上に
構築される鍵は辞書に含まれる単語の読みである。トラ
イによって見つかった鍵に応じてこの辞書項目が読み出
せる。辞書項目としての各単語の読み、品詞、その品詞
のグループ、及び統計的データを記録しておく。また、
トライ上の各ノードには、それより子供のノードにある
単語すべての品詞のグループのビット毎に論理和をとっ
たラベルを付与しておく。

【００３６】処理の流れとしては、音節単位のグラフの
先頭から辞書引き及び構文解析を始める。発話の先頭に
くることができる品詞の表とその品詞のグループのラベ
ル表現を読み、音節単位のグラフ表現の先頭から辞書引
きを始める。図５の例では、音節グラフは無音を示す
「＃」で始まり、そして終わっているので、「＃」の次
から辞書引きは始まる。辞書引きの作業は前記実施の形
態と同様に行われる。根（ルート）ノードからラベルの
ビット毎の論理積演算を行い０でなかったら探索を進め
る。但し本実施の形態では音節グラフの上を探索する点
が異なる。

【００３７】ある音節グラフ上のノードから辞書検索を
行う手順を図６を用いて説明する。まず、構文解析の状
態からＬＲテーブルを参照して次にくることのできる品
詞をリストアップする（ステップＳ３０１）。その品詞
の属するグループから探索対象テーブルを作成する（ス
テップＳ３０２）。辞書検索の検索結果を入れるリスト
を初期化する（ステップＳ３０３）。検索を開始する音
節グラフのノードと、トライの根ノードを現在の検索中
の現ノードとする（ステップＳ３０４、Ｓ３０５）。音
節グラフの先頭から検索するときは先頭のノードが現ノ
ードとなる。トライの根ノードに付属しているラベルと
論理積演算を行う（ステップＳ３０６）。これが０のと
きは対象となる品詞に属する単語が辞書の中に存在しな
いことになるので、辞書検索は照合した単語無しという
結果で終了する。演算の結果が０でない場合は、以後、
音節を一つずつ照合する手続きに入る（ステップＳ４０
０）。

【００３８】音節を一つずつ照合する手続きの流れを図
７を用いて説明する。まず、音節グラフ上の現ノードか
ら次につながるアークを探す（ステップＳ４０２）。探
索すべきアークがないならば、そのアークに対応する音
節で始まる単語があるかトライを探索する（ステップＳ
４０３、Ｓ４０４、Ｓ４０５）。トライ上で対応するア
ークがなければ、その音節では単語が照合しないことを
示すので、別の音節で探索を進める。アークが有れば、
トライ上の現ノードを、そのアーク分一つ進める（ステ
ップＳ４０６）。

【００３９】読み進んだノードが、対応する辞書項目を
指し示すポインタを持つならば、辞書項目を読み出し、
現在対象としている品詞であるか確認する（ステップＳ
４０７、Ｓ４０８）。該当する品詞である単語は辞書検
索に成功した単語なので、検索結果を格納するリストに
追加する（ステップＳ４０９）。このとき、同じ読みの
単語が複数ある場合には、該当する品詞の単語すべてを
リストに追加する。単語をリストに追加した場合もそう
でない場合も、新たなノードでラベルの照合を行う（ス
テップＳ４１０）。照合に成功すれば、以後の音節グラ
フ上を検索する価値があることを意味する。このとき
は、音節グラフの現ノードを今照合に成功したアークを
たどり次のノードに変更し（ステップＳ４１１）、次の
アークに対してさらに音節を一つずつ照合する別のステ
ップＳ４００の手続きに入る。ステップＳ４１０で、ラ
ベルの照合に失敗したとき、もしくは後続のアークにた
いするステップＳ４００が終了したときには、並列する
別のアークについても探索するため、再びステップＳ４
０１に戻り探索を進める。以上の手続きをすべての現ノ
ードに接続するすべてのアークについて処理を行った
ら、それまでに検索に成功したリストを結果としてステ
ップＳ４００の処理は終了する。

【００４０】以上の処理の結果として、照合に成功した
リストの単語に応じて構文解析を進めたり、統計的言語
評価を行い音声認識作業が進むことになる。

【００４１】

【発明の効果】以上の通り、本発明によれば、木構造を
利用した通常の鍵探索に加えて、鍵の別の属性により検
索条件が限定されている場合において、検索条件を満足
しない対象しか存在しない副木など、無駄な副木を探索
する比率を低下させて有効な検索を可能とするものであ
る。

【００４２】また、あるノードより下位にある鍵が、検
索条件を満たしているかいないかの判定、すなわちラベ
ルによる照合演算に時間を費やすと、探索時間が余分に
必要になる原因となる。本発明ではさらに、属性をグル
ープ化して時間をあまり要しない２進数の論理演算を利
用することで、探索の速度を低下させるのを防止し、高
速な鍵探索方法を実現することができる。

【図面の簡単な説明】

【図１】本発明の第１の実施の形態によるトライを用い
た辞書の概念図である。

【図２】本発明の第１の実施の形態による鍵探索方法を
示す図である。

【図３】本発明の第１の実施の形態による鍵の登録処理
を示す図である。

【図４】本発明の第２の実施の形態による音声認識装置
を示す図である。

【図５】本発明の第２の実施の形態による音声認識方法
を示す図である。

【図６】本発明の第２の実施の形態による音声認識方法
を示す図である。

【図７】本発明の第２の実施の形態による音声認識方法
を示す図である。

【符号の説明】

１ 根ノード ２ ノード ３ ノードに対応する読み ４ 属性を示すラベル ５ 辞書項目へのポインタ １０ 音韻認識手段 ２０ 言語処理手段 ３０ 辞書 ４０ 文法 ５０ 言語統計情報

Claims (4)

【特許請求の範囲】
1. 【請求項１】所定の属性に基づいて作成された木構造を
   利用して検索する鍵検索方法において、 前記木構造を作成した指標となる属性とは別のグループ
   に分類された属性を有し、前記木構造の各ノード又は各
   アークに、前記各ノード又は各アークより枝方向にある
   すべての鍵の属するグループをラベルとして記録し、 探索時に探索条件と前記ラベルとを照合して条件を満た
   さなければそれ以下の枝の探索を停止することを特徴と
   する鍵探索方法。
2. 【請求項２】所定の属性に基づいて作成された木構造を
   利用して検索する鍵検索方法において、 前記木構造を作成した指標となる属性とは別の順序関係
   のある属性を有し、前記木構造の各ノード又は各アーク
   に、前記各ノード又は各アークより枝方向にあるすべて
   の鍵の順序関係を持つ属性の範囲をラベルとして記録
   し、 探索時に探索条件と前記ラベルとの順序関係を判定して
   条件を満たさなければそれ以下の枝の探索を停止するこ
   とを特徴とする鍵探索方法。
3. 【請求項３】請求項１記載の鍵探索方法において、 鍵の持つ木構造を構築する属性とは別の属性をグループ
   とし、２進数表現の各桁に前記グループを対応させ、 前記木構造の各ノード又は各アークにそれより枝方向に
   あるすべての鍵の属性によって決まるグループを所定の
   数値で表現することを特徴とする鍵探索方法。
4. 【請求項４】所定の属性に基づいて作成された木構造を
   利用して検索する鍵検索装置において、 前記木構造を作成した指標となる属性とは別のグループ
   に分類された属性を有し、前記木構造の各ノード又は各
   アークに、前記各ノード又は各アークより枝方向にある
   すべての鍵の属するグループをラベルとして記録する手
   段と、 探索時に探索条件と前記ラベルとを照合して条件を満た
   さなければそれ以下の枝の探索を停止する手段とを有す
   ることを特徴とする鍵探索装置。