Dany Breslauer

TCS Journal 2014 Journal Article

Towards optimal packed string matching

• Oren Ben-Kiki
• Philip Bille
• Dany Breslauer
• Leszek Ga̧sieniec
• Roberto Grossi
• Oren Weimann

In the packed string matching problem, it is assumed that each machine word can accommodate up to α characters, thus an n-character string occupies n / α memory words. (a) We extend the Crochemore–Perrin constant-space O ( n ) -time string-matching algorithm to run in optimal O ( n / α ) time and even in real-time, achieving a factor α speedup over traditional algorithms that examine each character individually. Our macro-level algorithm only uses the standard A C 0 instructions of the word-RAM model (i. e. no integer multiplication) plus two specialized micro-level A C 0 word-size packed-string instructions. The main word-size string-matching instruction wssm is available in contemporary commodity processors. The other word-size maximum-suffix instruction wslm is only required during the pattern pre-processing. Benchmarks show that our solution can be efficiently implemented, unlike some prior theoretical packed string matching work. (b) We also consider the complexity of the packed string matching problem in the classical word-RAM model in the absence of the specialized micro-level instructions wssm and wslm. We propose micro-level algorithms for the theoretically efficient emulation using parallel algorithms techniques to emulate wssm and using the Four-Russians technique to emulate wslm. Surprisingly, our bit-parallel emulation of wssm also leads to a new simplified parallel random access machine string-matching algorithm. As a byproduct to facilitate our results we develop a new algorithm for finding the leftmost (most significant) 1 bits in consecutive non-overlapping blocks of uniform size inside a word. This latter problem is not known to be reducible to finding the rightmost 1, which can be easily solved, since we do not know how to reverse the bits of a word in O ( 1 ) time.

TCS Journal 2013 Journal Article

Simple real-time constant-space string matching

• Dany Breslauer
• Roberto Grossi
• Filippo Mignosi

String matching is the classical problem of finding all occurrences of a pattern in a text. A real-time string matching algorithm takes worst-case constant-time to check if a pattern occurrence ends at each text location. We derive a real-time variation of the elegant Crochemore–Perrin constant-space string matching algorithm that has a simple and efficient control structure. We use observations about the locations of critical factorizations to deploy two tightly-coupled simplified real-time instances of the Crochemore–Perrin algorithm that search for complementary parts of the pattern whose simultaneous occurrence indicates an occurrence of the complete pattern.

TCS Journal 2012 Journal Article

On suffix extensions in suffix trees

• Dany Breslauer
• Giuseppe F. Italiano

Suffix trees are inherently asymmetric: prefix extensions only cause a few updates, while suffix extensions affect all suffixes causing a wave of updates. In his elegant linear-time on-line suffix tree algorithm Ukkonen relaxed the prevailing suffix tree representation and introduced two changes to avoid repeated structural updates and circumvent the inherent complexity of suffix extensions: (1) open ended edges that enjoy gratuitous leaf updates, and (2) the omission of implicit nodes. In this paper we study the implicit nodes as the suffix tree evolves. We partition the suffix tree’s edges into collections of similar edges called bands, where implicit nodes exhibit identical behavior, and generalize the notion of open ended edges to allow implicit nodes to “float” within bands, only requiring updates when moving from one band to the next, adding up to only O ( n ) updates. We also show that internal implicit nodes are separated from each other by explicit suffix tree nodes and that all external implicit nodes are related to the same periodicity. These new properties may be used to keep track of the waves of implicit node updates and to build the suffix tree on-line in amortized linear time, providing access to all the implicit nodes in worst-case constant time.

TCS Journal 1998 Journal Article

On competitive on-line paging with lookahead

• Dany Breslauer

This paper studies two methods for improving the competitive efficiency of on-line paging algorithms: in the first, the on-line algorithm can use more pages; in the second, it is allowed to have a lookahead, or in other words, some partial knowledge of the future. The paper considers a new measure for the lookahead size as well as Young's resource-bounded lookahead and proves that both measures have the attractive property that the competitive efficiency of an on-line algorithm with k extra pages and lookahead l depends on k + l. Hence, under these measures, an on-line algorithm has the same benefit from using an extra page or knowing an extra bit of the future.

TCS Journal 1998 Journal Article

The suffix tree of a tree and minimizing sequential transducers

• Dany Breslauer

This paper gives a linear-time algorithm for the construction of the suffix tree of a tree, which was introduced by Kosaraju, as a natural generalization of the suffix tree of a string. The suffix tree of a tree is used to obtain an efficient algorithm for the minimization of sequential transducers.

TCS Journal 1996 Journal Article

Saving comparisons in the Crochemore-Perrin string-matching algorithm

• Dany Breslauer

Crochemore and Perrin discovered an elegant linear-time constant-space string-matching algorithm that makes at most 2n − m symbol comparisons. This paper shows how to modify their algorithm to use fewer comparisons. Given any fixed ε > 0, the new algorithm takes linear time, uses constant space and makes at most n + [ 1 + ε 2 (n − m)] symbol comparisons. If O(log m) space is available, then the algorithm makes at most n + [ 1 2 (n − m)] symbol comparisons. The pattern preprocessing step also takes linear time and uses constant space. These are the first string-matching algorithms that make fewer than 2n − m symbol comparisons and use sub-linear space.

TCS Journal 1995 Journal Article

Fast parallel string prefix-matching

• Dany Breslauer

An O(log log m) time n log m log log m -processor CRCW-PRAM algorithm for the string prefix-matching problem over general alphabets is presented. The algorithm can also be used to compute the KMP failure function in O(log log m) time on m log m log log m processors. These results improve on the running time of the best previous algorithm for both problems, which was O(log m), while preserving the same number of operations.

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.

STOC Conference 1991 Conference Paper

A Lower Bound for Parallel String Matching

• Dany Breslauer
• Zvi Galil

STOC Conference 1989 Conference Paper

Highly Parallelizable Problems (Extended Abstract)

• Omer Berkman
• Dany Breslauer
• Zvi Galil
• Baruch Schieber
• Uzi Vishkin