Author name cluster

Noa Lewenstein

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.

5 papers

2 author rows

TCS Journal 2016 Journal Article

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

Amihood Amir
Alberto Apostolico
Tirza Hirst
Gad M. Landau
Noa Lewenstein
Liat Rozenberg

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 | Σ | 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 | Σ | ) in time O ( r 2 ( log ⁡ r + | Σ | log ⁡ | Σ | ) ), which allows answering histogram queries in O ( | Σ | 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 S [ 1. . j ], if such exists. We provide an algorithm that solves this problem in O ( | Σ | ( r 2 + n ) ) time, and O ( | Σ | n ) space. A Jumbled Square is a string of the form x x ¯, where x ¯ 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 ( | Σ | ( r 2 + n ) ) time, and O ( | Σ | n ) space.

Details DOI

TCS Journal 2016 Journal Article

Permuted scaled matching

Ayelet Butman
Noa Lewenstein
J. Ian Munro

Scaled matching and permutation matching are two well known paradigms in the domain of pattern matching. Scaled matching refers to finding an occurrence of a pattern which is enlarged proportionally by some scale k within a larger text. Permutation matching is the problem of finding all substrings within a text where the character statistics of the substring and the pattern are the same. Permutation matching is easy, while scaled matching requires innovative solutions. One interesting setting of applications is the merge of the two. The problem of scaled permuted matching (i. e. first permuting and then scaling) has been addressed and solved optimally. However, it was left as an open problem whether there are efficient algorithms for permuted scaled matching. In this paper we solve the problem efficiently in a deterministic setting and optimally in a randomized setting.

Details DOI

TCS Journal 2014 Journal Article

Closest periodic vectors in L p spaces

Amihood Amir
Estrella Eisenberg
Avivit Levy
Noa Lewenstein

The problem of finding the period of a vector V is central to many applications. Let V ′ be a periodic vector closest to V under some metric. We seek this V ′, or more precisely we seek the smallest period that generates V ′. In this paper we consider the problem of finding the closest periodic vector in L p spaces. The measures of “closeness” that we consider are the metrics in the different L p spaces. Specifically, we consider the L 1, L 2 and L ∞ metrics. In particular, for a given n-dimensional vector V, we develop O ( n 2 ) time algorithms (a different algorithm for each metric) that construct the smallest period that defines such a periodic n-dimensional vector V ′. We call that vector the closest periodic vector of V under the appropriate metric. We also show (three) O ˜ ( n ) time constant approximation algorithms for the period of the approximate closest periodic vector.

Details DOI

TCS Journal 2014 Journal Article

Detecting approximate periodic patterns

Amihood Amir
Alberto Apostolico
Estrella Eisenberg
Gad M. Landau
Avivit Levy
Noa Lewenstein

Given ϵ ∈ [ 0, 1 ), the ϵ-Relative Error Periodic Pattern Problem (REPP) is the following: INPUT: An n-long sequence S of numbers s i ∈ N in increasing order. OUTPUT: The longest ϵ-relative error periodic pattern, i. e. , the longest subsequence s i 1, s i 2, …, s i k of S, for which there exists a number p such that the absolute difference between any two consecutive numbers in the subsequence is at least p and at most p ( 1 + ϵ ). The best known algorithm for this problem has O ( n 3 ) time complexity. This bound is too high for large inputs in practice. In this paper we give a new algorithm for finding the longest ϵ-relative error periodic pattern (the REPP problem). Our method is based on a transformation of the input sequence into a different representation: the ϵ-active maximal intervals list L, defined in this paper. We show that the transformation of S to the list L can be done efficiently (quadratic in n and linear in the size of L) and prove that our algorithm is linear in the size of L. This enables us to prove that our algorithm works in sub-cubic time on inputs for which the best known algorithm works in O ( n 3 ) time. Moreover, though it may happen that our algorithm would still be cubic, it is never worse than the known O ( n 3 ) -algorithm and in many situations its complexity is O ( n 2 ) time.

Details DOI

FOCS Conference 1997 Conference Paper

Pattern Matching with Swaps

Amihood Amir
Yonatan Aumann
Gad M. Landau
Moshe Lewenstein
Noa Lewenstein

Let a text string T of n symbols and a pattern string P of m symbols from alphabet /spl Sigma/ be given. A swapped version T' of T is a length n string derived from T by a series of local swaps, (i. e. t/sup '//sub l//spl larr/t/sub l+1/ and t'/sub l+1//spl larr/t/sub l/) where each element can participate in no more than one swap. The Pattern Matching with Swaps problem is that of finding all locations i for which there exists a swapped version T' of T where there is an exact matching of P in location i of T'. It has been an open problem whether swapped matching can be done in less than O(mn) time. In this paper we show the first algorithm that solves the pattern matching with swaps problem in time O(mn). We present an algorithm whose time complexity is O(nm/sup 1/3/ log m log/sup 2/ /spl sigma/) for a general alphabet /spl Sigma/, where /spl sigma/=min(m, |/spl Sigma/|).

Details