---
# System prepended metadata

title: Lecture 5

---

# Lecture 5

## Reference

[Lec05 資料結構 第三週課程](https://youtu.be/cgaPEsMJkSc)

## Notes

### Sparse Matrix (00:10)

- 左邊是一個sparse matrix，因為大部分的值是0，所以可以用其他資料結構來存

![](https://hackmd.io/_uploads/ryzdj0VSn.png)

- 將sparse matrix中的值及所在的行列依照<row, col, value>的格式記下來
- 注意行列有排序

![](https://hackmd.io/_uploads/BJn_iAEH2.png)

- Transpose (轉置):
    - 方法一：直接把row/col交換，交換完再調整這個值所在的位置，例如下方轉置完的(1, 1, 11)應該要往上移
    
    ![](https://hackmd.io/_uploads/r1aTs0NS3.png)
    
    - 程式碼實現：
        - 前三行：將行列最大值交換、值的個數不變
        - 最外面的if：如果矩陣有元素的話，執行裡面的兩個for迴圈
        - 外面的for迴圈是依照原本的Cols去排序，因為轉置之後新的row就變成col了
        - 裡面的for迴圈會檢查原本的矩陣中所有terms的col，如果是c的話，就把元素擺進去，然後CurrentB++，找轉置後的矩陣中，下一個位置要擺的term
        - Time Complexity: $O(terms*cols)$
    
    ![](https://hackmd.io/_uploads/Sk8RiAEBh.png)
    
    - 方法一的問題是對於不同的cols，都要檢查一遍所有的terms有沒有符合
    - 方法二：多利用一組資料，資料會記載原本的matrix中，每個不同的row出現的次數，還有這個row出現的起始位置，index就是row的值
    
    ![](https://hackmd.io/_uploads/ryoAs04S2.png)
    
    - 程式碼實現：
        - if判斷式之前的程式與方法一大同小異，只是多了Rows跟RowStart
        - if判斷式判斷matrix不是空的
        - 剩下三個for迴圈在計算RowSize跟RowStart
    
    ![](https://hackmd.io/_uploads/HJ_1hREH2.png)
    
    - 程式碼實現 (cont.)：
        - for迴圈對於每個Terms做轉置
        - int j 代表的是現在這個term應該要丟到的新矩陣的對應位置
        - 接下來三行就是把單個term的行列互換、值直接丟過去新的矩陣
        - RowStart要++這樣才不會丟到同一個位置
    - 綜合上述，時間複雜度大約是$O(row*column)$
    
    ![](https://hackmd.io/_uploads/H1jk204S2.png)

### Matrix Multiplication (29:12)

$$
result_{ij} = \sum_{k=0}^{n-1}a_{ik}b_{kj}
$$

### Arrays in Memory (30:09)

- Row Major : 記憶體會先把一整列的值放完，再放下一列
- 延伸成多維矩陣，記憶體會以最高維度的資料作為擺放方式

![](https://hackmd.io/_uploads/S1Gx2RVrh.png)

### String (33:21)

- 可以當作字元陣列 (character array)
- 常見的字串處理包含：字串比對、串接、複製、插入等

### String Matching (36:36)

- P : Pattern; T : Text; m : Length of P; n : Length of T
- 目標找出P出現在T中的起始位置
- 最簡單的方式就是從T的第一個位置開始慢慢比對，如果比錯了就把pattern位移一個字元，然後再比對一次

![](https://hackmd.io/_uploads/B1Txn0NHn.png)

### KMP Method (52:55)

- 主要精神：比錯的時候，可不可以一次位移多個字元
- 例子：
    - 比對到第四個位置時，Pattern直接位移三格

![](https://hackmd.io/_uploads/By1b3RNSh.png)

- 例子：
    - 第七個位置不一樣，把P的粉紅色區塊跟T的粉紅色對齊，這時候移了五格
    - 接下來比對T的第七個位置及P的第二個位置

![](https://hackmd.io/_uploads/ryfb2CErh.png)

- 例子：
    - 同樣比到不一樣的位置時，根據粉紅色的區塊位移

![](https://hackmd.io/_uploads/SJ4b3C4S3.png)

- KMP Algorithm
    - 如果比對到不相同時，根據Failure function決定要移多少格
    - 粉紅色區塊代表這兩段的字串長得一樣，Failure function是在算粉紅色區塊的最大長度k
    - 兩段粉紅色區塊有overlap沒關係

![](https://hackmd.io/_uploads/SyDZhAErn.png)

- 計算Failure function的例子(注意這裡index是從1開始算)：
    1. 第一個位置沒得比較，Failure function[1]為0
    2. 第二個位置p[2]=’b’，Failure function[2]為0
    3. 第三個位置p[3]=’a’，Failure function[3]為1，因為p[3]==p[1]
    4. 第四個位置p[4]=’b’，Failure function[4]為2，因為[p[3], p[4]]==[p[1], p[2]]，也就是’ab’
    5. 其他同理

![](https://hackmd.io/_uploads/BJFZnAVH2.png)

![](https://hackmd.io/_uploads/HJ3W30EH3.png)

- 如果S[i]跟P[j]不一樣，下次就比對S[i]跟P[f(j-1)+1]，等同於前面所講的位移

![](https://hackmd.io/_uploads/rJ0Z3C4H2.png)

- 更多例子：
1. 一開始比對S[1]與P[1]，不一樣，所以位移一格
2. 比對S[2]與P[1]，一樣

![](https://hackmd.io/_uploads/r1WMnA4Hh.png)

1. 比對S[3]與P[2]，不一樣，看P[2-1]的Failure function為0，因此比對S[3]與P[1]，還是不一樣，因此位移一格，總共位移兩格
2. 比對S[4]與P[1]，不一樣，位移一格
3. 比對S[5]與P[1]，一樣

![](https://hackmd.io/_uploads/ryEz20ESn.png)

1. 比對S[6]與P[2]，一樣
2. 比對S[7]與P[3]，一樣
3. 比對S[8]與P[4]，一樣

![](https://hackmd.io/_uploads/S1rz304Hn.png)

1. 比對S[9]與P[5]，還是一樣
2. 比對S[10]與P[6]，不一樣了，看P[6-1]的Failure function為3，因此比對S[10]與P[4]，現在一樣了
3. 繼續比對S[11]與P[5]，一樣

![](https://hackmd.io/_uploads/B1dznCVr2.png)

1. 比對S[12]與P[6]，一樣
2. 比對S[13]與P[7]，一樣，P完全一樣，程式結束

![](https://hackmd.io/_uploads/SJYz3CNB2.png)

- Time complexity : $O(m+n)$
    - $m:$ P的長度，計算Failure function
    - $n:$ S的長度