2015年12月9日 星期三

再談漢字的部件檢索

今年的四月初,我發布了一篇「部件檢索辭典」的發文,將我研究漢字部件檢索的過程與心得記錄了下來,也將實作的測試版成果分享出來,給有興趣的朋友進行使用、測試。然後我又花了數個月的時間整理拆分資料(期間蒙文良兄支援,幫我負擔了近一半的工作,再次申謝),由於整理的過程費時勞心,以致完成初步整理後便氣力放盡,不想再碰,接下來的幾個月也就沒再動它。一直到了九月底,開始有一些朋友陸續回應一些問題及建議(感謝瑾昀提供了許多字理的分析及專業的建議),我才又開始把這個題目再撿回來,好好地重新檢視一遍,這一檢視又開始了一段「廢寢忘食」的辛苦旅程。年過半百,忘性漸增,趁著記憶猶新,趕緊再整理記錄下來,也為自己留下一段「有趣」的人生記憶。

前情摘要

最小拆分
將漢字做最小程度的分解,讓它可以保留最多的可能特徵,這種拆分方式我稱之為「最小拆分」。以「𨀣」字為例,我們可以將它最小拆分成「𧾷、企」。因為「𧾷」字可以再分解成「口、止」、「企」字可以再分解成「𠆢、止」,所以這樣的拆分方式隱含的可以讓「𨀣」字保留了「𧾷、口、止、企、𠆢、止」等六個特徵。

完全拆分(最大拆分)
將漢字做最大程度的完全分解,拆分到所有的部件都無法再繼續拆分為止,這種拆分方式我稱之為「完全拆分」。以「𨀣」字為例,我們可以將它完全拆分成「口、止、𠆢、止」。這些已無法再分解的部件,稱之為「終端部件」或「字根」,而這樣的拆分方式可以讓「𨀣」字保留了「口、止、𠆢、止」等四個特徵。

一字多拆
同一個字有一種以上的最小拆分方法,但每種拆法的最終完全拆分都是相同,這種情形我稱之為「一字多拆」。例如「羆」字,可以拆成「罒、熊」,也可以拆成「罷、灬」,而兩種拆法的最終完全拆分都是「罒、厶、⺼、匕、匕、灬」。

同字異拆
同一個字有一種以上的最小拆分方法,但每種拆法的最終完全拆分卻是不同,這種情形我稱之為「同字異拆」。例如「主」字,可以拆成「丶、王」,也可以拆成「亠、土」,因為兩種拆法都已是終端部件無法繼續再拆,所以同一字最終的完全拆分卻是完全不同。

完拆比對法(完全拆分比對法)
[前置作業] 事先將所有基礎漢字拆分表裡的最小拆分,利用遞迴的技巧(每個部件都查拆分表,並用查到的新拆分取代掉該部件)轉換成「完全拆分」。最好同時做排序,以利比對時加快速度。例如:
明:日月 (為方便理解,並未排序)
朋:月月 (為方便理解,並未排序)
𣋂:日十日十月 (為方便理解,並未排序)
盟:日月皿 (為方便理解,並未排序)
𣇵:日日月 (為方便理解,並未排序)
......
[1] 將使用者輸入的部件序列,查表轉換成「完全拆分」。這個結果我們可以稱之為「完拆特徵」。譬如使用者輸入「日、明」,「日」查表得到「日」,代表無法再拆,「明」查表得到「日、月」,所以得到的完全拆分為「日、日、月」。
[2] 將「完拆特徵」逐筆與拆分表裡的「完全拆分」比對,只要該筆完全拆分裡同時包含有所有的「特徵」,那麼這個字便是符合條件的字。例如「𣋂、𣇵」。而其中「完全拆分」與「特徵描述」一模一樣的字,我稱之為「精確命中」,例如「𣇵」字;其餘則稱之為「模糊命中」,例如「𣋂」字。
因為「明」字會被拆分為「日、月」,所以「日、明」必然會跟「日、日、月」等效(失去了「明」這個特徵的限定),這個現象我稱之為「限縮等效」,這是「完拆比對法」的缺點。
沒有「一字多拆」的問題。「同字異拆」或許可以用增加拆分定義的方式解決。例如原本「主:丶王」再增補一筆「主:亠土」。

窮舉比對法
[前置作業] 事先將所有基礎漢字拆分表裡的最小拆分,利用遞迴的技巧(每個部件都查拆分表,並將查到的新拆分插進既有的拆分之中)轉換成「窮舉拆分」。最好同時做排序,以利比對時加快速度。例如:
明:日月 (為方便理解,並未排序)
朋:月月 (為方便理解,並未排序)
𣋂:日朝𠦝十早日十月 (為方便理解,並未排序)
盟:明日月皿 (為方便理解,並未排序)
𣇵:日明日月 (為方便理解,並未排序)
......
[1] 將使用者輸入的部件序列,經排序而不拆分直接做為「特徵描述」。
[2] 將「特徵描述」逐筆與拆分表裡的「窮舉拆分」比對,只要該筆窮舉拆分裡同時包含有所有的「特徵」,那麼這個字便是符合條件的字。譬如使用者輸入「日、日、月」,結果會找到「𣋂、𣇵」;輸入「日、明」,結果會找到「盟、𣇵」。
實作上為減少比對次數,常將窮舉拆分表轉換為「部件:字...」的形式,例如「日:明盟...(所有含有日的字集)」,查表時用每個「特徵」去找出字集,然後取這些字集的交集便是我們要找的字了。但這個做法會讓「月月」、「月月月」、「月月月月」都與「月」等效(失去了重複部件的數量限定),也是一種「限縮等效」,是為其缺點。
因為含有「明」這個部件的字,必然含有「日」與「月」,所以「日、明」、「月、明」必然都會跟「明」等效(失去了「日」或「月」額外特徵的限定),同樣是「限縮等效」,這是「窮舉比對法」的缺點。另一缺點為無法判定是否「精確命中」。
「一字多拆」與「同字異拆」可以用增加「中間部件」的方式解決。例如「羆:罒熊厶⺼匕匕灬罷」、「主:丶王亠土」。

二次比對法
[前置作業] 事先將所有基礎漢字拆分表裡的最小拆分,利用遞迴的技巧(每個部件都查拆分表,並用查到的新拆分取代掉該部件)轉換成「完拆部件」加上「中間部件」。最好同時做排序,以利比對時加快速度。例如:
明:日月 (為方便理解,並未排序)
朋:月月 (為方便理解,並未排序)
𣋂:日十日十月 + 朝𠦝早 (為方便理解,並未排序)
盟:日月皿 + 明 (為方便理解,並未排序)
𣇵:日日月 + 明 (為方便理解,並未排序)
......
[1] 將使用者輸入的部件序列,經排序而不拆分直接做為「特徵描述」。
[2] 將「特徵描述」逐筆與拆分表裡的「完拆部件」加「中間部件」比對(等同於「窮舉比對」),只要該筆拆分裡同時包含有所有的「特徵」,那麼這個字便可能是符合條件的字,繼續下面的第二次比對。譬如使用者輸入「日、明」,結果符合條件的字是「盟、𣇵」。
[3] 將使用者輸入的部件序列,查表轉換成「完全拆分」做為「完拆特徵」。譬如使用者輸入「日、明」,則完全拆分為「日、日、月」。
[4] 將「完拆特徵」與拆分表裡的「完拆部件」比對,只要該筆完全拆分裡同時包含有所有的「特徵」,那麼這個字便是符合條件的字。譬如使用者輸入「日、明」,則符合條件的字是「𣇵」。如此一來便是既符合「窮舉比對」又符合「完拆比對」的字。
這是我自己為解決「完拆比對法」及「窮舉比對法」的缺點所設計出來的演算法,沒有「限縮等效」的問題。
「一字多拆」可以用增加「中間部件」的方式解決。例如「羆:罒厶⺼匕匕灬 + 熊罷」。「同字異拆」或許可以用增加拆分定義的方式解決。例如原本「主:丶王 +」再增補一筆「主:亠土 +」。

異體映射
定義一種不同部件之間的映射關係,藉由比對時的單向取代替換,達到視「異體」為「相同」的目的。例如定義一組「⻏→邑」的映射,在進行「包容異體」的比對時,依定義將所有的「⻏」替換成「邑」,所有的「邑」則維持不變,如此便能達成視「⻏」與「邑」為相同的目的。

新的挑戰
十月初開始把這個題目再撿回來重新檢視,終於又把《部件檢索》做了一次更新,將我跟文良兄合力整理的拆分結果、以及 Unicode Ext-E 的字也都放了進去,「異體映射」也做了一些修訂,另外增加了一個常用部件的輔助輸入鍵盤,方便鍵入一些不易輸入的部件,讓使用起來更方便一些。接著陸續又接受了一些好友的建議,加強了一些功能。但也在這個時候發現了一個嚴重的瑕疵:隨著「異體映射」關係的陸續擴增,開始引發了複雜的交互影響,導致檢索結果偶有缺漏。



先說說為什麼需要有「異體映射」的設計呢?舉個例來說,屬於部首「邑」的字很多都作「⻏」的偏旁,像「部」字的拆分就是「咅、⻏」。可是這個「⻏」一般輸入法很難打出來,比較理想的做法就是讓使用者可以輸入「邑」來替代,這就是「包容異體」的主要作用。或許有人會說:只要把「部」字的拆分改做成「咅、邑」不就得了。確實有些拆分的整理便是如此處理類似問題,但「邑」部還真有個拆分為「咅、邑」的「郶」字(為「部」的古字),如果真的這樣處理,那這兩個字的拆分便沒有機會加以區分了。

既然「異體映射」的設計在實際的使用上是有其必要的,那麼這個瑕疵也就避無可避,必須解決。

我花了許多時間想找出問題癥結,但千絲萬縷、牽一髮而動全身,修改了幾個版本都淪於治標不治本,西線無事東線又起,並不能真正的解決問題。像瞎子摸象一般的毫無頭緒,我陷入了束手無策的困境。

我知道必須沉住氣靜下心來。於是開始收集朋友們反饋回來的所有問題案例,一一建檔,在記事本上將每個字的拆分畫成一棵棵的拆分樹,並且標註上異體之間的映射關係。根據這些圖譜,我試著歸納分析,想找出到底什麼樣的映射定義會引起交互影響?什麼樣的定義又沒有問題?導致檢索結果缺漏的機轉又是什麼?
果然,靜心是解決問題的不二法門,我終於建立出一套分析模型,可以完整評估異體映射的影響機轉。

異體映射分析模型
若異體關係為 a 或 A 部件映射至 b 或 B 部件,這裡以小寫字母表示不可拆分的部件;大寫字母表示尚可拆分的部件,而 A 可被完全分解成 a1、a2、...、aN,B 可被完全分解成 b1、b2、...、bN。在 b 或 B 不可再繼續進行映射的前提下:
ab 型映射:拆分表裏的 a 部件被取代成 b,b 部件則不變;查詢輸入裏的 a 部件被取代成 b,b 部件則不變。結果「完拆比對」的基準一致,都變成 b,沒有問題。
例如「⺌→小」、「丷→八」。
aB 型映射:拆分表裏的 a 部件被取代成 B,B 部件則不變,然後 B 被完全分解成 b1、b2、...、bN;查詢輸入裏的 a 部件被取代成 B,B 部件則不變,然後 B 被完全分解成 b1、b2、...、bN。結果「完拆比對」的基準一致,都變成 b1、b2、...、bN,沒有問題。
例如「⻖→阜」(⻖:⻖ 阜:丿㠯十)。
Ab 型映射:完全拆分表裏的 a1、a2、...、aN 部件不變,b 部件不變;查詢輸入裏的 A 部件被取代成 b,b 部件則不變。結果「完拆比對」的基準不一致,一個是 a1、a2、...、aN,一個是 b,造成問題,含有 A 部件的字將無法被檢出。
例如「𦥑→臼」(𦥑:ㅌ彐 臼:臼),拆分表裏含有「𦥑」的字將無法被檢出。
【解法】可將 A 與 b 對調,成為 aB 型映射便可解決。
AB 型映射:❶ 若 A 與 B 的「完全拆分」經映射後最終相同
拆分表裏的 a1、a2、...、aN 部件最終被取代成 b1、b2、...、bN,b1、b2、...、bN 部件則不變;查詢輸入裏的 A 部件被取代成 B,B 部件則不變,然後 B 被完全分解成 b1、b2、...、bN。結果「完拆比對」的基準一致,都變成 b1、b2、...、bN,沒有問題。
例如「𧾷→足」(𧾷:口止 足:口龰→口止)、「兑→兌」(兑:丷口儿→八口儿 兌:八口儿)。
❷ 若 A 與 B 的「完全拆分」經映射後最終不同
拆分表裏的 a1、a2、...、aN 部件不變,b1、b2、...、bN 部件也不變;查詢輸入裏的 A 部件被取代成 B,B 部件則不變,然後 B 被分解成 b1、b2、...、bN。結果「完拆比對」的基準不一致,一個是 a1、a2、...、aN,一個是 b1、b2、...、bN,造成問題,含有 A 部件的字將無法被檢出。
例如「卽→即」(卽:白匕卩 即:卩),拆分表裏含有「卽」的字將無法被檢出。
【解法】目前無解。

根據這個分析模型的推導可知,造成問題的根源在於「完拆比對法」的特性,只要遇上 Ab 型或 AB 型的異體映射便有可能造成問題。我所設計的「二次比對法」,聯合使用了「窮舉比對法」與「完拆比對法」,雖然成功地解決了它們的「限縮等效」缺點,但卻仍然繼承了「完拆比對法」的此一缺點。至此我心裏明白,這個「二次比對演算法」對目前設定的這些問題已缺少了簡潔、優雅的特質,多年的系統開發經驗所演化出來的直覺告訴我:「我用了不合適的演算法」來解決問題,如此再繼續東修西補下去,勢必還有許多「無法可解的瑕疵」存在。

我陷入了苦思:「如果該放棄二次比對法,那我還有什麼更好的方法?」整日裡縈繞著這個難題,連晚上也不曾 "安眠",躺在床上腦袋也還停不下來地繼續思索,深深陷入 "全面作戰" 的專注情緒。

拆分樹比對法
數天後的某日,就在我一邊畫著一棵一棵「拆分樹」,一邊深深思索時,突然靈光一閃。既然畫出「拆分樹」能幫助我釐清「部件拆分」與「異體映射」間的複雜交互關係,這不就代表著它是個解決問題的「好方法」?真是眾裡尋他千百度,驀然回首,那人卻在燈火闌珊處。我大喜過望,立刻開始將此一想法試著轉化成實際可行的演算法。經過幾天的努力推演,評估確實可行,於是大刀闊斧將整個「二次比對演算法」砍掉重練,完全拋開「完拆比對」、「窮舉比對」,重新設計出一套全新的演算法。因為運作的靈感與原理均得自於「漢字拆分樹」,所以我將它命名為「拆分樹比對演算法」。採用了這個演算法後,沒有了那種當「完全拆分」遇上「異體映射」的「無法掌控」感,理路清晰而明確,能夠以「簡」馭「繁」。我知道,這方法應該是對了。

「拆分樹比對法」集成了所有先前方法的優點而無其缺點:① 沒有「限縮等效」的問題。② 可以標示「精確命中」。③ 不須多重比對。④ 能完全駕馭「異體映射」,沒有複雜的交互影響。⑤ 同時可以包容實踐「一字多拆」、「同字異拆」的功能。⑥ 體積幾乎沒有增加(目前輕微變大是因為已多加入了「同字異拆」的定義)。如果我的想法沒有新的漏洞,這個「拆分樹比對法」堪稱是目前為止最完美的演算法了。

簡單的說(請一邊參照上面的漢字拆分樹圖片),假設每個部件就是一片葉子,使用者輸入數個部件來進行檢索,就相當於用一個「檢索籃子」裝著數片「葉子」。我們提著籃子走進「漢字樹林」中,在第一棵樹下我們拿出一片「葉子」跟樹上的「葉子」比對一番,若有相同的則將其「連枝帶葉」摘下一同丟於地上,然後再從籃子裡拿出下一片繼續搜尋比對。若有找不到的「葉子」,那麼這棵「樹」便不是我們所要的,換下一棵。若所有的「葉子」都找到了,那麼這棵「樹」便是我們所要的(若剛好樹上的「葉子」也都摘光了,那就是「精確命中」),再繼續進行下一棵。用這樣的比喻來形容「拆分樹比對法」,是不是很容易理解呢!

結語
為了一個跟我的工作、跟商業營利無關的「漢字部件檢索」,我投入了大量的心力與時間,殫精竭慮、苦苦思索,白髮又不知新添多少。但我喜歡這樣的挑戰,發掘問題、分析歸納、設計方法,找出問題的最佳解決方案。過程是極辛苦的,但其中的樂趣卻也不是旁人所能領略。雖然拆分資料尚不完善,部件鍵盤也還有待調整,但現在先將這個「最終測試版」分享出來,有興趣的朋友不妨玩玩看,順便多幫我測試一下。

使用時,若查詢的結果出現「豆腐」字(即空心的方框),表示您的系統字型未支援完整的漢字(Unicode、Ext-A、B、C、D、E)。建議可下載安裝「花園明朝體字型」,這樣應該就能完整地顯示查詢的結果。

這一次除了 MDict 格式的版本外,我特地又轉了一份 HTML 格式的離線版(功能完全相同,應該可以在各種平台環境下運行),提供給沒有使用 MDict 的朋友試用。
畫面上的幾個操作 UI 簡述如下:
「X」:清除按鈕,清除所有的查詢輸入及查詢結果。
「▶」:查詢按鈕,進行查詢檢索,查詢結果的上限為一千字。
「包容異體」:勾選時會將所有互為異體的部件視為相同;反之則視為不同。
「即時查詢」:勾選時輸入框裡有任何輸入變動均會自動執行查詢檢索(為縮短反應時間,查詢結果僅限一百字,但「精確命中」的字一定會列出,不在此限。若要查看百字以外的字,可再多按一下「▶」);反之則需等到按下「▶」才會執行查詢檢索。
「▲」:收起按鈕,按一下則收起部件鍵盤,方便查看大量的查詢結果。
「▼」:展開按鈕,按一下則展開部件鍵盤,方便輸入難以鍵入的部件。

下載連結:部件檢索(MDict版).zip
部件檢索(Html版).zip

「部件檢索」已是我閱讀詩經時的一項重要工具,碰到書上那些唸不出來、不知何義的字,利用「部件檢索」我便可進行輸入、查詢,查閱那些我自己製作的離線字、辭典,方便而有效率。

在設計整理的過程中,體認到了現有的拆分整理還是不夠完善,我決定再重新做一次審訂。目前已將「漢字構形資料庫」的最後版本(2.7 版)中可還原成 Unicode 的使用者造字還原完畢(這也花了我數個月的時間),再整合了「字形IDSデータ」上個月才發布的 ids.txt(2015 小幅修正版),做成了一份拆分資料原始稿。計畫接下來就拿它來跟我的拆分表慢慢核對,以「漢字構形資料庫」的資料為主軸(因為它的拆分大多是有字源、字理依據的),審定出一套較完善的拆分資料。不過有近萬處的相異待一一審核,這工作大概又得花上大半年的時間,就當作是磨練心性、慢慢做吧!我不保證這工作一定能做完,「最終測試版」也湊和著還堪用,但等到它真正的完成之日,應該才會是《部件檢索》正式版的推出之時,大家陪我一起慢慢「熬」吧,呵呵!

備註
拆分資料取自於「漢字構形資料庫」與「字形IDSデータ」,再經自行修整而成,目前支援至 Unicode Ext-E。
文中的一些名詞,如「完全拆分」、「窮舉拆分」等等,是我為方便理解而自創,並非嚴謹的學術名詞。
程式完全是我自己獨立設計,未引用任何第三方的程式庫。
文章的內容及程式,請勿用於任何商業應用,引用則請註明出處。


沒有留言:

張貼留言