自動目錄
前言
網頁文字中的正簡互換方式,就是設定一個長長的正體字(請勿說繁體字),對照簡體字的字串,轉換時,每個中文字會拿到這長長的字串中比對每個字,當找到相同的字時,再查找對映的正/簡體字作為轉換的字。這字串當中文字的排列方式就影響到平均每個字要比對多少次的重要關鍵。
為了加速正簡互換的效能,我針對常見的簡體字做了挑選,花了六個小時,整理出最常用的1200個簡體中文字及正體中文字對照。因為過去拿別人的正簡2500個文字庫來用時會發現,裡面有許多的罕用字,罕用字的簡體字拿來轉換讓網頁效能低落,例如每轉換一個字,程式就得掃描2500字庫,直到比對完成為止,這樣的演算複雜度為O(n),理論上平均數為2500/2=1250次,但未在列的文字常得掃描到尾發現不存在後才停止,以正簡相同有2500個字來算,有2500個字得掃到底才知道字不存在轉換的列表中如此就做了2500次的比對,因此實際平均為(2500+1250)/2=1975次/每字。
因此我找尋iCIAC[1]這裡提供的常用字2500及次常用字1000,一個字一個字的挑掉正簡相同的字,然後建立一個1200字的表,這樣子平均轉換的時間就能減到(1200+600)/2=900次比對/每字。雖然會有些漏網之魚,但是速度快了約1倍。為了加速比對,我另外加了100個常用字在最前面,這100個常用字正簡相同,在轉換時,由於常見,所以平均轉換速度理論值為(設常用字出現率為全部之10%):
假設有5000個字,其中2500個正簡相同,2500正簡轉換,插入前100個正簡相同的字出現率為10%,則平均每字的比對次數為:
正簡相異 (100+1200/2)*50%+ 正簡相異 (100+1200)*40%+ 100/2*10%=350+520+5=875 (次/每字) 小於未加入100正簡相同的常用字900次比對/每字
假設常用字的出現比率沒這麼高,只有全字的5%,則重算公式為:
正簡相異 (100+1200/2)*50%+ 正簡相異 (100+1200)*45%+ 100/2*5%=350+520+5=937.5(次/每字) 大於未加入100正簡相同的常用字900次比對/每字
以上是假設數值假設機率粗算的結果,接下來要考慮每個字出現的機率作比較精確的估算
這裡有幾個變數,分別是1正簡相異字出現率u 2正簡相同字出現率-正簡相同常用字出現率為v 3正簡相同常用字出現率w,4n是平均每字的比對次數,5M是正簡相同字的常用字數,6正簡相異的字有L個。他們有這樣的關係:
n= (M+L/2)*u+ (M+L)*v+ M/2*w
常用1200字庫
(實際為1130字,依簡字的筆劃排序):
對映的簡體字為
至於常用的正簡相同的100個字(實際169字),我參考了華語網的最常用的一千个汉字使用频率排名[2][6],把正簡相同的字取出來,括號中為換算後之該排文字全文出現率和:
的一是了我(10% 共5字)
不人在他有上到 (5.83% 共7字)
大地子中你生年著就那和要她出也得里自以( 7.60% 共19字)
家可下而天去能小多然於心之都好看起沒成只如事把用第道想作(6.94% 共28字)
美情己面最女但前些所同日手又行意方期它回位分老因很名法斯知世什次使身者被高已其此常活正感(7.21% 共44字)
明力理文定本公特做外孩相西果走月十向全信重三工物每別真打太新比才便夫再部水像眼等卻加主界利海受表德少克代稜先口由死安性光白或住望教命花結色
(7.50% 共69字)
M=172,這172字的全文出現率為 45.08,即w=45.08%,在3500常用字及次常用字中,正簡相異字為1130,因此L=1130,出現比率為 u=1130/3500=32.3%,v=2370/3500-0.4508=22.63% (ps u+v+w=100%[3]),重新推算整理過的字組,代入公式得到n:
n= (172+1130/2)*32.3%+ (172+1130)*22.63%+ 172/2*45.08%= 571.46
這表示以這種方式 [最常用正簡相同172字][正簡相異字1130字]來作字串比表置換的話,每個字的平均比對次數為 571.46次
如果原始情況不取用169常用正簡相同172字而直接比對,得到的理論值為
no= (1130/2)*32.3%+ (1130)*67.71%= 947.61
他們的改善比率提升了約 +40% 的效能
再增加正簡相同的常用字
假設我們再採用更多的正簡相同常用字放在比對字串的前端,是否能再提升更多效能,由於正簡相同常用字出現有機率並非定值,例如「的一是了我」的出現率和是10%,但「家可下而天去能小多然于心之都好看起没成只如事把用第道想作」的出現率和卻是6.9%,這些字並非連續出現,很難用微積分來估算最大值,但採用列舉法來計算,因此,我增加了一組共97字,出現率和為 6.654%
更拉神母父直字平友放至接告入笑内英候民往何度山路男解叫任金快原吃通立象四失格士音目呢病始深完今提求清王化空思切怎非找片元喜曾科言干流约各即指合反必交林晚制球决保及房早院量苦火布品近坐答星精五司巴
重算n(M=269)值為 n269=(269+1130/2)*32.3%+ (269+1130)*15.98%+ 269/2*51.73%=562.51
再加上這76個字,出現率和為 3.47%
奇管未朋且婚台夜青北久乎越落形影红爸百令周吧步希留市半送造容随演收首根整式取照强石古諣拿您似足妻尼米客南衣站黑刻福城故包另建系示持千史准基志静阿痛消社算
重算n(M=345)值為 n345=(345+1130/2)*32.3%+ (345+1130)*12.51%+ 345/2*55.20%=573.67
這裡可以發現,後來加的常用字越來越多,但是出現的比率確沒有大幅增加,必定會有個極值,推估這個極值可能會在560附近,加了97個常用字後,他的平均n值也不過由571.46減少為562.51,減少幅度很有限;再加更多常用字,他的n值反而增加為573.67,比169常用字時n=562.51還高。
常用正簡相同字269字
結論
n=560並不會是最優化的結果,n值一定可以再小,目前想到的作法是不再拆出正簡相同正簡相異的排列法,而採用出現機率來作為排列方式,依據[2]所言1000個常用字(其中正簡相同字約680個,正簡相異字約320個)約為字的出現機率為90%,剩餘再取用810(1130-320)個正簡相異字,理論的n值最佳化:
2.5*0.1+11.5*0.1+30*0.1+61*0.1+110*0.1+186*0.1+355*0.1+441*0.0543+750*(1-0.7543) = 286.17
上式為1000常用字n值再加上非常用字約10%的出現機率,得到最後的n為
n = 286.17 * 90% + 1405*10% =398.05 這應該會是一個非常理想的值,改善提升了 +58%的效能(減少58%的比對時間),更比最初始不挑過的2500版簡字體效能增進 79.8% ,換句話說,如果採用[4]原始的字串組,每個字只需要原本約1/5的比對時間,效能改善非常的可觀。
要得到n=398最佳化的n值,必需要將文字再重新挑過,費時費工費眼力,因此我可能會撰寫程式來做這件事,現階段只能取用n=576的字串。
參考資料
[1] iCIBA 現代罈語常用字表 http://hanyu.iciba.com/zt/3500.html
[2] 最常用的一千个汉字使用频率排名 http://www.thn21.com/base/zi/17300.html
[3] 在[2]中有提供一級字庫常用字3755個出現的機率為99.7%,因此我們粗略的把這3500個字視為100%,誤差±3%。
[4] 正簡轉換用的JS,感謝無名氏提供的程式,程式相當的簡捷,印象中這個程式早在2007年時我就已經有用過了 Std_StranJF.zip
[5] 史上最常用3000漢字 http://www.360doc.com/content/11/0301/14/2053176_97155908.shtml
[6] 教育部 字頻總表 http://www.edu.tw/files/site_content/M0001/pin/biau1.htm