CedIME 字典

CedIME 裡內建了很多不同的字典

英文 auto-correct 字典 - 821K
倉頡輸入法字典 - 180K
速成輸入法字典 - 66K
筆劃輸入法字典 - 490K
注音輸入法字典 - 47K
中文關聯詞字典 - 386K
倉頡字根查詢字典 - 156K
筆劃字根查詢字典 - 184K

除了英文字典，最佔空間的要算是筆劃輸入法字典了。一直以來筆劃輸入法的字典和倉頡字典的格式都是一樣的，是一個樹狀數據結構。類似下圖：

這裡每個圓圈 (Internal Node) 代表一個字根，例如倉頡的：日、月、金、木等等。從上面開始： A->B->F 可以代表 日 -> 弓 -> 木 = 閑，如此類推。筆劃輸入也是一樣的道理，只是字根變成 (一丨丿丶フ)。

這個樹狀的結構在使用時非常有效率，例如當你輸入"日"倉頡字根，CedIME就可以把"日"這個 Internal Node 以下所有可能的字都找出來，因此你很多時不必整段倉頡字根輸入完已經能夠從選字表中找到要輸入的文字。

然而筆劃字根和倉頡字根的差異非常大：
- 倉頡輸入法字根長度最長只是 5 ，而筆劃字根最長可以去到 48
- 倉頡輸入法盡用 26 個字母作為字根，筆劃基本字根只有五個 (一丨丿丶フ)

因此相對於倉頡輸入法來說，筆劃輸入法的樹結構相對較長而且窄，並且有很多無用的 Internal Node。當理解這點以後，改善辦法自然就是要從樹的結構入手，盡量把浪費的 Internal Node 省略掉。

而我在 CedIME 裡處理這個問題的方法就是用一種叫 Radix Tree (Patricia tries) 的數據結構。它也是樹結構的一種，特點是所有 Internal Node 都必然會有兩個或以上的 Child。如下圖：

這種結構對於筆劃字根來說很適合，它能把幾個無用而連續的 Internal Node 合併為一個 Node ，這大大省略了整棵樹佔用的空間。轉用了這個新的結構後筆劃輸入法的字典由本來的 490K 大幅減少至 238K，加上 Android APK本身的壓縮功能，實際上在手機中只佔大約 130K左右。另外由於使用時字典必須載入到手機的記憶體中，因此在 CedIME 運行時也節省了相當的記憶體。