2D dictionary matching in small space
Item
-
Title
-
2D dictionary matching in small space
-
Identifier
-
d_2009_2013:2113026915fa:11342
-
identifier
-
11670
-
Creator
-
Neuburger, Shoshana,
-
Contributor
-
Dina Sokol
-
Date
-
2012
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer science | algorithms | dictionary matching | pattern matching | small-space
-
Abstract
-
The dictionary matching problem seeks all locations in a given text that match any of the patterns in a given dictionary. Efficient algorithms for dictionary matching scan the text once, searching for all patterns simultaneously. There are many scenarios in which storage capacity is limited or the data sets are exceedingly large. The added constraint of performing efficient dictionary matching using little or no extra space is a challenging and practical problem. This thesis focuses on the problem of performing dictionary matching on two-dimensional data in small space. We have developed the first efficient algorithms for succinct 2D dictionary matching in both static and dynamically changing data. Although time and space optimal dictionary matching algorithms for one-dimensional data have recently been developed, they have not yet been implemented. Since our two-dimensional algorithms employ one-dimensional dictionary matching, we created software to solve one-dimensional dictionary matching in small space. This is a first step towards developing software for succinct dictionary matching in two-dimensional data.
-
Type
-
dissertation
-
Source
-
2009_2013.csv
-
degree
-
Ph.D.
-
Program
-
Computer Science
