图数据表示与压缩技术综述

对包含亿万个节点和边的图数据进行高效、紧凑的表示和压缩,是大规模图数据分析处理的基础.图数据压缩技术可以有效地降低图数据的存储空间,同时支持在压缩形式的图数据上进行快速访问.通过深入分析该技术的发展现状,将该技术分为基于传统存储结构的压缩技术、网页图压缩技术、社交网络图压缩技术、面向特定查询的图压缩技术4类.分别对每类技术详细分析了其代表方法并比较了它们之间的性能差异.最后对该技术进行了总结和展望.     

定序窗口布尔表达式匹配技术研究

提出了布尔表达式匹配技术，给出了算法框架，在此框架上实现了2种常用的实现方式；为了进一步增加布尔表达式的描述功能，增加了定序和窗口2个限制条件，提出了BitCount_OWBE算法，通过理论分析和实验数据证明该算法在多数情况下仍然可以达到原先的性能，从而很好地解决了上万规模的复杂规则匹配问题。     

串匹配算法中的自动机紧缩存储技术

自动机是串匹配算法中常用的数据结构,对自动机实现紧缩存储可以节省算法空间。总结常用自动机紧缩存储方法,分析其原理、时间效率、空间效率和优缺点,给出各种方法与数据稀疏性之间的关系。运用紧缩存储方法实现基本AC算法,对随机数据和真实数据的实验结果证明该算法有效。     

支持模式串动态更新的多模式匹配Karp-Rabin算法

多模式匹配算法是网络监测和内容过滤系统的核心算法,但是现有的多模式匹配算法无法实现高并发下动态更新模式串的功能。通过改进Karp-Rabin 算法,实现了多模式字符串匹配技术,实验表明多模式Karp-Rabin算法具有良好的性能。随后在多模式Karp-Rabin 算法的基础上进一步改进,使其在高并发情况下能够支持模式串动态增删功能。实验表明该算法在单个线程不断更新的条件下,随着扫描线程个数的增加,搜索速度能够保持线性增长。     

基于自动机理论的PDF文本内容抽取

现有的从PDF文档抽取文本内容的方法(如PDFBox类库采用的方法)处理速度较低,无法满足高速网络中内容分析的需求,也不能对网络中部分到达的PDF数据包进行流式的处理。为此,提出了基于自动机理论的PDF文本内容抽取方法。该方法通过建立具有层次的关键字自动机,可以快速地抽取完整PDF文档和不完整PDF文档中的文本内容。在中文和英文PDF文档数据集下的实验结果表明,基于自动机理论的PDF文本内容抽取方法耗时仅为PDFBox方法的17%~37%。