涓婁竴綃囨枃绔?/a>浠嬬粛浜?jiǎn)鍙屾暟缁勫瓧鍏告?DATrie錛岀幇鍦ㄨ鎴戜滑鏉ョ畝鍗曠殑嫻嬭瘯涓嬪唴瀛樺崰鐢ㄦ儏鍐點(diǎn)?/p>
嫻嬭瘯鐢ㄤ緥錛屾垜閫変簡(jiǎn)The Holy Bible錛屾暟鎹枃浠跺ぇ灝忎負(fù)4.2MB銆傚彧璁板綍鑻辨枃鍗曡瘝錛屽叏閮ㄨ漿涓哄皬鍐欍?/p>
Trie鐨勫疄鐜版垜宸茬粡鍋氫簡(jiǎn)涓浜涗紭鍖栵紝鍒濆姣忎釜鑺傜偣鐨勬寚閽堟暟緇?size 涓?錛屽綋鏈夎妭鐐規(guī)彃鍏ユ椂錛屽啀寮 max(size, char) 澶у皬鐨勬暟緇勩倀rie-mem 鏄劇ず鐨勬槸宸茬粡闄ゅ幓鑺傜偣鑷韓鐨勫ぇ灝忥紝鍗寵鏁板間綋鐜扮殑鏄敵璇風(fēng)殑鎸囬拡鏁扮粍鎬誨ぇ灝忋?/p>
trie-mem / ptr-size / nodes = 9.1錛岃鏄庡鉤鍧囨瘡涓妭鐐癸紙鍐呰妭鐐?鍙惰妭鐐癸級(jí)鍒嗛厤浜?.1涓寚閽堛傜浉瀵瑰畬鍏═rie鏍?wèi)鑰岃█錛屽凡緇忚妭鐪佷簡(jiǎn)寰堝絀洪棿浜?jiǎn)銆備絾榪欐牱綆楁氮璐圭殑閲忔槑鏄炬槸涓嶅綺劇‘鐨勶紝nodes 搴旇鎹㈡垚鍐呰妭鐐規(guī)暟錛堣繖閲屽氨鐢?u-words 浠f浛鍙惰妭鐐癸紝铏界劧涓よ呮槸涓嶇瓑鍚岀殑錛夛紝鍥犱負(fù)鍙惰妭鐐規(guī)湭鍒嗛厤鎸囬拡鏁扮粍錛屽茍搴旇鍑忓幓鐪熸鏈夌敤鐨勮漿縐昏竟銆傝繖涓氮璐圭殑鍊煎簲璇ユ槸 (trie-mem / ptr-size – nodes) / (nodes – u-words) = 12.8銆?/p>
DATrie鐨勬氮璐瑰煎簲璇ユ槸 (datrie-mem / (2 * int-size) – nodes) / (nodes – u-words) – 1 = 1.2錛屽彲瑙?DATrie 鐨勭┖闂村鏉傚害榪樻槸鐩稿綋涓嶉敊鐨勩傚綋鐒禗ATrie鐨勫疄鐜版垜榪樻病鏈夎繘琛屾繁鍏ョ殑浼樺寲錛屽熀鏈氨鏄?a style="COLOR: rgb(119,0,0); TEXT-DECORATION: none" >涓婁竴綃囨枃绔?/a>閲岀殑浠g爜鍋氱殑嫻嬭瘯銆傚鏋滄寜閭f枃绔犻噷鎻愬埌鐨勪紭鍖栨柟娉曠戶(hù)緇紭鍖栵紝絀洪棿鐨勬氮璐瑰間細(xì)鏇翠綆銆?/p>
浣咲ATrie瀛樺湪涓涓瘮杈冨ぇ鐨勯棶棰橈紝灝辨槸瀹冪殑絀洪棿鏄鍏堢敵璇峰ソ鐨勶紝鍥犱負(fù)鏍規(guī)湰鏃犱粠寰楀嚭瀹冨疄闄呯殑澶у皬錛屽鏋滅┖闂翠笉澶熷ぇ浜?jiǎn)鍐嶉噸鏂板垎閰嶇殑璇濆Q岄偅鍔垮繀鍙堝緱娑堣楁椂闂達(dá)紝鑰屼笖榪樻槸鏃犳硶瑙e喅絀洪棿鏄惁瓚沖鐨勯棶棰樸傚彟澶栵紝闄勫姞鐨勪俊鎭煙鏈濂戒繚瀛樹(shù)負(fù)鎸囬拡鐨勫艦寮忥紝鍚﹀垯閲嶆帓鏃跺鍒剁殑澶嶆潅搴﹀氨鍙兘浼?xì)寰堥珮銆?/p>
鎬葷粨錛孌ATrie榪樻槸姣旇緝閫傚悎鍦ㄥ伐紼嬩腑搴旂敤錛屽挨鍏跺浜庢暟鎹泦姣旇緝鍥哄畾鐨勩?/p>