Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/13083
Title: String matching and indexing with suffix data structures
Authors: WONG SWEE SEONG
Keywords: suffix tree, suffix array, compressed suffix data structures, string indexing, string matching, sequence alignment search
Issue Date: 7-Feb-2008
Source: WONG SWEE SEONG (2008-02-07). String matching and indexing with suffix data structures. ScholarBank@NUS Repository.
Abstract: This thesis studies methods for indexing a text so that the occurrences of any given query string in the text can be located efficiently. An occurrence or match may be imprecise, allowing some deviations from the actual query. This gives rise to a family of interesting string matching problems like exact and approximate string matching, and sequence alignment. We consider two different computing models to handle the problem. The first is to compress the index so that it is small enough to be stored in the main memory. Another computing model is to make use of secondary disk, where the index resides on the hard disk. Blocks or chunks of the index are fetched into memory upon request. In this case, we are concern with the number of IO accesses to perform string search on the index. In both scenarios, it is essential to have efficient computation algorithms to support various string search. Mixed computing model is also possible with multiple levels of indexing, combining both in-memory and disk-based indices.
URI: http://scholarbank.nus.edu.sg/handle/10635/13083
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
thesis.pdf556.73 kBAdobe PDF

OPEN

NoneView/Download

Page view(s)

212
checked on Dec 11, 2017

Download(s)

97
checked on Dec 11, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.