28596 articles – 22090 Notices  [english version]

hal-00306572, version 1

The Gapped-Factor Tree

Pierre Peterlongo () 1, Julien Allali () 1, Marie-France Sagot 2, 3, 4

Prague Stringology Conference 2006 (2006) 182--196

Résumé : We present a data structure to index a specific 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 suffix tree and indexes all the gapped-factors of a text with a fixed 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 filtration.

  • 1 :  Laboratoire d'Informatique Gaspard-Monge (LIGM)
  • Université Paris-Est Marne-la-Vallée (UPEMLV) – ESIEE – Ecole des Ponts ParisTech – Fédération de Recherche Bézout – CNRS : UMR8049
  • 2 :  HELIX (INRIA Rhône-Alpes)
  • INRIA – CNRS : UMR5558 – Université Claude Bernard - Lyon I
  • 3 :  Laboratoire de Biométrie et Biologie Evolutive (LBBE)
  • Université Claude Bernard - Lyon I – CNRS : UMR5558 – INRIA
  • 4 :  Department of Computer Science (DCS)
  • King's College London
  • Domaine : Informatique/Autre
 
  • hal-00306572, version 1
  • http://hal.archives-ouvertes.fr/hal-00306572
  • oai:hal.archives-ouvertes.fr:hal-00306572
  • Contributeur : Julien Allali <>
  • Soumis le : Mercredi 14 Janvier 2009, 16:50:32
  • Dernière modification le : Mardi 10 Février 2009, 16:10:20