部件檢索辭典

對 "漢字構形檢索" 實作原理沒有興趣的朋友，請直接跳至最後的結論處下載 "部件檢索.mdx"(789 KB)，幫忙進行使用測試。對演算法原理有興趣的朋友，從 "漢字的拆分" 一節開始，是我近日來研究 "漢字構形檢索" 的心得筆記，我儘量用淺顯的說明來表達，希望能有所助益(當初研究時，幾乎找不到什麼資料可以參考，希望能為此補上一小塊)。對程式設計也有興趣的朋友，除了原理的說明外，亦附上我自己撰寫的幾個範例程式，可供參照、測試之用，希望對演算法的理解有其輔助的效果(我其實沒學過 Javascript，又為遷就 MDict 使用的 IE7 內核，邊查邊寫，不周之處尚請包涵)。

序曲
閱讀詩經時，常遇到一些生僻的古字；整理離線辭典時，也常需要把一些圖片字、構字式還原成 Unicode 字。我沒學過倉頡一類的輸入法，只能用自己製作的 "部首索引.mdx" 來檢字(可檢索七萬五千多漢字，包含 Unicode 的 Ext-A, B, C, D)，對我而言已經很好用，但遇到完全猜不出部首或很難算出正確筆畫的字就還是很麻煩。

也曾整理製作過注音索引(只有三萬餘字)、拼音索引(只有三萬餘字)、四角號碼索引(只有兩萬七千多字)等一類的檢索字典，但遇上這些冷僻的怪字根本就涵蓋不了，所以輸入這些生僻字一直是個惱人的問題。

後來找到了一個對岸朋友所寫的辭典工具程式漢文博士，它內建了一個 "漢字構形檢索" 功能(利用中研院所發展出來的漢字構形資料庫技術，可以用部件組合來檢索漢字)，這才算是方便了一些。

但我還是不怎麼喜歡用 "漢文博士"。一是它的使用介面完全是簡體的，讓人不太習慣；一是它應該是用 .NET 開發環境所寫，執行時的啟動速度有點慢(我喜歡立即彈現的那種感覺)。當我日常實際要進行查詢時，必須先執行 "漢文博士"，等它啟動，點選 "漢字構形檢索"，輸入部件組合，找到目標字，點選複製，然後貼到 MDict 裡才能真正開始查詢字典，實在是有點不方便。

阿文兄也幾次向我探詢製作 MDict 部件查詢辭典的可能性，但我總認為 MDict 辭典都是以靜態聯結來相互索引，對於部件查詢這種需要動態生成查詢結果的索引方式，沒寫個應用程式是做不到的。於是這個構想也就被這麼擱置了下來。

就在今年二月初，偶然之間找到了一份 "剎那字引" 的離線版(2012.10.3版)，這才又勾起了我的興趣。我想既然用 HTML 加上 Javascript 就能夠做出這樣的部件查詢功能，MDict 辭典本就是基於 IE 核心來運作，如此一來，製作一個具有部件查詢功能的 MDict 辭典似乎並非是不可能的事。

我沒學過 Javascript 對它並不熟悉，加上剎那字引離線版的核心程式似乎是經過一些特殊處理，實在讀不出它的實際演算法到底是如何設計的。但是我並沒有死心，於是開始對漢字構形的演算邏輯認真的研究了起來。

我到剎那工坊看了一下它的 Javascript lesson，lesson 3、lesson 4 涵蓋到了一點部件處理的基礎，我大概參考了一下它的基本概念(呵呵！我承認我是跳著看的，我喜歡讀文件，偏偏它只有影音教學)，自己再加以延伸、驗證、融會貫通，終於把漢字構形的演算法原理、實作邏輯給弄清楚了。我把我的心得用比較淺顯的方式記在這裡備忘，也提供給有興趣的朋友參考(中研院的漢字部件檢字系統原始碼與剎那字引的原始碼實在是不容易讀懂)。

漢字的拆分
一個漢字的結構常可以分解成幾個更小的單元，稱為部件。例如：「盟」字，我們可以把它分解成「明、皿」，或是更進一步拆解成「日、月、皿」。每個部件就是該字的一個 "特徵"，利用適當的演算法，我們便可以用描述特徵的方式來檢索漢字。所以要實做這種檢字方式，首先就是要建立一個漢字的拆分對照表。

最小拆分與完全拆分
以上面「盟」字的例子，我們可以拆分成「明、皿」或是拆成「日、月、皿」，前者我們可以稱之為「最小拆分」；後者可以稱之為「最大拆分」或是「完全拆分」。「最小拆分」顧名思義是將漢字做最少的分解，讓它可以保留較多的可能特徵(「明」字因為可以再分解成「日、月」，所以這樣的拆分方式可以讓「盟」字保留了「明、日、月、皿」四種特徵)。而「完全拆分」顧名思義是將漢字做完全的分解，拆到所有部件都無法再拆分為止(這樣的拆分方式可以讓「盟」字保留了「日、月、皿」三種特徵)。因為「最小拆分」基本上可以涵蓋所有「完全拆分」的特徵，故建立基礎的漢字拆分表時，應當以「最小拆分」為原則。例如：
明：日月
𣋂：日朝
盟：明皿
𣇵：日明
......

拆分表可以從漢字構形資料庫整理取得，或是參考 "剎那字引" 離線版裡的 ids_char.js 取得(兩者都是 GPL3 授權開放，但後者並沒有包含 Unicode 的 Ext-C, D 字)。

完拆比對法
有了基礎的漢字拆分表後，要做部件檢字，最簡單的方法就是「完全拆分比對法」。它的演算法如下：
[前置作業] 事先將所有基礎漢字拆分表裡的最小拆分，利用遞迴的技巧(每個部件都查拆分表，並用查到的新拆分取代掉該部件)轉換成「完全拆分」(當然也可以比對時再即時進行拆分，但查詢速度相對就慢)。最好同時做排序，以利比對時加快速度。例如：
明：日月
𣋂：十十日日月
盟：日月皿
𣇵：日日月
......
1. 將使用者輸入的部件序列，先查表轉換成「完全拆分」。譬如使用者輸入「日、明」，「日」查表得到「日」，代表無法再拆，「明」查表得到「日、月」，所以得到完全拆分的結果為「日、日、月」。這個結果我們可以稱之為「特徵描述」。
2. 將「特徵描述」逐筆與拆分表裡的完全拆分比對，只要該筆完全拆分裡同時包含有所有的「特徵」，那麼這個字便是符合條件的字。例如「𣋂、𣇵」。
沒想到原來部件查詢可以是這麼簡單吧！因為做了完全拆分的緣故，所以輸入「日、明」跟輸入「日、日、月」所得到的結果會是相同的。

範例程式：部件檢索(完拆比對).zip
4/7 更新：改為新整理的拆分表，除部分相容表意字外，已涵蓋 Unicode Ext-A,B,C,D 所有字。

窮舉比對法
完拆比對法雖然簡單，但有個問題，因為輸入「日、明」跟「日、日、月」是等效的，如果有個字同時有「日、日、月」三個特徵，但其中的「日」與「月」並不構成「明」這個特徵，例如「𣋂」這個字，那麼輸入「日、明」會找出「𣋂」便顯得有點不怎麼合理。於是我們再換另一個「窮舉拆分比對法」來試試，它的演算法如下：
[前置作業] 事先將所有基礎漢字拆分表裡的最小拆分，利用遞迴的技巧(每個部件都查拆分表，並將查到的新拆分插進既有的拆分之中)轉換成「窮舉拆分」(當然也可以比對時再即時進行拆分，但查詢速度相對就慢)。最好同時做排序，以利比對時加快速度。例如：
明：日月
𣋂：日朝𠦝十早日十月 (為方便理解，並未排序)
盟：明日月皿 (為方便理解，並未排序)
𣇵：日明日月 (為方便理解，並未排序)
......
1. 將使用者輸入的部件序列，經排序而不拆分直接做為「特徵描述」。
2. 將「特徵描述」逐筆與拆分表裡的窮舉拆分比對，只要該筆窮舉拆分裡同時包含有所有的「特徵」，那麼這個字便是符合條件的字。譬如使用者輸入「日、日、月」，結果會找到「𣋂、𣇵」；輸入「日、明」，結果會找到「盟、𣇵」。
雖然輸入「日、明」不會再找到「𣋂」這個字，改善了「完拆比對法」的缺點，但現在卻多跑出了個「盟」字。「盟」字具備有「明、日、月、皿」四個特徵，但它並沒有 "同時" 具備「日、明」兩個特徵，把它找出來並不合理。「日、明」跟「明」等效，這是「窮舉比對法」的缺點。
實作上為加快比對速度，可以將窮舉拆分表轉換為 "部件：字..." 的形式，例如 "日：明盟...(所有含有日的字集)"，查表時用每個「特徵」去找出字集，然後取這些字集的交集便是我們要找的字了。

範例程式：部件檢索(窮舉比對).zip
4/7 更新：改為新整理的拆分表，除部分相容表意字外，已涵蓋 Unicode Ext-A,B,C,D 所有字。

實際驗證
接下來我用幾個既有的主流 "漢字構形檢索工具" 跟我自己寫的 "範例程式" 來做一個比較驗證。這些工具的網址連結分別是：漢字構形庫---部件檢字、漢文博士、剎那字引，有興趣的朋友不妨一起動手試試。

漢文博士有一個 "檢索嵌套部件" 的選項，以下以 "+嵌" 表示勾選(預設)。另外由於剎那字引沒有包含 Unicode 的 Ext-C, D 字，為得到合理的比較，故將漢文博士的 Ext-C, D 字排除統計。以下不合理的檢出字以紅色標示。
1. 輸入 [日月]
漢字構形庫：282字 - 明 脂 萌 盟 腥 猒 腊 奛 𡹌 琞 ...
漢文博士+嵌：241字 - 冐 厭 厴 嘲 嚈 壓 奛 奣 嬮 廟 ...
漢文博士：15字 - 冐 明 䐶 𡦇 𢧠 𣎇 𣎘 𣎦 𤦛 𦛭 𦜄 𦜷 𦟢 𦣙 𩎂
剎那字引：99字 - 㬯 㬼 㿢 䳟 嘲 奛 奣 廟 擝 明 ...
完拆比對：99字 - ... (與剎那字引相同)
窮舉比對：99字 - ... (與剎那字引相同)
◎各檢索工具所收字數、拆法略有不同，故檢出字數有所出入。我的範例程式暫借剎那字引的基礎拆分表來用，故基本上與其一致。
◎漢文博士未勾選檢索嵌套時，只列出最小拆分即含有該特徵的字，與使用者期待完全不符，沒有什麼意義。為省篇幅以下不再贅述。
2. 輸入 [明]
漢字構形庫：282字 - 明 脂 萌 盟 腥 猒 腊 奛 𡹌 琞 ... (與 [日月] 相同)
漢文博士+嵌：47字 - 奛 奣 擝 曌 朚 橗 焽 琞 盟 萌 㿢 䳟 𠒫 𠓓 𡦀 𡪙 𡹌 𢅆 𢜏 𢜠
   　 - 𢡗 𢡰 𢢤 𣇴 𣇵 𣈂 𣈇 𣊧 𣋐 𣔂 𣷠 𤀄 𤊉 𥎒 𥯋 𦁠 𦡉 𦻽 𧖽 𧡜
   　 - 𧾆 𨞚 𨧹 𨮠 𨵛 𩣶 𪂡
漢文博士：40字 - 奛 奣 曌 朚 焽 琞 盟 萌 㿢 䳟 𠒫 𠓓 𡦀 𡪙 𡹌 𢜏 𢜠 𢡰 𢢤 𣇴
  - 𣇵 𣈂 𣈇 𣊧 𣋐 𣔂 𣷠 𤊉 𥎒 𥯋 𦁠 𦻽 𧖽 𧡜 𧾆 𨧹 𨮠 𨵛 𩣶 𪂡
剎那字引：48字 - 奛 奣 擝 曌 朚 橗 焽 琞 盟 萌 㿢 䳟 𠒫 𠓓 𡦀 𡪙 𡹌 𢅆 𢜏 𢜠
  - 𢡗 𢡰 𢢤 𣇴 𣇵 𣈂 𣈇 𣊧 𣊧 𣋐 𣔂 𣷠 𤀄 𤊉 𥎒 𥯋 𦁠 𦡉 𦻽 𧖽
  - 𧡜 𧾆 𨞚 𨧹 𨮠 𨵛 𩣶 𪂡
完拆比對：99字 - ... (與 [日月] 相同)
窮舉比對：47字 - ... (與漢文博士+嵌相同)
◎漢字構形庫，[明] 與 [日月] 等效，與使用者的直覺期待不符。
◎剎那字引的拆分檢字表有誤，部件形成的疊字均會重複出現，例如 "𣊧" 字即重複出現兩次。
◎完拆比對法，[明] 與 [日月] 等效，與使用者的直覺期待不符。
3. 輸入 [日日月]
漢字構形庫：8字 - 𣇵 𣊧 𣊿 𣋂 𣋐 𣎱 𦣖 □
漢文博士+嵌：241字 - 冐 厭 厴 嘲 嚈 壓 奛 奣 嬮 廟 ... (與 [日月] 相同)
漢文博士：15字 - 冐 明 䐶 𡦇 𢧠 𣎇 𣎘 𣎦 𤦛 𦛭 𦜄 𦜷 𦟢 𦣙 𩎂 (與 [日月] 相同)
剎那字引：7字 - 𣇵 𣊧 𣊿 𣋂 𣋐 𣎱 𦣖
完拆比對：7字 - 𣇵 𣊧 𣊿 𣋂 𣋐 𣎱 𦣖
窮舉比對：99字 - ... (與 [日月] 相同)
◎漢文博士的檢字，[日日月] 與 [日月] 等效，與使用者的直覺期待不符。
◎窮舉比對法，[日日月] 與 [日月] 等效，與使用者的直覺期待不符。
4. 輸入 [日明]
漢字構形庫：8字 - 𣇵 𣊧 𣊿 𣋂 𣋐 𣎱 𦣖 □ (與 [日日月] 相同)
漢文博士+嵌：47字 - 奛 奣 擝 曌 朚 橗 焽 琞 盟 萌 㿢 䳟 𠒫 𠓓 𡦀 𡪙 𡹌 𢅆 𢜏 𢜠
   　 - 𢡗 𢡰 𢢤 𣇴 𣇵 𣈂 𣈇 𣊧 𣋐 𣔂 𣷠 𤀄 𤊉 𥎒 𥯋 𦁠 𦡉 𦻽 𧖽 𧡜
   　 - 𧾆 𨞚 𨧹 𨮠 𨵛 𩣶 𪂡 (與 [明] 相同)
漢文博士：1字 - 𣇵
剎那字引：47字 - ... (與 [明] 相同)
完拆比對：7字 - 𣇵 𣊧 𣊿 𣋂 𣋐 𣎱 𦣖 (與 [日日月] 相同)
窮舉比對：47字 - ... (與 [明] 相同)
◎漢字構形庫，[日明] 與 [日日月] 等效，與使用者的直覺期待不符。
◎漢文博士勾選檢索嵌套時，[日明] 與 [明] 等效，與使用者的直覺期待不符。
◎剎那字引，[日明] 與 [明] 等效(少了重出的𣊧字)，與使用者的直覺期待不符。
◎完拆比對法，[日明] 與 [日日月] 等效，與使用者的直覺期待不符。
◎窮舉比對法，[日明] 與 [明] 等效，與使用者的直覺期待不符。

比對結果
"漢字構形庫" 的表現與 "完拆比對" 基本上一致，故可推論它的內部是採用完拆比對的演算法。

"漢文博士+嵌" 的表現與 "窮舉比對" 基本上一致，故可推論它的內部是採用窮舉比對的演算法。

漢文博士未勾選檢索嵌套時，只列出最小拆分即含有特徵的字，與使用者期待完全不符，沒有什麼實用上的意義。

"剎那字引" 的表現與 "窮舉比對" 基本上一致，只在特徵有重複部件時(見 3. [日日月])有做特殊處理(檢視官網上的版本說明，2012.9.15版-修正輸入重複部件，重複顯示之問題。或許與此有關)，故可推論它的內部是採特例修正的窮舉比對演算法。

結論
幾個主流的 "漢字構形檢索工具" 大概不是採用「完拆比對法」就是「窮舉比對法」來實作檢字的功能，但這兩種方法都有其檢字不夠精確、與使用者直覺期待不符的缺點。我分析這兩種方法的特性，最後綜合二者，把它們聯合起來使用，改良出一種新的演算法，姑且稱之「二次比對法」。使用這個方法，基本上沒有上述的缺點，檢字比較能符合使用者的直覺期待。最後我用這個方法，製作了一部 "部件檢索" MDict 辭典，目前僅為測試版，暫借用了 "剎那字引" 的拆分表資料，故未包含 Unicode 的 Ext-C, D 字。部件的異體處理則由阿文兄仗義相助提供了一份部首異體表來應急。雖然缺失還很多，不過至少證明一件事，製作一個具有部件查詢功能的 MDict 辭典，技術上是可行的。有興趣的朋友不妨玩玩看，順便幫我測試一下。

下載連結：部件檢索.zip
4/7 更新：改為新整理的拆分表，除部分相容表意字外，已涵蓋 Unicode Ext-A,B,C,D 所有字。

請將 "部件檢索" 辭典與其他中文辭典(例如前兩篇分享的 "教育部重編國語辭典修訂本"、"開放康熙字典")設成聯合辭典群組，並切換至該辭典群組。直接輸入 "+"(取其部件相加的聯想) 或 "G"(取其構形發音的聯想)，MDictPC 1.3 Beta2 以後的版本會吃符號字元，僅能用後者。此時應該就會叫出檢索畫面，在部件輸入框輸入特徵描述即可開始檢字，點擊檢索輸出的字即可跳轉查詢其他字典。

這部辭典的完成，要感謝阿文兄的發想、督促與支援。沒有他，也就沒有這部檢索辭典的誕生。

備註
◎測試版及範例程式使用的拆分表資料，轉換自 "剎那字引" 的拆分表(GPL3 授權開放)。
4/7 更新：改為自行整理的拆分表(以 "漢字構形資料庫" 為主，另以 "字形ＩＤＳデータ" 做為補充)，雖仍有許多瑕疵待修正，但除部分相容表意字外，已涵蓋 Unicode Ext-A,B,C,D 所有字，共 75353 字。由於變更了拆分表，上述驗證的記錄可能已有出入，但應不影響結果與結論。
◎文中的一些名詞，如「完全拆分」、「窮舉拆分」等等，是我為方便理解而自創，並非嚴謹的學術名詞。
◎範例程式完全是我自己設計，未引用任何第三方的程式，較為簡潔、易於閱讀。
◎文章的內容及範例程式，請勿用於任何商業應用，引用則請註明出處。