(57)【要約】パトリシア・トライのインデックスは、非常に小さい。しかし、このインデックスは、効率的にナビゲートするのが非常に困難であり、横断エラーを生じやすい。再始動可能なハッシュ・アルゴリズムを使用して、発明的な方法及び装置が、パトリシア・トライノードでのキーハッシュの計算について検討される。本発明は、パフォーマンスを高め、かつパトリシア・トライで使用されるその他のハッシングシステムの限界を克服するので、ハッシュの長いチェーンを一緒に構成できる。これにより、介在する複数のハッシュ・セクションとマッチするキー文字列について論理的判断が可能になる。【特許請求の範囲】
【請求項１】
コンピュータで読み取り可能なメディア上でパトリシア構造に並んだ複数のノードと、
当該パトリシア構造のノードに関連したハッシュ値と、を備えるトライであって、
当該ハッシュ値が、
開始ハッシュ値と、
当該パトリシア構造での開始位置と、
当該開始位置から当該ノードまでのデータ・シーケンスと、
当該パトリシア構造内での当該ノードの位置と、
から導出される値を有する再始動可能なハッシュ値を備える、トライ。
【請求項２】
当該複数のノードが、少なくとも1つのノードを備え、その1つのノードが、少なくとも2つのセグメントを有するキーを備える、請求項1に記載のトライ。
【請求項３】
当該再始動可能なハッシュ値の前記生成を可能にするための予め計算されているハッシュ値をさらに備える、請求項１に記載のトライ。
【請求項４】
当該パトリシア構造が、
パトリシア・トライ、パトリシア・トライを組み込んだブロック・インデックス、及びレイヤード・パトリシア・トライ、のうちの1つを備える、請求項4に記載のトライ。
【請求項５】
請求項1に記載のトライを備える、メモリー。
【請求項６】
少なくともトライを1つ有するデータ・ベース・ファイル管理システムにおける記憶メディアであって、
当該トライが、パトリシア構造に並んだ複数のノードと、当該パトリシア構造のノードに関連したハッシュ値とを備え、
当該ハッシュ値が、再始動可能なハッシュ値を備え、
当該再始動可能なハッシュ値が、
開始ハッシュ値と、
当該パトリシア構造での開始位置と、
当該開始位置から当該ノードまでのデータ・シーケンスと、
当該パトリシア構造内での当該ノードの位置と、
から導出される値を備える、記憶メディア。
【請求項７】
当該複数のノードが、少なくとも1つのノードを備え、その1つのノードが、少なくとも2つのセグメントを有するキーを備える、請求項６に記載の記憶メディア。
【請求項８】
当該再始動可能なハッシュ値の生成を可能にするための予め計算されているハッシュ値をさらに備える、請求項６に記載の記憶メディア。
【請求項９】
当該パトリシア構造が、
パトリシア・トライ、パトリシア・トライを組み込んだブロック・インデックス、及びレイヤード・パトリシア・トライ、のうちの1つを備える、請求項８に記載の記憶メディア。
【請求項１０】
パトリシア構造に並んだ複数のノードと、
再始動可能なハッシュ値を少なくとも1つ発生するための手段であって、
当該再始動可能なハッシュ値が、当該複数のノードの少なくとも1つのキ    
ーから導出される値を備え、
当該再始動可能なハッシュ値が、始動ハッシュ値と、当該パトリシア構造
における始動位置と、当該始動ポイントから当該ノードへのデータ・シー
クエンスと、当該パトリシア構造内の当該ノードの位置とから導出された  
値を備える、
手段と、
当該ハッシュ値を当該複数のノードの1つと関連させるための手段と、
を備える、トライのインデックス・システム。
【請求項１１】
当該キーが2つ以上のセグメントに分割される、請求項10に記載のシステム。
【請求項１２】
パトリシア構造のための再始動可能なハッシュを計算するための方法であって、
開始ハッシュ、開始位置、データ・シーケンス及び終了位置を受理するステップと、
全体ハッシュを計算するステップであって、当該全体ハッシュが、当該開始ハッシュと、当該開始位置で開始しかつ当該終了位置で終了する当該データ・シーケンスのセグメントとの関数であり、当該全体ハッシュは、第1ハッシュ及び第2ハッシュを計算することにより取得される計算されたハッシュに等しく、当該第1ハッシュは、当該開始位置と、当該データ・シーケンスと、中間位置との入力を有して、かつ中間ハッシュを結果とし、当該第2ハッシュは、当該中間ハッシュと、中間位置と、当該データ・シーケンスと、当該終了位置との入力を有し、当該第1ハッシュ及び当該第2ハッシュの前記組み合わせが、当該全体ハッシュに等しい、計算ステップと、
当該パトリシア構造のための当該全体ハッシュを返すステップと、
を備える方法。
【請求項１３】
現在の値を初期値に初期化するステップと、
新しい現在の値を生み出すために、当該現在の値を、当該開始位置と当該終了位置との間の当該データ・シーケンスの要素と組み合わせるステップと、
新しい現在の値を生み出すために、当該現在の値を、当該開始位置と当該終了位置との間の当該データ・シーケンスの第2要素と組み合わせるステップと、
当該新しい現在の値を当該パトリシア構造のための当該全体ハッシュとして返すステップと、
をさらに備える、請求項12に記載の方法。
【請求項１４】
当該データ・シーケンスが、インデックスにおけるキーである、請求項13に記載の方法。
【請求項１５】
パトリシア構造のための再始動可能なハッシュを計算するための命令シーケンスを含むコンピュータソフトウェア製品であって、
前記命令シーケンスが、
開始ハッシュ、開始位置、データ・シーケンス及び終了位置を受理するステップと、
全体ハッシュを計算するステップであって、当該全体ハッシュが、当該開始ハッシュと、当該開始位置で開始しかつ当該終了位置で終了する当該データ・シーケンスのセグメントとの関数であり、当該全体ハッシュは、第1ハッシュ及び第2ハッシュを計算することにより取得される計算されたハッシュに等しく、当該第1ハッシュは、当該開始位置と、当該データ・シーケンスと、中間位置との入力を有して、かつ中間ハッシュを結果とし、当該第2ハッシュは、当該中間ハッシュと、中間位置と、当該データ・シーケンスと、当該終了位置との入力を有し、当該第1ハッシュ及び当該第2ハッシュの前記組み合わせが、当該全体ハッシュに等しい、計算ステップと、
当該パトリシア構造のための当該全体ハッシュを返すステップと、
を備える方法、をさらに備える、コンピュータソフトウェア製品。
【請求項１６】
当該方法が、さらに、
現在の値を初期値に初期化するステップと、
新しい現在の値を生み出すために、当該現在の値を、当該開始位置と当該終了位置との間の当該データ・シーケンスの要素と組み合わせるステップと、
新しい現在の値を生み出すために、当該現在の値を、当該開始位置と当該終了位置との間の当該データ・シーケンスの第2要素と組み合わせるステップと、
当該新しい現在の値を当該パトリシア構造のための当該全体ハッシュとして返すステップと、
を備える、請求項15に記載のコンピュータソフトウェア製品。
【請求項１７】
当該データ・シーケンスが、インデックスにおけるキーである、請求項16に記載のコンピュータソフトウェア製品。
【請求項１８】
パトリシア構造のための再始動可能なハッシュ・コードをキャッシュするための方法であって、
データ・シーケンス及び位置を受理するステップと、
保存された前回のハッシュ、保存された前回の位置、当該データ・シーケンス及び当該位置に少なくとも基づいて再始動可能なハッシュを計算するステップと、
当該位置を当該前回の位置として保存するステップと、
当該再始動可能なハッシュを当該前回のハッシュとして保存するステップと、
当該ハッシュを結果として返すステップと、
を備える方法。
【請求項１９】
請求項18に記載の方法により生成された再始動可能なハッシュ・コードを含む、メモリー。
【請求項２０】
パトリシア構造として組織された複数のノードを含むメモリーであって、少なくとも1つのノードが関連したハッシュ・コードを有し、請求項24に記載の方法により再始動可能なハッシュ・コードが生成される、メモリー。
【請求項２１】
パトリシア構造のための再始動可能なハッシュ・コードをキャッシュするための命令シーケンスを含むコンピュータソフトウェア製品であって、
前記命令シーケンスが、
データ・シーケンス及び位置を受理するステップと、
少なくとも、保存された前回のハッシュ、保存された前回の位置、当該データ・シーケンス及び当該位置に基づいて再始動可能なハッシュを計算するステップと、
当該位置を当該前回の位置として保存するステップと、
当該再始動可能なハッシュを当該前回のハッシュとして保存するステップと、
当該ハッシュを結果として返すステップと、
を備える方法をさらに備える、コンピュータソフトウェア製品。
【請求項２２】
所定位置で、トライでのキーについてハッシュ・コードを計算するための方法であって、
データ・シーケンス及び位置を受理するステップと、
固定位置で開始しかつ当該位置で終了する当該データ・シーケンスのハッシュ・コードを計算するステップと、
当該計算されたハッシュ・コードを返すステップと、
を備え、
当該トライが、パトリシア、レイヤード・パトリシア、及びブロック・インデックストライ、のうちの1つを備える、方法。
【請求項２３】
請求項25に記載の方法により生成されたキーについてのハッシュ・コードを含む、メモリー。
【請求項２４】
パトリシア構造として組織された複数のノードを含むメモリーであて、少なくとも1つのノードがキーについて関連したハッシュ・コードを有し、  請求項22に記載の方法により前記キーについて前記ハッシュ・コードが生成される、メモリー。
【請求項２５】
所定位置で、トライでのキーについてハッシュ・コードを計算するための命令シーケンスを含むコンピュータソフトウェア製品であって、
前記命令シーケンスが、
データ・シーケンス及び位置を受理するステップと、
固定位置で開始しかつ当該位置で終了する当該データ・シーケンスのハッシュ・コードを計算するステップと、
当該計算されたハッシュ・コードを返すステップと、
を備える方法、をさらに備え、
当該トライが、パトリシア、レイヤード・パトリシア、及びブロック・インデックストライ、のうちの1つを備える、コンピュータソフトウェア製品。
【請求項２６】
パトリシア構造において、トライでのキーについて再始動可能なハッシュ・コードを計算するための方法であって、
当該キーを、当該再始動可能なハッシュ・コードが計算されるセグメントに分割するステップを備え、
如何なる位置の当該再始動可能なハッシュ・コードも、直前のセグメント終了後の当該キー内でのデータにのみ依存する、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的にパトリシア・トライのインデックスハッシングに関する。より詳細には、本発明は、パトリシア・トライでの再始動可能なハッシングの仕組みに関する。
【背景技術】
【０００２】
パトリシア（PATRICIA: Practical Algorithm To Retrieve Information Coded In Alphanumeric）は、1968年にD.R.モリソンにより示されたトライである。パトリシアは、インデックスのコンパクトな方法としてこの業界では周知であり、かつデータ・ベース及びネットワーク技術において一般に使用されている。基本的に、パトリシアの実施の場合、子を1つしか持たないトライノードは排除される。残りのノードには、この非圧縮トライでのノードの深さを示す文字位置番号がラベルされる。
【０００３】
図1は、アルファベットの場合について、このようなパトリシア・トライの実施の一例を示す。保存される単語は、「greenbeans」、「greentea」、「grass」、「corn」及び「cow」である。最初の3つの単語は、後の2つの単語と第1文字目で異なる。すなわち、これら3つは、文字「g」で始まるが、他の2つは、文字「c」で始まるので、第1位置で相違する。したがって、「g」の単語と「c」の単語を分けるノードは、深さ「0」に存在する。
【０００４】
「g」から移動して、次に相違が見つかるのは第3位置である。これは、2つの単語「greenbeans」及び「greentea」においては、「e」であるが、単語「grass」では、「a」である。したがって、このレベルでのノードは、深さレベル「2」を示す。
【０００５】
左のパスを下方に移動すると、次に、第6位置で異なる文字が見つかることが判る。それは、1方の単語「greenbeans」では、「b」であるが、他方の単語「greentea」では、「t」である。したがって、ノードは、深さ「5」に存在する。
【０００６】
この実施での1つの問題は、キーが検索パスにより一意に指定されなくなってしまうことである。したがって、キー自体は、適切なリーフに保存させる必要がある。このアプローチの利点は、k*nのポインタしか要求されないことである（ここで「k」は、アルファベットのサイズであり、かつ「n」は、ポインタ数である）。k=2を有するアルファベットは、2つの記号（可能性としては「0」及び「1」）のみを有する2値のアルファベットであることは、当業者には容易に認識されるであろう。図2は、このようなアルファベットに対するトライの実施のサンプルである。
【０００７】
パトリシア・トライは、キー
2009512099.tif 000002
を含むリーフ
2009512099.tif 000003
、又はビットオフセット
2009512099.tif 000004
及び左サブツリー
2009512099.tif 000005
及び右サブツリー
2009512099.tif 000006
を含むノード
2009512099.tif 000007
の何れかである。これは、パトリシア・ツリーのノードの再帰的記述である。ノード
2009512099.tif 000008
から辿り着くリーフは、最初の
2009512099.tif 000009
ビットでは必ず一致する。パトリシア・トライの説明は、コンパクトBツリー（Bumbulis及びBowman）（データ管理に関する2002年ACM SIGMOD国際会議報告、p.533〜541）に紹介されたもので、これは、参照として、その全体が本願に組み込まれている。ここでポインタのブロックは、パトリシア・トライのアーキテクチャを使用して作成してもよく、このブロックは、データの効率よい呼び出しを可能にするポインタを有することになる。ポインタ数又はブロックのファン・アウトは、複数のパラメータに基づいて計算される可能性がある。
【０００８】
パトリシア・トライでは、図3に示すように、如何なるノードにもハッシングが使用されないため、その文献に記されるように、トライを通るナビゲーションは、困難かつ非効率となる可能性があり、さらには横断エラーを引き起こしやすい。別の従来技術の解決策であるサフィックス・ハッシングは、図4に示すように、サフィックス・バイトの使用を提案している。サフィックス・バイトは、パトリシア・トライのすべてのノードに直接先行する8ビットを使用する。これは、ハッシングが全くないよりは、確かにインデックス上、有利である。しかし、複雑性及び横断エラーの両方において、パフォーマンス改善は、限られている。ある典型的な例の場合、横断エラー数は、75％低減した。しかしながら、ハッシングが全くない場合のエラー数は、膨大であるので、この低減でも意義深い。
【０００９】
さらにもう1つの解決策は、図5に示すような、バリュー・ハッシングの使用である。バリュー・ハッシングの場合、各ノードは、チェーン全体を表すハッシュ値をパトリシア・トライのルートから受理する。このため、ノード510は、そのルート・ノードからのパス（実線）を表すハッシュ値515を受理し、ノード520は、そのルート・ノードからのパス（破線）を表す別のハッシュ値525を受理し、ノード530は、そのルート・ノードからのパス（二点鎖線）を表すハッシュ値535を受理する。各ハッシュ値515、525及び535は、固有であり、かつ独立している。このハッシュは、サフィックス・ハッシングよりも大幅に計算が高額になり、かつ、しかも、ノードがパトリシア・トライをさらに下がるにつれて複雑さが増す。しかし、バリュー・ハッシングにより、横断エラーは大幅に低減でき、可能性としては、ハッシングが全くないパトリシア・トライと比較して0.15％まで下げることができる。
【００１０】
【特許文献１】米国特許出願番号10/912,872
【非特許文献１】コンパクトBツリー（A Compact B-Tree）（Bumbulis及びBowman）（データ管理に関する2002年ACM SIGMOD国際会議報告、p.533〜541）
【発明の開示】
【発明が解決しようとする課題】
【００１１】
従来技術の限界を考えると、計算を高速に行うハッシングの仕組みを提供する解決策があれば、有益であろう。また、このような計算が、前段階のハッシュ計算を活用することができれば、さらに有益であろう。また、このようなハッシングの仕組みが、検索文字列におけるギャップに対処できれば、さらにもっと有益であろう。
【課題を解決するための手段】
【００１２】
パトリシア・トライのインデックスは、非常に小さい。しかし、このインデックスは、効率的にナビゲートするのが非常に困難であり、横断エラーを生じやすい。再始動可能なハッシュ・アルゴリズムを使用して、発明的な方法及び装置が、パトリシア・トライノードでのキーハッシュの計算について検討される。本発明は、パフォーマンスを高め、かつパトリシア・トライで使用されるその他のハッシングシステムの限界を克服するので、ハッシュの長いチェーンを一緒に構成することを可能にする。これにより、介在する複数のハッシュ・セクションとマッチするキー文字列について論理的判断が可能になる。
【発明を実施するための最良の形態】
【００１３】
従来技術の限界を克服するため、パトリシア・トライ又はキーをインデックスする他のスパースツリー、特にレイヤード・パトリシア、のインデックスをサポートするハッシングの仕組みを導入することにより、横断エラーの頻度が低減する。
【００１４】
さらには、検索文字列中のギャップ、すなわち、未知値、をサポートできる再始動可能なハッシングの仕組みが、導入される。また、キーハッシュの高速計算を提供する再始動可能なハッシングを使用する手段も、開示される。再始動可能なハッシングを使用するハッシュのキャッシング方法も、示される。さらには、新規性のあるセグメント化されたキー・ハッシング手法も、開示される。レイヤード・パトリシアの詳細な説明は、本出願人に譲渡された米国特許出願番号10/912,872、発明の名称「カスケード・インデックス法及びその装置」"A Cascading Index Method and Apparatus"により提供されるが、これは、参照として、その全体が本願に組み込まれている。
【００１５】
図6は、代表例であり、かつこれに限定されない、再始動可能なハッシングの仕組みを使用するパトリシア・トライである。ハッシング構造、すなわち、ノード起点に戻ることは、図5のものと同様であるが、重要な相違点は、実際のハッシングの仕組み自体に存在する。詳細には、図5及び図6のトライが、瓜二つであるとしても、それぞれのハッシュ値、例えば、ハッシュ値615が、値515とは異なり、かつ同様に、ハッシュ値635が、ハッシュ値535とは異なる。しかし、ハッシュ値615、625及び635は、それぞれがルート・ノードからノード610、620及び630への特定のパスに対応する。このハッシング関数の特質を図7に示し、ここでは、ハッシュ値625をノード620とノード630間で計算されるハッシュ値720とともに使用することにより、ノード630にハッシュ値635を生成する能力があることを実演している。したがって、ルート・ノードからハッシュ全体を計算する必要がない。そのため、本発明の実施例は、トライのハッシュ値計算を大幅に簡略化する。より詳細には、非常に長いインデックス文字列から、ハッシュ値を計算する必要性を回避する。代表例ではあるが、これに限定されないハッシュとしては、例えば、あるノード、ノード730に先行するノード数を数える単純な8ビット若しくはモジュロ256、又はあるノードに先行するバイトと部分バイトのXOR若しくは和でもよい。提案される再始動可能なハッシングのアルゴリズムのより詳細な検討は、以下に説明される。
【実施例】
【００１６】
各ノードに対するハッシュ計算の速度化を提供するのに加えて、本発明は、たとえギャップがあるとしても、ある文字列が検索文字列とマッチするかどうかを正確に予測する能力も提供する。検索文字列として次の例を考察する。
【００１７】
????????????????????00110
この場合、例えば、「1」又は「0」の何れにもマッチすることができる20個の「?」マークがあり、この後には、「00110」が続く。すなわち、このクエリでは、最初の20ビット（ビット0〜19）のマッチは問わずに、位置20〜24の「00110」がマッチするものはすべて、マッチと考える。ハッシングは、使用されるすべてのビットに依存するため、再始動不可能なハッシングの仕組みでは、通常、役に立たない答えになってしまう。
【００１８】
これとは対照的に、本発明で開示される再始動可能なハッシングは、有効な情報を提供する。すなわち、本発明で開示される再始動可能なハッシングの仕組みの利点は、ハッシュの中に包まれたキー文字列の一部を評価することである。これは、キー文字列のプレフィックスを知らなくても完了できる。
【００１９】
上記の例に戻り、文字列「00110」が、シーケンス732として記されるノード730からノード740に導く文字列であるかどうかを確認したい場合がある。再始動可能なハッシングの仕組みを使用して、ノード740の期待ハッシュが、ノード730の値、ノード730のハッシュ、ノード740の値及び文字列「00110」を使用して計算できる。これは、ノード740の期待ハッシュを生成し、この期待ハッシュをハッシュ735の実際値と比較することを可能にする。計算されたハッシュが、735のハッシュとマッチする場合、インデックスでマッチする確率は高い。計算されたハッシュが、735でのハッシュとマッチしない場合、マッチは存在しない。本発明者により実施されたシミュレーションは、横断エラーの大幅な低下を示す。そのため、システムの全体的なパフォーマンスが、改善される。実際に、そのパフォーマンスは、ハッシング計算を大幅に低減し、しかもキー・ハッシングのものに匹敵することがシミュレーションにより示され、さらには、上記のようなギャップ又は部分マッチ検索を提供する。図8は、代表例であり、かつこれに限定されないパフォーマンス比較を示す。
【００２０】
さらに、当業者には、再始動可能なハッシング関数の本特性が構成可能であることが、分かるであろう。したがって、ハッシュの長いチェーンを一緒に構成して、介在する複数のハッシュ・セクションとマッチするキー文字列について論理的判断をすることが可能になる。これは、以下のように記述することができる。
2009512099.tif 000010
【００２１】
図9は、開示される本発明の代表例であり、かつこれに限定されない再始動可能なハッシングを示す。当業者は、このJava（登録商標）言語の例を、あらゆるコンピュータ言語、ファームウェア、ハードウェア又はこれらを組み合わせたものに変換して、開示される本発明の範囲から逸脱することなく、実施することが可能であろう。ハッシュを再始動するには、先頭ビット文字列のハッシュ・コードが、アルゴリズムに再び差し込まれ、かつ末尾ビット文字列のビットが、そのポイントから注入される。これにより、先頭及び末尾のビット文字列を一度にハッシュして計算されるであろう値と同じハッシュ値が、取得し直される。このため、本発明で開示される再始動可能なハッシュは、如何なるポイントでも、ハッシュ・コードの値に全体の状態が含まれている特性を有する。
【００２２】
開示される本発明を明確にし、かつ一般性を高める目的で、図10は、代表例であり、かつこれに限定されない再始動可能なハッシングのフローチャートを示す。本発明では、Java（登録商標）言語での実施が、示されているが、別のプログラミング言語を使用したものが、本発明の開示から逸脱するものと考えるべきでなく、かつこのようなプログラムが、本発明の範囲内にあることは、当業者には認識されるであろう。
【００２３】
再始動可能なハッシュは、いくつかの文字列内ノード（及びそれらのサブトライ）、すなわち、その位置が相対キー文字列の中にあるノード、をスキップすることを可能にする。左端の文字列内ノードはチェック出来ないが、右側（より大きな位置）のものはスキップしてよい。このアルゴリズムは、左端の文字列内ノードの前の相対キー文字列ビットを無視するが、これらのビットが反復キーとマッチするものと仮定する。そして、ハッシュ・アルゴリズムは、この左端ノードのハッシュ・コードを使用して再始動され、その位置から右方向の相対文字列からのビットが注入される。この注入が、相対キー文字列を介して進行するので、ハッシュ・コードは、ノードが通過した場合にアルゴリズムから抽出することが出来、かつ抽出されたハッシュ・コードは、この通過したノードのハッシュ・コードと比較することができる。ノードのハッシュ・コードとアルゴリズムのハッシュ・コードとの間に相違がある場合、マッチは「誤」を返す。そうでない場合、パスは、マッチする可能性があり、「正」を返す。
【００２４】
再始動可能性に関してさらに新規性のある使用は、キーハッシュ・コードのキャッシングにある。単調に位置を増加させる局部的なパターンを有するハッシュの計算は、低減させることができる。ハッシュのキャッシュを保存するための、好適ではあるが、これに限定されない方法は、キー文字列自体にある。図11が、代表例でありかつこれに限定されないフローチャート1100を示す。現在の位置及び現在のハッシュ・コードは、維持される。現在の位置が前回の位置より大きい場合には常に、前回のハッシュ・コードを使用して、その位置でハッシングを再始動し、かつそれを新しい位置に前進させる。次いで、新しい位置が、キャッシュされたハッシュ及び位置としての新しいハッシュ・コードと共に保存される。操作の結果として、この新しいハッシュ・コードは、そのキャッシングが使用されなかったものとして、返される。より詳細には、ステップS1110において、データ・シーケンス及び位置が受理される。ステップS1120では、再始動可能なハッシュが、前回のハッシュ、前回の位置、受理されたデータ・シーケンス及び受理された位置に基づいて計算される。ステップS1130では、S1120で計算された再始動可能なハッシュ値が、返される。ステップS1140及びS1150において、前回の位置は、受理された位置で置き換えられ、かつ前回のハッシュは、計算された新しいハッシュにより置き換えられる。
【００２５】
位置を増加させるパターンは、ノードにキーハッシュを含むトライでのほとんどの操作の検索局面では、非常に一般的であり、かつ多くの場合、位置の増加は、非常に小さいので、それに応じて計算時間の低減も、大きくなる。各ノードが、下方横断中に検査される場合、別のハッシュ計算を実行しなければならないことは、一般的である。トライが二値である、好適な実施例の場合、ノードが50以上にまでなるトライの深さは、珍しくない。そのため、計算スピードを増大させることは、非常に重要である。トライが、各ノードで、可能性のある小さな組合せのラベルを有する場合、より多くのノードが存在するので、その計算時間は、さらに重要となる。
【００２６】
トライのノードでの再始動可能又はその他のハッシュへのさらに新規性のある改善は、セグメンテーションである。この仕組みの場合、キーは、セグメントに分割され、そのセグメント内でハッシュ・コードが計算されるので、如何なる位置のハッシュ・コードも、直前のセグメント終了後のキーでのデータにしか依存しない。本方法のこれに限定されない例が、図9A及び9Bに示される。ここには、代表例であり、かつこれに限定されないJava（登録商標）コードが、示される。ハッシュ・コードをこのようなセグメントに分割することは、再始動可能なハッシングのみならず、あらゆるタイプのトライで使用されるハッシングにも適用可能であり、かつこの手法は、如何なるプログラミング言語を使用しても容易に適用できることは、当業者には認識されるであろう。このようなアプローチの利点には、ハッシュ計算時間の低減、及びキーの既知の部分が生じるセグメントが始まる前に生じるギャップで、パターンマッチを実行する能力が含まれる。実施の代表例は、再始動可能性とセグメンテーションを組み合わせているが、セグメンテーションは、再始動可能性なしで使用することも可能である。
【００２７】
開示される本発明の教示内容を活用する目的で、本発明を、データ・ベース・システム、より詳細には、データ・ベース・ファイル管理システムの一部として統合してもよいことは、当業者には、直ちに理解されるであろう。さらに、本発明の教示内容は、複数の命令が含まれるコンピュータソフトウェア製品に実装してもよい。これらの命令が実行されると、本発明の教示内容が実行される結果が得られる。
【００２８】
本発明は、好適な実施例を参照して説明されたが、本発明の精神と範囲から逸脱することなく、他のアプリケーションも、本発明で開示されるものに代えて用いることができることは、当業者には直ちに理解されるであろう。したがって、本発明は、添付の請求の範囲によってのみ制限されるべきである。
【図面の簡単な説明】
【００２９】
【図１】アルファベットの場合についてのパトリシア・トライの代表例である（従来技術）。
【図２】数値の場合についてのパトリシア・トライの代表例である（従来技術）。
【図３】インデックスハッシュを使用しないパトリシア・トライの代表例である（従来技術）。
【図４】サフィックス・バイトを使用するパトリシア・トライの代表例である（従来技術）。
【図５】キー・ハッシングを使用するパトリシア・トライの代表例である（従来技術）。
【図６】再始動可能なハッシングを使用するパトリシア・トライの代表例である。
【図７】再始動可能なハッシングの利点を実演するパトリシア・トライの代表例である。
【図８】再始動可能なハッシングの仕組みと従来技術の解決策とのパフォーマンスの比較例である。
【図９Ａ】及び
【図９Ｂ】再始動可能なハッシュ関数についてのJava（登録商標）コードの代表例である。
【図１０】再始動可能なハッシュ関数のフローチャートの代表例である。
【図１１】ハッシュ・コードをキャッシュするフローチャートの代表例である。
【符号の説明】
【００３０】
510、520、530、610、620、630  ノード
515、525、535、615、625、635、720  ハッシュ値
S1110、S1120、S1130、S1140、S1150  ステップ
【図１】
2009512099.tif 000011
【図２】
2009512099.tif 000012
【図３】
2009512099.tif 000013
【図４】
2009512099.tif 000014
【図５】
2009512099.tif 000015
【図６】
2009512099.tif 000016
【図７】
2009512099.tif 000017
【図８】
2009512099.tif 000018
【図９Ａ】
2009512099.tif 000019
【図９Ｂ】
2009512099.tif 000020
【図１０】
2009512099.tif 000021
【図１１】
2009512099.tif 000022
【国際調査報告】
2009512099.tif 000023