私は、既知の固定サイズ (64 ビットまたは 128 ビットなど) の任意の大きな符号なし整数にインデックスを付けるアルゴリズムを使用しています。utf-8 文字列にも適用できるようにしたいのですが、そのためには、任意の長さの特定の文字列を、そのような形式の符号なしバイトの固定サイズ配列にマップする信頼できる方法が必要です。少なくとも文字列のプレフィックスの辞書順が保持されるようにします。
これに対する素朴なアプローチは、単純にX文字列の最初の文字を取得し、各文字に完全な 4 バイトを与え、必要に応じて実際の値の前にゼロを追加することです。ただし、これにはX * 4バイトが必要です。よりスペース効率の良い方法でこれを行う方法があることを願っています。
- - 編集 - -
非常に重要なことは、衝突が許容されることです。
上記の素朴なアプローチを使用して、文字列を指定します。
['Alabama', 'Alakazam', 'Alaska', 'Arkansas', 'Corduroy']
3に設定Xすると、「Alabama」、「Alaska」、および「Alakazam」が衝突します。マッピングから生成される一意の 12 バイト値は 3 つだけです (「Ala」の 1 文字あたり 4 バイトの表現)。 、「Ark」および「Cor」)。ただし、これら 3 つの値が辞書式順序を維持することが非常に重要です。
4 バイトを使用する必要があるのは、これが 1 つの文字が utf-8 で占有できる最大のサイズである (と私は信じている) ためです。マッピングが固定サイズのバイト配列を与えることを保証するために (少なくともこのスキームでは)、通常は 1 バイトしか占有しない ASCII 文字でさえ、最大 4 バイトを占有する必要があります。
'A' => 01100001、ゼロでパディング: 0000000000000000000000001100001
'l' => 01101100、ゼロでパディング: 0000000000000000000000001101100
'a' => 01100001、ゼロでパディング: 0000000000000000000000001100001
したがって、= 4 の例では、X「Ala」で始まる文字列は次のようにマップされます。
000000000000000000000000011000010000000000000000000000000110110000000000000000000000000001100001
96 ビットの unsigned int として表示すると、この例の他の接頭辞 (「Ark」と「Cor」) のマッピングの値よりも小さい値を持つため、マッピングが辞書編集順序を保持するという要件を満たします。 .
このスキームは機能しますが、文字列のサイズ要件が 4 倍にも膨れ上がります。希望は、より少ないX * 4バイト数で utf-8 プレフィックス インデックス作成を達成するマッピング スキームを見つけることです。