登录

  • 登录
  • 忘记密码?点击找回

注册

  • 获取手机验证码 60
  • 注册

找回密码

  • 获取手机验证码60
  • 找回
毕业论文网 > 外文翻译 > 计算机类 > 计算机科学与技术 > 正文

基于双阵列Trie树的汉字分割词典改进算法研究外文翻译资料

 2022-11-30 04:11  

英语原文共 8 页,剩余内容已隐藏,支付完成后下载完整资料


基于双阵列Trie树的汉字分割词典改进算法研究

Wenchuan Yang, Jian Liu, and Miao Yu

北京邮电大学,北京,100876

摘要:基于双阵列Trie树的中文分词词典具有更高的搜索效率,但是动态插入会浪费很多时间。本文提出了一种改进算法-iDat,它在基于双阵列Trie树进行中文分词的基础上进行改进。在初始化原始字典后,我们为基数组的空序索引值实现一个哈希过程。使最终的哈希表存储当前空序列之前的空序列的总和。该算法采用单模匹配的星期跳跃算法,利用空间成本的微小和合理的增加,iDAT降低了Trie Tree中动态插入过程的平均时间复杂度。实际结果表明它具有良好的操作性能。

关键字:双阵列,Trie树,时间复杂度,分词词典。

1 介绍

目前基于词典的匹配算法仍然是主要的搜索引擎公司使用的方法。中文自动分词的基础是字典,其结构与分词的速度和效率直接相关。自动分词是中文信息处理系统的基础,从而进一步提高了中文文本的语法和语义分析[1]。词汇将直接影响分词速度。字典的数据结构主要通过索引方法,包括索引表,反转列表,哈希表和搜索树[2]。

最大匹配算法在文献[3]中给出。文献[4]中提出了基于第一个单词哈希算法的最邻近算法文档。在文献[5]中,提出了词典组合方法和算法,结合了第一个单词哈希和全双字搜索,进一步提高了分割速度。既然有这么多中文的话,很难使用哈希表来控制数据分发,减少冲突。GB-2312中有6768个常用汉字,每个汉字可以唯一地映射到1-6768 [6]。所以我们可以使用双阵列Trie Tree作为中文分词字典的数据结构。在文献[7]中提出,双阵列Trie Tree是一个改进的版本。

双阵列Trie Tree的搜索效率为O(n),n为匹配字符串的长度。它具有良好的搜索性能和弱插入性能。即使调整后,它的插入性能仍然为O(cm2)。这里m是字符集大小,常数C.对于基于双阵列Trie Tree的中文字典的研究,首先处理具有更多分支的节点的方法来提高空间利用率[8]。

正如我们之前在文献[2]中提到的,有一种安排冲突节点进入哈希表,而不需要重新分发节点来提高插入的效率处理方法。然而哈希冲突是不可避免的,使用哈希会增加搜索次数。文献[8]中提出了基于遗传算法和舍伍德双阵列Trie Tree的优化方法。它提高了空间利用率,同时也避免了算法的局部最优解。

在本文中,我们将提出一种基于双阵列Trie树的分词词典的改进算法-iDAT算法。iDAT算法优化了双阵列Trie树的插入效率和搜索性能。

2 双阵列Trie树

2.1双阵列Trie树

Trie Tree本质上是一个确定性的有限状态自动机,每个节点表示一个状态。 其状态根据不同的输入变量进行转移。

双阵列使用两个数组作为base []和check []来实现Trie Tree。假设输入字符为c,双阵列Trie Tree从状态s更改状态t,它适合以下条件:

base[s] c=t (1)

check[t]=s (2)

图1 双阵列Trie树结构

对于图1所示的双阵列Trie树,s和t是数组索引。输入c,状态转移到状态t,所以我们有t = base [s] c,并且检查[t] = s。 所以我们可以说,检查数组保留状态t的状态转换记录。

2.2 插入处理

假设每个状态对应一个数组索引。 对于状态s,如果base [s]和check [s]都为0,s表示空的地方(注意:当节点空闲时,可以进行检查)。 假设t1,t2 ... tn是以s开头的后缀状态,c1,c2 ... cn分别对应于输入状态转换。 base [s]由以下过程定义:

如果有一个数组base[s],其中base [s] c1 = 0,base [s] c2 = 0,... base[s] cn = 0,那么数组可以被接受, 后缀状态ti可以存储在base [s] ci中。

如果出现新的tx后缀状态,并且相应的数组为base [s] cx不是空的,那么我们需要重做上面的过程,并重新计算base [s]的值。

要确定base [s]的值,需要遍历整个数组。 base [s]的初始值通过查找空节点来确定。

2.3插入优化

为了避免从一开始就遍历空节点的数组,可以使用空状态来构建基于双链表结构的空状态序列,如下所示:

假设r1,r2 ... rcm是双阵列状态的空状态的数组索引

从上述定义,当检查值为负值时,表示该位置为空。

在基于数组的双链表结构下,我们可以通过直接遍历空节点来选择初始状态基[i]的值。

与整个阵列的遍历相比,这减少了时间。 它还使用双链表结构优化节点删除操作。

3 改进算法

与传统的Trie Tree相比,双阵列Trie Tree节省了空间。 当这个插入处理遇到冲突时,需要确定最大子前缀基值,这是花费时间的。 为了解决这个问题,我们提出了一种iDAT算法,以相同的搜索效率优化其插入时间复杂度。

3.1 iDAT的定义

我们对iDAT有以下定义:

  1. N = {n1 n2 ... nl}是基数(或检查)数组节点集,ni表示i节点,i对应数组索引,l是数组大小,l = N_Length;
  2. R = {r1 r2 ... rm}是N中的全空节点,rj是第j个空节点,m是空节点长度;
  3. T是插入状态下的最大子前缀,S = {S1 S 2 ... S k ... Ss _ length}是T的子节点字符集。 由于base [s] c = t,由遍历N创建的S set中的字符序列按升序排列。 所以我们有S kgt; Sk -1,其长度为s_length;
  4. 假设S * = {S * S * ... S * ... S * s _ length}是插入的子节点集合。 pos(s1 *)是最新插入字符s1 *的索引;
  5. 将“START”作为在集合S中插入位置的最后一个字符。由base [ri 1] = - ri,我们有START = -base [pos(s1)];

3.2 哈希表

假设哈希表的长度D = N_Length / 10,映射函数为Hash(t)= t%D。 我们使用链表来解决节点冲突。

步骤1:对于空节点计数,我们有一个临时变量tem = 0来初始化哈希表ht [D];
步骤2:双阵列字典初始化后,我们从check [0]位置遍历空节点;
步骤3:对于空节点对应的数组索引,依次进行哈希变换。
步骤4:让ht [Hash(i)] = tem; tem值增加1,这里我是当前的空数组索引。

这里count是阵列位置之前的所有空节点的总和。

3.3 跳跃算法

为了改进和加速算法,我们设计了一个跳过函数isAc-(S,START)确定是否跳过某些基数。详细的工作流程列为:

步骤1:假设s = slength - s1,s表示slength和s1之间的间隔。 所以s1的插入位置应该是START。 尝试找到是否检查[START-s]小于0.如果小于0,则该位置为空,并进入步骤2。 否则跳出来返回false;

步骤2:计算count =哈希(START) - 散列(START-s _ length)-1,这里哈希(START)是START之前的空位置号。count是Set S中的头节点和尾节点之间的空节点数。IF count lt;s _ length -2,跳出并返回false。 否则进入步骤3;

步骤3:base 0 [T] = START-S,这里base 0 [T]是base[T]的初始值。 让我们记录值并返回true/。

3.4 树的构建

方法步骤描述为:

步骤1:根据前面描述的双阵列Trie Tree优化流程初始化字典。 对于初始化的数组,我们用公式(3) - (8)构造空节点链表。 然后创建哈希表。

步骤2:假设插入字是T sx,base [T] sx不为空。 我们来检查表,并获得字符集S = {S1 S 2 ... S k ... Ss _ length},其后缀是最大子前缀T.

步骤3:将集合S做为isAccept(S,START)的输入参数。如果返回值为true,则确定base [T]的初始值,然后进入步骤4。 否则进入步骤5。

步骤4:按照iDAT算法中描述的节点插入过程。 如果找到base的初始值,我们记录pos(s1)。 否则进入步骤5。

步骤5:根据公式base [ri 1] = -ri,改变START的值,然后跳转到step3。

步骤6:如果pos(s1)为0,则按照步骤1所述更新哈希表。

跳过函数isAccept(S,START)是一种收敛算法。 其常规时间复杂度为O(1),其最坏情况复杂度为O(cm2)(这里c是连续的,m是空节点数)。 由于isAccept函数具有快速跳过和跳转的能力。 它避免了一些不必要的比较,也减少了算法的平均时间复杂度。

为了提高平均时间复杂度,我们创建一个哈希表。 它花费一些空间。 为了最小化哈希表的维护次数。 iDAT实现了从后到前的插入。

4 评估

实验尝试将我们改进的双阵列Trie Tree(iDAT)解决方案与文献[8]中提出的优化双阵列解决方案进行比较。
实验环境:CPU Core i7,内存16Gb,操作系统是window7,编程语言是Java over Eclipse。 要测试的字典是由sogou(http://www.sogou.com/)提供的开放中文词典,其中包括157201条目。 在使用双阵列Trie Tree加载测试字典后,base(check)数组大小为574464。

在构建双阵列中文字典的过程中,通过实际仿真发现,插入成功率,双数组空节点比例和插入节点数之间存在一定关系。

图2 插入成功率与插入节点号之间的关系图

图2示出了插入成功率和插入节点数之间的关系。 空闲率是阵列大小中空节点的比例。 有三个阵列空闲率,分别是3/4,2/3和1/2。 X轴是插入节点号,Y轴是成功率。 从图。 2,我们可以发现,随着闲置率的不断提高,插入成功率可能会在某些插入值下产生根本的转变。
对于插入算法,具有多个子节点的单词具有高优先级。 基于阵列的空闲率,选择在字尾分配新的空间。 这有助于跳过整个阵列的插入位置选择过程,并可以进一步提高插入算法的效率。
从仿真数据,我们发现阵列中的空闲速率约为2/3。 所以我们用红色的曲线来标记它们。 当节点数超过35时,我们在数组的末尾分配一些新的空间。

新空间的大小由子节点的映射代码范围决定。 iDAT和EDS的时间成本比较如表2所示。

表1. iDAT和EDS的时间成本比较

从表1可以看出,对于较少的插入条目,iDAT的优点是不明显的。 随着进入的增加,优化的解决方案将跳过更多的不必要的比较。 看起来更有效。
iDAT中使用的哈希表需要额外的空间成本。 仿真结果表明,当散列表的大小约为双倍阵列大小的1/10时,性能可以满足要求。 表2显示了两种方法的空间成本分析。

表2. EDS和iDAT的空间成本比较

5 总结

在本文中,我们介绍了iDAT,它是基于双阵列Trie Tree的中文分词字典的改进算法。 iDAT可实现快速机械字分割,如最大匹配或反向匹配。 搜索iDAT的时间成本与原始解决方案几乎相同。 但它比插入操作中的其他解决方案更有效。 在iDAT中也可以解决传统的Trie Tree在中文分词中的空间成本问题。 无论如何,在实际的仿真过程中,阵列的闲置率约为60%。 需要进一步研究优化空间成本的算法。

确认。 本文由数字出版技术国家重点实验室开放项目支持。

参考文献

  1. Huang, C.N.: A review of ten years of Chinese word segmentation. Journal of Chinese Information 147, 195–199 (2007)
  2. Zhao, H.Y.: A study on Chinese word segmentation based on Double-Array Trie Tree. Journal of Hunan University 22, 322–329 (2009)
  3. Zhao, C.Y.: A word segmentation method based on the word. Journal of Soochow University 18, 44–48 (2002)
  4. Chen, G.L.: An improved fast segmentation algorithm. Journal of Computer Research and Development 37, 418–424 (2009)
  5. Li, Z., Xu, Z., Tang, W.: A full two points maximum matching in Computer Engineering and

    剩余内容已隐藏,支付完成后下载完整资料


    资料编号:[25633],资料为PDF文档或Word文档,PDF文档可免费转换为Word

您需要先支付 30元 才能查看全部内容!立即支付

企业微信

Copyright © 2010-2022 毕业论文网 站点地图