(57)【特許請求の範囲】
【請求項１】
文字列の類似性を判定する類似情報照合装置において、
入力された検索文から検索文字列を生成する検索データ生成部と、
文書が記憶された記憶装置から被検索文字列を生成する被照合データ生成部と、
検索文字列の各文字と被検索文字列の各文字を２次元配列に対応付ける照合マップを生成し、対応づけられた文字が一致する照合位置の座標を取得する照合マップ生成部と、
所定の前記照合位置を起点に有効距離内の前記照合位置を連結したリンク、及び、前記リンクの終端の前記照合位置と始端の前記照合位置が一致する、一連の前記リンクを接続した経路を生成し、
前記リンクの始端と終端に対応する文字の記号種の組み合わせに応じた重み付けとリンクの長さによる重み付けがされたリンク毎の評価値Ｖｋを決定し、前記経路上の全てのリンクの評価値Ｖｋを加算した評価値Ｖを当該経路を形成した各照合文字の評価値Ｖｘｙとし、検索文字列の評価値Ｖｘｙを加算した値を評価値Ｖｔとする連続性評価部と、
評価値Ｖｔの大きさに基づき検索文字列と被検索文字列の合致度を判定するパターン照合部と、
を有することを特徴とする類似情報照合装置。
【請求項２】
前記パターン照合部は、検索文字列と被検索文字列が完全に一致した場合の評価値により評価値Ｖｔを除して、合致度を算出する、
ことを特徴とする請求項１記載の類似情報照合装置。
【請求項３】
前記パターン照合部は、照合位置毎に該照合位置を通過する前記経路に対し得られた評価値Ｖの中で最も高い評価値Ｖとなる照合位置を選択して、各照合文字の評価値Ｖｘｙを決定する、
ことを特徴とする請求項１又は２記載の類似情報照合装置。
【請求項４】
入力された検索文字列の少なくとも一部の文字又は単語と、同義的な文字又は単語を生成する検索文拡張部を有し、
前記照合マップ生成部は、同義的な文字又は単語により検索文字列を置換して、前記照合マップを生成し、対応づけられた文字が一致する照合位置の座標を取得し、
前記連続性評価部は、置換前の検索文字列と置換後の検索文字列とを並行して処理して置換前の検索文字列と置換後の検索文字列それぞれの評価値Ｖｔを決定する、
ことを特徴とする請求項１ないし３いずれか記載の類似情報照合装置。
【請求項５】
前記検索データ生成部は、検索文字列に連続した数値が含まれる場合に、検索文字列と被検索文字列とからそれぞれ連続した数値を取り出し、
前記パターン照合部は、それぞれの数値の相対値に基づき検索文字列と被検索文字列の合致度を算出する、
ことを特徴とする請求項１ないし４いずれか記載の類似情報照合装置。
【請求項６】
検索データ生成部と、被照合データ生成部と、照合マップ生成部と、連続性評価部と、パターン照合部とを有する類似情報照合装置における類似照合方法おいて、
前記検索データ生成部が、入力された検索文から検索文字列を生成するステップと、
前記被照合データ生成部が、文書が記憶された記憶装置から被検索文字列を生成するステップと、
前記照合マップ生成部が、検索文字列の各文字と被検索文字列の各文字を２次元配列に対応付ける照合マップを生成し、対応づけられた文字が一致する照合位置の座標を取得するステップと、
前記連続性評価部が、所定の前記照合位置を起点に有効距離内の前記照合位置を連結したリンク、及び、前記リンクの終端の前記照合位置と始端の前記照合位置が一致する、一連の前記リンクを接続した経路を生成し、前記リンクの始端と終端に対応する文字の記号種の組み合わせに応じた重み付けとリンクの長さによる重み付けがされたリンク毎の評価値Ｖｋを決定し、前記経路上の全てのリンクの評価値Ｖｋを加算した評価値Ｖを当該経路を形成した各照合文字の評価値Ｖｘｙとし、検索文字列の評価値Ｖｘｙを加算した値を評価値Ｖｔとするステップと、
前記パターン照合部が、評価値Ｖｔの大きさに基づき検索文字列と被検索文字列の合致度を判定するステップと、
を有することを特徴とする類似情報照合方法。
【請求項７】
前記パターン照合部が、検索文字列と被検索文字列が完全に一致した場合の評価値により評価値Ｖｔを除して合致度を算出するステップ、を有する
ことを特徴とする請求項６記載の類似情報照合方法。
【請求項８】
前記パターン照合部が、照合位置毎に該照合位置を通過する前記経路に対し得られた評価値Ｖの中で最も高い評価値Ｖとなる照合位置を選択して、各照合文字の評価値Ｖｘｙを決定するステップ、を有する、
ことを特徴とする請求項６又は７記載の類似情報照合方法。
【請求項９】
検索文拡張部が、入力された検索文字列の少なくとも一部の文字又は単語と、同義的な文字又は単語を生成するステップと、
前記照合マップ生成部が、同義的な文字又は単語により検索文字列を置換して、前記照合マップを生成し、対応づけられた文字が一致する照合位置の座標を取得するステップと、
前記連続性評価部が、置換前の検索文字列と置換後の検索文字列とを並行して処理して置換前の検索文字列と置換後の検索文字列それぞれの評価値Ｖｔを決定するステップと、を有する
ことを特徴とする請求項６ないし８いずれか記載の類似情報照合方法。
【請求項１０】
前記検索データ生成部が、検索文字列に連続した数値が含まれる場合に、検索文字列と被検索文字列とからそれぞれ連続した数値を取り出すステップと、
前記パターン照合部が、それぞれの数値の相対値に基づき検索文字列と被検索文字列の合致度を算出するステップと、を有する、
ことを特徴とする請求項６ないし９いずれか記載の類似情報照合方法。
【請求項１１】
請求項６ないし１０いずれか記載の類似情報照合方法をコンピュータに実行させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パターンとして表現できる情報の類似性を判定する類似情報照合装置及び類似情報照合方法に係わり、特に、コンピュータで情報処理される種々のパターンの照合技術に関する。
【０００２】
【従来の技術】
文字、図形、画像、音声、或いは、一般的な記号のような情報は、その情報を構成する要素が位置と特徴とによって表現することができる。このように、要素の特徴に着目したときに各要素の特徴が時空間的に関連して配置される情報は、所謂パターンと呼ばれる。従来より、このパターンをコンピュータで処理するため各種のパターン情報処理方式が提案されている。パターン情報処理の過程において、類似した情報の合致度を評価すべき状況、例えば、文字情報の場合に、類似文字列を検索することは頻繁に要求される。そのため、情報の類似性を判定する方式として、情報の要素をパターンとして表現し、パターン間の関連性を評価するパターン照合方式が知られている。
【０００３】
従来のパターン照合方式の例として、文字列照合システムについて説明する。例えば、文字列照合システムを利用する従来の高速全文検索技術は、“第２部  高速全文検索の要素技術  カギを握るインデクス処理”、日経バイト、１９９６年１０月号、ページ１５８−１６７に記載されている。この引用文献に記載されている従来の典型的な照合システムは、照合文字列及び被照合文字列を固定長の微小な部分に分割する。ここで、用語「照合文字列」及び「被照合文字列」の用法を簡単に説明すると、例えば、文字列Ａと類似した文字列Ｂを文書Ｃの中から見つける場合に、文字列Ａが「照合文字列」であり、文書Ｃの中の文字列Ｂが「被照合文字列」である。次に、照合システムは、照合文字列の微小部分が被照合文字列の微小部分文字列群に含まれるかどうかを判定し、当該微小部分文字列を含む被照合文字列を照合文字列に類似した文字列として出力する。
【０００４】
このようなタイプの照合システムは、文字列の中の微小部分が完全一致する文字列の有無を判定する。そのため、文字列の一部が欠落した場合、文字列の一部が他の文字列で置換された場合、或いは、文字列の中に他の文字列が混入した場合のように、照合文字列若しくは被照合文字列に局部的な変形が生じた場合に、変形した箇所の周辺の微小文字列が一致しないため、文字列が照合しないと判定される。このように従来技術の第１のタイプの照合システムでは、文字列の局所的な変形を許容できないという欠点がある。
【０００５】
【発明が解決しようとする課題】
本発明は、上述の従来の照合システムの問題点に鑑み、情報の類似性を判定する類似情報照合装置において、照合される情報に対応した第１のパターン或いは第２のパターン内で、部分的に一致する微小パターンが一部欠落、他のパターンとの置換、或いは、他のパターンによる混入などによって、パターンの全域に分散された場合でも、パターンの照合を行うことにより情報の類似性を判定することができる類似情報照合装置、類似情報照合方法及び類似情報照合プログラムを記録した記録媒体の提供を目的とする。
【０００６】
【課題を解決するための手段】
上記の目的を達成するため、本発明は、パターンの照合位置を追跡し、離間した照合位置を許容する連続性の概念を導入し、この連続性を評価して照合の漏れを防止する。
図１は本発明の原理構成図である。本発明の情報の類似性を判定する類似情報照合装置１は、
照合されるべき第１の情報及び第２の情報から、情報の要素の位置及び特徴により表されるパターンとして、上記第１の情報に対応する第１のパターン及び上記第２の情報に対応する第２のパターンを生成するパターン生成手段１０と、
上記第１のパターン及び上記第２のパターンの中で同じ特徴を有する上記第１のパターンに属する第１の要素及び上記第２のパターンに属する第２の要素の夫々の位置の対を座標とする照合位置により構成される照合マップ３０を作成する照合マップ生成手段２０と、
上記照合マップ３０内で近傍にある上記照合位置が順次に連結された経路毎に上記経路の連続性を評価する連続性評価手段４０と、
上記経路毎に評価された連続性に基づいて上記第１のパターンと上記第２のパターンの合致度を判定するパターン照合手段５０とを含む。
【０００７】
上記照合マップ作成手段２０は、同じ特徴を有する上記第１の要素及び上記第２の要素の複数の組合せに対し、個別に上記照合位置を作成することを特徴とする。
また、上記パターン照合手段５０は、上記照合位置毎に該照合位置を通過する上記経路に対し評価された連続性の中で最も高い連続性を該照合位置の評価値として設定する手段と、上記照合位置毎に設定された評価値に基づいて上記第１のパターンと上記第２のパターンの合致度を計算する手段とを有する。
【０００８】
さらに、上記パターン生成手段１０は、上記パターンとして表される上記情報の少なくとも一部の要素に対し、上記少なくとも一部の元の要素の特徴を置換可能な特徴を有する同義的な要素を生成する手段と、上記同義的な要素が上記元の要素と同時に列挙されるよう上記パターンを生成する手段とを有し、上記照合マップ生成手段２０と、上記連続性評価手段３０と、上記パターン照合手段４０とは、同時に列挙された上記同義的な要素を上記元の要素と並行して処理するよう適合されていることを特徴とする。
【０００９】
また、上記照合マップ生成手段２０は、上記要素が数値を表現する特徴を有する場合に、数値の表す値が一致する場合に同じ特徴であると判定する手段を有するように構成してもよい。
図２は、上記本発明の目的を達成する情報の要素の位置及び特徴により表される第１のパターンと第２のパターンを照合することにより情報の類似性を判定する類似情報照合方法の動作フローチャートである。同図に示す如く、本発明の類似情報照合方法は、
上記第１のパターン及び上記第２のパターンを入力する段階（ステップ１）と、
上記第１のパターン及び上記第２のパターンの中で同じ特徴を有する上記第１のパターンに属する第１の要素及び上記第２のパターンに属する第２の要素を検出する段階（ステップ２）と、
上記検出された第１の要素及び第２の要素の夫々の位置の対を座標とする照合マップを作成する照合マップ生成段階（ステップ３）と、
上記照合マップ内で近傍にある上記照合位置を順次に連結することにより経路を生成する経路生成段階（ステップ４）と、
上記生成された経路毎に上記経路の連続性を評価する連続性評価段階（ステップ５）と、
上記経路毎に評価された連続性に基づいて上記第１のパターンと上記第２のパターンの合致度を判定するパターン照合段階（ステップ６）とを含む。
【００１０】
また、情報の類似性を判定する類似情報照合システムにおいて、情報の類似性を判定する上記の本発明の類似情報照合装置及び方法は、コンピュータが読み取り可能な記録媒体に記録したプログラム（ソフトウェア）として実現してもよい。
したがって、本発明は、情報の類似性を判定する類似情報照合プログラムを記録したコンピュータが読み取り可能な記録媒体を含む。上記類似情報照合プログラムは、
照合されるべき第１の情報及び第２の情報から、情報の要素の位置及び特徴により表されるパターンとして、上記第１の情報に対応する第１のパターン及び上記第２の情報に対応する第２のパターンを生成させるパターン生成コードと、
上記第１のパターン及び上記第２のパターンの中で同じ特徴を有する上記第１のパターンに属する第１の要素及び上記第２のパターンに属する第２の要素の夫々の位置の対を座標とする照合位置により構成される照合マップを作成させる照合マップ生成コードと、
上記照合マップ内で近傍にある上記照合位置が順次に連結された経路毎に上記経路の連続性を評価させる連続性評価コードと、
上記経路毎に評価された連続性に基づいて上記第１のパターンと上記第２のパターンの合致度を判定させるパターン照合コードとを含むことを特徴とする。
【００１１】
【発明の実施の形態】
以下、添付図面を参照して本発明の一実施例による文字列照合システムを説明する。本実施例の文字列照合システムは、被検索文書ファイルに保存された被検索文書の中からオペレータが入力した検索文と類似した文を含む被検索文書をオペレータに提示するシステムである。
【００１２】
図３は、本発明の一実施例による文字列照合システムの概略的な構成図であり、図４は、この文字列照合システムの動作フローチャートである。文字列照合システムは、ステップ１０においてオペレータから入力された検索文を受ける照合データ生成部１１０を有する。また、照合データ生成部１１０は、検索文を照合に適した照合データとしての照合文字列に変換する（ステップ２０）。文字列照合システムは、ステップ２０において被検索文書ファイル１４０から被検索文書を取り出し、照合文字列との照合に適した被照合文字列及び被照合文字列が属する被検索文書の文書識別番号を含む被照合データを生成する被照合データ生成部１３０を更に有する。
【００１３】
照合データとしての照合文字列及び被照合データとしての被照合文字列は、種々の情報を表現するパターンの中で、特に、文字情報を表現するパターンである。文字列内の各文字がパターンの要素に対応する。要素は、その文字の特徴としての文字コードと、その文字の文字列内における位置とによって表される。
また、文字列照合システムは照合マップ生成部１５０を更に有し、照合マップ生成部１５０は、照合データ生成部１１０からの照合文字列と、被照合データ生成部１３０からの被照合文字列とを受け、共通文字を検出し（ステップ３０）、照合マップを作成、出力する（ステップ４０）。
【００１４】
照合マップは、照合文字列及び被照合文字列に共通して含まれる共通文字の照合文字列及び被照合文字列での位置を夫々Ｘ座標及びＹ座標として表される位置（Ｘ，Ｙ）を照合位置として有するマップである。照合マップは、パターンとして文字列が採用される場合には２次元のマップとして構築することができる。
文字列照合システムは連続性評価部１６０及び検索結果出力部１７０を更に有する。連続性評価部１６０は、照合マップ生成部１５０によって作成、出力された照合マップを受け、照合文字列と被照合文字列とを照合し、照合結果を検索結果出力部に渡す。そのため、連続性評価部１６０は、照合マップ内で、照合位置から近傍の照合位置を順次に追跡することにより一連の照合位置を含む経路を形成し（ステップ５０）、経路毎に連続性の値を計算し（ステップ６０）、各照合位置に対する評価値として、その照合位置を通過する経路の連続性の値の中で最高の連続性の値を選択し（ステップ７０）、照合文字列の各文字についての照合位置の評価値を集計する（ステップ８０）。この集計結果は、照合文字列と被照合文字列の類似性を表している。
【００１５】
検索結果出力部１７０は、連続性評価部１６０から照合結果を受け、照合文字列と類似していると判定された被照合文字列を含む被検索文書に関する情報を被検索文書ファイル１４０から取り出し、オペレータに通知する（ステップ９０）。
以下、本発明の一実施例の文字列照合システムについて詳述する。
【００１６】
図５は本例における文字列照合システムの照合データ生成部１１０の構成図である。同図に示す如く、照合データ生成部１１０は、検索文を入力し、検索文拡張辞書１２０を参照して拡張検索文を出力する検索文拡張部１１１と、検索拡張部を入力して正規化拡張検索文に変換する検索文正規化部１１２と、正規化拡張検索文を入力して数値表現部分を同じ形式に変換し、最終的な照合データとしての照合文字列を出力する数値表現置き換え部１１３とを有する。
【００１７】
検索文拡張部１１１は、オペレータから検索文（例えば、「文書検索の高速化」）が入力され、検索文の中の文字列（例えば、「検索」）を置き換え可能な文字列が検索文拡張辞書１２０内に存在するかどうかを判定し、置き換え可能な文字列（例えば、「抽出」）が検索文拡張辞書１２０内に存在する場合に、その置き換え可能な文字列（「抽出」）を、文字列（「検索」）の同義語として検索文に付加し、拡張検索文を出力する。置き換え可能な文字列が存在しない場合には、入力された検索文がそのまま拡張検索文として出力される。この場合の拡張検索文は、「文書｛検索｜抽出｝の高速化」のように表現され、｛文字列ａ｜文字列ｂ｝の部分が拡張された部分であり、文字列ａと文字列ｂが同義語であることを表す。
【００１８】
検索文正規化部１１２は、検索文拡張部１１１から出力された拡張検索文を入力し、拡張検索文内の文字の正規化を行い、正規化拡張検索文を出力する。文字の正規化とは、例えば、英数字カナの半角文字から全角文字への変換、英字の小文字から大文字への変換、或いは、句読点、改行制御文字及び伸張音等の検索の際に無視されるべきノイズ文字の削除等の処理を意味する。
【００１９】
数値表現置き換え部１１３は、検索文正規化部１１２から出力された正規化拡張検索文を受け、正規化拡張検索文中に数値により定量表現された部分文字列が存在するかどうかを判定する。定量表現された部分文字列が存在する場合、その部分文字列を値に変換し、正規化拡張検索文中の定量表現部分が値によって置換された最終的な照合データとしての照合文字列を作成、出力する。
【００２０】
図６は本例における文字列照合システムの被照合データ生成部１３０の構成図である。同図に示す如く、被照合データ生成部１３０は、被検索文書ファイル１４０から、検索に必要な全ての被検索文書を読み出し、出力する被検索文書読み込み部１３１を有する。被照合データ生成部１３０は、被検索文書正規化部１３２及び数値表現置き換え部１３３を更に有する。
【００２１】
被検索文書正規化部１３２は、被検索文書読み込み部１３１から被検索文書を入力し、被検索文書内の文字の正規化を行い、正規化被検索文書を出力する。文字の正規化については、検索文正規化部１１２で説明した通りである。
また、数値表現置き換え部１３３は、被検索文書正規化部１３２から正規化被検索文書を受け、正規化被検索文書中に数値により定量表現された部分文字列が存在する場合に、その部分文字列を値に変換し、正規化被検索文書中の定量表現部分が値によって置換された最終的な被照合データとしての被照合文字列を作成、出力する。
【００２２】
次に、本発明の一実施例による文字列照合システムの照合マップ生成部１５０の機能について詳述する。図３に示される如く、照合マップ生成部１５０は、照合データ生成部１１０及び被照合データ生成部１３０に接続され、照合データとしての照合文字列及び被照合データとしての被照合文字列を夫々から受け、照合マップを生成するよう機能する。
【００２３】
照合マップ生成部１５０は、最初に、照合文字列と被照合文字列の双方に共通して含まれる文字、すなわち、共通文字を検出する。例えば、照合文字列を「文書検索の高速化」とし、被照合文字列を「高速な文書の検索を行う」とすると、共通文字は、「高」、「速」、「文」、「書」、「の」、「検」及び「索」である。次に、照合文字列における共通文字の位置をＹ座標とし、被照合文字列における共通文字の位置をＸ座標とする照合位置により構成される照合マップを生成する。
【００２４】
図７は、照合マップの概念がよりよく理解されるように、一例として、上記の照合文字列及び被照合文字列に対し生成された照合マップを視覚的に表現した説明図である。同図において“○”で示される点が照合位置に対応する。本例では、簡単のため、被照合文字列は同義語を含まない場合を想定している。
一方、既に説明した通り、検索文拡張部１１１において、照合文字列「文書検索の高速化」が拡張検索文「文書｛検索｜抽出｝の高速化」の形として同義語を含むように拡張されている場合、図８に示すような照合マップが得られる。この場合、検索文字列内での共通文字の位置を表すＹ座標は補正される。すなわち、「検」と「抽」のＹ座標、並びに、「索」と「出」のＹ座標は一致するように補正される。
【００２５】
かくして、照合マップ生成部１５０は、照合文字列中の共通文字の位置を表すＹ座標値と、照合文字列に同義語が含まれる場合の共通文字の位置の補正値であるＹ補正値と、被照合文字列中の共通文字の位置を表すＸ座標値と、被照合データに対応する文書識別番号とを照合マップとして出力する。
連続性評価部１６０は、総合マップ生成部１５０から照合マップを入力する。連続性評価部１６０では、文書識別番号毎に、照合文字列と被照合文字列の類似性が評価される。そのため、連続性評価部１６０は、最初に、照合マップ内の照合位置を追跡し、全ての照合位置に連続性評価値を付与し、次に、同じ照合文字列内の文字に対し存在し得る複数の照合位置の連続性評価値の中から最大値を照合文字列内の当該文字の連続性評価値として選択する。最後に、照合文字列内の文字毎に得られた連続性評価値を照合文字列全体に関して集計し、正規化し、得られた値を照合文字列と被照合文字列の合致度とする。合致度は、文書識別番号と共に連続性評価部１６０から検索結果出力部１７０に送られる。
【００２６】
以下、連続性評価について詳述する。図９は、本発明の一実施例による文字列照合システムにおいて行われる連続性評価のための経路追跡の説明図である。経路追跡処理は、図７に示された照合マップの照合位置に関して、一つの照合位置から有効距離内にある他の照合位置を探し、リンクを張る。この経路追跡処理を繰り返すことにより、照合マップ内の照合位置は、分岐を含む幾つかの経路に分類される。図９には、「高」から「速」への経路と、「書」から「の」の分岐及び「書」から「検」を経由して「索」に至る分岐を含む「文」と「書」を含む経路とが示されている。
【００２７】
図１０は、照合位置の典型的な４通りの連続性の形を説明する図である。一般に、連続した文字列が照合している箇所では、照合位置のリンクは右下４５度の方向に並ぶ。同図の（Ａ）は、全ての照合位置が右下４５度方向に並ぶ完全一致の場合を示す図である。同図の（Ｂ）は、データの（１字）欠落がある場合を示し、（Ｃ）はデータの（１字）置換がある場合を示し、（Ｄ）はデータの（２字）混入がある場合を示す図である。これらのリンクを追跡することにより、データの欠落、置換、混入が生じている場合でも、連続性を保ったまま照合を評価することができる。
【００２８】
連続性評価部１６０は、経路の生成に続いて合致度の算出処理を行う。ここで、照合位置間のリンクに重みを付けるため、全ての文字について文字種別（タイプ）を設定し、照合位置の各文字を分類する。本例において、文字種別として、「漢字」と「かな」の２種類に分類する場合を想定すると、
漢字：「高」「速」「文」「書」「検」「索」
かな：「の」
のような分類がなされる。次に、リンクの前後の文字の文字種別ｔ１及びｔ２に応じて、文字種間のリンクの重みを以下の通り設定する。
0003955410.tif 000002
また、リンクには、リンクの長さ（リンクの前後の照合位置間の距離）に応じた重みを設定する。例えば、リンクの長さによる重みは以下の通り表される。
リンクの長さによる重み（Ｗl ）＝
ｇ（ｘ1 ，ｙ1 ，ｘ2 ，ｙ2 ）＝１／｛（ｘ2 −ｘ1 ）2 ＋（ｙ2 −ｙ1 ）2 ｝
最後に、上記の文字種間の重み（Ｗt ）とリンクの長さによる重み（Ｗl ）とを結合することにより、一つのリンクについての以下の評価値が得られる。
１リンクの評価値＝
ｖ＝Ｗt ・Ｗl ＝ｆ（ｔ1 ，ｔ2 ）・ｇ（ｘ1 ，ｙ1 ，ｘ2 ，ｙ2 ）
連続性評価部１６０では、次に、照合マップ内の経路追跡によって獲得された経路上の全てのリンクに対し、リンクの評価値を集計し、一つの経路全体の評価値を得る。この一つの経路の評価値Ｖは、例えば、次の式に従って計算することができる。
【００２９】
【数１】
0003955410.tif 000003
式中、ｋは着目経路上のリンクのインデックス、ｎは着目経路上のリンクの総数＋１、ｖk は着目経路上の各リンクの評価値を表す。
かくして得られた一つの経路の評価値Ｖは、着目経路上の各照合位置に照合位置の評価値Ｖxyとして設定される。また、経路が分岐を含む場合には、例えば、分岐毎に計算された経路の評価値の中で最も評価値の高い分岐を含む経路が有効であるとして選択することができる。このようにして、照合マップ内で生成された全ての経路に対して上記の一つの経路の評価値Ｖを求めることにより、照合マップの内の全ての照合位置に関して照合位置の評価値Ｖxyが得られる。
【００３０】
次に、照合文字列中の各文字列に関する評価値を得る。例えば、図７に示される如く、照合文字列中の文字に対応する照合位置が高々１個しかない場合には、対応する照合位置が存在する照合文字列中の文字の評価値として、その照合位置の評価値を設定し、照合文字列中のそれ以外の文字の評価値は零とする。また、照合文字列中の文字に対応する照合位置が２個以上存在する場合には、対応する照合位置の評価値の中で最大の評価値をその文字の評価値として設定する。かくして、照合文字列中の全ての文字に対し連続性の評価値を得ることができる。
【００３１】
最後に、照合文字列全体として被照合文字列との合致度を求めるため、照合文字列中の全ての文字に関する連続性の評価値を集計して集計値を得る。連続性評価値の集計値Ｖtotal は、例えば、次式に従って計算される。
【００３２】
【数２】
0003955410.tif 000004
照合文字列全体としての被照合文字列との合致度は、例えば、この連続性評価値の集計値Ｖtotal を完全一致の場合の連続性評価値の集計値Ｖequal で除算した値によって表される。
合致度＝Ｖtotal ／Ｖequal
合致度をこのように表現することにより、連続性評価値の集計値は完全一致の場合に最大値１．０をとる。このようにして得られた合致度は、文書識別番号と共に、照合結果として次の検索結果出力部１７０に送られる。
【００３３】
図１１は本発明の一実施例による文字列照合システムの検索結果出力部の構成図である。同図に示されるように、検索結果出力部１７０は、照合結果変換部１７１と、検索結果表示部１７２と、検索結果選択部１７３と、文書表示部１７４とを含む。
照合結果変換部１７１は、連続性評価部１６０から、上記合致度及び文書識別番号を照合結果として入力し、文書識別番号に基づいて照合結果に対応する文書の見出し、要約情報等を被検索文書ファイル１４０から読み込み、合致度の順に照合結果の文書に関する情報を並べ換え、検索結果として出力する。
【００３４】
検索結果表示部１７２は、照合結果変換部１７１から検索結果を入力し、この検索結果をディスプレイなどの表示装置に表示させ、次の段の検索結果選択部１７３に検索結果を渡す。
検索結果選択部１７３は、検索結果表示部１７２から検索結果を入力し、また、検索結果表示に応じたオペレータからの指示を入力し、オペレータから読み込むべき文書が指定された場合、指定された文書を被検索文書ファイル１４０から読み込み、選択文書として出力する。
【００３５】
文書表示部１７４は、検索結果選択部１７３から出力された選択文書を入力し、読み込まれた選択文書をディスプレイなどの表示装置に表示させる。
本発明の一実施例による文字列照合システムは、図３乃至１１を参照して説明した構成及び動作に従って、オペレータから入力された検索文を被検索文書ファイルに格納された文書と照合し、検索文に類似した被検索文を含む文書をオペレータに提示することができる。
【００３６】
次に、本発明の一実施例の文字列照合システムにおいて、特に、検索文拡張部１１１が拡張検索文を出力した場合の処理を説明する。本例では、検索文「文書検索の高速化」において、文字列「検索」の同義語「抽出」が存在する場合を考える。既に説明したように、照合データが同義語を含む場合、複数の照合データ「文書検索の高速化」及び「文書抽出の高速化」が存在すると解釈される。また、
同義データ正規表現：文書｛検索｜抽出｝の高速化
を用いることにより同義語が照合データ内に列挙して表現されるような拡張検索文が作成される。このように照合データが同義語を含む場合、照合データは、同じ位置にある同義語の中の一つの同義語が選択されたとして処理される。図１２は、図８に示された同義語を含む照合マップにおける経路追跡の説明図である。経路追跡の際の有効距離は、実際に生成された照合マップに配置された経路上の照合位置間の距離と、一つの同義語が選択されたとして処理された場合に生成される理論上の照合マップ上での照合位置間の距離との差違を表す距離補正値を考慮して計算される。
【００３７】
最後に、本発明の一実施例による文字列照合システムの数値表現置き換え部１１３又は１３３において、照合文字列又は被照合文字列中の定量表現が数値に置換された場合の処理について説明する。図１３は、類似定量文字照合の処理手順のフローチャートである。
第１に、照合文字列又は被照合文字列から、数値により定量表現された部分文字列を抽出する（ステップ１００）。第２に、抽出された部分文字列を値に変換する（ステップ１０１）。第３に、変換された値に基づいて数値の合致度を計算する（ステップ１０２）。
【００３８】
ここで、数値により定量表現された部分文字列の抽出は、文字列内に数値表現文字が連続して出現した部分を検出し、取り出すことにより行われる。例えば、以下のような文字が数値表現文字として検出される。
１  ２  ３  ４  ５  ６  ７  ８  ９  ０
一  二  三  四  五  六  七  八  九  零
十  百  千  万  ・・・・
合致度は、照合文字列から得られた値（Ｖｓ）と、被照合文字列から得られた値（Ｖｄ）とに基づいて以下の式に従って計算することができる。
【００３９】
【数３】
0003955410.tif 000005
図１４は、類似定量文字照合処理の説明図である。同図には、照合文字列及び被照合文字列、定量表現による部分文字列、部分文字列から変換された数値、並びに、変換された数値の合致度が示されている。
したがって、本発明の一実施例によれば、コンピュータを利用した文字列照合システムにおいて、照合文字列或いは被照合文字列内に部分文字列の欠落、他の文字列との置換、他の文字列の混入などによって、部分的に一致する文字列が分散した場合に、文字列の照合を行うことができる。
【００４０】
また、本発明の一実施例による文字列照合システムの構成は、上記の実施例で説明された例に限定されることなく、文字列照合システムの各々の構成要件をソフトウェア（プログラム）で構築し、ディスク装置等に記録しておき、必要に応じて文字列照合システムのコンピュータにインストールして文字列照合を行うことも可能である。さらに、構築されたプログラムをフロッピーディスクやＣＤ−ＲＯＭ等の可搬記録媒体に格納し、このような文字列照合システムを用いる場面で汎用的に使用することも可能である。
【００４１】
本発明は、上記の実施例に限定されることなく、特許請求の範囲内で種々変更・応用が可能である。
【００４２】
【発明の効果】
上述の如く、本発明によれば、パターン照合を行う際に、パターンの照合位置を追跡し、照合位置が離間していてもパターンの連続性を評価することができる。したがって、照合パターン或いは被照合パターンにおいて一部のパターンが欠落し、他のパターンと置換され、若しくは、他のパターンが混入される等の影響によって、照合パターンと被照合パターンとの間で部分的に一致するパターンが分散して存在する場合でも、照合が行える。そのため、本発明によれば、オペレータが被照合パターンの内容を熟知していなくても、漏れの無い照合が実現され、オペレータの負担が軽減される利点が得られる。
【図面の簡単な説明】
【図１】本発明の原理構成図である。
【図２】本発明の類似情報照合方法の動作フローチャートである。
【図３】本発明の一実施例による文字列照合システムの概略的な構成図である。
【図４】本発明の一実施例による文字列照合システムの動作フローチャートである。
【図５】本発明の一実施例による文字列照合システムの照合データ生成部の構成図である。
【図６】本発明の一実施例による文字列照合システムの被照合データ生成部の構成図である。
【図７】本発明の一実施例による照合マップを視覚的に表現した説明図である。
【図８】同義語を含む場合の照合マップの説明図である。
【図９】本発明の一実施例による文字列照合システムにおいて行われる連続性評価のための経路追跡の説明図である。
【図１０】照合位置の連続性を説明する図である。
【図１１】本発明の一実施例による文字列照合システムの検索結果出力部の構成図である。
【図１２】図８に示された同義語を含む照合マップにおける経路追跡の説明図である。
【図１３】類似定量文字照合の処理手順のフローチャートである。
【図１４】類似定量文字照合処理の説明図である。
【符号の説明】
１    類似情報照合装置
１０    パターン生成手段
２０    照合マップ作成手段
３０    照合マップ
４０    連続性評価手段
５０    パターン照合手段
【図１】
0003955410.tif 000006
【図２】
0003955410.tif 000007
【図３】
0003955410.tif 000008
【図４】
0003955410.tif 000009
【図５】
0003955410.tif 000010
【図６】
0003955410.tif 000011
【図７】
0003955410.tif 000012
【図８】
0003955410.tif 000013
【図９】
0003955410.tif 000014
【図１０】
0003955410.tif 000015
【図１１】
0003955410.tif 000016
【図１２】
0003955410.tif 000017
【図１３】
0003955410.tif 000018
【図１４】
0003955410.tif 000019