(57)【特許請求の範囲】
【請求項１】
識別子によりデータを管理するデータ管理装置において、
前記識別子が入力される識別子入力手段と、
入力された前記識別子を、前記識別子よりも短い所定のデータ長の複数のセグメントに分割する識別子分割手段と、
得られた複数の前記セグメント間において排他的論理和を演算することにより、前記所定のデータ長のタグを生成するタグ生成手段と、
前記タグ生成手段によって生成された前記タグを元にして、索引を生成する索引生成手段と、
を有することを特徴とするデータ管理装置。
【請求項２】
識別子によりデータを管理するデータ管理装置において、
前記識別子が入力される識別子入力手段と、
入力された前記識別子を、前記識別子を構成するフィールド毎に分割する識別子分割手段と、
得られた個々の前記フィールドの値から、取り得る値の個数が多い前記フィールドほど桁数の大きいハッシュ値を計算し、複数の前記ハッシュ値を結合して、前記識別子よりもデータ長の短いタグを生成するタグ生成手段と、
前記タグ生成手段によって生成された前記タグを元にして、索引を生成する索引生成手段と、
を有することを特徴とするデータ管理装置。
【請求項３】
前記識別子のデータ構造に関する情報を記録するデータ構造情報記録手段を更に有し、
前記識別子分割手段と前記タグ生成手段は、前記データ構造情報記録手段に記録されている情報を参照して処理を行うことを特徴とする請求項２記載のデータ管理装置。
【請求項４】
前記識別子のデータ構造を記述した構造記述データが入力される構造記述データ入力手段と、
入力された前記構造記述データを解析して前記識別子のデータ構造に関する情報を生成する構造記述データ解析手段と、
得られた前記識別子のデータ構造に関する情報を前記データ構造情報記録手段に書き込む書き込み手段と、
を更に有することを特徴とする請求項３記載のデータ管理装置。
【請求項５】
前記識別子入力手段から入力された複数の前記識別子のデータ構造を統計的な手法により解析するデータ構造解析手段と、
得られた前記識別子のデータ構造に関する情報を前記データ構造情報記録手段に書き込む書き込み手段と、
を更に有することを特徴とする請求項３記載のデータ管理装置。
【請求項６】
新たに入力された識別子に対応する前記タグが前記タグ生成手段によって生成された場合に、前記索引生成手段によって生成された前記索引を参照し、同一の前記タグが存在するか否かを判定する同一タグ存在判定手段と、
同一の前記タグが存在すると判定された場合には、判定された前記タグに対応する前記識別子と前記新たに入力された識別子とが同一であるか否かを判定する識別子同一性判定手段と、
を更に有することを特徴とする請求項２記載のデータ管理装置。
【請求項７】
前記識別子同一性判定手段は、前記識別子のデータ構造を参照して、比較コストが小さい部分から前記識別子を順次比較することを特徴とする請求項６記載のデータ管理装置。
【請求項８】
前記同一タグ存在判定手段によって同一の前記タグが存在すると判定された場合には、判定された前記タグに対応する前記識別子と前記新たに入力された識別子とを比較してこれらの間で異なる部分を特定し、特定した部分を指示する指示情報を前記索引に対して付与する指示情報付与手段を更に有することを特徴とする請求項６記載のデータ管理装置。
【請求項９】
前記同一タグ存在判定手段によって同一の前記タグが複数存在すると判定された場合には、前記指示情報付与手段によって付与された前記指示情報を参照して前記識別子の異なる部分のみを比較することにより、前記識別子の候補を絞り込む候補絞り込み手段を更に有し、
前記識別子同一性判定手段は、絞り込まれた前記候補と前記新たに入力された識別子との同一性を前記識別子のデータ構造を参照して判定することを特徴とする請求項８記載のデータ管理装置。
【請求項１０】
識別子によりデータをコンピュータに管理させるためのデータ管理プログラムを記録したコンピュータ読み取り可能な記録媒体において、
前記識別子が入力される識別子入力手段、
入力された前記識別子を、前記識別子よりも短い所定のデータ長の複数のセグメントに分割する識別子分割手段、
得られた複数の前記セグメント間において排他的論理和を演算することにより、前記所定のデータ長のタグを生成するタグ生成手段、
前記タグ生成手段によって生成された前記タグを元にして、索引を生成する索引生成手段、
としてコンピュータを機能させるためのデータ管理プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１１】
識別子によりデータをコンピュータに管理させるためのデータ管理プログラムを記録したコンピュータ読み取り可能な記録媒体において、
前記識別子が入力される識別子入力手段、
入力された前記識別子を、前記識別子を構成するフィールド毎に分割する識別子分割手段、
得られた個々の前記フィールドの値から、取り得る値の個数が多い前記フィールドほど桁数の大きいハッシュ値を計算し、複数の前記ハッシュ値を結合して、前記識別子よりもデータ長の短いタグを生成するタグ生成手段、
前記タグ生成手段によって生成された前記タグを元にして、索引を生成する索引生成手段、
としてコンピュータを機能させるためのデータ管理プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデータ管理装置および記録媒体に関し、特に、識別子によりデータを管理するデータ管理装置および記録媒体に関する。
【０００２】
【従来の技術】
記録装置に記録されている複数のデータを管理する場合、データ集合に対する演算処理を行う必要がしばしば生ずる。
【０００３】
一般に、データ集合を対象とする演算処理においては、同一のデータであることを判定するデータ同定処理が頻繁に使用される。
従来においては、データとそのデータを一意に識別するための識別子とを対応付けて管理し、この識別子を比較することによって識別子の同一性を判定し、データを同定していた。
【０００４】
通常、データ自身のデータ長に比較して識別子のデータ長は非常に小さいため、識別子によるデータの同定処理は効率的なものであった。
しかし、データ管理システムが分散環境で運用されるなどして、管理するデータ数が多数になると、データを識別するための識別子を表すデータ長も次第に大きくなってきた。
【０００５】
そこで、そのデータ（ファイル）が記録されている位置をパス名によって指定する方法が提案されている。即ち、このような方法では、ファイルというデータをパス名によって識別する。
【０００６】
ところで、パス名にはユーザが認識しやすい名前をつけるため、管理するファイルが多くなるほど、パス名の長さ（パス名のデータ長）も長くなる傾向がある。従って、ファイルの階層が増加すると、必然的にパス名も長くなる結果となる。このとき、ファイル（データ）の同定処理はパス名（文字列）の比較処理となるため、パス名が長くなるほど処理コストが増加することになる。
【０００７】
そのような問題点を解決する方法として、特開平４−３３８８４４「ファイルのパス名管理制御方式」がある。この発明では、パス名に対応するＩＤを作成し、パス名の代わりにこのＩＤ利用する。ＩＤの作成にあたっては、ＩＤはパス名よりもバイト数が少なく、かつ、ＩＤとパス名との対応関係が一意となるように留意する。パス名の代わりにこのＩＤを利用することによって、メモリを節約したり、処理を高速化することが可能となり、その結果、ＩＤ同士を比較することによって、パス名を使用した場合に比較して迅速にファイルを同定することが可能となる。
【０００８】
一方、データ長の長いキーに対する効率的な探索方法として、「トライ」が知られている。トライでは長い文字列に含まれる文字を索引である木構造のノードに対応させる。そして、探索する文字列をこの木構造のノードごとに比較することによって、目的となる文字列を探索することが可能となる。
【０００９】
たとえば、特開平５−２６０７「木構造データ構造による高速探索方式」では、長くなった識別子をコンパクトなブロックに分割することによって、文字列を識別子に、また、文字をブロックに置き換えることでトライを適用している。つまり、ブロックを索引である木構造データのノードとして表現し、識別子の比較ではなく、ブロック列を比較することによって比較処理のコストを少なくしている。
【００１０】
ところで、Ｂ木を利用した探索においては、木のノードごとに何度か識別子全体を比較する必要がある。特開平５−２６０７に開示されている方法では、データ長の小さいブロックごとに比較して、比較処理のコストを低減している。
【００１１】
【発明が解決しようとする課題】
しかし、特開平４−３３８８４４に開示されている方法では、ファイルにアクセスするためには、ＩＤからパス名を取り出す必要があるため、パス名とＩＤとを管理する（対応付ける）テーブルや管理手段を設ける必要がある。このテーブルは、当然のことながら全てのパス名を含んでいる必要があることから、パス名とＩＤの対応テーブルの大きさは、ファイルの数に比例して大きなものになる。従って、ファイルの数の増加に応じて、占有されるメモリ容量が増大するという問題点があった。
【００１２】
一方、特開平５−２６０７に開示されている方法では、木構造を利用した探索処理において、識別子の比較回数を削減するものであって、識別子の比較処理そのものを効率化するものではない。この方法の本来の目的は、データ長の長いキーを利用した場合の探索処理の高効率化にある。従って、集合演算処理のように識別子の比較処理を何度も繰り返し実行しなければならない場面においては、この方法をそのまま利用することは困難である。
【００１３】
しかし、あえて集合演算処理に使用するならば、演算対象の識別子集合から索引となる木構造を作成し、もう１つの識別子集合の要素を１つずつ探索していく方式を採ることになる。そのため、あらかじめ識別子全体のために作成してある索引を利用することができないことから、その場で索引を作成する処理が必要となり、その結果、処理速度が低下するという問題点があった。
【００１４】
本発明はこのような点に鑑みてなされたものであり、データ長の長い識別子に対しても、データの集合演算処理の場面で、複数の識別子から識別子の同一性を迅速に判定してデータを識別することが可能なデータ管理装置を提供する。
【００１５】
【課題を解決するための手段】
本発明では上記課題を解決するために、識別子によりデータを管理するデータ管理装置において、前記識別子が入力される識別子入力手段と、入力された前記識別子を、前記識別子よりも短い所定のデータ長の複数のセグメントに分割する識別子分割手段と、得られた複数の前記セグメント間において排他的論理和を演算することにより、前記所定のデータ長のタグを生成するタグ生成手段と、前記タグ生成手段によって生成された前記タグを元にして、索引を生成する索引生成手段と、を有することを特徴とするデータ管理装置が提供される。
ここで、識別子入力手段からは識別子が入力される。識別子分割手段は、入力された識別子を、識別子よりも短い所定のデータ長の複数のセグメントに分割する。タグ生成手段は、得られた複数のセグメント間において排他的論理和を演算することにより、所定のデータ長のタグを生成する。索引生成手段は、タグ生成手段によって生成されたタグを元にして索引を生成する。
【００１６】
また、上記課題を解決するために、識別子によりデータを管理するデータ管理装置において、前記識別子が入力される識別子入力手段と、入力された前記識別子を、前記識別子を構成するフィールド毎に分割する識別子分割手段と、得られた個々の前記フィールドの値から、取り得る値の個数が多い前記フィールドほど桁数の大きいハッシュ値を計算し、複数の前記ハッシュ値を結合して、前記識別子よりもデータ長の短いタグを生成するタグ生成手段と、前記タグ生成手段によって生成された前記タグを元にして、索引を生成する索引生成手段と、を有することを特徴とするデータ管理装置が提供される。
ここで、識別子入力手段からは識別子が入力される。識別子分割手段は、入力された識別子を、識別子を構成するフィールド毎に分割する。タグ生成手段は、得られた個々のフィールドの値から、取り得る値の個数が多いフィールドほど桁数の大きいハッシュ値を計算し、複数のハッシュ値を結合して、識別子よりもデータ長の短いタグを生成する。索引生成手段は、タグ生成手段によって生成されたタグを元にして索引を生成する。
【００１７】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して説明する。
図１は、本発明のデータ管理装置の原理を説明する原理図である。この図において、識別子入力手段１からは、データを識別するための識別子が入力される。識別子分割手段２は、入力された識別子を複数のセグメントに分割して出力する。タグ生成手段３は、得られたセグメントに対して所定の論理演算を施すことにより、識別子よりもデータ長の短いタグを生成する。索引生成手段４は、生成されたタグを元にして、例えば、木構造を有する索引を生成する。
【００１８】
次に、図２を参照して本発明の実施の形態の一例について説明する。
この図において、識別子入力手段１１からは、データを識別するための識別子が入力される。識別子分割手段１２は、入力された識別子をタグと同一長の複数のセグメントに分割して出力する。タグ生成手段１３は、得られたセグメントの間で排他的論理和を演算することにより、識別子よりもデータ長の短いタグを生成する。索引生成手段１４は、生成されたタグを元にして、木構造を有する索引を生成する。同一タグ存在判定手段１５は、新たな識別子が入力された場合に、その識別子に対応するタグが、索引中に既に存在しているか否かを判定する。識別子同一性判定手段１６は、同一タグ存在判定手段１５によって同一のタグが既に存在していると判定された場合に、そのタグに対応する識別子と新たに入力された識別子とを比較してこれらが同一であるか否かを判定し、その結果を出力する。
【００１９】
次に、以上の実施の形態の動作について説明する。
以下では、第１および第２の識別子集合が入力された場合において、これらの間で識別子の同定を行うための同定処理を例に挙げて動作の説明をする。
【００２０】
なお、このような同定処理は、識別子集合の間で論理和や論理積などを算出するときに利用される。
図３は、図２に示す実施の形態において同定処理を行う場合に実行される処理の一例を説明するフローチャートである。このフローチャートが開始されると、以下の処理が実行されることになる。
［Ｓ１］識別子入力手段１１は、第１の識別子集合を入力する。
［Ｓ２］識別子分割手段１２とタグ生成手段１３は、タグを生成する。
【００２１】
即ち、識別子分割手段１２は、入力された識別子集合から識別子を１つだけ取得し、取得した識別子をタグと同一データ長のセグメントに分割する。タグ生成手段１３は、１つの識別子から得られた複数のセグメントの間で排他的論理和を演算し、得られた結果をその識別子のタグとする。
【００２２】
なお、排他的論理和の代わりに他のハッシュ関数を使用してもよい。
［Ｓ３］索引生成手段１４は、生成されたタグを元にして索引を生成する。
即ち、索引生成手段１４は、生成されたタグを利用して、第１の識別子集合に対応する索引（２進木）を生成する。図４は、以上の処理によって生成される索引の一例を示している。この例において、左端の索引が以上の処理によって作成される部分である。この索引はｎ１〜ｎ７のノードによって構成されており、それぞれのノードには、分岐する際に必要な情報が付与されている。なお、このような２進木については、岩波講座情報科学１１「データ管理算法」, Ｐ３３に詳しい記述がある。
【００２３】
索引の右端のノード（ｎ４〜ｎ７）には、タグが少なくとも１つずつ関係付けられている。この例では、ノードｎ４にタグｔ１，ｔ２が関連付けられており、また、ノードｎ５〜ｎ７には、タグｔ３〜ｔ５がそれぞれ関連付けられている。更に、各タグには識別子がそれぞれ関連付けられている。この例では、タグｔ１〜ｔ５に識別子ｉ１〜ｉ５がそれぞれ関連付けられている。なお、本実施の形態においては、図４に示すような索引、タグ、および、識別子が索引生成手段１４内部のメモリ等に記憶される。
【００２４】
このような索引を用いることにより、第１の識別子集合に属する識別子のうち、同一のタグを持つ識別子（タグが衝突した識別子）を効率よくまとめることができる。なお、実際に作成される索引は、図４の場合に比較して大きいものとなる。
［Ｓ４］識別子入力手段１１は、第２の識別子集合を入力する。
［Ｓ５］識別子分割手段１２とタグ生成手段１３は、入力された第２の識別子集合に属している各識別子に対応するタグを前述の場合と同様の処理により生成する。
［Ｓ６］同一タグ存在判定手段１５と識別子同一性判定手段１６は協働して、識別子の同定処理を実行する。即ち、同一タグ存在判定手段１５は、索引を参照して同一のタグが存在しているか否かを判定し、その結果、同一のタグが存在していると判定した場合には、識別子同一性判定手段１６がそれらの識別子が同一であるか否かを更に判定する。なお、この処理の詳細については、図５を参照して後述する。
［Ｓ７］識別子同一性判定手段１６は、全ての識別子の同定が終了したか否かを判定する。その結果、全ての識別子の同定が終了した場合には処理を完了し、また、終了していない場合にはステップＳ６に戻る。次に、図５を参照して図３に示す同定処理の詳細について説明する。
【００２５】
このフローチャートは、図３に示すステップＳ６の「同定処理」が開始された場合に、呼び出されて実行される。このフローチャートが開始されると、以下のような処理が実行されることになる。
［Ｓ２１］同一タグ存在判定手段１５は、タグ生成手段１３によって生成された第２の識別子集合に属する識別子に対応するタグを１つ選択し、索引生成手段１４によって生成された第１の識別子集合に対応する索引を参照することにより、同一のタグが存在しているか否かを検索する。
［Ｓ２２］同一タグ存在判定手段１５は、ステップＳ２１の処理の結果、同一のタグが存在していると判定した場合にはステップＳ２３に進み、また、同一のタグが存在していないと判定した場合にはステップＳ２５に進む。
［Ｓ２３］識別子同一性判定手段１６は、同一のタグが存在している場合には、そのタグに対応する識別子（第１の識別子集合に属している識別子）と、処理の対象となっている識別子（第２の識別子集合に属している識別子）とをバイナリデータとして比較し、同一であるか否かを判定する。その結果、これらの識別子が同一であると判定した場合にはステップＳ２４に進み、同一ではないと判定した場合にはステップＳ２５に進む。
【００２６】
なお、処理対象となっているタグに対して、複数のタグが同一であるとステップＳ２２において判定された場合には、最初の識別子と比較し、同一でなかったら、次の同一のタグを有する識別子を比較する。また、同一であったら、これを同一な識別子と判定し、残りの同一のタグを持つ識別子を無視する。
［Ｓ２４］識別子同一性判定手段１６は、同定した識別子を第３の識別子集合として退避させる。
［Ｓ２５］同一タグ存在判定手段１５は、第２の識別子集合に属しているタグ（同定処理の対象となるタグ）がまだあるか否かを判定する。その結果、タグがまだあると判定した場合にはステップＳ２１に戻り、次のタグに対する同定処理を行う。また、タグがないと判定した場合には、図３の処理に復帰（リターン）する。
【００２７】
以上の処理によれば、索引を利用して同一のタグが存在しているか否かを高速に判定した後、同一のタグが存在している場合には、対応する識別子同士を比較するようにしたので、同一なタグを持つ識別子の数は、識別子集合内の要素数に比較して十分少なくなっていることから、同定処理を迅速に実行することが可能となる。
【００２８】
なお、以上のようにして生成された第３の識別子集合は入力された第１の識別子集合と第２の識別子集合の論理積となっている。また、第１の識別子集合と重複する識別子を取り除いた第２の識別子集合は識別子の重複がないため、第１の識別子集合と第２の識別子集合とを単純に結合しただけで、第１および第２の識別子集合の論理和を作成することができる。
【００２９】
次に、図６を参照して本発明の第２の実施の形態の構成例について説明する。なお、この図において、図２の場合と対応する部分には同一の符号が付してあるのでその説明は省略する。
【００３０】
この実施の形態においては、図２の場合と比較してデータ構造情報記録手段２０が新たに追加されているとともに、識別子分割手段１２、タグ生成手段１３、および、識別子同一性判定手段１６における処理が異なっている。その他の構成は、図２の場合と同様である。
【００３１】
データ構造情報記録手段２０は、識別子のデータ構造に関する情報を記録しており、要求がなされた場合には、必要な情報を、識別子分割手段１２、タグ生成手段１３、または、識別子同一性判定手段１６に供給する。
【００３２】
識別子分割手段１２は、データ構造に応じて識別子を分割する。
タグ生成手段１３は、データ構造情報記録手段２０に記録されている情報を参照して、識別子の値のばらつきが大きい部分に対して、タグのデータ領域をより多く割り当てることにより、衝突の少ないタグを生成する。
【００３３】
識別子同一性判定手段１６は、同一のタグが存在している場合には、データ構造情報記録手段２０に記録されている情報を参照して、比較コストが小さい部分から識別子を順次比較する。
【００３４】
次に、以上の実施の形態の動作について説明する。なお、以下の処理では、前述の場合と同様に、第１および第２の識別子集合の同定処理を例に挙げて説明を行う。また、前述の場合と同様の処理については説明を省略する。
【００３５】
識別子が入力されると、識別子分割手段１２は、データ構造情報記録手段２０に記録されている構造情報を参照し、同一の属性を有する領域毎に識別子を分割する。
【００３６】
タグ生成手段１３は、入力されたすべての識別子から対応するタグを生成する。即ち、タグ生成手段１３は、データ構造情報記録手段２０に予め記録されている識別子の構造情報を参照し、識別子の構造に応じてタグを生成する。例えば、識別子の値のばらつき（統計的なばらつき）が多い部分に対して、タグのデータ領域をより多く割り当てることによって、異なる識別子から生成されるタグが重なりにくいように最適化する。
【００３７】
いま、図７に示すような構造情報を参照してタグを生成する場合を考える。この例では、識別子は以下のようなデータによって構成されている。
（Ａ）length  ・・・  ４バイトの整数データであり、全ての識別子が同一の値（固定値）を有する。
（Ｂ）name  ・・・  固定値を持つ文字列。
（Ｃ）unknown   ・・・  ２０４８バイトのバイナリデータであり、特定の値をとる。
（Ｄ）number  ・・・  ４バイトのデータが１６個並んだ配列データであり、１つ１つのデータは、４バイトで表現可能な数値すべてを表す。
【００３８】
なお、以上のような構造情報の代わりに、図８に示すような構造情報を用いることも可能である。即ち、このような構造情報の場合では、「役割」の“長さ”や“区切り”により、他のフィールドの長さを決定することによって、可変長データである識別子を表現することができる。
（Ａ）length  ・・・  ４バイトの整数であり、nameの長さを表す。
（Ｂ）name  ・・・  文字列であり、データ長は前述のlengthによって表される。
（Ｃ）unknown1  ・・・  バイナリデータであり、データの末端はフィールドbo                        undaryによって決定される。
（Ｄ）boundary  ・・・  ４バイトの整数であり、その値は０である。前後のデータの区切りを表す。
（Ｅ）unknown2  ・・・  バイナリデータであり、データの先頭はフィールドbo                        undaryによって決定される。
【００３９】
ここでは、図７に示す構造情報について話をすすめる。この例では、ばらつき度の項目に示してあるように、「length」および「name」では、ばらつきは固定値となっているため、その他のフィールドに対してのみタグの領域を割り当てることが望ましい。
【００４０】
従って、先ず、識別子分割手段１２が、構造情報に応じて識別子を、「length」、「name」「unknown 」「number」の４つの領域に分割する。そして、タグ生成手段１３は、構造情報の「ばらつき度」を参照して、numberのフィールドに対応するタグ部分に多くの領域を割り当て、固定値を有するlengthやnameに対応するフィールドはタグ生成に利用しない。ここでは、タグのデータ長を４バイトとし、ばらつき度の重みを図９のようにすると、全体の重みが５（＝４＋１）となる。
【００４１】
その結果、unknown は４×１÷５＝０．８となり、一方、numberは、４×４÷５＝３．２となり、四捨五入して１バイトと３バイトをそれぞれ割り当てる。そして、例えば、ハッシュ関数によって、unknown を１バイト、また、numberを３バイトのハッシュ値に変換する。
【００４２】
このように構造情報を利用してタグの生成方法を決定することによって、タグの衝突を減少させることができる。
なお、それぞれのフィールドを等価に１バイトずつ割り当てた場合では、タグの領域のうち、lengthとnameとに対応する領域の２バイト分はすべてのタグで同じ値となり、実質的に表現できるタグの値は２（＝４−２）バイトになり、タグの衝突が起きやすくなる。
【００４３】
以上の実施の形態では、重みに応じてフィールドを割り当てるようにしたが、例えば、データ型など別の情報に応じてハッシュ関数を変更するようにしてもよい。
【００４４】
以上のようにして作成されたタグを元にして、索引生成手段１４が索引（第１の識別子集合に対する索引）を生成する。
次に、第２の識別子集合が入力された場合の同定処理について説明する。
【００４５】
第２の識別子集合が入力されると、識別子分割手段１２は、第１の識別子集合の場合と同様の分割方法により、第２の識別子集合に属している各識別子を分割する。タグ生成手段１３も前述の場合と同様の処理によりタグを生成する。
【００４６】
同一タグ存在判定手段１５は、第１の識別子集合に対する索引を参照することにより、同一のタグが存在しているか否かを判定する。
その結果、同一のタグが存在していると判定された場合には、識別子同一性判定手段１６は、これらのタグに対応する識別子が同一であるか否かを判定する。即ち、識別子同一性判定手段１６は、偶然にタグが同一になった識別子であるか、同一の識別子であるかを判定する。
【００４７】
識別子同一性判定手段１６は、先ず、データ構造情報記録手段２０から識別子の構造情報を取得し、フィールドの比較順序を決める。即ち、値のばらつきの多いフィールドや、バイト数が少ないなど比較処理コストの小さいフィールドから比較する。また、固定値を持つ（すべての識別子において同じ値を有する）フィールドは比較対象にしない。いまの例では、「number」に対応するフィールドのばらつき度が大きいので、このフィールドを優先して比較処理を行う。そして、このフィールドにおいて同一性が検出されなかった場合には、次に、「unknown 」に対応するフィールドを比較する。なお、「length」および「name」は固定値であるため、これらのフィールドは比較対象としない。フィールドが１つでも異なっていれば、その時点で２つの識別子が異なるものであると判定する。一方、比較対象となるすべてのフィールドが同一であれば、識別子も同一であると判定する。
【００４８】
なお、識別子同一性の判定処理では、ばらつき度によるフィールド判定は複数の識別子を判定する場合であっても一度でよい。
以上の実施の形態によれば、識別子のデータ構造に応じて、ばらつきの大きい部分に対して、タグのデータ領域をより多く割り当てるようにしたためタグの衝突を低減した。さらに、同定処理において、同一のタグがあると判定された場合には、データ構造を参照して、同一性が低い部分、比較コストが低い部分から優先的に比較処理を行うようにしたので、同定処理を高速に実行することが可能となる。
【００４９】
次に、図１０を参照して本発明の第３の実施の形態について説明する。なお、この図において、図６の場合と対応する部分には同一の符号を付してあるのでその説明は省略する。
【００５０】
この実施の形態においては、構造記述データ入力手段３０、構造記述データ解析手段３１、および、書き込み手段３２が新たに追加されている。なお、その他の構成は、図６の場合と同様である。
【００５１】
構造記述データ入力手段３０は、識別子の構造を記述したデータである構造記述データ（図１１参照）を入力する。
構造記述データ解析手段３１は、構造記述データ入力手段３０から入力された構造記述データを解析し、識別子の構造情報（前述の図７および図８参照）を生成する。
【００５２】
書き込み手段３２は、構造記述データ解析手段３１によって得られた識別子の構造情報をデータ構造情報記録手段２０に書き込んで記録させる。
次に、以上の実施の形態の動作について説明する。なお、以下の説明では、前述の場合と同様に、第１および第２の識別子集合の同定処理を例に挙げて説明を行う。また、前述の場合と同様の処理については説明を省略する。
【００５３】
この実施例では、ユーザが識別子のデータ構造を知っているとき、そのデータ構造が記述された構造記述データを入力し、この構造記述データを解析して構造情報を生成し、データ構造情報記録手段２０に書き込む。そして、この構造情報を参照して、第２の実施の形態の場合と同様の処理により、タグの生成処理や同定処理を行う構成とされている。なお、識別子の同定方法は第２の実施の形態の場合と同様であるため、以下では、構造情報の登録手順についてのみ説明する。
【００５４】
例えば、図７に示す構造情報を有する識別子に対する構造記述データは、図１１のようになる。この例の第１行目に示されている「int length 4*1  const;」は、このフィールドが、整数型（int ）であり、４バイト（4*1 ）の長さを持ち、また、固定値（const ）を有することを示している。このように、構造記述データは、データ型、フィールド名、データ長、ばらつき度を示している。
【００５５】
同様にして、「string」は文字列型を、「bin 」はバイナリ型を、「change」はばらつきが小さいことを、「volatile」はばらつきが大きいことを表す。
また、図１２は、図８に示す構造情報を有する識別子に対する構造記述データの一例である。この例では、第４行目に、データの「区切り」を示す「bound 」が示されている。この「bound 」は「区切り」であることを指している。なお、構造記述データのシンタックスは問わない。構造記述データによって構造情報を表現できればよい。
【００５６】
このような構造記述データは、例えば、テキストエディタなどにより作成し、構造記述データ入力手段３０から入力する。
入力された構造記述データは、構造記述データ解析手段３１によって解析される。即ち、構造記述データ解析手段３１は、入力された構造記述データをパーズ（構造解析）し、構造情報を有する解析木を作成する。そして、パーズによって得られた解析木から構造情報を作成する。
【００５７】
以上のようにして作成された構造情報は、書き込み手段３２によってデータ構造情報記録手段２０の所定の領域に書き込まれる。
このようにして作成された構造情報は、第２の実施の形態において説明したように、タグの作成処理と同定処理において参照されることになる。
【００５８】
次に、図１３を参照して、本発明の第４の実施の形態の構成例について説明する。なお、この図において、図１０の場合と対応する部分には同一の符号を付してあるのでその説明は省略する。
【００５９】
この実施の形態においては、データ構造解析手段４０、指示情報付与手段４１、および、候補絞り込み手段４２が新たに追加されており、また、識別子同一性判定手段１６の処理が異なっている。その他の構成は、図１０の場合と同様である。
【００６０】
データ構造解析手段４０は、識別子入力手段１１から入力された複数の識別子のデータ構造を統計的な手法により解析する。
指示情報付与手段４１は、同一タグ存在判定手段１５によって同一のタグが存在すると判定された場合には、そのタグに対応する識別子と新たに入力された識別子とを比較し、これらの間で異なる部分を特定し、特定した部分を指示する指示情報を索引に対して付与する。
【００６１】
候補絞り込み手段４２は、同一タグ存在判定手段１５によって同一のタグが複数存在すると判定された場合には、指示情報付与手段４１によって付与された指示情報を参照して、異なる部分のみを比較することにより、候補を絞り込む。
【００６２】
識別子同一性判定手段１６は、絞り込まれた候補と新たに入力された識別子との同一性を識別子のデータ構造を参照して判定する。
次に、以上の実施の形態の動作について説明する。なお、以下の説明では、前述の場合と同様に、第１および第２の識別子集合の同定処理を例に挙げて説明を行う。また、前述の場合と同様の処理については説明を省略する。
【００６３】
データ構造解析手段４０は、識別子入力手段１１から入力された複数の識別子を統計的手法により解析し、識別子の構造情報を生成する。図１４は、データ構造解析手段４０において実行される処理の一例を説明するフローチャートである。このフローチャートが開始されると、以下の処理が実行されることになる。
［Ｓ４１］識別子入力手段１１から解析しようとする識別子を入力する。
【００６４】
ここでは、１００個の識別子を入力したものとする。
［Ｓ４２］識別子入力手段１１から入力されたすべての識別子を処理に適する大きさのセグメントに分割する。
【００６５】
この分割の様子を図１５に示す。各識別子は、それぞれが４バイトからなるｎ個のセグメントに分割される。なお、インデックスは、各セグメントを特定するために割り振った番号である。
［Ｓ４３］すべてのセグメントからセグメントごとの統計情報を得る。
【００６６】
即ち、第ｉ（１≦ｉ≦ｎ）番目のセグメントの値の分布を調べ、同一の値がいくつ存在しているかを検出する。そして、これをまとめて解析結果とする。
解析結果の一例を図１６に示す。この例では、インデックスの１から４までは、値の種類（値の分布）が１種類だけである（１００個全てのセグメントが同一の値を有している）。また、インデックスの２６１から２７２までは、値の種類は７種類であり、また、同一の値の最大個数は７９個であることが分かる。
［Ｓ４４］ステップＳ４３での解析結果に基づいて構造情報を生成する。
【００６７】
即ち、各セグメントの値の偏り具合から、データ型と値のばらつき度を推定する。このとき、隣接するセグメントのデータ型とばらつき度が同一であったら、ひとまとめにする。なお、ここでは、たとえば、ばらつき度は「大きい」と「中程度」の境界を値の種類数２０とし、また、「小さい」と「中程度」の境界を種類数５とする。
【００６８】
例えば、図１６に示す解析結果を対象として、前後のインデックスのばらつき度が同一である場合にはそのインデックスをまとめる処理を実行すると、図１７に示すような構造情報を得ることができる。
［Ｓ４５］データ構造解析手段４０は、生成された構造情報を書き込み手段３２に対して出力する。
【００６９】
以上の処理により、識別子の構造が未知の場合においても、複数の識別子から構造情報を推定することが可能となる。これらの処理は、識別子集合の同定処理と同時ではなく事前に実行し、構造情報を得ることができる。
【００７０】
次に、図１８を参照して、タグおよび索引の生成処理について説明する。このフローチャートが開始されると以下の処理が実行されることになる。
［Ｓ６１］タグ生成手段１３は、データ構造情報記録手段２０に記録されている構造情報に基づいて、入力された識別子からタグを生成する。
［Ｓ６２］同一タグ存在判定手段１５は、索引を参照し、同一のタグが存在しているか否かを判定する。その結果、同一のタグが存在している場合にはステップＳ６３に進み、存在していない場合にはステップＳ６５に進む。
［Ｓ６３］指示情報付与手段４１は、衝突しているタグに対応する識別子を比較し、異なっている部分を特定する。
［Ｓ６４］指示情報付与手段４１は、ステップＳ６３において特定された識別子の異なる部分を指示する指示情報を索引に付与する。
［Ｓ６５］タグ生成手段１３は、全ての識別子に対するタグの生成処理が終了したか否かを判定する。その結果、タグの生成が終了した場合には処理を完了し、また、終了していないと判定した場合にはステップＳ６１に戻る。
【００７１】
以上の処理により、タグの衝突が発生した場合には、それらのタグに対応する識別子が比較され、異なっている部分が特定される。そして、特定された部分を指示する指示情報が索引に付加されることになる。
【００７２】
次に、以上のようにして作成された索引を参照して、識別子を同定する場合の処理について説明する。
図１９は、図１８の処理によって作成された、指示情報が付与された索引を参照して、識別子を同定する場合の処理の一例を説明するフローチャートである。このフローチャートが開始されると、以下の処理が実行されることになる。
［Ｓ８１］同一タグ存在判定手段１５は、索引を参照し、比較の対象となる識別子のタグと同一のタグを取得する。
［Ｓ８２］同一タグ存在判定手段１５は、同一のタグが１つだけ存在しているか否かを判定する。その結果、同一のタグが１つだけ存在している場合にはステップＳ８５に進み、また、複数存在している場合にはステップＳ８３に進む。
［Ｓ８３］候補絞り込み手段４２は、索引から指示情報を取得する。
［Ｓ８４］候補絞り込み手段４２は、取得した指示情報を参照し、識別子の異なる部分だけを比較して、候補を１つに絞る。
［Ｓ８５］識別子同一性判定手段１６は、データ構造情報記録手段２０に記録されている構造情報を参照して、識別子を比較する部分を特定する。
［Ｓ８６］識別子同一性判定手段１６は、候補絞り込み手段４２によって絞り込まれた候補の識別子と、比較の対象となる識別子との相違を、ステップＳ８５において特定された部分を比較することによって判定する。
【００７３】
以上の処理によれば、索引作成時、同一タグを持つ識別子間において、異なる値を有するフィールドを示す情報を索引に持たせ、識別子の同定時には、構造情報ではなく、この情報をもとに識別子を比較するようにしたので、タグの衝突によって複数の識別子が同一の識別子の候補として現われても、少ない比較処理によって１つの識別子に絞り込むことができる。
【００７４】
なお、以上の実施の形態は、１つの識別子集合に対して索引を作成し、いくつもの識別子集合と演算する場合や、タグが衝突しやすい場合（たとえば、識別子に未知の部分が多く、処理があまり最適化されていない場合）に有効である。
【００７５】
次に、以上の実施の形態をファイルのコピー管理に適用した場合について説明する。以下では、２つのデータ管理装置において、一方のデータ管理装置Ａのデータをもう一方のデータ管理装置Ｂへコピー（転写）して、そのデータ間の一貫性を管理するために、その対応関係を管理している場合について考える。
【００７６】
データ管理装置Ａからの検索結果となる識別子集合Ａと、データ管理装置Ｂからの検索結果となる識別子集合Ｂとがあるとき、識別子集合Ａの要素である識別子ａと識別子集合Ｂの要素である識別子ｂとが同じデータ( オリジナルデータとコピーされたデータ) を示している可能性がある。このため、検索結果をそのままマージしたのでは、コピーされているデータが重複することになる。同時に利用する管理システムが多くなるほど、また、データのコピーが多くなるほど、このような問題は深刻になる。
【００７７】
そのような場合に対処するための処理の一例を図２０に示す。このフローチャートが開始されると、以下の処理が実行されることになる。
［Ｓ１０１］データ管理装置Ａからの検索結果として識別子集合Ａを、また、データ管理装置Ｂからの検索結果として識別子集合Ｂを得る。
［Ｓ１０２］オリジナルデータとコピーデータの識別子の対応表を利用して、識別子集合Ｂの要素を対応するオリジナルのデータの識別子に変換する。
［Ｓ１０３］ステップＳ１０２において、オリジナルデータに変換できなかった識別子集合を識別子集合Ｂ’とする。一方、変換できた識別子集合を識別子集合Ｂ”とする。
［Ｓ１０４］図２、図６、図１０、または、図１３の実施の形態により、識別子集合Ａと識別子集合Ｂ”の重複する識別子をチェックする。
［Ｓ１０５］図２、図６、図１０、または、図１３の実施の形態により、識別子集合Ａと識別子集合Ｂ”の論理和を算出する。
［Ｓ１０６］ステップＳ１０５において得られた結果と、識別子集合Ｂ’とをマージする。
【００７８】
このような処理によれば、重複のない検索結果を得ることができる。
以上に示したように、本発明を利用した結果である識別子集合の論理和を利用すると、簡単な処理で複数のデータ管理装置にわたってデータの重複のない検索結果を得ることができる。
【００７９】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、データ管理装置が有すべき機能の処理内容は、コンピュータで読み取り可能な記録媒体に記録されたプログラムに記述されており、このプログラムをコンピュータで実行することにより、上記処理がコンピュータで実現される。
【００８０】
コンピュータで読み取り可能な記録媒体としては、磁気記録装置や半導体メモリ等がある。市場を流通させる場合には、ＣＤ−ＲＯＭ(Compact Disk Read Only Memory) やフロッピーディスク等の可搬型記録媒体にプログラムを格納して流通させたり、ネットワークを介して接続されたコンピュータの記憶装置に格納しておき、ネットワークを通じて他のコンピュータに転送することもできる。コンピュータで実行する際には、コンピュータ内のハードディスク装置等にプログラムを格納しておき、メインメモリにロードして実行する。
【００８１】
【発明の効果】
以上説明したように本発明では、識別子入力手段から識別子を入力し、識別子分割手段は、入力された識別子を、識別子よりも短い所定のデータ長の複数のセグメントに分割し、タグ生成手段は、得られた複数のセグメント間において排他的論理和を演算することにより、所定のデータ長のタグを生成し、索引生成手段は、タグ生成手段によって生成されたタグを元にして索引を生成するようにしたので、同一のタグをもつ識別子を効率よくまとめることができ、識別子の同定処理を高速に実行することが可能となる。
また、本発明では、識別子入力手段から識別子を入力し、識別子分割手段は、入力された識別子を、識別子を構成するフィールド毎に分割し、タグ生成手段は、得られた個々のフィールドの値から、取り得る値の個数が多いフィールドほど桁数の大きいハッシュ値を計算し、複数のハッシュ値を結合して、識別子よりもデータ長の短いタグを生成し、索引生成手段は、タグ生成手段によって生成されたタグを元にして、索引を生成するようにしたので、タグの衝突をより低減でき、識別子の同定処理を高速に実行することが可能となる。
【図面の簡単な説明】
【図１】本発明の原理を示す原理図である。
【図２】本発明の第１の実施の形態の構成例を示す図である。
【図３】図２に示す実施の形態において実行される処理の一例を説明するフローチャートである。
【図４】図２に示す実施の形態において生成される索引の一例を示す図である。
【図５】図２に示す実施の形態において実行される同定処理の一例を説明するフローチャートである。
【図６】本発明の第２の実施の形態の構成例を示す図である。
【図７】図６に示す実施の形態において使用される構造情報の一例を示す図である。
【図８】構造情報の他の一例を示す図である。
【図９】ばらつきと重みとの関係を示す図である。
【図１０】本発明の第３の実施の形態の構成例を示す図である。
【図１１】図１０に示す実施の形態において使用される構造記述データの一例を示す図である。
【図１２】図１０に示す実施の形態において使用される構造記述データの他の一例を示す図である。
【図１３】本発明の第４の実施の形態の構成例を示す図である。
【図１４】図１３に示す実施の形態において実行される処理の一例を示す図である。
【図１５】図１３に示す実施の形態によってセグメントに分割された識別子の様子を示す図である。
【図１６】図１３に示す実施の形態によって解析されたセグメントの情報の一例を示す図である。
【図１７】図１６に示す解析結果から生成された構造情報の一例を示す図である。
【図１８】図１３に示す実施の形態において実行される処理の一例を説明するフローチャートである。
【図１９】図１３に示す実施の形態において実行される処理の他の一例を説明するフローチャートである。
【図２０】データのコピー管理に本発明を適用した場合の処理の一例を説明するフローチャートである。
【符号の説明】
１  識別子入力手段
２  識別子分割手段
３  タグ生成手段
４  索引生成手段
１１  識別子入力手段
１２  識別子分割手段
１３  タグ生成手段
１４  索引生成手段
１５  同一タグ存在判定手段
１６  識別子同一性判定手段
２０  データ構造情報記録手段
３０  構造記述データ入力手段
３１  構造記述データ解析手段
３２  書き込み手段
４０  データ構造解析手段
４１  指示情報付与手段
４２  候補絞り込み手段
【図１】
0003855423.tif 000002
【図２】
0003855423.tif 000003
【図３】
0003855423.tif 000004
【図４】
0003855423.tif 000005
【図５】
0003855423.tif 000006
【図６】
0003855423.tif 000007
【図７】
0003855423.tif 000008
【図８】
0003855423.tif 000009
【図９】
0003855423.tif 000010
【図１０】
0003855423.tif 000011
【図１１】
0003855423.tif 000012
【図１２】
0003855423.tif 000013
【図１３】
0003855423.tif 000014
【図１４】
0003855423.tif 000015
【図１５】
0003855423.tif 000016
【図１６】
0003855423.tif 000017
【図１７】
0003855423.tif 000018
【図１８】
0003855423.tif 000019
【図１９】
0003855423.tif 000020
【図２０】
0003855423.tif 000021