Author name cluster

A. Levy

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2019 Journal Article

Approximate cover of strings

A. Amir
A. Levy
R. Lubin
E. Porat

Regularities in strings arise in various areas of science, including coding and automata theory, formal language theory, combinatorics, molecular biology and many others. A common notion to describe regularity in a string T is a cover, which is a string C for which every letter of T lies within some occurrence of C. The alignment of the cover repetitions in the given text is called a tiling. In many applications finding exact repetitions is not sufficient, due to the presence of errors. In this paper, we use a new approach for handling errors in coverable phenomena and define the approximate cover problem (ACP), in which we are given a text that is a sequence of some cover repetitions with possible mismatch errors, and we seek a string that covers the text with the minimum number of errors. We first show that the ACP is NP -hard, by studying the cover-length relaxation of the ACP, in which the requested length of the approximate cover is also given with the input string. We show that this relaxation is already NP -hard. We also study another two relaxations of the ACP, which we call the partial-tiling relaxation of the ACP and the full-tiling relaxation of the ACP, in which a tiling of the requested cover is also given with the input string. A given full tiling retains all the occurrences of the cover before the errors, while in a partial tiling there can be additional occurrences of the cover that are not marked by the tiling. We show that the partial-tiling relaxation has a polynomial time complexity and give experimental evidence that the full-tiling also has polynomial time complexity. The study of these relaxations, besides shedding another light on the complexity of the ACP, also involves a deep understanding of the properties of covers, yielding some key lemmas and observations that may be helpful for a future study of regularities in the presence of errors.

Details DOI

TCS Journal 2016 Journal Article

LCSk: A refined similarity measure

G. Benson
A. Levy
S. Maimoni
D. Noifeld
B.R. Shalom

In this paper we define a new similarity measure: LCSk, aiming at finding the maximal number of k length substrings matching in both input strings while preserving their order of appearance, for which the traditional LCS is a special case, where k = 1. We examine this generalization in both theory and practice. We first describe its basic solution and give an experimental evidence in real data for its ability to differentiate between sequences that are considered similar according to the LCS measure. We then examine extensions of the LCSk definition to LCS in at least k-length substrings ( LCS ≥ k ) and 2-dimensional LCSk and also define complementary EDk and ED ≥ k distances.

Details DOI

I&C Journal 2015 Journal Article

Approximate periodicity

Amihood Amir
Estrella Eisenberg
A. Levy

Finding an approximate period in a given string S of length n is defined as follows. Let S ′ be a periodic string closest to S under some distance metric, find the smallest period of S ′. This period is called an approximate period of S under the given metric. Let the distance between the input string S and a closest periodic string under the Hamming distance S ′ be k. We develop algorithms that construct an approximate period of S under the Hamming distance in time O ( n k log ⁡ log ⁡ n ) and under the swap distance in time O ( n 2 ). Finally, we show an O ( n log ⁡ n ) 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.

Details DOI

I&C Journal 2011 Journal Article

LCS approximation via embedding into locally non-repetitive strings

G.M. Landau
A. Levy
I. Newman

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 ϵ for some constant ϵ > 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 O ( n 2 - ϵ ) for some constant ϵ ) which can find common subsequences of linear (and near linear) size that cannot be detected efficiently by the existing tools.

Details DOI