File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: Approximate string matching using compressed suffix arrays
  • Basic View
  • Metadata View
  • XML View
TitleApproximate string matching using compressed suffix arrays
 
AuthorsHuynh, TND2
Hon, WK2
Lam, TW1
Sung, WK1
 
Issue Date2004
 
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
CitationLecture 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?]
 
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.
 
ISSN0302-9743
2013 SCImago Journal Rankings: 0.310
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorHuynh, TND
 
dc.contributor.authorHon, WK
 
dc.contributor.authorLam, TW
 
dc.contributor.authorSung, WK
 
dc.date.accessioned2010-09-06T09:52:48Z
 
dc.date.available2010-09-06T09:52:48Z
 
dc.date.issued2004
 
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.
 
dc.description.naturelink_to_subscribed_fulltext
 
dc.identifier.citationLecture 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?]
 
dc.identifier.epage444
 
dc.identifier.hkuros130777
 
dc.identifier.hkuros107880
 
dc.identifier.issn0302-9743
2013 SCImago Journal Rankings: 0.310
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-35048848454
 
dc.identifier.spage434
 
dc.identifier.urihttp://hdl.handle.net/10722/89134
 
dc.identifier.volume3109
 
dc.languageeng
 
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
dc.publisher.placeGermany
 
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
 
dc.relation.referencesReferences in Scopus
 
dc.rightsTheoretical Computer Science. Copyright © Elsevier BV.
 
dc.titleApproximate string matching using compressed suffix arrays
 
dc.typeArticle
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Huynh, TND</contributor.author>
<contributor.author>Hon, WK</contributor.author>
<contributor.author>Lam, TW</contributor.author>
<contributor.author>Sung, WK</contributor.author>
<date.accessioned>2010-09-06T09:52:48Z</date.accessioned>
<date.available>2010-09-06T09:52:48Z</date.available>
<date.issued>2004</date.issued>
<identifier.citation>Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3109, p. 434-444</identifier.citation>
<identifier.issn>0302-9743</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/89134</identifier.uri>
<description.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 &#8805; 1. &#169; Springer-Verlag 2004.</description.abstract>
<language>eng</language>
<publisher>Springer Verlag. The Journal&apos;s web site is located at http://springerlink.com/content/105633/</publisher>
<relation.ispartof>Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</relation.ispartof>
<rights>Theoretical Computer Science. Copyright &#169; Elsevier BV.</rights>
<title>Approximate string matching using compressed suffix arrays</title>
<type>Article</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=0304-3975&amp;volume=352:1-3&amp;spage=240&amp;epage=249&amp;date=2006&amp;atitle=Approximate+string+matching+using+compressed+suffix+arrays</identifier.openurl>
<description.nature>link_to_subscribed_fulltext</description.nature>
<identifier.scopus>eid_2-s2.0-35048848454</identifier.scopus>
<identifier.hkuros>130777</identifier.hkuros>
<identifier.hkuros>107880</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-35048848454&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>3109</identifier.volume>
<identifier.spage>434</identifier.spage>
<identifier.epage>444</identifier.epage>
<publisher.place>Germany</publisher.place>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. National University of Singapore