問題タブ [perfect-hash]

順序付けられていないマップで完全なハッシュを実現したい。何かにマッピングされているコンパイル時の既知の文字列のセットがあります。それらの完全なハッシュ関数を生成したい。unordered_map のサイズを既知の文字列セットのサイズの 3 倍にすると、完全なハッシュ関数 (シード番号) を見つけることができました。その数を最小限にしたい。関連する質問ですが、より大きな順序付けられていないマップを使用すると、より高速なマップが得られるというのは本当ですか?

Google の CityHash 関数で遊んでみました: http://code.google.com/p/cityhash/

それぞれサイズ N1 と N2 の 2 つの 32 ビット符号なし整数の並べ替えられていない配列があります。各配列には重複が含まれる場合があります。各キーの頻度を記録するために、各値 (2^32 の可能なキー) をサイズ (N1 + N2) のバイト配列内のスポットにマップしたいと思います。重複するキー値は、この配列内の同じ位置にマップする必要があります。さらに、各整数の頻度が 100 を超えることはありません (これが、スペースを節約するために各キーの頻度を記録するためにバイト配列を選択した理由です)。最大可能周波数がこれを超える場合は、単純にバイト配列を short の配列などに変更します。

最後に、サイズ N1 + N2 の配列が必要です。重複が発生する可能性があるため、必ずしもすべてのエントリが使用されるとは限りません。各一意のキー値の頻度があります。最悪の場合、1 バイトのエントリのみが使用され (たとえば、両方の配列のすべての値が同じ)、((N1 + N2) - 1) 個のエントリが未使用のままになります。最良のシナリオでは、すべてのバイト エントリが使用されます。

私が理解していることから、既知の数の未知のキー (N1 + N2; すべて 0 - 2^32 の範囲) を既知の数のスポット (N1 + N2)にマップするための最小限の完全なハッシュ関数を見つける必要があります。他にもいくつかの投稿を見つけることができましたが、どちらの回答も基本的に gperf を使用すると述べています。

この状況で最小限の完全なハッシュ関数を作成することは可能ですか?

最小限の完全ハッシュ関数

2 つ目 (最小完全ハッシュ関数) は、まさに私がやろうとしていることです。

回答からソースコードを期待するのではなく (ちなみに私は C を使用しています)、 N 個のバケットに対して N 個の可能な正の整数に対して最小限に完全なハッシュ関数を作成する方法について説明したいと思います。未使用のスペースがたくさんある可能性のあるすべての整数の直接マッピングの 4 GB 配列でこれを簡単に行うことができますが、この大量の非効率なスペースを減らしたいと思います。また、主に教育目的でハッシュ自体についてさらに学ぶために、外部ライブラリを使用しないことも望んでいます。

私の使用例では、JavaScript トラッカーは、訪問者がサイトにアクセスするたびに、次の式を使用して一意の ID を生成します。

次のような文字列を生成します (rfc4122):

次に、Mahout で読み取ることができる Number (Java の BigInteger など) でその文字列をエンコードする必要があります。同様に、(PHP で) 復元して結果を表示します。それを行うための高速で一貫した信頼できる方法はありますか?

いくつかの解決策は次のとおりです。

• 可能な各文字 (英数字 + '-') を数値 [1..M] にマッピングし、それに応じて各文字位置を合計します。
• md5 ハッシュから 2 つの long を取得します
• ハッシュマップをメモリに保持する

どんなアイデアでも大歓迎です！

ここに問題があります。プロジェクトで MongoDB を使用しているため、16 進数のアルファベットのみを使用して 24 文字の ObjectId があります。私は自分のプロジェクトでプロバイダーに http 要求を作成しています。この要求では、コールバックの目的で一意の ID を入力する必要がありますが、プロバイダーはこの ID に20 文字しか許可していません。理由はわかりません。

だから、私の質問は、16文字のアルファベット（ヘキサ）で、16 ^ 24の可能なモンゴIDがありますよね？HTTP リクエストで 64 個の異なる文字 ([0-9][az][AZ]-_) に基づく Id を使用すると仮定すると、間違っている場合は訂正しますが、64^20 の可能な ID があると思います。技術的には、可能なすべての MongoDB ObjectId を対応する ID でエンコードすることは可能ですよね?

古典的な Base64 エンコーディングのようですが、不思議なことに、これは期待どおりに機能しません。生成された文字列が元の文字列よりも大きいため、Base64 エンコーディングがどのように機能するかを理解していなかったと思います...

これはすべて可能だと思いますか、それとも私は何かを完全に見逃しましたか?

前もって感謝します！

編集: 私の同僚の 1 人は、動作するように見える何かを試しました。Javaコードは次のとおりです。

私が無視する理由により、これを行うことは同じではありません:

そしてそれは印刷します：NTM4ODQ1OTRlNGIwNjk1ZjM2NmY4MTI4

Go で Minimalistic Acyclic Finite State Automaton (MA-FSA; 特定の種類の DAG) を実装しており、EOW (単語の終わり) を示すノードに追加のデータを関連付けたいと考えています。MA-FSA では、そのノードで終わる単語が複数ある可能性があるため、従来のアプローチは不可能です。そのため、代替手段として最小限の完全ハッシュ関数を検討しています。

Steve Hanov は、ブログ投稿の上部にある「修正」ボックスで、Lucchesi と Kowaltowski によるこの論文で説明されている方法を使用したと述べています。図 12 (19 ページ) を見ると、ハッシュ関数が説明されています。

8 行目では と を参照してFirstLetterいPredecessor()ますが、それらが何であるかについては説明していません。または、私はそれを見ていません。彼らは何ですか？

私が理解できるのは、ツリーをたどり、Number各ノードから加算するだけだということだけですが、それはおそらく正しいとは言えません。紙が言うように、それは大きすぎる数値を生成し、1対1ではありません. 私は何かを誤解していますか？

gperf が自分のプロジェクトに適していることがわかり、現在、生成されたテーブルのサイズを最適化する方法を探しています。スイッチ -i と -j は決定論的にテーブルの長さに影響を与えるため、これらの値を反復処理して最小のテーブル長を見つける小さなスクリプトを作成しました。スクリプトは、現在の最小テーブルを取得するための -i 値と -j 値、およびスクリプトの終了時に現在試行されている値を保存するため、後で検索を続行できます。

これで、スイッチ -m が存在することがわかりました。これは、私の小さなスクリプトで行うこととまったく同じことを行うことを示しています。このスイッチを使用すると、単一の反復のみで gperf を呼び出すよりもはるかに高速になると思います。しかし、gperf ヘルプで見つけることができなかった gperf 呼び出しを置き換えるために、2 つのことを知る必要があります。

1. -m スイッチを使用した場合に -i と -j が試される場合、どの値が試されますか?
2. -i と -j のどの値が実際に使用されているか、つまり、現在の gperf 呼び出しで検出されたテーブルの長さの最小値につながる値を知るにはどうすればよいですか?

4000 個の文字列があり、これらの文字列を使用して完全なハッシュ テーブルを作成したいと考えています。文字列は事前にわかっているので、最初のアイデアは一連のifステートメントを使用することでした。

ただし、これは非常に非効率的です。より良い方法はありますか？

C++ 関数のセットがあります。この関数を次のようなハッシュテーブルにマップしたい: unordered_map<function<ReturnType (Args...)> , SomethingElse>、SomethingElseこの質問には関係ありません。

この一連の関数は以前から知られており、小規模 (たとえば 50 未満) であり、静的 (変更される予定はありません) です。

ルックアップのパフォーマンスが重要であるため ( で実行する必要がありますO(1))、完全なハッシュ関数を定義したいと考えています。

このシナリオに最適なハッシュ関数ジェネレーターはありますか?

完全なハッシュ関数ジェネレーター ( GPERFやCMPHなど) が存在することは知っていますが、それらを使用したことがないため、それらが私のケースに適しているかどうかはわかりません。

理由：

FC++ で記述されたプログラムが与えられた場合、ユーザーがこのプログラムで定義された関数のサブセットを選択できるフレームワークを設計しようとしています。

fに属するそれぞれについて、フレームワークはメモ化戦略をF実装します: input で呼び出すと、何らかのデータ構造内に格納されます。したがって、 で AGAIN を呼び出す場合は、(時間のかかる) 計算を再度実行せずに戻ります。fi(i,o)fio

「すでに計算された結果」は、さまざまなユーザー間で (おそらくクラウド上で) 共有されるため、ユーザーu1が既に計算を行っている場合o、ユーザーは(以前と同じアノテーションを使用して) を呼び出してu2計算時間を節約できます。fi

明らかに、ペアのセットを保存する必要があります(f,inputs_sets)(inputs_sets前に説明した計算済みの結果セットはどこにありますか )。

したがって、このシナリオのコメントで提案されている「列挙トリック」を使用することは、すべてのユーザーがまったく同じ列挙を使用すると仮定すると、解決策になる可能性があります。これは問題になる可能性がありf1ます。と(so )のみ、一方( so )のみをメモしたいですか? プログラムで定義されているすべての関数を列挙するのはやり過ぎの解決策かもしれませんが、これは大量のメモリの浪費を引き起こす可能性があります。f2f3u1f1f2F={f1,f2}u2f3F={f3}