Transformation de Burrows-Wheeler
J'avais besoin d'un programme qui réalisait la transformation de Burrows-Wheeler (TBW) sur de simples lignes de texte et non pas sur des énormes fichiers binaires comme c'est le cas d'habitude. J'ai donc pondu le code qui suit :
#include <iostream>
int LineLen;
int Cmp(const void* a,const void*b)
{
return strncmp(*(const char**)a,*(const char**)b,LineLen);
}
int main()
{
int i;
char *Line=new char[1000], **Rows=new char*[1000];
while(gets(Line)){
LineLen = strlen(Line);
//On utilise un double buffer pour la ligne courante
memcpy(Line+LineLen, Line, LineLen);
//Les permutations en utilisant de simples pointeurs
for(i=0; i<LineLen; i++) Rows[i]=Line+i;
//On trie les pointeurs en fonction de leurs données
qsort(Rows, LineLen, 4, Cmp);
//On cherche la ligne originale dans la liste triée.
i=0;
while (i<LineLen && strncmp(Rows[i], Line, LineLen)) i++;
int OriginalIndex = i;
//
printf("%d\t",OriginalIndex);
for(i=0; i<LineLen; i++) printf("%c", Rows[i][LineLen-1]);
printf("\n");
}
delete []Line;
delete []Rows;
}
pour les données d'entrée suivante :
ABCABC abracadabra BurrowsWheelerTransform gaattcctgggcctggggctgtggcagctgcctcgtccct tcacctcctggcttattctctccctccatatcttagcaat ctcatgcctgtaatcccagcattttggtaggccaaggcgg gtcggatcacctgaggtcaggagttcgagggccagcctga tgaccatggtgaaaccccatctctactaaaaatacaaaat taatcgggcatggtggcacatgcctgtaatcccagctact ctgaggcaggagaatcgcttaaacccaggaagtggaggtt tcagtgagctgagattgtgccattgcactccagcctgggt aacaagagcaaaactccatcaaaaaaaataatatatgtat atatatattacaattttatatatatatacacattatgtaa taccattttatatatatacattacgtaatggtaaatgttt gatcgtctccctggagaataatccccaatgtgaaattact ctaagtggtgggattacaggcgtgtgcccaacttttcctg agccttttgaggctgacaccagaggtagaagcccagcctc tccccactggccatgtggggagaggctccagcctgcagca accagggatctggcctcaagtgatgccccaacagtgggcg 1001110010001111110101011101101110010100 1100111011000100110110010000011011100111 1000100001000001010101101000010110000011 0000000000111111000100100001011010100011 0011011000001111001010010001001011101111 0010110110101011100100010011000000010000 1101011110010100001000111001000100011001 0011001010001001001110100000101001001101 1110110100001001100110001010101001100100 1110001011101110110000110100011011100001
le programme renvoie :
0 CCAABB 2 rdarcaaaabb 0 mrsrhelsWerafreToruwnBo 16 gcagtgctgtccgccgtgtgagtggtgtctgtcccgccca 28 cctctatgtcttcatctctctgagttattcccctacccaa 17 ctctaacccctggctgggcagtggaacttgggcaatctta 31 cccgggggtctgagttcccttgggaacgaagaaagtgccg 37 tacgaaaaatgataccaacccacaatttttgcaccagtaa 31 ttctcaaccgcagctgtgcaggtatgcttggtcaaagacc 17 taggagccggaacgcattggagtggcaataaagtatcgcg 29 cgcgccggctctggagcttattaatgatgtccgtgctgaa 8 caaacaaatacataaagtaatcttgactaaataagaaaca 11 tacttctttttattttcaaaatgtaaaaataataaatata 25 ttatttttttaaccacaatgctggattaaataatatttga 25 ggtcatgaagaacccttcttactagttctatacaggccaa 13 cttacagcacgtggcagtgtgatttgaccttgcgggattc 7 ggctcaccggacctacgggcgcattaaaagaaggcctttc 35 cgccgcccgcgcctgctggcagatagaggtagttcaccga 3 ccagcacggctcacacgggctcgttgggtgataacagacg 21 1111100100111011001010010110111100010110 30 1010101011001100100011011111001110010010 30 1110100100000000001010111001001100000100 0 1000001010101000001010010101000100101110 8 1010101110010001010110010101010110111000 13 1010000010010010001010111100101010001000 35 1101110010011000010001000011101011010100 9 1010011101111110100000000000100010010100 39 1010101111110011000010011100010001000010 36 1110100000101001110111011110011010101000
Je voulais un code qui soit rapide à implémenter mais :
- la limite de 1000 octets n'est pas terrible pour une routine généraliste.
- j'utilise qsort qui n'est pas optimal par rapport à mon radix sort pour des données de taille importante.
- J'utilise gets ce qui est déconseillé !
- On n'a pas à dupliquer la ligne de données, en compliquant un peu le code ça devrait pouvoir marcher.
- Le buffer Rows est de trop il faut trouver une astuce pour ne pas l'utiliser il prend une mémoire folle.
Tout ceci sera fixé plus loin, pour l'instant ce qui nous intéresse c'est d'avoir un outil de test à utiliser en conjonction avec d'autres compresseurs maison.
La transformation inverse
Maintenant que l'exécutable précédent (que j'ai appelé bwt) est fait et fonctionne, comment retrouver à partir de sa sortie les données originales ?