File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Approximate string matching using compressed suffix arrays

TitleApproximate string matching using compressed suffix arrays
Authors
Issue Date2004
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), 2004, v. 3109, p. 434-444 How to Cite?
Abstract
Let T be a text of length n and P be a pattern of length m, both strings over a fixed finite alphabet A. The k-difference (k-mismatch, respectively) problem is to find all occurrences of P in T that have edit distance (Hamming distance, respectively) at most k from P. In this paper we investigate a well-studied case in which k = 1 and T is fixed and preprocessed into an indexing data structure so that any pattern query can be answered faster [16-19]. This paper gives a solution using O(n) bits indexing data structure with O(m log 2 n) query time. To the best of our knowledge, this is the first result which requires linear indexing space. The results can be extended for the fc-difference problem with k ≥ 1. © Springer-Verlag 2004.
Persistent Identifierhttp://hdl.handle.net/10722/89134
ISSN
2013 SCImago Journal Rankings: 0.310
References

 

Author Affiliations
  1. The University of Hong Kong
  2. National University of Singapore
DC FieldValueLanguage
dc.contributor.authorHuynh, TNDen_HK
dc.contributor.authorHon, WKen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorSung, WKen_HK
dc.date.accessioned2010-09-06T09:52:48Z-
dc.date.available2010-09-06T09:52:48Z-
dc.date.issued2004en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3109, p. 434-444en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89134-
dc.description.abstractLet T be a text of length n and P be a pattern of length m, both strings over a fixed finite alphabet A. The k-difference (k-mismatch, respectively) problem is to find all occurrences of P in T that have edit distance (Hamming distance, respectively) at most k from P. In this paper we investigate a well-studied case in which k = 1 and T is fixed and preprocessed into an indexing data structure so that any pattern query can be answered faster [16-19]. This paper gives a solution using O(n) bits indexing data structure with O(m log 2 n) query time. To the best of our knowledge, this is the first result which requires linear indexing space. The results can be extended for the fc-difference problem with k ≥ 1. © Springer-Verlag 2004.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.rightsTheoretical Computer Science. Copyright © Elsevier BV.en_HK
dc.titleApproximate string matching using compressed suffix arraysen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0304-3975&volume=352:1-3&spage=240&epage=249&date=2006&atitle=Approximate+string+matching+using+compressed+suffix+arraysen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-35048848454en_HK
dc.identifier.hkuros130777en_HK
dc.identifier.hkuros107880-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-35048848454&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3109en_HK
dc.identifier.spage434en_HK
dc.identifier.epage444en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridHuynh, TND=8846778300en_HK
dc.identifier.scopusauthoridHon, WK=7004282818en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridSung, WK=13310059700en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats