File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/11602613_35
 Scopus: eid_2s2.033744960824
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Article: Improved approximate string matching using compressed suffix data structures
Title  Improved approximate string matching using compressed suffix data structures 

Authors  
Issue Date  2005 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2005, v. 3827 LNCS, p. 339348 How to Cite? 
Abstract  Approximate string matching is about finding a given string pattern in a text by allowing some degree of errors. In this paper we present a space efficient data structure to solve the 1mismatch and 1difference problems. Given a text T of length n over a fixed alphabet A, we can preprocess T and give an O(n√log n)bit space data structure so that, for any query pattern P of length m, we can find all 1mismatch (or 1difference) occurrences of P in O(m log log n +occ) time, where occ is the number of occurrences. This is the fastest known query time given that the space of the data structure is o(n log2 n) bits. The space of our data structure can be further reduced to O(n) if we can afford a slow down factor of logεn, for 0 < ε ≤ 1. Furthermore, our solution can be generalized to solve the kmismatch (and the kdifference) problem in O(Akm k(k + log log n) + occ) and O(logε n(A kmk(k + log log n) + occ)) query time using an O(n√log n)bit and an O(n)bit indexing data structures, respectively. © SpringerVerlag Berlin Heidelberg 2005. 
Persistent Identifier  http://hdl.handle.net/10722/60628 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Lam, TW  en_HK 
dc.contributor.author  Sung, WK  en_HK 
dc.contributor.author  Wong, SS  en_HK 
dc.date.accessioned  20100531T04:15:16Z   
dc.date.available  20100531T04:15:16Z   
dc.date.issued  2005  en_HK 
dc.identifier.citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2005, v. 3827 LNCS, p. 339348  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/60628   
dc.description.abstract  Approximate string matching is about finding a given string pattern in a text by allowing some degree of errors. In this paper we present a space efficient data structure to solve the 1mismatch and 1difference problems. Given a text T of length n over a fixed alphabet A, we can preprocess T and give an O(n√log n)bit space data structure so that, for any query pattern P of length m, we can find all 1mismatch (or 1difference) occurrences of P in O(m log log n +occ) time, where occ is the number of occurrences. This is the fastest known query time given that the space of the data structure is o(n log2 n) bits. The space of our data structure can be further reduced to O(n) if we can afford a slow down factor of logεn, for 0 < ε ≤ 1. Furthermore, our solution can be generalized to solve the kmismatch (and the kdifference) problem in O(Akm k(k + log log n) + occ) and O(logε n(A kmk(k + log log n) + occ)) query time using an O(n√log n)bit and an O(n)bit indexing data structures, respectively. © SpringerVerlag Berlin Heidelberg 2005.  en_HK 
dc.language  eng  en_HK 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  en_HK 
dc.title  Improved approximate string matching using compressed suffix data structures  en_HK 
dc.type  Article  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=01784617&volume=51&issue=3&spage=298&epage=314&date=2008&atitle=Improved+Approximate+String+Matching+Using+Compressed+Suffix+Data+Structures  en_HK 
dc.identifier.email  Lam, TW:twlam@cs.hku.hk  en_HK 
dc.identifier.authority  Lam, TW=rp00135  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.doi  10.1007/11602613_35  en_HK 
dc.identifier.scopus  eid_2s2.033744960824  en_HK 
dc.identifier.hkuros  146734  en_HK 
dc.identifier.hkuros  124239   
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.033744960824&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  3827 LNCS  en_HK 
dc.identifier.spage  339  en_HK 
dc.identifier.epage  348  en_HK 
dc.publisher.place  Germany  en_HK 
dc.identifier.scopusauthorid  Lam, TW=7202523165  en_HK 
dc.identifier.scopusauthorid  Sung, WK=13310059700  en_HK 
dc.identifier.scopusauthorid  Wong, SS=8439889300  en_HK 