通配符用于模糊查找的算法

操作系统及一些工具软件中,常见使用通配符。“*”和“?”进行文件名的简化输入、模糊查找的事例。“*”可匹配于任何字符串,“?”可匹配于任一字符。在适当地方加以使用,可以省去用户记忆和输入大量字符,从而减少出错和增加用户界面的友好性。在应用软件中,也可将通配符用于模糊查询中。用户输入的字符串(检索串)可在任意位置加入任意个通配符,由系统(程序)查找与其含义相符的内部字符串(目标串)。为阐明算法,暂且撇开语义,讨论形式化的字符串。     

在FOXBASE中使用通配符

DOS命令中,允许使用通配符“*”、“?”,给操作带来很大方便。FOXBASE中,同样也需要使用通配符。如人员档案管理系统中,用户只记得某人姓“王”,查询很难实现,模糊查询及代码处理中也经常遇到这类问题。能否让FOXBASE也支持通配符呢?我们设计了一字符串匹配函数,可以解决这一问题。该函数程序名为LIKE.PRG,可象内部函数一样供程序或命令直接调用。调用时需要二个参数C、S,其中C为字符串框架,可包含*或?,而S为一字符串、变量或字段。若C中不含通配符,仅当C=S时该函数返回.T.;否则按     

支持块编辑距离的索引结构

在近似字符串匹配中,传统的编辑距离不能很好地衡量诸如人名、地址等数据的相似关系,而块编辑距离可以很好地衡量两个字符串的相似性.如何有效地支持块编辑距离,进行近似字符串查询处理具有重要的意义.计算两个字符串的块编辑距离是一个NP完全问题,因此希望提供有效的方法可以增强过滤能力,并减少假通过率.设计了一种支持移动编辑距离的新颖的索引结构SHV-Trie,通过研究移动编辑距离的操作特性,使用字母出现的频率作为支持移动编辑距离操作的一个下界,并且提出相应的查询过滤算法,同时,针对索引SHV-Trie的空间开销过大的问题,提出一种优化字母排列的索引结构和一种压缩的索引结构及相关查询过滤算法.真实数据集上的实验结果与分析显示了所提出的索引结构具有良好的过滤能力,并通过减少效率假通过率提高查询的效率.     

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

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

基于Trie结构的带通配符的相似字符串匹配算法

提出了一种新的相似字符串查询的方法。其目的在于提高基于相似字符串匹配的查询在大规模字符串数据库中的查询效率，并且提供带通配符的字符串查询方式。该方法使用Trie数据结构组织数据库中的数据，使用基于编辑距离的相似字符串匹配方法，在Trie数据结构中进行高效的匹配和查询，得到K相似度下的候选词集。实验证明，本方法在K≤2时具有相当高的查询效率。     

支持局部最优化匹配的近似子串查询算法

基于编辑距离的字符串近似查询算法一般是先给定阈值k,然后计算那些与查询串的编辑距离小于或等于k的结果。但是对于近似子串查询,结果中有很多是交叠的,并且是无意义的,于是提出了一种局部最优化匹配的概念,只计算那些符合阈值条件,并且是局部最优的结果,这样不仅避免了结果的交叠,而且极大节省了时间开销。给出了支持局部最优化匹配的近似子串查询的定义,相应提出了一种基于gram索引的局部最优化近似子串查询算法,分析了子串近似匹配过程中的规律,研究了基于局部最优化匹配的边界限定和过滤策略,给出了一种过滤优化的局部最优化近似子串查询算法,提高了查询效率。     

一个简单实用的字符串匹配函数

FoxBASE不支持通配符,给程序设计带来很大困难。如数据库查询、字符串处理等。为此,我们利用自定义函数设计了一字符串匹配函数;LIKE(C,S)。其中C为字符串框架,可含通配符*,?;S可为字符串、变量或字段。若C与S匹配,该函数返回.T.,否则.F.。该函数可像     

一种新的基于Dewey编码的XML路径索引

建立高效的索引来快速定位满足要求的节点是提高XML数据查询效率的一个必要手段.文中以降低复杂度和提高查询效率为目标,以基于路径的XML索引原理为基础,提出了一种新型的基于Dewey编码的索引结构RTL-Index.RTL-Index通过对文档节点编码来表示结构信息,利用前缀路径匹配操作完成结构查询,支持含通配符" 和后代轴"//"的查询以及兄弟节点无序的模式树的查询.仿真实验结果表明RTL-Index索引具有较低的时间和空间复杂度,解决了XML文档分支路径查找问题,是一种较为有效的XML索引结构.     

支持快速查询的数据库加密方法研究

为了解决数据库中加密字符串数据的查询问题。提出了为待加密的字段建立辅助索引字段的两阶段查询方法。索引字段的内容由原始数据的划分值和特征值两部分组成，它可以用来支持字符串数据的精确匹配查询和模糊匹配查询。查询加密数据时，首先利用索引字段对加密数据进行一次粗糙查询，然后在解密的数据上再进行一次精确查询。实验表明，其性能较传统的先解密后查询方法有较大的提高。     

外存中高效的字符串相似性查询处理

字符串相似性查询是众多应用的基础操作,如数据清洁、拼写校验、生物信息学和信息集成等。随着数据的爆炸性增长,大规模字符串数据日益普遍,现代的信息系统中也广泛使用字符串作为数据的表达形式。现有支持字符串相似性查询的方法大多是基于q‐g ram的内存倒排索引,在处理大规模字符串集合会消耗无法忍受的内存容量,甚至在数据量过大时造成内存容量不足而无法支持查询处理。现有的外存倒排索引Behm‐Index在查询的过滤阶段只支持少数过滤器,不能有效地减少查询I/O代价。提出了LPA‐Index ：一种支持长度过滤器和位置过滤器的外存倒排索引,并通过选择查询时使用的倒排表来有效地降低查询I/O代价。实验结果表明,与现有性能最好的外存索引Behm‐Index相比,LPA‐Index能够大幅降低查询的I/O代价,获得了更短的查询响应时间。     

gStore: a graph-based SPARQL query engine

We address efficient processing of SPARQL queries over RDF datasets. The proposed techniques, incorporated into the gStore system, handle, in a uniform and scalable manner, SPARQL queries with wildcards and aggregate operators over dynamic RDF datasets. Our approach is graph based. We store RDF data as a large graph and also represent a SPARQL query as a query graph. Thus, the query answering problem is converted into a subgraph matching problem. To achieve efficient and scalable query processing, we develop an index, together with effective pruning rules and efficient search algorithms. We propose techniques that use this infrastructure to answer aggregation queries. We also propose an effective maintenance algorithm to handle online updates over RDF repositories. Extensive experiments confirm the efficiency and effectiveness of our solutions.     

Structure and attribute index for approximate graph matching in large graphs

The increasing popularity of graph data in various domains has lead to a renewed interest in developing efficient graph matching techniques, especially for processing large graphs. In this paper, we study the problem of approximate graph matching in a large attributed graph. Given a large attributed graph and a query graph, we compute a subgraph of the large graph that best matches the query graph. We propose a novel structure-aware and attribute-aware index to process approximate graph matching in a large attributed graph. We first construct an index on the similarity of the attributed graph, by partitioning the large search space into smaller subgraphs based on structure similarity and attribute similarity. Then, we construct a connectivity-based index to give a concise representation of inter-partition connections. We use the index to find a set of best matching paths. From these best matching paths, we compute the best matching answer graph using a greedy algorithm. Experimental results on real datasets demonstrate the efficiency of both index construction and query processing. We also show that our approach attains high-quality query answers.     

Pattern Matching with Flexible Wildcards

Pattern matching with wildcards (PMW) has great theoretical and practical significance in bioinformatics, information retrieval, and pattern mining. Due to the uncertainty of wildcards, not only is the number of all matches exponential with respect to the maximal gap flexibility and the pattern length, but the matching positions in PMW are also hard to choose. The objective to count the maximal number of matches one by one is computationally infeasible. Therefore, rather than solving the generic PMW problem, many research efforts have further defined new problems within PMW according to different application backgrounds. To break through the limitations of either fixing the number or allowing an unbounded number of wildcards, pattern matching with flexible wildcards (PMFW) allows the users to control the ranges of wildcards. In this paper, we provide a survey on the state-of-the-art algorithms for PMFW, with detailed analyses and comparisons, and discuss challenges and opportunities in PMFW research and applications.     

3D-List: a data structure for efficient video query processing

A video query model based on the content of video and iconic indexing is proposed. We extend the notion of two-dimensional strings to three-dimensional strings (3D-Strings) for representing the spatial and temporal relationships among the symbols in both a video and a video query. The problem of video query processing is then transformed into a problem of three-dimensional pattern matching. To efficiently match the 3D-Strings, a data structure, called 3D-List, and its related algorithms are proposed. In this approach, the symbols of a video in the video database are retrieved from the video index and organized as a 3D-List according to the 3D-String of the video query. The related algorithms are then applied on the 3D-List to determine whether this video is an answer to the video query. Based on this approach, we have started a project called Vega. In this project, we have implemented a user friendly interface for specifying video queries, a video index tool for constructing the video index, and a video query processor based on the notion of 3D-List. Some experiments are also performed to show the efficiency and effectiveness of the proposed algorithms     

路径分区编码优化小枝查询

有效地存储查询XML文档已经成为当今数据库领域的研究热点。从XML文档的路径统计出发,提出了路径分区存储编码方案,并依此消除了小枝查询的后裔边和通配符。针对这类不含//和*的小枝查询,利用路径分区编码的特性,给出了基于结构约束节点的Twig查询算法,极大地减少了结构连接次数。实验表明,该算法能有效滤除无关元素,提高小枝查询效率。     

带任意长度通配符的模式匹配

基因序列中,许多病毒并不是简单的直接复制自己,而是相邻字符间插入或者删除序列片段,如何从序列数据中检索这些病毒具有重要的研究价值.提出了一个更普遍的问题,带任意长度通配符的模式匹配问题(Pattern matching with arbitrary-length wildcards,PMAW),这里模式中不仅可以有多个通配符约束,而且每个通配符的约束可以是两个整数,也可以从整数到无穷大.给定序列S和带通配符的模式P,目标是从S中检索P的所有出现和每一次出现的匹配位置,并且要求任意两次出现不能共享序列中同一位置.为了有效地解决该问题,设计了两个基于位并行的匹配算法MOTW (Method of ocurrence then window)算法和MWTO (Method of window then ocurrence)算法.同时,MWTO算法进行细微改动就可以满足全局长度约束.实验结果既验证了算法求解问题的正确性,又验证了比相关的模式匹配算法具有更好的时间性能.     

一种带稀疏间隙约束的并行模式匹配算法

带通配符的模式匹配是一个经典的研究问题,带有可变间隙约束的模式匹配是近年来比较热门的研究方向.为适应某些查询精度要求较高的应用领域,提出一种在稀疏间隙约束条件下求解模式匹配完备解的算法SGPM-SAI（pattern matching with sparse gaps constraint based on suffix automaton index）.SGPM-SAI通过对文本串预处理,建立一种称为W-SAM的图索引结构,然后对模式串分段查找EndPos集合,最后以集合归并求交的方法得到模式匹配的完备解.实验结果表明：在不考虑预处理时间的情况下,相比几种最典型的模式匹配算法（KMP,BM,AC,suffix array）,SGPM-SAI算法性能优势显著,至少高出3~5倍.通过与SAIL算法的最新优化版本（SAIL-Gen）进行比较,在稀疏间隙约束条件下,SGPM-SAI的性能要显著优于SAIL-Gen算法.此外,为有效利用现代处理器的大规模并行处理单元,提出了并行优化后的算法Parallel SGPM-SAI.实验结果表明：Parallel SGPM-SAI算法的加速效果显著,且具有良好的并行可扩展性,能够充分利用现代众核处理器的高并行计算优势.     

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

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