JPH0944507A

JPH0944507A - マッチング装置

Info

Publication number: JPH0944507A
Application number: JP7190343A
Authority: JP
Inventors: Tadanobu Miyauchi; 忠信宮内; Yoshihiro Ueda; 良寛上田
Original assignee: Fuji Xerox Co Ltd
Current assignee: Fujifilm Business Innovation Corp
Priority date: 1995-07-26
Filing date: 1995-07-26
Publication date: 1997-02-14
Anticipated expiration: 2015-07-26
Also published as: JP3603395B2

Abstract

(57)【要約】【課題】シソーラスにおける単語間のマッチングを、
高速かつ少ないデータサイズで効率的に行なうマッチン
グ装置を提供する。【解決手段】階層関係コード化部２には、あらかじ
め、単語とその単語の階層間の位置にしたがって付与さ
れたコードが格納されている。入力部１から比較すべき
データが与えられると、階層関係コード化部２は、入力
されたデータに応じてコードを返す。マッチング部３
は、入力部１から与えられた複数のデータを、階層関係
コード化部２から得られるコードを用いて、ビット論理
演算を行なう。このビット論理演算によって、階層関係
における概念距離や、階層レベル差等を算出し、さら
に、これらをもとに優先度を算出する。マッチング結果
は、出力部４から出力される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、データのマッチン
グの度合いを算出するマッチング装置に関連するもので
あり、特に、データ間の階層関係に基づくマッチング装
置に関するものである。

【０００２】

【従来の技術】従来より、テキスト検索や自動分類の研
究が活発に行なわれている。こうした分野において、シ
ソーラスと呼ばれる単語間の上位／下位関係および類義
語を定義した辞書の重要性がますます高まっている。

【０００３】テキスト検索においては、ユーザの入力し
た表現が検索対象中の表現と一致しないことがしばしば
発生する。このため、検索された内容のヒット率を確保
するために、類義語や上位／下位語を含めた検索が必要
である。そこで、シソーラスを用いることにより検索要
求の単語を展開する手法などがよく用いられる。

【０００４】一般的には、検索時に検索要求に基づきシ
ソーラスの階層をたどり、得られた類義語または上位／
下位語のそれぞれを用いて検索がなされる。このとき、
検索のたびに毎回シソーラスの階層をたどったのでは検
索速度が低下するため、例えば、特開平２−２８０２７
４号公報の「データベース検索システムの包括検索方
式」で述べられているように、あらかじめシソーラスの
上位／下位などを含めた包括インデックスを作成し、検
索時の速度低下を防ごうとする技術などが提案されてい
る。

【０００５】しかしながら、このような包括インデック
スを保持したとしても、包括インデックスに含まれる複
数のデータベースキーに基づいた検索を行なう必要があ
るため、依然として単純一致検索に比べて速度の低下は
発生する。また、こうした包括インデックス情報を予め
作成しておく必要があるため、データ量やデータベース
構築時のコストの増加を招くという問題もある。

【０００６】例えば、検索キーとキーワード間でシソー
ラスを考慮したマッチングを行ない、マッチング度合い
によって検索結果とするか否かを判定することも考えら
れるが、従来のマッチング手法では、マッチングの計算
に時間がかかり、検索で用いることができる技術ではな
かった。

【０００７】一方、テキストの自動分類と呼ばれる分野
では、なんらかの基準を用いてテキスト間の意味的な距
離を用いることにより、テキストの分類が行なわれる。
このとき、テキスト間の距離を求めるためにもシソーラ
スが用いられる。

【０００８】例えば、情報処理，Ｖｏｌ．３６，Ｎｏ．
２，１９９５．２，飯田，「人工知能におけるスーパー
コンピューティング」，ｐｐ．１６４−１６８において
は、句同士の間の距離を求める技術の一環として、概念
階層を用いた単語間の距離計算方法が示されており、入
力と用例間の意味距離が、あらかじめ付与された１０進
シソーラスコードの照合により計算されている。

【０００９】しかしながら、この計算法は共通の上位ノ
ードへの距離のみによる計算であるため、木構造のリー
フ（葉）であり、同一階層に並ぶ単語間の距離しか計算
できない。単語はすべて同一レベルのリーフとして表現
されるわけではないので、階層の途中の概念やリーフま
での階層数が異なる場合には適用できない。したがっ
て、単語間の距離の比較においては、このような単純な
方法では依然充分ではない。また、並列計算機を想定し
ているため、効率的な距離計算には連想メモリなど特殊
な処理を必要とし、現在のところ一般的でない。

【００１０】このように、従来の技術においては、シソ
ーラスにおける単語間のマッチングを効率的に行なうに
は、依然不十分な技術しか存在しなかった。

【００１１】

【発明が解決しようとする課題】本発明は、上述した事
情に鑑みてなされたものであり、特に、シソーラスにお
ける単語間のマッチングを、高速かつ少ないデータサイ
ズで効率的に行なうマッチング装置を提供することを目
的とするものである。

【００１２】

【課題を解決するための手段】本発明は、データ間の階
層関係に基づく類似度を算出するマッチング装置におい
て、階層関係をもつデータ群の各データを階層関係に応
じたコードとともに保持し入力に応じたコードに変換す
る階層データコード化手段と、与えられた少なくとも二
つのデータについて前記階層データコード化手段より得
られたコードに基づき論理演算により階層関係における
距離を算出する距離算出手段を有することを特徴とする
ものである。

【００１３】さらに、請求項２に記載の発明のように、
与えられた少なくとも二つのデータについて前記階層デ
ータコード化手段より得られたコードに基づき論理演算
により階層レベルの差を算出する階層差算出手段を設け
ることができる。

【００１４】さらに、請求項３に記載の発明のように、
前記距離算出手段および前記階層差算出手段の結果に基
づき優先度を算出する優先度算出手段を設けることがで
きる。

【００１５】

【作用】本発明によれば、階層関係をもつデータ群の各
データに対して、階層関係に応じたコードを保持させて
おく。そして、与えられた少なくとも二つのデータにつ
いて、対応するコードを得て、そのコードに基づき論理
演算により階層関係における距離を算出する。これによ
り、従来のように算術演算など、時間のかかる演算を行
なうことなく距離計算を行なうことができ、データ間の
階層関係に基づくマッチングが高速かつ容易に実現可能
となる。また、請求項２および請求項３に記載の発明の
ように、用途に応じ、階層差算出手段や、さらに優先度
算出手段を設けるなど、種々の構成をとることで、階層
レベル差や優先度といったよりきめ細かな比較が可能と
なる。

【００１６】

【発明の実施の態様】図１は、本発明のマッチング装置
の１つの実施の態様を示す概略構成図である。図中、１
は入力部、２は階層関係コード化部、３はマッチング
部、４は出力部である。入力部１は、比較すべきデータ
を与える。階層関係コード化部２は、入力に応じて、あ
らかじめ階層間の位置にしたがって付与されたコードを
返す。マッチング部３は、入力部１から与えられた複数
のデータを、階層関係コード化部２から得られるコード
を用いてビット論理演算でマッチングを行なう。出力部
４は、マッチング部３により得られた結果を出力する。

【００１７】図２は、本発明のマッチング装置の１つの
実施の態様を類似語検索システムに適用した場合の一例
を示すブロック構成図である。図中、１０は検索要求入
力部、１１は端末、１２はＯＣＲ、１３は電話および音
声認識部、１４は記憶装置、１５は赤外線・無線受信
部、２０はシソーラスコード化部、２１はシソーラス、
３０はマッチング部、３１は距離算出部、３２は階層差
算出部、３３は優先度算出部、３４は出力指示部、４０
は出力部、４１は端末、４２はファクシミリやプリン
タ、４３は電話やポケベル、４４は赤外線・無線発信
部、５０はデータベース部、５１はデータベースであ
る。検索要求入力部１０は、図１に示した入力部１に対
応し、同様に、シソーラスコード化部２０は階層関係コ
ード化部２に、マッチング部３０はマッチング部３に、
出力部４０は出力部４にそれぞれ対応する。データベー
ス部５０は、検索対象となる各種の文書を電子的に記憶
する部分であり、文書はデータベース５１に記憶され
る。

【００１８】検索要求入力部１０は、例えば、端末１
１、ＯＣＲ１２、音声を入力するマイクなどを具備した
電話および音声認識部１３、メモリやディスク、テープ
等の記憶装置１４、携帯情報機器などからの赤外線や無
線を受信する赤外線・無線受信部１５などから構成され
ている。もちろん、これらのうちの一部でもよいし、こ
れ以外の入力装置を用いるようにしてもよい。

【００１９】出力部４０は、端末４１のディスプレイ、
ファクシミリ／プリンタ４２、音声合成によりスピーカ
から出力する電話やポケベル４３、携帯情報機器へ赤外
線や無線を用いて情報を伝送する赤外線・無線発信部４
４などから構成される。もちろん、これらの一部で構成
してもよいし、これ以外の出力装置を用いるようにして
もよく、いったんネットワーク等に接続された記憶装置
に蓄えるように構成してもよい。

【００２０】シソーラスコード化部２０は、入力された
単語に応じて、シソーラス２１の階層構造に応じて保持
されたコードに変換する部分である。

【００２１】マッチング部３０は、入力された単語とデ
ータベース５１中の文書のキーワードを比較し、検索要
求に一致あるいは類似したキーワードを有する文書を出
力指示する部分である。距離算出部３１は、シソーラス
コード化部２０で変換された検索要求と文書のキーワー
ドのコード同士を論理演算し、階層関係における距離を
算出する部分である。階層差算出部３２は、シソーラス
コード化部２０で変換された検索要求と文書のキーワー
ドのコード同士を論理演算し、階層レベルの差を算出す
る部分である。優先度算出部３３は、距離算出部および
階層差算出部の結果に基づき、マッチング結果の優先度
を算出する部分である。出力指示部３４は、優先度算出
部３３で得られた結果に基づき、データベース部５０か
ら検索要求に一致または類似したキーワードを有する文
書を取り出し、出力部４０に出力を指示する。

【００２２】図３は、類似語検索システムの一例におけ
る全体の動作の一例を示すフローチャート、図４は、マ
ッチングアルゴリズムの一例の概略を示すフローチャー
トである。まず、Ｓ６１において、検索要求入力部１０
からユーザの検索要求ＲＱが入力されると、Ｓ６２にお
いて、シソーラスコード化部２０でシソーラスコードへ
の変換が行なわれ、検索要求のシソーラスコードＣ１が
得られる。

【００２３】続いて、Ｓ６３において、検索対象となる
データベース５１より一つの文書ＤＱが取り出される。
さらに、Ｓ６４において、この文書のキーワードＫＷを
順次取り出す。キーワードは、検索時にその場で文書中
から抽出してもよいし、検索の高速性が必要であれば、
あらかじめ文書に手動または自動で付与されたものを用
いればよい。Ｓ６５において、キーワードＫＷは、検索
要求ＲＱと同様に、シソーラスコード化部２０でコード
変換され、キーワードのシソーラスコードＣ２が得られ
る。

【００２４】検索要求のシソーラスコードＣ１とキーワ
ードのシソーラスコードＣ２がともに得られると、Ｓ６
６において、コードのマッチングが行なわれる。まず、
階層差算出部３２は、Ｓ８１において、検索要求のシソ
ーラスコードＣ１の階層レベルを論理演算によって求
め、検索要求の階層レベルＬ１とする。同様に、Ｓ８２
において、キーワードのシソーラスコードＣ２の階層レ
ベルを論理演算によって求め、キーワードの階層レベル
Ｌ２とする。Ｓ８３において、検索要求の階層レベルＬ
１とキーワードの階層レベルＬ２の差を求め、階層レベ
ル差ＬＤとする。続いて、距離算出部３１は、Ｓ８４に
おいて、検索要求のシソーラスコードＣ１とキーワード
のシソーラスコードＣ２のビット排他論理和を計算し、
概念距離ＣＤとする。さらに、優先度算出部３３は、Ｓ
８５において、抽出された階層レベル差ＬＤと概念距離
ＣＤに応じて優先度ＰＬを算出する。

【００２５】このようにしてコードのマッチングが行な
われると、得られた階層レベル差ＬＤ、概念距離ＣＤ、
優先度ＰＬなどが基準を満たしているか否かを、Ｓ６７
でチェックする。Ｓ６８で基準を満たしていると判定さ
れれば、出力指示部３４は、Ｓ６９で結果バッファＢＦ
に文書ＤＱを出力する。もちろん、出力部４０に直接出
力指示を行なってもよい。

【００２６】Ｓ７０において、現在処理中の文書に付与
されているキーワードがすべて処理されたか否かを判定
し、最後のキーワードの処理が終了するまで、Ｓ６４〜
Ｓ７０の処理を繰り返し行なう。１つの文書について、
すべてのキーワードの処理が終了すると、Ｓ７１におい
て、すべての文書について処理を行なったか否かを判定
し、最後の文書の処理が終了するまで、Ｓ６３〜Ｓ７０
の処理を繰り返し行なう。

【００２７】このような処理を行なうことによって、検
索要求に一致あるいは類似したキーワードを有する文書
が検索され、出力されることになる。上述のように、マ
ッチング処理では階層差や概念距離を、論理演算を用い
て行なっているので、高速にマッチング処理を行なうこ
とができる。そのため、従来のようにシソーラス階層を
たどったり、包括インデックスを用いることなどもな
く、少ないデータサイズで高速な類似語検索を実現する
ことができる。

【００２８】以下、具体例を用いて、上述の動作の一例
を説明する。図５は、シソーラスの構成の具体例を示す
説明図である。例えば、「自家用車」という単語は、
「自動車」の下位概念であり、「スポーツカー」、「セ
ダン」、「ＲＶ車」などの上位概念を表わす。それぞれ
の単語には、図中の角カッコ“［］”内に示すように、
各階層の同じ親を有する各単語について、レベル１から
始まるコードを順次割り振る。ここでは一つの階層につ
き２進４ビットを用い、１６進数で示している。

【００２９】実際に各単語に割り当てられるコードの例
の一部も、図中の丸カッコ“（）”内に示している。例
えば、「自家用車」という単語においては、具体物［２］→機械［３］→乗物［Ａ］→車両［２］→
自動車［４］→自家用車［４］という階層をたどり、さらに１レベルの下位データを持
つため、これを［０］と表わし、「２３Ａ２４４０Ｈ」
という４バイトの１６進コードを割り当てる。ここで、
末尾の‘Ｈ’は、１６進数であることを示しており、１
６進の「２３Ａ２４４０」という値を示している。同様
に、「自家用車」の下位に位置し、末端のデータである
「セダン」という単語には、「２３Ａ２４４２Ｈ」とい
うコードを割り当てる。ここでは各ノードが１５個以下
の８階層としたため、４ビット７レベルのコードを用い
たが、もちろんこの割り当ては自由であり、シソーラス
の構造に応じて設計すればよい。なお、この割り当て
は、シソーラスの階層構造をトラバースすることにより
容易に自動的化できるため、人手によるコード付与など
の手間を排除することが可能である。

【００３０】図３のＳ６１で入力された検索要求ＲＱ
は、Ｓ６２において、シソーラスコードＣ１へ変換され
る。図６は、シソーラスコードへの変換の一例を示す概
念図である。ここでは、データ構造として特開平５−２
８１９４号公報の「データアクセス方式」に述べられて
いるような、ハッシングを用いた例を示す。入力された
データは、ハッシュ関数によって得られたハッシュ値を
もとにハッシュテーブルを参照する。ここでは、ハッシ
ュテーブルにはチェインインデックスへのポインタが格
納されており、このポインタをもとにチェインインデッ
クスを参照し、このチェインインデックスで衝突をチェ
ックした後、変換データが参照される。変換データに
は、単語に対応するコードが格納されており、入力デー
タに対応するコードが得られる。

【００３１】例えば、「セダン」というデータが入力さ
れると、ハッシュ関数によりハッシュ値が得られ、これ
をもとにハッシュテーブルが参照され、さらにチェイン
インデックにより衝突がチェックされた後、シソーラス
コードＣ１として「２３Ａ２４４２Ｈ」が得られる。ま
た、図６に示したように、「オートバイ」と「バイク」
などの同義語は、入力データとしては異なるが、変換に
より同一化されたコードとなる。このように、シソーラ
スにおける階層関係をたどる必要なしに、直接、データ
からコードを得ることができる。

【００３２】なお、ここではハッシュ法を用いた例につ
いて説明したが、ＢＴｒｅｅなど、他のデータ構造を用
いてもよいことはもちろんである。

【００３３】このようにして、入力された検索要求ＲＱ
は、ハッシュ関数により変換され、ハッシュテーブルと
チェインインデックスをたどることにより、シソーラス
コードＣ１に変換される。続いて、Ｓ６３で検索対象と
なるデータベース５１より文書が１つ取り出され、さら
にＳ６４でこの文書のキーワードが取り出される。ここ
では、キーワードＫＷとして「パソコン」が取り出され
たとする。キーワードＫＷは、Ｓ６５で上述と同様の方
法によりシソーラスコード化部２０でコード変換され
る。たとえばキーワードが「パソコン」の場合には、図
５に示すように、「２３ＥＣ２２０Ｈ」というシソーラ
スコードに変換される。

【００３４】検索要求のシソーラスコードＣ１と、キー
ワードのシソーラスコードＣ２がともに得られると、Ｓ
６６でコードのマッチングが行なわれる。マッチング
は、大きく階層差算出部３２におけるレベル差の計算
と、距離算出部３１における概念距離の計算に分けられ
る。

【００３５】まず、階層差算出部３２は、Ｓ８１，Ｓ８
２において、検索要求のシソーラスコードＣ１とキーワ
ードのシソーラスコードＣ２の階層レベルを計算する。
具体的には、次に示すような４ビット単位のマスクコー
ドを用意し、検索要求のシソーラスコードＣ１およびキ
ーワードのシソーラスコードＣ２とのＡＮＤを順次と
り、非ゼロになるまで繰り返すことでレベルが決定され
る。なお、レベル１までのＡＮＤがすべて０であった場
合、すなわちＣ１またはＣ２のコードが０の場合、それ
はシソーラスの根、この場合「概念」であるからレベル
は０となる。レベル７：００００００ＦＨレベル６：０００００Ｆ０Ｈレベル５：００００Ｆ００Ｈレベル４：０００Ｆ０００Ｈレベル３：００Ｆ００００Ｈレベル２：０Ｆ０００００Ｈレベル１：Ｆ００００００Ｈ

【００３６】「セダン」に関するコードは、上述のよう
に「２３Ａ２４４２Ｈ」であったから、まず０００００
０ＦＨとのＡＮＤを取ると、００００００ＦＨＡＮＤ２３Ａ２４４２Ｈ＝２Ｈとなり、非ゼロであるのでレベル７の単語であることが
わかり、終了する。

【００３７】「パソコン」に関するコードは、上述のよ
うに「２３ＥＣ２２０Ｈ」であったから、まず００００
００ＦＨとのＡＮＤを取ると、００００００ＦＨＡＮＤ２３ＥＣ２２０Ｈ＝０Ｈとなり、ゼロであるので、さらに０００００Ｆ０Ｈとの
ＡＮＤを取る。すると、０００００Ｆ０ＨＡＮＤ２３ＥＣ２２０Ｈ＝２０Ｈとなり、非ゼロであるので、レベル６の単語であること
がわかり、終了する。

【００３８】ここでは、ＡＮＤによるマスクを用いた方
法を述べたが、レベルに応じたビット数、例えば、レベ
ル７の場合４ビットだけ右シフトし、下位桁あふれフラ
グをチェックするなどの方法でも、もちろん論理的に同
一になる。いずれにせよ、これらのビット単位の論理演
算は、一般に非常に高速に実行可能であるため、処理の
高速化を実現することが可能である。

【００３９】こうして得られた階層レベルの差の絶対値
をＳ８３で計算し、階層レベル差ＬＤとする。ここでは
｜７−６｜＝１となる。

【００４０】続いて、距離算出部３１において、単語間
の概念距離が計算される。概念距離は、コード間のビッ
ト排他的論理和（ＸＯＲ）に基づいて求められる。ここ
では、２３Ａ２４４２ＨＸＯＲ２３ＥＣ２２０Ｈ＝４Ｅ６６２Ｈとなる。こうして得られる値は、単語（概念）間のいわ
ば近さを示す。概念距離はここで得られた値の範囲に応
じて付与する。この付与には、上述の階層レベルチェッ
クと同様に、次に示すマスクコードとのＡＮＤで非ゼロ
になる最小のものとして、容易に求められる。なお、Ｘ
ＯＲの結果が全ビット０の場合、同一のコードであるか
ら概念距離は０となる。概念距離７：Ｆ００００００Ｈ概念距離６：０Ｆ０００００Ｈ概念距離５：００Ｆ００００Ｈ概念距離４：０００Ｆ０００Ｈ概念距離３：００００Ｆ００Ｈ概念距離２：０００００Ｆ０Ｈ概念距離１：００００００ＦＨ

【００４１】ここでは、ビット排他論理和の値が「４Ｅ
６６２Ｈ」であるので、Ｆ００００００ＨＡＮＤ４Ｅ６６２Ｈ＝０Ｈ０Ｆ０００００ＨＡＮＤ４Ｅ６６２Ｈ＝０Ｈ００Ｆ００００ＨＡＮＤ４Ｅ６６２Ｈ＝４００００Ｈとなり、概念距離＝５であることがわかる。

【００４２】図７は、マッチング結果の具体例の説明図
である。図７には、「セダン」を検索要求として、各キ
ーワードと、そのキーワードのシソーラスコードＣ２、
「セダン」のシソーラスコードＣ１「２３Ａ２４４２
Ｈ」とのビット排他論理和の値、概念距離、レベル差、
優先度について示している。優先度については、後で再
びこの図を参照して説明する。

【００４３】図７に示すように、概念距離はレベル差と
は直接関係ない。例えば、「セダン」に関し、１レベル
上位（親子関係）である「自家用車」とのビット排他論
理和の値は２Ｈ、その１レベル下で同じ上位語を持つ
「スポーツカー」とは３Ｈとなり、これらは非常に近い
関係であり、概念距離は１になる。

【００４４】一方、２レベル上位（祖父母関係）である
「自動車」では、ビット排他論理和の値は４２Ｈである
が、その１レベル下位（おじ／おば）にあたる「バス」
とは５２Ｈ、さらに１レベル下（いとこ）、すなわち同
レベルの「ボンネットバス」では５０Ｈとなり、これら
との概念距離は２になる。さらに、前述の「パソコン」
に対しては、ビット排他論理和の値は４Ｅ６６２Ｈとな
り、概念距離は５である。

【００４５】図８は、具体例における概念距離の一部を
２次元にマッピングした概念図である。図８において、
○はノードを示し、実線はシソーラス階層を示してお
り、高さが階層レベルを示している。ここで示したシソ
ーラス階層は、図５に示したものの一部である。いま、
「セダン」を基準とし、概念距離を２次元上の距離に対
応させると、等しい概念距離のノードは、図８に示すよ
うに等距離の円弧上に配置して示すことができる。

【００４６】なお、上述の例では、概念距離の計算にあ
たり、マスクコードによるＡＮＤを用いたが、論理的に
同一であればさまざまな方法で実現し得る。図９は、概
念距離のＯＲゲートによる算出法の説明図である。例え
ば、図９に示すように、同一階層に相当するビットのＯ
Ｒをとり、ＯＮとなる最上位ビットを概念距離とするこ
とが考えられる。図９に示した例では、「セダン」と
「パソコン」のシソーラスコードのビット排他論理和の
値「４Ｅ６６２Ｈ」を４ビットごとにＯＲ回路に入力
し、出力として「００１１１１１」を得る。この結果の
最上位ビットの位置は５番目であるので、概念距離は５
となる。この計算方法では、ワイヤードロジックにより
簡単に回路を構成できるので、ハードウェア化に向いた
方法ということができる。もちろん、他の方法を用いて
演算してもよい。

【００４７】また、この例では、この後に優先度を算出
するために、０〜７に限定した概念距離を導入してい
る。実際に上述のようにして、ある概念距離をもつ表現
間のＸＯＲの演算を行なうと、その結果は特定の範囲
（概念距離２の場合１０Ｈ〜ＦＦＨ）のみをとるので、
例えば、単語間のおおざっぱな距離を求める場合には、
ＸＯＲを計算した結果を直接用いてももちろんよい。

【００４８】さらに、この実施の態様では、シソーラス
の全階層に４ビットの固定長を割り当てているが、リー
フに近付くにつれてノード数が増えるなどシソーラスの
構造はさまざまである。このような場合には、各階層ご
とに異なるビット数を割り当てればよく、記憶容量が限
られている場合でも、これを有効に利用することが可能
である。加えて、シソーラスにおいてはすべてのリーフ
データが同じ階層レベルになるとは限らないが、本発明
は異なる階層レベルにまたがるデータが比較可能である
ため、このような場合においても非常に有効である。

【００４９】続いて、優先度算出部３３ではＳ８５にお
いて、距離算出部３１で算出された概念距離と、階層差
算出部３２で算出された階層レベル差に応じ、優先度を
算出する。上述のように、概念距離と階層レベル差は直
接関係はない。また、概念距離が同一でも、それらの間
の類似度が異なることは多い。上述の図８に示すよう
に、「セダン」に対して「自動車」と「ボンネットバ
ス」はともに概念距離２であるが、類似度は「自動車」
のほうが直接の孫であるため、類似度は高いと考えられ
る。一方、シソーラスの構成によっては上位ノードに対
し下位ノードとして類義語が並ぶような場合もある。こ
のような場合は同じ階層レベルの方が類似度が高くな
る。このように、概念距離と階層レベル差を用いること
により、これらを別の軸として評価することができる。

【００５０】この例では、優先度として、次のような計
算式を用いる。優先度＝総レベル数×２ − （概念距離×２ − レベル差）ここで、この例では総レベル数は７としている。上述の
図７に示した各キーワードでは、「セダン」に対し、次
のような値が返される。１４：セダン（７×２ − （０×２ − ０）＝１４）１３：自家用車１２：スポーツカー，自動車１１：バス，車両，・・・１０：ボンネットバス，オートバイ，・・・・・・５：パソコン，・・・・・・もちろん、上述の計算式のほか、種々の計算方法によっ
て優先度を算出してもよい。

【００５１】続いて、図３のＳ６７で、上述のようにし
て得られたマッチング結果を用いて、抽出基準のチェッ
クを行なう。ここでは単純に優先度の値が１２以上の場
合、適合結果とする。上述の図７に示した各キーワード
の例では、文書が「セダン」、「自家用車」、「スポー
ツカー」、「自動車」のいずれかのキーワードを有して
いれば、結果バッファＢＦに出力される。

【００５２】もちろん、この基準とする値は適宜設定す
ればよい。また、この抽出基準については、他の抽出基
準を用いてもよい。例えば、必要に応じて文書全体を走
査したのちに統計処理によって抽出基準に対して重みづ
けをするなどがある。

【００５３】このようにして、検索要求と１つのキーワ
ードとのマッチング処理および文書の抽出が終了する。
ここまでの処理が１つの文書に付されているすべてのキ
ーワードについて繰り返し、さらに、それらをデータベ
ース５１中の各文書に対して順次行なうことで処理が進
められる。

【００５４】以上の処理により、結果バッファＢＦに
は、ユーザからの検索要求「セダン」に類似したキーワ
ードを含む文書、具体的には「セダン」、「スポーツカ
ー」、「ＲＶ車」、「自家用車」、「自動車」などを含
む文書が蓄積される。この結果に対し、出力指示部３４
は優先度に基づいた文書の出力指示を出力部４０に対し
て行なう。出力部４０は、検索結果を出力し、検索処理
は終了する。

【００５５】上述の類似語検索システムでは、マッチン
グ部３０において、概念距離、階層レベル差、およびこ
れらから優先度を算出したが、例えば、概念距離のみを
利用したり、概念距離と階層レベル差を利用するなど、
これらのうちの一部の計算結果を利用してもよい。

【００５６】本発明は、階層関係を持つデータ間の比較
処理一般に適用でき、上述の類似語検索システムへの適
用のみに限定されるものではないことは言うまでもな
い。以下、本発明のマッチング装置の１つの実施の態様
を文書自動分類システムに適用した場合について述べ
る。

【００５７】現在、自動分類においては、標本データを
用いた自動分類が一般的な技術のひとつである。しか
し、シソーラス展開を含めることは、コストの問題から
従来は困難であった。本発明のマッチング装置を、標準
データとのマッチングに適用することにより、低コスト
で自動分類が可能となる。

【００５８】例えば、次のようなキーワードを持つ標本
データ群（一部）に対して、ある文書を自動分類するこ
とを考える。［標本１］キーワード：携帯，電話，自動車，ＰＨＳカテゴリ：移動体電話［標本２］キーワード：端末，反射，抵抗，遅延カテゴリ：ターミネータ［標本３］キーワード：携帯，端末，ＰＤＡ，ネットワークカテゴリ：携帯端末

【００５９】入力文書も同様にキーワードを持つとす
る。これは、あらかじめ付与されたものでも、その場で
抽出したものでもかまわない。［入力文書］キーワード：モーバイル，端末，通信

【００６０】ここで、シソーラス展開を含めた入力文書
と各標本のキーワード間の類似度を求める。類似度の計
算には、上述の類似語検索システムの場合と同様の方法
を用いることができる。さらに、入力文書の各キーワー
ドとの類似度がもっとも低いもの同士の和を求める。標
本１〜３において計算した例を示す。（標本１）モーバイル：携帯＝１，端末：ＰＨＳ＝４，通信：電話
＝２合計７（標本２）モーバイル：遅延＝６，端末：端末＝０，通信：遅延＝
３合計９（標本３）モーバイル：携帯＝１，端末：端末＝０，通信：ネット
ワーク＝２合計３

【００６１】こうして得られた和のもっとも小さい標本
が、入力文書との類似度がもっとも高いと考えられるた
め、入力された文書を当該カテゴリに分類する。この例
では、標本３において計算された和が最も小さいので、
入力文書は標本３のカテゴリ「携帯端末」に分類され
る。以上の処理を入力文書すべてに対して順次行なこと
で自動分類が行なわれる。

【００６２】なお、上述の各システムへの適用例におい
ては、シソーラスを用いた例について述べたが、階層構
造をなすデータは一般に広く用いられているため、本発
明はファイルディレクトリなど、シソーラス以外のデー
タ間のマッチングにも適用することができる。

【００６３】

【発明の効果】以上の説明から明らかなように、本発明
によれば、シソーラスのような階層構造をなすデータ間
での比較が、ＡＮＤ、ＸＯＲといった単純なビット論理
演算をベースとする簡単な処理のみで高速に実行するこ
とが可能となる。また、ビット論理演算処理をベースと
することにより、ソフトウェアによる実現はもちろん、
ハードウェア化も容易である。

【００６４】本発明により、従来の共通上位ノードまで
の階層数といった単純な処理では困難であった、階層の
途中にまたがるようなデータ間の場合でも比較可能とな
った。加えて、階層レベル差を用いることにより、デー
タの種類に応じたきめ細かな比較基準を設け、優先度づ
けを行なうことができる。

【００６５】このように、従来困難であったシソーラス
展開を含むマッチング処理が簡単に、しかも高速に実行
できるので、本発明のマッチング処理を適用した例えば
類似テキスト検索やテキスト自動分類などが、高速かつ
低コストで実現可能となるという効果がある。

【図面の簡単な説明】

【図１】本発明のマッチング装置の１つの実施の態様
を示す概略構成図である。

【図２】本発明のマッチング装置の１つの実施の態様
を類似語検索システムに適用した場合の一例を示すブロ
ック構成図である。

【図３】類似語検索システムの一例における全体の動
作の一例を示すフローチャートである。

【図４】マッチングアルゴリズムの一例の概略を示す
フローチャートである。

【図５】シソーラスの構成の具体例を示す説明図であ
る。

【図６】シソーラスコードへの変換の一例を示す概念
図である。

【図７】マッチング結果の具体例の説明図である。

【図８】具体例における概念距離の一部を２次元にマ
ッピングした概念図である。

【図９】概念距離のＯＲゲートによる算出法の説明図
である。

【符号の説明】

１…入力部、２…階層関係コード化部、３…マッチング
部、４…出力部、１０…検索要求入力部、１１…端末、
１２…ＯＣＲ、１３…電話および音声認識部、１４…記
憶装置、１５…赤外線・無線受信部、２０…シソーラス
コード化部、２１…シソーラス、３０…マッチング部、
３１…距離算出部、３２…階層差算出部、３３…優先度
算出部、３４…出力指示部、４０…出力部、４１…端
末、４２…ファクシミリ／プリンタ、４３…電話・ポケ
ベル、４４…赤外線・無線発信部、５０…データベース
部、５１…データベース。

Claims

【特許請求の範囲】

【請求項１】データ間の階層関係に基づく類似度を算
出するマッチング装置において、階層関係をもつデータ
群の各データを階層関係に応じたコードとともに保持し
入力に応じたコードに変換する階層データコード化手段
と、与えられた少なくとも二つのデータについて前記階
層データコード化手段より得られたコードに基づき論理
演算により階層関係における距離を算出する距離算出手
段を有することを特徴とするマッチング装置。
【請求項２】さらに、与えられた少なくとも二つのデ
ータについて前記階層データコード化手段より得られた
コードに基づき論理演算により階層レベルの差を算出す
る階層差算出手段を有することを特徴とする請求項１に
記載のマッチング装置。
【請求項３】さらに、前記距離算出手段および前記階
層差算出手段の結果に基づき優先度を算出する優先度算
出手段を有することを特徴とする請求項２に記載のマッ
チング装置。