0

現在、AIZU ONLINE JUDEGE ALDS1_4_Cをやっています。
その中で、ダブルハッシュを使用したオープンアドレス法を学んでいます。

以下がオープンアドレス法のコードです。

#include <stdio.h>
#include <string.h>

using namespace std;
using ll =long long;

#define M 1000003
#define L 14

char H[M][L]; /* Hash Table */

int GetChar(char ch){
    if ( ch == 'A') return 1;
    else if ( ch == 'C') return 2;
    else if ( ch == 'G') return 3;
    else if ( ch == 'T') return 4;
    return 0;
}

ll GetKey(char str[]){
    ll sum=0, p=1, i;
    for (i=0; i<strlen(str); i++){
        sum += p*(GetChar(str[i]));
        p *= 5;
    }
    return sum;
}

int Hash1(ll key){ return key % M; }
int Hash2(ll key){ return (1 + (key%(M - 1)); }

int find(char str[]){
    ll key = GetKey(str);
    int k=0;
    while(true){
        int hash_index = (Hash1(key) + k*Hash2(key)) % M;
        if(strcmp(H[hash_index],str) == 0) return 1;
        if(strlen(H[hash_index]) == 0){
            return 0;
        }
        k++;
    }
    return 0;
}

int insert(char str[]){
    ll key = GetKey(str);
    int k=0;
    while(true){
        ll hash_index = (Hash1(key) + k*Hash2(key)) % M;
        if(strcmp(H[hash_index],str) == 0) return 1;
        if(strlen(H[hash_index]) == 0){
            strcpy(H[hash_index], str);
            return 1;
        }
        k++;
    }
    return 0;
}

int main(){
    int i, n;
    char str[L], com[9];
    for (i=0; i<M; i++) H[i][0] = '\0';

    scanf("%d", &n);

    for(i=0; i<n; i++){
        scanf("%s %s", com, str);

        if (com[0]=='i'){
            insert(str);
        }else{
            if(find(str)){
                printf("yes\n");
            }else{
                printf("no\n");
            }
        }
    }

    return 0;
}

この中で、文字を数値に変える関数GetKeyの中でやっていることが分かりません。
具体的には、

sum += p*(GetChar(str[i]));
p *= 5;

このpが存在している意味が分かりません。
似ている文字だったら、この後ハッシュ関数に変えたインデックスの値が近くなるので
それを避けるために、文字列の数によってpを掛けたり、pを1回のループが終わるごとに5を乗算しているでしょうか?
ネット上で、ここで5を乗算しているのは、文字を1から4の数値に置き換えているためというのを見たのですがどういうことか理解できません。

ご教授宜しくお願い致します。

2
  • 質問の ALDS1_4_C というのは AIZU ONLINE JUDEG の onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_C のことですか?
    – raccy
    Commented 2022年10月15日 12:35
  • raccy様 コメントありがとうございます。 はい、そちらの問題です。ご回答ご存知でしたら、ご教授お願い致します。 Commented 2022年10月15日 12:38

1 件の回答 1

1

簡単に言えば、ACGTからなる文字列を[文字無し]=0,A=1,C=2,G=3,T=4とした逆順の5進数とみなして、Keyとしているというものです。入力例に出てくる文字列を5進数(0pXXX)で表現すると次のようになります。

AAA = 0p111 = 31
AAC = 0p211 = 56 # 1文字目が1桁目に相当することに注意
CCC = 0p222 = 62
AGA = 0p131 = 41
AGG = 0p331 = 91
TTT = 0p444 = 124
T   = 0p4   = 4

上の例にあるとおり、1文字目が1桁目なので1を掛けますが、2文字目は5、3文字目は25(5*5)とn文字目には5のn乗を掛けるとなります。p *= 5;というのがその5のn乗のpということです。

なお、この方法では文字列とKeyは1対1に対応しています。コードではKeyはハッシュ値を求める所でしか使用していませんが、Keyをそのままテーブルに入れて利用した方が比較などがより高速になるはずです。また、最大でも、12文字TTTTTTTTTTTT = 0p444444444444 = 244140624なので、long longではなくlongでも十分のはずで、そこらへんも最適化はできそうです。

5
  • raccy様 大変分かりやすいコメントありがとうございます。頂いたコメントでは、入力の1文字目が1桁目になり2文字目が5進数で考えると桁上がりしているため、pに対してn倍の乗算を掛けることで、5進数から10進数に変更していると分かりました。頂いた中で、逆順の5進数とみなすという説明が理解できなかったですが、上記の通りなのでしょうか? またraccyさんが仰る通りに、このハッシュ値をそのままHのキーとして入れていないのは、なぜなのでしょうか?コード上では、insert関数の中で、strcpy関数を呼び出していますが、普通にH[hash_index] = str とすれば良いと思うのですがいかがでしょうか? ご教授宜しくお願い致します。とても簡潔で分かりやすい説明で非常にありがたいです。 Commented 2022年10月16日 11:07
  • 1
    「逆順」と言っているのは、一番左の1文字目が一番右の1桁目二層等すると言うことです。ACGなら0p321と対応する文字と数字が逆の順番になって5進数表記とみなすと言うことです。
    – raccy
    Commented 2022年10月16日 11:10
  • 1
    次に、Keyをそのままテーブルに使わない理由はわかりません。考えられるとしたら、このコードを応用してより大きい文字列を扱う場合にも対応しようとしたのかも知れませんが、詳細はこのコードを書いた人に聞く以外に無いでしょう。(そもそも、問題文のコードはどこから持ってきたのでしょうか?自分で書いたのではないのであれば、引用元を明記するようにしてください。)
    – raccy
    Commented 2022年10月16日 11:14
  • 1
    最後に、strcpyを使っているのは、代入ではヌル終端文字列をハッシュテーブルに入れたことにならないからです。H[hash_index] = strでは文字列がある場所のアドレス値(ポインタ)を入れただけに過ぎず、その値はmain関数のstrになります。mainforループで、関数に渡されるstrつまりポインタは毎回同じであり、ポインタの先にある文字列の値が毎回変わると言うことになるので、その文字列の値そのものをテーブルに記憶するには、strcpyを使う必要があると言うことです。ここら辺は、C/C++におけるヌル終端文字列の操作についてきちんと学ぶと理解できると思います。(C++のstd::stringや他言語の文字列とはかなり異なるので、ちゃんとした入門書をきちんと読まないと、理解は難しいと思います)
    – raccy
    Commented 2022年10月16日 11:25
  • raccyさんコメントありがとうございます。自分でraccyさんに対して、このハッシュ値をそのままHのキーとして入れていない理由をお尋ねしたのですが、このkeyをそのままHのインデックスとして入れた場合には、たまにkey自体が重複する可能性があるので、このダブルハッシュ法でそれを回避していることを思い出しました。strcpyに対してのコメントありがとうございます。cやc++では、文字列は配列として扱われ、その文字列を代入した変数は、その文字列の最初のポインタであることを失念していました。分かりやすい解説と迅速なコメントありがとうございます。 Commented 2022年10月16日 12:27

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。