基于扩展Trie树的中文敏感词变体检测

网络语言表达方式的随意性和自由性使词语变体在网页上经常出现,给网页信息安全带来了挑战。本文针对中文敏感词变体检测问题,提出一种基于扩展Trie树的敏感词变体快速检测方法。首先,对中文敏感词变体类型进行归类,结合中文敏感词特点,通过增强节点内信息和节点间联系构建扩展Trie树;再依据中文变体的生成规则检索Trie树;最后,使用基于BERT的二分类算法对结果进行二次判别,降低误检率。实验表明:该算法精准度达到98.69%,召回率达到94.25%,能够识别常见的中文敏感词变体并在时间效率上满足应用需求。

一种带改进密钥样本函数的Trie树算法

针对Trie树算法在进行字符搜索会造成内存访问效率低下等问题,提出一种带改进密钥样本函数的Trie树算法.在Trie算法中引入叶节点和分支节点,通过新的搜索方式来改善Trie树的搜索效率,以提升空间利用率,并减少Trie树的搜寻层级.通过对多个密钥词搜索结果进行对比,验证了所提出算法是科学合理的.

基于哈希和双数组trie树的多层次地址匹配算法

针对目前地址匹配算法匹配速率低、空间开销大的不足,提出了一种基于哈希和双数组trie树的多层次地址匹配算法.利用中文地址的分类、分层及组合规则,改进了地址匹配词典的构建方式,减少了词典构建的时间和空间开销.通过哈希运算,将空间坐标存储在哈希表相应的位置上,加快了空间坐标的检索效率.同时,在地址匹配的过程中,采用双向扫描及哈希运算代替传统的数据库检索方式,提高了地址匹配速率.最后,通过实验对算法的有效性进行了验证.

双数组Trie树算法优化及其应用研究

本文对双数组Trie树(Doub le-Array Trie)算法提出了一种优化策略,即在采用Trie树构造数组的过程中,优先处理分支结点数更多的结点。这种优化策略可以在保证该算法数据查找效率不变的同时,进一步减少数据稀疏,提高空间利用率。我们基于该优化算法实现了一个词典管理程序,并与利用其他索引机制的词典进行了实验对比。实验结果表明,利用优化的双数组Trie树算法的词典不仅在查询速度上优于用其他索引机制的词典,而且存储数据的空间占用也比较小。

Trie树路由查找算法在网络处理器中的实现

Trie树数据结构的实现方法灵活,所需存储器空间小,是实现高速路由查找和分组转发的理想选择。为满足10 Gb/s线速度网络处理器中微引擎的设计要求,提出一种基于最优平衡、多层存储的Trie树路由查找算法。建立一种平衡的压缩树结构,将该树中相邻的多层节点压缩到一个存储节点中。通过构造特定的数据存储结构来减小树的搜索深度,以空间换取时间,从而提高路由查找速度和分组转发效率。在网络处理器的查找微引擎设计中实现Trie路由查找算法,实验结果表明,单个微引擎的查找速度为4.4 Mb/s,能达到节省存储空间、提高查找效率的效果。

基于双数组Trie树中文分词研究

对双数组Trie树(Double-Array Trie)分词算法进行了优化:在采用Trie树构造双数组Trie树的过程中,优先处理分支节点多的结点,以减少冲突;构造一个空状态序列;将冲突的结点放入Hash表中,不需要重新分配结点.然后,利用这些方法构造了一个中文分词系统,并与其他几种分词方法进行对比,结果表明,优化后的双数组Trie树插入速度和空间利用率得到了很大提高,且分词查询效率也得到了提高.

基于多槽哈夫曼Trie树的规则引擎快速匹配算法

为了提高机场类企业数据在海量规则集合中的匹配能力,提出了基于多槽哈夫曼Trie树(MSTHTrie)的规则引擎快速匹配算法。该算法充分利用了规则点属性名数与规则条数之间的不对称特性,将对规则的线性比对转换为对多槽的并行比对,从而在稳定的空间复杂度下提高了规则引擎的匹配效率。首先对通用规则进行了严格的形式化描述,并在合理假设条件下证明了槽内规则分布命题和动作数定理;然后基于动作数定理提出了简化操作符的MSH tree算法;随之扩展操作类型提出了MSHTrie算法,使规则引擎有了普适性;最后在国内枢纽机场的业务数据上完成对比实验,表明新算法在空间复杂度上较传统线性匹配算法节约了52.6%,匹配性能上与Policytree算法相比提高了21.3%。

基于Trie树的相似字符串查找算法

基于Trie树的相似字符串查找算法是利用编辑距离的阈值来计算每个节点的活跃节点集,已有算法由于存在大量的冗余计算,导致时间复杂度和空间复杂度都比较高。针对这个问题,采用了基于活跃节点的对称性和动态规划算法的思想对已有算法进行改进,并对活跃节点集进行了修剪,提出了New-Trie-Stack算法。该算法避免了活跃节点的重复计算,以及已有算法在保存所有已遍历节点的活跃节点集时的空间开销。实验结果表明New-Trie-Stack算法在时间复杂度和空间复杂度上都有明显的下降。

基于Trie树的哈希表

受到AC算法与链式哈希的启发,提出了一种基于Trie树的哈希表。该算法通过增加一个后继状态计数器,能够为后续的查找等运算提供更加简单和快速的信息。分析与实验表明该算法具有较高的效率、较强的稳定性,且降低了能耗。

基于双数组Trie树的中文分词词典算法优化研究

基于双数组Trie树的中文分词词典具有较高的查找效率,但其插入时间复杂度较高。为此提出了一种基于双数组Trie树结构的改进算法iDAT,在原始词典初始化时优先处理分支多的节点,并在初始化之后对base数组中的空序列的下标值做Hash,Hash表中存放空序列之前的所有空序列个数之和,而后运用iDAT算法进行插入。本算法借鉴了单模式匹配的Sunday算法中的跳跃思想,在适当增加空间开销的基础上,降低了Trie树在动态插入过程中的平均时间复杂度,在实际操作过程中有着良好的性能。

基于Trie树的词语左右熵和互信息新词发现算法

由于大量新词的出现,使得中文文本分析产生了较大的困难,因此新词发现成为目前中文自然语言处理中的热点和难点问题。为此,文中提出了一种基于Trie树的词语左右熵和互信息新词发现算法。先根据成词规则,筛选掉文本中的停用词和非中文字符,将每个字与其右邻的字组成二元组;然后利用左右信息熵和互信息进行成词概率的计算,根据计算到的成词概率和词频筛选出新词;并且设计了三个实验,验证了算法的有效性和可行性。实验结果表明,该新词发现算法成词准确率较高,比其他新词发现算法时间效率有较大的提高,对于中文分词结果的优化起到重要的作用。

一种基于哈希表和Trie树的快速IP路由查找算法

Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法。论文提出了一种基于8比特的前向查找表(LFT)和7比特的简单二进制回退查找Trie树(HBT)的IP路由查找算法。算法综合考虑了IP地址的分布特点,兼顾了查找速度、存储空间利用、硬件实现,以及向IPv6过渡等几个因素。具有算法简单、查找速度较快、存储空间利用率较高、易于扩展和便于硬件实现等特点。

基于随机分布的多比特Trie树IP数据包分类算法研究

在无冲突散列算法和多比特Trie树算法的基础上,提出了一种基于随机分布的IP分类算法,该算法的核心有3点:一是基于目的/源端口和协议域构造无冲突散列,由于该三域的组合数目非常少,避免了空间爆炸;二是将目的/源IP连成比特串后分为4块,每块16bit,并将其中一块映射到一随机空间,将随机数和其余3块进行异或,获得分类索引值,并用此值生成多比特Trie树,一般情况下减小了空间和时间复杂度;三是在Trie树终点存放最终分类规则的索引值,为了保证查找到的规则的正确性,对每一个索引值的源/目的IP地址均匹配一次。通过以上3点改进一般要降低算法的时间复杂度和空间复杂度,通过仿真,当对10000条分类规则进行包分类时,该算法的包分类速度可以达到2Mpacket/s,所消耗的最大内存为1MB。

最长前缀匹配查找的索引分离trie树结构及其算法

Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法。索引分离trie树结构建立了具有k比特的一级索引,m比特的二级索引和步宽为s、最大深度为m/s的多分支trie树结构。在这种数据结构中进行最长前缀匹配查找的算法复杂度为:O(m/s+2)。它具有算法简单、查找速度快、易于更新、便于向IPv6过渡等特点,是一种综合性能较好的快速最长前缀匹配查找算法。

一种基于Trie树和扩展B树的RFID标签编码过滤方法研究

面向EPC模式(EPC Pattern)的标签编码过滤是RFID中间件的主要功能之一.为提高过滤效率,本文给出了一种基于trie树和扩展B树相结合的标签编码过滤方法.通过分析标签编码和EPC模式的结构特征,将系统中大量的EPC模式构造成一个层次查找结构,对于EPC模式中的常规编码段采用trie树表达,对于区间形式采用扩展B树表达.查找过程按照编码段由高至低依次进行,并采用了基于位向量集合的优化方法.实验表明标签编码过滤效率受EPC模式数量变化的影响较小,能够有效降低向上层应用传输数据的延迟.

基于无冲突哈希Trie树的IP分类算法的研究

随着计算机网络的快速发展,IP分类算法被广泛地应用于路由器、防火墙和流量计费等软件中。本文在基于无冲突哈希Trie树的快速IP分类算法的基础上给出了一组哈希函数,进一步增强了算法的灵活性。

双数组Trie树索引的可操作性研究

双数组是组织和实现Trie树的一种数据结构。双数组Trie树索引实现的是一种线性时间复杂度的搜索机制,因此被广泛的应用于信息检索和中文分词等领域。然而双数组Trie树索引建立后不易于更新,限制了这种索引的现实应用。在前人的双数组Trie树优化索引构造的基础上,分析了插入和删除操作的所有可能情况,提出了对双数组Trie树索引进行相关操作的算法。最后分析了其时间和空间开支,并用实验结果证明了其可行性。

网络安全态势感知中Trie树关键词高速匹配算法研究

海量数据中关键词高速检索对增强网络安全态势感知系统反应速度,提高系统整体效率和安全性具有重要意义。基于双数组Trie树的网络信息检索算法具有较高的查找效率,但其插入时间复杂度较高,同时叶子结点占用了大量存储空间。为此,文章提出一种基于叶子结点压缩存储的双数组Trie树构造方法,按层次遍历Trie树,将分枝结点存储在基本双数组中,对叶子结点进行压缩后以位图形式存储于压缩数组中。该方法在保留双数组Trie树查询性能的同时,一定程度上提高了插入效率,改善了存储空间利用效率。

基于Trie树和有限状态自动机的中文地址解析模型

目前,无论是在研究或者是商业领域中,中文地址解析都没有一个成熟的模型结果。要素识别是地址解析的关键技术,传统的地址要素识别是基于特征词和字典匹配的方法,难以解决地址命名的多样性问题。利用自然语言处理技术,根据Trie树模型对行政区域寻址的方法和有限状态自动机模型对非规范地址的要素提取方法,本文提出T-FA模型对地址进行分级划分。其中,采用隐马尔可夫模型的切词方法和最长公共子序列算法,可以解决地址要素识别的模糊化搜索。T-FA模型具有良好的泛化能力,在批量处理地址时具有很好的通用效果,能比较有效地解决中文地址多样化的解析难题。

一种基于哈希表和Trie树的快速内容路由查找算法

内容分发网络CDN(Content Delivery Network)是一个建立并覆盖在互联网之上的一层特殊网络,专门用于通过互联网高效传递丰富的多媒体内容。与传统的网络一样,要求核心路由器每秒能转发几百万个以上的分组,而实现高速分组转发的关键是路由表的组织和快速的路由查找算法。首先概述了内容路由网络的背景,罗列出了几种常见的路由查找算法,并在此基础上,引入基于Hash和Trie树的路由查找算法,最后在试验的基础上对平均查找时间、平均查找次数以及最大匹配次数进行了比较分析,试验结论显示该算法缩短了查找时间,提高了系统性能。