Two-dimensional dictionary matching

Amihood Amir; Martin Farach

doi:10.1016/0020-0190(92)90206-B

Two-dimensional dictionary matching

Amihood Amir, Martin Farach

Research output: Contribution to journal › Article › peer-review

Abstract

Most traditional pattern matching algorithms solve the problem of finding all occurrences of a given pattern string P in a given text T. Another important paradigm is the dictionary matching problem. Let D={P₁,...,P_k} be the dictionary. We seek the locations of all dictionary patterns that appear in a given text T. Previous dictionary matching algorithms have all involved exact matching of a set of strings. In this paper, we present an algorithm for the Two-Dimensional Dictionary Problem. The two-dimensional dictionary problem is that of finding each occurrence of a set of two-dimensional patterns in a text. Our algorithm runs in time O(|D|log k) preprocessing, O(|T|log k) text processing.

Original language	English (US)
Pages (from-to)	233-239
Number of pages	7
Journal	Information Processing Letters
Volume	44
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(92)90206-B
State	Published - Dec 21 1992

Keywords

Algorithms
analysis of algorithms
dictionary matching
pattern matching
text processing

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/0020-0190(92)90206-B

Cite this

@article{decbbd235db04911abef5dea98517ffe,

title = "Two-dimensional dictionary matching",

abstract = "Most traditional pattern matching algorithms solve the problem of finding all occurrences of a given pattern string P in a given text T. Another important paradigm is the dictionary matching problem. Let D={P1,...,Pk} be the dictionary. We seek the locations of all dictionary patterns that appear in a given text T. Previous dictionary matching algorithms have all involved exact matching of a set of strings. In this paper, we present an algorithm for the Two-Dimensional Dictionary Problem. The two-dimensional dictionary problem is that of finding each occurrence of a set of two-dimensional patterns in a text. Our algorithm runs in time O(|D|log k) preprocessing, O(|T|log k) text processing.",

keywords = "Algorithms, analysis of algorithms, dictionary matching, pattern matching, text processing",

author = "Amihood Amir and Martin Farach",

year = "1992",

month = dec,

day = "21",

doi = "10.1016/0020-0190(92)90206-B",

language = "English (US)",

volume = "44",

pages = "233--239",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Two-dimensional dictionary matching

AU - Amir, Amihood

AU - Farach, Martin

PY - 1992/12/21

Y1 - 1992/12/21

N2 - Most traditional pattern matching algorithms solve the problem of finding all occurrences of a given pattern string P in a given text T. Another important paradigm is the dictionary matching problem. Let D={P1,...,Pk} be the dictionary. We seek the locations of all dictionary patterns that appear in a given text T. Previous dictionary matching algorithms have all involved exact matching of a set of strings. In this paper, we present an algorithm for the Two-Dimensional Dictionary Problem. The two-dimensional dictionary problem is that of finding each occurrence of a set of two-dimensional patterns in a text. Our algorithm runs in time O(|D|log k) preprocessing, O(|T|log k) text processing.

AB - Most traditional pattern matching algorithms solve the problem of finding all occurrences of a given pattern string P in a given text T. Another important paradigm is the dictionary matching problem. Let D={P1,...,Pk} be the dictionary. We seek the locations of all dictionary patterns that appear in a given text T. Previous dictionary matching algorithms have all involved exact matching of a set of strings. In this paper, we present an algorithm for the Two-Dimensional Dictionary Problem. The two-dimensional dictionary problem is that of finding each occurrence of a set of two-dimensional patterns in a text. Our algorithm runs in time O(|D|log k) preprocessing, O(|T|log k) text processing.

KW - Algorithms

KW - analysis of algorithms

KW - dictionary matching

KW - pattern matching

KW - text processing

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

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

U2 - 10.1016/0020-0190(92)90206-B

DO - 10.1016/0020-0190(92)90206-B

M3 - Article

AN - SCOPUS:0001100107

SN - 0020-0190

VL - 44

SP - 233

EP - 239

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

Two-dimensional dictionary matching

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this