File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Space efficient indexes for string matching with don't cares
  • Basic View
  • Metadata View
  • XML View
TitleSpace efficient indexes for string matching with don't cares
 
AuthorsLam, TW1
Sung, WK2
Tam, SL1
Yiu, SM1
 
Issue Date2007
 
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), 2007, v. 4835 LNCS, p. 846-857 [How to Cite?]
 
AbstractGiven a text T of length n, the classical indexing problem for pattern matching is to build an index for T so that for any query pattern P, we can report efficiently all occurrences of P in T. Cole et al (2004) extended this problem to allow don't care characters (wildcards) in the text and pattern, and they gave the first index that supports efficient pattern matching. The space complexity of this index is linear in n (text length) but exponential in terms of the number of wildcards. Motivated by bioinformatics applications, we investigate indexes whose size depends on n only. In the literature, space efficient indexes for wildcard matching are known only for the special case when wildcards appear only in the pattern (Iliopoulos and Rahman, 2007); the space required is O(n). Not much has been heard for the case when wildcards appear in the text only, or in both the text and pattern. In this paper we give an O(n) space index to support efficient wildcard matching in all three cases. Our solution to the pattern-only case improves the matching time of the previous work tremendously in practice. In addition, our solution can be extended to handle optional wildcards, each of which can match zero or one character. © Springer-Verlag Berlin Heidelberg 2007.
 
ISSN0302-9743
2012 SCImago Journal Rankings: 0.332
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorLam, TW
 
dc.contributor.authorSung, WK
 
dc.contributor.authorTam, SL
 
dc.contributor.authorYiu, SM
 
dc.date.accessioned2010-09-25T14:54:30Z
 
dc.date.available2010-09-25T14:54:30Z
 
dc.date.issued2007
 
dc.description.abstractGiven a text T of length n, the classical indexing problem for pattern matching is to build an index for T so that for any query pattern P, we can report efficiently all occurrences of P in T. Cole et al (2004) extended this problem to allow don't care characters (wildcards) in the text and pattern, and they gave the first index that supports efficient pattern matching. The space complexity of this index is linear in n (text length) but exponential in terms of the number of wildcards. Motivated by bioinformatics applications, we investigate indexes whose size depends on n only. In the literature, space efficient indexes for wildcard matching are known only for the special case when wildcards appear only in the pattern (Iliopoulos and Rahman, 2007); the space required is O(n). Not much has been heard for the case when wildcards appear in the text only, or in both the text and pattern. In this paper we give an O(n) space index to support efficient wildcard matching in all three cases. Our solution to the pattern-only case improves the matching time of the previous work tremendously in practice. In addition, our solution can be extended to handle optional wildcards, each of which can match zero or one character. © Springer-Verlag Berlin Heidelberg 2007.
 
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), 2007, v. 4835 LNCS, p. 846-857 [How to Cite?]
 
dc.identifier.epage857
 
dc.identifier.hkuros146739
 
dc.identifier.issn0302-9743
2012 SCImago Journal Rankings: 0.332
 
dc.identifier.scopuseid_2-s2.0-38149062674
 
dc.identifier.spage846
 
dc.identifier.urihttp://hdl.handle.net/10722/93219
 
dc.identifier.volume4835 LNCS
 
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.titleSpace efficient indexes for string matching with don't cares
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Lam, TW</contributor.author>
<contributor.author>Sung, WK</contributor.author>
<contributor.author>Tam, SL</contributor.author>
<contributor.author>Yiu, SM</contributor.author>
<date.accessioned>2010-09-25T14:54:30Z</date.accessioned>
<date.available>2010-09-25T14:54:30Z</date.available>
<date.issued>2007</date.issued>
<identifier.citation>Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4835 LNCS, p. 846-857</identifier.citation>
<identifier.issn>0302-9743</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/93219</identifier.uri>
<description.abstract>Given a text T of length n, the classical indexing problem for pattern matching is to build an index for T so that for any query pattern P, we can report efficiently all occurrences of P in T. Cole et al (2004) extended this problem to allow don&apos;t care characters (wildcards) in the text and pattern, and they gave the first index that supports efficient pattern matching. The space complexity of this index is linear in n (text length) but exponential in terms of the number of wildcards. Motivated by bioinformatics applications, we investigate indexes whose size depends on n only. In the literature, space efficient indexes for wildcard matching are known only for the special case when wildcards appear only in the pattern (Iliopoulos and Rahman, 2007); the space required is O(n). Not much has been heard for the case when wildcards appear in the text only, or in both the text and pattern. In this paper we give an O(n) space index to support efficient wildcard matching in all three cases. Our solution to the pattern-only case improves the matching time of the previous work tremendously in practice. In addition, our solution can be extended to handle optional wildcards, each of which can match zero or one character. &#169; Springer-Verlag Berlin Heidelberg 2007.</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>
<title>Space efficient indexes for string matching with don&apos;t cares</title>
<type>Conference_Paper</type>
<description.nature>Link_to_subscribed_fulltext</description.nature>
<identifier.scopus>eid_2-s2.0-38149062674</identifier.scopus>
<identifier.hkuros>146739</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-38149062674&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>4835 LNCS</identifier.volume>
<identifier.spage>846</identifier.spage>
<identifier.epage>857</identifier.epage>
<publisher.place>Germany</publisher.place>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. National University of Singapore