# 2020q3 Homework3 (dict)
contributed by < `jeremy3951` >

###### tags: `(2020q3)進階電腦系統理論與實作`

## 題目 1 :
* **在 GitHub 上 fork dict，視覺化 ternary search tree + bloom filter 的效能表現並分析。注意，需要設計實驗，允許不同的字串輸入並探討 TST 回應的統計分佈**

對題意的理解 : 把老師的實驗自己做一遍
[情境 1: 搜尋字串全部在字典內](https://hackmd.io/nnYME5GkRS2JEfY1WD28FA?view#%E6%83%85%E5%A2%83-1-%E6%90%9C%E5%B0%8B%E5%AD%97%E4%B8%B2%E5%85%A8%E9%83%A8%E5%9C%A8%E5%AD%97%E5%85%B8%E5%85%A7)
[情境 2：搜尋字串在第一個字元即可判斷不在字典內](https://hackmd.io/nnYME5GkRS2JEfY1WD28FA?view#%E6%83%85%E5%A2%83-2%EF%BC%9A-%E6%90%9C%E5%B0%8B%E5%AD%97%E4%B8%B2%E5%9C%A8%E7%AC%AC%E4%B8%80%E5%80%8B%E5%AD%97%E5%85%83%E5%8D%B3%E5%8F%AF%E5%88%A4%E6%96%B7%E4%B8%8D%E5%9C%A8%E5%AD%97%E5%85%B8%E5%85%A7)
[情境 3: 搜尋到最後一個字元才發現字串不在字典內](https://hackmd.io/nnYME5GkRS2JEfY1WD28FA?view#%E6%83%85%E5%A2%83-3-%E6%90%9C%E5%B0%8B%E5%88%B0%E6%9C%80%E5%BE%8C%E4%B8%80%E5%80%8B%E5%AD%97%E5%85%83%E6%89%8D%E7%99%BC%E7%8F%BE%E5%AD%97%E4%B8%B2%E4%B8%8D%E5%9C%A8%E5%AD%97%E5%85%B8%E5%85%A7)

情境 1 做的事 ：
1. 把程式碼中 find 的功能獨立出來
2. 把 find 中的 bloom filter 功能拿掉
3. 把輸入改成 cities.txt 中的所有城市
4. 把結果畫成圖



把 test_common.c 裡面建立 tst 的部份提出來 , 再把 find 裡面的程式提出來 (bloom filter的部份去掉)


上圖是 test_common.c 中的部份程式碼 , 用意為把 cities.txt 中的資訊加入 tst 中(並且去掉標點符號)
註解的地方就是從 find 中提出來的 tst_search .


上圖為 search 分別用 CPY 和 REF 制度所產生的圖

做完 search 的圖之後再來就是加入 bloom filter 了

把 find 中的 bloom filter 加回來 :


被註解的地方就是原本 find 中的 blomm filter