Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214

Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214

Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214

Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214

Boyer Moore en Rust

Fiche de l'exercice

La difficulté ici vient surtout de la gestion des chaînes de caractères par Rust. En effet, la chaîne est comme un tableau d'octets représentant les caractères en UTF8 de sorte qu'il est difficile de savoir quand un caractère sera codé par un octet et quand il sera codé par 2 octets ou plus. On ne peut dès lors pas atteindre les caractères directement par leur indice : Par exemple, dans "éléphant", le p est codé par un seul octet (caractère ASCII) mais à quelle position ? La réponse n'est pas 3 à cause des deux é qui nécessitent 2 octets. L'octet de p est donc à l'indice 5. Le problème est qu'il faudrait parcourir tous les caractères pour faire ce travail… Dans ma solution, j'ai choisi de travailler au niveau de l'octet. Ainsi, la réponse donnée correspondra au décalage en nombre d'octets. Si on reste en ASCII, ça ne fait pas de différence.

J'ai choisi d'utiliser un module (histoire de montrer comment c'est…)

// mesfonctions.rs

use std::collections::HashMap;

fn verif_position(foin:&str, aiguille:&str,shift:usize) -> bool
{
    /*
    le premier caractère [0] de aiguille étant
    placé devant le caractère [shift] de foin,
    renvoie true si tous les caractères de aiguille concordent à leur vis à vis, false sinon
    */
    for (j, c) in aiguille.bytes().enumerate() {
        if c != foin.as_bytes()[shift + j] {
            return false;
        }
    }
    true
}

fn bons_droite(foin:&str, aiguille:&str, shift:usize) -> usize
{
    /*
    le premier caractère [0] de aiguille étant
    placé devant le caractère [shift] de foin.
    compte le nombre de caractères successifs valides
    en partant de la droite de aiguille
    */
    let mut count = 0;
    for (j, c) in aiguille.bytes().enumerate().rev() {
        if c != foin.as_bytes()[shift + j] {
            return count;
        }
        count += 1;
    }
    count
}

fn make_rangs(aiguille:&str) -> HashMap<u8, usize>
{
    /* aiguille : chaine de caractères à trouver dans le texte foin
       arr_rangs: tableau contenant les indices des premières occurences
         en partant de la fin.
       exemple : aiguille = "ACCAT"
       arr_rangs = {1, 5, 2, 5,...}
    */

    let mut rangs:HashMap<u8, usize> = HashMap::new();
    let n = aiguille.len();
    for (j, c) in aiguille.bytes().enumerate() {
        rangs.insert(c, n -1 - j);
    }
    rangs
}

pub fn recherche_naive(foin:&str, aiguille:&str) -> Option<usize> {
    /* renvoie l'indice de la première occurence de aiguille dans foin
       si elle existe, -1 sinon.
       utilise une méthode naïve */
    let n = aiguille.len();
    let m = foin.len();
    for s in 0..=m-n {
        if verif_position(foin, aiguille, s) {
            return Some(s);
        }
    }
    None
}

pub fn recherche_boyer_moore_1(foin:&str, aiguille:&str) -> Option<usize>
{
    /* renvoie l'indice de la première occurence de aiguille dans foin
       si elle existe, None sinon.
       utilise une méthode boyer moore avec amélioration 1 du TD */
    let n = aiguille.len();
    let m = foin.len();
    let rangs = make_rangs(aiguille);
    let mut s = 0usize;
    while s + n <= m {
        let b = bons_droite(foin, aiguille, s);
        if b == n {
            return Some(s);
        } else if b == 0 {
            let last = foin.as_bytes()[s+n-1];
            match rangs.get(&last) {
                Some(d) => s += d,
                None    => s += n,
            }
        } else {
            s += 1;
        }
    }
    None
}

Notez le mot clé pub utilisé pour indiquer les fonctions devant être visibles pour qui utilisent le module.

Autre particularité : les fonctions de recherche renvoient un Option<usize>. Cela signifie qu'en utilisant l'une ou l'autre des fonctions de recherche, on devra vérifier la réponse renvoyer pour voir si c'est une valeur numérique (usize) ou None.

Fichier principal :

// main.rs

use mesfonctions;
use std::env;
use std::fs; // file system

fn main() {
    let args: Vec<String> = env::args().collect();
    if args.len() < 3 {
        panic!("Usage : {} nomfichier aiguille", args[0]);
    }
    let filename = &args[1];
    let foin = fs::read_to_string(filename)
        .expect("Impossible d'ouvrir le fichier.");
    let aiguille = &args[2];
    match mesfonctions::recherche_boyer_moore_1(&foin, aiguille) {
        Some(s) => println!("{}", s),
        None => println!("pas trouvé"),
    }
}

Il faudra bien sûr placer un fichier foin à côté de l'exécutable.