(57)【要約】本発明は、検索を実行するために必要とされたメモリリソースを最小化しつつ、効率的な態様で検索を実行するための技術を説明する。本発明の技術によると、クエリエレメントがエレメントのセットに含まれるかどうかを判定するために必要とされた比較数は、クエリエレメントの長さに比例し、エレメントのセットにおけるエレメントの数から独立する。本発明の方法は、エレメントのセットにおけるエレメントを識別する情報に基づいてデータ構造を構築するステップと、クエリエレメントを識別する情報を受け取るステップと、クエリエレメントがエレメントのセットに含まれるかどうかを判定するために必要とされた比較の数が該クエリエレメントの長さに比例し、該エレメントのセットのエレメントの数から独立しているように、クエリエレメントがエレメントのセットに含まれているかどうかを判定するためにデータ構造を使用するステップとを含む。【選択図】図２
2004531789.tif 000002
【特許請求の範囲】
【請求項１】
クエリエレメントがエレメントのセットに含まれるかどうかを判定するコンピュータにインプリメントされた方法であって、
該エレメントのセットにおけるエレメントを識別する情報に基づいてデータ構造を構築するステップと、
該クエリエレメントを識別する情報を受け取るステップと、
該クエリエレメントが該エレメントのセットに含まれるかどうかを判定するために必要とされた比較の数が該クエリエレメントの長さに比例し、該エレメントのセットのエレメントの数から独立しているように、該クエリエレメントが該エレメントのセットに含まれているかどうかを判定するために該データ構造を使用するステップと
を含む、クエリエレメントがエレメントのセットに含まれるかどうかを判定するコンピュータにインプリメントされた方法。
【請求項２】
前記クエリエレメントは、長さ「ｑ」であり、該クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために、多くとも「ｑ」文字の比較が必要とされる、請求項１に記載の方法。
【請求項３】
前記エレメントのセットは、「ｍ」文字の文字セットを有する領域Σからのエレメントを含み、「Ｚ」は、領域Σのエレメントの最大可能長さであり、「Ｙ」は、１≦Ｙ≦Ｚであるように該エレメントのセットの最長のエレメントの長さであり、
前記データ構造を構築するステップは、ルートメモリ構造によってヘッダーが付けられた複数のメモリ構造を含む該データ構造を構築するステップを含み、該複数のメモリ構造における各メモリ構造は、第１のメモリ位置および「ｍ」のメモリ位置のアレイを含む、請求項１に記載の方法。
【請求項４】
前記データ構造は、全体で（Ｙ＋１）レベルを含み、
該データ構造の各々のメモリ構造は、レベルＬ（０≦Ｌ≦Ｙ）に属し、特定のメモリ構造に対するレベルは、該メモリ構造の数を表し、前記ルートメモリ構造から開始し、該ルートメモリ構造は、該特定のメモリ構造に到達するように移動される必要があり、該ルートメモリ構造はレベル０に属する、請求項３に記載の方法。
【請求項５】
前記エレメントのセットのエレメントを識別する情報に基づいて前記データ構造を構築するステップは、ｉ＝１で開始する該エレメントのセットの各エレメント「Ｒ」（あるｆ≦Ｙ、各ｃｉ（１≦ｉ≦ｆ）に対して、Ｒ＝ｃ１ｃ２．．．ｃｆである）に対して、
（ａ）レベル「（ｉ−１）」でメモリ構造を選択するステップと、
（ｂ）該現在選択されたメモリ構造のメモリ位置のアレイにおける文字ｃｉに対応するメモリ位置が前記データベース内で別のメモリ構造を参照しない場合、該現在選択されたメモリ構造のメモリ位置のアレイにおける文字ｃｉに対応するメモリ位置にレベル「ｉ」で新しいメモリ構造のアドレスを格納するステップと、
（ｃ）該レベル「ｉ」でメモリ構造を選択するステップであって、該メモリ構造のアドレスは、該現在選択されたメモリ構造のメモリ位置のアレイにおける文字ｃｉに対応するメモリ位置に格納される、該レベル「ｉ」におけるメモリ構造を選択するステップと、
（ｄ）「ｉ」が「ｆ」に等しい場合に、ステップ（ｃ）において選択された該メモリ構造の第１のメモリ位置にエレメント「Ｒ」への参照を格納するステップと、
（ｅ）「ｉ」の値を１だけインクリメントするステップと、
（ｆ）「ｉ」≦「ｆ」である各ｃｉに対してステップ（ｂ）、（ｃ）、（ｄ）、および（ｅ）を繰り返すステップと
を含む、請求項４に記載の方法。
【請求項６】
前記クエリエレメントを識別する情報を受け取るステップは、クエリエレメントｋ（あるｑ≦Ｚに対して、ｋ＝ｃ１ｃ２．．．ｃｑである）を識別する情報を受け取るステップを含み、
該クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために前記データ構造を使用するステップは、１≦ｉ≦ｆである、ｉ＝１で開始する、ｋの各ｃｉに対して、
（ａ）レベル「（ｉ−１）」で前記データベースのメモリ構造を選択するステップと、
（ｂ）該現在選択されたメモリ構造のメモリ位置のアレイにおける文字ｃｉに対応するメモリ位置が、前記データベース内で別のメモリ構造を参照しない場合、該クエリエレメントが該エレメントのセットに含まれないことを示す信号を出力するステップと、
（ｃ）該現在選択されたメモリ構造のメモリ位置のアレイにおける文字ｃｉに対応するメモリ位置が、レベル「ｉ」の該データベースのメモリ構造のアドレスを格納する場合、該レベル「ｉ」でメモリ構造のアドレスが格納される、該レベル「ｉ」のメモリ構造を選択するステップと、
（ｄ）該「ｉ」の値を１だけインクリメントするステップと、
（ｅ）「ｉ」≦「ｑ」の間、ステップ（ｂ）、（ｃ）、および（ｄ）を繰り返すステップであって、該クエリエレメントは、該エレメントのセットに含まれないことを示す信号は、出力されていない、ステップとを含み、
該クエリエレメントが該エレメントのセットに含まれないことを示す信号が出力されていない場合に、
ステップ（ｃ）において選択された該メモリ構造の該第１のメモリ位置が該クエリエレメントを参照するかどうかを判定するステップと、
ステップ（ｃ）において選択された該メモリ構造の第１のメモリ位置が該クエリエレメントを参照する場合、該クエリエレメントが該エレメントのセットに含まれることを示す信号を出力し、他の場合は、該クエリエレメントが該エレメントのセットに含まれないことを示す信号を出力する、請求項５に記載の方法。
【請求項７】
前記エレメントのセットにおけるエレメントを識別する情報に基づいて前記データ構造を構築するステップは、前記エレメントのセットにおける各々のエレメント「Ｒ」（あるｆ≦Ｙ、各ｃｉに対するＲ＝ｃ１ｃ２．．．ｃｆである）に対して、各文字ｃｉは、領域Σの文字セットに属し、エレメントＲにおける各文字の位置およびアイデンティティを示す情報を前記データベースに格納するステップを含む、請求項３に記載の方法。
【請求項８】
前記クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために前記データ構造を使用するステップは、該クエリエレメントが、前記データベースによって格納された情報、ならびに、文字および該クエリエレメントにおけるそれらの位置を識別する情報に基づいてエレメントのセットに含まれるかどうかを判定するステップを含む、請求項７に記載の方法。
【請求項９】
前記エレメントのセットにおけるエレメントを識別する情報に基づいて前記データ構造を構築するステップは、該エレメントのセットにおける各エレメント「Ｒ」に対して、
（ａ）前記選択されたメモリ構造として該データ構造の前記ルートメモリ構造を選択するステップと、
（ｂ）該エレメントＲの第１の文字を選択するステップと、
（ｃ）該選択されたメモリ構造のメモリ位置のアレイにおいて選択された文字に対応するメモリ位置が、該データ構造における別のメモリ構造を参照しない場合、該現在選択されたメモリ構造のメモリ位置のアレイにおいて該選択された文字に対応する該メモリ位置に新しいメモリ構造のアドレスを格納するステップと、
（ｄ）該メモリ構造のアドレスが、該選択されたメモリ構造のメモリ位置のアレイにおいて該選択された文字に対応する該メモリ位置に該選択されたメモリ構造として格納される該メモリ構造を選択するステップと、
（ｅ）該選択された文字がエレメントＲの最後の文字である場合、ステップ（ｄ）において選択された該メモリ構造の前記第１のメモリ位置においてエレメントＲへの参照を格納するステップと、
他の場合では、エレメントＲの次の文字を選択し、ステップ（ｃ）、（ｄ）、および（ｅ）を繰り返すステップと
を含む、請求項３に記載の方法。
【請求項１０】
前記クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために前記データ構造を使用するステップは、
（ａ）前記選択されたメモリ構造として該データ構造の前記ルートメモリ構造を選択するステップと、
（ｂ）該クエリエレメントの第１の文字を選択するステップと、
（ｃ）該選択されたメモリ構造のメモリ位置のアレイにおいて選択された文字に対応するメモリ位置が、該データ構造における別のメモリ構造を参照しない場合、該クエリエレメントが該エレメントのセットに含まれないことを示す信号を出力するステップと、
他の場合では、該メモリ構造のアドレスが該選択されたメモリエレメントとして格納される該メモリ構造を選択するステップと、
（ｄ）該選択された文字が該クエリエレメントの最後の文字である場合、
ステップ（ｃ）で選択された、該メモリ構造の第１のメモリ位置が該クエリエレメントを参照するかどうかを判定するステップと、
ステップ（ｃ）において選択された該メモリ構造の第１のメモリ位置が該クエリエレメントを参照する場合、該クエリエレメントが該エレメントのセットに含まれることを示す信号を出力し、他の場合は、該クエリエレメントが該エレメントのセットに含まれないことを示す信号を出力するステップと、
他の場合では、該クエリエレメントの次の文字を選択し、ステップ（ｃ）および（ｄ）を繰り返すステップと
を含む、請求項９に記載の方法。
【請求項１１】
前記データ構造のサイズは、前記エレメントのセットのエレメントの数から独立している、請求項１に記載の方法。
【請求項１２】
前記エレメントのセットは、文字「ｍ」の文字セットを有する領域Σからのエレメントを含み、「Ｚ」は、領域Σのエレメントの最大可能長さであり、
前記データ構造は、「Ｚ」メモリ構造を含み、各メモリ構造は、「ｍ」スロットを含み、各スロットは、第１のメモリ位置およびメモリ位置のアレイを含み、メモリ位置の各アレイは、「（ｍ＋１）」メモリ位置を含む、請求項１１に記載の方法。
【請求項１３】
前記エレメントのセットにおけるエレメントを識別する情報に基づく前記データ構造を構築するステップは、
各メモリ構造における各スロットのメモリ位置のアレイにおける前記第１のメモリ位置およびメモリ位置をゼロ値に初期化するステップと、
該エレメントのセットにおける各エレメント「Ｒ」（あるｆ≦Ｙ、各ｃｉ（１≦ｉ≦ｆ）に対してＲ＝ｃ１ｃ２．．．ｃｆである）に対して、
「ｉ」＜「ｆ」である場合、メモリ構造ｉのｃｉに対応するスロットのメモリ位置のアレイにおける文字ｃｉ＋１に対応するメモリ位置にゼロでない値を格納するステップと、
「ｉ」＝「ｆ」である場合、メモリ構造ｉのｃｉに対応するスロットのメモリ位置のアレイの内の（ｍ＋１）番目のメモリ位置にゼロでない値を格納するステップと、
メモリ構造ｉのｃｉに対応する該スロットの第１のメモリ位置にエレメント「Ｒ」への参照を格納するステップと
を含む、請求項１２に記載の方法。
【請求項１４】
前記クエリエレメントを識別する情報を受け取るステップは、クエリエレメント「ｋ」（あるｑ≦Ｚに対してｋ＝ｃ１ｃ２．．．ｃｑである）を識別する情報を受け取るステップを含み、
該クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために前記データ構造を使用するステップは、ｋの各ｃ１に対して
「ｉ」＜「ｑ」である場合、ゼロでない値がメモリ構造ｉのｃｉに対応する前記スロットのメモリ位置のアレイにおける文字ｃｉ＋１に対応するメモリ位置に格納される場合、
「ｉ」が「ｑ」に等しい場合、ゼロでない値がメモリ構造ｉのｃｉに対応する該スロットのメモリ位置のアレイにおける（ｍ＋１）番目のメモリ位置に格納され、メモリ構造ｉのｃｉに対応する該スロットの前記第１のメモリ位置が該クエリエレメントを参照する場合、
該クエリエレメントが、前記エレメントのセットに含まれることを示す信号を出力するステップを含む、請求項１３に記載の方法。
【請求項１５】
前記クエリエレメントを識別する情報を受け取るステップは、クエリエレメント「ｋ」（あるｑ≦Ｚに対してｋ＝ｃ１ｃ２．．．ｃｑである）を識別する情報を受け取るステップを含み、
該クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために前記データ構造を使用するステップは、ｋの任意のｃｉに対して
「ｉ」が「ｑ」に等しい場合、ゼロでない値がメモリ構造ｉのｃｉに対応する前記スロットのメモリ位置のアレイにおける（ｍ＋１）番目のメモリ位置に格納されるか、またはメモリ構造ｉのｃｉに対応するスロットの前記第１のメモリ位置が該クエリエレメントを参照しない場合、
「ｉ」＜「ｑ」である場合、ゼロでない値が、メモリ構造ｉのｃｉに対応する該スロットのメモリ位置のアレイにおける文字ｃｉ＋１に対応するメモリ位置に格納される場合、
該クエリエレメントが該エレメントのセットに含まれないことを示す信号を出力するステップを含む、請求項１３に記載の方法。
【請求項１６】
クエリエレメントがエレメントのセットに含まれるかどうかを判定するためのシステムであって、
プロセッサと、
該プロセッサに接続され、該プロセッサによって実行可能な複数のコードモジュールを格納するために構成されたメモリとを含み、該複数のコードモジュールは、
該エレメントのセットのエレメントを識別する情報に基づいてデータ構造を構築するためのコードモジュールと、
該クエリエレメントを識別する情報を受け取るためのコードモジュールと、
該クエリエレメントが該エレメントのセットに含まれるかどうかを判定するために必要とされた比較の数が該クエリエレメントの長さに比例し、該エレメントのセットのエレメントの数から独立しているように、該クエリエレメントが該エレメントのセットに含まれるかどうかを判定するために該データ構造を用いるためのコードモジュールと
を含む、クエリエレメントがエレメントのセットに含まれるかどうかを判定するためのシステム。
【請求項１７】
前記クエリエレメントは、長さ「ｑ」であり、該クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために、多くとも「ｑ」文字の比較が必要とされる、請求項１６に記載のシステム。
【請求項１８】
前記エレメントのセットは、「ｍ」文字の文字セットを有する領域Σからのエレメントを含み、「Ｚ」は、領域Σのエレメントの最大可能長さであり、「Ｙ」は、１≦Ｙ≦Ｚであるように該エレメントのセットの最長のエレメントの長さであり、
前記データ構造を構築するためのコードモジュールは、ルートメモリ構造によってヘッダーが付けられた複数のメモリ構造を含む該データ構造を構築するためのコードモジュールを含み、該複数のメモリ構造における各メモリ構造は、第１のメモリ位置および「ｍ」のメモリ位置のアレイを含む、請求項１６に記載のシステム。
【請求項１９】
前記データ構造は、全体で（Ｙ＋１）レベルを含み、
該データ構造の各々のメモリ構造は、レベルＬ（０≦Ｌ≦Ｙ）に属し、特定のメモリ構造に対するレベルは、該メモリ構造の数を表し、前記ルートメモリ構造から開始し、該ルートメモリ構造は、該特定のメモリ構造に到達するように移動される必要があり、該ルートメモリ構造はレベル０に属する、請求項１８に記載のシステム。
【請求項２０】
前記エレメントのセットにおけるエレメントを識別する情報に基づく前記データ構造を構築するためのコードモジュールは、ｉ＝１で開始する該エレメントのセットの各エレメント「Ｒ」（あるｆ≦Ｙ、各ｃｉ（１≦ｉ≦ｆ）に対して、Ｒ＝ｃ１ｃ２．．．ｃｆである）に対して、
（ａ）レベル「（ｉ−１）」でメモリ構造を選択するためのコードモジュールと、
（ｂ）該現在選択されたメモリ構造のメモリ位置のアレイにおける文字ｃｉに対応するメモリ位置が、前記データベース内で別のメモリ構造を参照しない場合に、該選択されたメモリ構造のメモリ位置のアレイにおける文字ｃｉに対応するメモリ位置にレベル「ｉ」で新しいメモリ構造のアドレスを格納するためのコードモジュールと、
（ｃ）該レベル「ｉ」でメモリ構造を選択するためのコードモジュールであって、該メモリ構造のアドレスは、該現在選択されたメモリ構造のメモリ位置のアレイにおける文字ｃｉに対応するメモリ位置に格納される、該レベル「ｉ」でメモリ構造を選択するためのコードモジュールと、
（ｄ）「ｉ」が「ｆ」に等しい場合、ステップ（ｃ）において選択された該メモリ構造の第１のメモリ位置にエレメント「Ｒ」への参照を格納するためのコードモジュールと、
（ｅ）「ｉ」の値を１だけインクリメントするためのコードモジュールと、
（ｆ）「ｉ」≦「ｆ」である各ｃｉに対してステップ（ｂ）、（ｃ）、（ｄ）、および（ｅ）を繰り返すためのコードモジュールと
を含む、請求項１９に記載のシステム。
【請求項２１】
前記クエリエレメントを識別する情報を受け取るためのコードモジュールは、
クエリエレメントｋ（あるｑ≦Ｚに対して、ｋ＝ｃ１ｃ２．．．ｃｑである）を識別する情報を受け取るためのコードモジュールを含み、
ｉ＝１で開始する、１≦ｉ≦ｆであるｋの各ｃ１に対して、該クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するように前記データ構造を使用するためのコードモジュールは、
（ａ）レベル「（ｉ−１）」で前記データベースのメモリ構造を選択するためのコードモジュールと、
（ｂ）該現在選択されたメモリ構造のメモリ位置のアレイにおける文字ｃｉに対応するメモリ位置が、前記データベース内で別のメモリ構造を参照しない場合、該クエリエレメントが該エレメントのセットに含まれないことを示す信号を出力するためのコードモジュールと、
（ｃ）該現在選択されたメモリ構造のメモリ位置のアレイにおける文字ｃｉに対応するメモリ位置が、レベル「ｉ」の該データベースのメモリ構造のアドレスを格納する場合、該レベル「ｉ」のメモリ構造のアドレスが格納される、該レベル「ｉ」でメモリ構造を選択するためのコードモジュールと、
（ｄ）該「ｉ」の値を１だけインクリメントするためのコードモジュールと、
（ｅ）「ｉ」≦「ｑ」の間、ステップ（ｂ）、（ｃ）、および（ｄ）を繰り返すためのコードモジュールであって、該クエリエレメントが該エレメントのセットに含まれないことを示す信号が出力されていない、コードモジュールと、
該クエリエレメントが該エレメントのセットに含まれないことを示す信号が出力されていない場合、
ステップ（ｃ）において選択された該メモリ構造の第１のメモリ位置が該クエリエレメントを参照するかどうかを判定するためのコードモジュールと、
ステップ（ｃ）において選択された該メモリ構造の該第１のメモリ位置が該クエリエレメントを参照する場合、該クエリエレメントが該エレメントのセットに含まれることを示す信号を出力し、他の場合は、該クエリエレメントが該エレメントのセットに含まれないことを示す信号を出力するためのコードモジュールと
を含む、請求項２０に記載のシステム。
【請求項２２】
前記エレメントのセットにおけるエレメントを識別する情報に基づいて前記データ構造を構築するためのコードモジュールは、前記エレメントのセットにおける各エレメント「Ｒ」（あるｆ≦Ｙに対してＲ＝ｃ１ｃ２．．．ｃｆである）に対して、各文字ｃｉは、領域Σの文字セットに属し（１≦ｉ≦ｆ）、エレメントＲにおける各文字の位置およびアイデンティティを示す情報を前記データベースに格納するためのコードモジュールを含む、請求項１８に記載のシステム。
【請求項２３】
前記クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために前記データ構造を使用するためのコードモジュールは、該クエリエレメントが前記データベースによって格納された情報、文字および該クエリエレメントにおけるそれらの位置を識別する情報に基づいてエレメントのセットに含まれるかどうかを判定するためのコードモジュールを含む、請求項２２に記載のシステム。
【請求項２４】
前記エレメントのセットにおけるエレメントを識別する情報に基づいて前記データ構造を構築するためのコードモジュールは、該エレメントのセットにおける各エレメント「Ｒ」に対して、
（ａ）前記選択されたメモリ構造として該データ構造の前記ルートメモリ構造を選択するためのコードモジュールと、
（ｂ）該エレメントＲの第１の文字を選択するためのコードモジュールと、
（ｃ）該選択されたメモリ構造のメモリ位置のアレイにおいて選択された文字に対応するメモリ位置が、該データ構造における別のメモリ構造を参照しない場合に、該現在選択されたメモリ構造のメモリ位置のアレイにおいて該選択された文字に対応する該メモリ位置に新しいメモリ構造のアドレスを格納するためのコードモジュールと、
（ｄ）該メモリ構造のアドレスが、該選択されたメモリ構造のメモリ位置のアレイにおいて該選択された文字に対応する該メモリ位置に該選択されたメモリ構造として格納される該メモリ構造を選択するためのコードモジュールと、
（ｅ）該選択された文字がエレメントＲの最後の文字である場合、ステップ（ｄ）において選択された該メモリ構造が前記第１のメモリ位置におけるエレメントＲへの参照を格納するためのコードモジュールと、
他の場合では、エレメントＲの次の文字を選択し、ステップ（ｃ）、（ｄ）、および（ｅ）を繰り返すためのコードモジュールと
を含む、請求項１８に記載のシステム。
【請求項２５】
前記クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために前記データ構造を使用するためのコードモジュールは、
（ａ）前記選択されたメモリ構造として該データ構造の前記ルートメモリ構造を選択するためのコードモジュールと、
（ｂ）該クエリエレメントの第１の文字を選択するためのコードモジュールと、
（ｃ）該選択されたメモリ構造のメモリ位置のアレイにおいて選択された文字に対応するメモリ位置が、該データ構造における別のメモリ構造を参照しない場合に、該クエリエレメントが該エレメントのセットに含まれないことを示す信号を出力するためのコードモジュールと、
他の場合では、該メモリ構造のアドレスが該選択されたメモリエレメントとして格納される該メモリ構造を選択するためのコードモジュールと、
（ｄ）該選択された文字が該クエリエレメントの最後の文字である場合、
ステップ（ｃ）で選択された、該メモリ構造の第１のメモリ位置が該クエリエレメントを参照するかどうかを判定するためのコードモジュールと、
ステップ（ｃ）において選択された該メモリ構造の第１のメモリ位置が該クエリエレメントを参照する場合、該クエリエレメントが該エレメントのセットに含まれることを示す信号を出力するコードモジュールと、他の場合は、該クエリエレメントが該エレメントのセットに含まれないことを示す信号を出力するためのコードモジュールと、
他の場合では、該クエリエレメントの次の文字を選択し、ステップ（ｃ）および（ｄ）を繰り返すためのコードモジュールと
を含む、請求項２４に記載のシステム。
【請求項２６】
前記データ構造のサイズは、前記エレメントのセットのエレメントの数から独立している、請求項１６に記載のシステム。
【請求項２７】
前記エレメントのセットは、「ｍ」文字の文字セットを有する領域Σからのエレメントを含み、「Ｚ」は、領域Σのエレメントの最大可能長さであり、
前記データ構造は、「Ｚ」メモリ構造を含み、各メモリ構造は、「ｍ」スロットを含み、各スロットは、第１のメモリ位置およびメモリ位置のアレイを含み、メモリ位置の各アレイは、「（ｍ＋１）」メモリ位置を含む、請求項２６に記載のシステム。
【請求項２８】
前記エレメントのセットにおけるエレメントを識別する情報に基づいて前記データ構造を構築するためのコードモジュールは、
各メモリ構造における各スロットのメモリ位置のアレイにおける前記第１のメモリ位置およびメモリ位置をゼロ値に初期化するためのコードモジュールと、
該エレメントのセットにおける各エレメント「Ｒ」（あるｆ≦Ｙ、各ｃｉ（１≦ｉ≦ｆ）に対してＲ＝ｃ１ｃ２．．．ｃｆである）に対して、
「ｉ」＜「ｆ」である場合、メモリ構造ｉのｃｉに対応する該スロットのメモリ位置のアレイにおける文字ｃｉ＋１に対応するメモリ位置にゼロでない値を格納するためのコードモジュールと、
「ｉ」＝「ｆ」である場合、メモリ構造ｉのｃｉに対応する該スロットのメモリ位置のアレイの内の（ｍ＋１）番目のメモリ位置にゼロでない値を格納するためのコードモジュールと、
メモリ構造ｉのｃｉに対応する該スロットの第１のメモリ位置におけるエレメント「Ｒ」への参照を格納するためのコードモジュールと
を含む、請求項２７に記載のシステム。
【請求項２９】
前記クエリエレメントを識別する情報を受け取るためのコードモジュールは、クエリエレメント「ｋ」（あるｑ≦Ｚに対してｋ＝ｃ１ｃ２．．．ｃｑである）を識別する情報を受け取るためのコードモジュールを含み、
該クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために前記データ構造を使用するためのコードモジュールは、ｋの各ｃｉに対して
「ｉ」＜「ｑ」である場合、ゼロでない値がメモリ構造ｉのｃｉに対応する前記スロットのメモリ位置のアレイにおける文字ｃｉ＋１に対応するメモリ位置に格納される場合、
「ｉ」が「ｑ」に等しい場合、ゼロでない値がメモリ構造ｉのｃｉに対応する該スロットのメモリ位置のアレイにおける（ｍ＋１）番目のメモリ位置に格納され、メモリ構造ｉのｃｉに対応する該スロットの前記第１のメモリ位置が該クエリエレメントを参照する場合、
該クエリエレメントが前記エレメントのセットに含まれることを示す信号を出力するためのコードモジュールを含む、請求項２８に記載のシステム。
【請求項３０】
前記クエリエレメントを識別する情報を受け取るためのコードモジュールは、クエリエレメント「ｋ」（あるｑ≦Ｚに対してｋ＝ｃ１ｃ２．．．ｃｑである）を識別する情報を受け取るためのコードモジュールを含み、
該クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために前記データ構造を使用するためのコードモジュールは、ｋの任意のｃｉに対して
「ｉ」が「ｑ」に等しい場合、ゼロでない値がメモリ構造ｉのｃｉに対応する前記スロットのメモリ位置のアレイにおける（ｍ＋１）番目のメモリ位置に格納されるか、またはメモリ構造ｉのｃｉに対応する該スロットの前記第１のメモリ位置が該クエリエレメントを参照しない場合、
「ｉ」＜「ｑ」である場合、ゼロでない値がメモリ構造ｉのｃｉに対応する該スロットのメモリ位置のアレイにおける文字ｃｉ＋１に対応するメモリ位置に格納される場合、
該クエリエレメントが、前記エレメントのセットに含まれないことを示す信号を出力するためのコードモジュールを含む、請求項２８に記載のシステム。
【請求項３１】
クエリエレメントがエレメントのセットに含まれるかどうかを判定するためのコンピュータ読み出し可能記録媒体に格納されたコンピュータプログラム製品であって、
該エレメントのセットにおけるエレメントを識別する情報に基づいてデータ構造を構築するためのコードと、
該クエリエレメントを識別する情報を受け取るためのコードと、
該クエリエレメントが該エレメントのセットに含まれるかどうかを判定するために必要とされた比較の数が該クエリエレメントの長さに比例し、該エレメントのセットのエレメントの数から独立しているように、該クエリエレメントが該エレメントのセットに含まれているかどうかを判定するためにデータ構造を使用するためのコードと
を含む、コンピュータプログラム製品。
【請求項３２】
前記クエリエレメントは、長さ「ｑ」であり、該クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために、多くとも文字「ｑ」の比較が必要とされる、請求項３１に記載のコンピュータプログラム製品。
【請求項３３】
前記エレメントのセットは、「ｍ」文字の文字セットを有する領域Σからのエレメントを含み、「Ｚ」は、領域Σのエレメントの最大可能長さであり、「Ｙ」は、１≦Ｙ≦Ｚであるように該エレメントのセットの最長のエレメントの長さであり、
前記データ構造を構築するためのコードは、ルートメモリ構造によってヘッダーが付けられた複数のメモリ構造を含む該データ構造を構築するためのコードを含み、該複数のメモリ構造における各メモリ構造は、第１のメモリ位置および「ｍ」のメモリ位置のアレイを含む、請求項３１に記載のコンピュータプログラム製品。
【請求項３４】
前記データ構造は、全体で（Ｙ＋１）レベルを含み、
該データ構造の各々のメモリ構造は、レベルＬ（０≦Ｌ≦Ｙ）に属し、特定のメモリ構造に対するレベルは、該メモリ構造の数を表し、前記ルートメモリ構造から開始し、該ルートメモリ構造は、該特定のメモリ構造に到達するように移動される必要があり、該ルートメモリ構造はレベル０に属する、請求項３３に記載のコンピュータプログラム製品。
【請求項３５】
前記エレメントのセットにおけるエレメントを識別する情報に基づいて前記データ構造を構築するためのコードは、該エレメントのセットにおける各エレメント「Ｒ」（あるｆ≦Ｙに対してＲ＝ｃ１ｃ２．．．ｃｆである）に対して、各文字ｃｉは、領域Σの文字セットに属し（１≦ｉ≦ｆ）、エレメントＲにおける各文字の位置およびアイデンティティを示す情報を前記データベースに格納するためのコードを含む、請求項３３に記載のコンピュータプログラム製品。
【請求項３６】
前記クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために前記データ構造を使用するためのコードは、該クエリエレメントが、前記データベースによって格納された情報、ならびに、文字および該クエリエレメントにおけるそれらの位置を識別する情報に基づいてエレメントのセットに含まれるかどうかを判定するためのコードを含む、請求項３５に記載のコンピュータプログラム製品。
【請求項３７】
前記データ構造のサイズは、前記エレメントのセットのエレメントの数から独立しており、
前記エレメントのセットは、「ｍ」文字の文字セットを有する領域Σからのエレメントを含み、「Ｚ」は、領域Σのエレメントの最大可能長さであり、
前記データ構造は、「Ｚ」メモリ構造を含み、各メモリ構造は、「ｍ」スロットを含み、各スロットは、第１のメモリ位置およびメモリ位置のアレイを含み、メモリ位置の各アレイは、「（ｍ＋１）」メモリ位置を含む、請求項３１に記載のコンピュータプログラム製品。
【請求項３８】
前記エレメントのセットにおけるエレメントを識別する情報に基づいて前記データ構造を構築するためのコードは、
各メモリ構造における各スロットのメモリ位置のアレイにおける前記第１のメモリ位置およびメモリ位置をゼロ値に初期化するためのコードと、
該エレメントのセットにおける各エレメント「Ｒ」（あるｆ≦Ｙ、各ｃｉ（１≦ｉ≦ｆ）に対してＲ＝ｃ１ｃ２．．．ｃｆである）に対して、
「ｉ」＜「ｆ」である場合、メモリ構造ｉのｃｉに対応するスロットのメモリ位置のアレイにおける文字ｃｉ＋１に対応するメモリ位置にゼロでない値を格納するためのコードと、
「ｉ」＝「ｆ」である場合、メモリ構造ｉのｃｉに対応するスロットのメモリ位置のアレイの内の（ｍ＋１）番目のメモリ位置にゼロでない値を格納するためのコードと、
メモリ構造ｉのｃｉに対応する該スロットの第１のメモリ位置におけるエレメント「Ｒ」への参照を格納するためのコードと
を含む、請求項３７に記載のコンピュータプログラム製品。
【請求項３９】
前記クエリエレメントを識別する情報を受け取るコードは、クエリエレメント「ｋ」（あるｑ≦Ｚに対してｋ＝ｃ１ｃ２．．．ｃｑである）を識別する情報を受け取るためのコードを含み、
該クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために前記データ構造を使用するためのコードは、ｋの各ｃｉに対して
「ｉ」＜「ｑ」である場合、ゼロでない値がメモリ構造ｉのｃｉに対応する前記スロットのメモリ位置のアレイにおける文字ｃｉ＋１に対応するメモリ位置に格納される場合、
「ｉ」が「ｑ」に等しい場合、ゼロでない値がメモリ構造ｉのｃｉに対応する該スロットのメモリ位置のアレイにおける（ｍ＋１）番目のメモリ位置に格納され、メモリ構造ｉのｃｉに対応するスロットの前記第１のメモリ位置が該クエリエレメントを参照する場合、
該クエリエレメントが前記エレメントのセットに含まれることを示す信号を出力するためのコードを含む、請求項３８に記載のコンピュータプログラム製品。
【請求項４０】
前記クエリエレメントを識別する情報を受け取るためのコードは、クエリエレメント「ｋ」（あるｑ≦Ｚに対してｋ＝ｃ１ｃ２．．．ｃｑである）を識別する情報を受け取るためのコードを含み、
該クエリエレメントが前記エレメントのセットに含まれるかどうかを判定するために前記データ構造を使用するためのコードは、ｋの任意のｃｉに対して
「ｉ」が「ｑ」に等しい場合、ゼロでない値がメモリ構造ｉのｃｉに対応する前記スロットのメモリ位置のアレイにおける（ｍ＋１）番目のメモリ位置に格納されるか、またはメモリ構造ｉのｃｉに対応する該スロットの前記第１のメモリ位置が該クエリエレメントを参照しない場合、
「ｉ」＜「ｑ」である場合、ゼロでない値がメモリ構造ｉのｃｉに対応する該スロットのメモリ位置のアレイにおける文字ｃｉ＋１に対応するメモリ位置に格納される場合、
該クエリエレメントが前記エレメントのセットに含まれないことを示す信号を出力するためのコードを含む、請求項３８に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願との相互参照）
本出願は、以下の出願からの優先権を主張し、この出願の全体は、本明細書において、全目的のために参考として援用される。
【０００２】
（１）米国仮特許出願第６０／２６３，３２０号、名称「ＴＥＣＨＮＩＱＵＥＳ  ＴＯ  ＦＡＣＩＬＩＴＡＴＥ  ＥＦＦＩＣＩＥＮＴ  ＳＥＡＲＣＨＩＮＧ」、２００１年１月１７日出願。
【０００３】
（２）米国非仮特許出願第１０／００６，１７９号、名称「ＥＦＦＩＣＩＥＮＴ  ＳＥＡＲＣＨＩＮＧ  ＴＥＣＨＮＩＱＵＥＳ」（代理人事件整理番号２０９６７−０００１１０ＵＳ）、２００１年１２月４日出願。
【背景技術】
【０００４】
（発明の背景）
本発明は、検索技術に関し、より詳細には、検索を行うために要求されるメモリリソースを最小にして効率に行われる検索を可能にする技術に関する。
【０００５】
検索は、重要な、かつ、広範囲に用いられる、コンピュータアプリケーションのオペレーションである。例えば、ファイルサーバ上のファイルリストは、そのリストが特定のファイル名を有するファイルを含むかを判定するために検索され得、均一なリソース識別子（ＵＲＩ）のリストは、ユーザ固有のＵＲＩがそのリスト中にあるかを判定するために検索され得、利用可能なリソースのリストは、リソースを位置づけるため、およびそのリソースに関連付けられたアクセス権を判定するために、アクセス制御アプリケーションによって検索され得、ファイルのコンテンツは、特定のキーワードがそのコンテンツ、およびくつかの他のアプリケーションに含まれるかを判定するように検索され得る。
【０００６】
効率的な検索技術に対する強まる需要を理解する一分野は、電子商業活動の領域である。オンラインコマーシャルサービスを提供する商業者および他のエンティティは、適宜な方法で顧客の要求に応答することを可能にするために高速で効率的な技術を使用する必要がある。彼らの利益を最大にするために、オンライン商業者はまた、検索に関連するコストを最小にするために、検索を行うための最小量のメモリおよび演算リソースを必要とする検索技術を好んで使用する。例えば、オンライン商業活動に対する支払いを認可するオンラインバンキング施設およびクレジットカード会社は、検索に関連するコストを最小にしながら、適宜に顧客の要求を処理するために効率的な検索技術を使用する必要がある。したがって、検索を行うための最小限の金銭および演算リソースを使用しながら適宜に検索を行う検索技術に対する需要が増大している。
【０００７】
検索することに対する異なるアプローチが多数ある。一つのアプローチによると、検索は、以下のようにモデリングされ得る。いくつかの領域Σからの「ｎ」個のエレメント「ｋ１，ｋ２，・・・，ｋｎ」を含むＳセット（すなわち、Ｓ＝（ｋ１，ｋ２，・・・，ｋｎ））、および、領域Σからのターゲットエレメントまたはクエリエレメントｋ（すなわち、ｋ∈Σ）が与えられる場合、検索は、ターゲットエレメントｋがセットＳに含まれるかどうか（すなわち、ｋ∈Ｓであるかどうか）を判定するプロセスである。検索プロセスは、さらに、Σにおける標的エレメントの位置を判定するためにプロセスする工程を含み得る。領域Σは、任意の不定領域、例えば、整数のセット、実数のセット、文字列のセット等であり得る。セットＳは、種々の形態でそれ自体を明らかにし得る。例えば、セットＳは、ファイルシステムを形成するファイルの集合、ＵＲＩのリスト、リソースのリスト等であり得る。セットＳの各エレメントｋｎは、領域Σの文字セットからの１以上の文字を含み得る。検索技術は、典型的には、ｋ∈Ｓであるかを判定するために必要な時間および処理リソースを最小にしようとする。
【０００８】
検索技術の効率を測定する一つの方法は、クエリエレメントｋがセットＳに含まれるかを判定するために検索技術によって必要とされる比較の数を判定することである。各比較は実施されるべき特定の時間単位を要求するので、検索技術は、クエリエレメントｋがセットＳに含まれるかを判定するための比較の数を低減することに努める。一般に、用語「比較」は、任意の２つの値を比較することに言及し得る。値は、１以上の文字、領域Σの１エレメントの１文字その他を含む領域Σのエレメントに対応し得る。したがって、領域Σのエレメントを領域Σの別のエレメントと比較する比較は、「エレメント比較」と呼ばれる。領域Σのエレメントの文字を別のエレメントの文字と比較する比較は、「文字比較」と呼ばれる。エレメント比較は、１以上の文字比較を含み得る。例えば、第一のエレメントが第二のエレメントと比較される場合、その比較は、第一のエレメントの個々の文字を第二のエレメントの文字と比較し得る。Σの各エレメントは、任意の長さであり得る（すなわち、可変数の文字を有する）ので、各比較は、比較を行うために「時間単位」より多くを要求し得る。
【０００９】
いくつかの従来の検索技術が、検索の問題を解決するために開発されてきた。一つのやみくもな力による（ｂｒｕｔｅ−ｆｏｒｃｅ）検索技術によると、クエリエレメントｋは、セットＳのすべてのエレメントと比較される。この技術は、検索を行うために「ｎ」エレメント比較までを要求し得る。ここで、ｎは、セットＳのエレメントの数である。したがって、ｎが非常に大きい場合（これは、きわめてよくある場合である）、このような検索技術のランタイム性能は、全く最適とはいえない。
【００１０】
いくつかの他の従来の検索技術は、セットＳがソートされた順序であることを要求する。例えば、バイナリ検索技術は、ｋ∈Ｓが提供された場合に、Ｓのエレメントがソートされた順序にあることを判定するために用いられ得る。バイナリ検索技術は、検索を完了するためにΘ（ｌｏｇｎ）エレメント比較を要求する（ここで、ｎは、セットＳのエレメントの数である）。しかしながら、このような検索技術の用途は、検索されるべきエレメントのセットがソートされた順序である必要がある条件のため極めて制限される。ソートされた順序内のデータセットを維持する際に含まれるコストが、検索の全体のコストに加わり、このような検索技術の使用は、多くの用途において実用的ではなくなる（特に、検索されるべきデータセットが大きく、データセットからのエレメントの頻繁な追加および削除がある場合の用途、例えば、電子商業環境での用途において）。結果として、このような検索技術の使用は、制限される。
【００１１】
他の検索技術は、Σがほぼ制限されるか、または、セットＳがΣ上に所定の分布を有する等の仮定に基づく。例えば、Σ＝{１，２，．．．，Ｎ}である場合、Ｐ．ｖａｎ  Ｅｍｄｅ  Ｂｏａｓ，Ｒ．ＫａｓｓおよびＥ．Ｚｉｊｌｓｔｒａによる「Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｏｆ  ａｎ  Ｅｆｆｉｃｉｅｎｔ  Ｐｒｉｏｒｉｔｙ  Ｑｕｅｕｅ，Ｍａｔｈｅｍａｔｉｃａｌ  Ｓｙｓｔｅｍｓ  Ｔｈｅｏｒｙ  １０，１９９７，ｐｐ．９９−１２７」に開示された検索技術（「内挿検索（ｉｎｔｅｒｐｏｌａｔｉｏｎ  ｓｅａｒｃｈ）」と呼ぶ）は、Ο（ｎ）の全メモリを用いるΟ（ｌｏｇｌｏｇＮ）時間において検索を行い得る。ｖａｎ  Ｅｍｄｅらの技術は、各オペレーションがΟ（ｌｏｇｌｏｇＮ）時間を利用する辞書（すなわち、挿入、削除、およびオペレーションをサポートするデータ構造）を用いる。例えば、Σがせいぜい１５０の長さの全文字列の領域である場合（およびΣのための文字セットに５０文字があることを仮定する）、検索を行うために要求される比較の数は、少なくとも（ｌｏｇｌｏｇ５０１５０＝１０）の比較となる。すなわち、検索時間は、少なくとも１０の比較になる。セットＳが（０，１）に均一に分布されると仮定される場合、ｖａｎ  Ｅｍｄｅらの技術（さらに、「内挿検索技術」と呼ぶ）は、予期されたΟ（ｌｏｇｌｏｇｎ）時間において検索し得る。しかしながら、これら検索技術の不都合は、それらは任意の不定領域Σに適用されることができないことである。さらに、これらの技術は、検索を行うために実質的なメモリリソースを要求し、結果として、検索されるべきデータセットが大きいときには全くコスト効率的でない。
【００１２】
辞書は、また、ｋ∈Ｓであるかを判定するために一つのみの比較が要求されるように規定され得る。例えば、Σ＝{１，２，．．．，Ｎ}である場合（すなわち、｜Σ｜＝Ｎ；領域Σは、Ｎ個のエレメントを含む）である。大きさΩ（Ｎ）のメモリを有する場合、辞書は、以下のようにインプリメントされ得る。Σのエレメントを、１，２，．．．，Ｎとしてラベルする。アレイＡ［１：Ｎ］（すなわち、アレイ「Ａ」は、Ｎエレメントを含む）は、Ａ［ｂ］が領域Σのエレメントｂに対応するように構成され得る。最初に、全ての位置が０に初期化される。次いで、セットＳのすべてのエレメントｋｉに対して、Ａ［ｋｉ］が１＜ｉ＜ｎに対して１に設定される（ここで、ｎは、セットＳにおけるエレメントの数である）。次いで、ｋ∈Ｓであるかの判定が、Ａ［ｋ］＝１（これは、エレメントの存在を示す）であるかを判定することによって行われ得る。この種の辞書がΟ（１）時間での検索を達成し得る一方で、この技術のために要求されるメモリリソースは、特に、Ｎが大きい場合に非常に大きくなり得る。例えば、Σがせいぜい１５０の長さの全ての文字列の領域である場合、Ｎは、５０の異なる文字があると仮定して５０１５０になる。したがって、このような技術のランタイム性能は、非常に最適である一方で、この技術によって要求される莫大な量のメモリリソースは、それを、大抵の用途に対して非実用的にする。
【００１３】
上記を考慮して、検索を行うために要求されるメモリリソースを最小にしながら効率的な方法で検索を行い得る検索技術に対する必要がある。
【発明の開示】
【課題を解決するための手段】
【００１４】
（発明の簡単な要旨）
本発明は、検索を行うために要求されるメモリリソースを最小にしながら効率的な方法で検索を行うための技術を提供する。本発明の技術によると、クエリエレメントがエレメントのセットに含まれているかを判定するために必要とされる比較の数は、クエリエレメントの長さに比例する。
【００１５】
本発明の実施形態によると、クエリエレメントがエレメントのセットに含まれるかを判定するための技術が提供される。この実施形態によると、データ構造は、エレメントのセットを識別する情報に基づいて構築される。クエリエレメントを識別する情報を受け取る本発明の実施形態は、クエリエレメントがエレメントのセットに含まれるかを判定するために、そのデータ構造を用い、その結果、クエリエレメントがエレメントのセットに含まれるかを判定するために必要とされる比較の数は、クエリエレメントの長さに比例し、エレメントのセットにおけるエレメントの数とは無関係である。
【００１６】
他の特徴を共に有する前述の実施形態、および本発明の利点は、以下の明細書、請求の範囲、および添付図面を参照するとより明らかになる。
【００１７】
（発明の詳細な説明）
本発明は、検索を行うために要求されるメモリリソースを最小にして効率的検索を行うための技術を提供する。本発明の技術に従う検索技術は、任意の領域Σ（すなわち、ｋ∈Σ）からの検索クエリエレメントｋがセットＳに含まれるか（すなわち、ｋ∈Ｓであるか）を判定する。このセットＳは、領域Σからの「ｎ」個のエレメント「ｋ１，ｋ２，．．．，ｋｎ」を含む（すなわち、Ｓ＝（ｋ１，ｋ２，．．．，ｋｎ）。領域Σにおける各エレメント（およびセットＳにおける続く各エレメント）は、領域Σの文字セットからの１以上の文字を含み得る。
【００１８】
図１は、本発明の実施形態を組み入れ得るコンピュータシステム１００の簡略化されたブロック図である。図１に示されるように、コンピュータシステム１００は、少なくとも１つのプロセッサ１０２を含む。このプロセッサ１０２は、バスサブシステム１０４を介して多数の周辺デバイスと通信する。これらの周辺デバイスは、格納サブシステム１０６を含み得る。この格納サブシステム１０６は、メモリサブシステム１０８およびファイル格納サブシステム１１０、ユーザインタフェース入力デバイス１１２、ユーザインタフェース出力デバイス１１４、およびネットワークインタフェースサブシステム１１６を含む。入出力デバイスは、コンピュータシステム１００とのユーザの相互作用を可能にする。ユーザは、人ユーザ、デバイス、プロセス、別のコンピュータその他であり得る。
【００１９】
ネットワークインタフェースサブシステム１１６は、他のコンピュータシステムおよび通信ネットワークにインタフェースを提供する。ネットワークインタフェースサブシステム１１６の実施形態は、イーサネット（Ｒ）カード、モデム（電話、衛星、ケーブル、ＩＳＤＮ等）、（非同期）デジタル加入者ライン（ＤＳＬ）ユニットその他を含む。コンピュータネットワークは、インターネット、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、無線ネットワーク、イントラネット、プライベートネットワーク、パブリックネットワーク、スイッチングされるネットワーク、その他を含み得る。
【００２０】
ユーザインタフェース入力デバイス１１２は、キーボード、マウス等のポインティングデバイス、トラックボール、タッチパッド、またはグラフィックタブレット、スキャナー、バーコードスキャナー、ディスプレイに組み込まれたタッチスクリーン、音声認識システム等のオーディオ入力デバイス、マイクロフォン、および他のタイプの入力デバイスを含み得る。一般に、用語「入力デバイス」の使用は、コンピュータシステム１００を用いて情報を入力するためのすべての可能なタイプのデバイスおよび方法を含めることが意図される。
【００２１】
ユーザインタフェース出力デバイス１１４は、ディスプレイサブシステム、プリンタ、ファックスマシン、または、オーディオ出力デバイス等の非視覚ディスプレイを含み得る。ディスプレイサブシステムは、陰極線管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）等のフラットパネルデバイス、または投影デバイスであり得る。ディスプレイサブシステムは、さらに、オーディオ出力デバイスを介する等で非視覚ディスプレイを提供し得る。一般に、用語「出力デバイス」の使用は、コンピュータシステム１００からの情報を出力する全ての可能なタイプのデバイスおよび方法を含めることが意図される。
【００２２】
格納サブシステム１０６は、コンピュータシステムおよび本発明の機能性を提供する基本プログラミングおよびデータ構築を格納するように構成され得る。例えば、本発明の実施形態によると、本発明の機能性をインプリメントするソフトウェアモジュールが、格納サブシステム１０６に格納され得る。これらのソフトウェアモジュールは、プロセッサ（単数または複数）１０２によって実行され得る。分散された環境では、ソフトウェアモジュールは、複数のコンピュータシステム上に格納され、複数のコンピュータシステムのプロセッサによって実行され得る。格納サブシステム１０６は、さらに、本発明の教示による情報を格納するために用いられ得る種々のデータベースおよびデータ構造を格納するための貯蔵所を提供し得る。格納サブシステム１０６は、メモリサブシステム１０８およびファイル格納サブシステム１１０を含み得る。
【００２３】
メモリサブシステム１０８は、プログラム実行の間インストラクションおよびデータを格納するための主要なランダムアクセスメモリ（ＲＡＭ）１１８および固定されたインストラクションが格納されているリードオンリーメモリ（ＲＯＭ）１２０を含む多数のメモリを含み得る。ファイル格納サブシステム１１０は、プログラムおよびデータファイルのための持続性（不揮発性）の格納を提供し、ハードディスクドライブ、取り外し可能なメディアおよびフロッピー（Ｒ）ディスクドライブ、コンパクトデジタルリードオンリーメモリ（ＣＤ−ＲＯＭ）ドライブ、光学ドライブ、取り外し可能なメディアカートリッジ、および他の同様な格納メディアを含み得る。１以上のドライブが他の接続されたコンピュータ上の遠隔位置に位置付けられ得る。
【００２４】
バスサブシステム１０４は、コンピュータシステム１００の種々のコンポーネントおよびサブシステム意図されるように互いに通信させる機構を提供する。コンピュータシステム１００の種々のサブシステムおよびコンポーネントは、同一の物理的位置にある必要はなく、種々の位置に分散され得る。バスサブシステム１０４は、単一バスとして概略的に示されるが、バスサブシステムの代わりの実施形態は、複数のバスを利用し得る。
【００２５】
コンピュータシステム１００自体は、パーソナルコンピュータ、ポータブルコンピュータ、ワークステーション、コンピュータ端末、ネットワークコンピュータ、メインフレーム、キオスク、携帯情報端末（ＰＤＡ）、セルフォン等の通信デバイス、エンターテイメントコンソール（ＰＳ２、Ｘ−ｂｏｘ）、または、任意の他のデータ処理システムを含む種々のタイプであり得る。コンピュータの常に変換する性質に起因して、図１に示されるンピュータシステム１００の説明は、本発明の好ましい実施形態を例示する目的のための特定の例としてのみ意図される。例えば、ＡＭＤからのＡｔｈｌｏｎＴＭクラスのマイクロプロセッサ、Ｉｎｔｅｌ  ＣｏｒｐｏｒａｔｉｏｎからのＰｅｎｔｉｕｍ（Ｒ）ＴＭクラスまたはＣｅｌｅｒｏｎＴＭクラスのマイクロプロセッサ、Ｍｏｔｏｒｏｌａ，Ｉｎｃ．，からのＰｏｗｅｒＰＣＴＭＧ３またはＧ４マイクロプロセッサ等の他のタイプのプロセッサ、Ｔｒａｎｓｍｅｔａ，ＩｎｃからのＣｒｕｓｏｅＴＭプロセッサその他が企図される。さらに、他のタイプのオペレーションシステムが、ＭｉｃｒｏｓｏｆｔからのＷｉｎｄｏｗｓ（Ｒ）オペレーションシステム（例えば、Ｗｉｎ９５、Ｗｉｎ９８、Ｗｉｎｄｏｗｓ（Ｒ）ＮＴＴＭ、Ｗｉｎｄｏｗｓ（Ｒ）ＸＰＴＭ等）、Ｓｕｎ  ＭｉｃｒｏｓｙｓｔｅｍｓからのＳｏｌａｒｉｓ、Ａｐｐｌｅ  Ｃｏｍｐｕｔｅｒ  ＣｏｒｐｏｒａｔｉｏｎからのＬＩＮＵＸ、ＵＮＩＸ（Ｒ）、ＭＡＣ  ＯＳ  Ｘ、ＢｅＯＳＴＭその他を含む代わりの実施形態において企図される。図１に示されるコンピュータシステムより多いまたはより少ないコンポーネントを有するコンピュータシステムの多くの他の構成が可能である。
【００２６】
本発明は、さらに、１以上のクライアントおよびサーバコンピュータを含む分散型ネットワーク環境において具体化され得る。このようなネットワーク環境では、本発明の教示に従って行われる処理および方法が、ネットワーク環境の１以上のコンピュータシステムの中で分散され得る。
【００２７】
図２は、本発明の環境に従って検索を行う方法の高レベルに簡略化されたフローチャート２００である。図２に示された方法は、コンピュータシステム１００上で実行するソフトウェアモジュール、コンピュータシステム１００に接続されたハードウェアモジュール、またはこれらの組み合わせによって行われ得る。図２に示されたフローチャート２００は、本発明を組み入れる実施形態の例示に過ぎず、請求の範囲に列挙された本発明の範囲を制限しない。当業者は、変形、改変、および代替を認識する。
【００２８】
図２に示されるように、本方法は、２つのフェーズを包含する。第一のフェーズの間、データ構造または他の同様なメモリ構造が、第２フェーズにおいて行われる検索オペレーションを促進するために生成される。第１フェーズの間に生成されたデータ構造は、検索されるべきデータセットに含まれるエレメントについての情報を封じ込める（すなわち、データ構造は、セットＳに含まれるエレメントに基づいて構築される）。本発明の実施形態によると、第１フェーズの間、コンピュータシステム１００は、セットＳのエレメントを識別する情報を受け取り得る（ステップ２０２）。エレメント自体は、コンピュータシステム１００のメモリサブシステムまたはコンピュータシステム１００にアクセス可能ななんらかのメモリに格納され得る。次いで、ステップ２０２において受け取られた情報に基づいて、コンピュータシステム１００は、第２フェーズにおいて行われる検索を容易にするためのデータ構造（または任意の他のメモリ格納構造）を構築し得る（ステップ２０４）。
【００２９】
種々の異なる種類のデータ構造が検索オペレーションを容易にするために用いられ得る。これらは、テーブル、データベース、リンクされたリスト、ツリー、定方向グラフ、その他を含む。一実施形態では、データ構造は、コンピュータシステム１００によって生成される一方で、本発明の代わりの実施形態では、セットＳのエレメントに関する情報を封じ込めるデータ構造は、別のコンピュータシステムによって構築され、そして、コンピュータシステム１００に提供され得る（例えば、データ構造は、別のシステムまたはデバイスによって生成され、コンピュータシステム１００にアクセス可能なメモリに格納され得る）。コンピュータシステム１００は、次いで、第２フェーズに従って検索を行うために格納されたデータ構造にアクセスし得る。
【００３０】
セットＳのエレメントに関する情報を格納するデータ構造が第１フェーズに従って構築された後、本発明は、次いで、本発明の教示に従って検索を行うためにデータ構造を用いる。本発明の実施形態によると、第２フェーズの間、コンピュータシステム１００は、検索クエリエレメント「ｋ」がセットＳに含まれるかを判定するために検索要求を受け取り得る（ステップ２０６）。検索クエリは、コンピュータシステム１００に接続された１以上の入力デバイスを用いてコンピュータシステム１００のユーザによって特定され得る。あるいは、検索クエリは、コンピュータシステム上で実行するプロセスから、コンピュータシステム１００に接続されたデバイスまたはシステム（例えば、ネットワークインタフェース１０６を介してコンピュータシステム１００に接続されたシステム）から、および／または、他のシステムまたはプロセスから構成および受け取られ得る。
【００３１】
ステップ２０４において生成されたデータ構造は、次いで、ステップ２０６において受け取られた検索要求で識別されたエレメントｋがセットＳに含まれるかを判定するために用いられる（ステップ２０８）。コンピュータシステム１００は、次いで、エレメントｋがセットＳにおいて見出されたかどうかを示す信号を出力し得る（ステップ２１０）。あるいは、コンピュータシステム１００は、ステップ２０８の結果に基づいて１以上の活動を行うように構成され得る。
【００３２】
本発明によると、種々の異なるデータ構造が検索プロセスを容易にするために、（第１フェーズの間に）構築され得る。さらに、種々の異なる検索技術が、第１フェーズの間に構築されたデータ構造によって格納された情報に基づいて特定のクエリエレメントｋがセットＳに含まれるかを判定するために用いられ得る。以下のセクションは、検索を行うために要求されたメモリリソースを最小にして効率的に検索を行うために用いられ得る２つの検索技術を記載する。以下に記載される検索技術の双方において、クエリエレメントｋがセットＳに含まれるかを判定するために必要とされる比較の数は、クエリエレメントの長さに比例する（すなわち、クエリエレメントに含まれる文字の数に比例する）。
【００３３】
（第１の検索技術）
この節は、クエリエレメントｋがセットＳに含まれるかどうかを判定するために用いられ得る第１の検索技術を説明する。図３は、本発明の実施形態に従う第１の検索技術を用いて検索演算を容易にするために、（図２のステップ２０４で）構築され得るツリーデータ構造３００の一部を示している。図３で示されたデータ構造３００は、本発明を組み込んだ実施形態を単に示しただけであり、特許請求の範囲に記載されたような本発明の範囲を制限しない。当業者は、改変、修正および代替物を認識する。
【００３４】
図３に示すように、ツリーデータ構造３００は、複数のノードまたはメモリ構造３０２、３０８、３１０等を含む。ツリー３００の各ノードは、第１のメモリ位置３０４を含む複数のメモリ位置、および、メモリ位置のアレイ（アレイ［］と呼ぶ）を含む。本発明の実施形態に従って、メモリ位置は３０４は、セットＳに関する情報を格納し得る。例えば、メモリ位置３０４は、セットＳのエレメントに対するポインタまたは参照、セットＳのエレメントに関連する情報に対するポインタまたは参照等を格納し得る。あるいは、メモリ位置３０４は、ヌル（またはゼロ）値を格納し得る。メモリ位置３０４がセットＳのエレメントに関する情報を格納するまたは指し示すので、メモリ位置３０４は、以下において「エレメントポインタ」として参照される。
【００３５】
アレイ３０６におけるメモリ位置は、データ構造３００の他のノードに対するポインタまたは参照を格納し得、あるいは、ヌル（またはゼロ）値に設定され得る。第１の検索技術を組み込んだ実施形態に従って、アレイ３０６における各メモリは、任意の領域Σに関連する文字セットからの文字に対応する。例えば、領域Σに対する文字セットが「ｍ」個の文字を含む場合、アレイ３０６は、（図３で示されたような）「ｍ」個のメモリ位置を含む。各メモリ位置は、文字セットからの特定の文字に対応する。従って、図３で示されるように、ツリー３００の各ノードは、「ｍ」個のメモリ位置を含むアレイＡｒｒａｙ［１：ｍ］を含む。ここで、Ａｒｒａｙ［１］は、領域Σに対する文字セットにおける第１の文字に対応し、Ａｒｒａｙ［２］は、領域Σに対する文字セットにおける第２の文字対応し、Ａｒｒａｙ［３］は、領域Σに対する文字セットにおける第３の文字に対応する（以下同様）。概して、Ａｒｒａｙ［ｉ］は、領域Σの文字セットにおけるｉ番目の位置の文字（ときに、領域Σのｉ番目の文字として参照される）に対応する（１≦ｉ≦ｍ）。例えば、領域Σに対する文字セットが英語のアルファベット（例えば、ａ，ｂ，ｃ，・・・，ｚ）で構成されている場合、ｍ＝２６である。この実施形態において、Ａｒｒａｙ［１］は、文字「ａ」に対応し、Ａｒｒａｙ［２］は、文字「ｂ」に対応し、Ａｒｒａｙ［３］は、文字「ｃ」に対応し、Ａｒｒａｙ［２６］は、文字「ｚ」に対応する（以下同様）。
【００３６】
図３に示された実施形態において、様々なノードがルートノード３０２を頭としたツリー構造の形態で組織されている。ツリー３００は、いくつかのレベルを含み得、各レベルは、一つ以上のノード（唯一のノード（すなわち、ルートノード３０２）を含む「レベル０」を除く）を含む。概して、特定のノードに対する「レベル」は、ルートノード３０２で開始し、特定のノードに到達するために移動する必要のあるノードの数を示す。ルートノード（例えば、図３におけるノード３０２）は、レベル０にある。なぜなら、ルートノードに到達するために移動する必要のあるノードが無いからである。図３に示されるノード３０８は、レベル１にある。なぜなら、ルートノード３０２は、ノード３０８に到達するために移動する必要があるからである。同様に、ノード３１０はまた、レベル１にある。ノード３０８および３１０に結合されたノードは、レベル２にあると考えられる（以下同様）。
【００３７】
第１の検索技術を適用する本発明の実施形態によると、特定のレベルＬにおける各ノードは、少なくとも（Ｌ＋１）の長さの文字を有するセットＳのエレメントに関する情報を格納する。詳細には、図３で示された実施形態において、特定のレベルＬにある各ノードは、少なくとも（Ｌ＋１）の長さの文字を有するセットＳのエレメントの（Ｌ＋１）番目の位置の（または、エレメント（Ｌ＋１）番目の文字と呼ばれる）文字に関する情報を格納する。この情報は、ノードのアレイ３０６に格納される。
【００３８】
第１の検索技術を適用する本発明の実施形態によると、セットＳが少なくとも（Ｌ＋１）の長さの文字を有する少なくとも一つのエレメントを含み、エレメントがエレメントの（Ｌ＋１）番目の位置におけるＡｒｒａｙ［ｉ］に対応する文字（すなわち、領域Σの文字セットのｉ番目の文字）を有する場合、ツリー３００のレベルＬにおけるノードのアレイメモリ位置Ａｒｒａｙ［ｉ］（１≦ｉ≦ｍ）は、非ヌル値に設定され、レベル（Ｌ＋１）におけるツリー３００の他のノードを指し示すポインタまたは参照を格納する。メモリ位置Ａｒｒａｙ［ｉ］が何らかのｉに対して設定され、ポインタＡｒｒａｙ［ｉ］がエレメントの（Ｌ＋１）番目のＡｒｒａｙ［ｉ］に対応する文字を有するセットＳにおけるエレメントに対応する一つ以上のノードのサブツリーを指し示す。逆に、本発明の教示に従って、ツリー３００のレベルＬにおけるノードのアレイメモリ位置Ａｒｒａｙ［ｉ］（１≦ｉ≦ｍ）は、セットＳがエレメント（Ｌ＋１）番目の位置におけるＡｒｒａｙ［ｉ］に対応する文字を有する任意のエレメントを含まない場合、ヌル（または、ゼロ）に設定される。
【００３９】
従って、セットＳ（このセットＳに対してデータ構造３００が構築される）が、少なくとも１つの文字長さを有する少なくとも１つのエレメントであって、エレメントの第１の位置におけるＡｒｒａｙ［ｉ］に対応する文字を有する少なくとも一つのエレメントを含む場合、ツリー３００におけるルートノード３０２（レベル０）のアレイメモリ位置Ａｒｒａｙ［ｉ］（１≦ｉ≦ｍ）は、非ヌル値に設定され、ツリー３００のレベル１にある別のノードを指し示すポインタまたは参照を格納する。例えば、図３に示されるように、ルートノード３０２のＡｒｒａｙ［２］は、レベル１でノード３０８に対するポインタを格納し、これにより、セットＳは、少なくとも１つの文字長さを有する少なくとも１つのエレメントであって、エレメントの第１の位置のＡｒｒａｙ［２］に対応する文字を有する少なくとも１つのエレメントを含む（言い換えると、セットＳは、領域Σの第２の文字で開始する少なくとも１つのエレメントを含む）。ルートノード３０２のＡｒｒａｙ［２］は、エレメントの第１の位置におけるＡｒｒａｙ［２］に対応する文字を有するセットＳのエレメントに対応するノードを構成するノード３０８を頭としたサブツリー３２０を指し示す。
【００４０】
同様に、図３で示されるように、ルートノード３０２のＡｒｒａｙ［ｍ］は、レベル１のノード３１０に対するポインタを格納し、これにより、セットＳが少なくとも１つの文字長さを有し、かつ、エレメントの第１の位置におけるＡｒｒａｙ［ｍ］に対応する文字を有する少なくとも１つのエレメントを含む（または、言い換えると、セットＳは、領域Σのｍ番目の文字で開始する少なくとも１つのエレメントを含む）ことを示す。ルートノード３０２のＡｒｒａｙ［ｍ］は、エレメントの第１の位置にあるＡｒｒａｙ［ｍ］に対応する文字を有するセットＳにおけるエレメントに対応するノードを含むノード３１０を頭としたサブツリー３３０を指し示す。
【００４１】
図３に示されるように、（レベル１の）ノード３０８のＡｒｒａｙ［ｌ］は、レベル２のノード（図示せず）に対するポインタを格納し、これにより、セットＳが少なくとも２つの文字長さを有する少なくとも１つのエレメントを含み、かつ、エレメントの第１の位置におけるＡｒｒａｙ［２］に対応する文字およびエレメントの第２の位置におけるＡｒｒａｙ［ｌ］に対応する文字を有する（または、言い換えると、セットＳは、エレメントの第１の位置における領域Σの第２の文字を有し、かつ、エレメントの第２の位置における領域Σの第１の文字を風する少なくとも１つのエレメントを含む。）ことを示す。ノード３０８のＡｒｒａｙ［ｌ］は、エレメントの第１の位置におけるＡｒｒａｙ［２］に対応する文字、および、エレメントの第２の位置におけるＡｒｒａｙ［ｌ］に対応する文字を有するセットＳのエレメントに対応するノードを構成するサブツリー３２２を指し示す。
【００４２】
図３に示すように、（レベル１である）ノード３０８のＡｒｒａｙ［ｍ］は、レベル２であるノード（図示せず）に対するポインタを格納し、これにより、セットＳは、少なくとも２つの文字長さを有し、エレメントの第１の位置におけるＡｒｒａｙ［２］に対応する文字を有し、そして、エレメントの第２の位置におけるＡｒｒａｙ［ｍ］に対応する文字を有する少なくとも１つのエレメントを含む（または、言い換えると、セットＳは、エレメントの第１の位置における領域Σの第２の文字、および、エレメントの第２に位置における領域Σのｍ番目の文字を有する少なくとも１つのエレメントを含む）ことを示す。ノード３０８のＡｒｒａｙ［ｍ］は、エレメントの第１の位置におけるＡｒｒａｙ［２］に対応する文字、および、エレメントの第２の位置におけるＡｒｒａｙ［ｍ］に対応する文字を有するセットＳにおけるエレメントに対応するノードを構成するサブツリー３２４を指し示す。
【００４３】
図３に示されるように、（レベル１である）ノード３１０のＡｒｒａｙ［２］は、レベル２であるノード（図示せず）に対するポインタを格納し、これにより、少なくとも２つの文字長さを有し、エレメントの第１の位置におけるＡｒｒａｙ［ｍ］に対応する文字を有し、エレメントの第２の位置におけるＡｒｒａｙ［２］に対応する文字を有する少なくとも１つのエレメントを含む（または、言い換えると、セットＳは、エレメントの第１の位置における領域Σのｍ番目の文字、および、エレメントの第２の位置における領域Σの２番目の文字を有する少なくとも１つのエレメントを含む）ことを示す。ノード３１０のＡｒｒａｙ［２］は、エレメントの第１の位置におけるＡｒｒａｙ［ｍ］に対応する文字、および、エレメントの第２の位置におけるＡｒｒａｙ［２］に対応する文字を有するセットＳのエレメントに対応するノードを構成するサブツリー３３２を指し示す。
【００４４】
図３で示されるように、ルートノード３０２のＡｒｒａｙ［ｌ］が（図３で「０」で示される）ＮＵＬＬに設定されるので、このことは、セットＳがエレメントの第１の位置におけるＡｒｒａｙ［ｌ］に対応する文字を有する任意のエレメントを含まない（または、言い換えると、セットＳは、領域Σの１番目の文字で開始する任意のエレメントを含まない）ことを示す。同様に、ノード３０８のＡｒｒａｙ［２］は、ＮＵＬＬに設定され、これにより、セットＳがエレメントの第１の位置におけるＡｒｒａｙ［２］に対応する文字、および、エレメントの第２の位置におけるＡｒｒａｙ［２］に対応する文字を有する任意のエレメントを含まないことを示す。同様に、ノード３１０のＡｒｒａｙ［ｌ］は、ＮＵＬＬに設定され、これにより、セットＳがエレメントの第１の位置におけるＡｒｒａｙ［ｍ］に対応する文字と、エレメントの第２の位置におけるＡｒｒａｙ［ｌ］に対応する文字との両方を有する任意のエレメントを含まないことを示す。
【００４５】
データ構造３００が構築される様態の結果として、本発明の実施形態に従って、データ構造３００の最大レベル（Ｌｍａｘ）は、セットＳにおける最大長さを有するエレメントの長さに等しい。上記のように、レベル「Ｌ」（ここで、１≦Ｌ≦Ｌｍａｘ）におけるツリー３００のノードは、少なくともＬの文字を有するセットＳのエレメントに対応する。従って、ツリー３００におけるレベルＬのノードの存在は、セットＳが少なくともＬの文字を構成する少なくとも１つのエレメントを含むことを示す。さらに、レベルＬにおけるノードのアレイメモリ位置Ａｒｒａｙ［ｉ］は、セットＳがエレメントにおける（Ｌ＋１）番目の位置における領域Σのｉ番目の文字を含む少なくとも１つのエレメントを含む場合、非ＮＵＬＬである。
【００４６】
セットＳが正確にＬの文字を含み（すなわち、エレメントの長さがＬである）、かつ、ルートノードから開始する特定のノードに到達するために移動する様々なノードのアレイポインタに対応する文字を含む少なくとも１つのエレメントを含み、文字が、移動したノードに１を加えたレベルで示される位置にある場合、レベルＬの特定のノードのメモリ位置３０４（または、エレメントポインタ３０４）が設定される。このようなエレメントがセットＳに存在しない場合、メモリ位置３０４は、（図３でゼロで示された）ヌル値に設定され得る。ノードのエレメントポインタ３０４は、エレメント自身を指し示し得る、あるいは、代わりに特定のエレメントに関するまたは関連する情報を指し示し得る。例えば、各エレメントがリソースに対応するアクセス制御アプリケーションにおいて、特定のエレメントに対応するエレメントポインタは、リソースにアクセスし得るユーザのリストを指し示し得る。第１の検索技術を用いる実施形態に従って、ルートノードのエレメントポインタは、常にヌル値に設定される。
【００４７】
例えば、図３で示されるように、ノード３０８のエレメントポインタ３０４は、非ヌル値に設定され、セットＳのエレメントに関するデータを指し示す。これは、セットＳが（Ｌ＋１）＝０＋１＝１の丁度の文字長さを有するエレメントを含み、文字がＡｒｒａｙ［２］に対応する領域Σの文字（すなわち、領域Σの文字セットの２番目の文字）であることを示す。同様に、ノード３１０のエレメントポインタ３０４は、非ヌル値に設定され、セットＳのエレメントに関連するデータを指し示し、これにより、セットＳが１つの文字の丁度の長さを有し、文字がＡｒｒａｙ［ｍ］に対応する領域Σの文字（すなわち、領域Σの文字セットのｍ番目の文字）であることを示す。
【００４８】
図４は、領域Σに属するエレメントを含む特定のセットＳのための第１の検索技術を適用する本発明の実施形態に従って構築されたツリーデータ構造４００を示す。領域Σに対する文字セットは５つの文字（すなわち、「１」、「２」、「３」、「４」および「５」）から構成されると仮定される。さらに、セットＳが以下の６つのエレメントＳ＝（「１」、「１２３」、「１３」、「１３４」、「２１」、「２５」）を含むことを想定する。これらの仮定に基づいて構築されたツリーデータ構造は、図４に示される。
【００４９】
図４で示されるように、ツリー４００の各ノードは、エレメントポインタおよびメモリ位置アレイＡｒｒａｙ［１：５］を含む。ツリー４００は、セットＳにおけるエレメント（エレメント「１２３」および「１３４」）の最大長さに対応するＬｍａｘ＝３である４つのレベル（レベル０、レベル１、レベル２、レベル３）を有する。例えば、エレメント「１２３」は、ツリー４００のレベル３におけるノード４１６によって示される。ノード４１６のエレメントポインタは、エレメント「１２３」、または、エレメント「１２３」に関連する情報を指し示す。同様に、ノード４０４のエレメントポインタは、エレメント「１」を指し示し、ノード４１０のエレメントポインタは、エレメント「１３」を指し示し、ノード４１８のエレメントポインタは、エレメント「１３４」を指し示し、ノード４１２のエレメントポインタは、エレメント「２１」を指し示し、そして、ノード４１４のエレメントポインタは、エレメント「２５」を指し示す。
【００５０】
図５は、第１の検索技術を適用する本発明の実施形態に従う検索を容易にするデータ構造を構築する方法の高レベルに単純化されたフローチャート５００である。図５で示される方法は、コンピュータシステム１００、コンピュータシステム１００に結合されたハードウェアモジュール、または、それらの組み合わせで実行するソフトウェアモジュールによって実施され得る。図５で示されるフローチャート５００は、本発明を組み込んだ実施形態を単に示しており、請求項に記載された本発明の範囲を制限するものではない。当業者は、改変、修正および代替物を認識する。
【００５１】
このプロセスは、構築されるべきデータ構造としてルートノードが存在するかしないかを判定することによって開始する（ステップ５０２）。ルートノードがまだ存在しない場合、新規のルートノードが生成され、かつ、初期化される（ステップ５０４）。ノード初期化プロセスの一部として、エレメントポインタおよびメモリ位置のアレイを含む全てのメモリ位置は、ヌル（または、ゼロ）値に初期化される。
【００５２】
次いで、データ構造おける挿入されるべきセットＳのエレメント（または、エレメントを識別する情報）がアクセスされる（ステップ５０６）。セットＳの第１のエレメント（または、セットＳの第１のエレメントを識別する情報）は、図５で示されたフローチャートの第１のパス中にアクセスされる。他のエレメント（または、セットＳの他のエレメントを識別する情報）は、セットＳ中の全てのエレメントが処理されるまで次のパス中でアクセスされる。
【００５３】
次いで、ポインタ変数「ＣｕｒｒＰｔｒ」は、（ポインタ変数がまだ存在しない場合）インスタント化され、ルートノードを指し示すまたは参照するように初期化される（ステップ５０８）。ポインタ変数ＣｕｒｒＰｔｒは、データ構造を移動させるために用いられ得る。数字変数「ｉ」は、１に初期化される（ステップ５１０）。この変数は、データ構造において挿入されるべきセットＳの各エレメントの様々な文字を移動させるように用いられる。文字変数「ｃ」は、ステップ５０６においてアクセスされるエレメントのｉ番目の位置における文字に初期化される（ステップ５１２）。数字変数「ｐ」は、領域Σに対する文字セットにおける変数ｃによって格納される文字の位置に初期化される（ステップ５１４）。例えば、文字セットが英語のアルファベット（例えば、ａ、ｂ、ｃ、・・・、ｚ）である場合、変数ｃが文字「ａ」を格納するなら変数ｐは１に設定され、変数ｃが文字「ｆ」を格納するなら変数ｐは６に設定され、変数ｃが文字「ｚ」を格納するなら変数ｐは２６に設定される（以下同様）。
【００５４】
次いで、ＣｕｒｒＰｔｒによって指し示されたノードのメモリ位置Ａｒｒａｙ［ｐ］は、次いで、メモリ位置がヌル値を格納するかどうかを判定するためにチェックされる（ステップ５１６）。ＣｕｒｒＰｔｒによって指し示されたノードのＡｒｒａｙ［ｐ］がヌル値を格納しない（すなわち、データ構造のノードにポインタを格納する）場合、ＣｕｒｒＰｔｒは、ＣｕｒｒＰｔｒによって現在指し示されているノードのＡｒｒａｙ［ｐ］によって指し示されたノードを指し示すまたは参照するように更新される（ステップ５１８）。次いで、以下のように、プロセスがステップ５２６に続く。
【００５５】
次いで、ＣｕｒｒＰｔｒによって指し示されたノードのＡｒｒａｙ［ｐ］がヌル値を格納することをステップ５１６において判定される場合、新規のノードが生成され、かつ、初期化される（ステップ５２０）。ノード初期化プロセスの一部として、エレメントポインタおよびメモリ位置のアレイを含む全てのメモリ位置がヌル（またはゼロ）値に初期化される。ＣｕｒｒＰｔｒによって指し示されたノードのメモリ位置Ａｒｒａｙ［ｐ］は、次いで、ステップ５２０において生成された新規のノードに対する参照またはポインタを格納するように更新される（ステップ５２２）。ＣｕｒｒＰｔｒはまた、ステップ５２０で生成されたノードを指し示すまたは参照するように更新される（ステップ５２４）。次いで、処理は、ステップ５２６に続く。
【００５６】
次いで、ステップ５０６においてアクセスされたエレメントの全ての文字が処理されるかどうかを判定するようにチェックが行われる（ステップ５２６）。言い換えると、ステップ５０６においてアクセスされたエレメントのエンドに到達したかどうかが判定される。エレメントのエンドに到達していない（すなわち、エレメントがまだ１つ以上の処理されていない文字を含む）場合、数字変数ｉの値は、１つだけ上がる（ステップ５２８）。次いで、処理は、ステップ５１２に続く。ここで、処理されているエレメントの次の文字がアクセスされる。エレメントのエンドに到達する（すなわち、エレメントの全ての文字が処理される）場合、ＣｕｒｒＰｔｒによって指し示されたノードのエレメントポインタは、ステップ５０６でアクセスされたエレメントを指し示すように更新される（ステップ５３０）。あるいは、エレメントポインタは、ステップ５０６においてアクセスされたエレメントと関連する情報を指し得る。
【００５７】
次いで、セットＳにおける全てのエレメントが処理されているかどうかを判定するためにチェックが行われる（ステップ５３２）。セットＳの全てのエレメントが処理されていない場合、処理は、ステップ５０６に続く。ここで、セットＳの次の処理されていないエレメントがアクセスされる。しかし、セットＳにおける全てのエレメントが処理されたことが判定された場合、図５で示されたプロセスは、終了する。
【００５８】
図５で示されたフローチャートに従って構築されたデータ構造は、次いで、第１の検索技術に従う検索を容易にするために用いられ得る。このデータ構造は、格納サブシステムに格納され得る。この格納サブシステムから、データ構造が検索演算中にアクセスされ得る。本発明の教示によると、データ構造の構造は、エレメントが挿入される順序に独立しており、挿入されているエレメント、および、エレメントの文字の長さにのみ依存している。データ構造のレベルの数は、セットＳにおける最長エレメントの長さに依存している。概して、データ構造のレベルの数は、Ｚの値に依存している（ここで、「Ｚ」は、領域Σにおけるエレメントの最大の可能な長さ（結果として、セットＳにおけるエレメントの最大の可能な長さ）である）。例えば、セットＳが長さＺのエレメントを含む場合、第１の検索技術に従って構築されたデータ構造は、Ｌｍａｘ＝Ｚである全体で（Ｚ＋１）レベルを有する。データ構造は、任意のレベルにおいて格納された二重の情報が無いので、スペースに効率的である。
【００５９】
データ構造の最大サイズが固定され、小さく、そして、セットＳにおけるエレメントの数に独立している。図５に示されたフローチャートに従って生成されたデータ構造（例えば、図３および図４で示されたデータ構造）に対して、用いられたメモリは、ビットアレイ（Ａｒｒａｙ［］）ポインタに対してＺｍ（ｍ＋１）であり、エレメントポインタに対して２Ｚｍバイトである（ここで、「Ｚ」は、領域Σにおけるエレメントの最大可能長さであり、「ｍ」は、領域Σに対する文字セットにおける文字長さである）。例として、領域Σにおけるエレメントの最大長さが２５５である場合（例えば、領域Σがコンピュータベースのファイルシステムにおけるストリングに対応する場合）、そして、文字セットのサイズが９１である場合（アルファベットの文字である場合）、データ構造に必要とされるメモリは、約３００ＫＢである。データ構造の効率的表示が与えられたために、検索要求の効率的処理に対して複数の位置（例えば、ウェブサーバ、プロキシサーバ等）でキャッシュされ得る。
【００６０】
図６は、セットＳが第１の検索技術を適用する本発明の実施形態に従う検索クエリエレメントｋを含むかどうかを判定する方法の高レベルに単純化されたフローチャート６００である。図６で示された方法は、コンピュータシステム１００、コンピュータシステム１００に結合されたハードウェアモジュール、または、それらの組み合わせ上で実行するソフトウェアモジュールによって実施され得る。図６で示されたフローチャート６００は、本発明を組み込んだ実施形態を単に示すのみであり、特許請求の範囲に記載されたような本発明の範囲を制限しない。当業者は、改変、修正および代替物を認識する。
【００６１】
図６で示されるように、セットＳが検索クエリエレメントｋを含むかどうかを判定するための検索要求をコンピュータシステム１００が受け取るとき、処理が初期化され得る（ステップ６０２）。上記されたように、検索要求は、コンピュータシステム１００に結合された１つ以上の入力デバイスを用いるコンピュータシステム１００のユーザによって特定され得る。あるいは、検索クエリは、また、コンピュータシステム１００上で実行するプロセスから、コンピュータシステム１００に結合されたデバイスまたはシステム（例えば、ネットワークインタフェース１０６を介してコンピュータシステム１００に結合されたシステム）から、および／または、他のシステムまたはプロセスから構成され得る、または、受け取られる。
【００６２】
次いで、コンピュータシステム１００は、処理用に用いられるべき変数を初期化する。次いで、ポインタ変数「ＣｕｒｒＰｔｒ」は、（ポインタ変数が存在しない場合）インスタント化され、（図５によって構築された）セットＳのために構築されたデータ構造のルートノードを指し示すまたは参照して、検索用に用いられるように初期化される（ステップ６０４）。データ構造は、検索を実行するコンピュータシステム１００にアクセス可能なメモリからアクセスされ得る。ポインタ変数ＣｕｒｒＰｔｒは、データ構造を移動するために用いられる。数字カウンタ変数「ｉ」は、次いで、１に初期化される（ステップ６０６）。この変数は、クエリエレメントｋの様々な特徴を移動するために用いられる。文字変数「ｃ」は、次いで、クエリエレメントｋのｉ番目の位置における文字に初期化される（ステップ６０８）。フローチャートを最初に通過する間、変数ｃは、エレメントｋの第１の文字に初期化される。数字変数「ｐ」は、次いで、領域Σに対する文字セットにおける変数ｃによって格納された文字の位置に初期化される（ステップ６１０）。例えば、文字セットが英語のアルファベット（例えば、ａ、ｂ、ｃ、・・・、ｚ）のセットである場合、変数ｃが文字「ａ」を格納すると変数ｐは１に設定され、変数ｃが文字「ｆ」を格納すると変数ｐは６に設定され、変数ｃが文字「ｚ」を格納すると変数ｐは２６に設定される（以下同様）。
【００６３】
ＣｕｒｒＰｔｒによって指し示されたノードのメモリ位置Ａｒｒａｙ［ｐ］は、次いで、メモリ位置がヌル値を格納しているかどうかを判定するためにチェックされる（ステップ６１２）。ＣｕｒｒＰｔｒによって指し示されたノードのＡｒｒａｙ［ｐ］がヌル値を格納する場合、Ａｒｒａｙ［ｐ］は、セットＳがエレメントｋを含まないことを示す。次いで、セットＳがクエリエレメントｋを含まないことを示す検索要求のソースに、信号が出力され得る（ステップ６１４）。他の適切な行動は、また、ステップ６１４において実施され得る。
【００６４】
ＣｕｒｒＰｔｒによって指し示されるノードのＡｒｒａｙ［ｐ］が非ヌル値を格納する（すなわち、データ構造における別のノードに対するポインタまたは参照を格納する）ことがステップ６１２において判定される場合、ＣｕｒｒＰｔｒは、ＣｕｒｒＰｔｒによって現在示されているノードのＡｒｒａｙ［ｐ］によって示されているノードを指し示すまたは参照するように更新される（ステップ６１６）。次いで、本発明は、クエリエレメントｋの全ての文字が処理されているかどうかをチェックする（ステップ６１８）。言い換えると、本発明は、クエリエレメントｋのエンドに到達しているかどうかを判定する。クエリエレメントｋのエンドに到達していない（すなわち、クエリエレメントｋがまだ一つ以上の未処理の文字を含んでいる）場合、数字変数ｉの値は、１つ加えられる（ステップ６２０）。次いで、プロセスは、ステップ６０８に続く。ここで、クエリエレメントｋの次の文字がアクセスされる。
【００６５】
クエリエレメントｋのエンドに到達したことがステップ６１８で判定される（すなわち、クエリエレメントｋの全ての文字が処理された）場合、ＣｕｒｒＰｔｒによって指し示されたノードのエレメントポインタは、エレメントポインタが非ヌル値を格納するかどうかを理解するためにチェックされる（ステップ６２２）。あるいは、ＣｕｒｒＰｔｒによって指し示されたノードのエレメントポインタは、エレメントポインタがエレメントｋを指し示す、または、エレメントｋに関連する情報を指し示すかどうかを理解するためにチェックされる。エレメントポインタがヌル値を格納する場合、エレメントポインタは、セットＳがエレメントｋを含まず、処理がステップ６１４に続くことを示す。
【００６６】
しかし、ＣｕｒｒＰｔｒによって指し示されたノードのエレメントポインタが非ヌル値を格納する（エレメント自身、または、エレメントに関連する情報を指し示し得る）ことがステップ６２２において判定される場合、エレメントポインタは、セットＳがクエリエレメントｋを含むことを示す。次いで、信号は、セットＳがクエリエレメントｋを含むことを示す検索要求のソースに出力され得る（ステップ６２４）。エレメントポインタによって指し示された情報を用い得る他の適切なアクションがまた、ステップ６２４で実施され得る。
【００６７】
上記されたように、図６で示された方法は、第１の検索技術を適用する本発明の実施形態に従うクエリエレメントを検索するように用いられ得る。例えば、図６で示された方法は、図４で示されたツリー４００のクエリエレメント「２３４」を検索するように適用され得る。処理の開始して、エレメント「２３４」がセットＳ＝｛「１」、「１２３」、「２１」、「１３」、「１３４」、「２１」、「２５」｝にあるかどうかを判定するように検索を要求するステップ６０２において、クエリ要求が受け取られ得る。ステップ６０４を通して、ＣｕｒｒＰｔｒは、ルートノード４０２に初期化される。変数ｉは、（ステップ６０６を通して）１に設定される。変数ｃは、クエリエレメント「２３４」の第１の文字である「２」に初期化される。変数ｐは、２（領域Σに対する文字セットにおける文字「２」の位置）に初期化される。次いで、本発明は、ノード４０２のＡｒｒａｙ［２］がＮＵＬＬであるかどうかをチェックする。ノード４０２のＡｒｒａｙ［２］が（図４で示されるような）ＮＵＬＬではないので、ＣｕｒｒＰｔｒは、ステップ６１６を通してノード４０６（すなわち、ノード４０２のＡｒｒａｙ［２］によって指し示されたノード）を指し示すように設定される。次いで、エレメント「２３４」のエンドに到達したかどうかを理解するために、（ステップ６１８を通して）チェックが行われる。エンドに到達していないので、変数ｉの値は、１を加えて２となり、処理はステップ６０８に続く。ここで、変数ｃは、クエリエレメント「２３４」の第２の文字である「３」に設定される。変数ｐは、３（領域Σに対する文字セットにおける文字「３」の位置）に初期化される。次いで、本発明は、ノード４０６のＡｒｒａｙ［３］がＮＵＬＬであるかどうかをチェックする。（図４で示されるように）ノード４０２のＡｒｒａｙ［２］がＮＵＬＬであるので、Ａｒｒａｙ［２］は、ストリング「２３４」がセットＳに含まれないことを示す。次いで、（ステップ６１４を通して）セットＳがクエリエレメント「２３４」を含まないことを示す検索要求のソースに信号が出力され得る。上記されたように、（ビットアレイＡｒｒａｙ［］の値をチェックする）２つの文字のみの比較は、エレメント「２３４」がセットＳに含まれるかどうかを判定するために必要とされる。
【００６８】
別の実施例として、検索クエリエレメントは、ステップ６０２において、検索クエリで受信され得る「１２」であると考える。ステップ６０４により、ＣｕｒｒＰｔｒがルートノード４０２に初期化される。変数ｉは１に設定される（ステップ６０６により）。変数ｃは、クエリエレメント「１２」の第１文字である「１」に初期化される。変数ｐは１に初期化される（領域Σに対する文字セットにおける文字「１」の位置）。次いで、本発明は、ノード４０２のＡｒｒａｙ［１］がＮＵＬＬであるか否かをチェックする。（図４に示されるように）ノード４０２のＡｒｒａｙ［１］がＮＵＬＬでないので、ステップ６１６により、ＣｕｒｒＰｔｒがノード４０４（すなわちノード４０２のＡｒｒａｙ［１］によって指し示されるノード）を指し示すように設定される。（ステップ６１８により）次いでエレメント「１２」の終わりが達されるか否かを見るためにチェックがされる。終わりが達されていないので、変数ｉの値が１だけ増やされ２になり、処理がステップ６０８に回帰され、これにより変数ｃは、クエリエレメント「１２」の第２の文字である「２」に設定される。変数ｐは２に初期化される（領域Σに対する文字セットにおける文字「２」の位置）。次いで、本発明は、ノード４０４のＡｒｒａｙ［２］がＮＵＬＬであるか否かをチェックする。（図４に示されるように）ノード４０４のＡｒｒａｙ［２］がＮＵＬＬでないので、ステップ６１６により、ＣｕｒｒＰｔｒがノード４０８（すなわちノード４０４のＡｒｒａｙ［２］によって指し示されるノード）を指し示すように設定される。次いで、（ステップ６１８によって）エレメント「１２」の終わりが達されるか否かを見るためにチェックされる。終わりが達されるので、本発明は、（ステップ６２２によって）ノード４０８のエレメントポインタがヌル値に設定されるか否かをチェックする。（図４に示されるように）ノード４０８のエレメントポインタがＮＵＬＬに設定されるので、このポインタは、ストリング「１２」がセットＳに含まれないことを示す。次いで、信号は検索リクエストのソースに出力され得る。（ステップ６１４によって）セットＳがクエリエレメント「１２」を含まないことを示す。上述のように、エレメント「１２」がセットＳに含まれるか否かを決定するために、二つの文字比較のみが必要とされる。
【００６９】
第３の例として、検索クエリが「１３４」であると仮定する。フローチャート６００に説明されるように、処理がルートノード４０２で開始する。次いで、ルートノードおよび次のノードのアレイポインタは、クエリエレメントがセットＳにあるか否かを決定するために移動される。例えば、エレメントクエリ「１３４」について、ルートノード４０２のＡｒｒａｙ［１］がノード４０４に達するように移動される。次いで、ノード４０４のＡｒｒａｙ［３］がノード４１０に達するように移動される。次いで、ノード４１０のＡｒｒａｙ［４］がノード４１８に達するように移動される。次いで、本発明は、（ステップ６２２によって）ノード４１８のエレメントポインタがＮＵＬＬに設定されるか否かをチェックする。ノード４１８のエレメントポインタがＮＵＬＬに設定されていないので、このポインタはエレメント「１３４」がセットＳに含まれることを示す。信号が（ステップ６２４によって）セットＳがクエリエレメント「１３４」を含むことを示しす検索リクエストのソースに出力され得る。次いで、本発明は適切なアクションを実行し得る。上記で説明されたように、三つの比較のみが、エレメント「１３４」がセットＳに含まれるか否かを決定するために必要とされる。
【００７０】
概して、第１の検索技術によると、所与の検索クエリエレメントｋに「ｋｌｅｎｇｔｈ」個の文字がある場合、図６に示される方法を適用することにより、ｋがセットＳに含まれるか否かを決定するために、せいぜい「ｋｌｅｎｇｔｈ」個の文字比較を行う。最悪のケースシナリオにおいて、ｋｌｅｎｇｔｈがＺに等しい（ここで「Ｚ」は領域Σのエレメントの可能な最大な長さである）。従って、せいぜい一つのエレメント比較が必要とされる。従って、検索を実行するために必要とされる比較の数はクエリエレメントの長さに比例する。従って、上記で説明された第１の検索技術は、特定の検索クエリエレメントが特定のデータセットにあるか否かを決定するために必要とされる比較の数に関して最適化される。第１の検索技術は、メモリ内検索について高度に最適化される。比較の数はセットＳのサイズに依存していない。所与のクエリエレメントがデータ構造内に存在しない（すなわちセットＳのメンバでない）場合、（アレイポインタの）数ビット比較のみがエレメントがセットＳにないことを決定するために必要とされる。これは、複数のエレメント比較を必要とし得る従来の検索技術と対照的である。
【００７１】
第１の検索技術の教示に従って構築されたデータ構造はまた、エレメントの前置きマッチングに用いられ得る。前置きマッチングは、所与の（またはユーザ特定の）クエリサブストリングで始まる全てのストリングを見出すプロセスを参照する。例えば、セットＳがＵＲＩを表示するストリングを含む場合、ユーザは、（クエリを表示する）「ｈｔｔｐ：／／ｗｗｗ．ａｒｃｏｔ．」で始まる全てのＵＲＩを決定することを望み得る。これは、第１の技術に従って構築されたデータ構造を用いて実行され得る。上述された態様で、クエリに含まれた文字に基づいて、ルートノードで始まるデータ構造が特定レベル「Ｌ」で特定のノードに到達するように移動される。特定のノードでルーティングされた全てのサブツリーは、「ｈｔｔｐ：／／ｗｗｗ．ａｒｃｏｔ．」で始まるセットＳのエレメント（または任意の他のクエリストリング）を表示する。例えば、図３に示されるように、サブツリー３２２は、エレメントの第１の位置にあるＡｒｒａｙ［２］に対応する文字とエレメントの第２の位置にあるＡｒｒａｙ［１］に対応する文字とを有する、セットＳのエレメントに対応する。同様に、サブツリー３２４は、エレメントの第１の位置にあるＡｒｒａｙ［２］に対応する文字とエレメントの第２の位置にあるＡｒｒａｙ［ｍ］に対応する文字とを有する、セットＳのエレメントに対応する。サブツリー３３２は、エレメントの第１の位置にあるＡｒｒａｙ［ｍ］に対応する文字とエレメントの第２の位置にあるＡｒｒａｙ［２］に対応する文字とを有する、セットＳのエレメントに対応する。従って、第１の技術に従って構築されたデータ構造は前置きマッチングを容易にする。
【００７２】
第１の検索技術はまた、ツリーデータ構造にエレメントを挿入する演算（「インサート」演算と呼ばれる）と、ツリーデータ構造からエレメントを削除する演算（「デリート」演算と呼ばれる）を容易にする。「インサート」演算は、新しいエレメントがセットＳに追加されるときに必要とされ得、一方で、「デリート」演算は、エレメントがセットＳから除去されるときに必要とされ得る。
【００７３】
「インサート」演算は、本発明の実施形態に従う以下の態様で達成され得る。新しいエレメント「Ｒ」がセットＳに挿入されると仮定する。ここで、Ｒ＝ｃ１ｃ２．．．ｃｑ、いくつかのｑ≦Ｚ（「Ｚ」は領域Σのエレメントの最大可能な長さ）、およびｃｉ∈Σ，１≦ｉ≦ｑ。挿入演算は、図５に示されるフローチャートを用いて実行され得る（一つのエレメントのみが挿入される予定の場合、ステップ５３２が必要とされない）。例えば、ツリーのルートノードで始まると、データ構造ツリーは、アレイポインタＡｒｒａｙ［ｃ１］，Ａｒｒａｙ［ｃ２］，Ａｒｒａｙ［ｃ３］，．．．，Ａｒｒａｙ［ｃｑ］を用いて横切られ、特定のノードに達する。次いで、特定のノードのエレメントポインタが新しいエレメント「Ｒ」または新しい「Ｒ」に対応する情報に向けられる。１以上の新しい中間ノードが挿入を達するように作製される必要がある。
【００７４】
「デリート」演算は、本発明の１実施形態に従う以下の態様で達成され得る。（上記で挿入された）エレメント「Ｒ」は、ここでセットＳから削除されると仮定する。ツリーデータ構造からエレメントを削除するために、ツリーのルートノードで始まり、アレイポインタＡｒｒａｙ［ｃ１］，Ａｒｒａｙ［ｃ２］，Ａｒｒａｙ［ｃ３］，．．．，Ａｒｒａｙ［ｃｑ］が特定のノードに達するように移動される。特定のノードのエレメントポインタが削除されるべきエレメントを指し示す。次いで、エレメントポインタは、ＮＵＬＬに設定され、セットＳからエレメント「Ｒ」の削除を完了する。
【００７５】
第１の検索技術を適用する本発明の１実施形態に従って、「インサート」および「デリート」演算がＯ（Ｒｌｅｎｇｔｈ）時間をとる。ここで「Ｒｌｅｎｇｔｈ」とは挿入または削除されるべきエレメントの長さである（すなわちＲｌｅｎｇｔｈ＝｜Ｒ｜）。さらに、インサートおよびデリート演算が並列に実行され得る。
【００７６】
従って、上述のツリーデータ構造等のデータ構造を用いて、「サーチ」，「インサート」，および「デリート」演算は、クエリエレメントまたは挿入または削除されるべきエレメント内の文字の数に比例する時間で実行され得る。特に、所与のクエリエレメントｋが「ｋｌｅｎｇｔｈ」個の文字から構成される場合、演算は、せいぜい「ｋｌｅｎｇｔｈ」個の文字比較を用いて実行され得る。
【００７７】
上述の第１の検索技術はまた、セットＳが１エレメントの複数のコピー（例えば二重、三重等）を含む状況で用いられ得る。このシナリオにおいて、複数のコピーを有するエレメントに対応するノードのエレメントポインタは、エレメントの複数のコピーに対応する構造のリンクされたリストを指し示し得るか、または照会し得る。上記データ構造によって用いられるメモリはＯ（Ｄ）ノードである。ここでＤはセットＳの全てのエレメントにある文字の総計、すなわち
【００７８】
【数１】
2004531789.tif 000003
である。従って、用いられるメモリはＯ（Ｄｍ）バイトである。このメモリ限界は、以下に説明される技術を用いてさらに低減され得る。
【００７９】
メモリ要件を低減するために、ツリーデータ構造が用いられ得る。ツリーのそれぞれのノードに対するＡｒｒａｙ［］ポインタのアレイは、（２−３ツリー、赤−黒ツリー（ｒｅｄ−ｂｌａｃｋ  ｔｒｅｅ）等）バランスツリー（ｂａｌａｎｃｅｄ  ｔｒｅｅ）と置き換えられる。「ポインタのアレイ」ツリーの場合において、ツリーのそれぞれのノードに必要とされるメモリがｍであった。他方、メモリを節約する目的で改良されたバージョンのそれぞれのノードに必要とされるメモリがＯ（ｑ）に過ぎない。ここでｑはそのノードの非ＮＵＬＬポインタの数である。従って、全ツリーに必要とされるメモリはＯ（Ｄ）バイトだけである。
【００８０】
また、前回のケースでは、ノードの任意のポインタを得ることはＯ（１）回で行われ得る。改変された「メモリセーバー」バージョンでは、それぞれのポインタアクセスはＯ（ｌｏｇｑ）回必要である。ここでｑはそのノードの非ＮＵＬＬポインタの数である。従って、上記に基づいて、本発明の実施形態に従って、ディクショナリーは、それぞれの演算がＯ（Ｈ  ｌｏｇ  ｍ）回必要であるように実施され得る。ここで「Ｈ」は検索クエリエレメントの文字の数であり、ｍ＝｜Σ｜である。本発明の本実施形態に従って必要とされるメモリはＯ（Ｄ）バイトだけである。ここで
【００８１】
【数２】
2004531789.tif 000004
である。
【００８２】
（ｌｏｇ  ｍ）の典型的な値は５または６である。従って、「メモリセーバー」技術は、（最悪のケース）、従来の検索技術の平均ケース性能と非常に競合的な性能を有する。
【００８３】
（第２の検索技術）
このセクションは、効率の高い態様で検索を実行する一方で、検索を実行するために必要とされるメモリリソースを最小限にする第２の検索技術を説明する。上述された第１の検索技術に関して、以下で説明される第２の検索技術は、任意の領域Σからの検索クエリエレメントｋ（すなわちｋ∈Σ）が、「ｎ」個のエレメント「ｋ１，ｋ２，．．．ｋｎ」（すなわちＸ＝（ｋ１，ｋ２，．．．，ｋｎ））を含むセットＳのメンバ（すなわちｋ∈Σである場合）であるか否かを決定するように用いられ得る。領域Σのそれぞれのエレメント（次には、セットＳのそれぞれのエレメント）は、領域Σの特定の文字セットからの１以上の文字を含み得る。
【００８４】
第２の検索技術は、図１に示されたコンピュータシステム１００等のコンピュータシステムで具体化され得る。図１が本発明を組み込んでいる実施形態の例示に過ぎず、請求項に記載された本発明の範囲を限定しないことは明らかであるべきである。当業者は、他の変更、改変および代替を理解する。
【００８５】
上述のように、第２の検索技術の処理は図２に示される二つのフェーズを含む。第１フェーズの間、データ構造または他の同様のメモリ構造が生成され、第２フェーズで実行される検索演算を容易にする。第１フェーズの間に生成されたデータ構造は検索されるべきデータセットに含まれるエレメントに基づいている（すなわちデータ構造はセットＳのエレメントに基づいて構築される）。第２の検索技術を実施する本発明の実施形態に従って、第１フェーズの間、コンピュータシステム１００はセットＳのエレメントを識別する情報を受信し得る（ステップ２０２）。エレメント自体がコンピュータシステム１００のメモリサブシステムまたはコンピュータシステム１００にアクセス可能ないくつかのメモリに格納され得る。次いで、ステップ２０２で受信された情報に基づいて、コンピュータシステム１００は、データ構造（任意の他のメモリストレージ構造）を構築し得、第２フェーズで実行される検索を容易にし得る（ステップ２０４）。
【００８６】
データ構造の様々な異なる種類は、検索演算を容易にするために用いられ得る。特定のデータ構造が以下で説明されるが、第２の検索技術の範囲はそのデータ構造に制限されない。１実施形態においてデータ構造がコンピュータシステム１００によって生成される一方で、本発明の別の実施形態では、セットＳのエレメントに関連されるデータ構造カプセル化情報が別のコンピュータシステムによって構築され得、コンピュータシステム１００に提供され得る（例えば、データ構造は、別のシステムまたはデバイスによって生成され得、コンピュータシステム１００にアクセス可能なメモリに格納され得る）。次いで、コンピュータシステム１００は、第２の検索技術に従って検索を実行するように格納されたデータ構造にアクセスし得る。
【００８７】
セットＳのエレメントに関連する情報を格納しているデータ構造が第１フェーズに従って構築された後、次いで、データ構造は、第２の検索技術を用いて、第２フェーズで実行される検索を容易にするために、用いられる。本発明の実施形態に従って、第２フェーズの間、コンピュータシステム１００は、検索クエリ「ｋ」がセットＳに含まれるか否かを決定するために検索リクエストを受信し得る（ステップ２０６）。検索クエリは、コンピュータシステム１００に接続される一つ以上の入力デバイスを用いてコンピュータシステム１００のユーザによって特定され得る。あるいは、検索クエリはまた、構成され得、コンピュータシステムで実行するプロセスから、コンピュータシステム１００に接続されたデバイスまたはシステム（例えばネットワークインターフェース１０６を介してコンピュータシステム１００に接続されたシステム）から、および／または他のシステムまたはプロセスから、受信され得る。
【００８８】
次いで、第２の検索技術に従って、ステップ２０４で生成されたデータ構造は、ステップ２０６で受信された検索リクエストにて識別されたエレメントｋがセットＳに含まれるか否かを決定する（ステップ２０８）ために用いられる。次いで、コンピュータシステム１００は、エレメントｋがセットＳに見出されたか否かを示す（ステップ２１０）信号を出力し得る。コンピュータシステム１００はまた、ステップ２０８の結果に基づいて１以上のアクションを実行するように構成され得る。
【００８９】
図７は、第２の検索技術を適用する本発明の実施形態に従って検索演算を容易にするために、（図２のステップ２０４で）構築され得るデータ構造７００を示す。図７に示されたデータ構造７００は、本発明を組み込んでいる実施形態の例示に過ぎず、請求項に記載された発明の範囲を限定しない。当業者は、変更、改変および代替を認識する。
【００９０】
図７に示されるように、データ構造７００は、Ｚ個のノードまたはメモリ構造（７０２−１〜７０２−Ｚ）を含む。Ｚは領域Σのエレメントの最大可能な長さである。それぞれのノード７０２は、セットＳのエレメント内の特定の位置にある文字に対応する。例えば、第１のノード７０２−１はエレメントの第１の位置にある文字に対応し、第２のノード７０２−２はエレメントの第２の位置にある文字に対応し、第３のノード７０２−３はエレメントの第３の位置にある文字に対応するなど。従って、Ｚ番目のノード７０２−ＺがエレメントのＺ番目の位置にある文字に対応する。
【００９１】
それぞれのノード７０２はｍスロット（７０４−１〜７０４−ｍ）を含む。ｍは領域Σの文字セットにある文字の数である。それぞれのスロット７０４は領域Σの文字セット内の文字に対応する。例えば、第１のスロット７０４−１は領域Σの文字セットの第１の文字に対応し、第２のスロット７０４−２は領域Σの文字セットの第２の文字に対応し、第３のスロット７０４−３は領域Σの文字セットの第３の文字に対応するなど。例えば、領域Σの文字セットが英語のアルファベット（例えばａ，ｂ，ｃ，．．．，ｚ）から構成される場合、ｍ＝２６。本実施形態において、それぞれのノードは２６個のスロットから構成される。第１のスロット７０４−１は文字「ａ」に対応し、第１のスロット７０４−２は文字「ｂ」に対応し、第１のスロット７０４−３は文字「ｃ」に対応するなど。
【００９２】
図７に示される実施形態において、それぞれのスロット７０４は、順に、（ｍ＋１）ビット位置を含むビットアレイ７０６（Ａｒｒａｙ［］として参照される）を含む。ｍは領域Σの文字セット内の文字の数である。それぞれのビットアレイＡｒｒａｙ［］７０６の最初のｍビットは領域Σの文字セットの文字に対応する。例えば、Ａｒｒａｙ［１］は領域Σの文字セットの第１の文字に対応し、Ａｒｒａｙ［２］は領域Σの文字セットの第２の文字に対応し、Ａｒｒａｙ［３］は領域Σの文字セットの第３の文字に対応するなど。例えば、領域Σの文字セットが英語のアルファベット（例えばａ，ｂ，ｃ，．．．，ｚ）から構成される場合、ｍ＝２６。本実施形態において、ビットアレイＡｒｒａｙ［］は、２７ビットを含む。Ａｒｒａｙ［１］は文字「ａ」に対応し、Ａｒｒａｙ［２］は文字「ｂ」に対応し、Ａｒｒａｙ［３］は文字「ｃ」に対応するなど。それぞれのビットアレイの最後のビット（すなわち、Ａｒｒａｙ［ｍ＋１］）は、エレメントの終わりを示すために用いられる。
【００９３】
本発明の実施形態に従って、それぞれのノードのそれぞれのスロットはまた、セットＳの（単数または複数の）エレメントに関連する情報を格納し得るメモリ位置７０８を含む。メモリ位置７０８は、ポインタまたはリファレンスをテーブルまたはセットＳの（複数の）エレメントに対する情報を格納する他のメモリ構造に格納し得る。あるいは、メモリ位置７０８はヌル（またはゼロ）値を格納し得る。メモリ位置７０８はセットＳの１以上のエレメントに関連する情報を格納または指し示すので、メモリ位置７０８は、本明細書後半で、特定のノードのスロットの「エレメントポインタ」と呼ばれる。
【００９４】
次の表記は第２の検索技術を説明する目的で用いられる。図７に示されたデータ構造は、ＤＳ［１：Ｚ］［１：ｍ］によって示される。詳細には、ＤＳ［ｘ］［ｙ］は、データ構造７００のｘ番目のノードにおけるｙ番目のスロット（すなわちスロットが領域Σの第ｙの文字に対応する）を示す。
【００９５】
データ構造を構築するために、データ構造７００内の全てのノードに対する全てのスロットのビットアレイは、ヌル（またはゼロ）値に初期化される。セットＳからエレメントＲ（いくつかのｑ≦Ｚに対してＲ＝ｃ１ｃ２．．．ｃｑで、「Ｚ」は領域Σのエレメントの最大可能な長さであり、ｃｉ∈Σ，１≦ｉ≦ｑである）を挿入するために、スロットＤＳ［１］［ｃ１に対応するスロット］のＡｒｒａｙ［文字セットのｃ２の位置］（すなわち文字ｃ２に対応するビット）内のビットが非ヌル値に設定され（例えば１に設定され）、スロットＤＳ［２］［スロットはｃ２に対応する］のＡｒｒａｙ［文字セットのｃ３の位置］（すなわち文字ｃ３に対応するビット）内のビットが非ヌル値に設定され、．．．スロットＤＳ［ｑ−１］［スロットはｃｑ−１に対応する］のＡｒｒａｙ［文字セットのｃｑの位置］（すなわちビットは文字ｃｑに対応する）内のビットが非ヌル値に設定され、スロットＤＳ［ｑ］［スロットはｃｑに対応する］のＡｒｒａｙ［ｍ＋１］内のビットが非ｎｕｌｌ値に設定される。スロットＤＳ［ｑ］［ｃｑに対応するスロット］のエレメントポインタは更新され、エレメントＲに関連する情報を指し示すか、エレメントＲに関連する情報を照会する。
【００９６】
図８は、第２の検索技術を適用して本発明の実施形態に従って検索を容易にするための、データ構造を構築する方法の高度に単純化されたフローチャート８００である。図８に示された方法は、コンピュータシステム１００、コンピュータシステム１００に接続されたハードウェアモジュールまたはこれらの組み合わせ上で実行するソフトウェアモジュールによって実行され得る。図８に示されたフローチャート８００は、本発明を組み込む実施形態の単なる例示であり、請求項に記載された本発明の範囲を限定しない。当業者は、変更、改変および代替を認識する。
【００９７】
処理は、ｍ（ｍは領域Σの文字セットの文字の数である）個のスロットを含むＺ（Ｚは領域Σのエレメントの最大の長さである）個のノードを生成することによって初期化され、それぞれのスロットは、［ｍ＋１］個のメモリ位置およびエレメントポインタを含むビットアレイＡｒｒａｙ［］を含む（ステップ８０２）。ステップ８０２の一部として、ビットアレイ位置およびエレメントポインタがヌル（またはゼロ）値に全て初期化される。
【００９８】
数値変数「ｍ」は、領域Σの文字セットの文字の数に設定される（ステップ８０４）。次いで、データ構造に挿入されるべきセットＳのエレメント（またはエレメントを識別する情報）がアクセスされる（ステップ８０６）。セットＳの第１のエレメントは、図８に示されたフローチャートの第１のパスの間にアクセスされる。セットＳの他のエレメント（または、他のエレメントを識別する情報）は、セットＳの全エレメントが処理されるまでの次のパスの間にアクセスされる。
【００９９】
次いで、数値変数「ｑ」は、ステップ８０６においてアクセスされるエレメントの長さ（すなわちエレメント内の文字数）である（ステップ８０８）。次いで、カウンタ変数「ｉ」が１に初期化される（ステップ８１０）。この変数は、データ構造に挿入されるべきエレメントの様々な文字を移動するように用いられる。次いで、文字変数「ｃ１」は、ステップ８０６においてアクセスされるエレメントのｉ番目の位置にある文字に初期化される（ステップ８１２）。次いで、数値変数「ｐ１」は、領域Σの文字セットに変数ｃ１に格納される文字の位置に初期化される（ステップ８１４）。例えば、文字セットが英語のアルファベットのセットである場合、次いで、変数ｃ１が文字「ａ」で格納される場合、変数ｐ１は１に設定され、次いで、変数ｃ１が「ｆ」で格納される場合、変数ｐ１は６に設定され、変数ｃ１が文字「ｚ」で格納される場合、変数ｐ１が２６に設定されるなど。
【０１００】
変数ｉに格納された値がｑの値に等しいか否かを決定するためにチェックが為される（ステップ８１６）。これは、ステップ８０６でアクセスされるエレメントの終わり（すなわちエレメントの最後の文字）が到達されたか否かを決定するために為される。ｉがｑに等しいことがステップ８１６で決定される（すなわちエレメントの終わりが到達される）場合、スロットＤＳ［ｉ］［ｐｌ］のＡｒｒａｙ［ｍ＋１］が非ヌルに設定される（ステップ８１８）。スロットＤＳ［ｉ］［ｐｌ］のエレメントポインタがステップ８０６でアクセスされたエレメントまたはステップ８０６にてアクセスされるエレメントに関連する情報を指し示すか、または照会するように設定される（ステップ８２０）。次いで、本発明は、セットＳの全てのエレメントが処理されたか否かをチェックする（ステップ８２２）。セットＳの全てのエレメントが処理されていない場合、処理がステップ８０６で続行し、セットＳの次の処理されていないエレメントがアクセスされる。しかし、セットＳの全てのエレメントが処理された場合、図８に示されたプロセスは終了する。
【０１０１】
ｉがｑに等しくないとステップ８１６で決定される（すなわちステップ８０６でアクセスされるエレメントの終わりが到達されていない）場合、文字変数「ｃ２」がステップ８０６でアクセスされたエレメントの（ｉ＋１）番目の位置の文字に設定される（ステップ８２４）。次いで、数値変数「ｐ２」は、領域Σの文字セット内の変数ｃ２によって格納された文字の位置に設定される（ステップ８２６）。次いで、スロットＤＳ［ｉ］［ｐ１］のＡｒｒａｙビットＡｒｒａｙ［ｐ２］が非ヌル値に設定される（ステップ８２８）。次いで、変数ｉの値が１だけ増やされる（ステップ８３０）。次いで、変数ｃ１は、変数ｃ２に格納された文字に設定される（ステップ８３２）。変数ｐ１は、変数ｐ２の値に設定される（ステップ８３４）。次いで、処理が上述のようにステップ８１６で続行する。
【０１０２】
次いで、図８に示されたフローチャートに従って構築されたデータ構造は、第２の検索技術を適用することによって検索を容易にするために用いられ得る。データ構造は、ストレージサブシステムに格納され得る。データ構造は検索演算の間、ストレージサブシステムからアクセスされ得る。本発明の教示に従って、図８に示されたフローチャートに従って構築されたデータ構造は、エレメントが挿入される順番と無関係であり、挿入されるべきエレメント、領域Σの文字セットの文字の数（「ｍ」）および領域Σのエレメントの最大可能な長さ（「ｚ」）のみに依存する。データ構造は、二重の情報が任意のノードに格納されないように効率の高い空間である。
【０１０３】
データ構造の最大サイズは固定され、小さく、セットＳのエレメントの数と独立である。図７に示されるデータ構造に関して、用いられるメモリは、ビットアレイポインタに対してＺｍ（ｍ＋１）であり、エレメントポインタに対して２Ｚｍバイトである（「Ｚ」は領域Σの最大可能な長さであり、「ｍ」が領域Σの文字セットの文字の数である）。例として、領域Σのエレメントの最大長さが２５５であり（例えば、領域Σがコンピュータベースのファイルシステム内のストリングに対応する場合）、文字セットのサイズが９１である場合、データ構造に必要とされるメモリは約３００ＫＢである。データ構造の効率の高い表示が与えられると、データ構造は、検索リクエストの効率の高い処理のために、複数の位置（例えば、ウェブサーバ、プロキシサーバ等）でキャッシュされ得る。
【０１０４】
図９は、本発明の実施形態に従って、ドメインΣに属するエレメントを含む特定のセットＳに対する第二の検索技術の教示に従って構築されたデータ構造９００を示す。図９で示された実施形態に関して、ドメインΣに対する文字のセットは、５つの文字、すなわち「１」、「２」、「３」、「４」および「５」からなり、ドメインΣにおけるエレメントの最大の長さが４であることが仮定される。さらに、セットＳは、続く８エレメントＳ＝（「１」、「１２３」、「１３」、「２１」、「１３４」、「４３２１」、「２５」、「３４２１」）を含むことが仮定される。
【０１０５】
図９に示されるように、同じ長さおよび同じ最後の文字を有するエレメントは、同じエレメントポインタにマッピングされる。例えば、図９に示されるようにエレメント「４３２１」および「３４２１」は、同じエレメントポインタ９０２にマッピングされる。本発明の一実施形態によると、エレメントは、エレメントポインタ９０２によって指し示されたテーブル、リンクされたリストまたは他のメモリ構造に格納され得る。
【０１０６】
図８において示されたフローチャートに従って構築されたデータ構造は、次いで、特定のクエリエレメントｋがセットＳのエレメントであるかどうかを判定するために使用され得る。ここで、ｋは、任意のｑ≦Ｚに対して（ここでＺはドメインΣにおけるエレメントの可能な限りの最大の長さである。）ｋ＝ｃ１ｃ２．．．ｃｑであり、ｃｉ∈Σ、１≦ｉ≦ｑである。本発明の一実施形態によれば、検索はビットアレイにおける次のビットがノンヌル値である場合、照合によって実行され得る。非ヌル値は、その命令において、スロットＤＳ［ｑ］［ｃｑに対応するＳｌｏｔ］のＡｒｒａｙ［ｍ＋１］、スロットＤＳ［ｑ−１］［ｃｑ−１に対応するＳｌｏｔ］のＡｒｒａｙ［文字のセットにおけるｃｑの位置］（すなわち、文字ｃｑに対応するビット）．．．、スロットＤＳ［２］［ｃ２に対応するＳｌｏｔ］のＡｒｒａｙ［文字セットにおけるｃ３の位置］（すなわち、文字ｃ３に対応するビット）およびスロットＤＳ［１］［ｃ１に対応するスロット］のＡｒｒａｙ［文字のセットにおけるｃ２の位置］（すなわち、文字ｃ２に対応するビット）。検索が任意のこのビットにおいて失敗する場合（すなわち、任意のビットがヌル値にセットされる場合）、クエリエレメントｋは、セットＳの成分ではないことが判定され得る。次いで、上記のビットの全てが設定される場合、クエリエレメントｋはセットＳに含まれ得る事が示される。次いで、スロットＤＳ［ｑ］［ｃｑに対応するＳｌｏｔ］のエレメントポインタは、エレメントｋまたはエレメントｋに関連のある情報に指し示すかどうかを判定するために使用される。エレメントポインタが、一つ以上のエレメントを含むテーブルまたはリンクされたリスト（例えば、クエリエレメントｋとして同じ長さおよび同じ最後の文字を有するエレメント）に指し示される場合、テーブルまたはリンクされたリストは、次いで、エレメントｋがセットＳのエレメントであるかどうかを判定するために検索され得る。
【０１０７】
図１０は、セットＳが第二の検索技術に適用される本発明の一実施形態に従った検索クエリエレメントｋを含むかどうかを判定する方法の高レベルで簡易化されたフローチャート１０００である。図１０において示された方法は、コンピュータシステム１００上で実行されるソフトウェアモジュール、コンピュータシステム１００に接続されたハードウェアモジュールまたはその組み合わせによって実行され得る。図１０において示されたフローチャート１０００は、本発明を援用する一実施形態の単なる図であり、請求項において列挙されたような本発明の範囲を限定しない。ある当業者は、変形、改良、代替を理解する。
【０１０８】
図１０に示されたように、処理は、セットＳが検索クエリエレメントｋを含むかどうか判定するためにコンピュータシステム１００が検索要求を受け取る時に初期化される（ステップ１００２）。前に図示したように、検索要求は、コンピュータシステム１００に接続された一つ以上の入力デバイスを使用してコンピュータシステム１００のユーザによって指定され得る。検索クエリはまた、コンピュータシステム上で実行されるプロセスから、コンピュータシステム１００接続されるデバイスまたはシステム（例えば、ネットワークインターフェース１０６を介するコンピュータシステム１００に接続されているシステム）から、および／または他のシステムまたはプロセスから構成され受け取られ得る。
【０１０９】
数値変数「ｍ」は、次いで、ドメインΣに対する文字セット内の文字の数に設定される（ステップ１００４）。他の数値変数「ｑ」は、クエリエレメントｋの長さに（すなわち、クエリエレメントｋにおける文字の数に）初期化される（ステップ１００６）。数値変数「ｉ」は、変数ｑによって格納される値に設定される（ステップ１００８）。この変数は、クエリエレメントの種々の文字を移動するために使用される。
【０１１０】
次いで、文字変数「ｃｌ」は、クエリエレメントｋのｉ番目の位置内の文字に初期化される（ステップ１０１０）。次いで、数値変数「ｐｌ」は、ドメインΣに対する文字設定において変数ｃｌによって格納された文字の位置に初期化される（１０１２）。例えば、文字セットが英語のアルファベットのセットであった場合、次いで変数ｃｌが数値「ａ」を格納した場合、変数ｐｌは１に設定され、変数ｃｌが文字「ｆ」を格納した場合、次いで変数ｐｌは、６に設定され、変数ｃｌが数値「ｚ」を格納した場合、次いで変数ｐｌは、２６に設定されるなどである。数値変数「Ｈ」は変数ｐｌによって格納される値に設定される（ステップ１０１４）。
【０１１１】
チェックが、スロットＤＳ［ｉ］［ｐｌ］のビットＡｒｒａｙ［ｍ＋１］がヌルに設定されるかどうかを判定するためになされる（ステップ１０１６）。スロットのＡｒｒａｙ［ｍ＋１］がヌル（またはゼロ）値に格納される場合、セットＳはクエリエレメントｋを含まないことを示す。信号は、セットＳがクエリエレメントｋを含まないことを示す（ステップ１０１８）検索要求のソースに出力され得る。他の適切な処理もまた、ステップ１０１８において実行され得る。
【０１１２】
スロットＤＳ［ｉ］［ｐｌ］のビットＡｒｒａｙ［ｍ＋１］がノンヌル値を格納することがステップ１０１６において判定される場合、次いで、チェックは、変数ｉが１に等しくなるかどうかを見るためになされる（ステップ１０２０）。ｉが１に等しい場合、クエリエレメントｋの全ての文字が処理されたことを示す。次いで、スロットＤＳ［ｑ］［Ｈ］のエレメントポインタが、それがエレメントｋまたはエレメントｋに関連した情報に指し示すまたは参照するかどうかを見るためにチェックされる（ステップ１０２２）。上述のように、エレメントポインタは、クエリエレメントと同じ長さであり、クエリエレメントと同じ最後の文字を有する複数のエレメントに指し示し得る。エレメントポインタが、一つ以上のエレメントを含むリストまたはテーブルに指し示す場合、次いでステップ１０２２においてエレメントのリストまたはテーブルは、クエリエレメントｋがリストまたはテーブルに含まれるかどうかを判定するために検索される。スロットＤＳ［ｑ］［Ｈ］のエレメントポインタがエレメントｋ（またはエレメントｋに関する情報）に指し示さない場合、またはエレメントポインタがエレメントｋを含まないエレメントのリストまたはテーブルに指し示す場合、次いで信号は、セットＳがステップ１０１８に従ってクエリエレメントｋを含まないことを示す検索要求のソースに出力され得る。他の適切な処理はまた実行され得る。スロットＤＳ［ｑ］［Ｈ］のエレメントポインタがエレメントｋ（またはエレメントｋに関する情報）に指し示す場合、またはエレメントポインタがエレメントｋを含むエレメントのリストまたはテーブルに指し示す場合、次いで信号は、セットＳがクエリエレメントｋを含むことを示す検索要求のソースに出力され得る（ステップ１０２４）。他の適切な処理はまた、ステップ１０２４において実行され得る。
【０１１３】
ステップ１０２０に戻って参照して、変数ｉが１でないと判定される場合（すなわち、エレメントｋの全ての文字が処理されなかった場合）、次いで変数ｉの値は、１だけ減少される（ステップ１０２６）。文字変数「ｃ２」は、次いでクエリエレメントｋのｉ番目の位置における文字に初期化される（ステップ１０２８）。数値変数「ｐ２」は、次いで、ドメインΣに対する文字セット内の変数ｃ２によって格納される文字の位置に初期化される（ステップ１０３０）。チェックは、スロットＤＳ［ｉ］［ｐ２］のビットＡｒｒａｙ［ｐ１］がヌルに設定されているかを判定する（ステップ１０３２）。スロットのＡｒｒａｙ［ｐ１］がヌル（またはゼロ）値を格納する場合、セットＳがクエリエレメントｋを含まないことを示し、信号は、セットＳがステップ１０１８に従ってクエリエレメントｋを含まないことを示す検索要求のソースに出力され得る。他の適切な処理もまた、ステップ１０１８において実行され得る。スロットＤＳ［ｉ］［ｐ２］のＡｒｒａｙ［ｐ１］がノンヌル値を格納する場合、変数ｃ１は次いで、変数ｃ２によって格納される文字に設定され（ステップ１０３４）、変数ｐ１は変数ｐ２の値に設定される（ステップ１０３６）。次いで、処理は、上述のようにステップ１０２０に続く。
【０１１４】
上述のように、セットＳにおける複数のエレメントが同じ長さおよび同じ最後の文字を有する場合、次いで、複数のエレメントは、第二の検索技術の教示に従って確立されたデータ構造の、特定のノードの特定のスロットの同じエレメントポインタにマッピングする。この場合において、エレメントポインタは、テーブル、リンクされたリストおよび同様なものの中のベクトルに指し示し得る。与えられたクエリエレメントｋがエレメントポインタにマッピングする場合、次いで、エレメントポインタによって指し示されたベクトルは、クエリエレメントｋがセットＳの成分であるかどうかを判定するために検索される。このシナリオにおいて、図７において示されたデータ構造は、ハッシュ関数の計算の必要なしに効率的に検索され得る小さなセットに対して検索されるべきその可能なエレメントのセットを効率的に引き下げるという点でハッシュメカニズムと同様に振舞う。
【０１１５】
本発明の教示に従って、いくつかの異なった技術はベクトルを維持するために使用され得る。一実施形態に従って、ベクトルは、格納されたリストとして維持され得るので、バイナリ検索は、クエリエレメントｋがベクトル内に含まれるかどうかを判定するためにベクトルを検索するために利用され得る。他の実施形態に従って、ベクトルは、安定した（ｂａｌａｎｃｅｄ）バイナリツリー（例えば、赤黒ツリー）として維持され得る。このような安定したバイナリツリーはＯ（ｌｏｇＱ）時刻において検索され得る。ここでＱはベクトル内のエレメントの数である。さらに別の実施形態に従って、ベクトルは第一の検索技術の教示に従って確立されたデータ構造（すなわち、図３において示されたデータ構造、および図５において示されたフローチャートに従った確立されたデータ構造）を使用して維持され得る。この実施形態では、ベクトルの検索に必要な時間は、クエリエレメントｋの長さに比例している（すなわち、クエリエレメント内の文字の数に比例）。
【０１１６】
第二の技術に従った検索を実行するために必要とされる比較の数は、クエリエレメントの長さに比例している。従って、上述の第二の検索技術は、特定の検索クエリエレメントが特定のデータセット内にあるかどうかを判定するために必要とされる比較の数に対して最適化される。第二の検索技術は、メモリ内検索に対して高度に最適化される。比較の数は、セットＳの大きさに依存しない。所与のクエリエレメントがデータ構造内に存在しない場合（すなわち、セットＳのエレメントでない場合）、（アレイポインタの）数個のビット比較のみが、エレメントがセットＳ内にないことを判定するために必要とされる。これは、複数のエレメント比較を必要とし得る従来の検索技術と対照的である。
【０１１７】
第二の検索技術の教示に従って確立されたデータ構造は、極端に効果的な検索のための任意のツリーの移動なしに、文字比較を命令することを可能にする。結果として、検索内部のパラレル技術（例えば、バイナリスプリット検索など）はまた、検索を実行するために使用され得る。全てのクエリエレメントのハッシュがハッシュバケットを判定するために計算されることが必要である従来のハッシュベースの検索技術と比較する際、本発明はクエリエレメントの長さのみとして計算されるために任意のハッシュを必要とせず、文字位置はクエリエレメントがセットＳの成分であるかどうかを判定するために使用される。
【０１１８】
上述のように、二つの検索技術がクエリエレメントｋがセットＳ内に含まれるかどうかを判定するために示された。しかしながら，請求項に列挙されたような、本発明の範囲は、上述の検索技術に限定されない。当業者に通常公知の他の検索技術のいくつかはまた、本発明の範囲内に含まれる。
【０１１９】
図１１は、本発明の一実施形態に従った第一および／または第二の検索技術をインプリメントするために使用され得る種々のモジュールおよび／またはエンジンを示す簡易化されたブロック図である。図１１に示されたモジュールは、ソフトウェアまたはハードウェアまたはその組み合わせでインプリメントされ得る。図１１において示されたように、モジュールは、ユーザインターフェース（ＵＩ）モジュール１１０２、データ構造ビルダモジュール１１０４、検索モジュール１１０６および通信モジュール１１０８を含み得る。
【０１２０】
データ構造ビルダーモジュール１１０４は、本発明の教示に従った検索を実行するために使用される一つ以上のデータ構造を確立するために構成され得る。例えば、データ構造モジュール１１０４は、、図３（第一の検索技術に従った）および図７（第二の検索技術に従った）に示されたデータ構造を確立するために構成され得る。データ構造ビルダーモジュール１１０４は、データベース１１１０からセットＳのエレメントに関する情報にアクセスし得る。ネットワーク化された実施形態において、データ構造ビルダモジュール１１０４は、通信モジュール１１０８を介する他のネットワークまたはコンピュータシステムからセットＳに関する情報を受け取っても良いし、アクセスしてもよい。セットＳに関する情報はまた、ユーザインターフェース１１０２を介してユーザによって提供され得る。データ構造ビルダ１１０４によって確立されたデータ構造は、後の使用のためにメモリシステム内に（例えば、コンピュータシステムのＲＡＭ内に）格納され得る。
【０１２１】
検索モジュール１１０６は、検索クエリ内の特定のクエリエレメントが、データ構造ビルダモジュール１１０４によって確立されるデータ構造（複数）を使用して、セットＳに含まれるかどうかを判定するために検索を実行するよう構成され得る。検索モジュール１１０６は、ユーザインターフェースモジュール１１０２を介して検索クエリを受け取り得る。検索は、第一の検索技術、第二の検索技術または他の技術に従って実行され得る。検索モジュール１１０６によって実行された検索の結果は、ユーザインターフェースモジュール１１０２を介してユーザに出力され得る。ネットワーク化された実施形態において、検索モジュール１１０６は、他のコンピュータシステムから、および通信モジュール１１０８を介して検索クエリを受け取り得、検索結果は、通信モジュール１１０８を介して検索要求のソースに通信され得る。ネットワーク環境において、検索モジュール１１０６は、通信モジュール１１０８を介する検索のために使用されたデータ構造にアクセスし得る。検索を実行するために検索モジュール１１０６によって使用されたデータ構造はまた、通信モジュール１１０８を介して外部のコンピュータまたはネットワークから受け取られ得る。
【０１２２】
通信モジュール１１０８は、本発明の教示に従って実行し処理するコンピュータシステムに、および、そこから情報およびデータの通信を容易にするために構成され得る。通信モジュール１１０８は、外部コンピュータシステムおよびネットワークを含む外部エンティティからの検索要求を受け得る。検索を容易にするために使用されるデータ構造はまた、外部エンティティから通信モジュール１１０８によって受け取られ得る。検索モジュール１１０６によって実行される検索の結果は、通信モジュール１１０８によって要求のソースに通信される。
【０１２３】
ユーザインターフェースモジュール１１０２は、インターフェースを提供する。インターフェースを介し、ユーザは、検索クエリを入力し得、検索クエリの結果を受け取り得る。本発明の一実施形態に従って、ユーザはまた、インターフェースモジュール１１０２を介してセットＳに関する情報を提供し得る。
【０１２４】
データ格納場所１１１０は、データ構造ビルダモジュール１１０４および検索モジュール１１０６によって実行される処理に関する情報を格納するために貯蔵所として働き得る。例えば、セットＳのエレメント（または、エレメントそれ自体）に関する情報は、データ格納場所１１１０内に格納され得る。
【０１２５】
上述した本発明に従った技術は、種々の異なる用途において使用され得る。例えば、コンピューターの技術は、ＵＲＩのセットが、特定のＵＲＩがそのセットに含まれるかどうかを判定するために検索される暗号化目的のために使用され得る。この技術は、クレジットカードの特定の数字がセットに含まれるかどうかを判定するためのセットまたはリストを検索するために使用され得る。目録リストまたはセットは、ユーザが購入を望む特定の項目が目録に含まれるかどうかを判定するために検索され得る。本発明によって提供される検索技術はまた、効率的な検索が望まれる種々の他の環境において使用され得る。
【０１２６】
上述したことは、本発明の特定の実施形態のみを示すことが理解されるべきであり、請求項に列挙されたような本発明の範囲に限定されない。本発明の特定の実施形態が示されたが、種々の変形、改変、代替、および等価物はまた、本発明の範囲内に含まれる。示された発明は、所定の特定のデータ処理環境内で動作することに制限されないが、複数のデータ処理環境内で自由に動作する。さらに、本発明は、特定の一連の処理およびステップを使用して示され、本発明の範囲が、示された一連の処理およびステップに制限されないことが当業者に理解されるべきである。
【０１２７】
さらに、本発明は、ハードウェアおよびソフトウェアの特定の組み合わせを使用して示されたので、他のハードウェアおよびソフトウェアの組み合わせもまた本発明の範囲内であることが理解されるべきである。本発明は、ハードウェアにおいてのみまたはソフトウェアにおいてのみ、またはその組み合わせを使用してインプリメントされ得る。
【０１２８】
従って、説明および図は、限定的な意味ではなく例示的に考慮されるべきである。しかしながら、付加、除去、削除、および他の変形および変化は、請求項で示されたような発明のより広い意図および範囲から逸脱することなしになされ得ることが明らかである。
【図面の簡単な説明】
【０１２９】
【図１】図１は、本発明の実施形態を組み入れ得るコンピュータシステムの簡略化されたブロック図である。
【図２】図２は、本発明の実施形態に従って検索を行う方法の高レベルに簡略化されたフローチャートである。
【図３】図３は、本発明の実施形態に従う第一の検索技術を用いて検索オペレーションを促進するために構築され得るツリーデータ構造の部分を示す。
【図４】図４は、領域Σに属するエレメントを含む特定のセットＳのために第一の検索技術を適用する本発明の実施形態に従って構築されたツリー構造を示す。
【図５】図５は、第一の検索技術を適用する本発明の実施形態に従って検索を促進するためにデータ構造を構築する方法の高レベルに簡略化されたフローチャートである。
【図６】図６は、第一の検索技術を適用する本発明の実施形態に従ってセットＳがを検索クエリエレメントｋを含むかを判定する方法の高レベルに簡略化されたフローチャートである。
【図７】図７は、第二の検索技術を適用する本発明の実施形態に従って検索オペレーションを促進するために構築され得るデータ構造を示す。
【図８】図８は、第二の検索技術を適用する本発明の実施形態に従って検索を促進するためにデータ構造を構築する方法の高レベルに簡略化されたフローチャートである。
【図９】図９は、本発明の実施形態に従って領域Σに属するエレメントを含む特定のセットＳのための第二の検索技術の技術に従って構築されたデータ構造を示す。
【図１０】図１０は、第二の検索技術を適用する本発明の実施形態に従ってセットＳが検索クエリエレメントｋを含むかを判定する方法の高レベルに簡略化されたフローチャートである。
【図１１】図１１は、本発明の実施形態に従って第一および／または第二の検索技術をインプリメントするために用いられ得る種々のモジュールおよび／またはエンジンを示す簡略化されたブロック図である。
【図１】
2004531789.tif 000005
【図２】
2004531789.tif 000006
【図３】
2004531789.tif 000007
【図４】
2004531789.tif 000008
【図５】
2004531789.tif 000009
【図６】
2004531789.tif 000010
【図７】
2004531789.tif 000011
【図８】
2004531789.tif 000012
【図１０】
2004531789.tif 000013
【図１１】
2004531789.tif 000014
【国際公開パンフレット】
2004531789.tif 000015
2004531789.tif 000016
2004531789.tif 000017
2004531789.tif 000018
2004531789.tif 000019
2004531789.tif 000020
2004531789.tif 000021
2004531789.tif 000022
2004531789.tif 000023
2004531789.tif 000024
2004531789.tif 000025
2004531789.tif 000026
2004531789.tif 000027
2004531789.tif 000028
2004531789.tif 000029
2004531789.tif 000030
2004531789.tif 000031
2004531789.tif 000032
2004531789.tif 000033
2004531789.tif 000034
2004531789.tif 000035
2004531789.tif 000036
2004531789.tif 000037
2004531789.tif 000038
2004531789.tif 000039
2004531789.tif 000040
2004531789.tif 000041
2004531789.tif 000042
2004531789.tif 000043
2004531789.tif 000044
2004531789.tif 000045
2004531789.tif 000046
2004531789.tif 000047
2004531789.tif 000048
2004531789.tif 000049
2004531789.tif 000050
2004531789.tif 000051
2004531789.tif 000052
2004531789.tif 000053
2004531789.tif 000054
2004531789.tif 000055
2004531789.tif 000056
2004531789.tif 000057
2004531789.tif 000058
2004531789.tif 000059
2004531789.tif 000060
2004531789.tif 000061
2004531789.tif 000062
2004531789.tif 000063
2004531789.tif 000064
2004531789.tif 000065
2004531789.tif 000066
2004531789.tif 000067
2004531789.tif 000068
2004531789.tif 000069
2004531789.tif 000070
2004531789.tif 000071
2004531789.tif 000072
2004531789.tif 000073
2004531789.tif 000074
2004531789.tif 000075
2004531789.tif 000076
【国際公開パンフレット（コレクトバージョン）】
2004531789.tif 000077
2004531789.tif 000078
【国際調査報告】
2004531789.tif 000079