File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Improved approximate string matching using compressed suffix data structures

TitleImproved approximate string matching using compressed suffix data structures
Authors
Issue Date2005
PublisherSpringer 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. 339-348 How to Cite?
AbstractApproximate 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 1-mismatch and 1-difference 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 1-mismatch (or 1-difference) 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 k-mismatch (and the k-difference) problem in O(|A|km 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. © Springer-Verlag Berlin Heidelberg 2005.
Persistent Identifierhttp://hdl.handle.net/10722/60628
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_HK
dc.contributor.authorSung, WKen_HK
dc.contributor.authorWong, SSen_HK
dc.date.accessioned2010-05-31T04:15:16Z-
dc.date.available2010-05-31T04:15:16Z-
dc.date.issued2005en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2005, v. 3827 LNCS, p. 339-348en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/60628-
dc.description.abstractApproximate 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 1-mismatch and 1-difference 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 1-mismatch (or 1-difference) 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 k-mismatch (and the k-difference) problem in O(|A|km 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. © Springer-Verlag Berlin Heidelberg 2005.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.titleImproved approximate string matching using compressed suffix data structuresen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0178-4617&volume=51&issue=3&spage=298&epage=314&date=2008&atitle=Improved+Approximate+String+Matching+Using+Compressed+Suffix+Data+Structuresen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/11602613_35en_HK
dc.identifier.scopuseid_2-s2.0-33744960824en_HK
dc.identifier.hkuros146734en_HK
dc.identifier.hkuros124239-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33744960824&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3827 LNCSen_HK
dc.identifier.spage339en_HK
dc.identifier.epage348en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridSung, WK=13310059700en_HK
dc.identifier.scopusauthoridWong, SS=8439889300en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats