Skiena による「Algorithm Design Manual」の本では、次の段落が 80 ページの見出し3.7 ハッシュと文字列の下にあります。
与えられた文字列 S が書かれているアルファベットのサイズを α とします。char(c) を、アルファベットの各記号を 0 から α − 1 までの一意の整数にマップする関数とします。
上記の段落の「アルファベットのサイズ」は何を意味していますか? すべてのアルファベット (az) は同じサイズではありませんか? また、アルファベットαに文字列Sをどのように書くことができますか. アルファベットを組み合わせて文字列を形成していませんか?
その使用例が見つかるまで、そのハッシュ関数を理解するのに苦労していました。Skiena が説明しているのは、Wikipediaで説明されている Rabin-Karp 文字列検索アルゴリズムの変形です。
使用されるハッシュ関数は次のとおりです。
与えられた文字列が書かれ
αているアルファベットのサイズとしましょう。Sアルファベットの各記号を から までの一意の整数char(c)にマップする関数を とし0ますα − 1。
アルファベットの大きさ α は、文字列 S を表すために使用できる記号の数です。
上にリンクされたウィキペディアのページから：
Rabin フィンガープリントは、すべての部分文字列を基数の数値として扱います。基数は通常、大きな素数です。たとえば、部分文字列が
"hi"でベースが101の場合、ハッシュ値は次のようになります。
104 * 101^1 + 105 * 101^0 = 10609 // (ASCII of 'h' is 104 and of 'i' is 105).
Skiena は、関数をアルファベットの記号から からまでchar()の整数へのマッピングとして定義していることに注意してください。ウィキペディアの例では、数字コードは実際にはアルファベットのサイズよりも大きくなる可能性があります。方式。0α − 1
「アルファベット」が何を意味するのか混乱しているかもしれません。アルファベットは単一の記号ではなく、文字列に現れる可能性のあるすべての記号のセットです。英語のアルファベットには 26 個の記号があります。ヘブライ語のアルファベットには 22 個の記号があります (英語のアルファベットとは異なる記号です)。