基于并行字符索引的多步长正则表达式匹配算法

深度包检测（deep packet inspection,DPI）是网络入侵检测与防御系统（network intrusion detection and prevention system,NIDPS）的核心.基于三态内容可寻址存储器（ternary content addressable memory,TCAM）的正则表达式匹配算法提高了数据包的处理速度,成为DPI技术的一个重要研究方向.TCAM具有查找速度快、存储空间小等特性,且能耗与存储空间成正比.由于DFA的存储空间开销比较大,且存储空间大小随着DFA步长数的增加而指数倍增,基于TCAM的DFA面临高能耗的问题,特别是多步长DFA.提出一种基于并行字符索引的多步长正则表达式匹配算法（multi-stride parallel character-indexed DFA,PCIDFA）,对确定型有限自动机（deterministic finite automaton,DFA）构造并行字符索引,通过比特位图取交集,减少匹配时激活的TCAM块数,显著降低TCAM能耗.实验结果表明：与多步长DFA相比,多步长PCIDFA在TCAM能耗上减少了99.8%以上,在TCAM存储空间开销上减少了48.5%-65.3%,在吞吐量上提高了1.9-2.6倍.

一种带有长度和位置约束的字符串索引方法

提出了一种基于BWT(Burrows-wheeler-transform)的字符串集合的索引方法,以解决带有匹配字符串长度和匹配子串位置约束的子串确切匹配查找问题.讨论了BWT和基于BWT索引进行确切子串查找的基本原理.分析了字符串集合、匹配字符串长度和匹配子串位置约束对原BWT索引的影响.重点解决了快速地从匹配后缀位置到字符串ID和匹配子串位置的计算问题.在3个真实的数据集上进行了比对实验,结果表明:所提出的基于BWT索引方法在没有增加原索引大小的情况下,大大提升了带有匹配字符串长度和匹配位置约束的确切子串的查找的性能,因此该算法更加适用于大规模的字符串集合的索引进行近似字符串匹配和连接.

支持快速索引的高效大数据存储结构

Trie树为处理字符串数据提供了高效的存储和索引。然而,当字符串数据很大时,利用Trie树进行数据存储会导致空间效率变得很低。因此,提出一种支持快速索引的高效大数据存储结构,称为16-bit Trie树,该结构使用16位表示子节点信息,同时用映射表帮助快速索引至指定的子节点,使得16-bit Trie树在处理大数据时仍然具有高效的空间效率。结果表明,16-bit Trie树保留了传统Trie树较高的索引速度,同时提高了其空间效率。与红黑树和B+树相比,16-bit Trie树的插入时间和空间消耗基本相同,但在索引速度上比其快了2倍左右。

字符串分段索引一次完成法

字符串分段索引一次完成法江西拖拉机发动机厂黄焕如ｄＢＡＳＥⅢ数据库中的数据是按事先设计好的输入顺序排列的，在实际工作中常常需要按某种要求重新排列，一般都采用分类（ＳＯＲＴ命令）或索引（ＩＮＤＥＸ命令）两种方法。前者将重新排列数据写入一个新的数据库，其...

一种适用于外包数据库的综合密文索引技术

外包数据库中密文索引技术的主要困难是如何减少查询结果中冗余元组的数量.目前的方案面临着查询命中率低和查询条件单一等问题.本文首先根据查询的不同要求,将数据分类,即需要执行各种模糊查询的数据和数值比较的数据.然后分别对它们建立密文索引.对于前者,通过映射函数为构成属性域的所有字符确定字符索引,从而形成一种新的基于映射的密文索引方法;对于后者,采用保序加密方法作为密文索引方法.并在此基础上,提出一种适用于外包数据库的综合密文索引技术,同时分析了该方法的有效性和安全性.最后,给出了应用于外包数据库的密文查询策略.

利用数据库的索引文件查找记录

介绍数据库索引文件的数据结构,利用数据库索引文件的数据结构设计快速查找数据库记录的程序。

基于TCAM的低能耗正则表达式匹配算法

提出一种基于字符索引的正则表达式匹配算法,对确定型有限自动机(DFA,deterministic finite automaton)的字母表和状态进行分离存储,构建字符索引,减少匹配时激活的TCAM块数,显著降低TCAM能耗。实验结果表明:与DFA相比,基于字符索引的DFA(CIDFA,character-indexed DFA)在能耗上平均减少了92.7%,在存储空间开销上平均减少了32.0%,在吞吐量上平均提高了57.9%。

基于空间压缩的外存字符串词典索引算法研究

随着大数据时代的到来,大规模的数据需要处理,其中字符串词典数据占据着越来越大的比重。现有的字符串词典索引,不是空间占用过大,就是数据的本地引用性能差,无法高效地应用到外存磁盘环境。针对这些问题,提出了一种具有高效I/O的压缩索引SB-trie,该索引不仅解决了以往索引空间占用过大的问题,同时也具有良好的本地引用性能,能够很好地工作于外存磁盘环境。实验结果表明,相比现有的索引,该索引不仅在空间上得到了有效的压缩,同时在磁盘环境下具有高效的查找性能。

基于Python的ABAQUS有限元强度折减法程序在边坡稳定性分析中的应用

强度折减法是边坡稳定性分析的主要方法之一.以ABAQUS为平台,基于ABAQUS中自带的方法(method),应用脚本语言Python编写了基于场变量的有限元强度折减法程序.通过Python语言中的文件处理方式,利用字符串索引修改关键字,完成了对模型输入文件的修改,从而可以控制场变量的变化范围,实现自动提交分析.通过工程实例讨论了二次开发中对象模型的调用流程,以及数据读取、结果输出等技术,验证了该Python脚本程序的可行性.本研究为后续Python的岩土工程仿真二次开发应用提供了借鉴.

星图识别三角形算法综述

在现代的航天领域,根据星敏感器所获得的星图分布情况,可得到飞行器的姿态。因其具有可靠性、保密性、精度高、适用范围大而得到广泛的应用。首先对传统的识别算法进行概述,然后对近年来提出的一些改进算法进行总结,并分别详细地介绍了改进三角形算法、向量索引的算法、字符串索引算法、无需标定参数识别算法、基于神经网络和支持向量机的算法。这些方法在识别速度、成功率、实时性上都有一定程度的提高,在降低虚警的情况下可以提高算法的鲁棒性,还总结了现在星敏感器识别方法的不足,并展望了今后的发展方向。