2018年 解答
テスト対策と言うことで2018年の過去問（講義（Web: link）に載っている）を解いたので、その解答をまとめました。
問題1
1
- i - left
- right - i
- i-1
- left=i+1
- i+1
- right=i-1
最終的なプログラムは以下のようになる。
void randomQuickSort3(int* target, int aLeft, int aRight) {
int left = aLeft; int right = aRight;
while (left < right) {
int i = partition(target, left, right);
if( i - left <= right - i ){ // The left interval is shorter.
randomQuickSort3(target, left, i-1);
left=i+1;
}else{ // The right interval is shorter.
randomQuickSort3(target, i+1, right);
right=i-1;
}
}
}この時、入力配列 target の長さが2^40のように長い配列でも stack overflow を起こさず動作する理由は、「短い部分列を先に処理することで深さを \(\log_2n\) 以下に抑えているから。」です。
関数呼出しの際には、パラメータや命令のアドレス、局所変数などをスタックに積み(push)、関数の実行が終わると取り出されます(pop)。
したがって、関数の中で関数を並列に呼ぶ分には問題はないのですが、直列に（こんな表現は多分正しくないです笑）呼ぶとその度にスタックに積まなくてはならず、メモリ領域が足りなくなり、stack overflowを起こしてしまいます。
ゆえに、再帰の深さを \(\log_2n\) 以下に抑えている上記のプログラムはstack overflowを起こしにくいのです。
2
下からk番目の要素の場合、以下のようになる。（いわゆるQuick select）k番目が含まれている配列のみをソート(partition)していく。
int select(int* target, int aLeft, int aRight, int k) {
int left = aLeft; int right = aRight;
if(left < right) {
int i = partition(target, left, right);
if(i == k){
return target[k];
else if( i < k ){
return select(target, i+1, right, k);
}else{ // i > k
return select(target, left, i-1, k);
}
}
}3
k番目の要素を選択する平均計算量を \(T(n,k)\) と表記し、最悪の場合でも上界が \(O(n)\) であることを示す。
まず、k番目の要素を選択する平均計算量を \(C(n)\) と表す。partition の結果 \(i\) 個と \(n-i\) 個の要素に分かれる確率を \(P(i,n)\) とすると、\(C(n)\) は \(i\) が \(1\sim n-1\) を動いた場合の期待値と考えられるので、
で与えられる。ここで、\(P(i,n)\) は pivot がちょうど \(i+1\) 番目の要素である確率であり、与えられた列の先頭2つに \(i\) 以下の要素とちょうど \(i+1\) 番目の要素が位置している確率であるので、\(2i/n(n-1)\) となる。これを代入して整理すると、
となる。この \(C(n)\) の計算量を示す方法として、解を仮定してその正しさを帰納法で示す方法をとる。まず、\(C(n)\leq an\) を仮定する。 \(n=2\) の時は、\(C(n) = 2c + C(1)\) であるので、\(a=c+C(1)\) とすれば成立する。 \(n=1,\ldots,k-1\) の時に成立したとして、\(n=k\) で成立することを示す。
したがって、\(a>c\) とすれば、\(C(k)\leq ak\) が示せたことになる。 以上により、\(a > c+C(1)\) とすれば、全ての \(n\) で \(C(k)\leq ak\) が示せたことになり、クイックセレクトの平均計算量が \(O(n)\) になることが示せた。
問題2
1
| 項目 | 定義 |
|---|---|
| suffix array SA | Sの全てのsuffixを辞書式順序でソートした時に、i番目(0<=i<n)にランクされたsuffixS[k,n)の開始位置kを、SA[i]=kと記録する。（開始位置kだけ記録すればSからsuffixの文字列は得られるので問題ない。） |
| inverse suffix array ISA | "SA[i]=k"ならば"ISA[k]=i"と記録したもの。suffix S[k,n)が何番目かを調べるための補助的データ構造。 |
| h-順序 | 最初のh文字だけでソートしたsuffixの順序 |
| 近似 suffix array | 最初のh文字だけで作成したsuffix array |
| 近似 inverse suffix array | 最初のh文字だけで作成したinverse suffix array |
2
基本的なアイデアは、「h文字目までの順番が確定している時、その順番を利用すればh+h=2h文字目までの順番も分かる」ということ。詳しくはここで図を用いて解説した。
3
データの順序を交換する過程を、h文字目までが同じものを１つのノードとした木構造で表現する。ここで、pivotの値を持つnodeを"pivot node(=pivot)"、それ以外を"non-pivot node(> or < pivot)"と呼ぶ。
ここで、各反復時には全ての要素を見るので、O(nlog(最大反復長))の時間がかかる。（すでにソートされている部分はスキップするので、次第に小さくなるが）
この時、pivotに中央値を選べば"non-pivot node"のデータ数は親ノードの半分未満となる。したがって、木の根から各葉へのパス上に"pivot node", "non-pivot node"はlog_2n+1以下となる。各ノードで中央値を線形時間で計算でき、その中央値をpivotとして分割するのも線形時間なので、各列の最悪計算量はO(n) ゆえに、最悪計算量はO(nlogn)
4
doubling法を実装した場合、suffixの最初のh文字だけをソートすることを繰り返す。
例えばAだけからなる長さnの記号列を入力として与えたことを考える。この時、同じ値をまとめるTernary-split quick sortを使わず、最悪時間計算量O(nlogn)のマージソートなどを使うと、h=1,2,4,...に対して毎回O(nlogn)かかるため、総計算量がO(n(logn)^2)になってしまう。 一方で、Ternary-split quick sortを使えば、この状況を回避できる。
問題3
Suffix Array に関しては、DoublingやSA-ISに関してアルゴリズムの課題時にまとめたので、省略。
問題4
1
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| BWT[i] | A | A | A | A | A | C | $ | A | A | A | A | A |
2
- suffix arrayの先頭文字の直前の文字を列にしたのがBWT
- T[i]は、SA[i]-1番目（つまり、BWT[i]）の文字のsuffixのランキングを表している。
- BWTの順番もsuffix arrayの順番と対応しているので、BWT[T[i]]には、BWT[i]のSでの直前の文字が書いてある。
- 最後の文字は"$"であり必要ないので、その１つ前の文字（つまりS[n-2]であり、BWT[0]）から直前の文字を再帰的に復元できる。
以上より、以下の式でSを復元できる。
3
BWT[i]はS[SA[i]-1]を記録しており、元の文字列よりも連続した値が続きやすいという性質を持つ。すると、ランレングス圧縮などをかけて文字列を圧縮しやすくなるから。
4
T[i]もBWT[i]も、iはsuffix arrayの順にソートされている。ここで、T[i]はBWT[i]の文字のsuffixのランキングを表しているので、その値はBWT[i]の文字情報だけで何番目なのか(累積和をとる, C[x])にBWT[i]の文字内で何番目なのか(Occ(x,i))を足せば良い(0-origin indexingなので-1する)
5
- xから始まるxWより小さいprefixの数を考えれば良い。SAでWは順番に並んでおり、prefixはBWT中でlb(W)-1の位置以下にある。その数は、Occ(x, lb(W)-1)個。
- xから始まるxW以下のprefixはBWT中でub(W)の位置以下にある。その数はOcc(x,ub(W))個。0-origin indexingなので最後に-1する。