利用关键因子过滤的正则表达式匹配算法

正则表达式(regular expression,RE)是一种能够提供复杂查询能力的技术,其通过特定的语法结构来描述一类文本的共同特征。正则表达式强大的表达能力和简洁的语法,使得其在各个领域都被广泛地应用。为了提高正则表达式的匹配效率,提出了一种利用关键因子进行过滤的匹配技术,关键因子指的是在文本中具有最小出现频率的有效过滤因子。由于实际文本中字符并不是均匀分布的,子串在文本中出现频率的差异将影响过滤因子的过滤能力。通过考虑有效过滤因子在文本中出现的频率,关键因子能获得更好的过滤能力。提出了利用正则表达式的划分来求取关键因子的算法,进而通过关键因子来过滤候选位置。通过在真实的蛋白序列和英文文本上进行实验,说明了基于关键因子过滤的匹配方法可以有效地提升正则表达式的匹配性能。     

维文领域本体组合词概念分类关系提取

针对维文黏着语的特点和广义后缀树提取概念间分类关系时后缀树中出现非概念词的问题,提出一种改进的基于广义后缀树的维文领域本体组合词概念分类关系提取算法。该算法首先对维文领域本体组合词概念构建广义后缀树,先序遍历广义后缀树,对叶子节点存储的后缀词进行维文词干提取,删除非概念词所在叶节点,合并经维文词干提取后表示相同概念的叶节点,实现广义后缀树的剪枝;进而自动提取组合词概念分类关系。实验表明,与传统的基于广义后缀树的概念分类关系提取算法相比,准确率、召回率都得到了提高。     

基于邻居向量的近似子图匹配

将近似子图匹配分成节点匹配和边匹配两个阶段。将数据图中所有节点的h-邻居节点表示成向量形式,采用一种启发式推理算法进行节点匹配得到节点对应关系,使用查询节点权重提高匹配相似度,使用节点过滤、索引技术和孤立候选节点提高运算效率;利用邻居向量索引得到匹配节点集合的扩展图,进行边匹配,得到匹配图。在真实数据上进行实验,实验结果表明,该算法效果较好,运算效率较高,可以应用于节点标签稀疏的情况和top-k近似匹配。     

基于正则表达式构建学习的网页信息抽取方法

正则表达式作为信息抽取领域中的一种常用方法已经被广泛应用多年。然而构建高质量并且复杂度较高的正则表达式通常需要耗费大量人工成本,为此,提出一种基于正则表达式状态转换的算法来学习复杂正则表达式的构建过程。该算法需要给定输入初始正则以及正反例样本,初始正则表达式在经过析取分离与合并交叉两大类正则表达式状态转换之后,得到候选正则表达式集合,利用F值评估候选项的信息抽取效果,通过贪心的启发式策略选择一个最优正则表达式作为输出。在多种数据集上对算法进行测评。实验表明,该算法性能与准确度均优于常规的机器学习方法。尤其在较小规模训练集和跨数据集上依然有较好的效果。     

基于哈希特征的大规模图像快速匹配算法

针对基于图像进行三维重建技术在使用大规模图像集合进行重建时,需要对图像集合中图像进行两两匹配耗时问题,提出了基于哈希技术对图像构建全局哈希特征的方法,通过过滤掉无效的图像关系对来减少计算时间,极大地提高了大规模图像集合三维重建的匹配计算效率。提出的大规模图像快速哈希匹配算法包括构建图像哈希特征、构建初始匹配图、挑选候选匹配对、哈希匹配几个步骤。实验结果表明该方法能显著地提高三维重建中图像匹配的速度。     

基于广义后缀树的二分网络社区挖掘算法

近年来,二分网络的社区挖掘问题得到了极大的关注。提出了一种基于广义后缀树的二分网络社区挖掘算法。首先从二分网络的邻接矩阵中提取网络中每个节点的链接节点序列,然后构建广义后缀树。广义后缀树的每个节点表示二分网络的一个完全二分团,由此获取并调整完全二分团。通过引入二分团的紧密度得到初始的社区划分,最后再对孤立点进行处理以得到最终的社区划分。所提算法不仅能发现重叠社区,而且能得到一对多关系的社区。在人工数据集和真实数据集上的实验表明,所提算法能准确地识别二分网络中的社区个数,获得很好的划分效果。     

基于改进的Trie树和DFA的敏感词过滤算法

通过对文本内容中敏感词过滤方法及相关技术的研究,提出了一种基于改进的Trie树和DFA的敏感词过滤算法,解决了敏感词过滤技术中的人工干扰、分词障碍等关键问题,提高了文本中敏感词过滤的准确性和有效性.提出的算法包括三个步骤:基于排列组合的数学原理对中文词向中拼混合词进行扩充;采用改进的Trie树结构来存储DFA的所有状态,构建敏感词树;根据构建的敏感词树结构以及采用最小匹配规则对文本内容中的敏感词进行检测和过滤.通过分析得到构建敏感词树算法的时间复杂度为O(n×len),敏感词检测及过滤算法时间复杂度为O(L).实验结果表明,本算法其查准率为100％,查全率约为87％～100％.     

一种面向专利摘要的领域术语抽取方法

专利领域中术语抽取结果的好坏决定了本体构建的质量。提出一种自动生成过滤词典并结合词汇密集度等影响因子的术语抽取方法。首先在分词和词性标注的基础上,对文献匹配词性规则算法生成的模板得到候选长术语和单词型短术语集合,然后利用文档一致度生成的过滤词典过滤部分候选长术语集,最后针对长术语的构成特点,将词汇密集度、文档差比、文档一致度三个术语因子加权平均作为整个长术语的术语权重值,并按值高低排序。在8000篇专利摘要文献的基准语料上进行实验,随机选取五组实验数据,平均准确率达到86%。结果表明该方法在领域术语抽取方面是行之有效的。     

基于winpcap的网络抓包系统

为了监控计算机当前网络信息,我们主要通过使用winpcap抓取当前计算机网络中使用的数据包,然后通过对抓取数据包中数据进行分析过滤,得到所抓数据包的协议、数据长度,以及http中的数据报内容等信息。此外,我们的项目还注重研究,主要体现在应用层协议的识别方面,同时采用了基于正则表达式技术得到某种应用层协议的特征表达式,然后通过利用正则表达式匹配引擎进行识别。     

基于不变矩和小波分析的指横纹匹配新算法

为了有效提高刑侦过程中采集到的指横纹匹配的准确率和效率,提出一种基于修正不变矩和小波多分辨率分析的指横纹特征提取和匹配算法。该方法在一次识别阶段,为克服比例因子和旋转角度对矩的影响,提出最小矩形的求矩区域修正方法并对由Radon投影得到的不变矩特征矩阵进行初等行变换确定旋转角度,从而建立候选图像集合。在二次识别阶段,利用小波多分辨率分析对候选图像集合的确定角度Radon投影进行分析,再由得到的加权不变矩特征向量进行最高相似度匹配。实验结果表明,该方法较传统方法有更好的识别率。     

基于后缀树模型的文本实时分类系统的研究和实现

本文在面向网络内容分析的前提下,提出了一种基于后缀树的文本向量空间模型(VSM) ,并在此模型之上实现了文本分类系统。对比基于词的VSM,该模型利用后缀树的快速匹配,实时获得文本的向量表示,不需要对文本进行分词、特征抽取等复杂计算。同时,该模型能够保证训练集中文本的更改,对分类结果产生实时影响。实验结果和算法分析表明,我们系统的文本预处理的时间复杂度为O(N) ,远远优于分词系统的预处理时间复杂度。此外,由于不需要分词和特征抽取,分类过程与具体语种无关,所以是一种独立语种的分类方法。     

A Linear Time Lower Bound on McCreight and General Updating Algorithms for Suffix Trees

Suffix trees are the fundamental data structure of combinatorial pattern matching on words. Suffix trees have been used in order to give optimal solutions to a great variety of problems on static words, but for practical situations, such as in a text editor, where the incremental changes of the text make dynamic updating of the corresponding suffix trees necessary, this data structure alone has not been used with success. We prove that, for dynamic modifications of order O(1) of words of length n, any suffix tree updating algorithm, such as the ones proposed by McCreight, requires O(n) worst-case running time, as for the full reconstruction of the suffix tree. Consequently, we argue that this data structure alone is not appropriate for the solution of combinatorial problems on words that change dynamically.     

面向互联网新闻的在线事件检测

为了提高互联网上新闻事件在线检测的效率,利用加窗策略、命名实体识别及后缀树聚类等技术提出了一种新的检测算法.该算法基于实体识别技术解析出新闻数据特有的信息元素(例如日期、地点、人物等),并在限定的时间窗口内,通过新闻特征的语义匹配实现了新事件的快速识别,从而大幅降低了基于文本相似度计算的检测算法带来的巨大时间消耗.实验结果证明,该算法能够实现在保障检测准确率的同时显著提高检测的效率.     

q-gram matching using tree models

q-gram matching is used for approximate substring matching problems in a wide range of application areas, including intrusion detection. In this paper, we present a tree-based model to perform fast linear time q-gram matching. All q-grams present in the text are stored in a tree structure similar to trie. We use a tree redundancy pruning algorithm to reduce the size of the tree without losing any information. We also use suffix links for fast q-gram search during query matching. We compare our work with the Rabin-Karp-based hash-table technique, commonly used for multiple q-gram search. We present results of experiments on system call sequence data used for intrusion detection.     

基于后缀树的带有通配符的模式匹配研究

由于在生物序列分析、文本索引、网络入侵检测等领域的应用需求,带有通配符的模式匹配问题一直是研究 的热点。针对已有的研究工作中通配符和长度约束具有较强的局限性问题,研究带有灵活通配符的模式匹配问题,其 中通配符可以在模式的任意两子串间出现且可以指定灵活的长度约束。采用非线性数据结构—后缀树,设计了求 解模式所有解的完备算法PAS"I'。预处理阶段采用在线增量式算法构建具有文本先验知识的后缀树,搜索阶段结合 动态规划的思想,逐个匹配模式中字符,最终得到完备解。在基因序列上的实验表明,PAST比其他算法具有更好的 时间性能。     

连续时间区间内的频繁词序列挖掘算法

查询文本中频繁出现的短语可快速掌握文本内容,然而传统频繁词序列挖掘算法面向挖掘任务时的时间复杂度较高,无法满足频繁更换查询条件及快速获得反馈的查询需求。利用基于频率树的快速频繁词序列挖掘算法（TS_Mining）,在保持后缀树线性构造时间的情况下实现文本集合中频繁词序列的查询,并采用树型索引结构避免多次扫描文本集合,降低算法时间复杂度。针对连续时间区间内的频繁词序列查询问题,提出改进的剪枝挖掘算法（TS_Pruning）,通过减少频率树的扫描范围进一步提高挖掘效率。实验结果表明,TS_Mining与TS_Pruning算法的运行时间相比经典Apriori挖掘算法约减少了2个数量级,具有更高的频繁词序列挖掘效率。     

基于后缀树的骨干网络垃圾邮件检测方法

虽然目前垃圾邮件过滤或检测的研究比较多,但是它们大多数是基于邮件客户端。文章提出了一种基于后缀树的骨干网络垃圾邮件检测方法,它采用后缀树文本表示方法,通过不定长统计方法判定邮件是否相似,然后利用邮件重复出现的次数判定是否为垃圾邮件。该方法不需要任何训练,直接对接收的邮件进行分类统计;对于长度为的邮件,算法的时间复杂度和空间复杂度均为;另外,该方法独立于任何语种。     

大型网络中近似子图匹配研究

为降低噪声对近似子图匹配准确率的影响,提出一种改进的近似子图匹配方法。在预处理阶段,利用k-近邻顶点集为数据图中的每个顶点建立标签-权重向量索引。在查询过程中,基于单个近邻标签的权重距离和所有近邻标签的整体匹配程度进行两级过滤,生成顶点候选集,采用生成树匹配和图匹配的方式确定查询图在大型网络中的位置。在真实数据集上的实验结果表明,该方法具有较高的执行效率和匹配准确率。     

基于匹配区域特征的相似字符串匹配过滤算法孙德才

相似字符串匹配过滤算法因其适合大库查找而被广泛应用,为通过提高过滤算法的过滤效率加快匹配速度,提出一种基于匹配区域特征的过滤算法.该算法将模式串和文本串分割成固定长度为kq+1的逻辑块,并从各块中提取了2个新的匹配区域特征:q-gram命中的均匀性和q-gram有效命中的区域性.新算法利用这些新特征优化了传统过滤标准,提高了算法的过滤效率;并改进了QUASAR中基于分块策略的过滤区确定方案.实验结果表明,新算法与改进前相比有效地加快了匹配速度,尤其在误差率较小时改进效果更佳.     

基于术语编码和树匹配的构件检索方法研究

在研究和分析已有编码和树匹配检索方法的基础上,给出了一种基于术语编码和树匹配的改进方法。通过对构件库中的术语进行编码来建立索引,依据树匹配思想计算构件的匹配代价和匹配度,按照匹配代价排序检索结果,最后根据匹配度要求提取并输出符合要求的构件。实验表明,该方法在保证较高查全率的基础上,能够有效提高构件的查准率。