计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2013年
9期
127-131
,共5页
双数组%Trie树%时间复杂度%分词词典
雙數組%Trie樹%時間複雜度%分詞詞典
쌍수조%Trie수%시간복잡도%분사사전
double-array%Trie-tree%time complexity%word segmentation dictionary
基于双数组Trie树的中文分词词典具有较高的查找效率,但其插入时间复杂度较高.为此提出了一种基于双数组Trie树结构的改进算法iDAT,在原始词典初始化时优先处理分支多的节点,并在初始化之后对base数组中的空序列的下标值做Hash,Hash表中存放空序列之前的所有空序列个数之和,而后运用iDAT算法进行插入.本算法借鉴了单模式匹配的Sunday算法中的跳跃思想,在适当增加空间开销的基础上,降低了Trie树在动态插入过程中的平均时间复杂度,在实际操作过程中有着良好的性能.
基于雙數組Trie樹的中文分詞詞典具有較高的查找效率,但其插入時間複雜度較高.為此提齣瞭一種基于雙數組Trie樹結構的改進算法iDAT,在原始詞典初始化時優先處理分支多的節點,併在初始化之後對base數組中的空序列的下標值做Hash,Hash錶中存放空序列之前的所有空序列箇數之和,而後運用iDAT算法進行插入.本算法藉鑒瞭單模式匹配的Sunday算法中的跳躍思想,在適噹增加空間開銷的基礎上,降低瞭Trie樹在動態插入過程中的平均時間複雜度,在實際操作過程中有著良好的性能.
기우쌍수조Trie수적중문분사사전구유교고적사조효솔,단기삽입시간복잡도교고.위차제출료일충기우쌍수조Trie수결구적개진산법iDAT,재원시사전초시화시우선처리분지다적절점,병재초시화지후대base수조중적공서렬적하표치주Hash,Hash표중존방공서렬지전적소유공서렬개수지화,이후운용iDAT산법진행삽입.본산법차감료단모식필배적Sunday산법중적도약사상,재괄당증가공간개소적기출상,강저료Trie수재동태삽입과정중적평균시간복잡도,재실제조작과정중유착량호적성능.
