检索结果-内蒙古大学图书馆

INFORMATION AND COMPUTATION 2015年 241卷 215-226页

作者： Amir, Amihood Eisenberg, Estrella Levy, A. Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Shenkar Coll Dept Software Engn Ramat Gan Israel Univ Haifa CRI IL-31905 Haifa Israel Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA

Finding an approximate period in a given string S of length n is defined as follows. Let S' be a periodic string closest to Sunder some distance metric, find the smallest period of S'. This period is called an approximate period of Sunder the given metric. Let the distance between the input string Sand a closest periodic string under the Hamming distance S' be k. We develop algorithms that construct an approximate period of Sunder the Hamming distance in time O (nk log logn) and under the swap distance in time O (n(2)). Finally, we show an O (n logn) algorithm for finite alphabets, and an O (n log(3) n) algorithm for infinite alphabets, that approximate the minimum number of mismatches between the input string and a closest periodic string under the Hamming distance. (C) 2015 Elsevier Inc. All rights reserved.

关键词： string algorithms Periodicity Approximate periodicity Approximate matching Hamming distance Swap distance

来源：评论

学校读者我要写书评

暂无评论

LCS approximation via embedding into locally non-repetitive strings

引用

INFORMATION AND COMPUTATION 2011年第4期209卷 705-716页

作者： Landau, G. M. Levy, A. Newman, I. Shenkar Coll Dept Software Engn Ramat Gan Israel Univ Haifa Dept Comp Sci IL-31905 Haifa Israel Univ Haifa CRI IL-31905 Haifa Israel NYU Poly MetroTech Ctr 6 Dept Comp Sci & Engn Brooklyn NY 11201 USA

A classical measure of similarity between strings is the length of the longest common subsequence (LCS) between the two given strings. The search for efficient algorithms for finding the LCS has been going on for more than three decades. To date, all known algorithms may take quadratic time (shaved by logarithmic factors) to find large LCS. In this paper, the problem of approximating LCS is studied, while focusing on the hard inputs for this problem, namely, approximating LCS of near-linear size in strings over a relatively large alphabet (of size at least n(epsilon) for some constant epsilon > 0, where n is the length of the string). We show that, any given string over a relatively large alphabet can be embedded into a locally non-repetitive string. This embedding has a negligible additive distortion for strings that are not too dissimilar in terms of the edit distance. We also show that LCS can be efficiently approximated in locally-non-repetitive strings. Our new method (the embedding together with the approximation algorithm) gives a strictly sub-quadratic time algorithm (i.e., of complexity 0(n(2-epsilon)) for some constant epsilon) which can find common subsequences of linear (and near linear) size that cannot be detected efficiently by the existing tools. (C) 2011 Elsevier Inc. All rights reserved.

关键词： string algorithms LCS approximation Embedding

来源：评论

学校读者我要写书评

暂无评论

Periodicity in Data Streams with Wildcards

引用

THEORY OF COMPUTING SYSTEMS 2020年第1期64卷 177-197页

作者： Ergun, Funda Grigorescu, Elena Azer, Erfan Sadeqi Zhou, Samson Indiana Univ Sch Informat & Comp Bloomington IN 47405 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

We investigate the problem of detecting periodic trends within a string S of length n, arriving in the streaming model, containing at most k wildcard characters, where k = o(n). A wildcard character is a special character that can be assigned any other character. We say that S has wildcard-period p if there exists an assignment to each of the wildcard characters so that in the resulting stream the prefix of length n - p equals the suffix of length n - p. We present a two-pass streaming algorithm that computes wildcard-periods of S using O(k3 polylog n) bits of space, while we also show that this problem cannot be solved in sublinear space in one pass. We also give a one-pass randomized streaming algorithm that computes all wildcard-periods p of S withp < n2 and no wildcard characters appearing in the last p symbols of S, using O(k3 log9 n) space.

关键词： Streaming algorithms Periodicity Wildcards Randomized algorithms string algorithms

来源：评论

学校读者我要写书评

暂无评论

Dynamic and Internal Longest Common Substring

引用

ALGORITHMICA 2020年第12期82卷 3707-3743页

作者： Amir, Amihood Charalampopoulos, Panagiotis Pissis, Solon P. Radoszewski, Jakub Bar Ilan Univ Dept Comp Sci Ramat Gan Israel Kings Coll London Dept Informat London England CWI Amsterdam Netherlands Vrije Univ Amsterdam Netherlands Univ Warsaw Inst Informat Warsaw Poland Samsung R&D Inst Poland Warsaw Poland

Given two strings S and T, each of length at most n, the longest common substring (LCS) problem is to find a longest substring common to S and T. This is a classical problem in computer science with an O(n)-time solution. In the fully dynamic setting, edit operations are allowed in either of the two strings, and the problem is to find an LCS after each edit. We present the first solution to the fully dynamic LCS problem requiring sublinear time in n per edit operation. In particular, we show how to find an LCS after each edit operation in (O) over tilde (n(2/3)) time, after (O) over tilde (n)-time and space preprocessing. This line of research has been recently initiated in a somewhat restricted dynamic variant by Amir et al. [SPIRE 2017]. More specifically, the authors presented an (O) over tilde (n)-sized data structure that returns an LCS of the two strings after a single edit operation (that is reverted afterwards) in (O) over tilde (1) time. At CPM 2018, three papers (Abedin et al., Funakoshi et al., and Urabe et al.) studied analogously restricted dynamic variants of problems on strings;specifically, computing the longest palindrome and the Lyndon factorization of a string after a single edit operation. We develop dynamic sublinear-time algorithms for both of these problems as well. We also consider internal LCS queries, that is, queries in which we are to return an LCS of a pair of substrings of S and T. We show that answering such queries is hard in general and propose efficient data structures for several restricted cases.

关键词： Longest common substring string algorithms Dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

algorithms for computing approximate repetitions in musical sequences

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2002年第11期79卷 1135-1146页

作者： Cambouropoulos, E Crochemore, M Iliopoulos, CS Mouchard, L Pinzon, YJ Austrian Res Inst Artificial Intelligence A-1010 Vienna Austria Univ Marne La Vallee Inst Gaspard Monge F-77454 Marne La Vallee 2 France Kings Coll London Dept Comp Sci London WC2R 2LS England Curtin Univ Technol Sch Comp Bentley WA 6102 Australia Univ Rouen LIFAR ABISS F-76821 Mont St Aignan France

Here we introduce two new notions of approximate matching with application in computer assisted music analysis. We present algorithms for each notion of approximation: for approximate string matching and for computing... 详细信息

关键词： string algorithms approximate string matching dynamic programming computer-assisted music analysis

来源：评论

学校读者我要写书评

暂无评论

algorithms for Jumbled Indexing, Jumbled Border and Jumbled Square on run-length encoded strings

引用

THEORETICAL COMPUTER SCIENCE 2016年第PartB期656卷 146-159页

作者： Amir, Amihood Apostolico, Alberto Hirst, Tirza Landau, Gad M. Lewenstein, Noa Rozenberg, Liat Bar Ilan Univ IL-52100 Ramat Gan Israel Johns Hopkins Univ Baltimore MD 21218 USA Georgia Tech Atlanta GA USA CNR IASI I-00185 Rome Italy Machon Tal Jerusalem Israel Univ Haifa IL-31999 Haifa Israel NYU New York NY 10003 USA Netanya Coll Netanya Israel

In this paper we investigate jumbled (Abelian) versions of three classical strings problems. In all these problems we assume the input string S[1..n] is given in its run-length format S'[1..r]. The Jumbled Indexing problem is the problem of indexing a string S'[1..r] over vertical bar Sigma vertical bar for histogram queries, i.e. given a pattern P, we want to find all substrings of S that are permutations of P. We provide an algorithm that constructs an index of size O (r(2)vertical bar Sigma vertical bar) in time O (r(2)(logr + vertical bar Sigma vertical bar log vertical bar Sigma vertical bar)), which allows answering histogram queries in O(vertical bar E vertical bar(3) log r)-time. The Jumbled Border problem is the problem of finding for every location j in S, the longest proper prefix of S[1.. j] that is also a permutation of a proper suffix of 5[1.. j], if such exists. We provide an algorithm that solves this problem in O(vertical bar Sigma vertical bar(r(2) +n)) time, and O(vertical bar Sigma vertical bar n) space. A Jumbled Square is a string of the form x (x) over bar, where (x) over bar is a permutation of x. The Jumbled Square problem is the problem of finding for every location j in S, the longest jumbled square that ends in j, if such exists. We provide an algorithm that solves this problem in O(vertical bar Sigma vertical bar(r(2) + n)) time, and O(vertical bar Sigma vertical bar n) space. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Pattern Matching Jumbled Indexing Abelian border Abelian square string algorithms

来源：评论

学校读者我要写书评

暂无评论

A note on the longest common substring with k-mismatches problem

引用

INFORMATION PROCESSING LETTERS 2015年第6-8期115卷 640-642页

作者： Grabowski, Szymon Lodz Univ Technol Inst Appl Comp Sci PL-90924 Lodz Poland

The recently introduced longest common substring with k-mismatches (k-LCF) problem is to find, given two sequences S-1 and S-2 of length n each, a longest substring A(1) of S-1 and A(2) of S-2 such that the Hamming distance between A(1) and A(2) is at most k. So far, the only subquadratic time result for this problem was known for k = 1 [5]. We present two output-dependent algorithms solving the k-LCF problem and show that for k = O (log(1-epsilon) n), where epsilon > 0, at least one of them works in subquadratic time, using O(n) words of space. The choice of one of these two algorithms to be applied for a given input can be done after linear time and space preprocessing. (c) 2015 Elsevier B.V. All rights reserved.

关键词： Combinatorial problems string algorithms Longest common substring with k-mismatches Word-level parallelism

来源：评论

学校读者我要写书评

暂无评论

A filtering algorithm for k-mismatch with don't cares

引用

INFORMATION PROCESSING LETTERS 2010年第22期110卷 1021-1025页

作者： Clifford, Raphael Porat, Ely Univ Bristol Dept Comp Sci Bristol BS8 1UB Avon England Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel

We present a filtering based algorithm for the k-mismatch pattern matching problem with don't cares. Given a text t of length n and a pattern p of length m with don't care symbols in either p or t (but not both), and a bound k, our algorithm finds all the places that the pattern matches the text with at most k mismatches. The algorithm is deterministic and runs in Theta(nm(1/3)k(1/3) log(2/3) m) time. (C) 2010 Elsevier B.V. All rights reserved.

关键词： algorithms Design of algorithms Combinatorial problems string algorithms Don't cares Pattern matching Filtering Fast Fourier transforms

来源：评论

学校读者我要写书评

暂无评论

Approximate pattern matching with k-mismatches in packed text

引用

INFORMATION PROCESSING LETTERS 2013年第19-21期113卷 693-697页

作者： Giaquinta, Emanuele Grabowski, Szymon Fredriksson, Kimmo Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland Tech Univ Lodz Inst Appl Comp Sci PL-90924 Lodz Poland Univ Eastern Finland Sch Comp FI-70211 Kuopio Finland

Given strings P of length m and T of length n over an alphabet of size sigma, the string matching with k-mismatches problem is to find the positions of all the substrings in T that are at Hamming distance at most k from P. If T can be read only one character at the time the best known bounds are O (n root klogk) and O(n + n root k/w logk) in the word-RAM model with word length w. In the RAM models (including AC(0) and word-RAM) it is possible to read up to left perpendicularw/log sigma right perpendicular characters in constant time if the characters of T are encoded using inverted right perpendicularlog sigma inverted left perpendicular bits. The only solution for k-mismatches in packed text works in O ((n log sigma/log n) inverted right perpendicularm log(k + logn/log sigma)/winverted left perpendicular + n(epsilon)) time, for any epsilon > 0. We present an algorithm that runs in time O(n/left perpendicularw/(m log sigma)right perpendicular (1 + log min(k, sigma)log m/log sigma)) in the AC(0) model if m = O (w/log sigma) and T is given packed. We also describe a simpler variant that runs in time O(n/left perpendicular/(m log sigma)right perpendicular log min(m, log w/log sigma)) in the word-RAM model. The algorithms improve the existing bound for w = Omega(log(1+epsilon) n), for any epsilon > 0. Based on the introduced technique, we present algorithms for several other approximate matching problems. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Combinatorial problems string algorithms k-mismatches Hamming distance Word-level parallelism

来源：评论

学校读者我要写书评

暂无评论

Faster semi-external suffix sorting

引用

INFORMATION PROCESSING LETTERS 2014年第4期114卷 174-178页

作者： Dhaliwal, Jasbir RMIT Univ Sch Comp Sci & Informat Technol Melbourne Vic Australia

Suffix array (SA) construction is a time-and-memory bottleneck in many string processing applications. In this paper we improve the runtime of a small-space - semi-external - SA construction algorithm by Karkkainen (TCS, 2007) [5]. We achieve a speedup in practice of 2-4 times, without increasing memory usage. Our main contribution is a way to implement the "pointer copying" heuristic, used in less space-efficient SA construction algorithms, in a memory-efficient way. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Data structures Suffix array Burrows-Wheeler transform string algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：