Data structures and algorithms for approximate string matching
Journal of ComplexityPublished 1 March 1988
Zvi Galil, Raffaele Giancarlo
Citations142
SJR quartileQ1
SJR score0.85
SNIP1.50
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper surveys techniques for designing efficient sequential and parallel approximate string matching algorithms and special attention is given to the methods for the construction of data structures that efficiently support primitive operations needed in approximatestring matching.
Abstract
This paper surveys techniques for designing efficient sequential and parallel approximate string matching algorithms. Special attention is given to the methods for the construction of data structures that efficiently support primitive operations needed in approximate string matching.
Keywords
Computer Science
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
Journal of the ACMThe String-to-String Correction Problem
3,063 Citations1974Robert A. Wagner, Michael J. Fischer
An algorithm is presented which solves the string-to-string correction problem in time proportional to the product of the lengths of the two strings.
SIAM Journal on ComputingFast Pattern Matching in Strings
2,917 Citations1977Donald E. Knuth, James H. Morris +1 more
An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings, showing that the set of concatenations of even palindromes, i.e., the language $\{\alpha \alpha ^R\}^*$, can be recognized in linear time.
Communications of the ACMA fast string searching algorithm
2,292 Citations1977Robert S. Boyer, J Strother Moore
The algorithm has the unusual property that, in most cases, not all of the first i.” in another string, are inspected.
Series on software engineering and knowledge engineeringData Structures and Algorithms
2,131 Citations2003
The basis of this book is the material contained in the first six chapters of the earlier work, The Design and Analysis of Computer Algorithms, and has added material on algorithms for external storage and memory management.
Linear pattern matching algorithms
1,810 Citations1973Peter Weiner
A linear time algorithm for obtaining a compacted version of a bi-tree associated with a given string is presented and indicated how to solve several pattern matching problems, including some from [4] in linear time.
Journal of the ACMA Space-Economical Suffix Tree Construction Algorithm
1,518 Citations1976Edward M. McCreight
A new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching that has the same asymptotic running time bound as previously published algorithms, but is more economical in space.
Journal of the ACMParallel Prefix Computation
1,282 Citations1980Richard E. Ladner, Michael J. Fischer
A recurstve construction is used to obtain a product circuit for solving the prefix problem and a Boolean clrcmt which has depth 2[Iog2n] + 2 and size bounded by 14n is obtained for n-bit binary addmon.
Communications of the ACMA linear space algorithm for computing maximal common subsequences
1,108 Citations1975D. S. Hirschberg
The problem of finding a longest common subsequence of two strings has been solved in quadratic time and space and an algorithm is presented which will solve this problem in QuadraticTime and in linear space.
SIAM Journal on ComputingFast Algorithms for Finding Nearest Common Ancestors
1,066 Citations1984Dov Harel, Robert E. Tarjan
An algorithm for a random access machine with uniform cost measure (and a bound of $\Omega (\log n)$ on the number of bits per word) that requires time per query and preprocessing time is presented, assuming that the collection of trees is static.
Parallelism in random access machines
880 Citations1978Steven Fortune, James Wyllie
A model of computation based on random access machines operating in parallel and sharing a common memory is presented and can accept in polynomial time exactly the sets accepted by nondeterministic exponential time bounded Turing machines.
Communications of the ACMA fast algorithm for computing longest common subsequences
692 Citations1977James Hunt, Thomas G. Szymanski
An algorithm for finding the longest common subsequence of two sequences of length n which has a running time of O((r + n) log n), where r is the total number of ordered pairs of positions at which the two sequences match.
Journal of Computer and System SciencesA faster algorithm computing string edit distances
654 Citations1980William Joseph Masek, Michael S. Paterson
An algorithm is described for computing the edit distance between two strings of length n and m, n ⪖ m, which requires O(n · max(1, mlog n) steps whenever the costs of edit operations are integral multiples of a single positive real number and the alphabet for the strings is finite.
SIAM Journal on ComputingOn Finding Lowest Common Ancestors: Simplification and Parallelization
535 Citations1988Baruch Schieber, Uzi Vishkin
DSpace@MIT (Massachusetts Institute of Technology)STRING-MATCHING AND OTHER PRODUCTS
397 Citations1974Manuela Fischer, Mike Paterson
By exploiting the formal similarity of string-matching with integer multiplication, a new algorithm has been obtained with a running time which is only slightly worse than linear.
Journal of AlgorithmsFinding approximate patterns in strings
384 Citations1985Esko Ukkonen
An algorithm is presented to construct a deterministic finite-state automaton that solves the problem of locating in any string a substring whose edit distance from p is at most a given constant t.
Parallel merge sort
363 Citations1986Richard Cole
A parallel implementation of merge sort on a CREW PRAM that uses n processors and O(logn) time; the constant in the running time is small.
SIAM Journal on ComputingGeneralized String Matching
310 Citations1987Karl Abrahamson
A generalization of string matching, in which the pattern is a sequence of pattern elements, each compatible with a set of symbols, is investigated, which shows that generalized string matching requires a time-space product of $\Omega ({{n^2 } / {\log n}})$ on a powerful model of computation, when the alphabet is restricted to n symbols.
Combinatorial Algorithms on Words
288 Citations1985Alberto Apostolico, Zvi Galil
The average-case Cost of the Brute force and the Knuth-Morris-Pratt String Matching Algorithm are compared and the Mellin integral Transform in the Analysis of Algorithms is compared.
The Myriad Virtues of Subword Trees
275 Citations1985Alberto Apostolico
AlgorithmicaThe longest common subsequence problem revisited
224 Citations1987Alberto Apostolico, Célia Fonseca Guerra
This paper re-examines, in a unified framework, two classic approaches to the problem of finding a longest common subsequence (LCS) of two strings, and proposes faster implementations for both.
AlgorithmicaParallel construction of a suffix tree with applications
170 Citations1988Alberto Apostolico, Costa S. Iliopoulos +3 more
This paper presents a CRCW parallel RAM algorithm that constructs the suffix tree associated with a string ofn symbols inO(logn) time withn processors that requires Θ(n2) space.
Lecture notes in computer scienceOn approximate string matching
140 Citations1983Esko Ukkonen
An algorithm is given for computing the edit distance as well as the corresponding sequence of editing steps between two strings a1a2...am and b1b2...bn, which is a considerable improvement over the best previously known algorithm that needs time and space 0(mn).
Theoretical Computer ScienceEfficient string matching with k mismatches
135 Citations1986Gad M. Landau, Uzi Vishkin
An algorithm for finding all occurrences of the pattern in the text, each with at most k mismatches, runs in O( k ( m log m + n )) time.
ACM SIGACT NewsImproved string matching with k mismatches
112 Citations1986Zvi Galil, Raffaele Giancarlo
A compact version of the authors' algorithm for string matching with k mismatches, achieving a time performance of 0(mlogm+kn) for general alphabets and of 0 (m+ Kn) for alphabet s whose size is fixed.
Efficient string matching in the presence of errors
76 Citations1985Gad M. Landau, Uzi Vishkin
An algorithm for finding all occurrences of the pattern in the text, each with at most k mismatches (superfluous characters in either the text or the pattern are not allowed), which runs in O(k(m logm + n)) time.
Open Problems in Stringology
60 Citations1985Zvi Galil
Lecture notes in computer scienceOn finding lowest common ancestors: Simplification and parallelization
49 Citations1988Baruch Schieber, Uzi Vishkin
A linear time and space preprocessing algorithm that enables us to answer each query in $O(1)$ time, as in Harel and Tarjan, which has the advantage of being simple and easily parallelizable.
Journal of the ACMAn Efficient General-Purpose Parallel Computer
42 Citations1983Zvi Galil, Wolfgang J. Paul
The main result is the construction of a universal parallel machine that can simulate every reasonable parallel machine with only a small loss of time and with essentially the same number of processors.
Lecture notes in computer scienceParallel construction of a suffix tree
25 Citations1987Gad M. Landau, Baruch Schieber +1 more
This work presents a parallel algorithm for constructing a suffix tree in O(log n) time and uses n processors and presents applications for designing efficient parallel algorithms for several string problems.
Optimal Factor Transducers
18 Citations1985Maxime Crochemore
It is shown that automata theory unifies the two approaches of Knuth-Morris-Pratt and Weiner andives a simple and efficient alsorithm to construct the structure, a sequential transducer, underlyins Weiner’s method.
Theoretical Computer ScienceParallel string matching with k mismatches
18 Citations1987Zvi Galil, Raffaele Giancarlo
Two improved algorithms for string matching with k mismatches are presented, one based on fast integer multiplication algorithms whereas the other follows more closely classic string-matching techniques.