Space Efficient Dynamic Orthogonal Range Reporting

In this paper we present new space efficient dynamic data structures for orthogonal range reporting. The described data structures support planar range reporting queries in time O(log n+klog log (4n/(k+1))) and space O(nlog log n), or in time O(log n+k) and space O(nlog  ^ε n) for any ε>0. Both data structures can be constructed in O(nlog n) time and support insert and delete operations in amortized time O(log ² n) and O(log nlog log n) respectively. These results match the corresponding upper space bounds of Chazelle (SIAM J. Comput. 17, 427–462, 1988) for the static case. We also present a dynamic data structure for d-dimensional range reporting with search time O(log  ^d−1 n+k), update time O(log  ^d n), and space O(nlog  ^d−2+ε n) for any ε>0. The model of computation used in our paper is a unit cost RAM with word size log n. A preliminary version of this paper appeared in the Proceedings of the 21st Annual ACM Symposium on Computational Geometry 2005. Work partially supported by IST grant 14036 (RAND-APX).     

Sparse LCS Common Substring Alignment

The “Common Substring Alignment” problem is defined as follows. The input consists of a set of strings S₁,S₂…,S_c, with a common substring appearing at least once in each of them, and a target string T. The goal is to compute similarity of all strings S_i with T, without computing the part of the common substring over and over again.In this paper we consider the Common Substring Alignment problem for the LCS (Longest Common Subsequence) similarity metric. Our algorithm gains its efficiency by exploiting the sparsity inherent to the LCS problem. Let Y be the common substring, n be the size of the compared sequences, L_y be the length of the LCS of T and Y, denoted |LCS[T,Y]|, and L be max{|LCS[T,S_i]|}. Our algorithm consists of an O(nL_y) time encoding stage that is executed once per common substring, and an O(L) time alignment stage that is executed once for each appearance of the common substring in each source string. The additional running time depends only on the length of the parts of the strings that are not in any common substring.     

Parameterized Intractability of Distinguishing Substring Selection

A central question in computational biology is the design of genetic markers to distinguish between two given sets of (DNA) sequences. This question is formalized as the NP-complete Distinguishing Substring Selection problem (DSSS for short) which asks, given a set of "good" strings and a set of "bad" strings, for a solution string which is, with respect to the Hamming metric, "away" from the good strings and "close" to the bad strings. More precisely, given integers d_g, d_b, and L, we ask for a length-L string s such that s has Hamming distance at least d_g to every length-L substring of the good strings and such that every bad string has a length-L substring with Hamming distance at most d_b to s. Studying the parameterized complexity of DSSS, we show that, already for binary alphabet, DSSS is W[1]-hard with respect to its natural parameters. This, in particular, implies that a recently given polynomial-time approximation scheme (PTAS) by Deng et al. cannot be replaced by a so-called efficient polynomial-time approximation scheme (EPTAS) unless an unlikely collapse in parameterized complexity theory occurs. This is seemingly the first computational biology problem for which such a border between PTAS (which exists) and EPTAS (which is unlikely to exist) could be established. By way of contrast, for a special case of DSSS, we present an exact fixed-parameter algorithm solving the problem efficiently. In this way we also exhibit a sharp border between fixed-parameter tractability and intractability results.     

The Noisy Substring Matching Problem

Let T(U) be the set of words in the dictionary H which contains U as a substring. The problem considered here is the estimation of the set T(U) when U is not known, but Y, a noisy version of U is available. The suggested set estimate S*(Y) of T(U) is a proper subset of H such that its every element contains at least one substring which resembles Y most according to the Levenshtein metric. The proposed algorithm for-the computation of S*(Y) requires cubic time. The algorithm uses the recursively computable dissimilarity measure Dk(X, Y), termed as the kth distance between two strings X and Y which is a dissimilarity measure between Y and a certain subset of the set of contiguous substrings of X. Another estimate of T(U), namely SM(Y) is also suggested. The accuracy of SM(Y) is only slightly less than that of S*(Y), but the computation time of SM(Y) is substantially less than that of S*(Y). Experimental results involving 1900 noisy substrings and dictionaries which are subsets of 1023 most common English words [11] indicate that the accuracy of the estimate S*(Y) is around 99 percent and that of SM(Y) is about 98 percent.     

求最长公共子串问题的算法分析

高效求解2个字符串的最长公共子串(Longest Common Substring)是实现很多字符串算法的关键.文中首先给出了求解LCP问题的动态规划算法,广义后缀树算法,研究并分析了这两种算法,得出动态规划算法易于理解,但时间复杂度较高;广义后缀树算法的时间复杂度较低,但实现较为复杂并且广义后缀树占用的空间也较多.最后提出了一个新算法,该算法使用2个字符串的广义后缀数组,在保持和广义后缀树时间复杂度相等的基础上,可以简单地实现并且占用较少的空间.     

一种基于独立性统计的子串归并算法

现行的子串归并算法都是采用一对一的方式针对同频子串提出的。但是在使用词法分析工具对文本进行切分时,不可避免地会产生很多的分词碎片,这直接导致了很多无意义子串的产生。通过分析这些无意义子串和众多父串之间的这种一对多关系,提出了一种基于独立性统计的子串归并算法。最后将该子串归并算法应用在中文术语抽取系统中,使得系统的准确率从91.3%提升到了93.32%。     

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

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

Substring search and repeat search using factor oracles

We present some simple but useful properties of factor oracles, and propose fast algorithms for indexed full-text search and finding repeated substrings. Some experiments are given to demonstrate the performance of our algorithms.     

具有子串检索功能的可扩展分布式数据结构

EH*S是可扩展分布式数据结构EH*的一个改进，增加了子串检索功能。通过对子串和关键字计算描述符向量，为EH*文件中的每个桶添加一个桶描述符向量，然后把子串描述符向量分别与关键字和桶的描述符向量进行比较，得到包含子串的关键字集。     

一种基于子串运算的模式匹配方法

本文的主要目的是找到一种通用的方法来解决模式匹配中的复杂匹配问题。文中描述了一种通过在数据库中搜索和匹配列的q-grams子串来找到一个源列和目标列间对应关系 的代数表达式,从而获得匹配结果的方法。该方法的优点是不需要再附加任何额外的用于匹配的信息就可以有效地找到模式中那些复杂的匹配,并且可以处理固定和可变长度类型的列。文章中使用了一个递归的算法来推论列的子串拼接的正确顺序,并结合一些例子介绍了这一算法,然后测试了算法的实际表现。     

两种基于双向比较的最长公共子串算法

查找两个给定字符串的最长公共子串(LCSstr)是一类重要字符串分析问题,在字符串近似匹配、计算机病毒特征码对比等方面有着广泛的用途.最长公共子串算法目前主要包括动态规划算法(LCSstrDP)和后缀数组算法(LCSstrSA),分别用于短串和长串的最长公共子串计算.前者代码简洁,但计算速度较慢,后者速度很快但算法非常复杂.提出两种基于双向比较的最长公共子串算法,即LCSstrSeL和LCSstrSCeL.LCSstrSeL跨越已有的最长公共子串长度,与LCSstrDP相比,代码同样简洁,平均计算效率提高近一个数量级,并且不需要额外的存储空间.LCSstrSCeL是在LCSstrSeL的基础上,增加字符跨越、连续同值区间跨越等机制,平均效率较LCSstrSeL亦有一定程度的提高,内存开销与LCSstrDP相近,在中小长度的字符串LCSstr计算中,平均计算效率高于LCSstrSA,某些情况下的计算效率可达到亚线性的速度.     

An LR Substring Parser Applied in a Parallel Environment

A sequential substring parser implemented by Cormack naturally lends itself to parallelization. Cormack's algorithm implements the theory developed by Richter for a suffix parser that parses the bounded context class of LR grammars. Of interest is the behavior of the parallel version, particularly the number of reductions done with small substrings. There are timing gains made when parsing sentences of an expression language on a balanced binary tree architecture. The behavior is analyzed for sentences of an expression language parsed on 7, 15, and 31 node trees. The expression language is parsable inO(logn) time in the best case. How evenly work is distributed among the processors depends on the number of tokens per leaf and the shape of the program's derivation tree.     

An improved lower bound on approximation algorithms for the Closest Substring problem

The Closest Substring problem (the CSP problem) is a basic NP-hard problem in the study of computational biology. It is known that the problem has polynomial time approximation schemes. In this paper, we prove that unless the Exponential Time Hypothesis fails, the CSP problem has no polynomial time approximation schemes of running time f(1/ε)n^o(1/ε) for any function f. This essentially excludes the possibility that the CSP problem has a practical polynomial time approximation scheme even for moderate values of the error bound ε. As a consequence, it is unlikely that the study of approximation schemes for the CSP problem in the literature would lead to practical approximation algorithms for the problem for small error bound ε.     

求最长公共子串的两类解法比较

在字符串的运算中,求两个字符串的最长公共子串是一个重要的算法,有着广泛的应用价值。一般认为一共有两大类解法,之所以叫两大类,是因为每一类都可以再细致划分。前一类易理解,占用内存单元大,时间复杂度低,后一类复杂,最好和KMP算法结合。     

求最长公共子串的两类解法比较

在字符串的运算中,求两个字符串的最长公共子串是一个重要的算法,有着广泛的应用价值。一般认为一共有两大类解法,之所以叫两大类,是因为每一类都可以再细致划分。前一类易理解,占用内存单元大,时间复杂度低,后一类复杂,最好和KMP算法结合。     

良构子串表在自然语言处理中的程序化应用以花园幽径句为例

自然语言处理是计算语言学研究的方向之一,通常借助计算机技术进行自然语言的分析和解读。NS 流程图具有选择算法剖析的结构性特点。良构子串表具有保存剖析过程多种结构的特性。花园幽径句是句法加工过程中能产生行进式错位且对前期模式破旧立新的特殊句式。基于NS 流程图算法的良构子串表可用于对自然语言中的特殊现象(如花园幽径句)进行程序剖析,最终使这种程序分析法在语言学中得到应用成为可能。     

Searching a Bitstream in Linear Time for the Longest Substring of Any Given Density

Given an arbitrary bitstream, we consider the problem of finding the longest substring whose ratio of ones to zeroes equals a given value. The central result of this paper is an algorithm that solves this problem in linear time. The method involves (i)?reformulating the problem as a constrained walk through a sparse matrix, and then (ii)?developing a data structure for this sparse matrix that allows us to perform each step of the walk in amortised constant time. We also give a linear time algorithm to find the longest substring whose ratio of ones to zeroes is bounded below by a given value. Both problems have practical relevance to cryptography and bioinformatics.