c - アナグラムを分離するための完全/理想的なハッシュ

Question

アナグラムの文字列をテストする際の高速化動作を高速化するために、私は素数ベースのハッシュ スキームを思いつきました。

基本的な考え方は、文字を素数にマッピングし、これらの素数の積を計算することです。文字を並べ替えても結果は同じになり、結果が任意に大きくなる可能性がある場合、他の文字の組み合わせで同じ結果が得られることはありません。

私は当初、これを単なるハッシュとして想定していました。最終的に、製品はオーバーフローし、他の文字の組み合わせにエイリアスを設定し始めます。ただし、最も頻繁に使用される文字を最小の素数にマッピングすることにより、積はゆっくりと成長し、多くの場合、オーバーフローを完全に回避できます。この場合、完全なハッシュが得られ、追加のテストなしで明確な肯定的な結果と否定的な結果の両方が得られます。

注目に値するのは、オーバーフローする前にコーディング スペースを非常に効率的に埋めないことです。素因数が 103 を超える結果はありません。小さな素数の分布は固定されており、必ずしも文字の頻度と完全に一致するとは限りません。

今、これよりもはるかに優れたものがあるかどうか疑問に思っています。完全なハッシュでより多くの結果をカバーし、残りのケースで強力な分布を持つもの。

私が考えることができる最も高密度のコーディング スキームは、文字を並べ替えてから、エントロピー コーダーを使用して単語にパックすることです。このスキームでは、各位置に範囲制約が適用されるため、文字の頻度は明らかに非常に偏っています (たとえば、z で始まる並べ替えられた配列の可能性は、az で終わる並べ替えられた配列の可能性よりも大幅に低くなります)。

しかし、それは大変な作業のように聞こえますが、オーバーフローの場合に適切な分散が保証されるとは思えません。

おそらく、文字をマッピングするためのより良い一連の要因と、エイリアシングのリスクがいつ開始されたかを検出するより良い方法があるでしょう. または、乗算に依存しないハッシュ方式ですか? 計算しやすいもの？

だから〜だ：

• 可能な限り多くの現実世界の入力に対する完全なハッシュ (適切な数のビット)。
• 2 つのケースを区別する手段を備えた、残りのケースの強力なハッシュ。
• 簡単に計算できます。

英語の制約 (典型的な英語のような単語構造を持つ 26 文字) は問題ありません。マルチバイトコーディングスキームは、まったく別の問題です。

私はそれを理解しているので、Cコードが好まれます。

Answer 1

ここにフランコアの回答を実装しました： https://github.com/sh1boot/anagram/blob/master/bitgram.c

http://ftp.debian.org/debian/pool/main/s/scowl/wbritish_7.1-1_all.debを辞書として使用すると、完全なコードの次の割合が得られます (ハッシュ比較からの正と負の両方の一致) ) これらのコーディング スキームを使用して:

order  | frequency|  alphabet| frequency|  alphabet| frequency
code   |    prime |    unary |    unary |  huffman |  huffman
-------|----------|----------|----------|----------|----------
64-bit |   93.95% |  100.00% |  100.00% |  100.00% |  100.00%
32-bit |   24.60% |   69.14% |   74.23% |   86.57% |   90.58%
28-bit |   15.20% |   41.75% |   60.27% |   68.16% |   74.34%
24-bit |    8.21% |   13.14% |   38.55% |   42.67% |   50.34%
20-bit |    3.72% |    3.35% |   16.73% |   19.41% |   25.59%
16-bit |    1.31% |    0.82% |    4.86% |    5.51% |    9.18%

これは、ビットパック ヒストグラム エンコーディングのどのバリアントでも、辞書全体を完全な 64 ビット ハッシュでキャプチャし、辞書の 3 分の 2 以上を 32 ビット ハッシュでキャプチャできることを示しています。一方、プライム プロダクト スキームは 64 ビットでも 100% に到達するのに苦労しており、32 ビット ハッシュでは辞書の 4 分の 1 をカバーすることさえできません。

ただし、このリストには多くのアポストロフィが含まれており、64 ビット ミスのほぼすべて (すべてではない) にアポストロフィが含まれています。その文字を度数表の適切な場所に配置すると役立つ場合があります。

追加のテスト:

周波数/ハフマン、オーバーフロー:

88aff7eb53ef9940: Pneumonoultramicroscopicsilicovolcanoconiosis

周波数/ハフマン、64 ビット完全:

17415fbc30c2ebf7: Chargoggagoggmanchauggagoggchaubunagungamaugg
018a6b5dda873fba: Supercalifragilisticexpialidocious
00021ae1bcf50dba: Pseudopseudohypoparathyroidism
00070003dd83b5fb: Floccinaucinihilipilification
00002b800ebbdf7a: Antidisestablishmentarianism
000006c6ab75b3f9: Honorificabilitudinitatibus
0000000421b2ad94: glyptoperichthys
0000000201b2ad94: pterygoplichtys

おそらく、境界近くに位置する可能性が高い単語に対してチューニングを行う必要があるのは、それらの単語がその分布に強く影響するプロパティ (たとえば、元の言語) を持っている可能性があるためです。彼らはオーバーフローします。