HAL - INRIA :: [inria-00179719, version 1] Indexing gapped-factors using a tree

inria-00179719, version 1

Indexing gapped-factors using a tree

Pierre Peterlongo ()^a^, 1, Julien Allali ()^b^, 2, Marie-France Sagot ()^a^, 3

International Journal of Foundation of Computer Science (2007)

Abstract: We present a data structure to index a speciﬁc kind of factors, that is of substrings, called gapped-factors. A gapped-factor is a factor containing a gap that is ignored during the indexation. The data structure presented is based on the suﬃx tree and indexes all the gapped-factors of a text with a ﬁxed size of gap, and only those. The construction of this data structure is done online in linear time and space. Such a data structure may play an important role in various pattern matching and motif inference problems, for instance in text ﬁltration.

a – INRIA
b – CNRS
1: SYMBIOSE (INRIA - IRISA)
CNRS : UMR6074 – INRIA – INSA Rennes – Université de Rennes 1
2: Laboratoire Bordelais de Recherche en Informatique (LaBRI)
CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – Ecole Nationale Supérieure d'Electronique, Informatique et Radiocommunications de Bordeaux – Université Victor Segalen - Bordeaux II
3: HELIX (INRIA Rhône-Alpes)
INRIA – CNRS : UMR5558 – Université Claude Bernard - Lyon I

inria-00179719, version 1
http://hal.inria.fr/inria-00179719
oai:hal.inria.fr:inria-00179719
From: Pierre Peterlongo <>
Submitted on: Wednesday, 24 October 2007 12:19:38
Updated on: Wednesday, 24 October 2007 14:18:48

See detailed view

Associated documents

PDF :

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles in peer-reviewed journal</head>
<biblStruct type="article" xml:id="inria-00179719"><analytic>
<author><persName><forename>Pierre</forename><surname>Peterlongo</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA - IRISA</orgName>
<orgName type="team">SYMBIOSE</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6074</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">INSA Rennes</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<author><persName><forename>Julien</forename><surname>Allali</surname></persName>
<affiliation>
<orgName type="laboratory">LaBRI</orgName>
<orgName type="team">Laboratoire Bordelais de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">Ecole Nationale Supérieure d'Electronique, Informatique et Radiocommunications de Bordeaux</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
</affiliation>
</author>
<author><persName><forename>Marie-France</forename><surname>Sagot</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Rhône-Alpes</orgName>
<orgName type="team">HELIX</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR5558</orgName>
<orgName type="institution">Université Claude Bernard - Lyon I</orgName>
</affiliation>
</author>
<title type="main" level="a">Indexing gapped-factors using a tree</title></analytic><monogr><title level="j" type="main">International Journal of Foundation of Computer Science</title><imprint><publisher>World Scientific</publisher><biblScope type="publicationDate">2007-00-00</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00179719</idno><idno type="HALFile">http://hal.inria.fr/inria-00179719/PDF/biFactorTree_IJFCS_erratum.pdf</idno></biblStruct>
</listBibl>
</listBibl>