JP3603395B2 - マッチング装置およびマッチング方法 - Google Patents
マッチング装置およびマッチング方法 Download PDFInfo
- Publication number
- JP3603395B2 JP3603395B2 JP19034395A JP19034395A JP3603395B2 JP 3603395 B2 JP3603395 B2 JP 3603395B2 JP 19034395 A JP19034395 A JP 19034395A JP 19034395 A JP19034395 A JP 19034395A JP 3603395 B2 JP3603395 B2 JP 3603395B2
- Authority
- JP
- Japan
- Prior art keywords
- data
- hierarchical
- code
- value
- distance
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims description 33
- 238000004364 calculation method Methods 0.000 claims description 37
- 238000010586 diagram Methods 0.000 description 14
- 238000006243 chemical reaction Methods 0.000 description 5
- 238000000605 extraction Methods 0.000 description 5
- 238000004891 communication Methods 0.000 description 4
- 230000008569 process Effects 0.000 description 4
- 230000006870 function Effects 0.000 description 3
- 230000014509 gene expression Effects 0.000 description 3
- 230000005540 biological transmission Effects 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 230000004044 response Effects 0.000 description 2
- 230000009471 action Effects 0.000 description 1
- 238000013473 artificial intelligence Methods 0.000 description 1
- 230000015572 biosynthetic process Effects 0.000 description 1
- 230000007423 decrease Effects 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 239000000284 extract Substances 0.000 description 1
- 230000010365 information processing Effects 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 238000003786 synthesis reaction Methods 0.000 description 1
Images
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、データのマッチングの度合いを算出するマッチング装置およびマッチング方法に関連するものであり、特に、データ間の階層関係に基づくマッチング装置およびマッチング方法に関するものである。
【０００２】
【従来の技術】
従来より、テキスト検索や自動分類の研究が活発に行なわれている。こうした分野において、シソーラスと呼ばれる単語間の上位／下位関係および類義語を定義した辞書の重要性がますます高まっている。
【０００３】
テキスト検索においては、ユーザの入力した表現が検索対象中の表現と一致しないことがしばしば発生する。このため、検索された内容のヒット率を確保するために、類義語や上位／下位語を含めた検索が必要である。そこで、シソーラスを用いることにより検索要求の単語を展開する手法などがよく用いられる。
【０００４】
一般的には、検索時に検索要求に基づきシソーラスの階層をたどり、得られた類義語または上位／下位語のそれぞれを用いて検索がなされる。このとき、検索のたびに毎回シソーラスの階層をたどったのでは検索速度が低下するため、例えば、特開平２−２８０２７４号公報の「データベース検索システムの包括検索方式」で述べられているように、あらかじめシソーラスの上位／下位などを含めた包括インデックスを作成し、検索時の速度低下を防ごうとする技術などが提案されている。
【０００５】
しかしながら、このような包括インデックスを保持したとしても、包括インデックスに含まれる複数のデータベースキーに基づいた検索を行なう必要があるため、依然として単純一致検索に比べて速度の低下は発生する。また、こうした包括インデックス情報を予め作成しておく必要があるため、データ量やデータベース構築時のコストの増加を招くという問題もある。
【０００６】
例えば、検索キーとキーワード間でシソーラスを考慮したマッチングを行ない、マッチング度合いによって検索結果とするか否かを判定することも考えられるが、従来のマッチング手法では、マッチングの計算に時間がかかり、検索で用いることができる技術ではなかった。
【０００７】
一方、テキストの自動分類と呼ばれる分野では、なんらかの基準を用いてテキスト間の意味的な距離を用いることにより、テキストの分類が行なわれる。このとき、テキスト間の距離を求めるためにもシソーラスが用いられる。
【０００８】
例えば、情報処理，Ｖｏｌ．３６，Ｎｏ．２，１９９５．２，飯田，「人工知能におけるスーパーコンピューティング」，ｐｐ．１６４−１６８においては、句同士の間の距離を求める技術の一環として、概念階層を用いた単語間の距離計算方法が示されており、入力と用例間の意味距離が、あらかじめ付与された１０進シソーラスコードの照合により計算されている。
【０００９】
しかしながら、この計算法は共通の上位ノードへの距離のみによる計算であるため、木構造のリーフ（葉）であり、同一階層に並ぶ単語間の距離しか計算できない。単語はすべて同一レベルのリーフとして表現されるわけではないので、階層の途中の概念やリーフまでの階層数が異なる場合には適用できない。したがって、単語間の距離の比較においては、このような単純な方法では依然充分ではない。また、並列計算機を想定しているため、効率的な距離計算には連想メモリなど特殊な処理を必要とし、現在のところ一般的でない。
【００１０】
このように、従来の技術においては、シソーラスにおける単語間のマッチングを効率的に行なうには、依然不十分な技術しか存在しなかった。
【００１１】
【発明が解決しようとする課題】
本発明は、上述した事情に鑑みてなされたものであり、特に、シソーラスにおける単語間のマッチングを、高速かつ少ないデータサイズで効率的に行なうマッチング装置およびマッチング方法を提供することを目的とするものである。
【００１２】
【課題を解決するための手段】
本発明は、データ間の階層関係に基づくマッチングを行なうマッチング装置において、階層関係をもつデータ群の各データを各階層の同じ親を有する各データに対して順次割り振った値とともに保持し入力されたデータまで階層をたどったときのそれぞれの階層のデータに割り振られた値を並べたコードに変換する階層データコード化手段と、与えられた少なくとも二つのデータについての階層関係におけるデータ間の近さを示す概念距離として前記二つのデータから前記階層データコード化手段より得られたコードの排他的論理和と各階層の値のマスクコードとの論理積が非ゼロになる最大のマスクコードから該マスクコードに対応づけられている値を前記概念距離として算出する距離算出手段を有することを特徴とするものである。
また本発明は、データ間の階層関係に基づくマッチングを行なうマッチング方法において、階層関係をもつデータ群の各データを各階層の同じ親を有する各データに対して順次割り振った値とともに階層データコード化手段に保持しており、与えられた少なくとも二つのデータについて前記階層データコード化手段により該データまで階層をたどったときのそれぞれの階層のデータに割り振られた値を並べたコードに変換し、得られたコードの排他的論理和と各階層の値のマスクコードとの論理積が非ゼロになる最大のマスクコードから該マスクコードに対応づけられている値を距離算出手段で算出し、該値を階層関係におけるデータ間の近さを示す概念距離とすることを特徴とするものである。
【００１３】
さらに、請求項２および請求項５に記載の発明のように、与えられた少なくとも二つのデータについて前記階層データコード化手段より得られたコードと各階層の値のマスクコードとの論理積が非ゼロになる最小のマスクコードから各データの階層レベルを求めて前記データ間の階層レベルの差を算出する階層差算出手段を設けることができる。
【００１４】
さらに、請求項３および請求項６に記載の発明のように、前記距離算出手段および前記階層差算出手段の結果に基づき優先度を算出する優先度算出手段を設けることができる。
【００１５】
【作用】
本発明によれば、階層関係をもつデータ群の各データに対して、階層関係に応じたコードを保持させておく。そして、与えられた少なくとも二つのデータについて、各データまで階層をたどったときのそれぞれの階層のデータに割り振られた値を並べたコードに変換し、得られたコードの排他的論理和と各階層の値のマスクコードとの論理積が非ゼロになる最大のマスクコードから該マスクコードに対応づけられている値を算出し、その値を階層関係におけるデータ間の近さを示す概念距離とする。これにより、従来のように算術演算など、時間のかかる演算を行なうことなく距離計算を行なうことができ、データ間の階層関係に基づくマッチングが高速かつ容易に実現可能となる。また、請求項２および請求項３に記載の発明のように、用途に応じ、階層差算出手段や、さらに優先度算出手段を設けるなど、種々の構成をとることで、階層レベル差や優先度といったよりきめ細かな比較が可能となる。
【００１６】
【発明の実施の態様】
図１は、本発明のマッチング装置の１つの実施の態様を示す概略構成図である。図中、１は入力部、２は階層関係コード化部、３はマッチング部、４は出力部である。入力部１は、比較すべきデータを与える。階層関係コード化部２は、入力に応じて、あらかじめ階層間の位置にしたがって付与されたコードを返す。マッチング部３は、入力部１から与えられた複数のデータを、階層関係コード化部２から得られるコードを用いてビット論理演算でマッチングを行なう。出力部４は、マッチング部３により得られた結果を出力する。
【００１７】
図２は、本発明のマッチング装置の１つの実施の態様を類似語検索システムに適用した場合の一例を示すブロック構成図である。図中、１０は検索要求入力部、１１は端末、１２はＯＣＲ、１３は電話および音声認識部、１４は記憶装置、１５は赤外線・無線受信部、２０はシソーラスコード化部、２１はシソーラス、３０はマッチング部、３１は距離算出部、３２は階層差算出部、３３は優先度算出部、３４は出力指示部、４０は出力部、４１は端末、４２はファクシミリやプリンタ、４３は電話やポケベル、４４は赤外線・無線発信部、５０はデータベース部、５１はデータベースである。検索要求入力部１０は、図１に示した入力部１に対応し、同様に、シソーラスコード化部２０は階層関係コード化部２に、マッチング部３０はマッチング部３に、出力部４０は出力部４にそれぞれ対応する。データベース部５０は、検索対象となる各種の文書を電子的に記憶する部分であり、文書はデータベース５１に記憶される。
【００１８】
検索要求入力部１０は、例えば、端末１１、ＯＣＲ１２、音声を入力するマイクなどを具備した電話および音声認識部１３、メモリやディスク、テープ等の記憶装置１４、携帯情報機器などからの赤外線や無線を受信する赤外線・無線受信部１５などから構成されている。もちろん、これらのうちの一部でもよいし、これ以外の入力装置を用いるようにしてもよい。
【００１９】
出力部４０は、端末４１のディスプレイ、ファクシミリ／プリンタ４２、音声合成によりスピーカから出力する電話やポケベル４３、携帯情報機器へ赤外線や無線を用いて情報を伝送する赤外線・無線発信部４４などから構成される。もちろん、これらの一部で構成してもよいし、これ以外の出力装置を用いるようにしてもよく、いったんネットワーク等に接続された記憶装置に蓄えるように構成してもよい。
【００２０】
シソーラスコード化部２０は、入力された単語に応じて、シソーラス２１の階層構造に応じて保持されたコードに変換する部分である。
【００２１】
マッチング部３０は、入力された単語とデータベース５１中の文書のキーワードを比較し、検索要求に一致あるいは類似したキーワードを有する文書を出力指示する部分である。距離算出部３１は、シソーラスコード化部２０で変換された検索要求と文書のキーワードのコード同士を論理演算し、階層関係における距離を算出する部分である。階層差算出部３２は、シソーラスコード化部２０で変換された検索要求と文書のキーワードのコード同士を論理演算し、階層レベルの差を算出する部分である。優先度算出部３３は、距離算出部および階層差算出部の結果に基づき、マッチング結果の優先度を算出する部分である。出力指示部３４は、優先度算出部３３で得られた結果に基づき、データベース部５０から検索要求に一致または類似したキーワードを有する文書を取り出し、出力部４０に出力を指示する。
【００２２】
図３は、類似語検索システムの一例における全体の動作の一例を示すフローチャート、図４は、マッチングアルゴリズムの一例の概略を示すフローチャートである。まず、Ｓ６１において、検索要求入力部１０からユーザの検索要求ＲＱが入力されると、Ｓ６２において、シソーラスコード化部２０でシソーラスコードへの変換が行なわれ、検索要求のシソーラスコードＣ１が得られる。
【００２３】
続いて、Ｓ６３において、検索対象となるデータベース５１より一つの文書ＤＱが取り出される。さらに、Ｓ６４において、この文書のキーワードＫＷを順次取り出す。キーワードは、検索時にその場で文書中から抽出してもよいし、検索の高速性が必要であれば、あらかじめ文書に手動または自動で付与されたものを用いればよい。Ｓ６５において、キーワードＫＷは、検索要求ＲＱと同様に、シソーラスコード化部２０でコード変換され、キーワードのシソーラスコードＣ２が得られる。
【００２４】
検索要求のシソーラスコードＣ１とキーワードのシソーラスコードＣ２がともに得られると、Ｓ６６において、コードのマッチングが行なわれる。まず、階層差算出部３２は、Ｓ８１において、検索要求のシソーラスコードＣ１の階層レベルを論理演算によって求め、検索要求の階層レベルＬ１とする。同様に、Ｓ８２において、キーワードのシソーラスコードＣ２の階層レベルを論理演算によって求め、キーワードの階層レベルＬ２とする。Ｓ８３において、検索要求の階層レベルＬ１とキーワードの階層レベルＬ２の差を求め、階層レベル差ＬＤとする。続いて、距離算出部３１は、Ｓ８４において、検索要求のシソーラスコードＣ１とキーワードのシソーラスコードＣ２のビット排他論理和を計算し、概念距離ＣＤとする。さらに、優先度算出部３３は、Ｓ８５において、抽出された階層レベル差ＬＤと概念距離ＣＤに応じて優先度ＰＬを算出する。
【００２５】
このようにしてコードのマッチングが行なわれると、得られた階層レベル差ＬＤ、概念距離ＣＤ、優先度ＰＬなどが基準を満たしているか否かを、Ｓ６７でチェックする。Ｓ６８で基準を満たしていると判定されれば、出力指示部３４は、Ｓ６９で結果バッファＢＦに文書ＤＱを出力する。もちろん、出力部４０に直接出力指示を行なってもよい。
【００２６】
Ｓ７０において、現在処理中の文書に付与されているキーワードがすべて処理されたか否かを判定し、最後のキーワードの処理が終了するまで、Ｓ６４〜Ｓ７０の処理を繰り返し行なう。１つの文書について、すべてのキーワードの処理が終了すると、Ｓ７１において、すべての文書について処理を行なったか否かを判定し、最後の文書の処理が終了するまで、Ｓ６３〜Ｓ７０の処理を繰り返し行なう。
【００２７】
このような処理を行なうことによって、検索要求に一致あるいは類似したキーワードを有する文書が検索され、出力されることになる。上述のように、マッチング処理では階層差や概念距離を、論理演算を用いて行なっているので、高速にマッチング処理を行なうことができる。そのため、従来のようにシソーラス階層をたどったり、包括インデックスを用いることなどもなく、少ないデータサイズで高速な類似語検索を実現することができる。
【００２８】
以下、具体例を用いて、上述の動作の一例を説明する。図５は、シソーラスの構成の具体例を示す説明図である。例えば、「自家用車」という単語は、「自動車」の下位概念であり、「スポーツカー」、「セダン」、「ＲＶ車」などの上位概念を表わす。それぞれの単語には、図中の角カッコ“［］”内に示すように、各階層の同じ親を有する各単語について、レベル１から始まるコードを順次割り振る。ここでは一つの階層につき２進４ビットを用い、１６進数で示している。
【００２９】
実際に各単語に割り当てられるコードの例の一部も、図中の丸カッコ“（）”内に示している。例えば、「自家用車」という単語においては、
具体物［２］→機械［３］→乗物［Ａ］→車両［２］→自動車［４］→自家用車［４］
という階層をたどり、さらに１レベルの下位データを持つため、これを［０］と表わし、「２３Ａ２４４０Ｈ」という４バイトの１６進コードを割り当てる。ここで、末尾の‘Ｈ’は、１６進数であることを示しており、１６進の「２３Ａ２４４０」という値を示している。同様に、「自家用車」の下位に位置し、末端のデータである「セダン」という単語には、「２３Ａ２４４２Ｈ」というコードを割り当てる。ここでは各ノードが１５個以下の８階層としたため、４ビット７レベルのコードを用いたが、もちろんこの割り当ては自由であり、シソーラスの構造に応じて設計すればよい。なお、この割り当ては、シソーラスの階層構造をトラバースすることにより容易に自動的化できるため、人手によるコード付与などの手間を排除することが可能である。
【００３０】
図３のＳ６１で入力された検索要求ＲＱは、Ｓ６２において、シソーラスコードＣ１へ変換される。図６は、シソーラスコードへの変換の一例を示す概念図である。ここでは、データ構造として特開平５−２８１９４号公報の「データアクセス方式」に述べられているような、ハッシングを用いた例を示す。入力されたデータは、ハッシュ関数によって得られたハッシュ値をもとにハッシュテーブルを参照する。ここでは、ハッシュテーブルにはチェインインデックスへのポインタが格納されており、このポインタをもとにチェインインデックスを参照し、このチェインインデックスで衝突をチェックした後、変換データが参照される。変換データには、単語に対応するコードが格納されており、入力データに対応するコードが得られる。
【００３１】
例えば、「セダン」というデータが入力されると、ハッシュ関数によりハッシュ値が得られ、これをもとにハッシュテーブルが参照され、さらにチェインインデックにより衝突がチェックされた後、シソーラスコードＣ１として「２３Ａ２４４２Ｈ」が得られる。また、図６に示したように、「オートバイ」と「バイク」などの同義語は、入力データとしては異なるが、変換により同一化されたコードとなる。このように、シソーラスにおける階層関係をたどる必要なしに、直接、データからコードを得ることができる。
【００３２】
なお、ここではハッシュ法を用いた例について説明したが、ＢＴｒｅｅなど、他のデータ構造を用いてもよいことはもちろんである。
【００３３】
このようにして、入力された検索要求ＲＱは、ハッシュ関数により変換され、ハッシュテーブルとチェインインデックスをたどることにより、シソーラスコードＣ１に変換される。続いて、Ｓ６３で検索対象となるデータベース５１より文書が１つ取り出され、さらにＳ６４でこの文書のキーワードが取り出される。ここでは、キーワードＫＷとして「パソコン」が取り出されたとする。キーワードＫＷは、Ｓ６５で上述と同様の方法によりシソーラスコード化部２０でコード変換される。たとえばキーワードが「パソコン」の場合には、図５に示すように、「２３ＥＣ２２０Ｈ」というシソーラスコードに変換される。
【００３４】
検索要求のシソーラスコードＣ１と、キーワードのシソーラスコードＣ２がともに得られると、Ｓ６６でコードのマッチングが行なわれる。マッチングは、大きく階層差算出部３２におけるレベル差の計算と、距離算出部３１における概念距離の計算に分けられる。
【００３５】
まず、階層差算出部３２は、Ｓ８１，Ｓ８２において、検索要求のシソーラスコードＣ１とキーワードのシソーラスコードＣ２の階層レベルを計算する。具体的には、次に示すような４ビット単位のマスクコードを用意し、検索要求のシソーラスコードＣ１およびキーワードのシソーラスコードＣ２とのＡＮＤを順次とり、非ゼロになるまで繰り返すことでレベルが決定される。なお、レベル１までのＡＮＤがすべて０であった場合、すなわちＣ１またはＣ２のコードが０の場合、それはシソーラスの根、この場合「概念」であるからレベルは０となる。
レベル７： ００００００ＦＨ
レベル６： ０００００Ｆ０Ｈ
レベル５： ００００Ｆ００Ｈ
レベル４： ０００Ｆ０００Ｈ
レベル３： ００Ｆ００００Ｈ
レベル２： ０Ｆ０００００Ｈ
レベル１： Ｆ００００００Ｈ
【００３６】
「セダン」に関するコードは、上述のように「２３Ａ２４４２Ｈ」であったから、まず００００００ＦＨとのＡＮＤを取ると、
００００００ＦＨ ＡＮＤ ２３Ａ２４４２Ｈ ＝ ２Ｈ
となり、非ゼロであるのでレベル７の単語であることがわかり、終了する。
【００３７】
「パソコン」に関するコードは、上述のように「２３ＥＣ２２０Ｈ」であったから、まず００００００ＦＨとのＡＮＤを取ると、
００００００ＦＨ ＡＮＤ ２３ＥＣ２２０Ｈ ＝ ０Ｈ
となり、ゼロであるので、さらに０００００Ｆ０ＨとのＡＮＤを取る。すると、
０００００Ｆ０Ｈ ＡＮＤ ２３ＥＣ２２０Ｈ ＝ ２０Ｈ
となり、非ゼロであるので、レベル６の単語であることがわかり、終了する。
【００３８】
ここでは、ＡＮＤによるマスクを用いた方法を述べたが、レベルに応じたビット数、例えば、レベル７の場合４ビットだけ右シフトし、下位桁あふれフラグをチェックするなどの方法でも、もちろん論理的に同一になる。いずれにせよ、これらのビット単位の論理演算は、一般に非常に高速に実行可能であるため、処理の高速化を実現することが可能である。
【００３９】
こうして得られた階層レベルの差の絶対値をＳ８３で計算し、階層レベル差ＬＤとする。ここでは｜７−６｜＝１となる。
【００４０】
続いて、距離算出部３１において、単語間の概念距離が計算される。概念距離は、コード間のビット排他的論理和（ＸＯＲ）に基づいて求められる。ここでは、
２３Ａ２４４２Ｈ ＸＯＲ ２３ＥＣ２２０Ｈ ＝ ４Ｅ６６２Ｈ
となる。こうして得られる値は、単語（概念）間のいわば近さを示す。概念距離はここで得られた値の範囲に応じて付与する。この付与には、上述の階層レベルチェックと同様に、次に示すマスクコードとのＡＮＤで非ゼロになる最大のものとして、容易に求められる。なお、ＸＯＲの結果が全ビット０の場合、同一のコードであるから概念距離は０となる。
概念距離７： Ｆ００００００Ｈ
概念距離６： ０Ｆ０００００Ｈ
概念距離５： ００Ｆ００００Ｈ
概念距離４： ０００Ｆ０００Ｈ
概念距離３： ００００Ｆ００Ｈ
概念距離２： ０００００Ｆ０Ｈ
概念距離１： ００００００ＦＨ
【００４１】
ここでは、ビット排他論理和の値が「４Ｅ６６２Ｈ」であるので、
Ｆ００００００Ｈ ＡＮＤ ４Ｅ６６２Ｈ ＝ ０Ｈ
０Ｆ０００００Ｈ ＡＮＤ ４Ｅ６６２Ｈ ＝ ０Ｈ
００Ｆ００００Ｈ ＡＮＤ ４Ｅ６６２Ｈ ＝ ４００００Ｈ
となり、概念距離＝５であることがわかる。
【００４２】
図７は、マッチング結果の具体例の説明図である。図７には、「セダン」を検索要求として、各キーワードと、そのキーワードのシソーラスコードＣ２、「セダン」のシソーラスコードＣ１「２３Ａ２４４２Ｈ」とのビット排他論理和の値、概念距離、レベル差、優先度について示している。優先度については、後で再びこの図を参照して説明する。
【００４３】
図７に示すように、概念距離はレベル差とは直接関係ない。例えば、「セダン」に関し、１レベル上位（親子関係）である「自家用車」とのビット排他論理和の値は２Ｈ、その１レベル下で同じ上位語を持つ「スポーツカー」とは３Ｈとなり、これらは非常に近い関係であり、概念距離は１になる。
【００４４】
一方、２レベル上位（祖父母関係）である「自動車」では、ビット排他論理和の値は４２Ｈであるが、その１レベル下位（おじ／おば）にあたる「バス」とは５２Ｈ、さらに１レベル下（いとこ）、すなわち同レベルの「ボンネットバス」では５０Ｈとなり、これらとの概念距離は２になる。さらに、前述の「パソコン」に対しては、ビット排他論理和の値は４Ｅ６６２Ｈとなり、概念距離は５である。
【００４５】
図８は、具体例における概念距離の一部を２次元にマッピングした概念図である。図８において、○はノードを示し、実線はシソーラス階層を示しており、高さが階層レベルを示している。ここで示したシソーラス階層は、図５に示したものの一部である。いま、「セダン」を基準とし、概念距離を２次元上の距離に対応させると、等しい概念距離のノードは、図８に示すように等距離の円弧上に配置して示すことができる。
【００４６】
なお、上述の例では、概念距離の計算にあたり、マスクコードによるＡＮＤを用いたが、論理的に同一であればさまざまな方法で実現し得る。図９は、概念距離のＯＲゲートによる算出法の説明図である。例えば、図９に示すように、同一階層に相当するビットのＯＲをとり、ＯＮとなる最上位ビットを概念距離とすることが考えられる。図９に示した例では、「セダン」と「パソコン」のシソーラスコードのビット排他論理和の値「４Ｅ６６２Ｈ」を４ビットごとにＯＲ回路に入力し、出力として「００１１１１１」を得る。この結果の最上位ビットの位置は５番目であるので、概念距離は５となる。この計算方法では、ワイヤードロジックにより簡単に回路を構成できるので、ハードウェア化に向いた方法ということができる。もちろん、他の方法を用いて演算してもよい。
【００４７】
また、この例では、この後に優先度を算出するために、０〜７に限定した概念距離を導入している。実際に上述のようにして、ある概念距離をもつ表現間のＸＯＲの演算を行なうと、その結果は特定の範囲（概念距離２の場合１０Ｈ〜ＦＦＨ）のみをとるので、例えば、単語間のおおざっぱな距離を求める場合には、ＸＯＲを計算した結果を直接用いてももちろんよい。
【００４８】
さらに、この実施の態様では、シソーラスの全階層に４ビットの固定長を割り当てているが、リーフに近付くにつれてノード数が増えるなどシソーラスの構造はさまざまである。このような場合には、各階層ごとに異なるビット数を割り当てればよく、記憶容量が限られている場合でも、これを有効に利用することが可能である。加えて、シソーラスにおいてはすべてのリーフデータが同じ階層レベルになるとは限らないが、本発明は異なる階層レベルにまたがるデータが比較可能であるため、このような場合においても非常に有効である。
【００４９】
続いて、優先度算出部３３ではＳ８５において、距離算出部３１で算出された概念距離と、階層差算出部３２で算出された階層レベル差に応じ、優先度を算出する。上述のように、概念距離と階層レベル差は直接関係はない。また、概念距離が同一でも、それらの間の類似度が異なることは多い。上述の図８に示すように、「セダン」に対して「自動車」と「ボンネットバス」はともに概念距離２であるが、類似度は「自動車」のほうが直接の孫であるため、類似度は高いと考えられる。一方、シソーラスの構成によっては上位ノードに対し下位ノードとして類義語が並ぶような場合もある。このような場合は同じ階層レベルの方が類似度が高くなる。このように、概念距離と階層レベル差を用いることにより、これらを別の軸として評価することができる。
【００５０】
この例では、優先度として、次のような計算式を用いる。
優先度 ＝ 総レベル数×２ − （概念距離×２ − レベル差）
ここで、この例では総レベル数は７としている。上述の図７に示した各キーワードでは、「セダン」に対し、次のような値が返される。
１４：セダン（７×２ − （０×２ − ０） ＝ １４）
１３：自家用車
１２：スポーツカー，自動車
１１：バス，車両，・・・
１０：ボンネットバス，オートバイ，・・・
・・・
５：パソコン，・・・
・・・
もちろん、上述の計算式のほか、種々の計算方法によって優先度を算出してもよい。
【００５１】
続いて、図３のＳ６７で、上述のようにして得られたマッチング結果を用いて、抽出基準のチェックを行なう。ここでは単純に優先度の値が１２以上の場合、適合結果とする。上述の図７に示した各キーワードの例では、文書が「セダン」、「自家用車」、「スポーツカー」、「自動車」のいずれかのキーワードを有していれば、結果バッファＢＦに出力される。
【００５２】
もちろん、この基準とする値は適宜設定すればよい。また、この抽出基準については、他の抽出基準を用いてもよい。例えば、必要に応じて文書全体を走査したのちに統計処理によって抽出基準に対して重みづけをするなどがある。
【００５３】
このようにして、検索要求と１つのキーワードとのマッチング処理および文書の抽出が終了する。ここまでの処理が１つの文書に付されているすべてのキーワードについて繰り返し、さらに、それらをデータベース５１中の各文書に対して順次行なうことで処理が進められる。
【００５４】
以上の処理により、結果バッファＢＦには、ユーザからの検索要求「セダン」に類似したキーワードを含む文書、具体的には「セダン」、「スポーツカー」、「ＲＶ車」、「自家用車」、「自動車」などを含む文書が蓄積される。この結果に対し、出力指示部３４は優先度に基づいた文書の出力指示を出力部４０に対して行なう。出力部４０は、検索結果を出力し、検索処理は終了する。
【００５５】
上述の類似語検索システムでは、マッチング部３０において、概念距離、階層レベル差、およびこれらから優先度を算出したが、例えば、概念距離のみを利用したり、概念距離と階層レベル差を利用するなど、これらのうちの一部の計算結果を利用してもよい。
【００５６】
本発明は、階層関係を持つデータ間の比較処理一般に適用でき、上述の類似語検索システムへの適用のみに限定されるものではないことは言うまでもない。以下、本発明のマッチング装置の１つの実施の態様を文書自動分類システムに適用した場合について述べる。
【００５７】
現在、自動分類においては、標本データを用いた自動分類が一般的な技術のひとつである。しかし、シソーラス展開を含めることは、コストの問題から従来は困難であった。本発明のマッチング装置を、標準データとのマッチングに適用することにより、低コストで自動分類が可能となる。
【００５８】
例えば、次のようなキーワードを持つ標本データ群（一部）に対して、ある文書を自動分類することを考える。
［標本１］
キーワード： 携帯，電話，自動車，ＰＨＳ
カテゴリ： 移動体電話
［標本２］
キーワード： 端末，反射，抵抗，遅延
カテゴリ： ターミネータ
［標本３］
キーワード： 携帯，端末，ＰＤＡ，ネットワーク
カテゴリ： 携帯端末
【００５９】
入力文書も同様にキーワードを持つとする。これは、あらかじめ付与されたものでも、その場で抽出したものでもかまわない。
［入力文書］
キーワード： モーバイル，端末，通信
【００６０】
ここで、シソーラス展開を含めた入力文書と各標本のキーワード間の類似度を求める。類似度の計算には、上述の類似語検索システムの場合と同様の方法を用いることができる。さらに、入力文書の各キーワードとの類似度がもっとも低いもの同士の和を求める。標本１〜３において計算した例を示す。
（標本１）
モーバイル：携帯＝１，端末：ＰＨＳ＝４，通信：電話＝２ 合計７
（標本２）
モーバイル：遅延＝６，端末：端末＝０，通信：遅延＝３ 合計９
（標本３）
モーバイル：携帯＝１，端末：端末＝０，通信：ネットワーク＝２ 合計３
【００６１】
こうして得られた和のもっとも小さい標本が、入力文書との類似度がもっとも高いと考えられるため、入力された文書を当該カテゴリに分類する。この例では、標本３において計算された和が最も小さいので、入力文書は標本３のカテゴリ「携帯端末」に分類される。以上の処理を入力文書すべてに対して順次行なことで自動分類が行なわれる。
【００６２】
なお、上述の各システムへの適用例においては、シソーラスを用いた例について述べたが、階層構造をなすデータは一般に広く用いられているため、本発明はファイルディレクトリなど、シソーラス以外のデータ間のマッチングにも適用することができる。
【００６３】
【発明の効果】
以上の説明から明らかなように、本発明によれば、シソーラスのような階層構造をなすデータ間での比較が、ＡＮＤ、ＸＯＲといった単純なビット論理演算をベースとする簡単な処理のみで高速に実行することが可能となる。また、ビット論理演算処理をベースとすることにより、ソフトウェアによる実現はもちろん、ハードウェア化も容易である。
【００６４】
本発明により、従来の共通上位ノードまでの階層数といった単純な処理では困難であった、階層の途中にまたがるようなデータ間の場合でも比較可能となった。加えて、階層レベル差を用いることにより、データの種類に応じたきめ細かな比較基準を設け、優先度づけを行なうことができる。
【００６５】
このように、従来困難であったシソーラス展開を含むマッチング処理が簡単に、しかも高速に実行できるので、本発明のマッチング処理を適用した例えば類似テキスト検索やテキスト自動分類などが、高速かつ低コストで実現可能となるという効果がある。
【図面の簡単な説明】
【図１】本発明のマッチング装置の１つの実施の態様を示す概略構成図である。
【図２】本発明のマッチング装置の１つの実施の態様を類似語検索システムに適用した場合の一例を示すブロック構成図である。
【図３】類似語検索システムの一例における全体の動作の一例を示すフローチャートである。
【図４】マッチングアルゴリズムの一例の概略を示すフローチャートである。
【図５】シソーラスの構成の具体例を示す説明図である。
【図６】シソーラスコードへの変換の一例を示す概念図である。
【図７】マッチング結果の具体例の説明図である。
【図８】具体例における概念距離の一部を２次元にマッピングした概念図である。
【図９】概念距離のＯＲゲートによる算出法の説明図である。
【符号の説明】
１…入力部、２…階層関係コード化部、３…マッチング部、４…出力部、１０…検索要求入力部、１１…端末、１２…ＯＣＲ、１３…電話および音声認識部、１４…記憶装置、１５…赤外線・無線受信部、２０…シソーラスコード化部、２１…シソーラス、３０…マッチング部、３１…距離算出部、３２…階層差算出部、３３…優先度算出部、３４…出力指示部、４０…出力部、４１…端末、４２…ファクシミリ／プリンタ、４３…電話・ポケベル、４４…赤外線・無線発信部、５０…データベース部、５１…データベース。
【発明の属する技術分野】
本発明は、データのマッチングの度合いを算出するマッチング装置およびマッチング方法に関連するものであり、特に、データ間の階層関係に基づくマッチング装置およびマッチング方法に関するものである。
【０００２】
【従来の技術】
従来より、テキスト検索や自動分類の研究が活発に行なわれている。こうした分野において、シソーラスと呼ばれる単語間の上位／下位関係および類義語を定義した辞書の重要性がますます高まっている。
【０００３】
テキスト検索においては、ユーザの入力した表現が検索対象中の表現と一致しないことがしばしば発生する。このため、検索された内容のヒット率を確保するために、類義語や上位／下位語を含めた検索が必要である。そこで、シソーラスを用いることにより検索要求の単語を展開する手法などがよく用いられる。
【０００４】
一般的には、検索時に検索要求に基づきシソーラスの階層をたどり、得られた類義語または上位／下位語のそれぞれを用いて検索がなされる。このとき、検索のたびに毎回シソーラスの階層をたどったのでは検索速度が低下するため、例えば、特開平２−２８０２７４号公報の「データベース検索システムの包括検索方式」で述べられているように、あらかじめシソーラスの上位／下位などを含めた包括インデックスを作成し、検索時の速度低下を防ごうとする技術などが提案されている。
【０００５】
しかしながら、このような包括インデックスを保持したとしても、包括インデックスに含まれる複数のデータベースキーに基づいた検索を行なう必要があるため、依然として単純一致検索に比べて速度の低下は発生する。また、こうした包括インデックス情報を予め作成しておく必要があるため、データ量やデータベース構築時のコストの増加を招くという問題もある。
【０００６】
例えば、検索キーとキーワード間でシソーラスを考慮したマッチングを行ない、マッチング度合いによって検索結果とするか否かを判定することも考えられるが、従来のマッチング手法では、マッチングの計算に時間がかかり、検索で用いることができる技術ではなかった。
【０００７】
一方、テキストの自動分類と呼ばれる分野では、なんらかの基準を用いてテキスト間の意味的な距離を用いることにより、テキストの分類が行なわれる。このとき、テキスト間の距離を求めるためにもシソーラスが用いられる。
【０００８】
例えば、情報処理，Ｖｏｌ．３６，Ｎｏ．２，１９９５．２，飯田，「人工知能におけるスーパーコンピューティング」，ｐｐ．１６４−１６８においては、句同士の間の距離を求める技術の一環として、概念階層を用いた単語間の距離計算方法が示されており、入力と用例間の意味距離が、あらかじめ付与された１０進シソーラスコードの照合により計算されている。
【０００９】
しかしながら、この計算法は共通の上位ノードへの距離のみによる計算であるため、木構造のリーフ（葉）であり、同一階層に並ぶ単語間の距離しか計算できない。単語はすべて同一レベルのリーフとして表現されるわけではないので、階層の途中の概念やリーフまでの階層数が異なる場合には適用できない。したがって、単語間の距離の比較においては、このような単純な方法では依然充分ではない。また、並列計算機を想定しているため、効率的な距離計算には連想メモリなど特殊な処理を必要とし、現在のところ一般的でない。
【００１０】
このように、従来の技術においては、シソーラスにおける単語間のマッチングを効率的に行なうには、依然不十分な技術しか存在しなかった。
【００１１】
【発明が解決しようとする課題】
本発明は、上述した事情に鑑みてなされたものであり、特に、シソーラスにおける単語間のマッチングを、高速かつ少ないデータサイズで効率的に行なうマッチング装置およびマッチング方法を提供することを目的とするものである。
【００１２】
【課題を解決するための手段】
本発明は、データ間の階層関係に基づくマッチングを行なうマッチング装置において、階層関係をもつデータ群の各データを各階層の同じ親を有する各データに対して順次割り振った値とともに保持し入力されたデータまで階層をたどったときのそれぞれの階層のデータに割り振られた値を並べたコードに変換する階層データコード化手段と、与えられた少なくとも二つのデータについての階層関係におけるデータ間の近さを示す概念距離として前記二つのデータから前記階層データコード化手段より得られたコードの排他的論理和と各階層の値のマスクコードとの論理積が非ゼロになる最大のマスクコードから該マスクコードに対応づけられている値を前記概念距離として算出する距離算出手段を有することを特徴とするものである。
また本発明は、データ間の階層関係に基づくマッチングを行なうマッチング方法において、階層関係をもつデータ群の各データを各階層の同じ親を有する各データに対して順次割り振った値とともに階層データコード化手段に保持しており、与えられた少なくとも二つのデータについて前記階層データコード化手段により該データまで階層をたどったときのそれぞれの階層のデータに割り振られた値を並べたコードに変換し、得られたコードの排他的論理和と各階層の値のマスクコードとの論理積が非ゼロになる最大のマスクコードから該マスクコードに対応づけられている値を距離算出手段で算出し、該値を階層関係におけるデータ間の近さを示す概念距離とすることを特徴とするものである。
【００１３】
さらに、請求項２および請求項５に記載の発明のように、与えられた少なくとも二つのデータについて前記階層データコード化手段より得られたコードと各階層の値のマスクコードとの論理積が非ゼロになる最小のマスクコードから各データの階層レベルを求めて前記データ間の階層レベルの差を算出する階層差算出手段を設けることができる。
【００１４】
さらに、請求項３および請求項６に記載の発明のように、前記距離算出手段および前記階層差算出手段の結果に基づき優先度を算出する優先度算出手段を設けることができる。
【００１５】
【作用】
本発明によれば、階層関係をもつデータ群の各データに対して、階層関係に応じたコードを保持させておく。そして、与えられた少なくとも二つのデータについて、各データまで階層をたどったときのそれぞれの階層のデータに割り振られた値を並べたコードに変換し、得られたコードの排他的論理和と各階層の値のマスクコードとの論理積が非ゼロになる最大のマスクコードから該マスクコードに対応づけられている値を算出し、その値を階層関係におけるデータ間の近さを示す概念距離とする。これにより、従来のように算術演算など、時間のかかる演算を行なうことなく距離計算を行なうことができ、データ間の階層関係に基づくマッチングが高速かつ容易に実現可能となる。また、請求項２および請求項３に記載の発明のように、用途に応じ、階層差算出手段や、さらに優先度算出手段を設けるなど、種々の構成をとることで、階層レベル差や優先度といったよりきめ細かな比較が可能となる。
【００１６】
【発明の実施の態様】
図１は、本発明のマッチング装置の１つの実施の態様を示す概略構成図である。図中、１は入力部、２は階層関係コード化部、３はマッチング部、４は出力部である。入力部１は、比較すべきデータを与える。階層関係コード化部２は、入力に応じて、あらかじめ階層間の位置にしたがって付与されたコードを返す。マッチング部３は、入力部１から与えられた複数のデータを、階層関係コード化部２から得られるコードを用いてビット論理演算でマッチングを行なう。出力部４は、マッチング部３により得られた結果を出力する。
【００１７】
図２は、本発明のマッチング装置の１つの実施の態様を類似語検索システムに適用した場合の一例を示すブロック構成図である。図中、１０は検索要求入力部、１１は端末、１２はＯＣＲ、１３は電話および音声認識部、１４は記憶装置、１５は赤外線・無線受信部、２０はシソーラスコード化部、２１はシソーラス、３０はマッチング部、３１は距離算出部、３２は階層差算出部、３３は優先度算出部、３４は出力指示部、４０は出力部、４１は端末、４２はファクシミリやプリンタ、４３は電話やポケベル、４４は赤外線・無線発信部、５０はデータベース部、５１はデータベースである。検索要求入力部１０は、図１に示した入力部１に対応し、同様に、シソーラスコード化部２０は階層関係コード化部２に、マッチング部３０はマッチング部３に、出力部４０は出力部４にそれぞれ対応する。データベース部５０は、検索対象となる各種の文書を電子的に記憶する部分であり、文書はデータベース５１に記憶される。
【００１８】
検索要求入力部１０は、例えば、端末１１、ＯＣＲ１２、音声を入力するマイクなどを具備した電話および音声認識部１３、メモリやディスク、テープ等の記憶装置１４、携帯情報機器などからの赤外線や無線を受信する赤外線・無線受信部１５などから構成されている。もちろん、これらのうちの一部でもよいし、これ以外の入力装置を用いるようにしてもよい。
【００１９】
出力部４０は、端末４１のディスプレイ、ファクシミリ／プリンタ４２、音声合成によりスピーカから出力する電話やポケベル４３、携帯情報機器へ赤外線や無線を用いて情報を伝送する赤外線・無線発信部４４などから構成される。もちろん、これらの一部で構成してもよいし、これ以外の出力装置を用いるようにしてもよく、いったんネットワーク等に接続された記憶装置に蓄えるように構成してもよい。
【００２０】
シソーラスコード化部２０は、入力された単語に応じて、シソーラス２１の階層構造に応じて保持されたコードに変換する部分である。
【００２１】
マッチング部３０は、入力された単語とデータベース５１中の文書のキーワードを比較し、検索要求に一致あるいは類似したキーワードを有する文書を出力指示する部分である。距離算出部３１は、シソーラスコード化部２０で変換された検索要求と文書のキーワードのコード同士を論理演算し、階層関係における距離を算出する部分である。階層差算出部３２は、シソーラスコード化部２０で変換された検索要求と文書のキーワードのコード同士を論理演算し、階層レベルの差を算出する部分である。優先度算出部３３は、距離算出部および階層差算出部の結果に基づき、マッチング結果の優先度を算出する部分である。出力指示部３４は、優先度算出部３３で得られた結果に基づき、データベース部５０から検索要求に一致または類似したキーワードを有する文書を取り出し、出力部４０に出力を指示する。
【００２２】
図３は、類似語検索システムの一例における全体の動作の一例を示すフローチャート、図４は、マッチングアルゴリズムの一例の概略を示すフローチャートである。まず、Ｓ６１において、検索要求入力部１０からユーザの検索要求ＲＱが入力されると、Ｓ６２において、シソーラスコード化部２０でシソーラスコードへの変換が行なわれ、検索要求のシソーラスコードＣ１が得られる。
【００２３】
続いて、Ｓ６３において、検索対象となるデータベース５１より一つの文書ＤＱが取り出される。さらに、Ｓ６４において、この文書のキーワードＫＷを順次取り出す。キーワードは、検索時にその場で文書中から抽出してもよいし、検索の高速性が必要であれば、あらかじめ文書に手動または自動で付与されたものを用いればよい。Ｓ６５において、キーワードＫＷは、検索要求ＲＱと同様に、シソーラスコード化部２０でコード変換され、キーワードのシソーラスコードＣ２が得られる。
【００２４】
検索要求のシソーラスコードＣ１とキーワードのシソーラスコードＣ２がともに得られると、Ｓ６６において、コードのマッチングが行なわれる。まず、階層差算出部３２は、Ｓ８１において、検索要求のシソーラスコードＣ１の階層レベルを論理演算によって求め、検索要求の階層レベルＬ１とする。同様に、Ｓ８２において、キーワードのシソーラスコードＣ２の階層レベルを論理演算によって求め、キーワードの階層レベルＬ２とする。Ｓ８３において、検索要求の階層レベルＬ１とキーワードの階層レベルＬ２の差を求め、階層レベル差ＬＤとする。続いて、距離算出部３１は、Ｓ８４において、検索要求のシソーラスコードＣ１とキーワードのシソーラスコードＣ２のビット排他論理和を計算し、概念距離ＣＤとする。さらに、優先度算出部３３は、Ｓ８５において、抽出された階層レベル差ＬＤと概念距離ＣＤに応じて優先度ＰＬを算出する。
【００２５】
このようにしてコードのマッチングが行なわれると、得られた階層レベル差ＬＤ、概念距離ＣＤ、優先度ＰＬなどが基準を満たしているか否かを、Ｓ６７でチェックする。Ｓ６８で基準を満たしていると判定されれば、出力指示部３４は、Ｓ６９で結果バッファＢＦに文書ＤＱを出力する。もちろん、出力部４０に直接出力指示を行なってもよい。
【００２６】
Ｓ７０において、現在処理中の文書に付与されているキーワードがすべて処理されたか否かを判定し、最後のキーワードの処理が終了するまで、Ｓ６４〜Ｓ７０の処理を繰り返し行なう。１つの文書について、すべてのキーワードの処理が終了すると、Ｓ７１において、すべての文書について処理を行なったか否かを判定し、最後の文書の処理が終了するまで、Ｓ６３〜Ｓ７０の処理を繰り返し行なう。
【００２７】
このような処理を行なうことによって、検索要求に一致あるいは類似したキーワードを有する文書が検索され、出力されることになる。上述のように、マッチング処理では階層差や概念距離を、論理演算を用いて行なっているので、高速にマッチング処理を行なうことができる。そのため、従来のようにシソーラス階層をたどったり、包括インデックスを用いることなどもなく、少ないデータサイズで高速な類似語検索を実現することができる。
【００２８】
以下、具体例を用いて、上述の動作の一例を説明する。図５は、シソーラスの構成の具体例を示す説明図である。例えば、「自家用車」という単語は、「自動車」の下位概念であり、「スポーツカー」、「セダン」、「ＲＶ車」などの上位概念を表わす。それぞれの単語には、図中の角カッコ“［］”内に示すように、各階層の同じ親を有する各単語について、レベル１から始まるコードを順次割り振る。ここでは一つの階層につき２進４ビットを用い、１６進数で示している。
【００２９】
実際に各単語に割り当てられるコードの例の一部も、図中の丸カッコ“（）”内に示している。例えば、「自家用車」という単語においては、
具体物［２］→機械［３］→乗物［Ａ］→車両［２］→自動車［４］→自家用車［４］
という階層をたどり、さらに１レベルの下位データを持つため、これを［０］と表わし、「２３Ａ２４４０Ｈ」という４バイトの１６進コードを割り当てる。ここで、末尾の‘Ｈ’は、１６進数であることを示しており、１６進の「２３Ａ２４４０」という値を示している。同様に、「自家用車」の下位に位置し、末端のデータである「セダン」という単語には、「２３Ａ２４４２Ｈ」というコードを割り当てる。ここでは各ノードが１５個以下の８階層としたため、４ビット７レベルのコードを用いたが、もちろんこの割り当ては自由であり、シソーラスの構造に応じて設計すればよい。なお、この割り当ては、シソーラスの階層構造をトラバースすることにより容易に自動的化できるため、人手によるコード付与などの手間を排除することが可能である。
【００３０】
図３のＳ６１で入力された検索要求ＲＱは、Ｓ６２において、シソーラスコードＣ１へ変換される。図６は、シソーラスコードへの変換の一例を示す概念図である。ここでは、データ構造として特開平５−２８１９４号公報の「データアクセス方式」に述べられているような、ハッシングを用いた例を示す。入力されたデータは、ハッシュ関数によって得られたハッシュ値をもとにハッシュテーブルを参照する。ここでは、ハッシュテーブルにはチェインインデックスへのポインタが格納されており、このポインタをもとにチェインインデックスを参照し、このチェインインデックスで衝突をチェックした後、変換データが参照される。変換データには、単語に対応するコードが格納されており、入力データに対応するコードが得られる。
【００３１】
例えば、「セダン」というデータが入力されると、ハッシュ関数によりハッシュ値が得られ、これをもとにハッシュテーブルが参照され、さらにチェインインデックにより衝突がチェックされた後、シソーラスコードＣ１として「２３Ａ２４４２Ｈ」が得られる。また、図６に示したように、「オートバイ」と「バイク」などの同義語は、入力データとしては異なるが、変換により同一化されたコードとなる。このように、シソーラスにおける階層関係をたどる必要なしに、直接、データからコードを得ることができる。
【００３２】
なお、ここではハッシュ法を用いた例について説明したが、ＢＴｒｅｅなど、他のデータ構造を用いてもよいことはもちろんである。
【００３３】
このようにして、入力された検索要求ＲＱは、ハッシュ関数により変換され、ハッシュテーブルとチェインインデックスをたどることにより、シソーラスコードＣ１に変換される。続いて、Ｓ６３で検索対象となるデータベース５１より文書が１つ取り出され、さらにＳ６４でこの文書のキーワードが取り出される。ここでは、キーワードＫＷとして「パソコン」が取り出されたとする。キーワードＫＷは、Ｓ６５で上述と同様の方法によりシソーラスコード化部２０でコード変換される。たとえばキーワードが「パソコン」の場合には、図５に示すように、「２３ＥＣ２２０Ｈ」というシソーラスコードに変換される。
【００３４】
検索要求のシソーラスコードＣ１と、キーワードのシソーラスコードＣ２がともに得られると、Ｓ６６でコードのマッチングが行なわれる。マッチングは、大きく階層差算出部３２におけるレベル差の計算と、距離算出部３１における概念距離の計算に分けられる。
【００３５】
まず、階層差算出部３２は、Ｓ８１，Ｓ８２において、検索要求のシソーラスコードＣ１とキーワードのシソーラスコードＣ２の階層レベルを計算する。具体的には、次に示すような４ビット単位のマスクコードを用意し、検索要求のシソーラスコードＣ１およびキーワードのシソーラスコードＣ２とのＡＮＤを順次とり、非ゼロになるまで繰り返すことでレベルが決定される。なお、レベル１までのＡＮＤがすべて０であった場合、すなわちＣ１またはＣ２のコードが０の場合、それはシソーラスの根、この場合「概念」であるからレベルは０となる。
レベル７： ００００００ＦＨ
レベル６： ０００００Ｆ０Ｈ
レベル５： ００００Ｆ００Ｈ
レベル４： ０００Ｆ０００Ｈ
レベル３： ００Ｆ００００Ｈ
レベル２： ０Ｆ０００００Ｈ
レベル１： Ｆ００００００Ｈ
【００３６】
「セダン」に関するコードは、上述のように「２３Ａ２４４２Ｈ」であったから、まず００００００ＦＨとのＡＮＤを取ると、
００００００ＦＨ ＡＮＤ ２３Ａ２４４２Ｈ ＝ ２Ｈ
となり、非ゼロであるのでレベル７の単語であることがわかり、終了する。
【００３７】
「パソコン」に関するコードは、上述のように「２３ＥＣ２２０Ｈ」であったから、まず００００００ＦＨとのＡＮＤを取ると、
００００００ＦＨ ＡＮＤ ２３ＥＣ２２０Ｈ ＝ ０Ｈ
となり、ゼロであるので、さらに０００００Ｆ０ＨとのＡＮＤを取る。すると、
０００００Ｆ０Ｈ ＡＮＤ ２３ＥＣ２２０Ｈ ＝ ２０Ｈ
となり、非ゼロであるので、レベル６の単語であることがわかり、終了する。
【００３８】
ここでは、ＡＮＤによるマスクを用いた方法を述べたが、レベルに応じたビット数、例えば、レベル７の場合４ビットだけ右シフトし、下位桁あふれフラグをチェックするなどの方法でも、もちろん論理的に同一になる。いずれにせよ、これらのビット単位の論理演算は、一般に非常に高速に実行可能であるため、処理の高速化を実現することが可能である。
【００３９】
こうして得られた階層レベルの差の絶対値をＳ８３で計算し、階層レベル差ＬＤとする。ここでは｜７−６｜＝１となる。
【００４０】
続いて、距離算出部３１において、単語間の概念距離が計算される。概念距離は、コード間のビット排他的論理和（ＸＯＲ）に基づいて求められる。ここでは、
２３Ａ２４４２Ｈ ＸＯＲ ２３ＥＣ２２０Ｈ ＝ ４Ｅ６６２Ｈ
となる。こうして得られる値は、単語（概念）間のいわば近さを示す。概念距離はここで得られた値の範囲に応じて付与する。この付与には、上述の階層レベルチェックと同様に、次に示すマスクコードとのＡＮＤで非ゼロになる最大のものとして、容易に求められる。なお、ＸＯＲの結果が全ビット０の場合、同一のコードであるから概念距離は０となる。
概念距離７： Ｆ００００００Ｈ
概念距離６： ０Ｆ０００００Ｈ
概念距離５： ００Ｆ００００Ｈ
概念距離４： ０００Ｆ０００Ｈ
概念距離３： ００００Ｆ００Ｈ
概念距離２： ０００００Ｆ０Ｈ
概念距離１： ００００００ＦＨ
【００４１】
ここでは、ビット排他論理和の値が「４Ｅ６６２Ｈ」であるので、
Ｆ００００００Ｈ ＡＮＤ ４Ｅ６６２Ｈ ＝ ０Ｈ
０Ｆ０００００Ｈ ＡＮＤ ４Ｅ６６２Ｈ ＝ ０Ｈ
００Ｆ００００Ｈ ＡＮＤ ４Ｅ６６２Ｈ ＝ ４００００Ｈ
となり、概念距離＝５であることがわかる。
【００４２】
図７は、マッチング結果の具体例の説明図である。図７には、「セダン」を検索要求として、各キーワードと、そのキーワードのシソーラスコードＣ２、「セダン」のシソーラスコードＣ１「２３Ａ２４４２Ｈ」とのビット排他論理和の値、概念距離、レベル差、優先度について示している。優先度については、後で再びこの図を参照して説明する。
【００４３】
図７に示すように、概念距離はレベル差とは直接関係ない。例えば、「セダン」に関し、１レベル上位（親子関係）である「自家用車」とのビット排他論理和の値は２Ｈ、その１レベル下で同じ上位語を持つ「スポーツカー」とは３Ｈとなり、これらは非常に近い関係であり、概念距離は１になる。
【００４４】
一方、２レベル上位（祖父母関係）である「自動車」では、ビット排他論理和の値は４２Ｈであるが、その１レベル下位（おじ／おば）にあたる「バス」とは５２Ｈ、さらに１レベル下（いとこ）、すなわち同レベルの「ボンネットバス」では５０Ｈとなり、これらとの概念距離は２になる。さらに、前述の「パソコン」に対しては、ビット排他論理和の値は４Ｅ６６２Ｈとなり、概念距離は５である。
【００４５】
図８は、具体例における概念距離の一部を２次元にマッピングした概念図である。図８において、○はノードを示し、実線はシソーラス階層を示しており、高さが階層レベルを示している。ここで示したシソーラス階層は、図５に示したものの一部である。いま、「セダン」を基準とし、概念距離を２次元上の距離に対応させると、等しい概念距離のノードは、図８に示すように等距離の円弧上に配置して示すことができる。
【００４６】
なお、上述の例では、概念距離の計算にあたり、マスクコードによるＡＮＤを用いたが、論理的に同一であればさまざまな方法で実現し得る。図９は、概念距離のＯＲゲートによる算出法の説明図である。例えば、図９に示すように、同一階層に相当するビットのＯＲをとり、ＯＮとなる最上位ビットを概念距離とすることが考えられる。図９に示した例では、「セダン」と「パソコン」のシソーラスコードのビット排他論理和の値「４Ｅ６６２Ｈ」を４ビットごとにＯＲ回路に入力し、出力として「００１１１１１」を得る。この結果の最上位ビットの位置は５番目であるので、概念距離は５となる。この計算方法では、ワイヤードロジックにより簡単に回路を構成できるので、ハードウェア化に向いた方法ということができる。もちろん、他の方法を用いて演算してもよい。
【００４７】
また、この例では、この後に優先度を算出するために、０〜７に限定した概念距離を導入している。実際に上述のようにして、ある概念距離をもつ表現間のＸＯＲの演算を行なうと、その結果は特定の範囲（概念距離２の場合１０Ｈ〜ＦＦＨ）のみをとるので、例えば、単語間のおおざっぱな距離を求める場合には、ＸＯＲを計算した結果を直接用いてももちろんよい。
【００４８】
さらに、この実施の態様では、シソーラスの全階層に４ビットの固定長を割り当てているが、リーフに近付くにつれてノード数が増えるなどシソーラスの構造はさまざまである。このような場合には、各階層ごとに異なるビット数を割り当てればよく、記憶容量が限られている場合でも、これを有効に利用することが可能である。加えて、シソーラスにおいてはすべてのリーフデータが同じ階層レベルになるとは限らないが、本発明は異なる階層レベルにまたがるデータが比較可能であるため、このような場合においても非常に有効である。
【００４９】
続いて、優先度算出部３３ではＳ８５において、距離算出部３１で算出された概念距離と、階層差算出部３２で算出された階層レベル差に応じ、優先度を算出する。上述のように、概念距離と階層レベル差は直接関係はない。また、概念距離が同一でも、それらの間の類似度が異なることは多い。上述の図８に示すように、「セダン」に対して「自動車」と「ボンネットバス」はともに概念距離２であるが、類似度は「自動車」のほうが直接の孫であるため、類似度は高いと考えられる。一方、シソーラスの構成によっては上位ノードに対し下位ノードとして類義語が並ぶような場合もある。このような場合は同じ階層レベルの方が類似度が高くなる。このように、概念距離と階層レベル差を用いることにより、これらを別の軸として評価することができる。
【００５０】
この例では、優先度として、次のような計算式を用いる。
優先度 ＝ 総レベル数×２ − （概念距離×２ − レベル差）
ここで、この例では総レベル数は７としている。上述の図７に示した各キーワードでは、「セダン」に対し、次のような値が返される。
１４：セダン（７×２ − （０×２ − ０） ＝ １４）
１３：自家用車
１２：スポーツカー，自動車
１１：バス，車両，・・・
１０：ボンネットバス，オートバイ，・・・
・・・
５：パソコン，・・・
・・・
もちろん、上述の計算式のほか、種々の計算方法によって優先度を算出してもよい。
【００５１】
続いて、図３のＳ６７で、上述のようにして得られたマッチング結果を用いて、抽出基準のチェックを行なう。ここでは単純に優先度の値が１２以上の場合、適合結果とする。上述の図７に示した各キーワードの例では、文書が「セダン」、「自家用車」、「スポーツカー」、「自動車」のいずれかのキーワードを有していれば、結果バッファＢＦに出力される。
【００５２】
もちろん、この基準とする値は適宜設定すればよい。また、この抽出基準については、他の抽出基準を用いてもよい。例えば、必要に応じて文書全体を走査したのちに統計処理によって抽出基準に対して重みづけをするなどがある。
【００５３】
このようにして、検索要求と１つのキーワードとのマッチング処理および文書の抽出が終了する。ここまでの処理が１つの文書に付されているすべてのキーワードについて繰り返し、さらに、それらをデータベース５１中の各文書に対して順次行なうことで処理が進められる。
【００５４】
以上の処理により、結果バッファＢＦには、ユーザからの検索要求「セダン」に類似したキーワードを含む文書、具体的には「セダン」、「スポーツカー」、「ＲＶ車」、「自家用車」、「自動車」などを含む文書が蓄積される。この結果に対し、出力指示部３４は優先度に基づいた文書の出力指示を出力部４０に対して行なう。出力部４０は、検索結果を出力し、検索処理は終了する。
【００５５】
上述の類似語検索システムでは、マッチング部３０において、概念距離、階層レベル差、およびこれらから優先度を算出したが、例えば、概念距離のみを利用したり、概念距離と階層レベル差を利用するなど、これらのうちの一部の計算結果を利用してもよい。
【００５６】
本発明は、階層関係を持つデータ間の比較処理一般に適用でき、上述の類似語検索システムへの適用のみに限定されるものではないことは言うまでもない。以下、本発明のマッチング装置の１つの実施の態様を文書自動分類システムに適用した場合について述べる。
【００５７】
現在、自動分類においては、標本データを用いた自動分類が一般的な技術のひとつである。しかし、シソーラス展開を含めることは、コストの問題から従来は困難であった。本発明のマッチング装置を、標準データとのマッチングに適用することにより、低コストで自動分類が可能となる。
【００５８】
例えば、次のようなキーワードを持つ標本データ群（一部）に対して、ある文書を自動分類することを考える。
［標本１］
キーワード： 携帯，電話，自動車，ＰＨＳ
カテゴリ： 移動体電話
［標本２］
キーワード： 端末，反射，抵抗，遅延
カテゴリ： ターミネータ
［標本３］
キーワード： 携帯，端末，ＰＤＡ，ネットワーク
カテゴリ： 携帯端末
【００５９】
入力文書も同様にキーワードを持つとする。これは、あらかじめ付与されたものでも、その場で抽出したものでもかまわない。
［入力文書］
キーワード： モーバイル，端末，通信
【００６０】
ここで、シソーラス展開を含めた入力文書と各標本のキーワード間の類似度を求める。類似度の計算には、上述の類似語検索システムの場合と同様の方法を用いることができる。さらに、入力文書の各キーワードとの類似度がもっとも低いもの同士の和を求める。標本１〜３において計算した例を示す。
（標本１）
モーバイル：携帯＝１，端末：ＰＨＳ＝４，通信：電話＝２ 合計７
（標本２）
モーバイル：遅延＝６，端末：端末＝０，通信：遅延＝３ 合計９
（標本３）
モーバイル：携帯＝１，端末：端末＝０，通信：ネットワーク＝２ 合計３
【００６１】
こうして得られた和のもっとも小さい標本が、入力文書との類似度がもっとも高いと考えられるため、入力された文書を当該カテゴリに分類する。この例では、標本３において計算された和が最も小さいので、入力文書は標本３のカテゴリ「携帯端末」に分類される。以上の処理を入力文書すべてに対して順次行なことで自動分類が行なわれる。
【００６２】
なお、上述の各システムへの適用例においては、シソーラスを用いた例について述べたが、階層構造をなすデータは一般に広く用いられているため、本発明はファイルディレクトリなど、シソーラス以外のデータ間のマッチングにも適用することができる。
【００６３】
【発明の効果】
以上の説明から明らかなように、本発明によれば、シソーラスのような階層構造をなすデータ間での比較が、ＡＮＤ、ＸＯＲといった単純なビット論理演算をベースとする簡単な処理のみで高速に実行することが可能となる。また、ビット論理演算処理をベースとすることにより、ソフトウェアによる実現はもちろん、ハードウェア化も容易である。
【００６４】
本発明により、従来の共通上位ノードまでの階層数といった単純な処理では困難であった、階層の途中にまたがるようなデータ間の場合でも比較可能となった。加えて、階層レベル差を用いることにより、データの種類に応じたきめ細かな比較基準を設け、優先度づけを行なうことができる。
【００６５】
このように、従来困難であったシソーラス展開を含むマッチング処理が簡単に、しかも高速に実行できるので、本発明のマッチング処理を適用した例えば類似テキスト検索やテキスト自動分類などが、高速かつ低コストで実現可能となるという効果がある。
【図面の簡単な説明】
【図１】本発明のマッチング装置の１つの実施の態様を示す概略構成図である。
【図２】本発明のマッチング装置の１つの実施の態様を類似語検索システムに適用した場合の一例を示すブロック構成図である。
【図３】類似語検索システムの一例における全体の動作の一例を示すフローチャートである。
【図４】マッチングアルゴリズムの一例の概略を示すフローチャートである。
【図５】シソーラスの構成の具体例を示す説明図である。
【図６】シソーラスコードへの変換の一例を示す概念図である。
【図７】マッチング結果の具体例の説明図である。
【図８】具体例における概念距離の一部を２次元にマッピングした概念図である。
【図９】概念距離のＯＲゲートによる算出法の説明図である。
【符号の説明】
１…入力部、２…階層関係コード化部、３…マッチング部、４…出力部、１０…検索要求入力部、１１…端末、１２…ＯＣＲ、１３…電話および音声認識部、１４…記憶装置、１５…赤外線・無線受信部、２０…シソーラスコード化部、２１…シソーラス、３０…マッチング部、３１…距離算出部、３２…階層差算出部、３３…優先度算出部、３４…出力指示部、４０…出力部、４１…端末、４２…ファクシミリ／プリンタ、４３…電話・ポケベル、４４…赤外線・無線発信部、５０…データベース部、５１…データベース。
Claims (6)
- データ間の階層関係に基づくマッチングを行なうマッチング装置において、階層関係をもつデータ群の各データを各階層の同じ親を有する各データに対して順次割り振った値とともに保持し入力されたデータまで階層をたどったときのそれぞれの階層のデータに割り振られた値を並べたコードに変換する階層データコード化手段と、与えられた少なくとも二つのデータについての階層関係におけるデータ間の近さを示す概念距離として前記二つのデータから前記階層データコード化手段より得られたコードの排他的論理和と各階層の値のマスクコードとの論理積が非ゼロになる最大のマスクコードから該マスクコードに対応づけられている値を前記概念距離として算出する距離算出手段を有することを特徴とするマッチング装置。
- さらに、与えられた少なくとも二つのデータについて前記階層データコード化手段より得られたコードと各階層の値のマスクコードとの論理積が非ゼロになる最小のマスクコードから各データの階層レベルを求めて前記データ間の階層レベルの差を算出する階層差算出手段を有することを特徴とする請求項１に記載のマッチング装置。
- さらに、前記距離算出手段および前記階層差算出手段の結果に基づき優先度を算出する優先度算出手段を有することを特徴とする請求項２に記載のマッチング装置。
- データ間の階層関係に基づくマッチングを行なうマッチング方法において、階層関係をもつデータ群の各データを各階層の同じ親を有する各データに対して順次割り振った値とともに階層データコード化手段に保持しており、与えられた少なくとも二つのデータについて前記階層データコード化手段により該データまで階層をたどったときのそれぞれの階層のデータに割り振られた値を並べたコードに変換し、得られたコードの排他的論理和と各階層の値のマスクコードとの論理積が非ゼロになる最大のマスクコードから該マスクコードに対応づけられている値を距離算出手段で算出し、該値を階層関係におけるデータ間の近さを示す概念距離とすることを特徴とするマッチング方法。
- データ間の階層関係に基づくマッチングを行なうマッチング方法において、階層関係をもつデータ群の各データを各階層の同じ親を有する各データに対して順次割り振った値とともに階層データコード化手段に保持しており、与えられた少なくとも二つのデータについて前記階層データコード化手段により該データまで階層をたどったときのそれぞれの階層のデータに割り振られた値を並べたコードに変換し、得られたコードの排他的論理和と各階層の値のマスクコードとの論理積が非ゼロになる最大のマスクコードから該マスクコードに対応づけられている値を距離算出手段で算出して階層関係におけるデータ間の近さを示す概念距離とし、さらに、前記データについて前記階層データコード化手段により変換されたコードと各階層の値のマスクコードとの論理積が非ゼロになる最小のマスクコードから各データの階層レベルを求めて前記データ間の階層レベルの差を階層差算出手段で算出することを特徴とするマッチング方法。
- データ間の階層関係に基づくマッチングを行なうマッチング方法において、階層関係をもつデータ群の各データを各階層の同じ親を有する各データに対して順次割り振った値とともに階層データコード化手段に保持しており、与えられた少なくとも二つのデータについて前記階層データコード化手段により該データまで階層をたどったときのそれぞれの階層のデータに割り振られた値を並べたコードに変換し、得られたコードの排他的論理和と各階層の値のマスクコードとの論理積が非ゼロになる最大のマスクコードから該マスクコードに対応づけられている値を距離算出手段で算出して階層関係におけるデータ間の近さを示す概念距離とし、さらに、前記データについて前記階層データコード化手段により変換されたコードと各階層の値のマスクコードとの論理積が非ゼロになる最小のマスクコードから各データの階層レベルを求めて前記データ間の階層レベルの差を階層差算出手段で算出し、前記概念距離および前記階層レベルの差に基づいて優先度を優先度算出手段で算出することを特徴とするマッチング方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP19034395A JP3603395B2 (ja) | 1995-07-26 | 1995-07-26 | マッチング装置およびマッチング方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP19034395A JP3603395B2 (ja) | 1995-07-26 | 1995-07-26 | マッチング装置およびマッチング方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0944507A JPH0944507A (ja) | 1997-02-14 |
| JP3603395B2 true JP3603395B2 (ja) | 2004-12-22 |
Family
ID=16256624
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP19034395A Expired - Fee Related JP3603395B2 (ja) | 1995-07-26 | 1995-07-26 | マッチング装置およびマッチング方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3603395B2 (ja) |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3543469B2 (ja) * | 1996-02-07 | 2004-07-14 | 富士ゼロックス株式会社 | 文書情報検索装置 |
| JP2002041885A (ja) * | 2000-07-27 | 2002-02-08 | Ribnet Co Ltd | 賃貸不動産物件又は売買不動産物件の情報交換システム |
| CN1235408C (zh) * | 2001-02-12 | 2006-01-04 | 皇家菲利浦电子有限公司 | 生成和匹配多媒体内容的散列 |
| JP5076706B2 (ja) * | 2007-07-26 | 2012-11-21 | 富士ゼロックス株式会社 | 遠隔会議システム |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0528199A (ja) * | 1991-07-18 | 1993-02-05 | Canon Inc | 文書検索装置 |
| JPH0573615A (ja) * | 1991-09-17 | 1993-03-26 | Kobe Nippon Denki Software Kk | 階層構造型情報の管理方式 |
| JP2913969B2 (ja) * | 1991-12-16 | 1999-06-28 | 株式会社日立製作所 | 事例検索システムおよびその検索方法 |
| JPH07141381A (ja) * | 1993-11-19 | 1995-06-02 | Sharp Corp | 電子辞書表示装置 |
-
1995
- 1995-07-26 JP JP19034395A patent/JP3603395B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0944507A (ja) | 1997-02-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN112464641B (zh) | 基于bert的机器阅读理解方法、装置、设备及存储介质 | |
| US6539373B1 (en) | Contextual searching by determining intersections of search results | |
| US9355171B2 (en) | Clustering of near-duplicate documents | |
| US8244767B2 (en) | Composite locality sensitive hash based processing of documents | |
| US20020073068A1 (en) | System and method for rapidly identifying the existence and location of an item in a file | |
| WO1998039715A9 (en) | System and method for rapidly identifying the existence and location of an item in a file | |
| JP2002520712A (ja) | データ検索システムと方法およびサーチ・エンジンにおけるその使用 | |
| US6735600B1 (en) | Editing protocol for flexible search engines | |
| Bachteler et al. | Similarity filtering with multibit trees for record linkage | |
| CN102867049A (zh) | 一种基于单词查找树实现的汉语拼音快速分词方法 | |
| JP7082542B2 (ja) | 軌跡検索装置及び軌跡検索プログラム | |
| CN101996257A (zh) | 可重构路由交换平台构件的检索方法 | |
| JP3603395B2 (ja) | マッチング装置およびマッチング方法 | |
| CN119938884A (zh) | 一种大语言模型的文档检索增强方法、装置及设备 | |
| CN117573096B (zh) | 一种融合抽象语法树结构信息的智能代码补全方法 | |
| CN118689963A (zh) | 工单信息查询方法、装置、计算机设备和存储介质 | |
| CN112416431B (zh) | 一种基于编码序列表示的源代码片段成对比较方法 | |
| US20050060314A1 (en) | System and methods involving a data structure searchable with O(logN) performance | |
| JP3632359B2 (ja) | 情報検索装置 | |
| Hernández-Ketchul et al. | String representation of trivalent 2-stratifolds with trivial fundamental group | |
| US6785699B1 (en) | Prefix comparator | |
| CN101425061A (zh) | 概念关联网络的数据标签建构方法与系统 | |
| JP4895988B2 (ja) | 文書分類装置の余分構造減退方法 | |
| JPH09245045A (ja) | 鍵検索方法および装置 | |
| CN110134758A (zh) | 一种面向连续空间-模糊关键字查询的索引方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040217 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040416 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040525 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040723 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20040907 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20040920 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20071008 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20081008 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20091008 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20101008 Year of fee payment: 6 |
|
| LAPS | Cancellation because of no payment of annual fees |