JP2000517086A - オフセット表を使用する完全ハッシュの生成 - Google Patents

Abstract

(57)【要約】 選択されたユニコード符号点のような大きい範囲の値の不連続部分集合を、完全ハッシュを用いて、連続またはほぼ連続したより小さい範囲に変換する方法および機構を提供する。大きい範囲をページとそのページ内へのオフセットの二次元ビットマップ行列（３８）に編成する。値が部分集合に含まれるならば、行列内のビットは１になり、含まれなければ０になる。次に、各ページを他のページの値との衝突を避けるために必要に応じてシフトすることによって、ページを次々に一次元ビットマップ（４０）にオーバレイする。シフト量を記録し、ハッシュ計算に使用する。ここで、大きい範囲の値を最初にページ番号とそのページ内へのオフセットに分離する。次に、そのページのシフト量を探索し、シフト量をページ内へのオフセットに加算することによって、大きい範囲の値を密な部分集合範囲の値にハッシュ化する。

Description

【発明の詳細な説明】 オフセット表を使用する完全ハッシュの生成 発明の分野 本発明は、一般的にコンピュータシステムの記憶装置に関し、さらに詳しくは 、表に対応づけられるデータを格納するための改良された方法およびシステムに 関する。 発明の背景 大きさ６４キロバイトで１６ビットのキーにより索引付けされる表のようなエ ントリの大きい表は、特定の用途によってサポートされる不連続エントリの比較 的小さい部分集合を含むことができる。例えば、ユニコードは、１６ビットの符 号化単位を基礎にする世界的な文字符号化標準である。特定の言語で使用される 符号点しかサポートしないユニコード構成製品では、その言語の符号点のより小 さい不連続部分集合が使用される。例を挙げると、日本語の場合、製品は、通常 日本工業規格（ＪＩＳ）コードを使用しており、ユニコードによってサポートさ れる６４キロバイトの可能な記号のうち、約６，０００個の記号しか使用されな い。この６０００個ほどの記号は、ユニコードの範囲全体の様々な位置に広く分 散され、残りの符号点は、その製品にとって無意味である。 より少数の文字属性または類似物をフルサイズ６４キロバイトの表に格納する と、多くの未使用のエントリ値が残る。この格納方法は、ユニコード値をキーと して使用して簡単な索引付け作業を可能にし、したがって、格納された情報を検 索する最高速の方法であるが、表は、属性のサイズの６４０００倍であり、空間 の多くが無駄になる。多くのシステムや用途では、高速検索速度は、この方法を 実現するために要求されるメモリの量に値せず、したがって他の格納方法が試み られてきた。 フルサイズのエントリ表に代わるものとして、二分探索を使用する方法がある 。そのような二分表ではスロットの無駄が無いが、各エントリと共にキーを格納 し なければならず、関心対象のエントリを格納するために使用する空間の量は増大 する。さらに、表の大きさをＮとした場合、探索を実行するためにＯ（ｌｏｇ（ Ｎ））の演算を行い、したがって平均すると、他の格納方法に比べて比較的遅い 検索になる。 ハッシュ表を使用して、符号点から計算したハッシュ値によって索引付けされ る属性を格納することもできる。ハッシュ表の１つの型として、衝突解消付きの ハッシュ表がある。この型のハッシュ表は、通常各エントリと共にキーを格納す ることによって達成される、衝突を処理するための情報を格納しなければならな い。衝突の有無を試験するために余分な時間を必要とし、また衝突が検知された ときに衝突を解消するためにさらに多くの時間を必要とする。最後に、この型の ハッシュ表は、一般的にしばしば、多数の余分な未使用のエントリで終わってし まう。つまり、表は必ずしも密にパックされるとは限らない。 最後に、完全ハッシュアルゴリズム（衝突が無い）は、メモリの使用と速度の 間の優れた調和をもたらすことができるので、多くの用途で望ましい性能を達成 する。さらに、完全ハッシュアルゴリズムでは、エントリと共にキーを格納しな いので空間が節約される。しかし、完全ハッシングでは、一般的に余分な未使用 のエントリが存在するので空間が無駄になる。また、検索時間は各探索作業にお ける重要な要素であるので、ハッシュ値を計算するために必要な費用（例えば処 理時間の量）にも重要な考慮を払わなければならない。さらに、比較的大きい範 囲の値の１つの部分集合のハッシングにうまく働いたものが、別の部分集合では うまく働かない。したがって、完全ハッシュアルゴリズムの大きな問題は、一般 的に、共に非常に高速である値の任意の部分集合の完全ハッシュを見つけ、およ びハッシュ値を一緒に密にパックするための優れた迅速な首尾一貫した方法が存 在しないことである。 発明の目的および概要 したがって、本発明の一般的目的は、大きい範囲の不連続値の任意の部分集合 に関する完全ハッシュを生成する方法および機構（装置）を提供することにある 。 さらに別の目的は、ハッシュ値を密にパックする、上述の特徴を持つ方法およ び機構を提供することにある。 別の目的は、ハッシュ値の非常に高速な計算を実行できる上述の種類の方法お よび機構を提供することにある。 関連目的は、自動的に作動する方法および機構を提供することにある。 これらの目的を達成する上での別の関連目的は、不連続ユニコード符号点の部 分集合でうまく機能する、上述の特徴を持つ方法および機構を提供することにあ る。 さらに別の目的は、高速であり、信頼でき、費用効果が高く、柔軟性があり、 様々な用途に拡張可能な上述の方法および機構を提供することにある。 簡単に言うと、本発明は、大きい範囲の値の不連続部分集合を、完全ハッシュ による連続したまたは大部分が連続したより小さい範囲に変換するための方法お よび機構を提供するものである。値の部分集合は、範囲内の値の中から選択され 、範囲は二次元行列に編成される。行列の１つの次元は、ページを表し、別の次 元はページ内へのオフセットを表す。行列は、ページとページ内へのオフセット との各交叉位置に、その交叉位置によって表される値が部分集合の選択値である か否かを示すビットなどの写像情報を含む。例えば、部分集合に選択される場合 、ビットは１であり、選択されない場合は零である。 次に、各ページを選択し、各ページの写像情報（例えば１のビット）に一次元 配列内の写像情報との衝突が無いかを検査し、衝突が検知されなくなるまで各ペ ージをある量づつ移動（シフト）することによって、行列は一次元配列（例えば ビットマップ）に変換される。衝突が検知されなければ、ページ写像情報がシフ ト位置における一次元配列にオーバレイされ、シフト量がページオフセット表に 記録される。 不連続範囲の値を受け取ると、その値は、ページ番号とそのページ内へのオフ セットとに分割される。値はそれにより、そのページのシフト量を探索し、その ページ内へのオフセットにシフト量を加算することによって、サブセット範囲の 値にハッシュ化される。 他の目的および利点は、図面に関連して取り上げる以下の詳細な説明から明ら かになるであろう。図面の簡単な説明 図１は、本発明に従って完全ハッシュを生成するためのコンピュータシステム を表すブロック図である。 図２は、可能なエントリの表の典型例を表すブロック図である。 図３から図４は、図２の表の選択されたエントリを示す代替的方法を表すブロ ック図である。 図５から図６は、選択されたエントリに関する情報を格納するためのビットマ ップ行列を表すブロック図である。 図７から図１０は、本発明の一態様に従ってビットマップ行列から一次元合成 ビットマップへページをオーバレイする過程を順次に示すブロック図である。 図１１から図１４は、本発明の一態様に従ってビットマップ行列のページが相 互にオーバレイされるときのページオフセット表におけるオフセット値を示す図 である。 図１５から図１８は、エントリ情報が充填されていくハッシュ表を表す図であ る。 図１９は、本発明に従って完全ハッシュを生成するための過程を一般的に表す 流れ図である。 図２０は、本発明に従って完全ハッシュを生成するためにビットマップ行列の ページをオーバレイするための過程を一般的に表す流れ図である。 図２１は、本発明の一態様に従ってキーからハッシュ値を計算するためのコン ピュータシステムを表すブロック図である。 図２２は、キーからハッシュ値を計算するための過程を一般的に表す流れ図で ある。 好ましい実施形態の詳細な説明 図面を参照しながら説明する。まず最初に図１であるが、本発明に従ってオフ セット表を使用して不連続値を再写像するためのコンピュータシステムが、全体 的に符号２０で表されている。コンピュータシステム２０は、記憶装置２４に効 果的に接続されたプロセッサ２２を含み、該記憶装置はランダムアクセスメモリ （ＲＡＭ）と、ハードディスクドライブ、光ドライブまたは類似物などの不揮発 性記憶装置とを含む。ご理解いただけるとおり、不揮発性記憶装置２８は、よく 知られたスワップ技術を介して、ＲＡＭと一緒に使用して比較的大量の仮想メモ リを形成することができる。明らかになるであろうが、本発明では、読取り専用 メモリ（ＲＯＭ）または同様の不揮発性システムを使用することができる。また 、埋込みシステムは本発明から利益を得ることができる。 コンピュータシステム２０はまた、ユーザコマンドをプロセッサ２２に伝える ために、入出力回路機構（Ｉ／Ｏ）３２を介して接続された少なくとも１つの入 力装置３０、通常はキーボードおよび／またはマウスなどのユーザポインティン グ装置を含む。同様に、コンピュータディスプレイモニタおよびスピーカなど、 少なくとも１つの局所出力装置３４が、グラフィカルユーザインタフェースなど を介して、プロセッサ２２からシステム２０のユーザへ情報を伝えるために、Ｉ ／Ｏ３２に接続される。 本発明の一態様では、値の大きい範囲内の不連続な位置にある値の部分集合が 与えられると、再写像プロセス３６がこの部分集合を、連続した、またはほぼ連 続した、零を基底とする範囲に変換する。例えば、大きい値の範囲は、文字属性 の大きい表３８に索引を付けるための００００ｈ（１６進数）から０ｆｆｆｆｈ までの範囲の索引に対応するかもしれない。例えば索引は、ユニコード符号点で ある。容易に理解できるように、表３８にかなりの量の空間を割り当てる必要が ある。しかし、特定の用途にとっては、表３８のエントリのうち、特定のものだ けが関心の対象である。例えば、用途またはオペレーティングシステムによって サポートされる文字に対応する符号点だけが、その用途またはオペレーティング システムにとって重要である。典型的な用途では、再写像プロセス３６は、基本 的に、関心のあるエントリを取り出し、それらを、元の表のキーを受け取り、ほ とんど密なハッシュ表４０に対するハッシュ値索引に変換することができる方法 で、ほとんど密なハッシュ表４０に再パックする。再写像プロセスの一部として オフセットの表４２が生成され、これを、以下で述べるように、元の索引値と一 緒に使用して、ほとんど密なハッシュ表４０のハッシュ値が計算される。 したがって、本発明には区別される２つの態様があることに注意する必要があ る。第一態様は、大きい表３８のキーなどの不連続値の部分集合をオフセット表 ４２へ変換することを含む。本発明の第二態様は、その後にオペレーティングシ ステム、ドライバ、アプリケーションプログラムまたは類似物がオフセット表４ ２を使用して、大きい表３８のキーをハッシュ値、例えばほとんど密なハッシュ 表４０に対するハッシュ値索引にハッシュ化することを含む。典型的な使用法で は、ほとんど密なハッシュ表４０は、ユニコード文字属性または類似物の表を提 供するために、コンピュータを使用する事実上どのような種類の装置にでもロー ドすることができる。大きいユニコード表３８における位置に対応するユニコー ド符号点を受け取ると、ハッシュ表４０のハッシュ値が計算され、そこから属性 が見つけ出される。 本発明の動作の説明に移ると、本発明は、６５５３６のユニコード符号点の範 囲内における日本語の文字の部分集合にかなりの利益をもたらす。それにもかか わらず、本発明は、ユニコード符号点の部分集合に限定されず、明らかになると おり、いつでも大きい範囲のより小さい不連続部分集合を取り扱うときに、多く の潜在的用途がある。 簡素な例として、図２に１６個のエントリの表３８を示す。そのうち特定のエ ントリだけが、ほとんど密なハッシュ表４０に再写像される。さらに詳しくは、 ００００ｂ、０００１ｂ、００１０ｂ、０１１０ｂ、１０００ｂ、および１１１ １ｂによって索引付けされたエントリが、アプリケーションプログラムの関心対 象である。例えば、図３に概念的に示すように、（多少異なる配列法で）、００ ００ｂは、図形的に文字「Ａ」を表示するための属性を索引付けし、０００１ｂ は文字「Ｂ」を索引付けし、以下１１１１ｂが「Ｐ」を表すまで繰り返される。 これらのうち、Ａ、Ｂ、Ｃ、Ｇ、Ｉ、およびＰだけがサポートされる。容易に理 解いただけるとおり、これは一般に、可能なユニコード文字の６５５３６個のエ ントリの表から文字（例えば日本語の文字）の不連続集合を選択することに対応 する。 変換を実行するために、ステップ８００〜８０４で、大きい表３８の索引が選 択され、行（ページ）と列のビットマップ行列に展開される。図５は、１６個の エントリの表に対する４行×４列の行列４４を示す。図３において、対応して関 心のあるエントリの索引は、ビットマップにおいて対応するビットが１にセット され、図５のビットマップ行列４４では「Ｘ」で示される。（見易さのため、お よび索引の１および０との混同を避けるため）一方、他のビットは全て０（すな わち空白）である。６４ｋのユニコード索引のように１６ビットで索引付けされ る表の場合、初期行列は、例えば２５６行（８ビット）および２５６列（８ビッ ト）で構成することができる。したがって、行０は、００００ｈから００ＦＦｈ の間の任意の所望のユニコード文字に対するビットが１にセットされ、行１は、 ０１００から０１ｆｆｈまでの範囲の所望の文字に対するビットが１にセットさ れ、等々と繰り返される。 表３８の索引が図５のビットマップ行列４４に展開される本実施例の説明を続 けると、各行は、００ｂから１１ｂまでの番号が付けられたページと考えること ができ、それによって列番号は、００ｂから１１ｂのページ内へのオフセットと なる。あるいは、列をページとして使用し、行番号がページ内へのオフセットを 表すこともできる。実際、６４キロバイトの可能なユニコード文字の集合の部分 集合を取り扱う場合、列をページとし、行をオフセットとして使用すると、大抵 の場合、さらにいっそう密なパッキングが得られることが明らかになっている。 しかし、以下で説明するとおり、両方の方法を試し、最良の結果（ほとんど密な パッキング）を選択することができる。 本実施例では、図６に最もよく示すとおり、図５の元の４×４の行列４４は、 新しい行列４５に概念的に再構成され、図５の列はページになり、（図６では水 平方向に示す）、行はページ内へのオフセットになる（図６では垂直方向に示す ）。 本発明の一態様に従って、ページは一度に１枚づつ、次々に上に重ねられ(オ ーバレイ)、密な、またはほとんど密な一次元合成ビットマップ４６になる。選 択された索引（ビットマップで１のビットで表される）は不連続であり、一般的 に幅広く分散しているので、幾つかのページのビットが衝突することなく、また は少なくともほとんど衝突せずにインタレースする傾向がある。索引を表すビッ トが別のビットと衝突するときはいつでも、合成ビットマップ４６にオーバレイ される現在のページが、一文字分だけ右にシフトする。ページが衝突無く完全に インタレースする場合、シフト量が、ページオフセット表４２にそのページのオ フ セットとして記録される。 ページが次々にオーバレイされる順序は、ページがいかによくインタレースす るか、したがってどれだけのシフトが必要になるかに影響し、これが最終的にハ ッシュ表４０の大きさを決定することに注意する必要がある。したがって、最良 のパッキングを見つけ出す１つの方法は、ページ順序付けの全ての組合せを試し て、最良の結果を選択することであろう。理解いただけるように、これは極めて 高価になる（例えば、２５６行および２５６列に分割された１６ビットの索引で は、２５６の階乗の組合せが可能である）。 ページをオーバレイする適正な順序を得るためのより安価な方法は、より多く の１ビットをそのうえに含むページが、１ビットの数がより少ないページより前 に合成ビットマップ４６にオーバレイされるように、ページを順位付けすること である（つまり、最多から最少への順位付け）。この目的のために、順位付けプ ロセスがステップ８０６で呼び出され、様々なページにおける１ビットの数を計 数し、その計数に従ってページを順位付けする。そうした１ビット加重順位付け プロセスは、極めて密なパッキングを達成することが明らかになっている。実際 、他の最適化（以下で説明する）をこの順位付けプロセスと結合したときに、１ ００％の（または１００％に非常に近い）パッキングが高速で達成される。 しかし、一般的な順位付け技術にもかかわらず、ハッシュ表を開始する最初の ページが、そこの文字数に関係なく、ビットマップ行列４５の最初のページとな るように選択することが好ましい。本発明に必要というわけではないが、明らか になるとおり、所望の索引として零を選択し、零としてこのページから始めるこ とにより、大きい表３８の零索引が常に零に写像されることが確実になり、これ は空白で終了する文字列および類似物を取り扱うときに有用である。 図７は、図２０の流れ図に対応し、Ｐａｇｅ₀₀は零索引を含むので、ステップ ９００で図６の第１ページＰａｇｅ₀₀から始まるオーバレイプロセスを示す。図 ７に示すように、合成一次元ビットマップ４６_aは、単にこのページになるだけ であり、このページのシフトは行われないので、ステップ９１０で零のオフセッ トがページオフセット表４２に書き込まれる。第１ページの場合、この時点で衝 突はなく、零が選択されることを前提として、第１ページに先行する零はないの で、ステップ９００から直接ステップ９０８に続くことに注意されたい。このプ ロセスが最終的に終了したときに、この特定のビットスプリットが選択された場 台、ｐａｇｅ₀₀の各１ビットに対応する表データが、ハッシュ表４０に書き込ま れる（ステップ８１４のように）ことに注意されたい。例えば、図１５に示すよ うに、零によって索引付けられた位置に「Ａ」属性データが書き込まれ、２によ って索引付けられた位置に「Ｉ」が書き込まれる。ステップ９１４は、別のペー ジを検査し、１が得られるので、ステップ９００に戻り、そこで次のページｐａ ｇｅ₁₀が選択される。 図８は、次のページｐａｇｅ₁₀の前の合成ビットマップ４６_aへのオーバレイ を表し、これにより新しい合成ビットマップ４６_bが生成される。ｐａｇｅ₁₀が 次にオーバレイされるのは、ステップ８０６の順位付けプロセスで、この行が残 りの行に比べて、１にセットされたビットが最も多い（２個）ことが決定された ためであることに注意されたい。 ｐａｇｅ₁₀をオーバレイするために、ステップ９０２でｐａｇｅ₁₀は、最初に 、先行する零ビットの数に等しい量だけ左にシフトされる。この位置で、衝突の 検査がステップ９０４で実行される。１つのそうした衝突の検査は、現行ページ (ｐａｇｅ₁₀)のビットと前の合成ビットマップ４６_aのＡＮＤ（論理積）を取り 、結果が零かどうかを検査することによって達成される。零になれば、衝突は無 い。零でなければ、衝突が検知され、それによりステップ９０６でページは、１ ビット右にシフトされ、衝突検査が繰り返される。衝突が検知されなくなるまで 、必要なだけシフト操作が続く。 本実施例では、ステップ９０４〜９０６の衝突検知および解消プロセスにより 、ｐａｇｅ₁₀は、このページが前のビットマップ４６_aに結合される前に、零の 右に３位置分シフトする（図８に最もよく表す）。このページの３のオフセット が、図１２に最もよく示すように、ページオフセット表４２に記録される。しば らく後で（ステップ８１４で行われるように）、このビット分割（スプリット） が選択されたと仮定して、配列データ、例えば「Ｃ」および「Ｇ」の属性は、図 １６に示すようにハッシュ表４０の適切な位置に追加されることに注意されたい 。図８に示すように、合成ビットマップ４６_bは、今５ビットの長さであり、ハ ッシュ 表４０は、少なくとも五個のエントリに割り当てられる空間を持たなければなら ないことに注意されたい。したがって、合成ビットマップ４６は、ハッシュ表４ ０と同様に、シフトされたビットを収容するために必要なだけ成長するが、１だ けが関心のあるエントリを表す（索引付ける）ので、後続零ビット（空白）は、 合成ビットマップ４６の一部と考慮されない。ハッシュ表４０の最終的大きさを 決定する合成ビットマップ４６が成長する量は、値の部分集合のパッキングがど の程度密であるかによって異なる。 合成ビットマップ４６にオーバレイされる次のページ（ステップ９１４および ９００）は、ｐａｇｅ₁₁である。ｐａｇｅ₁₁およびｐａｇｅ₀₁は各々１ビットが そこにセットされているが、この実施例では、ステップ８０６の順位付けプロセ スで、ｐａｇｅ₁₁がｐａｇｅ₀₁より前に配置されるように順位付けられたと仮定 していることに注意されたい。図６の行列４５および図９に示すように、ｐａｇ ｅ₁₁には３個の先行する零ビット（空白）がある。したがって、オーバレイプロ セスを試みる前に、ステップ９０２で、ｐａｇｅ₁₁は、衝突を検査する前に、最 初に３回左にシフトされる。明らかなとおり、ステップ９０４で、この（マイナ ス３の）オフセットに衝突が存在することが決定され、したがってステップ９０ ６でページは１つ右にシフトされ（オフセットが増分される）、衝突試験が繰り 返される。今度はステップ９０４で、衝突が無いと決定され、したがってステッ プ９０８でｐａｇｅ₁₁はマイナス２のオフセットで前の合成ビットマップ４６_b に結合され、新しい合成ビットマップ４６_c（図９）になる。ステップ９１０で 、このページのマイナス２のオフセットが、図１３に最もよく示すように、ペー ジオフセット表４２の適切な位置（位置３）に記録される。後で、ステップ８１ ４で行われるように、この索引に対応するデータ、例えば「Ｐ」の属性が図１７ に示すように、ハッシュ表４０における合成ビットマップ４６_cの索引位置に対 応する位置に格納されることに注意されたい。 合成ビットマップ４６にオーバレイされる最後に残った１枚のページは、ｐａ ｇｅ₀₁である。図６の行列４５および図１０に示すように、ｐａｇｅ₀₁には先行 する零ビット（空白）が無い。したがって、ｐａｇｅ₀₁は、衝突検査の前に、ス テップ９０２で左にシフトされない。明らかなように、ステップ９０４で零オフ セットに衝突が存在し、したがってこのｐａｇｅは、ステップ９０６で１つ右に シフトし、オフセットが増加され、ステップ９０４の衝突検査が繰り返される。 容易に理解できるように、ステップ９０４で衝突が検出され続け、ｐａｇｅ₀₁が プラス５の位置分オフセットされるまで、ページはステップ９０６でシフトされ る。その結果、ｐａｇｅ₀₁は、プラス５のオフセットで前の合成ビットマップ４ ６_cに結合され、新しい最終合成ビットマップ４６が形成される（図１０）。ｐ ａｇｅ₀₁前の合成ビットマップの大きさ全体分シフトしたことに注意されたい。 さらに詳しくは、前のビットマップ４６_cが１００％パッキングされていたので 、ｐａｇｅ₀₁は、前の合成ビットマップの終わりの位置からオーバレイされた。 １００％パッキングを検査し、検知された場合には、ビットマップの先頭から始 めて終わりまで繰り返しシフトするのではなく、すぐに最後に次のページをオー バレイすることが可能であることに注意されたい。 ステップ９１０で、このページの５のオフセットが、図１４に最もよく示すよ うに、ページオフセット表４２に記録される。プロセスは次に図１９に戻る。再 び、少し後のステップ８１４で、この索引に対応する属性データ、例えば「Ｂ」 の属性が、図１８に示すように、合成ビットマップ４６の索引位置に対応する位 置ハッシュ表４０に格納されることに注意されたい。 この時点で、初期の１６個のエントリの表３８の６個の分散索引および対応す るデータを、４個のエントリ（例えばバイト）のページオフセット表４２と共に 、０から５までの範囲の値によって索引付けされた密にパックされたハッシュ表 ４０に再写像することができる。このような小さい例でも、メモリの節約が顕著 になることに注目されたい。例えば、初期の１６個のエントリの表３８に各索引 ごとに１キロバイトが割り当てられた場合、この表は１６キロバイトのメモリを 必要とする。しかし、同じデータを６キロバイトのハッシュ表＋ページオフセッ ト表のための４個の格納単位（例えば語またはバイト）に保存することができる 。実際、以下で説明するように、初期の大きい表３８に対するキーを密なハッシ ュ表４０のハッシュ値索引に変換するために必要なものは、ページオフセット表 ４２だけである。さらに大きい配列の大きい部分集合でも同様の節約が達成され 、自動再写像プロセスから特に利益を得られる。 本発明に必要というわけではないが、最適に高密なパッキングを見つけ出すた めに，行と列に同じ番号を持たないものを含めて、様々なビットマップ行列を試 すことができる。例えば、１６ビットの索引の場合、８ビット×８ビット以外の 分割を使用して、上述のような方法で値を再写像することができる。最適分割の 発見を達成するために、ステップ８０８では、合成ハッシュ表４０の大きさおよ びページオフセット表４２を、ハッシュ表４０に対応する統計として保存する。 次に、プロセスはステップ８０２にループバックし、その都度値を行と列に分割 する方法を変えながら、別の行列を構成する。例えば、１６ビットの索引は、５ １２列の１２８ページ（７×９ビット）、１２８列の５１２ページ（９×７ビッ ト）１０２４列の６４ページ（６×１０ビット）等々のように分割することがで きる。特定のループ反復により、以前の最良の分割が改善される場合には、その ページオフセット表および付随する統計を前のものと置換し、それによって全て の（適正な）分割を試みた後、最少量の空間を使用する分割が最終的に残る（ス テップ８１２）。上述の写像動作は充分に高速であるので、この方法により得ら れる最適写像法が認識されるまで、全ての実際的な組合せを試みることができる ことに注目されたい。さらに、上述のとおり、いったん行と列に分割した上で、 重ねられるページを垂直方向および水平方向から観察して、最適可能なパッキン グを見つけだすことができる。最適写像が見つかったら、そのためのオフセット 表４２を使用して、ステップ８１４において元の表エントリを密な、またはほと んど密なハッシュ表４０に書き込むことができる。 ページオフセット表を使用してハッシュ表に対するハッシュ値索引を計算する 方法について説明する。図２１に別のコンピュータシステムが示されている。図 ２１では、図１の場合と同様の構成要素に対しては、図１における符号より１０ ００高い符号を使用した。例えば比較的パワーの低いハンドヘルドコンピュータ 装置とすることができるこのシステム１０２０では、記憶装置１０２４は、ユニ コード文字などのような選択された文字を表示する目的などのために、完成した ハッシュ表１０４０およびページオフセット表１０４２を含む。したがって、本 発明の第二態様は、元の大きい表３８のキーから、密なハッシュ表１０４０に対 する索引として機能するハッシュ値１０４４への変換を取り扱う。表１０４０ および１０４２は一般的に、ＲＯＭまたは類似物にバーンインするなど、不揮発 性メモリに格納される。 ハッシュ計算を達成するために、アプリケーションプログラム１０４８または 類似物が最初に、ページオフセット表１０４２およびハッシュ表１０４０を記憶 装置１０２４にロードする（またはすでにロードされている場合には、探し出す ）（図２２のステップ１１００）。キー１０４６（入力値）をアプリケーション プログラム１０４８または類似物が受け取り、ハッシュ計算プロセス１０５０に 渡し、それによりステップ１１０４（図２２）で、値は最初に同一ビットグルー プに分割され、これはページオフセット表１０４２を構成するために使用される 。ビット分割は、ページオフセット表１０４２の大きさから明らかである。すな わち、ページオフセット表１０４２のエントリの数がページの数に等しく、した がってページのオフセット情報を格納するために使用されるビット数を表す。例 えば、１２８個のエントリは７ビットに対応する。いうまでもなく、分割および その他の情報（例えば、対応するハッシュ表のファイル名）もまた、ページオフ セット表１０４２によりヘッダ情報または類似物に維持することができる。 いかなる場合でも、初期の大きい表３８に対応する入力値を受け取ると（垂直 方向の列がページになる場合）、値の高位部分がステップ１１０４の一ステップ として計算プロセス１０４８によってマスクされ、ページ番号を表す適切な数の 有効な低位ビットが残される。簡単な例で、４つの可能なビットのうち２つのビ ットが高位部分に当たり、したがって上位の２ビットがマスクされる。残りの２ ビットは、オフセット表１０４２への零を基底とする索引として使用される。例 えば「Ｇ」文宇を表示する目的などのために、０１１０ｂを受け取ると、上位ビ ットがマスクされ、１０ｂが残る。同様に、ステップ１１０４内で、マスクされ ない上位ビットをページ番号内のビットの数と同数だけ右にシフトすることによ って、ページ内へのオフセットを表す上位ビットが得られる。 ステップ１１０６で、ページ番号は、ページオフセット表１０４２への索引と して使用され、それによって対応するページのオフセット値を決定するために探 索動作が実行される。本実施例では、１０ｂから３のオフセット値が得られる。 ステップ１１０８で、この値はページ内へのオフセットに追加される（ステップ １１０４における上位ビットのマスキングおよびシフトから決定される０１ｂに 等しい）。結果（３＋１＝４）がハッシュ表１０４０に対する計算されたハッシ ュ値索引であり、ステップ１１１０でアプリケーションプログラム１０４８に返 され、アプリケーションプログラムは次にハッシュ表１０４０から適切なデータ を獲得する。お分かりのように、図１８のハッシュ表４０の４個（１００ｂ）の エントリは、適切に「Ｇ」文字を索引付けする。下表は全ての有効な計算の結果 を示すが、これについて本書ではそれ以上詳しく説明しない。 ご理解いただけるように、計算はＡＮＤ（論理和）（マスキングのため）、シ フト、配列の索引付け（ページオフセット表１０４２）、および加算のみで構成 され、きわめて高速である。 正確な結果を出すために、ハッシュ計算は有効な入力値、すなわちハッシュ表 を使用するアプリケーションプログラムによってサポートされる入力値を必要と することに注意すべきである。ハッシュ計算を実行する前に、有効性検査（ステ ップ１１０２で表されるような）を値に実行して、有効な入力に対応することを 確認することができる。入力値が有効であれば、有効なキーから衝突の無い一意 の結果が得られるので、ハッシュは完全である。 さらに、ハッシュ表データ自体以外に、ハッシュ値を計算し続けるために必要 なものはオフセット表だけである。したがって、合成ビットマップおよび統計な ど、オフセット表の作成中に蓄積されたその他の情報は廃棄することができる。 いうまでもなく、例えば２つ以上をシステムで利用できる場合には、アプリケー ションプログラムが適切なハッシュ表および対応するオフセット表をロードでき るようにするために、必要とあらば、幾つかのメタデータおよび／またはその他 の情報をオフセット表および／またはハッシュ表と共に維持することもできる。 以上の詳細な説明から分かるように、より大きい範囲の不連続値の任意の部分 集合に対する完全なハッシュを生成する方法および機構を提供する。この方法お よび機構は、ハッシュ値の非常に高速な計算を可能にしながら、ハッシュ値を一 緒に密にパックするものである。この方法および機構は、自動的に作動し、不連 続ユニコード点の部分集合で特によく機能する。この方法および機構は、高速で あり、信頼でき、費用効果が高く、柔軟であり、拡張性がある。 本発明は、様々な変更および代替構成が可能であるが、その特定の例示的実施 形態を図面に示し、以上に詳細に記述した。しかし、本発明を開示した特定の形 態に限定する意図はなく、反対に、本発明は、本発明の精神および範囲に該当す る全ての変更、代替構成、および均等物を網羅するものであることを理解された い。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＣＹ， ＤＥ，ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，Ｉ Ｔ，ＬＵ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ ，ＣＦ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ， ＮＥ，ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＧＨ，ＧＭ，ＫＥ，Ｌ Ｓ，ＭＷ，ＳＤ，ＳＺ，ＵＧ，ＺＷ)，ＥＡ(ＡＭ，ＡＺ ，ＢＹ，ＫＧ，ＫＺ，ＭＤ，ＲＵ，ＴＪ，ＴＭ)，ＡＬ ，ＡＭ，ＡＴ，ＡＵ，ＡＺ，ＢＡ，ＢＢ，ＢＧ，ＢＲ， ＢＹ，ＣＡ，ＣＨ，ＣＮ，ＣＵ，ＣＺ，ＤＥ，ＤＫ，Ｅ Ｅ，ＥＳ，ＦＩ，ＧＢ，ＧＥ，ＧＨ，ＧＭ，ＧＷ，ＨＵ ，ＩＤ，ＩＬ，ＩＳ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ， ＫＺ，ＬＣ，ＬＫ，ＬＲ，ＬＳ，ＬＴ，ＬＵ，ＬＶ，Ｍ Ｄ，ＭＧ，ＭＫ，ＭＮ，ＭＷ，ＭＸ，ＮＯ，ＮＺ，ＰＬ ，ＰＴ，ＲＯ，ＲＵ，ＳＤ，ＳＥ，ＳＧ，ＳＩ，ＳＫ， ＳＬ，ＴＪ，ＴＭ，ＴＲ，ＴＴ，ＵＡ，ＵＧ，ＵＺ，Ｖ Ｎ，ＹＵ，ＺＷ

Claims (1)

1. 【特許請求の範囲】 １．ある範囲の値を含むコンピュータシステムで、前記範囲の値の不連続部分集 合を完全なハッシュを用いて連続した、またはほとんど連続したより小さい範囲 に変換する方法において、 前記範囲の値の中から値の部分集合を選択するステップと、 前記範囲を二次元行列に編成するステップであって、前記行列の１つの次元が ページを表し、他の次元が前記ページ内へのオフセットを表し、前記行列のペー ジと該ページ内へのオフセットとの各交叉位置に、その交叉によって表される値 が部分集合に選択された値であるか否かを示す写像情報を含むようにするステッ プと、 各ページを選択し、各ページの写像情報を検査して一次元配列内の写像情報と の衝突が無いかを調べ、衝突が検知されなくなるまで各ページをある量だけシフ トし、ページの写像情報を一次元配列のシフト後の位置にオーバレイし、シフト 量を記録することによって、前記行列を一次元配列に変換するステップと、 を具えたことを特徴とする方法。 ２．前記行列および一次元配列がビットマップであり、写像情報がビットの値に 格納されることを特徴とする請求項１に記載の方法。 ３．前記方法がページを順序付けの順番に並べるステップをさらに含み、各ペー ジを選択する前記ステップが順序付けの順番に従って各ページを選択するステッ プを含むことを特徴とする請求項１に記載の方法。 ４．ページを順序付ける前記ステップが、ページにおける値が部分集合に選択さ れた値であることを写像情報が示す回数を計数するステップと、最も高い回数か ら最も低い回数への順番にページを順序付けるステップとを含むことを特徴とす る請求項３に記載の方法。 ５．ページを順序付ける前記ステップが、行列内の第１ページを順序付けの順番 における第１ページとして選択するステップを含むことを特徴とする請求項３に 記載の方法。 ６．値の範囲の値が複数のビットで構成される二進数に等しく、行列の次元が前 記値を表すビットの分割に対応することを特徴とする請求項１に記載の方法。 ７．複数のビット分割を選択するステップと、各々のビット分割を用いて編成お よび変換のステップを繰り返すステップと、各ビット分割について部分集合の連 続範囲に対応する統計情報を獲得するステップと、その統計と他の部分集合範囲 の統計を比較して部分集合値の範囲を選択するステップとをさらに具えたことを 特徴とする請求項６に記載の方法。 ８．値の範囲が情報の表に対応し、前記方法は、表からの情報を、ハッシュ表の 、記録されたページシフト情報とそれに対応する選択された値のそのページ内へ のオフセットとに対応する位置に書き込むステップをさらに具えたことを特徴と する請求項１に記載の方法。 ９．不連続範囲の値を受け取るステップと、前記値をページ番号とそのページ内 へのオフセットとに分離し、そのページのシフト量を探索し、そのページ内への オフセットに前記シフト量を加算することによって前記値を部分集合範囲の値に ハッシュ化するステップをさらに具えたことを特徴とする請求項１に記載の方法 。 １０．値の範囲が０から６５５３５までの範囲であることを特徴とする請求項１ に記載の方法。 １１．値により可能なユニコード符号点を表し、値の部分集合により選択された ユニコード符号点を表すことを特徴とする請求項１０に記載の方法。 １２．ある範囲の値を含むコンピュータシステムにおいて、前記範囲の値の不連 続部分集合を完全なハッシュを用いて連続した、またはほとんど連続したより小 さい範囲に変換する機構において、 前記範囲の値の中から値の部分集合を選択する手段と、 前記範囲を二次元行列に編成する手段であって、前記行列の１つの次元がペー ジを表し、他の次元が前記ページ内へのオフセットを表し、前記行列のページと 該ページ内へのオフセットとの各交叉位置に、その交叉によって表される値が部 分集合に選択された値であるか否かを示す写像情報を含むようにする手段と、 各ページを選択することによって前記行列を一次元配列に変換する手段であっ て、該手段が各ページの写像情報を検査して一次元配列内の写像情報との衝突が 無いかを調べる手段と、衝突が検知されなくなるまで各ページをある量だけシフ トする手段と、ページの写像情報を一次元配列のシフト後の位置にオーバレイす る手段と、シフト量を記録する手段とから構成される手段と、 を具えたことを特徴とする機構。 １３．前記行列および一次元配列がビットマップであり、写像情報がビットの値 に格納されることを特徴とする請求項１２に記載の機構。 １４．ページを順序付けの順番に並べる手段をさらに具え、各ページを選択する 前記手段が順序付けの順番に従って各ページを選択する手段を含むことを特徴と する請求項１２に記載の機構。 １５．ページを順序付ける前記手段が、ページの値が部分集合に選択された値で あることを写像情報が示す回数を計数する手段と、最も高い回数から最も低い回 数への順番にページを順序付ける手段とを含むことを特徴とする請求項１４に記 載の機構。 １６．ページを順序付ける前記手段が、行列内の第１ページを順序付けの順番に おける第１ページとして選択する手段を含むことを特徴とする請求項１４に記載 の機構。 １７．値の範囲の値が複数のビットで構成される二進数に等しく、行列の次元が 前記値を表すビットの分割に対応することを特徴とする請求項１２に記載の機構 。 １８．複数のビット分割を選択する手段と、各々のビット分割を用いて編成およ び変換のステップを繰り返す手段と、各ビット分割について部分集合の連続範囲 に対応する統計情報を獲得する手段と、各々の部分集合の統計を比較して部分集 合値の範囲を選択する手段とをさらに具えたことを特徴とする請求項１７に記載 の機構。 １９．値の範囲が情報の表に対応し、前記機構がハッシュ表と、表からの情報を 、ハッシュ表の、記録されたページシフト情報とそれに対応する選択された値の そのページ内へのオフセットとに対応する位置に書き込む手段とをさらに具えた 請求項１２に記載の機構。 ２０．不連続範囲の値を受け取る手段と、前記値をページ番号とそのページ内へ のオフセットとに分離する手段と、そのページのシフト量を探索する手段、およ びそのシフト量をそのページ内へのオフセットに加算する手段を含み、前記値を 部分集合範囲の値にハッシュ化する手段とをさらに具えたことを特徴とする請求 項１２に記載の機構。 ２１．値の範囲が０から６５５３５までの範囲であることを特徴とする請求項１ ２に記載の機構。 ２２．値により可能なユニコード符号点を表し、値の部分集合により選択された ユニコード符号点を表すことを特徴とする請求項２１に記載の機構。