東京大学 情報理工学系研究科 電子情報学専攻 2016年8月実施 専門 第3問

标签：

• Tokyo-University
• Boyer-Moore-Majority-Vote-Algorithm

Author

adj-matrix, 祭音Myyura

Description

ある Web サービスに対し、異常に高頻度でアクセスするユーザをアクセスログから見つけたい。各ユーザには一意なユーザ ID が割り当てられており、アクセスログにはアクセスしたユーザの ID が時系列順で記録されている。このとき、以下の問いに答えよ。

(1) アクセスログにおいて、全体の過半数のアクセスを行っているユーザがいるかどうかを、全ユーザに対する頻度ヒストグラム等を生成することなく検証したい。そこで、以下のようなアルゴリズムを考えた。

• i. 空リスト $\{\}$ で初期化されたリスト $L$ を用意する。
• ii. 配列 $A$ の要素に先頭からアクセスし、$i$ 番目の要素 $A[i]$ について、そのときの $L$ の値に応じて以下のいずれかの処理を行う。
  • ii-(a). $L$ が空である場合、$A[i]$ を $L$ に追加する。
  • ii-(b). $L$ が空でない場合、$A[i]$ が $L$ に含まれていれば $L$ に追加し、含まれていなければ $L$ から任意の要素を1つ取り除く。
• iii. $L$ を出力する。

このアルゴリズムを用いて以下のユーザ ID の系列を先頭の要素から処理し、ii で各要素を処理した後のリスト $L$ の値を順に示せ。

$11,10,11,11,7,11,11,3,8$

(2) (1) のアルゴリズムにおいて、$L$ に含まれる要素の種類数は高々一つであることを証明せよ。

(3) アクセスログにおいて過半数を占めるユーザ $u_{\mathrm{MAJORITY}}$ が存在するとき、$u_{\mathrm{MAJORITY}}$ は (1) のアルゴリズムが出力するリスト $L$ に含まれる唯一のユーザであることを証明せよ。

(4) (1) のアルゴリズムでは、配列 $A$ のサイズが非常に大きい場合にリスト $L$ のサイズが問題となる場合がある。この点に注意し、$L$ をリストとして陽に表現しないことで空間効率を改善した上で、アクセスログからユーザ ID を1つずつ順に読み込む関数 read_log() を用いて (1) のアルゴリズムを擬似コードで示せ。

なお、read_log() は最初に呼び出されるとアクセスログの先頭のユーザ ID を返し、以降、呼び出すたびに続くユーザ ID を返す。また、アクセスログの末尾に到達すると $-1$ を返すものとする。

题目描述

希望从 Web 服务的访问日志中找出访问次数极多的用户。每位用户有唯一 ID，日志按时间顺序记录每次访问者的 ID。回答下列问题。

(1) 为判断日志中是否存在占全部访问次数过半的用户，同时不为所有用户建立频数直方图，考虑以下算法：

1. 准备列表 $L$，初始为空列表 $\{\}$。
2. 从头依次访问数组 $A$ 的元素。处理第 $i$ 个元素 $A[i]$ 时：
   • 若 $L$ 为空，将 $A[i]$ 加入 $L$；
   • 若 $L$ 非空且 $A[i]$ 已包含在 $L$ 中，再加入一个 $A[i]$；否则从 $L$ 中任意删除一个元素。
3. 输出 $L$。

按顺序用该算法处理用户 ID 序列

$$11,10,11,11,7,11,11,3,8,$$

依次写出步骤 2 每次处理 $A[i]$ 后 $L$ 的值。

(2) 证明在 (1) 的算法中，$L$ 所含用户 ID 的种类数至多为 $1$。

(3) 若日志中确实存在多数用户 $u_{\mathrm{MAJORITY}}$，证明它是 (1) 的算法最终输出列表 $L$ 中唯一种类的元素。

(4) 当数组 $A$ 很大时，显式保存列表 $L$ 会造成空间问题。使用每次从日志读取一个用户 ID 的函数 read_log()，写出不显式表示 $L$、空间效率更高但实现同一算法的伪代码。read_log() 第一次调用返回日志中的第一个用户 ID，随后逐次返回后续 ID，到达日志末尾时返回 $-1$。

Kai

(1)

処理した ID	処理後の $L$
11	$\{11\}$
10	$\{\}$
11	$\{11\}$
11	$\{11,11\}$
7	$\{11\}$
11	$\{11,11\}$
11	$\{11,11,11\}$
3	$\{11,11\}$
8	$\{11\}$

(2)

帰納法で示す。初期状態では $L$ は空である。処理前の $L$ が空なら1要素を追加するので種類数は1となる。空でなければ、その唯一の種類と同じ ID を追加するか、既存要素を1つ削除するだけなので、種類数は高々1に保たれる。

(3)

削除操作は、異なる ID の2要素（入力要素と $L$ 内の要素）を組にして除く操作とみなせる。過半数ユーザを $u$ とすると、$u$ の出現数は他の全ユーザの出現数の和より多い。従って、異なる ID を何組取り除いても $u$ は少なくとも1個残る。(2) より最終的な $L$ の種類は高々1なので、その唯一の種類は $u$ である。

(4)

$L$ を「候補 ID とその個数」で表す。

FindCandidate():
    candidate = NONE
    count = 0
    while true:
        id = read_log()
        if id == -1:
            break
        if count == 0:
            candidate = id
            count = 1
        else if id == candidate:
            count = count + 1
        else:
            count = count - 1
    if count == 0:
        return (NONE, 0)
    return (candidate, count)

この組は元の出力リストを圧縮して表し、追加空間は $O(1)$、時間はログ長に対して $O(N)$ である。過半数ユーザの存在そのものを判定するには、候補の実際の出現数を再走査で数え、$N/2$ を超えることを確認する。