基于双阵列Trie树的汉字分割词典改进算法研究外文翻译资料
2022-11-30 16:53:57
英语原文共 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有以下定义：
- N = {n1 n2 ... nl}是基数（或检查）数组节点集，ni表示i节点，i对应数组索引，l是数组大小，l = N_Length;
- R = {r1 r2 ... rm}是N中的全空节点，rj是第j个空节点，m是空节点长度;
- T是插入状态下的最大子前缀，S = {S1 S 2 ... S k ... Ss _ length}是T的子节点字符集。 由于base [s] c = t，由遍历N创建的S set中的字符序列按升序排列。 所以我们有S kgt; Sk -1，其长度为s_length;
- 假设S * = {S * S * ... S * ... S * s _ length}是插入的子节点集合。 pos（s1 *）是最新插入字符s1 *的索引;
- 将“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％。 需要进一步研究优化空间成本的算法。
确认。 本文由数字出版技术国家重点实验室开放项目支持。
参考文献
- Huang, C.N.: A review of ten years of Chinese word segmentation. Journal of Chinese Information 147, 195–199 (2007)
- Zhao, H.Y.: A study on Chinese word segmentation based on Double-Array Trie Tree. Journal of Hunan University 22, 322–329 (2009)
- Zhao, C.Y.: A word segmentation method based on the word. Journal of Soochow University 18, 44–48 (2002)
- Chen, G.L.: An improved fast segmentation algorithm. Journal of Computer Research and Development 37, 418–424 (2009)
-
Li, Z., Xu, Z., Tang, W.: A full two points maximum matching in Computer Engineering and
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[25633]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
