Complexité de la recherche de motifs dans un texte aléatoire - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Thèse Année : 2019

The Complexity of the Multiple Pattern Matching Problem for Random Strings

Complexité de la recherche de motifs dans un texte aléatoire

Résumé

Let Ʃ be an alphabet of size s ⩾2. A pattern or dictionary is a set of words written with letters from Ʃ. The multiple pattern-matching problem consist in finding all occurrences of the words of a given dictionary in a text. In this thesis, we focuse on the estimation of the complexity of the exact or appromate multiple pattern-matching problem in termes of minimum ratio of text to be read in a random text of lenght n in order to find all the exact or approximate occurrences of the words of an arbitrary dictionary. This complexity is linked to the notion of content r = (rᵢ)I ≥1 of a dictionary, i.e., the vector of integers whose i-th entry rᵢ is the number of words of lenght i int the dictionary. On one hand, we prove that the complexity of the exact multiple pattern-matching problem for a random dictionary of content r when at most k editiong errors (insertion, deletion, substitution) are allowed is in Ɵ (αsΦ(r)+ βs K+1/ᵐmᵢn) with Φ(r)=1/ks (max/m In(smr m)/m + 1/2ˢᵐmᵢn), and αs, βs, et ks depend only on the size s of the alphabet. For the exact pattern-matching problem as well as for the approximate pattern-matching problem, the steps of proof are the same. For the upper bounds, algorithms that reached the required complexity for dictionary of content r are presented and analyzed. The lower bounds are established thanks to counting arguments.
Soit Ʃ un alphabet à s ⩾2 symboles. Un motif ou dictionnaire est un ensemble de mots écrits sur l'alphabet Ʃ. Le problème de la recherche de motifs consiste à trouver toutes les occurrences des mots d'un dictionnaire donné dans un texte. Dans cette thèse, on s'intéresse plus précisément à établir la complexité de la recherche exacte ou approchée de motifs en termes de proportion de texte à lire dans un texte aléatoire de longueur n pour trouver toutes les occurrences exactes ou approchées des mots d'un dictionnaire arbitraire. Cette complexité est liée à la notion de contenu r = (rᵢ)I ≥1 d'un dictionnaire, i.e. le vecteur d'entiers dont le i-ème coefficient rᵢ est le nombre de mots de longueur i du dictionnaire. D'une part, on montre que la complexité de la recherche exacte pour un dictionnaire aléatoire de contenu r est en Ɵ (max sur m, In(ˢᵐrm) sur m + 1 sur 2ˢᵐmᵢn) où ᵐmᵢn est la longueur du mot le plus court du dictionnaire. Ce résultat est une généralisation de celui établi par Yao en 1979 dans le cas d'un dictionnaire réduit à un seul mot. D'autre part, on établit que la complexité de la recherche approchée pour un dictionnaire aléatoire de contenu r, et en autorisant au plus k erreurs d'édition (suppression, insertion, substitution) est en Ɵ (αsΦ(r)+ βs K+1 sur ᵐmᵢn) où Φ(r)=1 sur ks (max sur m In(ˢᵐr m) sur m + 1 sur 2ˢᵐmᵢn), et αs, βs, et ks dépendent uniquement de la taille s de l'alphabet.Que ce soit pour la recherche exacte ou la recherche approchée, l'approche est similaire. Pour établir les bornes supérieures, des algorithmes ayant la complexité cherchée pour n'importe quel dictionnaire de contenu r sont présentés et analysés. Les bornes inférieures sont établies par des arguments de comptage.
Fichier principal
Vignette du fichier
edgalilee_th_2019_rakotoarimalala.pdf (64.91 Mo) Télécharger le fichier
Origine : Version validée par le jury (STAR)

Dates et versions

tel-02947291 , version 1 (23-09-2020)

Identifiants

  • HAL Id : tel-02947291 , version 1

Citer

Tsinjo Tony Rakotoarimalala. Complexité de la recherche de motifs dans un texte aléatoire. Complexité [cs.CC]. Université Sorbonne Paris Cité, 2019. Français. ⟨NNT : 2019USPCD015⟩. ⟨tel-02947291⟩
201 Consultations
8 Téléchargements

Partager

Gmail Facebook X LinkedIn More