Computing discriminating and generic words - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

Computing discriminating and generic words

Résumé

We study the following three problems of computing generic or discriminating words for a given collection of documents. Given a pattern P and a threshold d, we want to report (i) all longest extensions of P which occur in at least d documents, (ii) all shortest extensions of P which occur in less than d documents, and (iii) all shortest extensions of P which occur only in d selected documents. For these problems, we propose efficient algorithms based on suffix trees and using advanced data structure techniques. For problem (i), we propose an optimal solution with constant running time per output word.
Fichier principal
Vignette du fichier
main.pdf (156.03 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00789986 , version 1 (19-02-2013)

Identifiants

Citer

Gregory Kucherov, Yakov Nekrich, Tatiana Starikovskaya. Computing discriminating and generic words. String Processing and Information Retrieval, Oct 2012, Cartagena de Indias, Colombia. pp.307-317, ⟨10.1007/978-3-642-34109-0_32⟩. ⟨hal-00789986⟩
103 Consultations
299 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More