基于双数组Trie树的渔业领域分词研究

《基于双数组Trie树的渔业领域分词研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、安徽农业科学袁允燥怎则灶葬造燥枣粤灶澡怎蚤粤早则蚤援杂糟蚤援圆园园8袁36渊11冤院4788-4790责任编辑金琼琼责任校对卢瑶基于双数组Trie树的渔业领域分词研究高艳萍，于红，尹祥贵，綦孝姬，王春永，赵志强（大连水产学院信息工程学院，辽宁大连116023）摘要渔业信息分词对渔业信息系统处理的速度和效率有很大的影响。对汉语词典查询算法进行了分析，用基于双数组Trie树机制的汉语词典实现了渔业信息的分词，并与基于双字Hash机制词典的分词方法进行了试验对比，证明双数组Trie树机制的词典比基于双字Ha

2、sh机制的词典有更高的查询速度。关键词双数组Trie；双字Hash；渔业信息处理；词典中图分类号S126文献标识码A文章编号0517-6611（2008）11-04788-03ResearchonDouble蛳arrayTrieBasedFisherySegmentationGAOYan蛳pingetal（SchoolofInformationEngineering,DalianFisheriesUniversity,Dalian,Liaoning116023）AbstractFisheryinfor

3、mationsegmentationisanimportantpartoffisheryinformationprocessingsystem,whichhasanimportantinfluenceonthespeedandefficiencyofthefisheryinformationsystem.TheChinesedictionaryqueryalgorithmwasfirstanalyzed.AndDouble蛳arrayTriebasedfisherysegmentationwasimp

4、lemented.TheperformanceofDouble蛳arrayTriebasedfisherysegmentationwascomparedwiththatofDouble蛳wordHashbasedfisherysegmentation.Theresultshowedthatthequeryspeedoftheformerwasfasterthanthelatter.KeywordsDouble蛳arrayTrie；Double蛳wordHash；Fisheriesinformation

5、processing；Dictionary1汉语词典查询的常用机制志‘’作为一个关键词位串，然后通过位串比较构造出渔业信息化是渔业现代化的重要组成部分，同时也是PATRICIAtree树，树的每个内部节点包括3个数据项：比促进渔业持续稳定增长最重要的手段之一[1-2]。目前已有较位、左指针、右指针，树的叶子节点代表1个词条，查询时不少渔业信息网、水产信息网建成并投入使用，如美国的根据内部节点选择后继路径直到叶子节点。该方法的优点“西太平洋渔业信息网”[3]，国内的“中国渔业信息网”、“中是引入了比

6、较位，避免了关键词的逐位比较，保证了国水产资讯网”等。在渔业信息处理系统中，汉语词典查询PATRICIAtree内的每个结点都有左右2个子树，所以是一个重要的基础环节，在整个处理过程中都需要频繁地PATRICIAtree满二叉树n个关键词的空间复杂度为O（n）。访问词典以获得汉语词语知识，因而汉语词典的快速查询2双数组Trie（Double蛳ArrayTrie）的数据结构与具体实现是提高系统效率的关键所在。早期的词典组织构造主要基Trie树是搜索树的一种，是英文单词“Retrieval”的简于传统的H

7、ash方法，其关键之处在于Hash函数的设计，桶写，可以建立有效的数据检索组织结构。Trie树在本质上是数多则内存耗费大，少则会出现严重的访问冲突，且由于一个确定的有限状态自动机（deterministicfiniteautomationHash表中分布的不均匀，会造成实际访问效率远低于理论DFA），每个节点代表自动机的一个状态，根据变量的不同[4]。进行状态转移，当到达结束状态或者无法转移时完成查询。Hash表中数据均匀下计算出的访问效率[5]，传统的DFA一般用转换表的方式来实现，表的列代表自动T

8、rie索引树是一种以树的多重链表形式表示的键树李江波[6]和王思力[7]将双数组Trie树用于中文分词，并证明机的不同状态，行代表转换变量，当DFA的状态增多时，需了算法的有效性。Trie索引树的词典机制由首字散列表和要的表空间以平方级增长，此时其空间复杂度为O（n2），这样表就可能变得异常庞大，从而浪费了许多存储空间[10]。使Trie索引树结点2部分组成。Trie索引树的优点在于分词应用，在对被切分语句的一次扫描过程中，不需预知待查询词用链表节点同样