15

最近、私はインタビューに参加し、ハッシュの衝突に関する良い質問に直面しました。

問題 : 文字列のリストが与えられた場合、アナグラムをまとめて出力します。

例 :

i/p : {行為、神、動物、犬、猫}

o/p : 行為、猫、犬、神


ハッシュマップを作成し、単語をキーとして、値をアナグラムのリストとして配置したい

衝突を避けるために、ソートしてソートされた単語をキーとして使用する代わりに、アナグラムの一意のハッシュ コードを生成したいと考えています。

チェーンを使用する以外に衝突を処理するハッシュ アルゴリズムを探しています。act と cat の両方に同じハッシュ コードを生成するアルゴリズムが必要です。次の単語が値リストに追加されるようにします。

誰でも良いアルゴリズムを提案できますか?

4

7 に答える 7

28

ソートされた文字列でハッシュするのはとてもいいことです。私はおそらくそうしていたでしょうが、実際には遅くて面倒かもしれません。これが機能するかどうかわからない別の考えがあります-好きなだけ小さく、文字セットと同じサイズの素数のセットを選択し、文字からそれに高速マッピング関数を構築します。次に、特定の単語について、各文字を一致する素数にマップし、乗算します。最後に、結果を使用してハッシュします。

これは Heuster が提案したものと非常に似ていますが、衝突が少ないだけです (実際、任意の数の素数分解の一意性を考えると、偽の衝突はないと思います)。

簡単な例 -

int primes[] = {2, 3, 5, 7, ...} // can be auto generated with a simple code

inline int prime_map(char c) {
    // check c is in legal char set bounds
    return primes[c - first_char];
}

...
char* word = get_next_word();
char* ptr = word;
int key = 1;
while (*ptr != NULL) {
    key *= prime_map(*ptr);
    ptr++;
}
hash[key].add_to_list(word);

[編集]

一意性についてのいくつかの言葉 - 任意の整数は、素数の乗算への単一の内訳を持っているため、ハッシュ内の整数キーが与えられると、ハッシュされる可能性のあるすべての文字列と、これらの単語のみを実際に再構築できます。素数 p1^n1*p2^n2*... に分割し、各素数を対応する文字に変換します。p1 の文字は n1 回表示されます。明示的に使用していない新しい素数を取得することはできません。素数であるということは、他の素数を乗算しても取得できないことを意味します。

これにより、別の改善が可能になります。文字列を構築できる場合は、ハッシュを入力するときに見た順列をマークするだけで済みます。順列は辞書式の順序で並べることができるため、それぞれを数字に置き換えることができます。これにより、実際の文字列をハッシュに格納するスペースが節約されますが、より多くの計算が必要になるため、必ずしも適切な設計上の選択ではありません。それでも、それはインタビューの元の質問をうまく複雑にします:)

于 2013-09-13T11:45:16.773 に答える
6

ハッシュ関数 : 各文字にプライマリ番号を割り当てます。ハッシュ コードの計算中に、その文字に割り当てられた素数を取得し、既存の値に乗算します。これで、すべてのアナグラムが同じハッシュ値を生成します。

例：a - 2、c - 3 t - 7

cat のハッシュ値 = 3*2*7 = 42 act のハッシュ値 = 2*3*7 = 42 同じハッシュ値を持つすべての文字列を出力します (アナグラムは同じハッシュ値を持つことになります)

于 2013-09-14T06:19:43.860 に答える
3

他のポスターは、文字を素数に変換し、それらを乗算することを提案しました。これを大きな素数で行うと、オーバーフローしない優れたハッシュ関数が得られます。ほとんどの英単語の Unix 単語リストに対して次の Ruby コードをテストしたところ、相互のアナグラムではない単語間にハッシュ衝突は見つかりませんでした。(MAC OS X では、このファイルは /usr/share/dict/words にあります。)

私の word_hash 関数は、各文字の mod 32 の序数値を取ります。これにより、大文字と小文字が同じコードを持つようになります。私が使用する大きな素数は 2^58 - 27 です。2^64 / A 未満であれば、どんな大きな素数でも構いません。ここで、A はアルファベットのサイズです。私はアルファベットのサイズとして 32 を使用しているので、これは約 2^59 - 1 より大きい数値を使用できないことを意味します。Ruby は符号に 1 ビットを使用し、値が数値かオブジェクトかを示すために 2 番目のビットを使用するためです。 、私は他の言語に少し負けています。

def word_hash(w)
  # 32 prime numbers so we can use x.ord % 32. Doing this, 'A' and 'a' get the same hash value, 'B' matches 'b', etc for all the upper and lower cased characters.
  # Punctuation gets assigned values that overlap the letters, but we don't care about that much.
  primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131]
  # Use a large prime number as modulus. It must be small enough so that it will not overflow if multiplied by 32 (2^5). 2^64 / 2^5 equals 2^59, so we go a little lower.
  prime_modulus = (1 << 58) - 27
  h = w.chars.reduce(1) { |memo,letter| memo * primes[letter.ord % 32] % prime_modulus; }
end

words = (IO.readlines "/usr/share/dict/words").map{|word| word.downcase.chomp}.uniq
wordcount = words.size
anagramcount = words.map { |w| w.chars.sort.join }.uniq.count

whash = {}
inverse_hash = {}
words.each do |w|
  h = word_hash(w)
  whash[w] = h
  x = inverse_hash[h]
  if x && x.each_char.sort.join != w.each_char.sort.join
    puts "Collision between #{w} and #{x}"
  else
    inverse_hash[h] = w
  end
end
hashcount = whash.values.uniq.size
puts "Unique words (ignoring capitalization) = #{wordcount}. Unique anagrams = #{anagramcount}. Unique hash values = #{hashcount}."
于 2016-03-30T13:48:27.983 に答える
3

小さな実用的な最適化 、上記のハッシュメソッドについてお勧めするのは次のとおりです。

最小素数を母音に割り当て、次に最も頻繁に発生する子音に割り当てます。例 : e : 2 a : 3 i : 5 o : 7 u : 11 t : 13 など...

また、英語の平均語長は : ~ 6

また、上位 26 の素数は 100 未満です [2,3,5,7, .. , 97]

したがって、平均して、ハッシュは約 100^6 = 10^12 の値を生成します。

したがって、10 ^ 12 より大きいモジュロの素数を使用すると、衝突の可能性が非常に低くなります。

于 2016-10-15T16:51:52.790 に答える
0

配列のバイナリ値表現を使用できます。このコード スニペットは、すべての文字が小文字のラテン文字であることを前提としています。

public int hashCode() {
    //TODO: so that each set of anagram generates same hashCode
    int sLen = s.length();
    int [] ref = new int[26];
    for(int i=0; i< sLen; i++) {
      ref[s.charAt(i) - 'a'] +=1;
    }
    int hashCode = 0;
    for(int i= 0; i < ref.length; i++) {
      hashCode += new Double(Math.pow(2, i)).intValue() * ref[i];
    }
    return hashCode;
  }
于 2021-10-19T20:09:44.193 に答える