Algorithmes de recherche

Problemes de recherche

Dans la plupart des problemes de recherche d'occurrences d'une lettre a dans un mot x, le resultat est :

• soit un booleen, valant VRAI si cette occurrence de a apparait dans x et FAUX sinon ;
• soit un entier, dont la valeur est l'indice de l'occurrence si a apparait dans x, soit le symbole NEANT.

Problemes etudies

Operations representatives

Comparaisons de lettres et acces aux lettres des mots.

premmin(x)

// @pre: aucune
// @post: j = premmin(x)
if (|x| == 0) {
    j = NEANT;
} else {
    j = 0;
    k = 1;
    // @invariant: 1 <= k <= |x| && j = premmin(x[0..k-1])
    // @variant: k
    while (k < |x|) {
        if (x[k] < x[j]) j = k;
        k = k + 1;
    }
}

Analyse

• Comparaisons : 0 si |x| = 0, |x|-1 sinon
• Complexite temporelle : Theta(|x|)
• Optimalite : Optimal en nombre de comparaisons

Utilisations

• Recherche du minimum
• Tri par selection du minimum

mocc(a, x)

// @pre: aucune
// @post: s = mocc(a, x)
s = mot_vide;
k = 0;
// @invariant: 0 <= k <= |x| && s = mocc(a, x[0..k-1])
// @variant: k
while (k < |x|) {
    if (x[k] == a) s = concat(s, k);
    k = k + 1;
}

Analyse

• Tours de boucle = |x|
• 1 comparaison par tour
• Complexite : Theta(|x|)

prem(a, x) — Cas general

// @pre: aucune
// @post: k = prem(a, x)
k = 0;
// @invariant: 0 <= k <= |x| && prem(a, x[0..k-1]) = NEANT
// @variant: k
while (k < |x| && x[k] != a) {
    k = k + 1;
}
if (k == |x|) k = NEANT;

Complexite : O(|x|)

Cas d'un mot croissant

Si x est croissant, arreter des que x[k] >= a.

Recherche par dichotomie

Hypotheses : acces direct + x croissant
Complexite : Theta(ln|x|)

Recherche efficace d'un mot dans un texte

Tableau des decalages

d[a] = min({m} U {m-1-j | 0 <= j < m-1 && a = x[j]})

Algorithme

// @pre: m >= 1
// @post: s = mgocc(x, y)
s = mot_vide;
if (m <= n) {
    d = tableau_decalages(x);
    k = 0;
    while (k < n - m + 1) {
        if (y[k..k+m-1] == x) s = concat(s, k);
        k = k + d[y[k + m - 1]];
    }
}

Complexite

• Temporelle : Omega(c+m+n/m), O(c+mn)
• Spatiale : Theta(c)
• Moyenne : Theta(c+m+n/c)

Fonctions de recherche en C

<string.h>

void *memchr(const void *s, int c, size_t n);
char *strchr(const char *s, int c);
char *strrchr(const char *s, int c);
int memcmp(const void *s1, const void *s2, size_t n);
int strcmp(const char *s1, const char *s2);
char *strstr(const char *s1, const char *s2);

<stdlib.h> — bsearch

void *bsearch(const void *key, const void *base, size_t nmemb,
              size_t size, int (*compar)(const void *, const void *));

Recherche par dichotomie dans un tableau ordonne.