Trie+结构函数式建模、机械化验证及其应用

Trie结构是一种使用搜索关键字来组织信息的搜索树,可用于高效地存储和搜索字符串集合.Nipkow等人给出了实现Trie的Isabelle建模与验证,然而其Trie在存储和操作时存在大量的冗余,导致空间利用率不高,且仅考虑英文单模式下查找.为此,基于索引即键值的思想提出了Trie+结构,相较于传统的索引与键值分开存储的结构能减少50%的存储空间,大大提高了空间利用率.并且,对Trie+结构的查找、插入、删除等操作给出了函数式建模及其严格的机械化验证,保证操作的正确性和可靠性.进一步,提出一种匹配算法的通用验证规约,旨在解决一系列的匹配算法正确性验证问题.最后,基于Trie+结构与匹配算法通用验证规约,建模和验证了函数式中英文混合多模式匹配算法,发现并解决了现有研究中的基于完全哈希Trie的多模式匹配算法的模式串前缀终止的Bug.该Trie+结构以及验证规约在提高Trie结构空间利用率和验证匹配算法中,有一定的理论和应用价值.

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

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

Lightweight Res-Connection Multi-Branch Network for Highly Accurate Crowd Counting and Localization

Crowd counting is a promising hotspot of computer vision involving crowd intelligence analysis,achieving tremendous success recently with the development of deep learning.However,there have been stillmany challenges including crowd multi-scale variations and high network complexity,etc.To tackle these issues,a lightweight Resconnection multi-branch network(LRMBNet)for highly accurate crowd counting and localization is proposed.Specifically,using improved ShuffleNet V2 as the backbone,a lightweight shallow extractor has been designed by employing the channel compression mechanism to reduce enormously the number of network parameters.A light multi-branch structure with different expansion rate convolutions is demonstrated to extract multi-scale features and enlarged receptive fields,where the information transmission and fusion of diverse scale features is enhanced via residual concatenation.In addition,a compound loss function is introduced for training themethod to improve global context information correlation.The proposed method is evaluated on the SHHA,SHHB,UCF-QNRF and UCF_CC_50 public datasets.The accuracy is better than those of many advanced approaches,while the number of parameters is smaller.The experimental results show that the proposed method achieves a good tradeoff between the complexity and accuracy of crowd counting,indicating a lightweight and high-precision method for crowd counting.

Multi-Branch Fault Line Location Method Based on Time Difference Matrix Fitting

The distribution network exhibits complex structural characteristics,which makes fault localization a challenging task.Especially when a branch of the multi-branch distribution network fails,the traditional multi-branch fault location algorithm makes it difficult to meet the demands of high-precision fault localization in the multi-branch distribution network system.In this paper,the multi-branch mainline is decomposed into single branch lines,transforming the complex multi-branch fault location problem into a double-ended fault location problem.Based on the different transmission characteristics of the fault-traveling wave in fault lines and non-fault lines,the endpoint reference time difference matrix S and the fault time difference matrix G were established.The time variation rule of the fault-traveling wave arriving at each endpoint before and after a fault was comprehensively utilized.To realize the fault segment location,the least square method was introduced.It was used to find the first-order fitting relation that satisfies the matching relationship between the corresponding row vector and the first-order function in the two matrices,to realize the fault segment location.Then,the time difference matrix is used to determine the traveling wave velocity,which,combined with the double-ended traveling wave location,enables accurate fault location.

Multi-Branch Deepfake Detection Algorithm Based on Fine-Grained Features

With the rapid development of deepfake technology,the authenticity of various types of fake synthetic content is increasing rapidly,which brings potential security threats to people’s daily life and social stability.Currently,most algorithms define deepfake detection as a binary classification problem,i.e.,global features are first extracted using a backbone network and then fed into a binary classifier to discriminate true or false.However,the differences between real and fake samples are often subtle and local,and such global feature-based detection algorithms are not optimal in efficiency and accuracy.To this end,to enhance the extraction of forgery details in deep forgery samples,we propose a multi-branch deepfake detection algorithm based on fine-grained features from the perspective of fine-grained classification.First,to address the critical problem in locating discriminative feature regions in fine-grained classification tasks,we investigate a method for locating multiple different discriminative regions and design a lightweight feature localization module to obtain crucial feature representations by augmenting the most significant parts of the feature map.Second,using information complementation,we introduce a correlation-guided fusion module to enhance the discriminative feature information of different branches.Finally,we use the global attention module in the multi-branch model to improve the cross-dimensional interaction of spatial domain and channel domain information and increase the weights of crucial feature regions and feature channels.We conduct sufficient ablation experiments and comparative experiments.The experimental results show that the algorithm outperforms the detection accuracy and effectiveness on the FaceForensics++and Celeb-DF-v2 datasets compared with the representative detection algorithms in recent years,which can achieve better detection results.

Wireless Interference Classification with Low Complexity Multi-Branch Networks

In non-cooperative communication systems,wireless interference classification(WIC)is one of the most essential technologies.Recently,deep learning(DL)based WIC methods have been proposed.However,conventional DL-based WIC methods have high computational complexity and unsatisfactory accuracy,especially when the interference-tonoise ratio(INR)is low.To this end,we propose three effective approaches.Firstly,we introduce multibranch convolutional neural networks(CNNs)for interference recognition.The multi-branch CNN is constructed by repeating a layer that aggregates several transformations with the same topology,and it notably improves the recognition ability for WIC.Our design avoids the carefully crafted selection of each transformation.Unfortunately,multi-branch CNNs are computationally expensive and memory-inefficient.To this end,we further propose Low complexity multibranch networks(LCMN),which are mathematically equivalent to multi-branch CNNs but maintain low computing costs and efficient inference.Thirdly,we present novel loss function,which encourages networks to have consistent prediction probabilities for samples with high visual similarities,resulting in increasing recognition accuracy of LCMN.Experimental results demonstrate the proposed methods consistently boost the classification performance of WIC without substantially increasing computational overhead compared to traditional DL-based methods.

Proppant transport law in multi-branched fractures induced by volume fracturing

To further clarify the proppant transport and placement law in multi-branched fractures induced by volume fracturing, proppant transport simulation experiments were performed with different fracture shapes, sand ratios, branched fracture opening time and injection sequence of proppants in varied particle sizes. The results show that the settled proppant height increases and the placement length decreases in main fractures as the fracturing fluid diverts gradually to the branched fractures at different positions. The flow rate in branched fractures is the main factor affecting their filling. The diverion to branched fractures leads to low flow rate and poor filling of far-wellbore branched fractures. The inclined fracture wall exerts a frictional force on the proppant to slow its settlement, thus enhancing the vertical proppant distribution in the fracture. The increase of sand ratio can improve the filling of near-wellbore main fracture and far-wellbore branched fracture and also increase the settled proppant height in main fracture. Due to the limitation of fracture height, when the sand ratio increases to a certain level, the increment of fracture filling decreases. When branched fracture is always open(or extends continuously), the supporting effect on the branched fractures is the best, but the proppant placement length within the main fractures is shorter. The fractures support effect is better when it is first closed and then opened(or extends in late stage) than when it is first opened and then closed(or extends in early stage). Injecting proppants with different particle sizes in a specific sequence can improve the placement lengths of main fracture and branched fracture. Injection of proppants in an ascending order of particle size improves the near-wellbore fracture filling, to a better extent than that in a descending order of particle size.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于LE-Trie的防火墙策略检测算法

防火墙策略是一系列具体的规则集合,策略的制定对防火墙功能的发挥至关重要,不能存在异常情况。为此,研究基于惰性展开的Trie数据结构,利用LE-Trie结构存储规则表,提出一种防火墙策略的冲突检测与消除算法。仿真结果表明,与使用普通Trie结构的算法相比,该算法具有更高的执行效率。

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

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

基于Trie树的哈希表

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

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

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

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

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

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

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