2017q3 Homework2 (prefix-search)

contributed by < vasv75182366 >

tags: sysprog2017

動作太慢了，趕快跟上
"jserv"

簡介

在字串的集合內要收尋字串時，除了本次作業提到的 Ternary search tree(TST)，可以使用 Hash Table 、 Binary search tree(BST) 或者是 Trie tree 。

• Hash Table 隨著資料數量的大小需要調整 Hash Table size ，若是調整 Hash Table size 則整個表需要重建不利增長和收縮，並且根據 Hash function 的選擇和資料的不同 Hash collisions 的機會也會增加。
• BST (binary search tree) 雖然較穩定但效能太差。
• Trie tree 雖然查詢速度較快但是需要的空間較大，以英文字母查詢來說每個節點需要有26個節點指標，若是考慮中文甚至多國語言則不切實際。

本次作業的 TST 結合 Trie 以及 BST 的優點用較少的儲存空間達到快速查詢。

學習 Ternary search tree

Ternary search tree

每個 Node 包含：

• 三個 Node 指標
• 一個字元
• 一個 Value

其中三個 Node 指標分別指向三個子樹：

• low (left)
• equal (middle)
• high (right)

typedef struct tst_node {
    char key;               /* char key for node (null for node with string) */
    unsigned refcnt;        /* refcnt tracks occurrence of word (for delete) */
    struct tst_node *lokid; /* ternary low child pointer */
    struct tst_node *eqkid; /* ternary equal child pointer */
    struct tst_node *hikid; /* ternary high child pointer */
} tst_node;

閱讀程式碼

---

修改程式碼

Reference

• Igor Ostrovsky Blogging