**Article:**Approximate string matching using compressed suffix arrays

Title | Approximate string matching using compressed suffix arrays |
---|---|

Authors | Huynh, TND2 Hon, WK2 Lam, TW1 Sung, WK1 |

Issue Date | 2004 |

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), 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. |

ISSN | 0302-9743 2012 SCImago Journal Rankings: 0.332 |

References | References in Scopus |

DC Field | Value |
---|---|

dc.contributor.author | Huynh, TND |

dc.contributor.author | Hon, WK |

dc.contributor.author | Lam, TW |

dc.contributor.author | Sung, WK |

dc.date.accessioned | 2010-09-06T09:52:48Z |

dc.date.available | 2010-09-06T09:52:48Z |

dc.date.issued | 2004 |

dc.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 ≥ 1. © Springer-Verlag 2004. |

dc.description.nature | Link_to_subscribed_fulltext |

dc.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 [How to Cite?] |

dc.identifier.epage | 444 |

dc.identifier.hkuros | 130777 |

dc.identifier.issn | 0302-9743 2012 SCImago Journal Rankings: 0.332 |

dc.identifier.openurl | |

dc.identifier.scopus | eid_2-s2.0-35048848454 |

dc.identifier.spage | 434 |

dc.identifier.uri | http://hdl.handle.net/10722/89134 |

dc.identifier.volume | 3109 |

dc.language | eng |

dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |

dc.publisher.place | Germany |

dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

dc.relation.references | References in Scopus |

dc.rights | Theoretical Computer Science. Copyright © Elsevier BV. |

dc.title | Approximate string matching using compressed suffix arrays |

dc.type | Article |

<?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 ≥ 1. © Springer-Verlag 2004.</description.abstract> <language>eng</language> <publisher>Springer Verlag. The Journal'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 © 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&issn=0304-3975&volume=352:1-3&spage=240&epage=249&date=2006&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> <relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-35048848454&selection=ref&src=s&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

- The University of Hong Kong
- National University of Singapore