跳到主要内容

お茶の水女子大学 人間文化創成科学研究科 理学専攻 情報科学コース 2016年8月実施 情報基礎 問題2

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

文字列を格納した変数 word が与えられた時に、それを引数として 0 から N−1N-1 までのいずれかの整数を返す関数 calcKey(word) があるとする。ただし異なる文字列に対して関数 calcKey が同じ整数を返す場合もあるとする。そしてこの関数の返り値 key が ii であったとき、2 次元配列 data[key][num[key]] に word を格納することを考える。ただしこの配列 data に同一な文字列は重複して格納されないものとする。また、関数 calcKey(word) が値 key を返すような文字列がいままでに mm 種類出現しているとき、num[key] には整数 mm が代入されているものとする。

図 1 はこの仕組みを図解したものである。新しい文字列 word が与えられ、関数 calcKey(word) の値が ii であるとき、data[i][num[i]] に word を代入している。

key                 data
 0   -> data[0][0], data[0][1], ...
 1   -> data[1][0], data[1][1], ...
 ...
 i   -> data[i][0], ..., data[i][num[i]-1], data[i][num[i]] <- word
 ...
N-1  -> data[N-1][0], data[N-1][1], ...

図1 文字列の集合を1個ずつ格納する仕組み

このような仕組みがあるとき、以下の各問に答えよ。

(1)​

この仕組みのように、関数の返り値に基づいてデータ要素の集合（本問題の場合には文字列の集合）を分散させて格納する手法をなんというか答えよ。

(2)​

この例では 2 次元配列を用いているが、メモリ使用量を効率化するためには配列の代わりになんというデータ構造を用いるのが望ましいか答えよ。

(3)​

この方法においてデータ要素の格納と検索の効率悪化を防ぐためには、関数 calcKey はどのような性質を有することが望ましいか説明せよ。

(4)​

この方法においてデータ要素の格納と検索の計算量を定数に近づける方法として、どのような工夫が考えられるか説明せよ。

(5)​

新しい文字列を格納した変数 word が与えられた時、この文字列を配列 data 中の適切な要素に格納する処理を開発したい。図 2 に示したプログラムを完成させよ。ただし以下の点に注意せよ。

  • このプログラムは C 言語で書かれているが、文法上の細かい規約との整合性は問わない。また、表示される文書の改行の位置やインデント（字下げ）の有無は問わない。
  • 2 つの文字列 a, b が同一であるかを判定する一方法として、関数 strcmp(a,b) の返り値が 0 であれば同一、さもなければ同一でない、という判定方法がある。
void register(char* word) {
    int key = calcKey(word);
    // ここから下を埋める。具体的には、
    // 既にwordと同一な文字列がdataに
    // 格納されているかを確認し、
    // まだ格納されていなければ
    // 新たにwordを格納する。

}

図 2　1 個の文字列を格納する関数 register のプログラム

题目描述​

给定函数 calcKey(word)，它把字符串映射为 0,1,…,N−10,1,\ldots,N-1 中的整数；不同字符串可能取得同一个值。键值为 ii 的字符串保存在 data[i] 中，num[i] 表示该处当前已有的不同字符串数，同一个字符串不得重复保存。

  1. 写出这种按函数返回值分散保存数据的方法名称。
  2. 为节省二维数组中的空闲空间，写出适合替代每行数组的数据结构。
  3. 说明 calcKey 应满足怎样的性质，才能防止插入和查找效率恶化。
  4. 说明如何使插入与查找的计算量接近常数。
  5. 补全 register：先检查同一字符串是否已经存在，若不存在则将其登记到正确位置。

Kai​

(1)​

この手法を

ハッシュ法（hashing）\boxed{\text{ハッシュ法（hashing）}}

という。calcKey はハッシュ関数、返り値はハッシュ値に相当する。

(2)​

各 key に対して必要な要素だけを保持できる

連結リスト\boxed{\text{連結リスト}}

を用いるのが望ましい。この衝突処理法を分離連鎖法という。

(3)​

calcKey は、入力される文字列を 0,1,…,N−10,1,\ldots,N-1 にできるだけ一様に分散させることが望ましい。特定の値に文字列が集中すると、その場所の要素を順に調べる時間が長くなる。また、ハッシュ値自体も短時間で計算できることが望ましい。

(4)​

格納する異なる文字列数を MM とし、負荷率を

α=MN\alpha=\frac{M}{N}

とする。十分大きい NN と一様な calcKey を用い、MM の増加に応じて表を拡張して再ハッシュすることで、α\alpha を一定以下に保つ。このとき各 key に属する要素数の期待値が一定に抑えられ、文字列長を一定とみなせば、検索は期待計算量 O(1)O(1)、格納は再ハッシュを含めて期待償却計算量 O(1)O(1) となる。文字列長を LL として数える場合、ハッシュ計算や文字列比較には一般に O(L)O(L) の時間が必要である。

(5)​

void register(char* word) {
    int key = calcKey(word);
    int i;

    for (i = 0; i < num[key]; i++) {
        if (strcmp(data[key][i], word) == 0) {
            return;
        }
    }

    data[key][num[key]] = word;
    num[key]++;
}

既存の num[key] 個を調べ、一致すれば何もせず終了する。一致しなければ添字 num[key] の位置に追加し、要素数を 1 増やす。

本页目录