Efficient randomized dictionary matching algorithms

Amihood Amir; Martin Farach; Yossi Matias

doi:10.1007/3-540-56024-6_21

Efficient randomized dictionary matching algorithms

Amihood Amir, Martin Farach, Yossi Matias

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The standard string matching problem involves finding all occurrences of a single pattern in a single text. While this approach works well in many application areas, there are some domains in which it is more appropriate to deal with dictionaries of patterns. A dictionary is a set of patterns; the goal of dictionary matching is to find all dictionary patterns in a given text, simultaneously. In string matching, randomized algorithms have primarily made use of randomized hashing functions which convert strings into “signatures” or “finger prints”. We explore the use of finger prints in conjunction with other randomized and deterministic techniques and data structures. We present several new algorithms for dictionary matching, along with parallel algorithms which are simpler of more efficient than previously known algorithms.

Original language	English (US)
Title of host publication	Combinatorial Pattern Matching - 3rd Annual Symposium, Proceedings
Editors	Alberto Apostolico, Maxime Crochemore, Zvi Galil, Zvi Galil, Udi Manber
Publisher	Springer Verlag
Pages	262-275
Number of pages	14
ISBN (Print)	9783540560241
DOIs	https://doi.org/10.1007/3-540-56024-6_21
State	Published - 1992
Event	3rd Annual Symposium on Combinatorial Pattern Matching, 1992 - Tucson, United States Duration: Apr 29 1992 → May 1 1992

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	644 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	3rd Annual Symposium on Combinatorial Pattern Matching, 1992
Country/Territory	United States
City	Tucson
Period	4/29/92 → 5/1/92

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-56024-6_21

Cite this

Amir, A., Farach, M., & Matias, Y. (1992). Efficient randomized dictionary matching algorithms. In A. Apostolico, M. Crochemore, Z. Galil, Z. Galil, & U. Manber (Eds.), Combinatorial Pattern Matching - 3rd Annual Symposium, Proceedings (pp. 262-275). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 644 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-56024-6_21

Efficient randomized dictionary matching algorithms. / Amir, Amihood; Farach, Martin; Matias, Yossi.
Combinatorial Pattern Matching - 3rd Annual Symposium, Proceedings. ed. / Alberto Apostolico; Maxime Crochemore; Zvi Galil; Zvi Galil; Udi Manber. Springer Verlag, 1992. p. 262-275 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 644 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Amir, A, Farach, M & Matias, Y 1992, Efficient randomized dictionary matching algorithms. in A Apostolico, M Crochemore, Z Galil, Z Galil & U Manber (eds), Combinatorial Pattern Matching - 3rd Annual Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 644 LNCS, Springer Verlag, pp. 262-275, 3rd Annual Symposium on Combinatorial Pattern Matching, 1992, Tucson, United States, 4/29/92. https://doi.org/10.1007/3-540-56024-6_21

Amir A, Farach M, Matias Y. Efficient randomized dictionary matching algorithms. In Apostolico A, Crochemore M, Galil Z, Galil Z, Manber U, editors, Combinatorial Pattern Matching - 3rd Annual Symposium, Proceedings. Springer Verlag. 1992. p. 262-275. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-56024-6_21

Amir, Amihood ; Farach, Martin ; Matias, Yossi. / Efficient randomized dictionary matching algorithms. Combinatorial Pattern Matching - 3rd Annual Symposium, Proceedings. editor / Alberto Apostolico ; Maxime Crochemore ; Zvi Galil ; Zvi Galil ; Udi Manber. Springer Verlag, 1992. pp. 262-275 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{30e5a6a8adf442f4b789e66be2e052a9,

title = "Efficient randomized dictionary matching algorithms",

abstract = "The standard string matching problem involves finding all occurrences of a single pattern in a single text. While this approach works well in many application areas, there are some domains in which it is more appropriate to deal with dictionaries of patterns. A dictionary is a set of patterns; the goal of dictionary matching is to find all dictionary patterns in a given text, simultaneously. In string matching, randomized algorithms have primarily made use of randomized hashing functions which convert strings into “signatures” or “finger prints”. We explore the use of finger prints in conjunction with other randomized and deterministic techniques and data structures. We present several new algorithms for dictionary matching, along with parallel algorithms which are simpler of more efficient than previously known algorithms.",

author = "Amihood Amir and Martin Farach and Yossi Matias",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1992.; 3rd Annual Symposium on Combinatorial Pattern Matching, 1992 ; Conference date: 29-04-1992 Through 01-05-1992",

year = "1992",

doi = "10.1007/3-540-56024-6_21",

language = "English (US)",

isbn = "9783540560241",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "262--275",

editor = "Alberto Apostolico and Maxime Crochemore and Zvi Galil and Zvi Galil and Udi Manber",

booktitle = "Combinatorial Pattern Matching - 3rd Annual Symposium, Proceedings",

}

TY - GEN

T1 - Efficient randomized dictionary matching algorithms

AU - Amir, Amihood

AU - Farach, Martin

AU - Matias, Yossi

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1992.

PY - 1992

Y1 - 1992

N2 - The standard string matching problem involves finding all occurrences of a single pattern in a single text. While this approach works well in many application areas, there are some domains in which it is more appropriate to deal with dictionaries of patterns. A dictionary is a set of patterns; the goal of dictionary matching is to find all dictionary patterns in a given text, simultaneously. In string matching, randomized algorithms have primarily made use of randomized hashing functions which convert strings into “signatures” or “finger prints”. We explore the use of finger prints in conjunction with other randomized and deterministic techniques and data structures. We present several new algorithms for dictionary matching, along with parallel algorithms which are simpler of more efficient than previously known algorithms.

AB - The standard string matching problem involves finding all occurrences of a single pattern in a single text. While this approach works well in many application areas, there are some domains in which it is more appropriate to deal with dictionaries of patterns. A dictionary is a set of patterns; the goal of dictionary matching is to find all dictionary patterns in a given text, simultaneously. In string matching, randomized algorithms have primarily made use of randomized hashing functions which convert strings into “signatures” or “finger prints”. We explore the use of finger prints in conjunction with other randomized and deterministic techniques and data structures. We present several new algorithms for dictionary matching, along with parallel algorithms which are simpler of more efficient than previously known algorithms.

UR - http://www.scopus.com/inward/record.url?scp=85015487998&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85015487998&partnerID=8YFLogxK

U2 - 10.1007/3-540-56024-6_21

DO - 10.1007/3-540-56024-6_21

M3 - Conference contribution

AN - SCOPUS:85015487998

SN - 9783540560241

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 262

EP - 275

BT - Combinatorial Pattern Matching - 3rd Annual Symposium, Proceedings

A2 - Apostolico, Alberto

A2 - Crochemore, Maxime

A2 - Galil, Zvi

A2 - Manber, Udi

PB - Springer Verlag

T2 - 3rd Annual Symposium on Combinatorial Pattern Matching, 1992

Y2 - 29 April 1992 through 1 May 1992

ER -

Efficient randomized dictionary matching algorithms

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this