(57)【要約】本発明はコンテンツ、特に第１及び第２ファイルに共通する１つ以上の抽出部分の検索方法に関する。本方法は少なくとも第１ファイルを準備する予備ステップとして、（ａ）第１ファイルを所定サイズの一連のデータパケットに分割し、ファイル内のパケットアドレスを識別し、（ｂ）各パケットアドレスを、ファイルから生じるデータの組み合わせ計算の結果として３つのファジー論理状態（真、偽、不定）を規定するデジタル署名と組み合わせる。本発明は、（ｃ）第１ファイルの各パケットアドレスに組み合わされたファジー論理状態を、第２ファイルから生じたデータに基づいて決定されたファジー論理状態と比較し、（ｄ）論理状態が真かつ偽、又は偽かつ真である第１及び第２ファイルのアドレスのペアを、共通の抽出部分の検索から排除し、また共通の抽出部分を含む可能性のあるデータパケットを特定する他のペアを保持することで、共通の抽出部分を実際に検索する。【選択図】図７Ｃ
2007531948.tif 000002
【特許請求の範囲】
【請求項１】
バリナリデータ形式の第１ファイルと第２ファイルとに共通する、１つ以上の抽出部分を検索するコンテンツ検索方法であって、
少なくとも第１ファイルの前準備として、
ａ）前記第１ファイルを、選択されたサイズをもった一連のデータパケットに区分し、該ファイル内のパケットのアドレスを識別するステップと、
ｂ）各パケットのアドレスにデジタル署名を関連付けるステップであって、該デジタル署名が、少なくとも３つの状態、つまり、「真」、「偽」、及び「不定」のうちから、１つのファジー論理状態を規定するとともに、該デジタル署名が、前記ファイルから生じるデータの組み合わせ計算の結果として得られるステップと、を有し、
さらに、前記方法は、共通の抽出部分の検索を続行するとともに、
ｃ）前記第１ファイルの各パケットアドレスに関連付けられたファジー論理状態を、前記第２ファイルから生じるデータに基づいて決定されたファジー論理状態と比較するステップと、
ｄ）前記共通の抽出部分の検索から、前記第１ファイル及び第２ファイルの各アドレスのペアであって、それぞれの論理状態が「真」及び「偽」、あるいは「偽」及び「真」とされるアドレスのペアを排除するとともに、前記共通の抽出部分を含む傾向をもつデータパケットを特定するアドレスのペアを保持するステップと、を有することを特徴とする方法。
【請求項２】
前記ステップｂ）において、データパケットには、
前記パケットのデータが全て第１の条件を満たす場合に、状態「真」を割り当て、
前記パケットのデータが全て前記第１の条件とは正反対である第２の条件を満たす場合に、状態「偽」を割り当て、
前記パケットの特定のデータが前記第１の条件を満たし、前記パケットの他のデータが前記第２の条件を満たす場合に、状態「不定」を割り当てることを特徴とする、請求項１に記載の方法。
【請求項３】
前記ステップｂ）に先立つ処理がファイルのデータに適用され、該先立つ処理は、
ａ１）前記ファイルのデータが、所定のサンプリング周波数（Ｆｅ）で得られ、かつ２進法表示コードに従ってコード化された値をもったサンプルの文字列とみなされるステップと、
ａ２）前記サンプル（ｆｎ）に対してデジタルフィルタを適用するステップであって、該フィルタが、前記サンプルのパケットに関連付けられたデジタル署名について「不定」状態を得る確率を最小限にするように構成されたステップと、を有することを特徴とする、請求項１又は２に記載の方法。
【請求項４】
前記デジタルフィルタの適用として、
前記サンプルデータにスペクトル変換を適用し、
前記スペクトル変換にローパスフィルタを適用し、
前記ローパスフィルタの後に、逆スペクトル変換を適用する、ことを特徴とする請求項３に記載の方法。
【請求項５】
前記ローパスフィルタは、
ほぼ［−Ｆｅ／２（ｋ−１），＋Ｆｅ／２（ｋ−１）］の区間の周波数帯域で動作し、
ここで、「Ｆｅ」は前記サンプリング周波数であり、「ｋ」はパケットに含まれるサンプルの数である、ことを特徴とする請求項４に記載の方法。
【請求項６】
前記デジタルフィルタが、同様の値の所定数の係数を含み、関連付けられた前記ローパスフィルタの周波数応答が、周波数ｆの関数として、
ｓｉｎ（ＰＩ・ｆ・Ｔ）／（ＰＩ・ｆ・Ｔ）
の形式で表現され、ここで、「ｓｉｎ（）」は正弦関数であり、
ＰＩ＝３．１４１６及び
Ｔ＝（Ｋ−１）／Ｆｅ
であり、ここで、「Ｋ」は係数の所定数であり、「Ｆｅ」は前記サンプリング周波数である、ことを特徴とする、請求項４又は５に記載の方法。
【請求項７】
前記デジタルフィルタが、所定数（２Ｋ＋１）個の係数をもった平均値フィルタであり、２つの連続するフィルタ処理されたサンプル間の差（ｒｎ＋１−ｒｎ）が、２つのフィルタ処理されていないサンプルであって係数の前記所定数だけ離れた、第１のランク及び第２のランクをもったサンプル間の差（ｆｎ＋Ｋ＋１−ｆｎ−Ｋ）に比例し、前記フィルタ処理されたサンプルの計算がこの関係を用いて実行され、行うべき計算動作の回数が低減されるようにしたことを特徴とする、請求項３から６のいずれか１項に記載の方法。
【請求項８】
前記フィルタの係数の所定数（２Ｋ＋１）は、「２ｋ−１」以上であり、ここで、「ｋ」がパケットに含まれるサンプルの数であることを特徴とする、請求項６又は７に記載の方法。
【請求項９】
パケットに対して、前記フィルタ処理されたサンプルの全てが選択された基準値（Ｖｒｅｆ）よりも大きい場合に、該パケットのアドレスに状態「真」を割り当て、
前記パケットに対して、前記フィルタ処理されたサンプルの全てが選択された基準値（Ｖｒｅｆ）よりも小さい場合に、該パケットのアドレスに状態「偽」を割り当て、
前記パケットに対して、前記フィルタ処理されたサンプルのあるものが選択された基準値（Ｖｒｅｆ）よりも小さく、かつ前記フィルタ処理されたサンプルの他のものが選択された基準値（Ｖｒｅｆ）よりも大きい場合には、該パケットのアドレスに状態「不定」を割り当てることを特徴とする、請求項２及び請求項３から８のいずれか１項に記載の方法。
【請求項１０】
任意の次数ｎをもつ、フィルタ処理されたサンプルｒｎの全てに対して、前記基準値（Ｖｒｅｆ）が、任意の同一次数ｎをもつ、フィルタ処理されていないサンプルｆｎを中心として、選択された数のフィルタ処理されていない連続のサンプルに亘って、フィルタ処理されていないサンプルｆｋの値を平均化することにより計算されることを特徴とする、請求項９に記載の方法。
【請求項１１】
前記フィルタ処理されたサンプルの値は、比較のために、ゼロ閾値に対して得られ、前記フィルタ処理されたサンプルｒ’ｎが、以下の形式の和で表現され、
2007531948.tif 000035
ここで、
「ｆｎ＋ｋ」は、前記ステップａ１）で得られたフィルタ処理されていないサンプルであり、
「Ｋ」は、前記デジタルフィルタの係数の個数であり、好ましくは偶数に選択され、
「Ｋｒｅｆ」は、フィルタ処理されていないサンプルｆｎの周りでの、前記フィルタ処理されていないサンプルの数であり、好ましくは偶数であって、かつ係数の個数Ｋよりも大きくなるように選択されることを特徴とする、請求項１０に記載の方法。
【請求項１２】
前記の和は、並行して行われる処理に従って、前記フィルタ処理されていないサンプルｆｎに対して、それぞれ前記係数の個数Ｋを変化させて複数回数適用されることを特徴とする、請求項１１に記載の方法。
【請求項１３】
少なくとも前記第１ファイルに関連付けられたファジー状態はそれぞれ、少なくとも２ビットでコード化されることを特徴とする、請求項１から１２のいずれか１項に記載の方法。
【請求項１４】
係数の最小の個数Ｋについて決定されたファジー状態が、最小有効ビットに関してコード化され、係数のより大きい個数Ｋについて決定されたファジー状態が、後続のビットに関してコード化され、選択された総ビット数まで同様にコード化されるようにしたことを特徴とする、請求項１２又は請求項１３に記載の方法。
【請求項１５】
フィルタ処理された各サンプルｒｎが、以下の形式の和として表現され、
2007531948.tif 000036
ここで、
「ｆ（ｎ＋ｉ）」は、フィルタ処理されていないサンプルであり、
「ｆｉｌｔｅｒｉ」は、デジタルフィルタの係数であり、場合によっては０とされる閾値を取り入れた係数であり、
そして、パケットに含まれる、フィルタ処理されていないサンプルの数ｋが選択され、これは、最小で２に等しく、式「（ＴＥＦ−Ｉ１−Ｉ２＋１）／２」以下であり、ここで「ＴＥＦ」は、検索される共通の抽出部分についての所望の最小サイズであることを特徴とする、請求項３から１０のいずれか１項に記載の方法。
【請求項１６】
検索される共通の抽出部分についての、前記した所望の最小サイズの任意値「ＴＥＦ」に対して、パケットに含まれるフィルタ処理されていないサンプルの前記した数ｋとして使用可能な値の範囲が決定され、
前記の数ｋとして使用可能な各々の値に対して、デジタル署名の連続するデータの最適サイズ「ＴＥＳ」が決定され、その連続に対してサイズＴＥＦの共通の抽出部分の検出が保証され、
前記最適サイズ「ＴＥＳ」が、式Ｅ［（ＴＥＦ−Ｉ１−Ｉ２＋１）／ｋ］−１以下であり、ここで、Ｅ（Ｘ）はＸの整数部を示す、ことを特徴とする請求項１５に記載の方法。
【請求項１７】
比較される２つのファイルが、英数字文字、特にテキスト及び／又はコンピュータ又は遺伝子コード、を表すデータを含む場合において、
粗い検索のための、デジタル署名の形成とそれらの比較を含む、第１のグループのステップと、
前記粗い検索を満足するアドレスの範囲における同一性の比較を含む、第２のグループのステップと、を有し、
ファイルのデータは、パケット毎の選択される数ｋのサンプルとされる該サンプルの文字列とみなされ、
この選択された数ｋの値は、実行される最小の比較演算を探すことにより、初期に最適化されることを特徴とする。請求項１から１６のいずれか１項に記載の方法。
【請求項１８】
パケット毎のサンプルの前記選択される数ｋの最適化について、
実行すべきデジタル署名の比較演算の総数、及び、
その後に実行すべきデータの同一性を比較する演算の総数が考慮され、
前記演算の総数は有限の組の数ｋに対して最小値であることを特徴とする、請求項１７に記載の方法。
【請求項１９】
パケット毎のサンプルの前記選択される数ｋを最適化するために用いる情報であって、検索される共通の抽出部分の、最小の所望のサイズ（ＴＥＦ）に関する情報が得られ、そして、パケット毎のサンプルの最適数ｋが、前記最小サイズ（ＴＥＦ）に伴って実質的に変化して、検索される共通の抽出部分についての所望の最小サイズが大きいほど、共通の抽出部分の検索にかかる期間が短くなることを特徴とする、請求項１７又は１８に記載の方法。
【請求項２０】
デジタル署名の形成及びその比較を含むステップの単一のグループを構成する、共通の抽出部分の検索を有し、パケット毎のデータ項目数は、共通の抽出部分についての誤検出確率の許容される閾値を明示する信頼度指数を初期に定めることで最適化されることを特徴とする、請求項１から１６のいずれか１項に記載の方法。
【請求項２１】
前記第１ファイルに対して、
選択されたサンプリング周波数でのサンプリングを行い、
周波数空間でのローパスフィルタリングに対応するデジタルフィルタリングを行い、
前記第１ファイルのアドレスのそれぞれに関連付けられた「真」、「偽」又は「不定」状態でのデジタル署名を得るための、フィルタ処理されたサンプルを組み合わせ、
他方、前記第２ファイルに対して、
選択されたサンプリング周波数でのサンプリングを行い、
周波数空間でのローパスフィルタリングに対応するデジタルフィルタリングを行い、
各パケットのフィルタ処理されたサンプルに関連付けられた論理状態を、各パケットから選択された、単一のフィルタ処理されたサンプルに関連付けられた論理状態に基づいて決定し、
これらを「真」又は「偽」の論理状態しか含まないデジタル署名を得るように行い、これにより、前記デジタル署名の比較の選択性を向上させることを特徴とする、請求項３から２０のいずれか１項に記載の方法。
【請求項２２】
前記第１ファイルのアドレスに関連付けられた論理状態が「真」又は「不定」であり、前記第２ファイルのアドレスに関連付けられた論理状態が「真」である場合に、前記アドレスのペアが、共通の抽出部分の検索から保持され、
前記第１ファイルのアドレスに関連付けられた論理状態が「偽」又は「不定」であり、前記第２ファイルのアドレスに関連付けられた論理状態が「偽」である場合に、前記アドレスのペアが、共通の抽出部分の検索に対して保持され、
また、アドレスのその他のペアは、検索から排除されるようにした、ことを特徴とする請求項２１に記載の方法。
【請求項２３】
前記第１及び第２ファイルが、デジタル化された信号のサンプルのファイルであり、データを前処理するステップを有し、ノイズ基準よりも高いレベルをもった信号部分に関連付けられたデータを考慮に入れたことを特徴とする、請求項２０に記載の方法。
【請求項２４】
前記第１及び第２ファイルが、デジタル化された信号のサンプルのファイルであり、好ましくは前記第１及び第２ファイルのパケットの相対サイズを調整することにより、前記第１及び第２ファイルの検索速度の相違を許容するように、検索結果を一元管理するステップを備えたことを特徴とする、請求項２０又は２３に記載の方法。
【請求項２５】
前記第１及び第２ファイルのうち、少なくとも１つはデータストリームであり、共通の抽出部分の検索方法がリアルタイムで実行されることを特徴とする、請求項１から２４のいずれか１項に記載の方法。
【請求項２６】
コンピュータの中央装置のメモリ、又は該中央装置の読取部と協働するように作られたリムーバブルメディアに格納される、コンピュータプログラム製品であって、請求項１から２５のいずれか１項に記載の方法のステップの全て又はその一部を行うための命令を含むことを特徴とする、コンピュータプログラム製品。
【請求項２７】
第１及び第２ファイルに共通する、１つ以上の抽出部分の検索に用いるための、第１ファイルを表わすデータ構造であって、
前記データ構造は、請求項１から２５のいずれか１項に記載した方法の前記ステップａ）及びｂ）を実施することにより得られ、
前記第１ファイルのアドレスを識別し、それぞれについて状態「真」、「偽」、及び「不定」のうちから、１つのファジー論理状態が割り当てられる一連のアドレスを含む、ことを特徴とするデータ構造。
【請求項２８】
前記第１及び第２ファイルに共通する、１つ以上の抽出部分を検索するために、少なくとも第１及び第２ファイルを格納するメモリを備えたコンピュータ装置であって、
請求項２６に記載のコンピュータプログラム製品の命令を格納するためのメモリを備える、ことを特徴とするコンピュータ装置。
【請求項２９】
第１ファイルを格納するための第１コンピュータエンティティと、
第２ファイルを格納するための第２コンピュータエンティティと、
前記第１コンピュータエンティティと前記第２コンピュータエンティティとの間の通信手段と、を備えたコンピュータ設備であって、
前記エンティティのうちの１つは、少なくとも、前記第１及び第２ファイルに共通の抽出部分を検索するために、請求項２６に記載のコンピュータプログラム製品の命令を格納するためのメモリを備える、ことを特徴とするコンピュータ設備。
【請求項３０】
前記コンピュータプログラム製品を格納するエンティティは、前記第１及び第２ファイルの一方と、前記第１及び第２ファイルの他方との遠隔アップデートを行うように設計されていることを特徴とする請求項２９に記載の設備。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータのコンテンツ検索に関し、特に２つのファイルに共通する抽出部分の検索に関する。
【０００２】
より具体的には、本発明は第１ファイルと第２ファイルとに共通する、１つ以上の抽出部分を、バイナリ（２進数）データの形式で検索することに関する。
【背景技術】
【０００３】
現在知られている技術では、一般に、データ項目単位での同一性についての検索が提案されている。サイズが大きなファイルに適用する場合には、検索の遅さが致命的となる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、このような状況の改善を目的とする。
【課題を解決するための手段】
【０００５】
従って、本発明はコンテンツ検索方法であって、少なくとも第１ファイルの事前準備として、以下のステップを有する方法を提案するものである。
ａ）第１ファイルを、選択されたサイズをもった一連のデータパケットに区分し、該ファイル内のパケットのアドレスを識別するステップ。
ｂ）各パケットのアドレスにデジタル署名を関連付けるステップであって、該デジタル署名が、少なくとも３つの状態、つまり、「真」、「偽」、及び「不定」のうちから、１つのファジー論理状態を規定するとともに、該署名が、前記ファイルから生じるデータの組み合わせ計算に起因するものとされるステップ。
その後に共通の抽出部分の検索を続行する本方法は、正確には、以下のステップを有する。
ｃ）前記第１ファイルの各パケットアドレスに関連するファジー論理状態を、前記第２ファイルから生じるデータに基づいて決定されるファジー論理状態と比較するステップ。
ｄ）前記共通の抽出部分の検索から、前記第１ファイル及び第２ファイルの各アドレスのペア、即ち、それぞれの論理状態が「真」及び「偽」、あるいは「偽」及び「真」とされるアドレスのペアを排除するとともに、前記共通の抽出部分を含む傾向をもつデータパケットを特定するアドレスの他のペアを保持するステップ。
【０００６】
前記ステップｂ）において、データパケットには、以下の状態が割り当てられる。
「真」（前記パケットの全データが、第１の条件を満たす場合）
「偽」（前記パケットの全データが、前記第１の条件とは正反対である第２の条件を満たす場合）
「不定」（前記パケットのあるデータが前記第１の条件を満たす一方で、前記パケットの他のデータが前記第２の条件を満たす場合）
【０００７】
好ましい実施形態において、前記ステップｂ）に先立つ処理がファイルのデータに適用され、当該処理は以下のステップを有する。
ａ１）前記ファイルのデータが、所定のサンプリング周波数で得られ、かつ２進法表示コードに従ってコード化された値をもったサンプルの文字列とみなされるステップ。
ａ２）前記サンプルに対してデジタルフィルタを適用するステップであって、該フィルタが、前記サンプルのパケットに関連付けられたデジタル署名について「不定」状態を得る確率を最小限にするように適合されたステップ。
【０００８】
好ましくは、前記デジタルフィルタの適用は、
前記サンプルデータにスペクトル変換を適用すること、
前記スペクトル変換にローパスフィルタを適用すること、
前記ローパスフィルタの後に、逆スペクトル変換を適用することである。
【０００９】
前記ローパスフィルタは、実質上、［−Ｆｅ／２（ｋ−１），＋Ｆｅ／２（ｋ−１）］の区間をもった周波数帯域で動作し、ここで、「Ｆｅ」は前記サンプリング周波数であり、「ｋ」はパケットに含まれるサンプルの数である。
【００１０】
有利には、前記デジタルフィルタが、同様の値の所定数の係数を含み、関連付けられた前記ローパスフィルタの周波数応答が、周波数ｆの関数として、
ｓｉｎ（ＰＩ・ｆ・Ｔ）／（ＰＩ・ｆ・Ｔ）
の形式で表現される。尚、ここで、「ｓｉｎ（）」は正弦関数であり、
ＰＩ＝３．１４１６及び
Ｔ＝（Ｋ−１）／Ｆｅ
である。ここで、「Ｋ」は係数の所定数であり、「Ｆｅ」は前記サンプリング周波数である。
【００１１】
好ましくは、前記デジタルフィルタが、所定数の係数をもった平均値フィルタであり、２つの連続するフィルタ処理されたサンプル間の差は、２つのフィルタ処理されていないサンプルであって係数の前記所定数だけ離れた、第１のランク（階数）及び第２のランクをもったサンプル間の差に比例する。前記フィルタ処理されたサンプルの計算はこの関係を用いて実行され、行うべき計算動作の回数が低減される。
【００１２】
前記フィルタの係数の所定数は「２ｋ−１」以上であり、ここで、「ｋ」はパケットに含まれるサンプルの数である。この値は以下に、インデックス比という用語で示される。
【００１３】
好ましくは、
前記パケットに対して、前記フィルタ処理されたサンプルの全てが選択された基準値（Ｖｒｅｆ）よりも大きい場合に、該パケットのアドレスに状態「真」が割り当てられ、
前記パケットに対して、前記フィルタ処理されたサンプルの全てが選択された基準値（Ｖｒｅｆ）よりも小さい場合に、該パケットのアドレスに状態「偽」が割り当てられ、
前記パケットに対して、前記フィルタ処理されたサンプルのあるものが選択された基準値（Ｖｒｅｆ）よりも小さく、かつ前記フィルタ処理されたサンプルの他のものが選択された基準値（Ｖｒｅｆ）よりも大きい場合には、該パケットのアドレスに状態「不定」が割り当てられる。
【００１４】
有利には、任意の次数ｎをもつ、フィルタ処理されたサンプルｒｎの全てに対して、前記基準値（Ｖｒｅｆ）が、任意の同一次数ｎをもつ、フィルタ処理されてないサンプルｆｎを中心として、選択された数の、フィルタ処理されてない連続のサンプルに亘って、フィルタ処理されていないサンプルｆｋの値を平均化することにより計算される。
【００１５】
前記フィルタ処理されたサンプルの値は、比較のために、ゼロ閾値に対して得られ、前記フィルタ処理されたサンプルｒ’ｎは、以下の形式の和で表現される。
【数１】
2007531948.tif 000003
ここで、
「ｆｎ＋ｋ」は、前記ステップａ１）で得られた、フィルタ処理されていないサンプルであり、
「Ｋ」は、前記デジタルフィルタの係数の個数であり、好ましくは偶数に選択され、
「Ｋｒｅｆ」は、フィルタ処理されていないサンプルｆｎの周りでの、前記フィルタ処理されていないサンプルの個数であり、好ましくは偶数であって、かつ係数の個数Ｋよりも大きくなるように選択される。
【００１６】
好ましい実施形態において、前記の和は、並行して行われる処理に従って、前記フィルタ処理されていないサンプルｆｎに対して多数回適用されるが、この間、係数の個数Ｋをそれぞれに変化させる。この措置によって、統計学的にほぼ独立した、複数のデジタル署名を決定することが可能となる。
【００１７】
特定の実施形態において、少なくとも第１ファイルに関連付けられたファジー状態はそれぞれ、２ビット以上でコード化される。
【００１８】
この実施形態では、係数の最小個数Ｋについて決定されたファジー状態が、最小有効ビットに関してコード化され、係数のより大きい個数Ｋについて決定されたファジー状態が、後続のビットに関してコード化され、選択された総ビット数まで同様にコード化される。この選択された数について、好ましくは、比較論理演算のためにコンピュータエンティティのマイクロプロセッサに使用されるバイナリデータサイズに適合し得ることが分かる。
【００１９】
好ましくは、フィルタ処理された各サンプルｒｎが、以下の形式の和として表現される。
【数２】
2007531948.tif 000004
ここで、
「ｆ（ｎ＋ｉ）」は、フィルタ処理されていないサンプルであり、
「ｆｉｌｔｅｒｉ」は、デジタルフィルタの係数であり、場合によっては０とされる閾値を取り入れた係数である。
そして、パケットに含まれる、フィルタ処理されていないサンプルの数ｋが選択され、これは、最小で２に等しく、式「（ＴＥＦ−Ｉ１−Ｉ２＋１）／２」以下である。尚、ここで、「ＴＥＦ」は、検索される共通の抽出部分についての所望の最小サイズである。
【００２０】
この措置によって、好ましくは、単一のデジタル署名のデータ項目の計算に用いる、ｋ個のデータのパケットの重複を保証することができる。
【００２１】
本実施形態において、
検索される共通の抽出部分についての、前記した所望の最小サイズの任意値ＴＥＦに対して、パケットに含まれるフィルタ処理されていないサンプルの前記した数ｋとして使用可能な値の範囲が決定され、
前記の数ｋについての使用可能な各々の値に対して、デジタル署名の連続するデータの最適サイズＴＥＳが決定され、その連続に対してサイズＴＥＦの共通の抽出部分の検出が保証される。
前記最適サイズＴＥＳは、式Ｅ［（ＴＥＦ−Ｉ１−Ｉ２＋１）／ｋ］−１以下であり、ここで、Ｅ（Ｘ）は、Ｘの整数部を示す。
【００２２】
比較される２つのファイルが、英数字文字、特にテキスト及び／又はコンピュータ又は遺伝子コード、を表すデータを含む場合への適用において、前記方法は、有利には、以下のステップを含む。
粗い検索のための、デジタル署名の形成とそれらの比較を含む、第１のグループのステップ。
・前記粗い検索を満足するアドレスの範囲における同一性の比較を含む、特に詳細な検索のための、第２のグループのステップ。
・ファイルのデータは、パケット当たりの選択される数ｋのサンプルとされる該サンプルの文字列とみなされ、この選択された数ｋの値は、実行される最小の比較演算を探すことにより、初期に最適化される。
【００２３】
パケット毎のサンプルについての選択される数ｋの最適化には、以下の総数が考慮される。
実行すべきデジタル署名の比較演算の総数、及び
その後に実行すべきデータの同一性を比較する演算の総数。
この演算の総数は有限の組の数ｋに対して最小値である。
【００２４】
この方法は、有利には、検索される共通の抽出部分についての、最小の所望のサイズに関する手掛かりが得られる過程で、パケット毎のサンプルの選択された数ｋを最適化するために用いるステップを提供する。パケット毎のサンプルの最適数ｋは、前記最小サイズにつれてほぼ変化し、検索される共通の抽出部分の所望の最小サイズが大きいほど、比較演算の総数が減少し、従って、共通の抽出部分の検索にかかる継続期間が短くなる。
【００２５】
オーディオ、ビデオ又はその他のファイルなどのコンテンツ検索に適用する場合に、共通の抽出部分の検索については、好ましくはデジタル署名の形成とそれらの比較を含む、単一グループのステップからなる。パケット毎のデータ項目の数については、共通の抽出部分の誤検出確率について、その許容し得る閾値を明らかにする信頼度指数を、初期に定めることで最適化される。
【００２６】
好適な一般的な実施形態では、前記第１ファイルに対して、
選択されたサンプリング周波数でのサンプリングを適用し、
周波数空間でのローパスフィルタリングに対応するデジタルフィルタリングを適用し、
第１ファイルのアドレスのそれぞれに関連付けられた「真」、「偽」又は「不定」状態でのデジタル署名を得るための、フィルタ処理されたサンプルの組み合わせを適用し、
他方、前記第２ファイルに対して、
選択されたサンプリング周波数でのサンプリングを適用し、
周波数空間でのローパスフィルタリングに対応するデジタルフィルタリングを適用し、
各パケットのフィルタ処理されたサンプルに関連付けられた論理状態を、各パケットから選択された単一のフィルタ処理されたサンプルに関連付けられた論理状態に基づいて決定し（好ましくは、各パケットの第１サンプルとして）、
これらを「真」又は「偽」の論理状態しか含まないデジタル署名を得るように行い、これにより、前記デジタル署名の比較の選択性を向上させる。
【００２７】
この実施形態において、
第１ファイルのアドレスに関連付けられた論理状態が「真」又は「不定」であり、他方で第２ファイルのアドレスに関連付けられた論理状態が「真」である場合に、前記アドレスのペアが、共通の抽出部分の検索から保持され、
第１ファイルのアドレスに関連付けられた論理状態が「偽」又は「不定」であり、他方で第２ファイルのアドレスに関連付けられた論理状態が「偽」である場合に、前記アドレスのペアが、共通の抽出部分の検索に対して保持され、
また、アドレスのその他のペアは、検索から除外される。
【００２８】
当然ながら、本発明の範囲内の方法は、後述するコンピュータプログラム製品などのコンピュータ手段によって実施される。この点について、本発明は、かかるコンピュータプログラム製品、及び、かかるプログラムがそのメモリの１つに格納されたコンピュータエンティティなどの装置をも対象としている。本発明はまた、後で分かるように、通信を行う、この種のコンピュータエンティティのシステムをも対象としている。
【００２９】
このコンピュータプログラムは、特に、バイナリデータのファイルのデジタル署名を生成する能力をもち、このデジタル署名はその後、共通の抽出部分の検索のために、別の署名と比較される。任意のデータファイルのデジタル署名、つまり、本発明の範囲内において形成されるデジタル署名は、比較ステップを行うために必要不可欠な手段であることが分かる。この点に関して、本発明は、このデジタル署名のデータ構造をも対象としている。
【００３０】
本発明のその他の特徴及び利点については、以下の詳細な説明及び添付図面の検討により明らかとなる。
【発明を実施するための最良の形態】
【００３１】
本発明の範囲内での方法は、あり得る全ての共通の抽出部分を検索するために、コンピュータファイルを相互比較することにある。この検査は、ファイルを構成するデータの２進表現に直接に関連し、よって、好ましくは、ファイルのフォーマットに関する予備知識を必要としない。さらに、比較されるファイルについては、テキストファイル、音声や画像を含むマルチメディアファイル、データファイルその他などの、如何なる性質のファイルでもよい。
【００３２】
各ファイルは１次元アレイ（配列）の形式で表現され、バイナリデータがディスク上での格納に用いられるのと同じ順序で配置される。このバイナリデータは、バイト（８ビットワード）である。従って、このアレイは、バイト数ではファイルと同じサイズである。このアレイの各セルは、アドレスによってラベル付けされている。プログラミングで用いる慣行によれば、アドレス０がアレイの最初のセルを指し、アドレス１がその次のセルを指すという具合に、以下同様に続く。
【００３３】
「抽出」という用語、特に「共通の抽出」という決まり文句は、次のように理解される。これは、連続するデータの列を伴い、この列は、決定された開始アドレスから始まるファイルのバイナリデータをコピーすることにより得られる。この列はそれ自体、開始アドレスに関連付けられているバイナリデータアレイの形式で表現され、これにより、元のファイルの抽出部分をラベル付けすることが可能となる。このバイナリデータは、バイト（８ビットワード）であることが示される。各データ項目は、（０と２５５との間にある）整数により表現され、これは、バイトのビットについての「２」を基底とする加算、
Ｂ０＋２１Ｂ１＋．．．＋２７Ｂ７
によって得られる。
【００３４】
従って、このアレイは、明らかに、（バイト数で）抽出部分と同じサイズを有する。この抽出部分のサイズは、１とファイルサイズとの間にある。
【００３５】
テキストフォーマットのファイルに保存されたドキュメントの例では、抽出部分が、例えば、テキストの単語、語句、又はページの場合もある。
【００３６】
本発明の範囲内の方法において、「２つのファイルに共通の抽出部分」という表現は、以下のように理解される。これは、コンテンツが一定している、連続するデータの列を必要とし、この列は、決められた開始アドレスから始まる第１ファイルのバイナリデータをコピーすること、又は別の決められた開始アドレスから始まる第２ファイルのバイナリデータをコピーすることによって得ることができる。換言すれば、抽出部分が、ラベル付けされた開始位置から始まる各ファイルから取り出される場合に、各抽出部分の第１のバイナリデータ項目のもつコンテンツの完全な同一性があり、その後に、次のバイナリデータ項目のもつコンテンツの完全な同一性があるという具合に続いていけば、共通の抽出部分の条件が満たされることになる。通常、テキスト形式のファイルの場合、各バイトは印字可能な文字（ラテン文字、数字、句読点など）のＡＳＣＩＩ（アスキー）コードをもっている。従って、２バイトのコンテンツについての完全な同一性は、これらのバイトによりコード化された文字の完全な同一性と等価である。発見された共通の抽出部分についてはいずれも、開始アドレスのペア（１ファイル当たり１つ）及びバイト数として表現されるサイズによってラベル付けがなされる。
【００３７】
以下に、短いテキストファイルからとった、例示的な抽出部分について説明する。この選択されたテキストは、「Ｌｅ  ｌｉｅｖｒｅ  ｅｔ  ｌａ  ｔｏｒｔｕｅ」である。テキストモードでのファイルの形式における表現を、以下のアレイにて例として示す。このファイルのサイズは２２バイトである。そして、このバイナリデータ（バイト）は、テキストの各文字に関連付けられ、かつ整数モードで示されるＡＳＣＩＩコードをもっている。
【表１】
2007531948.tif 000005
【００３８】
抽出部分である「ｌｉｅｖｒｅ」がファイルで見つかる。データアレイ形式での、この表現を、次のアレイに示す。これは、６つのバイナリデータ項目を占める。ファイルにおけるその開始位置は、アドレス３である。
【表２】
2007531948.tif 000006
【００３９】
２つの短いテキストファイルに共通する抽出部分の一例を、以下に説明する。選択されたテキストは「Ｌｅ  ｌｉｅｖｒｅ」と「Ｌａ  ｔｏｒｔｕｅ」である。テキストモードのファイルの形式での表現は、以下に示すアレイの表現である。各ファイルのサイズは９バイトである。このバイナリデータ（バイト）は、整数モードで示される。
【表３】
2007531948.tif 000007
【００４０】
従って、これらのファイルには、５つの共通の抽出部分が存在する。これらは、第１ファイルの開始アドレスから昇順に提示される。
「Ｌ」：位置（０，０）及びサイズ１
「ｅ」：位置（１，８）及びサイズ１
「  」：位置（２，２）及びサイズ１（「スペース」）
「ｒ」：位置（７，５）及びサイズ１
「ｅ」：位置（８，８）及びサイズ１
【００４１】
尚、「Ｌ」と「ｌ」とを別の文字として区別しているが、これは、それらのＡＳＣＩＩコードの値が異なるためである。
【００４２】
検索結果が膨大にならないよう回避するために、発見される共通の抽出部分について最小サイズが選択基準として用いられる。抽出部分を見い出す確率が、検索する抽出部分のサイズの増加に伴って減少することは、容易に理解できる。従って、２つのファイルを相互比較する場合に、見つかる共通の抽出部分の数は、発見される共通の抽出部分についての最小サイズが増えるにつれて少なくなる。
【００４３】
同じ目的で、さらに、重複する検索結果を除外することを試みる。この処理は、賢明ではあるが、必須ではない。その完全な実施においては、実際上、検索結果のセット全体を格納することが必要となるが、これは、他の検索結果によって重複するものを、それらから除外できるようにするためである。
【００４４】
以下では、２つの短いテキストファイルに共通する抽出部分について別例を説明する。選ばれたテキストは、「Ｕｎ  ｍｏｕｔｏｎ」と「Ｄｅｓ  ｍｏｕｔｏｎｓ」である。検索される共通の抽出部分についての最小サイズは、６バイトである。そのバイナリデータ（バイト）は、整数モードで示される。
【００４５】
テキストモードにおけるファイルの形式での表現を、以下のアレイにおいて一例として示す。
【表４】
2007531948.tif 000008
【００４６】
発見された、これらのファイルに共通の抽出部分は、位置（２，３）にある、サイズ７の「  ｍｏｕｔｏｎ」である。
【００４７】
上述のように、「  」（空白文字）についてはデータ項目として扱っている。サイズ６の、２つの共通抽出部分は、検索結果から除外されるが、これは、よりサイズの大きい抽出部分「  ｍｏｕｔｏｎ」（７）と重複するためである。つまり、
「  ｍｏｕｔｏ」：位置（２，３）及びサイズ６
「ｍｏｕｔｏｎ」：位置（３，４）及びサイズ６
である。
【００４８】
これらの基本的な原則を定義し、この原則を用いた、いわゆる「従来の」検索アルゴリズムについて説明する。概して、実施される検索の方針は、開始位置のあり得る限り全てのペア、つまり、比較される２つのファイルに関して共通の抽出部分によって取り出し得るペアを調べることである。ここで説明されるアルゴリズムは、「従来の」という語によって定義されるが、この定義は、必ずしも先行技術で見い出されるということを意味するものではない。本発明の範囲内でのアルゴリズムが、デジタル署名を形成するための特別な演算を行うことは単純に理解されるが、これについては後述する。
【００４９】
開始位置のペア（１ファイル毎に１つの開始位置）の各値については、各ファイルから取り出し得る、抽出部分同士の間で比較が行われる。この比較は、共通抽出条件が達成されるか否かを示すとともに、検討される開始位置のペアについて発見される共通の抽出部分の最大サイズを決定する。適切な場合、このサイズは、発見される共通の抽出部分の最小サイズ値と最終的に比較される。
【００５０】
ファイルに関する開始位置のペア全てについては、全く同一とされる、一連のステップを用いて共通の抽出部分の存在を識別する。開始位置のペアは、以下に示す所定の順序でテストされる。
・開始位置のペア（０，０）の分析開始
・第１ファイルに関する開始位置の昇順、及び第１ファイルに関する同開始位置を有するペア全てについての、第２ファイルに関する開始位置の昇順
・その位置のペアについての分析の終了（第１ファイルの最終データ項目、第２ファイルの最終データ項目）
・ペア（ｎ，ｍ）は、第１ファイルに関する開始位置ｎ及び第２ファイルに関する開始位置ｍを、最終的にラベル付けする。
【００５１】
位置（ｎ，ｍ）で発見された、共通の抽出部分を表示するために、検索が停止された場合には、他の共通の抽出部分の検索が、次の開始位置のペアから再開される。
・一般的な場合には、（ｎ，ｍ＋１）
・位置ｍ＋１が第２ファイルの最終データ項目を行過ぎ、かつ、位置ｎ＋１が第１ファイルの最終データ項目を行過ぎない特別な場合には、（ｎ＋１，０）。
【００５２】
図１を参照すると、２つのファイルについてテストされる抽出部分の開始位置のペア（ステップ１１）が固定される。そして、各抽出部分の第１データが比較される（ステップ１２）。同一である場合、各抽出部分の次のデータが引き続き比較される（ステップ１３）。
【００５３】
そうでない場合（つまり、共通の抽出部分が見つからない場合）、比較は中断される（ステップ１４）。各抽出部分の第２データについても同じステップが繰り返され（ステップ１５、１６、１７）、ｎ番目のデータまで繰り返される（ステップ１８、１９、２０）。例えば、抽出部分のサイズが値ｎに達したら、比較が終了する（ステップ２１）。
【００５４】
以下、図２Ａに示すアレイを用いた２次元表現について説明する。
【００５５】
縦軸Ａ１には第１ファイルのデータのアドレスをとっている。また、横軸Ａ２には第２ファイルのデータのアドレスをとっている。アレイの各セル（ｍ，ｎ）は、共通の抽出部分を検索するために、評価される開始位置のペアを示している。
【００５６】
例えば、第１ファイルのサイズは６に等しく（アドレス０〜５）、第２ファイルのサイズは１０に等しい（アドレス０〜９）。アレイにおける矢印Ｆは、発見された共通の抽出部分の、あり得る開始位置のペアの全セットをテストするために用いられる移動方向を示す。
【００５７】
図２Ｂに示す例は、テキスト「Ｕｎ  ｍｏｕｔｏｎ」と「Ｄｅｓ  ｍｏｕｔｏｎｓ」との間で、最小サイズ６の共通抽出部分の検索に関するものである。縦軸Ａ１に第１ファイル（「Ｕｎ  ｍｏｕｔｏｎ」）のデータのアドレスをとっている。また、横軸Ａ２には第２ファイル（「Ｄｅｓ  ｍｏｕｔｏｎｓ」）のデータのアドレスをとっている。斜線のかかったセルは、開始位置のペア（２，３）から始まる、サイズ７（単語の前にあるスペースを含む）の発見された共通の抽出部分「  ｍｏｕｔｏｎ」を示す。
【００５８】
コンピュータプログラミングツールは、プログラムで使用できるデータアレイのサイズに制約を課すため、このアルゴリズムを用いるコンピュータプログラムは、好ましくは、サイズを低減させた、連続するデータブロックへとファイルを事前に分割する手続きを進める（この分割は、ブロック間の必要な重複を考慮に入れて行われ、これによって、検索される共通の抽出部分の開始位置のペアについて、その全セットの検査を保証することができる。）。このアルゴリズムは、次に、データブロックのペアについての、あらゆる可能な組み合わせのセット全体に適用される。データブロックのペアの比較の順序は、前述の順序と同様に、即ち、抽出部分の開始位置のペアを介したものである。但し、ここでは単に、この比較は、分離されたデータではなく、データのブロックに関する。通常、第１ファイルの第１ブロックが、第２ファイルの第１ブロックと比較され、そして、第２ファイルのこれに続くブロックと比較される。次に、第１ファイルの次のブロックが第２ファイルの第１ブロックと比較され、続いて第２ファイルのこれに続くブロックと比較されるという具合に、以下同様にして各ファイルの最終ブロックに到達するまで続く。
【００５９】
パフォーマンス（性能）の観点からすると、「フルテキスト」モード（即ち、ファイルのコンテンツ全体の分析による場合）において、検索エンジンプログラムの実行時間は、基本的に、データ間で行われる比較の回数に依存する。このパラメータは最も重要であるが、唯一という訳ではない。というのも、ディスクとランダムアクセスメモリ（ＲＡＭ）との間の転送速度、及びＲＡＭとマイクロプロセッサとの間の転送速度も考慮に入れる必要があることによる。サイズ１の共通する抽出部分の検索を実現するために、データ間で実行される比較の最小回数は、以下の積に等しい。
（第１ファイルのサイズ）×（第２ファイルのサイズ）
【００６０】
最小サイズｎの共通する抽出部分を検索する場合に、検索アルゴリズムは、分析対象のあらゆる可能な開始位置のペアから、エンド・オブ・ファイル（ファイル末端）位置を除外するように最適化される。この場合、データ間で実行される比較の最小回数は、以下の積となる。
（第１ファイルのサイズ−ｎ＋１）×（第２ファイルのサイズ−ｎ＋１）
【００６１】
サイズが大きいファイルの場合、この数値は、ファイルサイズ同士の積値に近いままである。
【００６２】
従来の検索アルゴリズムによるプログラムは、この値を用いて、既にテストされた開始位置のペアの数及び経過した検索時間の補間により、全継続時間及び検索速度を推定する。
【００６３】
本発明の範囲内における、共通の抽出部分を検索するアルゴリズムについて、次に説明する。
【００６４】
概して、検索パフォーマンスを向上させることが求められ、これは、従来のアルゴリズムに対して、データ間で行われる比較演算の回数を減らすことで行われる。ここで採用する方法は、検索を２つのパスで行うことである。ファイルに関する粗い検索、つまり、共通の抽出部分を含まないファイル部分を速やかに排除する検索と、残りのファイル部分に関する詳細検索、つまり、上記した従来のアルゴリズムに大変よく似たアルゴリズムを用いた検索である。但し、後で分かるように、ある種のファイルの場合に、第２のパスは必要ではなく、好ましくは、比較されるテキストファイルに用いられる。
【００６５】
粗い検索の場合に、本発明の範囲内でのアルゴリズムは、比較されるファイルに関する、デジタル署名の好適な計算を実施する。この「デジタル署名」については、これらの署名がファイルから生じる、当該ファイルのサイズによりも小さなサイズをもったファイル又はデータのアレイとみなすことができる。
【００６６】
デジタル署名は、ファイル、即ち、それらのデジタル署名が関連するファイルのインデックスとして用いることができるという特性を有する。さらには、数学的な関係によって、デジタル署名の任意の抽出部分を、該デジタル署名が関連するファイルの、対応する該当部分とつき合わせることができる。さらに、デジタル署名の抽出部分の開始位置は、該デジタル署名が関連するファイルの抽出部分についての、一定数の開始位置に対応してマッチする。逆に、あるサイズの抽出部分の前方で、ファイルから取り出される任意のデータ抽出部分は、デジタル署名の抽出部分に関連付けることができる。デジタル署名はまた、署名の共通の抽出部分を識別するために、互いに比較することができるという特性を有している。
【００６７】
しかしながら、デジタル署名の共通の抽出部分の定義及びデジタル署名の比較に用いられる数学演算については、ファイルに共通の抽出部分の検索に関して上述したものとは異なる。デジタル署名のインデックス（指数）特性は、署名の共通の抽出部分についての検索結果を解釈するのに用いられる。詳しくは、決定された開始位置（１つのデジタル署名に１つ）のペアについて、ファイルの２つの部分（各デジタル署名に関連するファイル毎に１つの部分）同士の間に、共通の抽出部分がないことによって、如何なる共通の抽出部分も存在しないことが数学的に得られる。逆に、２つのデジタル署名の間で発見された共通の抽出部分は、ファイルの２つの部分（各デジタル署名に関連するファイル毎に１つの部分）に対して、共通の抽出部分についてのあり得る存在によって与えられる。
【００６８】
ファイルに共通の抽出部分を検索することについては、デジタル署名の共通の抽出部分の検索における、肯定的な結果によってラベル付けされたファイル部分に関して実行される。デジタル署名の共通の抽出部分は全て、各署名の開始位置のペアによりラベル付けされており、これに応じて、各署名の開始位置は、ファイルにおける開始位置の固定した整数（Ｎ）によって区切られたファイルの部分と一致する。よって、発見されるデジタル署名の各共通の抽出部分については、検査される開始位置の（Ｎ×Ｎ）個のペアの、減少したセットに関して、ファイル間での共通の抽出部分の検索として明らかである。逆に、デジタル署名の共通の抽出部分がないことが明らかな、各開始位置のペアについては、テストされる開始位置の（Ｎ×Ｎ）個のペアのセットに関して、ファイル間での共通の抽出部分の検索を省略することとして明らかとなる。
【００６９】
デジタル署名の計算は、ファイル間で発見される共通の抽出部分についての最小サイズ値を条件付ける。各デジタル署名のデータ項目に一致する、ファイルについての抽出部分の開始位置の固定数（Ｎ）は、デジタル署名を計算するための処理における調整可能なパラメータである。
【００７０】
粗い検索アルゴリズムで発見可能な、ファイルの共通の抽出部分について最小サイズの値については、以下に詳細に説明する、数式を用いた数字に基づいて決定される。この値は、位置についての固定数Ｎの値が増加すると、増加する。以下では、この数Ｎを、「インデックス比」という用語で表すことにする。
【００７１】
デジタル署名の共通の抽出部分を検索するためのアルゴリズムが、ファイルに共通の抽出部分を検索する従来のアルゴリズムと、ある種の類似性をもつことについては、後で詳細に説明する。
【００７２】
ここでは、実施される検索の方針が、比較される２つのデジタル署名に関して、共通の抽出部分によって取り出され得る、あらゆる全ての開始位置のペアを調べるものであることを示すに止める。発見されるデジタル署名についての、共通の抽出部分の最小サイズは、後で説明する数式を用いて決定され、これは、インデックス比の値及び発見されるファイルの共通の抽出部分の最小サイズ値に基づいて決定される。
【００７３】
開始位置のペア（デジタル署名毎に１つの開始位置）の各値に対して、各デジタル署名から取り出すことができる抽出部分の間で比較が行われる。
【００７４】
従って、全体として、本発明の範囲内でのアルゴリズムは、以下の検索ステップを一緒のつないだものである。
・比較されるファイル毎のデジタル署名の計算、及びデジタル署名の共通の抽出部分の検索とともにデジタル署名の比較を用いた、ファイル間での粗い検索、並びに、
・ファイルの部分、つまり、これに対応してデジタル署名の共通の抽出部分にマッチするファイルの部分において、共通の抽出部分を検索する従来のアルゴリズムの実施を用いた、デジタル署名の発見された共通の各抽出部分に対する、ファイル間での詳細検索。
【００７５】
本発明の範囲内でのアルゴリズムの原理を、以下により詳細に説明する。図３を参照すると、データファイルＤＡＴＡは、インデックス比に等しいサイズを有する、データの連続するブロックＢＬＯに分割されている。概して、デジタル署名計算は、署名データ項目を、ファイルのデータの各ブロックに関連付ける。図３では、インデックス比が４に等しい。
【００７６】
図４Ａ及び図４Ｂには、テキストファイル「Ｕｎ  ｍｏｕｔｏｎ」と「Ｄｅｓ  ｍｏｕｔｏｎｓ」との間の、最小サイズ６の共通の抽出部分を検索する、２次元配列を示す。この例では、インデックス比が２である。第１ファイルのデジタル署名は、５つのデータを含む。また、第２ファイルのデジタル署名は６つのデータを含む。図４Ａの斜線部は、２つのファイル間における、デジタル署名ＥＣＳの共通の抽出部分を示す（例えば、参照符号４１）。通常、図４Ｂを参照すると、この参照符号４１は、ファイルについてテストされる抽出部分の開始位置の４つ（２×２）のペアについて、減少した検索ゾーンに対応する。この減少した検索ゾーンは、デジタル署名の共通の抽出部分についての、開始位置のペア（１，１）に関連付けられる。
【００７７】
計算の工程及びデジタル署名の比較演算を、以下に詳細に説明する。
【００７８】
デジタル署名のデータの計算には、ファジー論理の数学理論を用いる。
【００７９】
通例、２値論理では、データビットを用いて２つの論理状態をコード化する。つまり、コード０は、状態「偽」に関連付けられ、コード１は、状態「真」に関連付けられる。
【００８０】
２値論理では、図５Ａ及び図５Ｂの真理値表に表されるように、２値状態の比較に論理演算のセットを用いる。
【００８１】
８ビットデータ項目（１バイト）は、８つの独立した２値状態を格納できる。
【００８２】
２値論理に比べて、ファジー論理では、不定状態「？」（全く同時に真であり偽でもある）と、禁止状態「Ｘ」（真でも偽でもない）という２つの追加の状態を用いる。
【００８３】
図５Ｃに示すように、４つのファジー論理状態が２ビットでコード化されており、同図では、参照符号ＢＯ及びＢ１が２ビットでの状態のコーディングを表し（横軸）、他方、縦軸は、各種のファジー論理状態「０」、「１」、「？」、及び「Ｘ」を表す。
【００８４】
８ビットデータ項目（１バイト）は、従って４つの独立したファジー状態を格納可能である。
【００８５】
ファジー論理では、ファジー状態間の比較のための一セットの論理演算、つまり、図５Ｄ及び図５Ｅに表されるような演算を用い、図５Ｄがファジー論理「ＯＲ」を示し、図５Ｅがファジー論理「ＡＮＤ」を示している。これらの演算結果は、２値ＯＲ又はＡＮＤの比較を、ファジー状態の２値要素の各コーディングビットに対して適用するだけで得ることができる。
【００８６】
本発明との関係において、デジタル署名の計算では、ＯＲ演算を使って、署名に関連付けられたファイルの、連続するデータのブロックに共通するファジー状態を決定する。はじめに、２値状態（０又は１）が、ファイルのデータのブロックにおいて、データ項目の各アドレスと関連付けられる。データブロックのサイズは、上述のようにインデックス比に等しい。その後、この２値状態は相互比較されて、デジタル署名のデータ項目についてのファジー状態、つまり「０」、「１」、又は「？」が決定される。デジタル署名のデータ項目は、その後、ファイルのデータブロックと関連付けられる。
【００８７】
その後、デジタル署名の比較は、厳密に言うと、ＡＮＤ演算を用いて、ファイルに共通の抽出部分を有することが可能か否かを決定する。従って、この決定は、デジタル署名のデータのペアに適用されたＡＮＤ演算の結果によって得られる、ファジー論理状態の関数として行われる。
【００８８】
禁止状態Ｘは、デジタル署名の共通する抽出部分についての、開始位置での現在のペア（デジタル署名のデータ項目毎に１ブロック）と関連付けられたデータゾーンにおいて、ファイル間に共通の抽出部分がないことを意味する。この場合については後で詳細に説明する。状態「０」、「１」、又は「？」は、逆に、デジタル署名の共通する抽出部分についての、開始位置での現在のペアと関連付けられたデータゾーンにおいて、ファイル間に共通の抽出部分が存在する可能性があることを意味する。
【００８９】
図６Ａ及び図６Ｂを参照すると、デジタル署名は２つのステップで計算される。
・２値状態をファイルの各データアドレスと関連付けることにより、２値署名を計算するステップ。用いる計算法則は、固定サイズのファイル抽出部分と各２値状態との後方関連付けを可能とする。
・インデックス比と等しいサイズをもったブロックに関する、２値署名の状態同士を相互比較することにより、ファジー署名を計算するステップ。Ｎ個の連続する２値状態の各ブロックが、１つのファジー状態を決定する。
【００９０】
図６Ａ及び図６Ｂの例では、インデックス比Ｎが２に等しい。図６Ａにおいて、参照記号「Ａｄｄ」は、ファイル「ＦＩＣ」のデータの各アドレスを示し、参照記号「Ｖａｌｂ」は、これらのデータの各アドレスと関連付けられた２値状態を示す。また、図６Ｂにおいて、同じ参照記号「Ｖａｌｂ」は、データの同じアドレスとそれぞれ関連付けられた２値状態を示し、参照記号「Ｖａｌｆ」は、ファイル「ＦＩＣ」から導かれたデジタル署名「ＳＮ」のデータと関連付けられた、ファジー論理状態を示す。１つのファジー論理状態は、Ｎ個のアドレスのブロック毎にカウントされ、Ｎはインデックス比（ここではＮ＝２）である。図６Ｂのファジー論理状態「Ｖａｌｂ」についての、連続した「？」、「０」、「？」、．．．は、通常、以下のように解釈される。
・ファイルの最初の２つのアドレスの２値状態「０」と「１」は異なるため、これらの状態に適用されるファジー論理ＯＲ演算は「？」を与える。
・ファイルの３番目と４番目のアドレスの２値状態「０」と「０」は、「０」に等しいため、これらの状態に適用されるファジー論理ＯＲ演算は「０」を与える。
・ファイルの５番目と６番目のアドレスの２値状態「１」と「０」は異なるため、これらの状態に適用されるファジー論理ＯＲ演算は「？」を与える、など。
【００９１】
選択されたテキスト「Ｌａ  ｔｏｒｔｕｅ」について、デジタル署名の計算例を以下に説明する。各テキストの文字は、ＡＳＣＩＩコードを用いてバイトでコード化されている。各ＡＳＣＩＩコードは、バイトの８ビットでコード化された整数値で表現される。この数は０と２５５との間にある。この２値状態は、各データアドレスと関連付けられており、例えば、以下のタイプの規則で決定される。
・文字のＡＳＣＩＩコードの整数値が厳密に１１１未満である場合には、状態０。
・文字のＡＳＣＩＩコードの整数値が１１１以上である場合は、状態１。
【００９２】
図７Ａの配列表は、テキストファイル「Ｌａ  ｔｏｒｔｕｅ」の場合に、インデックス比の値２から４までの、デジタル署名のファジー状態の計算について得られた結果を示す。
【００９３】
次に、図７Ｂは、２つのテキストファイル「Ｌｅ  ｌｉｅｖｒｅ」及び「Ｌａ  ｔｏｒｔｕｅ」に関して、インデックス比の値が２の場合に、デジタル署名のファジー状態の計算について得られた結果を示す。データ項目のアドレスは、抽出部分の開始位置のアドレスである。２値状態を決定するための規則は、既に説明した規則である（ＡＳＣＩＩ値を１１１と比較すること）。
【００９４】
図７Ｃには、インデックス比が２の場合において、テキストファイル「Ｌｅ  ｌｉｅｖｒｅ」と「Ｌａ  ｔｏｒｔｕｅ」との間で、共通の抽出部分を検索する際の２次元配列を示す。各データアドレスと関連付けられた２値状態を決定する規則は、上述の規則と同じである（１１１と比較されるＡＳＣＩＩ値）。イニシャルＡＤ１及びＡＤ２は、ファイル「Ｌｅ  ｌｉｅｖｒｅ」とファイル「Ｌａ  ｔｏｒｔｕｅ」から導かれた、各ブロックのアドレスを参照し、イニシャルＳＮ１及びＳＮ２は、これらの各ブロックの連続するファジー論理状態を参照する。斜線のかかっていないセルは、デジタル署名データに関連付けられたファイル位置同士の間に、サイズ１の共通の抽出部分がない位置を示している。また、斜線のかかったセルは、逆に、デジタル署名データに関連付けられたファイル位置同士の間に、最小サイズ１の共通の抽出部分が存在し得る状況を示している。
【００９５】
以下に、好適な実施形態において、デジタル署名の計算に用いられる数学的な規則を説明する。以下の説明は、本発明の範囲内での検索アルゴリズムの２値署名を計算する、前述した第１のステップを補完するものであり、ファイルの各データアドレスに関連付けられた２値状態を決定するために用いられる数学的規則を記載したものである。上記の例において、デジタル署名の各２値状態は、ファイルの各バイトのコードの整数値と整数の基準値とを比較することに基づく簡単な規則によって決定される。しかしながら、この規則の利点は限られており、その理由は、各々の２値署名のデータ項目が、一度にファイルの１つのデータ項目しか明らかにしないからである。ファジー署名のデータ（計算の第２ステップにおいて得られる）間の比較結果の解釈は、従って、サイズ１のファイルに共通する抽出部分のあり得る存在に限定される。サイズが１よりも大きい、ファイルに共通の抽出部分のあり得る存在又は不存在については、ファジー署名のデータ間における１回の比較演算では検出することができない。このような状況を改善するために、２値署名の状態を決定する数学的規則は、２値署名の各データ項目が、ファイルの好ましくは固定されたサイズの抽出部分を明らかにするように選択される。データ抽出部分のサイズは、２値署名の状態を決定するための数学的規則のパラメータである。このパラメータの値は、常にインデックス比の値以上である。この条件に基づいて、ファジー署名データのペア間の比較の結果は、ファジー署名データのペアと関連付けられたファイルの、共通の抽出部分の開始位置のペアの（Ｎ×Ｎ）個のセットのうち、インデックス比（Ｎ）以上のサイズをもった、ファイルの共通の抽出部分の不存在又はあり得る存在のいずれかによって解釈することができる。
【００９６】
同様にして、デジタル署名の間に発見される、サイズＫの共通の抽出部分は、デジタル署名の発見された共通の抽出部分の開始位置のペアと関連付けられた、ファイルの共通の抽出部分の開始位置のペアの（Ｎ×Ｎ）個のセットのうち、少なくともＮ×Ｋに等しいサイズをもった、ファイルの共通の抽出部分のあり得る存在によって解釈される。
【００９７】
また、ファジー状態「？」の割合が、インデックス比のサイズが増えるにつれて増加することも分かる。従って、デジタル署名間で共通の抽出部分を検索するステップについては、インデックス比が増加した場合に、選択性がさらに低下することになる。具体的には、デジタル署名のデータが全て「？」状態に等しい場合に、この署名と別の署名との比較は、署名に関連付けられたファイルに関して、検索される抽出部分の開始位置のペアのいずれをも除外しない。このような状況を改善するために、２値状態を決定する規則については、（２値状態のブロックを比較することにより）ファジー状態を計算するステップが生成する「？」状態の割合が低く、逆に「０」又は「１」状態の割合が高くなるように選択することを要する。
【００９８】
以下では、デジタル署名の選択性を向上させるための処理を説明する。尚、以下の説明では、変換の代数及びデジタル信号処理の分野からの数学的理論の結果を用いる。
【００９９】
フーリエ変換は、以下の数式による、変数ｔの関数ｆ（ｔ）を、変数ｆの別の関数Ｆ（ｆ）に対応させる数学的変換であることを想起されたい。
【数３】
2007531948.tif 000009
【０１００】
フーリエ変換の特性は相互的であり、以下の数式により、Ｆ（ｆ）から逆に関数ｆ（ｔ）を得ることができる。
【数４】
2007531948.tif 000010
【０１０１】
この数式は、任意の実関数ｆ（ｔ）を周波数ｆ、振幅２・｜Ｆ（ｆ）｜、位相φ（ｆ）の余弦関数の無限和に分解できることを示す。
【数５】
2007531948.tif 000011
【０１０２】
位相φの各種の値について、関数ｃｏｓ（２πｆｔ＋φ）の変化を図８Ａに示す。この関数は周期的であり、その周期Ｔは１／ｆに等しい。サイズＴ／２の期間で正であり、補完的なサイズＴ／２の期間では負である。
【０１０３】
後者の特性は、２値署名を決定する規則の選択に利用することができる。ファジー状態を決定するための、２変数を有するＳｔａｔｅｓ（ｔ，ｐ）の規則は、関数ｓ（ｔ）＝ｃｏｓ（２πｆｔ＋φ）に関連付けられる。尚、Ｔ＝１／ｆとする。
【０１０４】
規則Ｓｔａｔｅｓ（ｔ，ｐ）については、任意の実数値ｔ及び（上記インデックス比と比較される）任意の正の実数値パラメータｐについて定義される。
∀ｘ∈［ｔ，ｔ＋ｐ］，ｓ（ｘ）＞０ならば、Ｓｔａｔｅｓ（ｔ，ｐ）＝１
∀ｘ∈［ｔ，ｔ＋ｐ］，ｓ（ｘ）＜０ならば、Ｓｔａｔｅｓ（ｔ，ｐ）＝０
それ以外の場合、Ｓｔａｔｅｓ（ｔ，ｐ）＝？
【０１０５】
図８Ｂには、ｐが約０．６Ｔである余弦関数を示す。任意の期間［ｔ，ｔ＋ｐ］に対して、関数ｓ（ｔ）は正負両方の値をとり、よって、「Ｓｔａｔｅｓ（ｔ，ｐ）＝？」となる。このように、パラメータｐがＴ／２よりも大きい場合、任意のｔに対して「Ｓｔａｔｅｓ（ｔ，ｐ）＝？」である。
【０１０６】
図８Ｃには、０とＴ／２との間にある固定値ｐ（図示の例では、ｐ＝０．３Ｔ）について、規則Ｓｔａｔｅｓ（ｔ，ｐ）のファジー状態を示す。ファジー状態となる確率は、周期Ｔ（Ｔ＝１／ｆ）に等しいサイズの期間に亘って記録をとり、あり得るファジー状態（０，１又は？）のそれぞれを生じさせる、変数ｔの期間のサイズを合計し、この合計されたサイズをＴで割ることによって得られる。
【０１０７】
以下では、次の表記を用いる。
状態１を引き出す確率：Ｐ１（ｆ，ｐ）
状態０を引き出す確率：Ｐ０（ｆ，ｐ）
状態？を引き出す確率：Ｐ？（ｆ，ｐ）
【０１０８】
規則Ｓｔａｔｅｓ（ｔ，ｐ）について、以下の結果が得られる。
ｐ∈［０，Ｔ／２］の場合
Ｐ１（ｆ，ｐ）＝Ｐ０（ｆ，ｐ）＝（Ｔ／２−ｐ）／Ｔ＝１／２−ｐ／Ｔ＝１／２−ｐｆ
Ｐ？（ｆ，ｐ）＝１−Ｐ１（ｆ，ｐ）−Ｐ０（ｆ，ｐ）＝２ｐｆ
ｐがＴ／２より大きい場合
Ｐ１（ｆ，ｐ）＝Ｐ０（ｆ，ｐ）＝０
Ｐ？（ｆ，ｐ）＝１
【０１０９】
ファジー状態を引き出す確率は、ファジー状態を決定する規則Ｓｔａｔｅｓ（ｔ，ｐ）を、関数ｓ（ｔ）＝ｃｏｓ（２πｆｔ＋φ）に適用した後で得られることを、もう一度想起されたい。また、ファジー状態を引き出す確率は、関数ｓ（ｔ）＝ｃｏｓ（２πｆｔ＋φ）の位相φに依存しないことが分かる。
【０１１０】
図９Ａ、図９Ｂ、図９Ｃを参照すると、周波数の関数としての確率Ｐ１（ｆ，ｐ）、Ｐ０（ｆ，ｐ）、及びＰ？（ｆ，ｐ）の変化を示すグラフからは、状態１及び状態０を引き出す確率については、周波数ｆが減少すると大きくなり、逆に、状態「？」を引き出す確率については、周波数ｆが増加すると大きくなることが分かる。
【０１１１】
次に、この所見を、本発明の範囲内でのバイナリデータの比較に適用する。
【０１１２】
変数ｔの関数ｆ（ｔ）のサンプリングは、この関数から、固定期間Ｔｅだけ区間をおいた時点Ｔｎにて得られる値を記録することにある。
【０１１３】
以下、次の表記を用いる。
ｎ  サンプル数（−∞から＋∞の間にある整数）
Ｔｎ  サンプルｎの時点：      Ｔｎ＝ｎ・Ｔｅ
ｆｎ  サンプルｎの値： ｆｎ＝ｆ（Ｔｎ）
【０１１４】
信号処理の理論において、シャノンの定理は、ｆ（ｔ）に関連付けられたフーリエ変換Ｆ（ｆ）の周波数スペクトルが、Ｆｅ＝１／Ｔｅとされた、区間［−Ｆｅ／２，Ｆｅ／２］で厳密に有界であるならば、元の関数ｆ（ｔ）が、サンプルｆｎから逆に得られることを示すものである。
【０１１５】
この条件下で、関数ｆ（ｔ）は、周波数帯域［−Ｆｅ／２，Ｆｅ／２］における理想的なローパスフィルタリングを、サンプルされた信号Ｆ（ｆ）のフーリエ変換に適用した後に得られる。
【０１１６】
以下では、データファイルが、上記の条件を満たす関数ｆ（ｔ）のサンプルｆｎを示すものとみなされる。特に、各データアドレスは、サンプル数ｎに相当する。また、各データ項目は、サンプルの値を格納する（通常、１バイトのビットでコード化された整数）。
【０１１７】
データファイルのサンプルｆｎと関連付けられた信号のフーリエ変換は、以下のとおりである。
【数６】
2007531948.tif 000012
【０１１８】
尚、サンプリング周期Ｔｅの選択が自由であることに留意されたい。
【０１１９】
フーリエ変換はまた、この場合に、以下の簡単化された数式で表現される。
【数７】
2007531948.tif 000013
尚、ここで、Ｎ＋ｌは、データファイルのサイズである。
【０１２０】
サンプルｆｎに関連付けられた、元の関数ｆ（ｔ）のフーリエ変換Ｆ（ｆ）は、シャノンの定理を適用することにより得られる。
ｆ∈［−Ｆｅ／２，Ｆｅ／２］に対して、
∧
Ｆ（ｆ）＝Ｆ（ｆ）／Ｆｅ
その他の値ｆに対して、
Ｆ（ｆ）＝０
【０１２１】
サンプルｆｎに関連付けられた関数ｆ（ｔ）は、逆フーリエ変換を適用することにより得られる。
【数８】
2007531948.tif 000014
最終的には、以下の項の有限和の形で表される。
ｆ（ｘ）＝ｓｉｎ（ｘ）／ｘ  、  ｘ＝πＦｅ（ｔ−ｎＴｅ）
即ち、以下のようになる。
【数９】
2007531948.tif 000015
【０１２２】
図１０には、比ｔ／Ｔの関数として、テキストファイル「Ｌｅ  ｌｉｅｖｒｅ」のデータと関連付けられた関数ｆ（ｔ）の例示的表現を示す。
【０１２３】
関数ｆ（ｔ）とサンプルｆｎ＝ｆ（ｎＴｅ）のセット（組）との間の上記関係は、シャノンの条件を満たす、任意の関数についても当てはまることが示される。
【０１２４】
従って、これらの関係は、以下の条件が維持される場合に、関数ｓ（ｔ）＝ｃｏｓ（２πｆｔ＋φ）にも当てはまる。
ｆ∈［−Ｆｅ／２，Ｆｅ／２］
【０１２５】
そして、ｓ（ｔ）については、Ｔｎ＝ｎＴｅの時点でのｓ（ｔ）を引き継いだ、サンプルｓｎの無限のセットによって表現することができる。
【０１２６】
規則Ｓｔａｔｅｓ（ｔ，ｐ）が、任意の実数値ｔ及び任意の正の実数値ｐについて以下のように定義されたことを想起されたい。
∀ｘ∈［ｔ，ｔ＋ｐ］，ｓ（ｘ）＞０ならば、Ｓｔａｔｅｓ（ｔ，ｐ）＝１
∀ｘ∈［ｔ，ｔ＋ｐ］，ｓ（ｘ）＜０ならば、Ｓｔａｔｅｓ（ｔ，ｐ）＝０
それ以外の場合、Ｓｔａｔｅｓ（ｔ，ｐ）＝？
【０１２７】
この規則の性質については、ファジー状態を決定するための、以下のような規則を対象とする場合において、ｋ個の連続するサンプル｛ｓｎ，ｓｎ＋１，．．．，ｓｎ＋ｋ＋１｝の列に亘って定義されるサンプルｓｎの範囲へと、簡単に置き換えることができる。
∀ｉ∈｛０，ｋ−１｝，ｓｎ＋ｉ＞０ならば、Ｓｔａｔｅｓ（ｎ，ｋ）＝１
∀ｉ∈｛０，ｋ−１｝，ｓｎ＋ｉ＜０ならば、Ｓｔａｔｅｓ（ｎ，ｋ）＝０
それ以外の場合、Ｓｔａｔｅｓ（ｎ，ｋ）＝？
【０１２８】
規則Ｓｔａｔｅｓ（ｎ，ｋ）に関連付けられるファジー状態を引き出す確率は、ｐを（ｋ−１）Ｔｅに置き換えることによって、規則Ｓｔａｔｅｓ（ｔ，ｐ）に基づいて、簡単に得られる。
【０１２９】
こうして、サンプルｓｎに関連付けられる関数ｓ（ｔ）の周波数の関数として、規則Ｓｔａｔｅｓ（ｎ，ｋ）についての、状態１又は状態０を引き出す確率を表すグラフが得られる。
【０１３０】
図１１の例において、ｋは３に固定されている。ｓ（ｎＴｅ）、ｓ（（ｎ＋ｌ）Ｔｅ）、ｓ（（ｎ＋２）Ｔｅ）が０よりも大きい、ｓ（ｔ）について、３つの連続するサンプルを引き出す確率は、Ｐ１（ｆ，３）で与えられ、これは、ｆが、ｐ＝（３−１）Ｔｅ＝２／Ｆｅにおいて、１／２ｐより大きい場合、即ちｆ＞Ｆｅ／４の場合にゼロとなる。
【０１３１】
ファジー状態を決定する規則の定義は、シャノンの条件を満たす任意の関数ｆ（ｔ）の場合に拡張される。一般的に、規則Ｓｔａｔｅｆ（ｔ，ｐ）は、任意の実数値ｔ及び任意の正の実数値ｐについて定義される。
∀ｘ∈［ｔ，ｔ＋ｐ］，ｆ（ｘ）＞０ならば、Ｓｔａｔｅｆ（ｔ，ｐ）＝１
∀ｘ∈［ｔ，ｔ＋ｐ］，ｆ（ｘ）＜０ならば、Ｓｔａｔｅｆ（ｔ，ｐ）＝０
それ以外の場合、Ｓｔａｔｅｆ（ｔ，ｐ）＝？
【０１３２】
ファジー状態を決定する本規則はまた、ｋ個の連続するサンプル｛ｆｎ，ｆｎ＋１，．．．，ｆｎ＋ｋ−１｝の列に亘るサンプルｆｎの範囲に置き換えられる。
∀ｉ∈｛０，ｋ−１｝，ｆｎ＋ｉ＞０ならば、Ｓｔａｔｅｆ（ｎ，ｋ）＝１
∀ｉ∈｛０，ｋ−１｝，ｆｎ＋ｉ＜０ならば、Ｓｔａｔｅｆ（ｎ，ｋ）＝０
それ以外の場合、Ｓｔａｔｅｆ（ｎ，ｋ）＝？
【０１３３】
既に取り扱ったような、ｆ（ｔ）が周波数ｆの純粋な正弦波である特別な場合とは対照的に、フーリエ変換Ｆ（ｆ）に基づいてファジー状態を引き出す確率について計算することをここで可能にする単純な数学的関係は存在しない。
【０１３４】
一方、規則Ｓｔａｔｅｓ（ｎ，ｋ）及びＳｔａｔｅｓ（ｔ，ｐ）と関連付けられるファジー状態を引き出す確率の特性を利用して、任意の関数ｆ（ｔ）へのローパスフィルタリングの適用は、状態０及び１を引き出す確率の増加を齎し、そして、状態？を引き出す確率の減少を齎すと推定することができる。これらの状態は規則Ｓｔａｔｅｆ（ｎ，ｋ）及びＳｔａｔｅｆ（ｔ，ｐ）と関連付けられる。
【０１３５】
規則Ｓｔａｔｅｆ（ｎ，ｋ）の場合、関数ｆ（ｔ）が周波数ｆの純粋な正弦関数であれば、ｆ＞Ｆｅ／２（ｋ−ｌ）及びｋ＞１にて以下が得られる。
Ｐ１（ｆ，ｋ）＝Ｐ０（ｆ，ｋ）＝０
Ｐ？（ｆ，ｋ）＝１
【０１３６】
周波数帯域［−Ｆｅ／２（ｋ−１），Ｆｅ／２（ｋ−ｌ）］における、理想的なローパスフィルタリングを関数ｆ（ｔ）に適用するならば、状態１及び０を引き出す確率が高くなることが分かるが、その理由は、結果の信号ｒｋ（ｔ）の各周波数成分Ｒｋ（ｆ）が、状態１又は０を引き出す個々のゼロでない確率をもった最終的な結果に寄与するからである。
【０１３７】
この主張は、周波数帯域［−Ｆｅ／２，Ｆｅ／２］において、スペクトルＢ（ｆ）の振幅が一定とされる、ランダムノイズ関数ｂ（ｔ）の場合に示すことができる。ランダムノイズ関数ｂ（ｔ）の場合、既知のように、サンプルを引き出す確率は以下のようになる。
Ｐ１ｂ（ｋ＝１）＝Ｐ０ｂ（ｋ＝１）＝１／２
Ｐ？ｂ（ｋ＝１）＝０
【０１３８】
２つの連続するサンプルの場合には、以下が得られる。
Ｐ１ｂ（ｋ＝２）＝Ｐ０ｂ（ｋ＝２）＝（１／２）２
Ｐ？ｂ（ｋ＝２）＝１−Ｐ１ｂ−Ｐ０ｂ＝１−２×（１／２）２
【０１３９】
そして、ｎ個の連続するサンプルの場合、以下が得られる。
Ｐ１ｂ（ｋ＝ｎ）＝Ｐ０ｂ（ｋ＝ｎ）＝（１／２）ｎ
Ｐ？ｂ（ｋ＝ｎ）＝１−Ｐ１ｂ−Ｐ０ｂ＝１−２・（１／２）ｎ
【０１４０】
このように、多数の連続するサンプルの場合に、状態「０」及び「１」を引き出す確率は０に近づき、また、不定状態「？」を引き出す確率は１に近づく。次に、関数ｒｎ（ｔ）を検討するが、該関数は、周波数帯域［−Ｆｅ／２（ｎ−１），Ｆｅ／２（ｎ−ｌ）］において、理想的なローパスフィルタリングを関数ｂ（ｔ）に適用することによって得られる。そして、Ｒｎ（ｆ）、Ｐ１（ｆ，ｎ）、Ｐ０（ｆ，ｎ）、Ｐ？（ｆ，ｎ）の各スペクトルの表現が、図１２Ａ及び図１２Ｂに示すように、Ｒ２（ｆ）、Ｐ１（ｆ，２）、Ｐ０（ｆ，２）、Ｐ？（ｆ，２）の各スペクトルとの、単純な相似（ｈｏｍｏｔｈｅｔｙ）によって得られることが見て取れる。また、図１２Ａには、関数ｂ（ｔ）に関連付けられたスペクトルＢ（ｆ）の振幅を示す。図１２Ｂにはまた、ｒｎ（ｔ）に関連付けられたスペクトルＲｎ（ｆ）の振幅を示す。
【０１４１】
以上のことから、フィルタ処理されたノイズ信号ｒｎ（ｔ）についての、ｎ個の連続したサンプルを引き出す確率と、フィルタ処理されていないノイズ信号ｂ（ｔ）についての、２つの連続したサンプルを引き出す確率との間に等価性があることが推論される。フィルタ処理されたノイズ信号ｒｎ（ｔ）のｎ個の連続したサンプルに対して、状態１又は状態０を引き出す確率は１／４に等しく、他方、フィルタ処理されたノイズ信号ｒｎ（ｔ）のｎ個の連続したサンプルに対して、状態「？」を引き出す確率は１／２に等しい。
【０１４２】
結論として、ローパスフィルタリングを、サンプルｆｎ＝ｆ（ｎＴｅ）に関連付けられた関数ｆ（ｔ）に適用することにより、デジタル署名の選択性が向上する。
【０１４３】
処理ステップ並びにファイルのデータ及びサンプル及び関数の関係は、図１３に示すようにまとめることができる。ステップ１３１において、処理されるファイルのデータｄｎが取得され、ステップ１３２でサンプリングがなされて、サンプルｆｎ、つまり、データｄｎによりコード化された整数であるサンプルが得られる。シャノンの定理に従って（ステップ１３２’）、これらのサンプルは、有界のスペクトルＦ（ｆ）の関数ｆ（ｔ）に関連付けられる。
【数１０】
2007531948.tif 000016
【０１４４】
この関数Ｆ（ｆ）に対して、ローパスフィルタを適用することにより（ステップ１３５’）、関数ｒ（ｔ）のフーリエ変換に対応する関数Ｒ（ｆ）が得られ（ステップ１３３’）、そのサンプルｒｎは、シャノンの定理によって、ｒｎ＝ｒ（ｎ・Ｔｅ）＝ｒ（ｎ／Ｆｅ）である（ステップ１３３）。
【０１４５】
実際には、ステップ１３５において、ローパスデジタルフィルタが、好ましくはサンプルｆｎに対して直接適用され、ステップ１３３でサンプルｒｎを得る。このデジタルフィルタについては、後で詳述する。最後に、フィルタ処理されたサンプルｒｎにファジー状態を決定する規則が適用され、ｋ個の連続するサンプル｛ｒｎ、ｒｎ＋１、．．．、ｒｎ＋ｋ−１｝に亘って、デジタル署名データ「ｓｎ／ｋ＝Ｓｔａｔｅｒ（ｎ，ｋ）」が得られる（ステップ１３４）。尚、ここでｎはｋの倍数である。
【０１４６】
上述のように、いずれにしても図１３の各ステップは、デジタルフィルタを用いて、サンプルｆｎに直接基づいてサンプルｒｎの計算を行うことにより簡略化できる。
【０１４７】
以下では、次の表記を採用する。
Ｆｉｌｔｅｒ（ｆ）：フィルタリング演算子のフーリエ変換
ｆｉｌｔｅｒ（ｔ）：逆フーリエ変換を適用することによりＦｉｌｔｅｒ（ｆ）に関連付けられた関数
ボレルの定理は、以下の関係を与える。
Ｒ（ｆ）＝Ｆｉｌｔｅｒ（ｆ）×Ｆ（ｆ）
【０１４８】
この関係は、以下の形の数式によって、関数ｒ（ｔ）、ｆｉｌｔｅｒ（ｔ）、ｆ（ｔ）に関して与えられる。
【数１１】
2007531948.tif 000017
【０１４９】
サンプルに関連付けられた（及びシャノンの条件を満たす）関数について考慮すると、この関係は以下のようになる。
【数１２】
2007531948.tif 000018
【０１５０】
従って、デジタルフィルタリングは、係数ｆｉｌｔｅｒｋのセットを定義することにあり、これらの係数を用いて上記の数式を適用することにより、各サンプルｒｎが計算されることになる。
【０１５１】
実際には、係数ｆｉｌｔｅｒｋのセットのサイズを制限することにより、予め決められたフィルタのテンプレートの近似が試みられる。見い出される妥協点は、以下の要因に依存する。
・デジタルフィルタの係数の個数が増加すると、生成されるフィルタの精度が高まる。
・逆に、サンプルｒｎの計算速度は、係数の個数が増加すると遅くなる。
【０１５２】
係数の個数がＫに等しい場合、サンプルｒｎの各計算は、Ｋ回の乗算と、（Ｋ−１）回の加算によって与えられる。
【０１５３】
本発明の範囲内での検索アルゴリズムで用いるデジタルフィルタに対して、採用される主たる基準は、サンプルｒｎの計算速度である。
【０１５４】
好適な実施形態において、その選択は、「平均値」フィルタと呼ばれる特定のフィルタ群に関連し、該フィルタについては、デジタルフィルタの係数が同一であって、以下のようになる。
整数ｋ∈［−Ｋ，Ｋ］に対して、ｆｉｌｔｅｒｋ＝Ｃｓｔ
その他のｋ値に対して、ｆｉｌｔｅｒｋ＝０
【０１５５】
デジタルフィルタの等式は、以下の形に簡単化される。
【数１３】
2007531948.tif 000019
【０１５６】
従って、「２Ｋ＋１」個の係数をもったフィルタに対して、サンプルｒｎの計算は、ほんの「２Ｋ＋１」回の加算演算と、そして、Ｃｓｔ項の値が１でない場合における、１回の乗算によって与えられる。
【０１５７】
さらに、サンプルｒ（ｎ＋１）が、関係「ｒ（ｎ＋１）＝ｒｎ＋Ｃｓｔ（ｆ（ｎ＋Ｋ＋１）−ｆ（ｎ−Ｋ））」によって、単にｒｎから得られることも分かる。
【０１５８】
特に有利な方法においては、この後者の関係を用いることにより、新たな各サンプルｒ（ｎ＋１）の計算が、２回の加算だけで与えられる。
【０１５９】
平均値デジタルフィルタの周波数応答は、以下の総和演算子σ（ｔ）のフーリエ変換から得られる。
ｔ∈［−Ｔ／２，Ｔ／２］に対して、σ（ｔ）＝１
それ以外の場合、σ（ｔ）＝０
【０１６０】
そして、演算子σ（ｔ）によるｆ（ｔ）のフィルタリングについては、以下の数式で与えられる。
【数１４】
2007531948.tif 000020
【０１６１】
演算子σ（ｔ）の周波数応答は、以下のΣ（ｆ）である。
【数１５】
2007531948.tif 000021
【０１６２】
最終的に、以下が得られる。
【数１６】
2007531948.tif 000022
【０１６３】
平均値フィルタの周波数応答は、総和演算子Σ（ｆ）をさらにＴで割ることで得られる。
【数１７】
2007531948.tif 000023
【０１６４】
Ｋ個の連続するサンプルに亘る平均値デジタルフィルタの周波数応答は、その後、Ｔを（Ｋ−１）Ｔｅに置き換えることで得られる。即ち、以下のとおりである。
【数１８】
2007531948.tif 000024
【０１６５】
Ｋのパリティ（偶奇性）に応じて、デジタルフィルタについての、２つの等式がサンプルｒｎの計算に用いられる。
【数１９】
2007531948.tif 000025
【０１６６】
図１４には、Ｋ値のいくつかについて、ｆ／Ｆｅの関数としての、Ｆｉｌｔｅｒ（Ｋ，ｆ）＝Σａｖｇ（Ｋ，ｆ）のプロットを例示している。ゼロにおける、フィルタの最初のカットオフは、ｆ＝Ｆｅ／（Ｋ−１）の場合に生ずる。
【０１６７】
さらに、周波数帯域［−Ｆｅ／２（ｎ−１），Ｆｅ／２（ｎ−１）］における、理想的なローパスフィルタリングの適用が、ｎ個の連続するサンプルの列に亘って計算されるファジー状態を引き出す、以下の確率で与えられることも分かる。
Ｐ１＝Ｐ０＝１／４
Ｐ？＝１／２
【０１６８】
理想的なローパスフィルタリングのテンプレートについては、ゼロカットオフ（遮断）周波数が「ｆ＝Ｆｅ／２（ｎ−１）」で生じる平均値デジタルフィルタを選択することにより、近似することができる。この条件は、Ｋ＝２ｎ−１の場合に得られる。
【０１６９】
実際、平均値デジタルフィルタの適用が、理想的なローパスフィルタによって得られる確率とは異なるファジー状態を引き出す確率で齎されることは勿論である。Ｋ値の決定は経験的に行われるが、これは、「Ｋ＝２ｎ−１」で得られる確率が、理想的なフィルタの確率に近くなること、そして、Ｐ１及びＰ０を引き出す確率もまた、Ｋ値とともに増加することが分かっているからである。
【０１７０】
以下に、ファジー状態を決定する規則、特に前述の関数としての規則に行われる適合について説明する。
【０１７１】
ファジー状態を引き出す確率の計算は、ファイルのデータがゼロ平均値の信号ｆ（ｔ）のサンプル値を示すという仮定に基づいている。この条件はまた、以下の関係で与えられる。
【数２０】
2007531948.tif 000026
【０１７２】
従って、ファジー状態を引き出す確率について得られる結果は、この条件がサンプルｆｎに対して以下のように満たされる場合にのみ有効である。
【数２１】
2007531948.tif 000027
【０１７３】
サイズＮのサンプルのファイルの場合に、この条件は以下のようになる。
【数２２】
2007531948.tif 000028
【０１７４】
次に、ゼロ平均値についての上記条件は、サンプルの値がファイルのバイナリデータから決定される場合において、体系的に満たされない。例えば、これらの条件は、「符号なし整数」のコーディング規則を用いて、ファイルのデータと関連付けられたサンプル値を表す場合に満たされない。詳しくは、この場合、各バイトが０と２５５との間の整数を表し、ランダムなコンテンツのファイルの場合、平均サンプル値が１２７．５となる。
この問題を軽減するために、以下のように、基準値パラメータＶｒｅｆが導入され、これは、サンプルｆｎに基づくデジタルフィルタリングによって得られる、ｋ個の連続するサンプルｒｎ｛ｒｎ、ｒｎ＋１、．．．、ｒｎ＋ｋ−１｝の列に亘ってファジー状態を決定する規則に対して持ち込まれる。
∀ｉ∈｛０，ｋ−１｝，ｒｎ＋ｉ＞＝Ｖｒｅｆならば、Ｓｔａｔｅｒ（ｎ，ｋ）＝１
∀ｉ∈｛０，ｋ−１｝，ｒｎ＋ｉ＜Ｖｒｅｆならば、Ｓｔａｔｅｒ（ｎ，ｋ）＝０
それ以外の場合、Ｓｔａｔｅｒ（ｎ，ｋ）＝？
【０１７５】
そして、Ｖｒｅｆ値の選択については、データファイルのサンプルｆｎから得られる平均値に最良な近似を与えるように行われる。
【０１７６】
検索の適用が、例えば、テキストファイルのような同類のファイルについての比較を対象とする場合において、Ｖｒｅｆの値については、ファイルデータのコーディング規則及び各コードを引き出す確率を熟知した上で、定めることを要する。
【０１７７】
フルテキストのコンピュータ検索プログラムの実施形態では、好適な実施形態において、比較されるファイルの形式が事前には分からないと考えられる。従って、Ｖｒｅｆの値については、比較されるファイルの事前分析を行うことによって決定される。本実施形態の場合、Ｖｒｅｆの値は、ｆｎを中心とする、固定サイズＫｒｅｆの列に亘ってサンプルｆｋについての平均値計算を行うことにより、各サンプルｒｎに対して次のように計算される。
【数２３】
2007531948.tif 000029
【０１７８】
サンプルｒｎが、Ｋ個の連続するサンプルｆｋに亘る平均値計算によって既に得られることが分かっているので、列のサイズＫｒｅｆ（Ｖｒｅｆｎの計算に用いられる）は、Ｋのサイズ（サンプルｒｎの計算に用いられる）よりも大きいサイズに選択される。
【０１７９】
ｋ個の連続するサンプルｒｎ｛ｒｎ，ｒｎ＋１，．．．，ｒｎ＋ｋ−１｝の列に亘ってファジー状態を決定する規則は、以下のようになる。
∀ｉ∈｛０，ｋ−１｝，ｒｎ＋ｉ＞＝Ｖｒｅｆｎ＋ｉならば、Ｓｔａｔｅｒ（ｎ，ｋ）＝１
∀ｉ∈｛０，ｋ−１｝，ｒｎ＋ｉ＜Ｖｒｅｆｎ＋ｉならば、Ｓｔａｔｅｒ（ｎ，ｋ）＝０
それ以外の場合、Ｓｔａｔｅｒ（ｎ，ｋ）＝？
【０１８０】
この規則は、「ｒ’ｎ＝（ｒｎ−Ｖｒｅｆｎ）」とすることで簡単になる。つまり、
∀ｉ∈｛０，ｋ−１｝，ｒ’ｎ＋ｉ＞＝０ならば、Ｓｔａｔｅｒ（ｎ，ｋ）＝１
∀ｉ∈｛０，ｋ−１｝，ｒ’ｎ＋ｉ＜０ならば、Ｓｔａｔｅｒ（ｎ，ｋ）＝０
それ以外の場合、Ｓｔａｔｅｒ（ｎ，ｋ）＝？
【０１８１】
Ｋが偶数であって、Ｋｒｅｆが偶数である場合に、デジタルフィルタの数式は以下のようになる。
【数２４】
2007531948.tif 000030
【０１８２】
サンプルｒ’ｎの計算に関連付けられたデジタルフィルタの周波数応答が、Σａｖｇ（Ｋ，ｆ）の計算によって簡単に得られることを想起されたい。
Ｆｉｌｔｅｒ（ｆ）＝Σａｖｇ（Ｋ，ｆ）−Σａｖｇ（Ｋｒｅｆ，ｆ）
【０１８３】
Ｋ値の選択については、フィルタのゼロ遮断周波数が、理想的なローパスフィルタで用いることを要する遮断周波数以下となるように行われ、この理想的なローパスフィルタでは、１／４に等しい、状態１又は０の確率を得ることができる。そして、想起されるのは、この理想的なローパスフィルタの遮断周波数が、数式「Ｆｅ／（２・（ｋ−１））」によってインデックス比ｋの関数として得られること、そして、この条件が、「２ｋ−１」以下のＫについて、Σａｖｇ（Ｋ，ｆ）に関して実現されることである。Ｋｒｅｆの選択については、Ｋよりも大きくされ、但し、大きくなりすぎないように行われる。
【０１８４】
フルテキストコンピュータ検索プログラムの好ましい実施形態では、Ｋ及びＫｒｅｆに用いる値が、インデックス比に望まれるｋ値の関数として自動的に調整される。Ｋの値及びＫｒｅｆの値は、ｋの倍数として選ばれ、これによってデータアドレス計算が容易になる。故に、
Ｋ＝ｉｎｔｅｒｖ×ｋ  及び  Ｋｒｅｆ＝ｉｎｔｅｒｖｒｅｆ×ｋ
【０１８５】
インデックス比ｋについて調整されたデジタルフィルタの応答は、以下のようになる。
Ｆｉｌｔｅｒ（ｋ，ｆ）＝Σａｖｇ（ｉｎｔｅｒｖ×ｋ，ｆ）−Σａｖｇ（ｉｎｔｅｒｖｒｅｆ×ｋ，ｆ）
【０１８６】
フルテキストコンピュータ検索プログラムの実施形態の場合、特定の実施形態において、ファジー状態を決定する４つの規則が同時に用いられる。
【０１８７】
第１の規則により決定されるファジー状態は、各デジタル署名のデータ項目の２つの最小有効ビットに関してコード化される。第２の規則により決定されるファジー状態は、各デジタル署名のデータ項目にかかる、次の２つの最小有効ビットに関してコード化され、各デジタル署名のデータ項目の８ビット（従って１バイト）が完全に占有されるまで以下同様に続く。
【０１８８】
この４つの規則は、パラメータｉｎｔｅｒｖ１、ｉｎｔｅｒｖ２、ｉｎｔｅｒｖ３、ｉｎｔｅｒｖ４、及びｉｎｔｅｒｖｒｅｆのセットにより明示される。同一のパラメータｉｎｔｅｒｖｒｅｆが各規則について用いられる。インデックス比ｋに対して、デフォルトの選択は、ファジー状態を決定する各規則に関連付けられた、以下のようなデジタルフィルタのセット（組）となる。
Ｆｉｌｔｅｒ１（ｋ，ｆ）＝Σａｖｇ（２ｋ，ｆ）−Σａｖｇ（１４ｋ，ｆ）
Ｆｉｌｔｅｒ２（ｋ，ｆ）＝Σａｖｇ（３ｋ，ｆ）−Σａｖｇ（１４ｋ，ｆ）
Ｆｉｌｔｅｒ３（ｋ，ｆ）＝Σａｖｇ（５ｋ，ｆ）−Σａｖｇ（１４ｋ，ｆ）
Ｆｉｌｔｅｒ４（ｋ，ｆ）＝Σａｖｇ（７ｋ，ｆ）−Σａｖｇ（１４ｋ，ｆ）
【０１８９】
図１５には、インデックス比がｋ＝５の場合に調整された、デフォルトのデジタルフィルタの周波数応答を示す。インデックス比ｋについて調整されたデフォルトのデジタルフィルタに対する数式は、以下のとおりである。
【数２５】
2007531948.tif 000031
【０１９０】
除算によって引き起こされる計算ノイズを回避するために、有利な実施形態においては、先ず和を求め、それから、最初の和にＫｒｅｆを掛けて、第２の和にＫを掛けることによって、ｒｎ項に関するサインテスト（符号検定）を行う。
【０１９１】
次に、フルテキスト検索エンジンに適用する際の、完全な最適化について説明する。
【０１９２】
この最適化は、適切なインデックス比の決定から始まる。
【０１９３】
ローパスデジタルフィルタの実施例（図１３）についてなされる、特定の選択を独立とするために、このデジタルフィルタに対する、以下の一般的な等式を用いる。
【数２６】
2007531948.tif 000032
【０１９４】
図１３との関連で示したように、各デジタル署名のデータ項目ｓｎ／ｋは、ｋ個の連続したサンプル｛ｒｎ，ｒｎ＋１，ｒｎ＋２，．．．，ｒｎ＋ｋ＋１｝のグループに基づいて決定され、ここで、ｋはインデックス比の値を示し、ｎはｋの倍数に選ばれる。この決定は、次の２ステップに分解できる。
・各サンプルｒｎに関連付けられた２値状態ｅｂｎの決定。
ここで、ｒｎ＜０であればｅｂｎ＝０、さもなくばｅｂｎ＝１とされる。
・連続する２値状態｛ｅｂｎ，ｅｂｎ＋１，ｅｂｎ＋２，．．．，ｅｂｎ＋ｋ＋１｝のグループに対する論理ＯＲによる、ファジー状態ｓｎ／ｋの決定。
ｓｎ／ｋ＝（ｅｂｎ  ｏｒ  ｅｂｎ＋１  ｏｒ  ｅｂｎ＋２  ｏｒ  ．．．  ｏｒ  ｅｂｎ＋ｋ＋１）
【０１９５】
図１６Ａには、ファイルのデータアドレスとデジタル署名のデータアドレスとの関係を示す。インデックス比ｋの選択の場合、アドレス（ｎ／ｋ）の各デジタル署名のデータ項目は、（Ｉ１＋ｋ＋Ｉ２）個のファイルデータのグループ、｛ｆｎ−Ｉ１，．．．，ｆｎ＋Ｉ２＋ｋ−１｝に基づいて決定されることが分かる。注意すべきは、サンプルｒｎの計算に用いるアドレスが、インデックス（指数付け）されるファイルのデータの範囲をオーバーフロー（桁あふれ）する場合に、関連付けられた状態ｅｂｎがファジー状態「？」に初期化されることである。図１６Ａにおいて、サンプルｆｎは、ファイルのデータからとり出される。そして、デジタルフィルタリングが、これらに適用され、対応するフィルタ処理されたサンプルｒｎ、つまり、関連する状態ｅｂｎにマッチするサンプルが得られる。デジタル署名データに対応するファジー状態ｓｎ／ｋは、その後、論理ＯＲを用いた比較によって、次のように決定される。
ｓｎ／ｋ＝（ｅｂｎ  ｏｒ  ｅｂｎ＋１  ｏｒ  ｅｂｎ＋２  ｏｒ  ．．．  ｏｒ  ｅｂｎ＋ｋ＋１）
尚、ここで好ましくは、サンプルｆｎの同じ開始アドレスに従う。
【０１９６】
フルテキスト検索エンジンへの適用において、インデックス比のｋ値は、２つのファイルに共通する抽出部分の最小サイズの値を条件付け、該抽出部分は、デジタル署名の共通の抽出部分の検索を行うことにより検出することができる。この、ファイルの共通の抽出部分についての最小サイズは、デジタル署名に共通の抽出部分についてのサイズが１に等しい場合に得られる。この場合、共通のファイル抽出部分を検出するための条件に要求されるのは、発見される抽出部分の、連続するデータのグループが、各デジタル署名のデータ項目の計算に用いる、連続するデータのグループを網羅することである。
【０１９７】
発見される共通のファイル抽出部分のサイズに対して、表記ｔｅｘｔを用い、また、インデックスデータ項目の計算に用いる、データのグループのサイズに対して、表記ｔｓｉｇｎを用いることで、関係「ｔｅｘｔ≧ｔｓｉｇｎ＋（ｋ−１）」が示される。
【０１９８】
図１６Ｂには、ファイル抽出部分の条件によって、デジタル署名のデータ項目の計算と関連付けられたデータの重複の条件を表している。図１６Ｂにおいて、参照記号ＥＸＴは、データ抽出部分を示し、当該部分は、アドレス（ｎ／ｋ）のデジタル署名のデータ項目を決定するために用いる、データグループについての重複条件を満たす。また、参照記号Ｇ１は、アドレス（ｎ／ｋ）のデジタル署名のデータ項目を決定するために用いるデータグループを示す。参照記号Ｇ２は、各アドレス（ｎ／ｋ）−１及び（ｎ／ｋ）のデジタル信号データを決定するために用いるデータグループを示す。そして、参照記号ＡＤＳＮは、デジタル署名データのアドレスを示す。尚、整数ｎはインデックス比ｋの倍数であることを想起されたい。
【０１９９】
重複条件は、検索されることになるデータ抽出部分の開始アドレスの位相に依存することが観察される。最も好ましい場合において、抽出部分の開始アドレスは、デジタル署名のデータ項目の計算に用いる、データグループの最初のデータ項目のアドレスに一致する。この場合、抽出部分の開始アドレスは、「ｎ−Ｉ１」（ｎはｋの倍数）であり、重複についての抽出部分の最小サイズは、「Ｉ１＋Ｉ２＋ｋ」である。最も好ましくない場合において、抽出部分の開始アドレスは、デジタル署名のデータ項目の計算に用いる、データグループの最初のデータ項目のアドレス＋１に一致する。この場合、抽出部分の開始アドレスは、「ｎ−Ｉ１−（ｋ−１）」（ｎはｋの倍数）であり、重複についての抽出部分の最小サイズは、「Ｉ１＋Ｉ２＋ｋ＋（ｋ−１）」に等しい。
【０２００】
全ての場合において、１つのデジタル署名のデータ項目の計算に用いるデータグループに対する重複条件は、発見される抽出部分のサイズが（Ｉ１＋Ｉ２＋２ｋ−１）以上であれば、満たされる。逆に、発見される抽出部分のサイズが（Ｉ１＋Ｉ２＋２ｋ−１）に等しい場合、抽出部分は、デジタル署名の１つのデータ項目の計算に用いるデータグループと実際に重複する。
【０２０１】
この論法は、サイズＴＥＳのデジタル署名データの抽出部分を計算するのに用いるデータグループの重複の場合に、拡張することができる。最も好ましい場合において、抽出部分の開始アドレスは、デジタル署名のＴＥＳ個の連続するデータを計算するために用いるデータグループの、最初のデータ項目のアドレスに一致する。抽出部分の開始アドレスが「ｎ−Ｉ１」（ｎはｋの倍数）に等しい場合、重複についての抽出部分の最小サイズは、「Ｉ１＋Ｉ２＋ｋ・ＴＥＳ」である。
【０２０２】
最も好ましくない場合、つまり、抽出部分の開始アドレスが、デジタル署名のＴＥＳ個のデータを計算するために用いるデータグループの、最初のデータ項目のアドレス＋１に一致する場合において、抽出部分の開始アドレスは、「ｎ−Ｉ１−（ｋ−１）」（ｎはｋの倍数）に等しく、重複についての抽出部分の最小サイズは、「Ｉ１＋Ｉ２＋ｋ・ＴＥＳ＋（ｋ−１）」に等しい。
【０２０３】
全ての場合において、デジタル署名のＴＥＳ個の連続するデータを計算するために用いるデータグループについての重複条件は、発見される抽出部分のサイズが（Ｉ１＋Ｉ２＋ｋ（ＴＥＳ＋１）−１）以上である場合に満たされる。
【０２０４】
上記の数式に基づき、逆の論法を適用して、サイズＴＥＦをもった、ファイルの共通の抽出部分を検索するために使用できる、インデックス比ｋの値を決定する。このとき、以下の関係を満たすことが必要である。
ＴＥＦ≧Ｉ１＋Ｉ２＋ｋ（ＴＥＳ＋１）−１、及び、
ＴＥＳ≧１  （これは単に、デジタル署名の共通の抽出部分についての最小サイズである。）
【０２０５】
ｋの最小値は、ｋｍｉｎ＝２であり、そうでない場合には勿論、検索速度に何らの改善も見られないことになる。
【０２０６】
最終的に、ここから、ＴＥＦに使用できる最小サイズの値を推定する。
ＴＥＦｍｉｎｉ＝Ｉ１＋Ｉ２＋２（ＴＥＳ＋１）−１
【０２０７】
ＴＥＳ＝１の場合に、ＴＥＦｍｉｎｉ＝Ｉ１＋Ｉ２＋３となることに留意されたい。
【０２０８】
ｋの最大値は、ＴＥＳ＝１とすることにより、逆向きに得られる。つまり、以下のとおりである。
ｋｍａｘ＝［（ＴＥＦ−Ｉ１−Ｉ２＋１）／２］の整数部
【０２０９】
ｋｍｉｎとｋｍａｘとの間にある任意のｋ値に対して、署名の共通の抽出部分のサイズＴＥＳを推定する。これは、サイズＴＥＦをもった、ファイルに共通する、あり得る抽出部分の検出を条件付けることになる。
ＴＥＳ≦［（ＴＥＦ−Ｉ１＋Ｉ２＋１）／ｋ］の整数部−１
【０２１０】
これらの数式は、既に見たように、インデックス比ｋに対して調整された、「デフォルト」のデジタルフィルタについての特定のケースに合わせることができる。その際、Ｉ１を（ｉｎｔｅｒｖｒｅｆ×ｋ）／２で置き換え、Ｉ２をＩ１−１で置き換えれば済む。ＴＥＦ、ＴＥＳ、ｋ、及びｉｎｔｅｒｖｒｅｆの間には、以下の関係が得られる。
ＴＥＦ≧ｋ（ｉｎｔｅｒｖｒｅｆ＋ＴＥＳ＋１）−２
【０２１１】
ｋ＝２及びＴＥＳ＝１の場合、ＴＥＦに使用できる最小サイズ値が得られ、「ＴＥＦｍｉｎｉ＝２・ｉｎｔｅｒｖｒｅｆ＋２」が導かれる。
【０２１２】
ＴＥＦを固定とした場合に、インデックス比ｋに対する正当な値の範囲が以下のように導出される。
ｋｍｉｎ＝２≦ｋ≦ｋｍａｘ＝［（ＴＥＦ＋２）／（ｉｎｔｅｒｖｒｅｆ＋２））］の整数部
【０２１３】
ｋｍｉｎとｋｍａｘとの間にある任意のｋ値に対して、署名の共通の抽出部分のサイズＴＥＳを以下のように推定する。該サイズは、サイズＴＥＦをもった、ファイルに共通な、あり得る抽出部分の検出を条件付ける。
ＴＥＳ≦［（ＴＥＦ＋２）／ｋ］の整数部−（ｉｎｔｅｒｖｒｅｆ＋１）
【０２１４】
従って、サイズＴＥＦの、ファイルの共通の抽出部分についての検出は、各種のインデックス比ｋの値を用いて、デジタル署名を比較することによって得られる。決定された値ＴＥＦに対して、ｋｍｉｎからｋｍａｘまでの間で使用できるｋ値の範囲が推定される。そして、使用できるｋ値のそれぞれに対して、デジタル署名の共通の抽出部分についての最大サイズの値ＴＥＳを決定するが、これは、サイズＴＥＦとされる、ファイルの共通の抽出部分を検出することを保証する。
【０２１５】
次に、検索速度を最速とするために、（正当な範囲、つまりｋｍｉｎとｋｍａｘとの間における）ｋ値の選定方法について検証する。
【０２１６】
既述のように、フルテキスト検索エンジンへの適用において、検索は以下の２つのパスで行われる。
・ＴＥＳ以上のサイズをもった、デジタル署名の共通の抽出部分を検索すること。
・デジタル署名の、発見された共通の抽出部分のそれぞれに対して、デジタル署名の共通の抽出部分についての開始位置のペアと関連して、ファイルの抽出部分についての開始位置のペアのセットの中から、サイズＴＥＦをもった、ファイルの共通の抽出部分を対象として検索すること。
【０２１７】
これら２つの検索パスに対して行われる、比較演算の回数を評価する場合に、最初の取り組みにおいて、以下のような簡単化した仮定を採用する。
・ファイルのデータを引き出す確率は独立である。
・さらに、デジタル署名のデータを引き出す確率は独立である。
【０２１８】
サイズ１をもつ、ファイルの共通の抽出部分を引き出す確率をＰＦで示す。また、サイズ２をもつ、ファイルの共通の抽出部分を引き出す確率をＰＦ２で示す。そして、サイズＴＥＦをもつ、ファイルの共通の抽出部分を引き出す確率はＰＦＴＥＦである。
【０２１９】
続いて、サイズ１をもつ、デジタル署名の共通の抽出部分を引き出す確率をＰＳで示す。また、サイズ２をもつ、デジタル署名の共通の抽出部分を引き出す確率をＰＳ２で示す。サイズＴＥＳの抽出部分を引き出す確率はＰＳＴＥＳである。
【０２２０】
さらに、以下の表記を採用する。
ＴＦ１：比較する第１ファイルのサイズ
ＴＦ２：第１ファイルと比較される第２ファイルのサイズ
ＴＳ１：第１ファイルに関連付けられたデジタル署名のサイズ
ＴＳ２：第２ファイルに関連付けられたデジタル署名のサイズ
【０２２１】
先ずは、サイズがＴＥＳ以上の、デジタル署名の共通の抽出部分について、「粗い」検索を行う第１のステップで行われる比較回数Ｔｏｔａｌ１を評価する。デジタル署名の共通の抽出部分について、そのあり得る開始位置のペアの数は、ＴＳ１×ＴＳ２に等しい。インデックス比ｋの値に対して、サイズＴＳ１及びＴＳ２は、以下の関係によって、サイズＴＦ１及びＴＦ２から導かれる。
ＴＳ１＝ＴＦｌ／ｋ  及び  ＴＳ２＝ＴＦ２／ｋ
【０２２２】
デジタル署名の共通の抽出部分について、そのあり得る開始位置の各ペアに対して、抽出部分の第１データを比較する。相関関係がある場合に、抽出部分の第２データとの比較が続行され、要求された、抽出部分のサイズＴＥＳが得られるまで、以下同様に行われる。
【０２２３】
各テストに対して、比較演算の平均回数は、引き出し確率ＰＳから、以下のように得られる。
抽出部分の第１データのテストに対して：１回の演算
抽出部分の第２データのテストに対して：ＰＳ回の演算
抽出部分のＴＥＳ番目のデータのテストに対して：ＰＳＴＥＳ−１回の演算
【０２２４】
全体として、１＋ＰＳ＋．．．＋ＰＳＴＥＳ−１、即ち、（１−ＰＳＴＥＳ）／（１−ＰＳ）回の演算が得られる。Ｔｏｔａｌｌの値は、これに（ＴＳ１×ＴＳ２）を掛けることにより導かれ、即ち、以下のようになる。
Ｔｏｔａｌ１＝（ＴＦ１×ＴＦ２）×（１−ＰＳＴＥＳ）／（ｋ２×（１−ＰＳ））
【０２２５】
次に、事前の粗い検索ステップで発見された、デジタル署名についての共通の抽出部分に関連して、ファイルの抽出部分について、その開始位置のペアのセット中から、サイズＴＥＦをもつファイルの共通の抽出部分を「対象」検索する第２ステップで行われる比較回数Ｔｏｔａｌ２を評価する。開始アドレスのペア（ｎ１，ｎ２）でラベル付けされたデジタル署名の共通の抽出部分に対して、第１ファイルに関してテストされる開始アドレスは、（ｋ・ｎ１＋Ｉ２＋ｋ・ＴＥＳ−ＴＥＦ）と（ｋ・ｎ１−Ｉ１）との間、つまり、全体で、Ｎａ＝（ＴＥＦ−Ｉ１−Ｉ２−ｋ・ＴＥＳ＋１）個の、あり得るアドレスの中にある（図１６Ａ及び図１６Ｂ）。
【０２２６】
さらに、ＴＥＦの値については、ｋに対する、あり得る最大の値を用いる場合において、以下の関係で括られる。
Ｉ１＋Ｉ２＋ｋ（ＴＥＳ＋１）−１≦ＴＥＦ＜Ｉ１＋Ｉ２＋ｋ（ＴＥＳ＋２）−１
【０２２７】
これより、「ｋ≦Ｎａ＜２ｋ」が導かれる。
【０２２８】
ｎ１にｎ２を置き換えることにより、同じ推論を、第２ファイルに関してテストされる開始アドレスに当てはめることができる。
【０２２９】
従って、合計でＮａ２個とされる、ファイルの共通の抽出部分についての開始位置のペアが評価されることになる。サイズＴＥＦをもつ、ファイルの共通の抽出部分を検索するための行われる比較の平均回数は、以下の粗い検索ステップの平均回数と同様の推論を適用することによって、引き出し確率ＰＳから得られる。
Ｎａ２×（１−ＰＦＴＥＦ）／（１−ＰＦ）
【０２３０】
第１のステップで発見されたデジタル署名の共通の抽出部分についての平均回数は、引出し確率ＰＳ及び署名サイズＴＳ１、ＴＳ２から、以下のように得られる。
ＴＳ１×ＴＳ２×ＰＳＴＥＳ
【０２３１】
ＴＳ１をＴＦｌ／ｋで置き換え、そしてＴＳ２をＴＦ２／ｋに置き換えると、最終的に上記した数式の積からＴｏｔａｌ２が、以下のように得られる。
Ｔｏｔａｌ２＝（ＴＦ１×ＴＦ２）×（Ｎａ２／ｋ２）×ＰＳＴＥＳ×（１−ＰＦＴＥＦ）／（１−ＰＦ）
【０２３２】
既に、「１≦Ｎａ／ｋ＜２」が示されている。このことから、以下の関係が導かれる。
Ｔｏｔａｌ２≧（ＴＦ１×ＴＦ２）×ＰＳＴＥＳ×（１−ＰＦＴＥＦ）／（１−ＰＦ）、及び、
Ｔｏｔａｌ２＜４×（ＴＦ１×ＴＦ２）×ＰＳＴＥＳ×（１−ＰＦＴＥＦ）／（１−ＰＦ）
【０２３３】
尚、記号「×」は「掛ける」（乗算）を意味することを指摘しておく。
【０２３４】
最終的に、２つの検索パスについて行われる比較演算の回数Ｔｏｔａｌ３の評価は、単にＴｏｔａｌｌとＴｏｔａｌ２とを加算することで得られ、以下のようになる。
Ｔｏｔａｌ３＝（ＴＦ１×ＴＦ２）×（１−ＰＳＴＥＳ）／（ｋ２（１−ＰＳ））
＋（ＴＦ１×ＴＦ２）×（Ｎａ／ｋ）２×ＰＳＴＥＳ×（１−ＰＦＴＥＦ）／（１−ＰＦ）
【０２３５】
ＴＥＦ及びＴＥＳの値が大きい場合、この関係は以下のように近似される。
Ｔｏｔａｌ３＝（ＴＦ１×ＴＦ２）×［（１／（ｋ２×（１−ＰＳ）））＋（（Ｎａ／ｋ）２×ＰＳＴＥＳ／（１−ＰＦ））］
【０２３６】
リファレンス検索アルゴリズムで行われる比較の総数は、ＴＦ１×ＴＦ２に近い。後者の数字とＴｏｔａｌ３との間の比により、本発明の範囲内でのアルゴリズムを用いることにより得られる、検索速度のゲイン（ｇａｉｎ：利得）についての推定が、以下のように与えられる。
Ｇａｉｎ＝１／［（１／（ｋ２×（１−ＰＳ）））＋（（Ｎａ／ｋ）２×ＰＳＴＥＳ／（１−ＰＦ））］
【０２３７】
上記の和における第２項が、１／ｋ２の項よりも小さい場合に、ｋ２／２（ｌ−ＰＳ）より大きいゲインが得られることに留意されたい。
【０２３８】
但し、効果的な検索速度のゲインを得るには、デジタル署名を計算するための、実際の回数を推定する必要があることを付言しておく。
【０２３９】
図１７を参照すると分かるように、インデックス比ｋの関数として、関数Ｔｏｔａｌ３の変化について、以下の検討結果が示される。
・１／ｋ２をもつ和の第１項は、ｋが増加するにつれて急速に減少する。
・ＰＳＴＥＳ（ｋ）をもつ和の第２項は、ｋが増加するにつれて増大する。というのも、ＴＥＳ（ｋ）の値は、ｋが増加するにつれて減少するからである。
【０２４０】
一般の場合に、「ＴＥＳ＝［（ＴＥＦ−Ｉ１−Ｉ２＋２）／ｋ］の整数部−１」、であることを想起されたい。
【０２４１】
最適化された平均値デジタルフィルタの場合には、以下のようになる。
ＴＥＳ＝［（ＴＥＦ＋２）／ｋ］の整数部−（ｉｎｔｅｒｖｒｅｆ＋１）
【０２４２】
この関数の最小値を得るために用いるｋ値が、単純な数学的関係によって決まらないことは明白である。しかしながら、ｋの、一連のあり得る値が減少すると、ｋの最適値は経験的に決められる。ｋのあり得る値（ｋｍｉｎとｋｍａｘとの間）のそれぞれに対して、ｋの関数としてＴｏｔａｌ３の値を計算し、Ｔｏｔａｌ３の最小値を生じさせるｋの値を保持すればよい。
【０２４３】
しかしながら、デジタル署名について、その共通の抽出部分を引き出す確率を計算するために用いるモデルを修正すれば、行われる比較演算の回数についての評価が、より正確となる。詳細には、デジタル署名のデータを引き出す確率は、相互に独立ではない。その理由は、アドレス（ｎ／ｋ）の、デジタル署名のデータ項目の計算に用いるファイルデータの範囲と、アドレス（ｎ／ｋ）＋１の、デジタル署名のデータ項目の計算に用いるファイルデータの範囲との間に、相当の重複が存在するためである。
【０２４４】
（Ｉ１＋Ｉ２＋１）個の係数をもったローパスデジタルフィルタの一般的な場合に、アドレス（ｎ／ｋ）及び（（ｎ／ｋ）＋ｊ）の、デジタル署名データによって得られるファジー状態については、それらの決定に用いるファイルデータの範囲同士の間に重複がなければ、独立したものとなる。この条件は、「（ｎ＋Ｉ２＋ｋ−１）＜（ｎ＋ｋ・ｊ−Ｉ１−ｋ＋１）」の場合、即ち、「ｊ＞（Ｉ１＋Ｉ２＋２ｋ−２）／ｋ」であれば、満たされる。
【０２４５】
インデックス比ｋに対して調整されたデフォルトのデジタルフィルタという、特定の事例では、上記式において（Ｉ１＋Ｉ２）を、（ｋ×ｉｎｔｅｒｖｒｅｆ−１）に、単に置き換える。すると、独立の条件は、「ｊ＞（ｉｎｔｅｒｖｒｅｆ＋２）−３／ｋ」であれば満たされ、あるいは、別の言い方をすると、デジタル署名データ間のアドレスの相違が、少なくとも（ｉｎｔｅｒｖｒｅｆ＋２）に等しい場合に、独立の条件が満たされることになる。
【０２４６】
デジタル署名の連続するデータによって得られるファジー状態の依存性を考慮に入れるため、確率モデルを以下に示すように修正する。
【０２４７】
サイズ１をもった、デジタル署名の共通の抽出部分を引き出す、独立の確率を、ＰＳＩで示す。また、サイズ２をもった、デジタル署名の共通の抽出部分を引き出す確率は、サイズ１の抽出部分を引き出す確率ＰＳＩに対して、以前発見されたサイズ１の抽出部分に引き続いてその次に別のサイズ１の抽出部分を引き出す条件付き確率ＰＳＤ（Ｄは依存性を示す）を掛けた確率に等しい。つまり、この引き出し確率は、ＰＳＩ×ＰＳＤとなる。サイズ３をもつ、デジタル署名の共通の抽出部分を引き出す確率は、ＰＳＩ×ＰＳＤ２となる。最終的に、サイズＴＥＳである抽出部分を引き出す確率は、ＰＳＩ×ＰＳＤＴＥＳ−１となる。ＰＳＩとＰＳＤとの間には、「ＰＳＤ（ｉｎｔｅｒｖｒｅｆ＋２）＜ＰＳＩ」という関係が示される。
【０２４８】
この新たな確率モデルに基づいて、Ｔｏｔａｌ１とＴｏｔａｌ２の数を計算するための数式について再び評価する。
Ｔｏｔａｌ１＝［（ＴＦ１×ＴＦ２）／ｋ２］×［１＋（ＰＳＩ×（１−ＰＳＤ（ＴＥＳ−１））／（１−ＰＳＤ））］
Ｔｏｔａｌ２＝（ＴＦ１×ＴＦ２）×（Ｎａ／ｋ）２×ＰＳＩ×ＰＳＤ（ＴＥＳ−１）×（１−ＰＦＴＥＦ）／（１−ＰＦ）
【０２４９】
ＴＥＦ及びＴＥＳの値が大きい場合に、数式は以下のように近似できる。
Ｔｏｔａｌ１＝［（ＴＦ１×ＴＦ２）／ｋ２］×［１＋（ＰＳＩ／（１−ＰＳＤ））］
Ｔｏｔａｌ２＝（ＴＦ１×ＴＦ２）×（Ｎａ／ｋ）２×ＰＳＩ×ＰＳＤ（ＴＥＳ−１）／（１−ＰＦ）
そしてＴｏｔａｌ３＝（ＴＦ１×ＴＦ２）×［（１＋（ＰＳＩ／（１−ＰＳＤ））／ｋ２＋（（Ｎａ／ｋ）２×ＰＳＩ×ＰＳＤ（ＴＥＳ−１））／（１−ＰＦ）］
【０２５０】
好適な実施形態において、ＰＳＩ及びＰＳＤの値は、サイズの大きなファイルで得られた、デジタル署名同士の間で比較した結果について、その統計的な分析から事前に決定される。このため、特定の統計的な分析プログラムによって、ＰＳＩ及びＰＳＤに用いる値が標準化される。
【０２５１】
インデックス比ｋに対して調整された、４つのデフォルトデジタルフィルタ（図１５）のセットについて、ＰＳＩ及びＰＳＤ用に記録された値は、ｋの関数としてほとんど変化しない。本例では、ＰＳＩ＝０．４及びＰＳＤ＝０．６のように、端数を切り捨てた値を使っている。
【０２５２】
図１７には、ｋの関数としてのＴｏｔａｌ１、Ｔｏｔａｌ２、及びＴｏｔａｌ３の変化を、デフォルトデジタルフィルタのセットで示しており、発見されるファイルの共通の抽出部分の最小サイズ値が１０００に等しく、そして、比較されるファイルのサイズが１００キロバイトである場合を示す。
【０２５３】
次に、フルテキスト検索エンジンのために、デジタル署名の共通の抽出部分を検索する際の選択性の向上についてさらに説明する。
【０２５４】
単純な場合、つまり、デジタル署名データがそれぞれに、１つのファジー論理状態のみを有する場合において、サイズ１をもつ、デジタル署名の共通の抽出部分を検出する確率ＰＳＩは、状態「０」、「１」、及び「？」を引き出す確率から導くことができる。
【０２５５】
Ｐ０によって、状態０を引き出す確率を示し、Ｐ１によって、状態１を引き出す確率を示し、Ｐ？によって、状態？を引き出す確率を示すものとする。
【０２５６】
評価対象となる、デジタル署名の抽出部分についての任意の開始位置のペアに対して、サイズ１をもつ、デジタル署名の共通の抽出部分を検出する条件は、以下のとおりである。
・第１ファイルに関連付けられたデジタル署名のデータ項目の状態が０に等しい場合には、第２ファイルに関連付けられたデジタル署名のデータ項目の状態が０又は？に等しいことを要する。
・第１ファイルに関連付けられたデジタル署名のデータ項目の状態が１に等しい場合には、第２ファイルに関連付けられたデジタル署名のデータ項目の状態が１又は？に等しいことを要する。
・第１ファイルに関連付けられたデジタル署名のデータ項目の状態が？に等しい場合には、第２ファイルに関連付けられたデジタル署名のデータ項目の状態は０、１、又は？の、いずれの値をとってもよい。
【０２５７】
評価対象となる、デジタル署名の抽出部分についての任意の開始位置のペアに対して、サイズ１をもつ、デジタル署名の共通の抽出部分を検出する確率は、上記の状況それぞれについて、以下のように決定される。
・第１ファイルに関連付けられたデジタル署名のデータ項目の状態が０に等しく、かつ第２ファイルに関連付けられたデジタル署名のデータ項目の状態が０又は？に等しい（確率＝Ｐ０×（Ｐ０＋Ｐ？））
・第１ファイルに関連付けられたデジタル署名のデータ項目の状態が１に等しく、かつ第２ファイルに関連付けられたデジタル署名のデータ項目の状態が１又は？に等しい（確率＝Ｐ１×（Ｐ１＋Ｐ？））
・第１ファイルに関連付けられたデジタル署名のデータ項目の状態が？に等しく、かつ第２ファイルに関連付けられたデジタル署名のデータ項目の状態が、任意の値をとる（確率＝Ｐ？×１＝Ｐ？）。
【０２５８】
検出確率ＰＳＩは、各状況の確率を加算することで以下のように得られる。
ＰＳＩ＝Ｐ０×（Ｐ０＋Ｐ？）＋Ｐ１×（Ｐ１＋Ｐ？）＋Ｐ？
【０２５９】
ＰＳＩを決定する数式は、ここでも、（Ｐ０＋Ｐ？）を（１−Ｐ１）に、（Ｐ１＋Ｐ？）を（１−Ｐ０）に、（Ｐ０＋Ｐ１＋Ｐ？）を１に置き換えることによって、以下のように簡単化できる。
ＰＳＩ＝Ｐ０×（１−Ｐ１）＋Ｐ１×（１−Ｐ０）＋Ｐ？＝１−２×Ｐ０×Ｐ１
【０２６０】
ＰＳＩの最大値は１に等しい。これはＰ０＝０又はＰ１＝０の場合に得られる。この状況は除外すべきとされるが、この場合に、デジタル署名の共通の抽出部分を検索する上で何らの選択性（ｓｅｌｅｃｔｉｖｉｔｙ）を持たないからである。
【０２６１】
ＰＳＩの最小値は１／２に等しい。これはＰ？＝０及びＰ０＝Ｐ１＝１／２の場合に得られる。この状況は理想的であり、既に見たように、パラメータｉｎｔｅｒｖｒｅｆ及びｉｎｔｅｒｖの値に大きな値をもった、調整済みのデフォルトのデジタルフィルタを用いる場合において、この状況を近似的に得ることができる。
【０２６２】
平均値デジタルフィルタに対して、ＰＳＩの値は、サイズの大きなデジタル署名の相互比較を統計的に分析することによって得られる。カットオフがＦｅ／２（ｋ−１）とされる、理想的なフィルタの適用が、確率Ｐ０＝Ｐ１＝１／４及びＰ？＝１／２によって与えられることは既に示されている。従って、「ＰＳＩ＝７／８」となる。
【０２６３】
それ故、好ましい実施形態においては、「ＰＳＩ＜７／８」となるように、さらに選択性をもったデジタルフィルタを用いる。
【０２６４】
デジタル署名データのそれぞれが、４つのファジー論理状態（追加された状態「Ｘ」（禁止））を有する一般的なケースにおいて、サイズ１をもつ、デジタル署名の共通の抽出部分を検出する確率ＰＳＩは、前述の結果に基づいて評価される。ファジー状態を決定する第１の規則によって得られる状態の比較のみに基づく、サイズ１をもったデジタル署名の共通の抽出部分を検出する確率として、これをＰＳＩ１によって示すものとする。また、ＰＳ２、ＰＳ３、及びＰＳ４は、ファジー状態を決定するための、規則１に続く規則（規則２、規則３、及び規則４）に関連付けられた同様の検出確率を示すものとする。これらの規則が相互に独立である場合には、「ＰＳＩ＝ＰＳＩ１×ＰＳＩ２×ＰＳＩ３×ＰＳＩ４」である。実際には、これらの規則間には依存性があり、よって、統計的な分析により得られるＰＳＩの値は、前記の積よりも大きい。
【０２６５】
従って、デジタル署名についての各ファジー状態の決定は、ｋ個の連続する２値状態のセットの事前計算によって行われる。ファイルの共通の抽出部分を検索する際に、以下の場合には、ファイル間での、あり得る共通の抽出部分の検出が常に保証されることが分かる。
・第１ファイルに関連付けられたアドレス（ｎ１／ｋ）をもった、デジタル署名のデータ項目のそれぞれは、アドレスｎ１，ｎ１＋１，．．．，ｎ１＋ｋ−１の、ｋ個の連続する２値状態を相互比較することにより決定される。
・第１ファイルに関連付けられたアドレス（ｎ２／ｋ）をもった、デジタル署名のデータ項目のそれぞれは、アドレスｎ２について計算された２値状態を単にコピーすることによって決定される。
【０２６６】
好適な実施形態において、ファジー状態（０、１、又は？）を有するデジタル署名（第１ファイル）が、実際上、２値状態（０又は１）のみを有するデジタル署名（第２ファイル）と相互比較されるということは、確かに示される。以下では、これによって、検索の選択性が向上することを示すが、その理由は、デジタル署名に共通の抽出部分を検出する確率が単に減少するためである。
【０２６７】
評価されるデジタル署名の抽出部分について、任意の開始位置のペアに対して、サイズ１をもつ、デジタル署名の共通の抽出部分を検出する必要条件は、以下のとおりである。
・第１ファイルに関連付けられたデジタル署名のデータ項目の状態が０に等しい場合には、第２ファイルに関連付けられたデジタル署名のデータ項目の状態が０に等しいことを要する。
・第１ファイルに関連付けられたデジタル署名のデータ項目の状態が１に等しい場合には、第２ファイルに関連付けられたデジタル署名のデータ項目の状態が１に等しくことを要する。
・第１ファイルに関連付けられたデジタル署名のデータ項目の状態が？に等しい場合には、第２ファイルに関連付けられたデジタル署名のデータ項目の状態は、０又は１のいずれの値をとってもよい。
【０２６８】
第２ファイルに関連付けられたデジタル署名のデータ項目がもっている２値状態を引き出す確率について、表記Ｐ０’及びＰ１’を用いる。以下の関係が得られる。
Ｐ０’＋Ｐ１’＝１
Ｐ０≦Ｐ０’≦Ｐ０＋Ｐ？
Ｐ１’≦Ｐ１’≦Ｐ１＋Ｐ？
【０２６９】
評価されるデジタル署名の抽出部分についての、任意の開始位置のペアに対して、サイズ１をもつ、デジタル署名の共通の抽出部分を検出する確率は、上記の状況のそれぞれについて、以下のように決定される。
・第１ファイルに関連付けられたデジタル署名のデータ項目の状態が０に等しく、かつ第２ファイルに関連付けられたデジタル署名のデータ項目の状態が０に等しい（確率＝Ｐ０×Ｐ０’）
・第１ファイルに関連付けられたデジタル署名のデータ項目の状態が１に等しく、かつ第２ファイルに関連付けられたデジタル署名のデータ項目の状態が１に等しい（確率＝Ｐ１×Ｐ１’）
・第１ファイルに関連付けられたデジタル署名のデータ項目の状態が？に等しく、かつ第２ファイルに関連付けられたデジタル署名のデータ項目の状態が、任意の値をとる（確率＝Ｐ？×１＝Ｐ？）。
【０２７０】
検出確率ＰＳＩ’は、各状況の確率を加算することで以下のように得られる。
ＰＳＩ’＝Ｐ０×Ｐ０’＋Ｐ１×Ｐ１’＋Ｐ？
≦Ｐ０×（Ｐ０＋Ｐ？）＋Ｐ１×（Ｐ１＋Ｐ？）＋Ｐ？
≦ＰＳＩ
【０２７１】
従って、「ＰＳＩ’≦ＰＳＩ」の関係は、ファジー状態をもつ署名と２値状態しかもたない署名との間での比較を行うことによる、検索の選択性の向上を示している。
【０２７２】
開始アドレスのペア（ｎ１，ｎ２）によりラベル付けされた、デジタル署名についての共通の抽出部分に対して、ファイルに関してテストされる開始アドレスは、検索のために２値のデジタル署名の使用を考慮する必要があることが分かる。ファジーデジタル署名が第１ファイルに基づいて計算される場合において、テストされる開始アドレスは、（ｋ×ｎ１＋Ｉ２＋ｋ×ＴＥＳ−ＴＥＦ）と（ｋ×ｎ１−Ｉ１）との間となる。即ち、全体では、以下のようになる。
Ｎａｆ＝（ＴＥＦ−Ｉ１−Ｉ２−ｋ×ＴＥＳ＋１）個の、あり得るアドレス
【０２７３】
２値デジタル署名が第２ファイルに基づいて計算される場合に、テストされる開始アドレスは、
（ｋ×ｎ２＋Ｉ２＋ｋ×（ＴＥＳ−１）−（ＴＥＦ−１））と（ｋ×ｎ２−Ｉ１）との間となる。即ち、全体として、以下のようになる。
Ｎａｂ＝（ＴＥＦ−Ｉ１−Ｉ２−ｋ×（ＴＥＳ−１））個の、あり得るアドレス
【０２７４】
パラメータｉｎｔｅｒｖｒｅｆをもつ、デフォルトデジタルフィルタに対して、以下が得られる。
Ｎａｆ＝ＴＥＦ−ｋ×ｉｎｔｅｒｖｒｅｆ−ｋ×ＴＥＳ＋２
Ｎａｂ＝ＴＥＦ−ｋ×ｉｎｔｅｒｖｒｅｆ−ｋ×（ＴＥＳ−１）＋１
【０２７５】
以下では、デジタルフィルタに関連付けられた確率規則の標準化について説明する。以下の表に記録されたものは、２つの、サイズの大きな（３００キロバイト）テキストファイルを比較することによって得られる、平均値デジタルフィルタの確率ＰＳＩ及びＰＳＤである。
【表５】
2007531948.tif 000033
【０２７６】
以下の点に留意されたい。
・ＰＳＩは常にＰＳＤ未満である。
・ｋが一定の場合、ｉｎｔｅｒｖが増加するとＰＳＩはわすかに減少するが、ＰＳＤはほぼ一定である。
・ｋが一定の場合、ｉｎｔｅｒｖｒｅｆが増加すると、ＰＳＩはわずかに減少する。
【０２７７】
４つのフィルタ（ｉｎｔｅｒｖ＝２，３，５，及び７）の集合に対して記録された確率は、各フィルタについての個別に記録された確率の積よりも大きい。従って、各規則に関連付けられた確率の相互依存性が存在することが理解される。
【０２７８】
確率の独立性をもった状況に、より近づけるためには、デジタル署名を計算する関数の実現に適合させるために、以下のような手順を想定可能である。
・規則１では、各データ項目の８ビットで整数をコード化する規則によって、サンプルｆｎがとる値を決定する。
・規則２では、２ビットでのシフトにより８ビットをローテイトした後で、これらの値を決定する。
・規則３では、４ビットでのシフトにより８ビットをローテイトした後で、これらの値を決定する。
・規則４では、６ビットでのシフトにより８ビットをローテイトした後で、これらの値を決定する。
・各規則では、平均値デジタルフィルタ、例えばｉｎｔｅｒｖ＝４及びｉｎｔｅｒｖｒｅｆ＝１０のフィルタに対して、全く同一のパラメータのペアを用いる。
【０２７９】
ＴＥＦ（及びＴＥＳ）値が大きい場合に、検索で実行される比較演算の回数を推定する数学的モデルは、用いるインデックス比の最適値の自動決定に関して、良好な結果を与える。
【０２８０】
ＴＥＦ（及びＴＥＳ）の値が小さい場合に、数学的推定モデルは、良好な結果を与えないが、これは、検索プロセスが、もはや比較演算に対して原理的に割り当てられないためである。
【０２８１】
発見されるデジタル署名についての共通の抽出部分のそれぞれに対して、プログラムは、ファイルに関する開始アドレスのペアについて、その制限された範囲に亘り、ファイルの共通の抽出部分を検索するための、対象となる検索用関数への呼び出しを開始させる。各呼び出しにおいて、関数は、呼び出しパラメータの正当性の検証及びローカル変数の初期化を、ある一定の回数で実行する。また、各呼び出しにおいて、この関数は、比較される各ファイルのデータを読み出す演算を実行するが、この演算は、その速度がコンピュータのハードディスク及びバスのパフォーマンスに依存する。これらの追加される処理時間の影響を考慮に入れるため、さらに補正された数学的モデルが用いられ、ここでは、ファイルの共通の抽出部分を検索するための、対象となる検索ステップにおいて、対象となる検索関数の呼び出し回数及び比較されるデータの読み出し回数を示す回数分の比較演算が加わる。通常、Ｔｏｔａｌ２に加え得る回数は以下の形式をとる。
［（（ＴＦ１×ＴＦ２）／ｋ２）×ＰＳＩ×ＰＳＤ（ＴＥＳ−１）］×［Ａ×Ｂ×ｋ］
ここで、Ａは、対象となる検索関数の呼び出し回数を表す定数であり、Ｂは、ハードディスクデータの読み出し回数を表す定数である。
【０２８２】
パラメータＡ及びＢの値は、プログラムの実行に用いられるコンピュータの特徴に依存し、経験的に決定される。
【０２８３】
以下に、評価用のコンピュータとして、１ＧＨｚのＰｅｎｔｉｕｍ（登録商標）ＩＩＩプロセッサ、１２８ＭバイトのＲＡＭ、２０Ｇバイトのハードディスクを用いた性能評価結果について説明する（Ｗｉｎｄｏｗｓ（登録商標）９８オペレーティングシステムで動作する）。
【０２８４】
パフォーマンスは、Ｃ＋＋言語で具体的に開発された、フルテキストコンピュータ検索プログラムの実行により記録される。このプログラムは、２つのファイルに共通の抽出部分の検索を行うために、「従来の」アルゴリズム又は本発明の範囲内でのアルゴリズムの選択を与える。本発明の範囲内でのアルゴリズムの実行回数も、デジタル署名の計算回数に統合される。
【０２８５】
パフォーマンス測定上のごまかしを回避するため、検索の実行に用いるファイルの選択には、特に注意を払う必要がある。具体的には、テストの過程で、ワード（登録商標）、エクセル（登録商標）、パワーポイント（登録商標）などの、日常用いられるソフトウェアに関連付けられたデータファイルは、同じ値０（０ｘ００）に初期化された無数の連続するデータの範囲をもたらす、ストレージフォーマットを有することが明らかとなった。これらの範囲のサイズが、数百程度のデータ項目になると、本実施形態でのプロトタイプの検索プログラムに用いる確率モデルは、ごまかされてしまう。このモデルの適合については、例えば、共通の抽出部分の開始位置としての、データ値のペア（０，０）については、対象となる検索関数において無視するといった具合に、ケースバイケースで調べることができる。
【０２８６】
テキストファイルのタイプの選択は、特に、ＨＴＭＬ形式の大きなサイズのテキスト文書にかかっている。その検索速度は、１００万比較演算毎秒（メガオペレーション／秒）で表現される。第１ファイルは、サイズ２１３２７５バイトであり、第２ファイルのサイズは１４５０４１バイトである。以下の表は、得られた結果を示す。
【表６】
2007531948.tif 000034
【０２８７】
あり得る共通の抽出部分を検索するための、他の適用について以下に説明する。ある適用分野では、ファイルの共通の抽出部分を検出する基準が、発見される抽出部分の完全な同一性とは異なる。具体的には、例えば、オーディオファイル（例えば、拡張子「．ｗａｖ」をもつ）など、信号のデジタル処理を表わすデータファイルの場合である。
【０２８８】
得られたサンプルの値は、サンプリングクロックの位相に依存することが知られている。さらに、デジタル化装置は、サンプル値に他のエラー（ノイズ、クロックジッター、ダイナミックスウィング（動的な揺れ）など）をもたらすことが知られている。
【０２８９】
このような用途では、本発明の範囲内での検索アルゴリズムの原理を、ファイル間での粗い検索のステップにのみ制限するように適合させることができる。想定されるステップは、従って以下のように、まとめられる。
・比較されるファイル当たりの、デジタル署名の計算
・デジタル署名の共通の抽出部分の検索を用いた、デジタル署名の比較
【０２９０】
以下では、確率を活用して、共通の抽出部分を検出するための基準を、自ら定義できるようにする方法について示す。
【０２９１】
既に示したとおり、インデックス比の値の最適化の枠内では、デジタル署名同士の間の、検索のための比較演算回数は、以下のように推定される。
Ｔｏｔａｌ１＝［（ＴＦ１×ＴＦ２）／ｋ２］×［１＋ＰＳＩ×（１−ＰＳＤ（ＴＥＳ―１））／（１−ＰＳＤ））］
【０２９２】
また、デジタル署名の共通の抽出部分を引き出す確率は、ＰＳＩ×ＰＳＤ（ＴＥＳ−１）に等しいことを示した。
【０２９３】
従って、それぞれのサイズがＴＦ１及びＴＦ２である、２つのファイルを相互比較することで発見されることになる、最小サイズＴＥＦをもった共通の抽出部分の推定数は、以下のようになる。
Ｎ＝［（ＴＦ１×ＴＦ２）／ｋ２］×ＰＳＩ×ＰＳＤ（ＴＥＳ−１）、
ここで、ＴＥＳ＝［（ＴＥＦ−Ｉ１−Ｉ２＋１）／ｋ］の整数部−１
【０２９４】
ｋ値の最適化は、ｋの増加につれて増大する検索速度（Ｔｏｔａｌ１に反比例）（従って、ｋの値を大きくすると有利である）と、ｋの増加につれて増大する数値Ｎ（従って、検出される、あり得る共通の抽出部分の数を制限したい場合は、ｋの値を低くするべきである）との間の妥協に依る。
【０２９５】
また、ｋ値の最適化は、Ｎに対する目標値Ｎｃ、及び発見される抽出部分の最小サイズＴＥＦの値を、事前に固定することによって行われる。これらのパラメータに基づいて、値Ｎは、ｋの許される値全てについて評価され、値Ｎｃを最良に近似することが可能なｋ値が保持される。
【０２９６】
この検索手続は、発見される、あり得る共通の抽出部分についての開始位置に不正確さをもたらす。ファジー署名と２値署名との間で、共通の抽出部分を検索する場合には（好適な実施形態に対応する）、ファイルの、あり得る共通の抽出部分について、その開始位置の不正確さが、ファジー署名に関連付けられたファイルにおいて、およそ＋ｋ又は−ｋ程度であり、そして、２値署名に関連付けられたファイルにおいて、およそ＋ｋ又は−２ｋ程度である。
【０２９７】
デジタル署名の共通の抽出部分を検出する有効確率は、ファジー署名に関する抽出部分の状態による変動を分析することで近似することができる。好ましくは、好適な実施形態では、上限確率を評価するが、これは、０状態のデータと１状態のデータとの間で生ずる移行回数を検出することにより評価され、これによって、測定された確率が所定の閾値よりも大きい共通の抽出部分を、検索結果からフィルタ処理することが可能となり、従って検索パラメータの最適化に用いる統計的な確率モデル（ＰＳＩ×ＰＳＤ（ＴＥＳ−１））を悪化させないように回避できる。
【０２９８】
従って、オーディオファイルの場合、２つの記録ファイルに共通するオーディオ抽出部分の検索については、次のように要約できる。先ずは、各ファイルに関連付けられたデジタル署名の事前計算から始める。この第１ステップが完了すると、デジタル署名ファイルは、一連の論理状態、即ち、オーディオ信号についての、一定した継続時間の連続するタイムスパンを明確化する論理状態とみなすことができる。通常、各デジタル署名のデータ項目に対して、１秒でのタイムスパンの継続期間を選択する場合に、１時間分のオーディオファイルの処理では、３６００データ項目（１秒毎に１つ）のデジタル署名のファイルを生成することになる。署名の第１データ項目は、記録における最初の１秒を特徴付け、第２データ項目が２秒を特徴付けるといった具合に、以下同様に続く。
【０２９９】
そして、共通のオーディオ抽出部分の検索が行われるが、これは、各オーディオ記録に基づいて計算されたデジタル署名のデータ同士を相互比較することで行われる。共通の抽出部分はいずれも、Ｎ個の連続したデジタル署名のデータのグループ（つまり、第１オーディオファイルに関連付けられた署名のデータ項目の第１グループ、及び第２オーディオファイルに関連付けられた第２グループ）のペアにより明らかとなる。そして、このグループに対して、第１グループのＮ個の連続したファジー論理状態と、第２グループのＮ個の連続したファジー論理状態との間には適合性（ｃｏｍｐａｔｉｂｉｌｉｔｙ）がある。
【０３００】
第１グループＧ１のデジタル署名についての、第１データ項目のアドレスによって、第１オーディオファイルにおける共通の抽出部分の一時的な位置をラベル付けすることができる。第２グループＧ２のデジタル署名についての、第１データ項目のアドレスによって、第２オーディオファイルにおける共通の抽出部分の一時的な開始位置をラベル付けすることができる。数Ｎ（個の関連して発見される連続するデータ）によって、発見される抽出部分の継続時間を推定できるようになるが、これは、各デジタル署名のデータ項目に関連付けられたタイムスパンの継続時間との簡単な積演算によってなされる。
【０３０１】
例えば、デジタル署名のデータ項目当たり１秒の継続期間をタイムスパンについて固定して、１時間の第１ファイル「ａｕｄｉｏ１」及び１時間の第２ファイル「ａｕｄｉｏ２」に関するデジタル署名が計算されたものと想定する。そして検索結果が、２０個の連続するデータ項目のデジタル署名についての共通の抽出部分であって、署名１においてアドレス１００でラベル付けされ、かつ署名２においてアドレス６２０でラベル付けされる、共通の抽出部分を与える場合において、この検索結果としては、ファイル「ａｕｄｉｏ１」に関して１分４０秒のスタートタイミングでラベル付けられるとともに、ファイル「ａｕｄｉｏ２」に関して、１０分２０秒のスタートタイミングでラベル付けされた、２０秒の継続時間をもった共通のオーディオ抽出部分で与えられる。
【０３０２】
テキストファイルにおける同一性によって抽出部分を検索することとは対照的に、デジタル署名を比較するステップで記録された抽出部分の同一性に関する疑義を払拭できる処理において、他のステップはない。デジタル署名の計算に用いる数学的アルゴリズムは、２つのオーディオファイルの間に共通の抽出部分が存在する場合において、ある共通の抽出部分が、その後にデジタル署名同士の間で検出されることを保証する。しかしながら、その逆は成り立たない。つまり、共通のオーディオ抽出部分に対応しないデジタル署名の共通の抽出部分を検出する可能性がある。
【０３０３】
検索結果に対して信頼度指数を利用できるようにするために、処理では、誤検出のエラーレートを計算することが可能な確率モデルを用いる。このモデルは、オーディオ抽出部分を表す、デジタル署名についてのＮ個の連続するデータ項目のグループを、ランダムな値をもち、かつランダムなオーディオ信号を表す、デジタル署名についてのＮ個の連続するデータ項目の別グループに適合（ｍａｔｃｈ  ｕｐ）させる確率を計算することにある。
【０３０４】
そして、デジタル署名についての、Ｎ個のデータをもった共通の抽出部分を検出する確率Ｐ（Ｎ）は、「Ｐ  ｅｘｐ（Ｎ）」の形式（ＰのＮ乗）で表現され、ここで、Ｐは、サイズ１の共通の抽出部分を引き出す確率である。実際には、いくつかのファジー論理状態が同時に使用されることを前提として、Ｐが１／２未満であり、従ってＰ（Ｎ）は、１／２ｅｘｐ（Ｎ）で上方に有界である。２１０を１０３に近似できるとすると、Ｎ個のデータ項目とされる共通の抽出部分について、その誤検出の確率を容易に推定できる。即ち、Ｐ（１０）＜１０−３，Ｐ（２０）＜１０−６，．．．となる。
【０３０５】
２つのオーディオファイルの比較に関連付けられることになる誤検出の推定数を評価するためには、この値Ｐ（Ｎ）に、デジタル署名の抽出部分についての開始位置のペアの総数、つまり、デジタル署名を比較するステップ中にテストされる総数を掛ける必要がある。ファイル「ａｕｄｉｏ１」のデジタル署名のデータ項目の数についての表記をＳ１とし、ファイル「ａｕｄｉｏ２」のデジタル署名のデータ項目の数についての表記をＳ２とすると、誤検出の推定数は、Ｐ（Ｎ）×Ｓ１×Ｓ２となる。
【０３０６】
上述のように、検索されるデジタル署名の共通の抽出部分のサイズが１増える毎に、この数は２で除算される（サイズが１０増えると１０００で除算される）。
【０３０７】
音楽の抽出部分を検出するアルゴリズムに磨きをかけるために、署名の共通の抽出部分の最小サイズは、５０データ項目に調整されており、これによって、１０−１５未満の誤検出の確率が保証される。この選択は、処理されるオーディオ信号の非ランダム性を考慮に入れたものであり、該信号は、音楽の場合に、多数の反復的な期間（リフレインなど）を含んでいる。このサイズは勿論、許容されるエラーレートを上げるか、あるいは下げるように、他の適用による要求に応じて適合される。
【０３０８】
この抽出部分の最小サイズに基づいて、プログラムは、検索される抽出部分の最小継続時間を、署名の各データ項目に関連付けられた期間の値の関数として逆方向に決定する（署名データの周波数の逆数）。
【０３０９】
デジタル署名周波数が２５Ｈｚの場合（１秒当たり２５データ項目）、プログラムは、最小継続時間２秒（５０×１／２５ｓ）のオーディオ抽出部分を検索することができる。デジタル署名周波数が５Ｈｚの場合（１秒当たり５データ項目）、プログラムは、最小継続時間１０秒（５０×１／５ｓ）のオーディオ抽出部分を検索することができる。デジタル署名周波数が１Ｈｚの場合（１秒当たり１データ項目）、プログラムは、最小継続時間５０秒のオーディオ抽出部分を検索することができる。
【０３１０】
実際上、それは、検索されるオーディオ抽出部分の最小継続時間の閾値を固定する適用である。広告のモニタリングへの適用の場合、必要条件は５秒のテレビ又はラジオのスポット広告についての抽出部分を検出することである。音楽のタイトル認識への適用の場合、必要条件は１５秒程度の抽出部分を検出することである。テレビ番組（映画、連続番組など）の認識への適用の場合、必要条件は１分程度の抽出部分を検出することである。
【０３１１】
さらに、オーディオ、ビデオ、又はその他のファイルへの適用、つまり、第１ファイル及び第２ファイルがデジタル化された信号のサンプルファイルである場合への適用において、本発明の範囲内の方法は、好ましくは、例えば、サブバンドフィルタリングによりデータの前処理をするステップを有し、第１ファイルと第２ファイルとの間の異なるイコライゼイション（均等化）の効果を制限するために、ノイズ基準よりも高いレベルの信号部分に関連付けられたデータを考慮することが示される。
【０３１２】
さらに、本方法は、好ましくは、第１ファイル及び第２ファイルのそれぞれの検索速度における相違を許容するように、第１ファイル及び第２ファイルのパケットの相対的なサイズを調整することによって、検索結果を一元管理（ｃｏｎｓｏｌｉｄａｔｅ）するステップを有利に提供する。
【０３１３】
そして、第１ファイル及び第２ファイルの少なくとも１つがデータストリームであってもよく、この適用において、共通の抽出部分を検索する方法がリアルタイムで実行されることが示される。
【０３１４】
Ｃ＋＋言語で記述された具体的なプログラムは、共通の抽出部分の検索を、３２ビットＷｉｎｄｏｗｓ（登録商標）オペレーティングシステムが搭載されたマイクロコンピュータで実行するように開発される。このプログラムは比較される２つのファイルを選択し、そこに発見される共通の抽出部分の最小サイズを規定し、その後に検索を促すように提示する。
【０３１５】
検索を促す場合に、プログラムが、好ましくは実行モニタリングウィンドウを表示する。このウィンドウは、検索開始からの経過時間並びに全継続時間及び検索速度の推定値を表示する。また、検索の継続時間が長すぎると判明した場合には、その検索を放棄することもできる。検索は、共通の抽出部分が見つかると直ちに中断される。そして、発見された抽出部分のサイズ及び各ファイルにおける位置が表示される。プログラムは、所定の命令に従ってファイルの分析を行う。その本質は、ファイルにおける共通の抽出部分がとり得る開始位置の各ペアをテストすることである。
【０３１６】
検索アルゴリズムの実装について、その説明を以下に記載する。検索は、ファイルに共通な他の抽出部分を見い出すために再開されてもよいことが示される。この場合に、検索は、最後に発見された共通の抽出部分についての開始位置のペアから再開され、ファイルの分析についての所定の順序に従って行われる。この検索は、ファイルが完全に分析されると終了する。そして、ファイルに共通の抽出部分が存在しないこと、又はファイルに共通の他の抽出部分が存在しないことを、必要に応じて示すために、停止条件が表示される。
【０３１７】
プログラムは、検索を実行するために２つのアルゴリズム、即ち、従来の検索アルゴリズムと、本発明の範囲内でのアルゴリズムを、自らの判断で使用することを提案する。
【０３１８】
従って、プログラムは、２つのアルゴリズムのパフォーマンスを、１台のコンピュータ上で比較することを可能とし、検索される共通の抽出部分の最小サイズや、ファイルのサイズ、ファイルの性質、その他に関して、あらゆる検索設定に対してパフォーマンスを比較することができる。
【０３１９】
パフォーマンスの評価基準は、アルゴリズムの実行の迅速性である。実行モニタリングウィンドウにより、検索を完了するまでの実行期間、検索速度などの推定を回復することができる。
【０３２０】
従来のアルゴリズムにおいて、検索速度が実質的に一定であって、発見される共通の抽出部分の最小サイズには依存しないことが明らかである。これは、コンピュータで実行される、１秒当たりのバイナリデータ（バイト）の比較演算回数として表される。その値は常にマイクロプロセッサのクロック周波数未満である。
【０３２１】
一方、本発明の範囲内でのアルゴリズムにおいて、検索速度は、発見される共通の抽出部分の最小サイズの関数として変化する。これは、１秒当たりのバイナリデータ（バイト）の比較演算回数の推定値により表され、従来のアルゴリズムが用いられた際のコンピュータによって行われる。従って、発見される共通の抽出部分の最小サイズが増加するほど、速度は大きくなる。その値は、マイクロプロセッサのクロック周波数の値を超越し得る。
【０３２２】
図１９Ａには、２つのテキストファイル間の共通の抽出部分を、同一性に基づいて検索するための、本発明の範囲内でのコンピュータプログラムにおけるマン・マシンインターフェースの枠内で、ダイアログボックスの画面コピーを示す。また、図１９Ｂは、図１９Ａの画面上で定義された検索の進行状況を示す画面コピーを示す。この検索にかかる時間は２秒であり、その際、ファイルサイズがそれぞれ８５３９０バイトと２１３２７５バイトであったことを記しておく（図１９Ａ）。
【０３２３】
図１９Ｃには、「．ＷＡＶ」形式での、２つのオーディオファイル間における共通の抽出部分を検索するための画面コピーを示す。上記のように、この場合、好ましくは、同一性に基づく検索ではなく、そのパラメータ（特に上記信頼度指数は該パラメータから派生する）が本ダイアログボックス内で決定される検索である（図１９Ｃの上部）。ここでは、一方で１時間のラジオ録音（パリのＦＭで１０３．９ＭＨｚ）が利用可能とされ、他方では２４４個の録音ベース（音楽やスポット広告など）が利用可能である。検索において、ラジオ録音のベースに８３個の共通の抽出部分が検出された。
【０３２４】
最後に、図１９Ｄにはデジタル署名ファイルの生成用の画面コピーを示すが、該ファイルは、２時間のラジオ録音（パリでの１０３．９ＭＨｚ）に対応するオーディオ信号の、サンプリング周波数２２．０５０ｋＨｚでのリアルタイム処理に基づいて形成されたものである。署名の精度（ここでは２、５、又は２５Ｈｚのうち、５Ｈｚを選択）が、曲の１秒当たりの、デジタル署名のデータ項目数に対応することを示している。このパラメータにより、特に、共通の抽出部分の検出を開始する瞬間の精度を高めることが可能となる。
【０３２５】
図１８には、特に、第１ファイル及び第２ファイルの一方を、該第１ファイル及び第２ファイルの他方に対して、遠隔でアップデートするための、本発明の範囲内における別の適用を示す。この目的のために、以下のものを備えたコンピュータ設備が提供される。
・第１ファイルの格納に好適な第１コンピュータエンティティＰＣ１
・第２ファイルの格納に好適な第２コンピュータエンティティＰＣ２
・第１コンピュータエンティティＰＣ１と第２コンピュータエンティティＰＣ２との間の通信手段ＣＯＭ
【０３２６】
これらのエンティティ（ｅｎｔｉｔｙ）のうちの少なくとも１つ（ＰＣ１及び／又はＰＣ２）は、メモリ（それぞれＭＥＭ１及び／又はＭＥＭ２）を備えており、これらのメモリは、既述のように、第１ファイルと第２ファイルとの間の、共通の抽出部分を検索するためのコンピュータプログラム製品の格納に好適とされる。
【０３２７】
これに関して、本発明はこのような装置をも対象としている。
【０３２８】
ここで、コンピュータプログラム製品を格納するエンティティは、第１ファイルと第２ファイルとを比較しつつ、第１ファイル及び第２ファイルの一方についての、第１ファイル及び第２ファイルの他方に対する遠隔アップデートを実行する能力がある。従って、エンティティの１つは、特定の期間（週、月など）をもって、新たなデータのエントリー又はその他の改変によって、コンピュータファイルを変更することがある。もう一方のコンピュータエンティティは、この場合に、第１のエンティティからのファイル出力の格納及び定期的なアップデートを行うことが必要とされ、これらのファイルを受信する。
【０３２９】
アップデート対象のファイルを、第１のエンティティから第２のエンティティへと完全に転送するのではなく、第１のエンティティは、本発明の範囲内の方法により、同じファイルの２つのバージョンの間で共通するデータ抽出部分をラベル付けする。この２つのバージョンとは、データの追加又は削除により改変された新しいバージョン、及び、以前に他方のエンティティに転送され、かつ第１のエンティティがローカルにバックアップを保存していた古いバージョンである。この本発明の範囲内での比較により、ファイルの新しいバージョンと古いバージョンと間で差分ファイルを生成することが可能となる。この差分ファイルは、共通のデータ抽出部分の位置及びサイズに関する情報をもっており、新しいバージョンのファイルを、古いバージョンのファイルに基づいて部分的に再構成するために用いられ、そして、差分ファイルは、新しいバージョンのファイルを完全に再構成するために用いる必要のある補完データを含む。ファイルのアップデートについては、差分ファイルを第２のエンティティに対して送信することによって行われ、その次に、古いバージョンのファイルと前記差分ファイルとを組み合わせることによって、新しいバージョンのファイルを再構成するためのローカルな処理を第２のエンティティに適用することで行われる。
【０３３０】
本発明の範囲内の方法を適用することによって、前記した差分ファイルの生成に要する処理時間を著しく低減させることができ、転送されるデータのボリューム（延いては転送コストと時間）を低減させて、巨大なコンピュータファイル、特に、アカウント、銀行取引などに関するデータを含むファイルであって僅かな修正しか受けていないファイルについての遠隔アップデートを行うことができる。
【０３３１】
コンピュータエンティティは、第１ファイルと第２ファイルとの間の１つ以上の共通の抽出部分を検索するために、第１ファイル及び第２ファイルを（少なくとも瞬間的に）格納するメモリを備えた、如何なるコンピュータ装置（コンピュータ、サーバー、その他）の形態をとってもよい。そして、これらは上述の種類のコンピュータプログラム製品の命令を格納するメモリをも備えている。この点について、本発明はコンピュータ装置をも対象としている。
【０３３２】
本発明はまた、コンピュータプログラム製品を対象としており、該製品は、上記のコンピュータ装置などのコンピュータの中央装置のメモリ、又は該中央装置の読取部と協働するものとされたリムーバブル（着脱自在な）メディアに格納されるようになっている。このプログラム製品は、上述した本発明の範囲内での処理ステップについて、その全て又は一部を実行するための命令を含む。
【０３３３】
また、本発明は、第１ファイル及び第２ファイルに共通する、１つ以上の抽出部分の検索に用いるためのデータ構造を対象としている。このデータ構造は、第１ファイルを表現するものであり、その前提として、該データ構造は、デジタル署名を形成するために、本発明の範囲内での処理を適用することで得られる。特に、このデータ構造は、上記方法のステップａ）及びｂ）を実行することにより得られ、該データ構造には、第１ファイルのアドレスを識別し、各アドレスに対して、状態「真」（１）、「偽」（０）、及び「不定」（？）のうち、１つのファジー論理状態が割り当てられた一連のアドレスが含まれる。
【図面の簡単な説明】
【０３３４】
【図１】詳細検索の主要なステップの概要を示す図である。
【図２Ａ】２つのデータファイルを比較するために、２次元配列のレイアウトを、これらの２つのファイルのデータについてのアドレスの関数として図式的に示す図である。
【図２Ｂ】２つのテキストファイル「Ｄｅｓ  ｍｏｕｔｏｎｓ」及び「Ｕｎ  ｍｏｕｔｏｎ」の同一性を比較するために、２次元配列を図式的に示す図である。
【図３】インデックス比が４に等しい場合において、デジタル署名の形成後に得られる、データのアドレスとデータブロックのアドレスとの間の対応関係を示す図である。
【図４Ａ】インデックス比が２とされる場合に、２つのテキストファイル「Ｄｅｓ  ｍｏｕｔｏｎｓ」及び「Ｕｎ  ｍｏｕｔｏｎ」のデジタル署名を比較するために、２次元配列を示す図である。
【図４Ｂ】同一性の詳細比較、つまり、原則的には図４Ａの２つのテキストファイル「Ｄｅｓ  ｍｏｕｔｏｎｓ」及び「Ｕｎ  ｍｏｕｔｏｎ」の粗い検索のステップに続いてなされる詳細比較のために２次元配列を示す図である。
【図５Ａ】２値論理の「ＯＲ」関数の真理値表を示す図である。
【図５Ｂ】２値論理の「ＡＮＤ」関数の真理値表を示す図である。
【図５Ｃ】２ビットＢ０及びＢ１についてのファジー状態をコード化するための配列表を示す図である。
【図５Ｄ】（図５Ｃのファジー状態のコード化規則を適用することによる）ファジー論理の「ＯＲ」関数の真理値表を示す図である。
【図５Ｅ】（図５Ｃのファジー状態のコード化規則を適用することによる）ファジー論理の「ＡＮＤ」関数の真理値表を示す図である。
【図６Ａ】ファイルデータのアドレスの関数としてファイルデータに関連付けられた２値論理状態の値を示す図である。
【図６Ｂ】ファイルデータのアドレスの関数としてファイルデータに関連付けられた２値論理状態の値、及び同アドレスの関数として、大域的にこれらのデータに関連付けられたファジー論理状態の値（「ＯＲ」のファジー論理関数が、ここでは、データの各ブロックにおいて、ブロックの各データ項目に関連付けられた論理状態間に適用される）を示す図である。
【図７Ａ】テキストファイルの例に基づいて２値状態及びファジー状態を決定するための配列表を示す図である。これらの例において、２値状態が以下の規則に基づいて決定される。・文字のＡＳＣＩＩコードの整数値が厳密に１１１未満の場合は０。・文字のＡＳＣＩＩコードの整数値が１１１以上の場合は１。本図では、インデックス比の各値に対して、テキストファイル「Ｌａ  ｔｏｒｔｕｅ」に関連する各種のファジー状態を表す配列を示す。
【図７Ｂ】テキストファイルの例に基づいて２値状態及びファジー状態を決定するための配列表を示す図である。これらの例において、２値状態が以下の規則に基づいて決定される。・文字のＡＳＣＩＩコードの整数値が厳密に１１１未満の場合は０。・文字のＡＳＣＩＩコードの整数値が１１１以上の場合は１。本図では、インデックス比が２の場合に、ファイル「Ｌｅ  ｌｉｅｖｒｅ」及び「Ｌａ  ｔｏｒｔｕｅ」のそれぞれに関連付けられたデジタル署名を与える配列を示す。
【図７Ｃ】共通の抽出部分を検索するために、図７Ｂのデジタル署名を比較する配置を示す図である。
【図８Ａ】各種の位相を有する余弦関数を、変数ｔ／Ｔの関数（Ｔは関数の周期である。）として示す図である。
【図８Ｂ】余弦関数の符号に基づいて得られた２値状態間での、論理の組み合わせについて、セグメント［ｔ／Ｔ，ｔ／Ｔ＋ｐ］に属する全セットの値への適用によって、変数ｔ／Ｔの値と個別に関連付けられたファジー論理状態の決定を示す図である。
【図８Ｃ】余弦関数の符号に基づいて得られた２値状態間での、論理の組み合わせについて、セグメント［ｔ／Ｔ，ｔ／Ｔ＋ｐ］に属する全セットの値への適用によって、変数ｔ／Ｔの各値に対して決定されるファジー論理状態の変化を示す図である。
【図９Ａ】余弦関数に関連付けられた周波数ｆ及びセグメントのサイズｐの関数として、ファジー状態「１」を引き出す確率を示す図である。
【図９Ｂ】余弦関数に関連付けられた周波数ｆ及びセグメントのサイズｐの関数として、ファジー状態「０」を引き出す確率を示す図である。
【図９Ｃ】余弦関数に関連付けられた周波数ｆ及びセグメントのサイズｐの関数として、ファジー状態「？」を引き出す確率を示す図である。
【図１０】テキストファイル「Ｌｅ  ｌｉｅｖｒｅ」のサンプルｆｎによる値の補間で得られた関数ｆ（ｔ／Ｔｅ）の変形例を示す図である（破線の曲線は曲線ｆ（ｔ／Ｔｅ）の構成に対するサンプルｆ４の寄与を示す）。
【図１１】インデックス比が３の場合に、周波数ｆの関数として、ファジー状態「１」（又はファジー状態「０」）を引き出す確率を示す図である。
【図１２Ａ】インデックス比が２の場合に、周波数ｆの関数として、ファジー状態「１」（又はファジー状態「０」）を引き出す確率を示す図である。
【図１２Ｂ】インデックス比がｎ（ｎ＞２）の場合に、周波数ｆの関数としての、ファジー状態「１」（又はファジー状態「０」）を引き出す確率を示す図である。
【図１３】デジタル署名ｓｎ／ｋを得るために実行される、各種のサンプリング及びフィルタリングのステップを図式的に示す図である。
【図１４】ｆ／Ｆｅの関数として、Ｋのいくつかの値について、（中央サンプルを中心とするＫ個のサンプルの平均値の組み込みをとり入れた）フィルタリング関数Ｆｉｌｔｅｒ（Ｋ，ｆ）＝Σａｖｇ（Ｋ，ｆ）の形状を、絶対値で示す図である。
【図１５】詳細な説明に記載したｉｎｔｅｒｖパラメータ値のいくつかについて、インデックス比ｋ＝５に調整されたデフォルトのデジタルフィルタの周波数応答を示す図である。
【図１６Ａ】サンプリングされたサンプルｆｎのアドレスと、デジタルフィルタが適用されたサンプルｒｎのアドレスと、（フィルタ処理されたサンプルｒｎのファジー論理における「ＯＲ」の）組み合わせによって得られたデジタル署名のブロックのアドレスと、を示す図である。
【図１６Ｂ】データファイル内で検索される抽出部分ＥＸＴのデータにより、デジタル署名のデータの計算に関連付けられたデータブロックの重複の条件を示す図である。
【図１７】実行される比較回数を、インデックス比ｋの関数として示す図であり、サイズが１００キロバイトの２つのファイル間における、１０００文字の最小サイズの共通する抽出部分の検索例について、粗い検索（Ｔｏｔａｌ１）、その後の詳細検索（Ｔｏｔａｌ２）、及びこの２つの検索の両方（Ｔｏｔａｌ３）の場合を示す図である。
【図１８】本発明の有利な適用を実施するために、コンピュータファイルを遠隔でアップデートする際に通信するコンピュータエンティティのシステムを示す図である。
【図１９Ａ】本発明の範囲内における、テキストファイルに共通な抽出部分を検索するための、コンピュータプログラムのマン・マシンインターフェースの枠内でのダイアログボックスの画面コピーを示す図である。
【図１９Ｂ】検索の進行状況を表示する画面コピーを示す図である。
【図１９Ｃ】２つのオーディオファイルに共通な抽出部分の検索用の画面コピーを示す図である。
【図１９Ｄ】オーディオ信号のリアルタイム処理に基づいて形成されるデジタル署名ファイルの生成用の画面コピーを示す図である。
【図１】
2007531948.tif 000037
【図２Ａ】
2007531948.tif 000038
【図２Ｂ】
2007531948.tif 000039
【図３】
2007531948.tif 000040
【図４Ａ】
2007531948.tif 000041
【図４Ｂ】
2007531948.tif 000042
【図５Ａ】
2007531948.tif 000043
【図５Ｂ】
2007531948.tif 000044
【図５Ｃ】
2007531948.tif 000045
【図５Ｄ】
2007531948.tif 000046
【図５Ｅ】
2007531948.tif 000047
【図６Ａ】
2007531948.tif 000048
【図６Ｂ】
2007531948.tif 000049
【図７Ａ】
2007531948.tif 000050
【図７Ｂ】
2007531948.tif 000051
【図７Ｃ】
2007531948.tif 000052
【図８Ａ】
2007531948.tif 000053
【図８Ｂ】
2007531948.tif 000054
【図８Ｃ】
2007531948.tif 000055
【図９Ａ】
2007531948.tif 000056
【図９Ｂ】
2007531948.tif 000057
【図９Ｃ】
2007531948.tif 000058
【図１０】
2007531948.tif 000059
【図１１】
2007531948.tif 000060
【図１２Ａ】
2007531948.tif 000061
【図１２Ｂ】
2007531948.tif 000062
【図１３】
2007531948.tif 000063
【図１４】
2007531948.tif 000064
【図１５】
2007531948.tif 000065
【図１６Ａ】
2007531948.tif 000066
【図１６Ｂ】
2007531948.tif 000067
【図１７】
2007531948.tif 000068
【図１８】
2007531948.tif 000069
【図１９Ａ】
2007531948.tif 000070
【図１９Ｂ】
2007531948.tif 000071
【図１９Ｃ】
2007531948.tif 000072
【図１９Ｄ】
2007531948.tif 000073
【国際調査報告】
2007531948.tif 000074
2007531948.tif 000075
2007531948.tif 000076
2007531948.tif 000077