ALEA 2019 - TP Séance d'exercices

Burrows-Wheeler, indexation, recherche de motifs

Quelques liens

Travaux pratiques

  1. Écrire une fonction BWT(s) qui calcule la transformée de Burrows-Wheeler de s (ajout d'un '$', tri des rotations, renvoyer une chaîne de caractères rassemblant les lettres de la dernière colonne). On pourra utiliser le code donné en annexe (mais vous n'êtes pas obligés pour un petit texte).

  2. Pour une position i dans la table L, l'entier LF[i] est la position de la lettre correspondante dans F = sorted(L) (en tenant compte nombre d'occurences de cette lettre).
    Proposer une implantation linéaire du calcul de la table LF.

  3. Rappeler comment reconstruire le mot t à l'aide de la fonction LF. Implanter la fonction transformée inverse de Burrows-Wheeler iBWT(s).
  4. Appliquer la transformée inverse à ("ntnnrrssshhha___issccccheuoaasuen__ss_aan$e")
  5. Recherche de motif. La recherche de motifs utilise la fonction LF et parcourt le motif à rebours en uilisant la fonction LF. À faire sur un exemple !
    1. Dérouler (sur papier) l'algorithme de recherche des motifs suivants dans aabaabaabba$: ab, bba, aaa, aba.
    2. Implanter la recherche d'un motif. On a besoin de la fonction LF si l'on souhaite simplement compter le nombre d'occurrences. Comment faire pour en plus localiser ces occurrences ?

Annexe

Le fichier tools_karkkainen_sanders.py (écrit par Romain Brixtel) implante l'algorithme de Kärkkäinen et Sanders pour la construction linéaire des tables de suffixes.

Ce fichier contient entre autres la fonction direct_kark_sort(s) pour le calcul de la table des suffixes TS.

Un programme minimal qui calcule la table des suffixes d'un mot u passé en argument serait:

# -*- coding: utf-8 -*-

import sys
from tools_karkkainen_sanders import *

if __name__ == '__main__':
    u = "abracadabra"
    """                                                                         
    direct_kark_sort(u) retourne la liste des indices des suffixes du mot u     
    en ordre croissant                                                          
    """
    TS = direct_kark_sort(u)
    print(TS)