Alberto Apostolico

TCS Journal 2017 Journal Article

String cadences

• Amihood Amir
• Alberto Apostolico
• Travis Gagie
• Gad M. Landau

Cadences are syntactic regularities in strings, of the family of periods, squares, and repetitions. We say a string has a cadence if a certain character is repeated at regular intervals, possibly with intervening occurrences of that character. We call the cadence anchored if the first interval must be the same length as the others. Although cadences' combinatorial properties have been explored, little work was done regarding the efficiency of their discovery. Recently, implementations involving cadences appeared in works on phylogenetic reconstruction, periodic subgraph mining, and monitoring events in computer networks. In this paper we begin a systematic study of the efficiency of finding cadences. We first give some basic definitions; we then give a sub-quadratic algorithm for determining whether a string has any cadence consisting of at least three occurrences of a character, and a nearly linear algorithm for finding all anchored cadences; finally, we propose a data structure that captures many features of cadences and allows for the efficient detection of many types of cadences. In particular, all sub-cadences can be detected and reported in time proportional to the sum of their lengths.

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.

TCS Journal 2016 Journal Article

Sequence similarity measures based on bounded hamming distance

• Alberto Apostolico
• Concettina Guerra
• Gad M. Landau
• Cinzia Pizzi

A growing number of measures of sequence similarity are being based on some underlying notion of relative compressibility. Within this paradigm, similar sequences are expected to share a large number of common substrings, or subsequences, or more complex patterns or motifs, and so on. In this paper, measures of sequence similarity are introduced and studied in which patterns in a pair are considered similar if they coincide up to a preset number of mismatches, that is, within a bounded Hamming distance. It is shown here that for some such measures bounds are achievable that are slightly better than O ( n 2 ). Preliminary experiments demonstrate the potential applicability to phylogeny and classification of these similarity measures.

TCS Journal 2015 Journal Article

A PTAS for the Square Tiling Problem

• Amihood Amir
• Alberto Apostolico
• Gad M. Landau
• Ely Porat
• Oren Sar Shalom

The Square Tiling Problem was recently introduced as equivalent to the problem of reconstructing an image from patches and a possible general-purpose indexing tool. Unfortunately, the Square Tiling Problem was shown to be NP -hard. A 1/2-approximation is known. We show that if the tile alphabet is fixed and finite, there is a Polynomial Time Approximation Scheme (PTAS) for the Square Tiling Problem with approximation ratio of ( 1 − ϵ 2 log ⁡ n ) for any given ϵ ≤ 1. Another topic handled in this paper is the NP -hardness of the Tiling problem with an infinite alphabet. We show that when the alphabet is not bounded, even the decision version for rectangles of size 3n is NP -Complete.

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.

TCS Journal 2014 Journal Article

Modulated string searching

• Alberto Apostolico
• Péter L. Erdős
• István Miklós
• Johannes Siemons

In his 1987 paper entitled Generalized String Matching Abrahamson introduced the concept of pattern matching with character classes and provided the first efficient algorithm to solve this problem. The best known solution to date is due to Linhart and Shamir (2009). Another broad yet comparatively less intensively studied class of string matching problems is numerical string searching, such as for instance “less-than” or L 1 -norm string searching. The best known solutions for problems in this class are based on FFT convolution after some suitable re-encoding. The present paper introduces modulated string searching as a unified framework for string matching problems where the numerical conditions can be combined with some Boolean/numerical decision conditions on the character classes. One example problem in this class is the locally bounded L 1 -norm matching problem with parameters b and τ: here the pattern “matches” a text of same length if their L 1 -distance is at most b and if furthermore there is no position where the text element and pattern element differ by more than the local bound τ. A more general setup is that where the pattern positions contain character classes and/or each position has its own private local bound. While the first variant can clearly be handled by adaptation of the classic FFT method, the second one is far too complicated for this treatment. The algorithm we propose in this paper can solve all such problems efficiently. The proposed framework contains two nested procedures. The first one, based on Karatsuba's fast multiplication algorithm, solves pattern matching with character classes within time O ( n m 0. 585 ), where n and m are the text and pattern length respectively (under some reasonable conventions). This is slightly better than the complexity of Abrahamson's algorithm for generalized string matching but worse than algorithms based on FFT. The second procedure, which works as a plug-in within the first one and is tailored to the specific problem variant at hand, solves the numerical and/or Boolean matching problem with high efficiency. Some of the previously known constructions can be adapted to match or outperform several (but not all) problem variations handled by the construction proposed here. The latter aims to be a general tool that provides a unified solution for all problems of this kind.

TCS Journal 2012 Journal Article

Parameterized searching with mismatches for run-length encoded strings

• Alberto Apostolico
• Péter L. Erdős
• Alpár Jüttner

Parameterized matching between two strings occurs when it is possible to reduce the first one to the second by a renaming of the alphabet symbols. We present an algorithm for searching for parameterized occurrences of a patten in a textstring when both are given in run-length encoded form. The proposed method extends to alphabets of arbitrary yet constant size with O ( | r p | × | r t | ) time bounds, previously achieved only with binary alphabets. Here r p and r t denote the number of runs in the corresponding encodings for p and t. For general alphabets, the time bound obtained by the present method exhibits a polynomial dependency on the alphabet size. Such a performance is better than applying convolution to the cleartext, but leaves the problem still open of designing an alphabet independent O ( | r p | × | r t | ) time algorithm for this problem.

TCS Journal 2009 Journal Article

The subsequence composition of a string

• Alberto Apostolico
• Fabio Cunial

Words that appear as constrained subsequences in a text-string are considered as possible indicators of the host string structure, hence also as a possible means of sequence comparison and classification. The constraint consists of imposing a bound on the number ω of positions in the text that may intervene between any two consecutive characters of a subsequence. A subset of such ω -sequences is then characterized that consists, in intuitive terms, of sequences that could not be enriched with more characters without losing some occurrence in the text. A compact spatial representation is then proposed for these representative sequences, within which a number of parameters can be defined and measured. In the final part of the paper, such parameters are empirically analyzed on a small collection of text-strings endowed with various degrees of structure.

TCS Journal 2008 Journal Article

Incremental discovery of the irredundant motif bases for all suffixes of a string in O ( n 2 log n ) time

• Alberto Apostolico
• Claudia Tagliacollo

Compact bases formed by motifs called “irredundant” and capable of generating all other motifs in a sequence have been proposed in recent years and successfully tested in tasks of biosequence analysis and classification. Given a sequence s of n characters drawn from an alphabet Σ, the problem of extracting such a base from s had been previously solved in time O ( n 2 log n log ∣ Σ ∣ ) and O ( ∣ Σ ∣ n 2 log 2 n log log n ), respectively, using the FFT-based string searching by Fischer and Paterson. More recently, a solution on binary strings taking time O ( n 2 ) without resorting to the FFT was also proposed. In the present paper, we considered the problem of incrementally extracting the bases of all suffixes of a string. This problem was solved in a previous work in time O ( n 3 ). A much faster incremental algorithm is described here, which takes time O ( n 2 log n ) for binary strings. Although this algorithm does not make use of the FFT, its performance is comparable to the one exhibited by the previous FFT-based algorithms involving the computation of only one base. The implicit representation of a single base requires O ( n ) space, whence for finite alphabets the proposed solution is within a log n factor from optimality.

TCS Journal 2008 Journal Article

Motif patterns in 2D

• Alberto Apostolico
• Laxmi Parida
• Simona E. Rombo

Motif patterns consisting of sequences of intermixed solid and don’t-care characters have been introduced and studied in connection with pattern discovery problems of computational biology and other domains. In order to alleviate the exponential growth of such motifs, notions of maximal saturation and irredundancy have been formulated, whereby more or less compact subsets of the set of all motifs can be extracted, that are capable of expressing all others by suitable combinations. In this paper, we introduce the notion of maximal irredundant motifs in a two-dimensional array and develop initial properties and a combinatorial argument that poses a linear bound on the total number of such motifs. The remainder of the paper presents approaches to the discovery of irredundant motifs both by offline and incremental algorithms.

I&C Journal 2007 Journal Article

Fast gapped variants for Lempel–Ziv–Welch compression

• Alberto Apostolico

Variants of classical data compression paradigms by Ziv, Lempel, and Welch are proposed in which the phrases used in compression are selected among suitably chosen strings of intermittently solid and wild characters produced by the autocorrelation of the sourcestring. Adaptations and extensions of the classical ZL78 paradigm as implemented by Welch are developed along these lines, and they are easily seen to be susceptible of simple linear time implementation. Both lossy and lossless schemata are considered, and preliminary analyses of performance are attempted.

TCS Journal 2005 Journal Article

Foreword

• Alberto Apostolico
• Raffaele Giancarlo

TCS Journal 2003 Journal Article

Truncated suffix trees and their application to data compression

• Joong Chae Na
• Alberto Apostolico
• Costas S. Iliopoulos
• Kunsoo Park

The suffix tree is a fundamental data structure in the area of string algorithms and it has been used in many applications including data compression. In this paper we propose a data structure called the truncated suffix tree, which is a truncated version of the suffix tree. We also present two linear-time construction algorithms for truncated suffix trees and two algorithms that delete suffixes from truncated suffix trees. The truncated suffix tree is particularly a useful data structure for LZ77 that compresses using a sliding window of a fixed size. Our algorithms lead to two implementations of LZ77 that maintain sliding windows by truncated suffix trees. We also present a technique of finding the longest match in a sliding window, which is a crucial step in LZ77.

I&C Journal 2002 Journal Article

Compact Recognizers of Episode Sequences

• Alberto Apostolico
• Mikhail J. Atallah

Given two strings X=a 1…a n and P=b 1…b m over an alphabet Σ, the problem of testing whether P occurs as a subsequence of X is trivially solved in linear time. It is also known that a simple O(n log |Σ|) time preprocessing of X makes it easy to decide subsequently, for any P and in at most |P| log |Σ| character comparisons, whether P is a subsequence of X. These problems become more complicated if one asks instead whether P occurs as a subsequence of some substring Y of X of bounded length. This paper presents an automaton built on the textstring X and capable of identifying all distinct minimal substrings Y of X having P as a subsequence. By a substring Y being minimal with respect to P, it is meant that P is not a subsequence of any proper substring of Y. For every minimal substring Y, the automaton recognizes the occurrence of P having the lexicographically smallest sequence of symbol positions in Y. It is not difficult to realize such an automaton in time and space O(n 2) for a text of n characters. One result of this paper consists of bringing those bounds down to linear or O(n log n), respectively, depending on whether the alphabet is bounded or of arbitrary size, thereby matching the corresponding complexities of automata constructions for offline exact string searching. Having built the automaton, the search for all lexicographically earliest occurrences of P in X is carried out in time O(∑ i=1 m rocc i ·i) or O(n+∑ i=1 m rocc i ·i· log n), depending on whether the alphabet is fixed or arbitrary, where rocc i is the number of distinct minimal substrings of X having b 1…b i as a subsequence (note that each such substring may occur many times in X but is counted only once in the bound). All log factors appearing in the above bounds can be further reduced to log log by resorting to known integer-handling data structures.

TCS Journal 2000 Journal Article

Fibonacci arrays and their two-dimensional repetitions

• Alberto Apostolico
• Valentin E. Brimkov

Notions related to repetitive substructures in two-dimensional arrays are introduced and studied in an attempt to parallel some of the analogous developments already known for strings. In particular, sequences of “Fibonacci arrays” are defined, capable of exhibiting extremal properties in terms of certain repetitive subpatterns called “tandems”. Two types of tandems are considered. For one type, it is shown that the number of occurrences in an m×n Fibonacci array attains the general upper bound of O(m2nlogn).

TCS Journal 1995 Journal Article

Parallel detection of all palindromes in a string

• Alberto Apostolico
• Dany Breslauer
• Zvi Galil

This paper presents two efficient concurrent-read concurrent-write parallel algorithms that find all palindromes in a given string: 1. 1. An O(log n) time, n-processor algorithm over general alphabets. In the case of constant size alphabets the algorithm requires only n log n processors, and thus achieves an optimalspeedup. 2. 2. An O(log log n) time, n log n loglog n-processor algorithm over general alphabets. This is the fastest possible time with the number of processors used. These new results improve on the known parallel palindrome detection algorithms by using smaller auxiliary space and either by making fewer operations or by achieving a faster running time.

TCS Journal 1993 Journal Article

Efficient CRCW-PRAM algorithms for universal substring searching

• Alberto Apostolico

A standard representation for strings is proposed, which has the following properties. (1) For any string x, putting x in such a standard representation requires O(log |x|) CRCW-PRAM steps and O(|x| log |x|) total work and space. (2) Let W be a collection of strings individually given in such a standard representation. Let w be an arbitrarily chosen string in W, w′ an arbitrary substring of w, and {w̄ 1, w̄ 2, …, w̄ t} an arbitrary set of substrings of strings in W. Then, a CRCW PRAM with O(n̄= ∑ h=1 t |w̄ h |+|w′|) processors will find all the occurrences of w′ in {w̄ 1, w̄ 2, …, w̄ t }, in constant time.

TCS Journal 1993 Journal Article

Efficient detection of quasiperiodicities in strings

• Alberto Apostolico
• Andrzej Ehrenfeucht

A string z is quasiperiodic if there is a second string w ≠ z such that the occurrences of w in z cover z entirely, i. e. , every position of z falls within some occurrence of w in z. It is shown here that all maximal quasiperiodic substrings of a string x of n symbols can be detected in time O(n log 2 n).