---
# System prepended metadata

title: データ構造テスト

---

# データ構造テスト

## String sort
### Key-Index Counying
朝陽のパワポみる

### LSD String sort
桁に優先度を設けてソートを行う。
最上位桁が最も優先順位の高いキー、次いでその下の桁が2番目の優先順位のキー、3番目の桁が……、といった要領である。優先度が低い桁からソートを行なっていく。
長さWのN個の文字列の場合、実行時間はWNに比例 ( W<<Nのとき線形時間 O(N) )
* 例: 170, 45, 75, 90, 2, 24, 802, 66
1. 1の位においてソートを行う
    * 170, 90, 2, 802, 45, 75, 66 
2. 10の位においてソートを行う
    * 2, 802, 24, 45, 66, 170, 75, 90
3. 100の位においてソートを行う
    * 2, 24, 45, 66, 75, 90, 170, 802

### MSD string sort
LSDは最下位の桁からソートを行なったがMSDは上位の桁からソートを行う。
MSD string sortの実行時間はデータによって異なる
* ランダム入力
    * 文字数に対し線形でない
* ランダムでない入力
    * 実行時間はほぼ線形
    * 等しいキーの数によって変更
* 最悪の入力
    * 全ての文字列が等しい場合
    * 文字数に対し線形

### Three-way string quick sort
* ソート済みあるいはそれに近い配列が最悪の入力
* あらかじめ配列をシャッフルすることによる改善
* 分割の基準となる文字列をランダムに選択することによる改善

![](https://i.imgur.com/gxcUzfp.png)
![](https://i.imgur.com/J5kstG4.png)

## Tries
* Trieとは
    * ノードにはR個のリンクを持つ
    * keyにvalueを付与して挿入
    * 1ノードあたり2つの子ノードを持てる

W: 検索する文字列の長さ, N: データ数, R: 文字の種類
* 利点
    * 検索が成功した時の計算量がO(W)で高速(最悪計算量: O(log_n R))
* 欠点
    * メモリを大量に消費 {(8R + 56)N to (8R + 56)NW}
        * 文字列Wに依存
    * アルファベットの数だけリンクを持つため無駄が多い

文字列を検索する場合、ルートから1文字ずつ検索
* 例1: shells => 3
* 例2: shell => Null

![](https://i.imgur.com/qxVn4S3.png)

Trie木へのinsert
* 挿入する場合にTrie木内を検索
    1. ヒットした場合 -> Valueを上書き
        * sea: 2 -> 6
    2. ミスした場合 -> 足りな分のノードとValueを追加 

### TST
* TSTとは
    * ルートを持たない
    * ノードはR個のリンクを持つ
    * keyにvalueを付与して挿入
    * 1ノードあたり3つの子ノードを持てる

W: 検索する文字列の長さ, N: データ数, R: 文字の種類
計算量 : best O(log_R N), worst O(N)
* 利点
    * 1ノードあたり3つの子ノードを持てる
    * Trie木と比べメモリ消費量が抑えられている{64N to 64NW}
* 欠点
    * アルファベットの数だけリンクを持つため無駄が多い

検索
![](https://i.imgur.com/mn6bwqy.png)

TST木へのinsert
* 挿入する前にTST木内を検索した後に挿入



## Substring-search
### Brute-force Substring Search
長さNのテキスト内に含まれる長さMのパターンを探索
1. テキストとパターンを先頭から一文字ずつ比較
    * 一致した場合、お互いの次の文字を比較
    * 不一致の場合、比較するテキストの先頭を一つ進める

計算量:O(N), 最悪計算量:O(NM)
![](https://i.imgur.com/LhxcEai.png)

### Knuth-Morris-Pratt substring search
文字列: AAABAAAAA
パターン: BAAAAA
1. 4文字目まではパターンと一致(BAAA)
2. 出現する文字が{A,B}の場合、BAAABがわかる
3. パターンの先頭文字が次に出現するのはi=4
4. 次の比較をi=4から行なう
![](https://i.imgur.com/jLDw0am.png)

### DFA
KMP searchはDFAで実装可能．(DFAは決定性有限オートマトンを意味する)
* DFAの実装方法
    * 2次元配列 dfa[ charAt(i) ][ j ] で実装
        * 整数 j は現在のオートマトンの状態番号
        * charAt(i) は現在参照している文字
    * 配列要素はオートマトンの状態遷移先
        * 下図の例では，状態0から状態1へ遷移する入力は"A"であるので，
          dfa[A][0] = 1　となる．
![](https://i.imgur.com/13cC96a.png)

### KMP construction
KMPにおけるDFAを真面目にシミュレートしてるだけの章
書くことなし

### Boyer-Moore Substring Search
長さNの文字列(text)中から長さMのパターン(pattern)を探索するアルゴリズム
1. パターンで用いられる文字から辞書(right)を作成 
    * rightはその文字が最も右にある場所のindex (存在しない場合は-1) 
3. パターンの長さ分の部分文字列をテキストのi文字目から取り出し、その文字列を後ろから比較
4. パターンのj文字目が不一致の時点で、iにj - right[ text[i + j] ]を加算
5. 文字が全て一致した時点でその位置のindexを返し探索終了(存在しない場合は-1)

![](https://i.imgur.com/Gb1yXCL.png)

検索対象の文章の長さをN、パターンの文字長をMとすると計算量はO(N/M)、最悪計算量はO(NM)

![](https://i.imgur.com/iIOiXaJ.png)
![](https://i.imgur.com/CwBN905.png)
![](https://i.imgur.com/R0upApl.png)
![](https://i.imgur.com/HQefvCm.png)
![](https://i.imgur.com/hSKdoSS.png)

### Rabin-Karp fingerprint substring search
部分文字列のハッシュ値の比較を用いた検索アルゴリズム
テキストの部分文字列のハッシュ値を計算し、パターンのハッシュ値と一致すれば探索終了。
#### Rolling Hash
文字1文字を値とし、その値と基数の積の総和をハッシュ値とするハッシュ関数を使う。

* x:ハッシュ値, t:部分文字列, R:基数, Q:素数
* 0~M文字目までの部分文字列のハッシュ値
$$x _ { i } = t _ { i } R ^ { M - 1 } + t _ { i + 1 } R ^ { M - 2 } + \ldots + t _ { i + M - 1 } R ^ { 0 } \bmod Q $$
* 1文字ずらした次のハッシュ値
$$x _ { i + 1 } = \left( x _ { i } - t _ { i } R ^ { M - 1 } \right) R + t _ { i + M } $$

* 例: abr
    * a = 1, b = 2, r = 5, 基数:10
$$ abr = 1 \times 10^2 + 2 \times 10^1 + 5 \times 10^0 = 125 $$
    * 文字列:babr
        1. bab
            $$ 2 \times 10^2 + 1 \times 10^1 + 2 \times 10^0 = 212$$
        2. abr
        $$ (212 - 2 \times 10^2) \times 10 + 5 = 125$$

Rolling Hashの場合、ハッシュ値の計算は初期値の計算O(M)
任意の区間の部分文字列のハッシュ値の計算はO(1)
O(N)の計算量で文字列検索が可能