/*************************************************************************************************************************************/
/* */
/* T R A N S F O R M A T I O N D E B U R R O W S - W H E E L E R E T I N V E R S E : */
/* */
/* */
/* Author of '$xtc/BurrowsWheeler.11$vv$I' : */
/* */
/* Jean-Francois Colonna (LACTAMME, 20151223080447). */
/* */
/*************************************************************************************************************************************/
/*************************************************************************************************************************************/
/* */
/* D E F I N I T I O N G E N E R A L E S : */
/* */
/*************************************************************************************************************************************/
int TransformationDeBurrowsWheeler_EditeLaMatrice=FAUX;
int TransformationDeBurrowsWheeler_EditerLesChaines=VRAI;
int TransformationDeBurrowsWheeler_EditionsHexaDecimalesDesChaines=FAUX;
/* Indicateurs de controle des editions... */
#ifndef CHAR
# define CHAR \
unsigned char \
/* Afin que tous les tests effectues fonctionnent correctement et que les relations */ \
/* d'odre soient bien celles que l'on attend, il est a priori necessaire que les */ \
/* caracteres soient non signes... */
#else
#endif
#ifndef FORMAT_CARACTERE
# define FORMAT_CARACTERE \
COND((TransformationDeBurrowsWheeler_EditionsHexaDecimalesDesChaines == VRAI),"%02x ","%c") \
/* Format d'edition des caracteres des chaines et de la matrice... */
#else
#endif
#define BurrowsWheeler_INDEXN \
NombreVersIndex(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines)
int TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines;
/* On notera qu'a priori, aucune des chaines utilisees n'a de caractere de fin. Cela */
/* vient du fait que ces chaines peuvent contenir 256 codes differents et qu'alors le */
/* code '0x00' habituel ne peut etre utilise. La fin d'une chaine est donc reperee via */
/* son dernier caractere d'index 'INDEXN'... */
#ifndef ACCES_CHAINE
# define ACCES_CHAINE(Chaine,IndexCaractere) \
*(Chaine+IndexCaractere) \
/* Acces a une chaine quelconque... */
#else
#endif
CHAR *TransformationDeBurrowsWheeler_ChaineAPermuter;
#define SIZE_IndexDeLaChaineAPermuterDansLaMatrice \
(sizeof(TransformationDeBurrowsWheeler_IndexDeLaChaineAPermuterDansLaMatrice)*NBITOC)
int TransformationDeBurrowsWheeler_IndexDeLaChaineAPermuterDansLaMatrice;
/* Definition de la chaine Argument a permuter... */
CHAR *TransformationDeBurrowsWheeler_ChainePermutee;
/* Definition de la version permutee de 'ChaineAPermuter'... */
CHAR *TransformationDeBurrowsWheeler_ChainePermuteeTriee;
int *TransformationDeBurrowsWheeler_CaracteresNombreOccurence;
/* Definition de la version permutee et triee de 'ChaineAPermuter'... */
CHAR *TransformationDeBurrowsWheeler_ChaineRetablie;
/* Definition de la chaine "depermutee" qui doit donc etre identique a 'ChaineAPermuter'... */
#define MATRICE(IndexLigne,IndexColonne) \
*(TransformationDeBurrowsWheeler_Matrice \
+((IndexLigne*TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines)+IndexColonne) \
)
CHAR *TransformationDeBurrowsWheeler_Matrice;
/* Definition de la matrice contenant 'ChaineAPermuter' et toutes ses permutations */
/* circulaires possibles. */
#define PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne) \
*(TransformationDeBurrowsWheeler_PermutationDesLignesDeLaMatrice+IndexLigne)
int *TransformationDeBurrowsWheeler_PermutationDesLignesDeLaMatrice;
/* Definition du tri par ordre croissant des differentes lignes de 'Matrice' via cette */
/* liste de permutation... */
/*************************************************************************************************************************************/
/* */
/* T R I S E N ' N . L O G ( N ) ' D E C H A I N E S Q U E L C O N Q U E S : */
/* */
/*************************************************************************************************************************************/
enum RelationsDOrdre
{
INFERIEUR=-1
,EGAL
,SUPERIEUR
};
/* Liste des trois relations d'ordre possibles. */
int TransformationDeBurrowsWheeler_ComparaisonDeDeuxChaines(int IndexLigne_1
,int IndexLigne_2
,int IndexColonneMinimal
,int IndexColonneMaximal
)
{
int IndexColonne=IndexColonneMinimal;
int PoursuivreLaComparaison=VRAI;
int ResultatDeLaComparaisonDeDeuxChaines;
while (PoursuivreLaComparaison == VRAI)
{
if (MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_1),IndexColonne)
< MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_2),IndexColonne)
)
{
ResultatDeLaComparaisonDeDeuxChaines = INFERIEUR;
PoursuivreLaComparaison = FAUX;
}
else
{
if (MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_1),IndexColonne)
== MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_2),IndexColonne)
)
{
ResultatDeLaComparaisonDeDeuxChaines = EGAL;
}
else
{
ResultatDeLaComparaisonDeDeuxChaines = SUPERIEUR;
PoursuivreLaComparaison = FAUX;
}
}
if (PoursuivreLaComparaison == VRAI)
{
if (IndexColonne < IndexColonneMaximal)
{
IndexColonne++;
}
else
{
PoursuivreLaComparaison = FAUX;
}
}
else
{
}
}
return(ResultatDeLaComparaisonDeDeuxChaines);
}
#define ECHANGE_DE_DEUX_CHAINES(IndexLigne_1,IndexLigne_2) \
{ \
int VariableDeManoeuvre=PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_1); \
PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_1) = PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_2); \
PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_2) = VariableDeManoeuvre; \
/* Permutation "virtuelle" des lignes de la matrice... */ \
}
int TransformationDeBurrowsWheeler_Reorganisation(int IndexLigneDebut
,int IndexLigneFin
,int IndexColonneMinimal
,int IndexColonneMaximal
)
{
int IndexLigne=IndexLigneDebut;
int ItererLaReorganisation=VRAI;
while (ItererLaReorganisation == VRAI)
{
int IndexLigneGauche=2*IndexLigne;
if (IndexLigneGauche > IndexLigneFin)
{
ItererLaReorganisation = FAUX;
}
else
{
int IndexMaximal=IndexLigneGauche;
int IndexLigneDroite=IndexLigneGauche+1;
if (IndexLigneDroite > IndexLigneFin)
{
}
else
{
if (TransformationDeBurrowsWheeler_ComparaisonDeDeuxChaines(IndexLigneGauche
,IndexLigneDroite
,IndexColonneMinimal
,IndexColonneMaximal
)
< 0
)
{
IndexMaximal = IndexLigneDroite;
}
else
{
}
}
if (TransformationDeBurrowsWheeler_ComparaisonDeDeuxChaines(IndexMaximal
,IndexLigne
,IndexColonneMinimal
,IndexColonneMaximal
)
<= 0
)
{
ItererLaReorganisation = FAUX;
}
else
{
ECHANGE_DE_DEUX_CHAINES(IndexLigne,IndexMaximal);
IndexLigne = IndexMaximal;
}
}
}
return(VRAI);
}
void TransformationDeBurrowsWheeler_TriRapideDeLEnsembleDesChaines(int IndexLigneDebut
,int IndexLigneFin
,int IndexColonneMinimal
,int IndexColonneMaximal
)
{
int IndexLigne=IndexLigneFin/2;
while (IndexLigne >= IndexLigneDebut)
{
TransformationDeBurrowsWheeler_Reorganisation(IndexLigne,IndexLigneFin,IndexColonneMinimal,IndexColonneMaximal);
IndexLigne = IndexLigne-1;
}
IndexLigne = IndexLigneFin;
while (IndexLigne > IndexLigneDebut)
{
ECHANGE_DE_DEUX_CHAINES(IndexLigneDebut,IndexLigne);
IndexLigne = IndexLigne-1;
TransformationDeBurrowsWheeler_Reorganisation(IndexLigneDebut,IndexLigne,IndexColonneMinimal,IndexColonneMaximal);
}
}
/*************************************************************************************************************************************/
/* */
/* E D I T I O N S D I V E R S E S : */
/* */
/*************************************************************************************************************************************/
#define BurrowsWheeler_EDITION_D_UNE_CHAINE(EditionPreliminaire,ChaineA) \
{ \
if (TransformationDeBurrowsWheeler_EditerLesChaines == VRAI) \
{ \
int IndexCaractere; \
\
EditionPreliminaire; \
\
for (IndexCaractere=INDEX0 ; IndexCaractere <= BurrowsWheeler_INDEXN ; IndexCaractere++) \
{ \
printf(FORMAT_CARACTERE,ACCES_CHAINE(ChaineA,IndexCaractere)); \
} \
\
printf("\n"); \
} \
else \
{ \
} \
}
#define EDITION_DE_LA_MATRICE(operateur) \
{ \
if (TransformationDeBurrowsWheeler_EditeLaMatrice == VRAI) \
{ \
int IndexLigne; \
\
printf("\n"); \
\
for (IndexLigne=INDEX0 ; IndexLigne <= BurrowsWheeler_INDEXN ; IndexLigne++) \
{ \
int IndexColonne; \
\
for (IndexColonne=0 ; IndexColonne <= BurrowsWheeler_INDEXN ; IndexColonne++) \
{ \
printf(FORMAT_CARACTERE,MATRICE(operateur(IndexLigne),IndexColonne)); \
} \
\
printf("\n"); \
} \
\
printf("\n"); \
} \
else \
{ \
} \
}
/*************************************************************************************************************************************/
/* */
/* I N I T I A L I S A T I O N D E L A C H A I N E A T R A I T E R : */
/* */
/*************************************************************************************************************************************/
#define TransformationDeBurrowsWheeler_InitialisationChaineATraiter(ChaineR,ChaineA,LongueurChaineA) \
{ \
int IndexCaractere; \
\
TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines = LongueurChaineA; \
/* ATTENTION : en toute generalite dans 'ChaineA' les 256 codes possibles peuvent */ \
/* etre presents et donc 'strlen(...)' ne peut pas fonctionner systematiquement. C'est */ \
/* pourquoi un pramatre de longueur 'LongueurChaineA' doit apparaitre explicitement... */ \
\
ChaineR = malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines); \
\
for (IndexCaractere=INDEX0 ; IndexCaractere <= BurrowsWheeler_INDEXN ; IndexCaractere++) \
{ \
ACCES_CHAINE(ChaineR,IndexCaractere) = ChaineA[IndexCaractere]; \
} \
}
#define TransformationDeBurrowsWheeler_DesinitialisationChaineATraiter(ChaineA) \
{ \
free(ChaineA); \
}
/*************************************************************************************************************************************/
/* */
/* T R A N S F O R M A T I O N D E B U R R O W S - W H E E L E R D I R E C T E : */
/* */
/*************************************************************************************************************************************/
#define GenerationDeLaChainePermutee(ChaineR) \
{ \
int IndexLigne; \
\
for (IndexLigne=INDEX0 ; IndexLigne <= BurrowsWheeler_INDEXN ; IndexLigne++) \
{ \
ACCES_CHAINE(ChaineR,IndexLigne) \
= MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne),BurrowsWheeler_INDEXN); \
/* Version permutee de la chaine initiale 'ChaineAPermuter'. Elle est en fait constituee */ \
/* de la derniere colonne ('INDEXN') de la matrice 'Matrice'... */ \
\
if (PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne) == INDEX0) \
{ \
TransformationDeBurrowsWheeler_IndexDeLaChaineAPermuterDansLaMatrice = IndexLigne; \
/* Memorisation de l'index de la ligne de la matrice 'Matrice' contenant dans le bon */ \
/* ordre la chaine Argument... */ \
} \
else \
{ \
} \
} \
\
BurrowsWheeler_EDITION_D_UNE_CHAINE({ \
printf("%08d " \
,TransformationDeBurrowsWheeler_IndexDeLaChaineAPermuterDansLaMatrice \
); \
} \
,ChaineR \
); \
}
#define TransformationDeBurrowsWheeler_InitialisationTransformationDirecte(ChaineA) \
{ \
TransformationDeBurrowsWheeler_Matrice \
= malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines \
*TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines \
); \
TransformationDeBurrowsWheeler_PermutationDesLignesDeLaMatrice \
= malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines*sizeof(int)); \
ChaineA = malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines); \
/* Allocations memoire diverses... */ \
}
#define TransformationDeBurrowsWheeler_TransformationDirecte(ChaineR,ChaineA) \
{ \
int IndexLigne; \
\
for (IndexLigne=INDEX0 ; IndexLigne <= BurrowsWheeler_INDEXN ; IndexLigne++) \
{ \
int IndexColonne; \
\
PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne) = IndexLigne; \
/* Initialisation neutre a priori du tri de toutes les chaines... */ \
\
for (IndexColonne=0 ; IndexColonne <= BurrowsWheeler_INDEXN ; IndexColonne++) \
{ \
int IndexCaractere=IndexColonne-IndexLigne; \
\
if (IndexCaractere < 0) \
{ \
IndexCaractere = IndexCaractere \
+TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines; \
} \
else \
{ \
} \
\
MATRICE(IndexLigne,IndexColonne) = ChaineA[IndexCaractere]; \
/* Permutations circulaires de 'ChaineAPermuter'... */ \
} \
} \
\
EDITION_DE_LA_MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE); \
\
TransformationDeBurrowsWheeler_TriRapideDeLEnsembleDesChaines(INDEX0,BurrowsWheeler_INDEXN \
,INDEX0,BurrowsWheeler_INDEXN \
); \
\
EDITION_DE_LA_MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE); \
\
GenerationDeLaChainePermutee(ChaineR); \
}
#define TransformationDeBurrowsWheeler_DesinitialisationsTransformationDirecte() \
{ \
free(TransformationDeBurrowsWheeler_PermutationDesLignesDeLaMatrice); \
free(TransformationDeBurrowsWheeler_Matrice); \
}
/*************************************************************************************************************************************/
/* */
/* T R A N S F O R M A T I O N D E B U R R O W S - W H E E L E R I N V E R S E ( V E R S I O N 01 ) : */
/* */
/*************************************************************************************************************************************/
#define GenerationDeLaChaineRetablie(ChaineR) \
{ \
int IndexCaractere; \
\
for (IndexCaractere=INDEX0 ; IndexCaractere <= BurrowsWheeler_INDEXN ; IndexCaractere++) \
{ \
ACCES_CHAINE(ChaineR,IndexCaractere) \
= MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE \
(TransformationDeBurrowsWheeler_IndexDeLaChaineAPermuterDansLaMatrice) \
,IndexCaractere \
); \
} \
}
#define TransformationDeBurrowsWheeler_InitialisationTransformationInverse_01(ChaineR) \
{ \
TransformationDeBurrowsWheeler_Matrice \
= malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines \
*TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines \
); \
TransformationDeBurrowsWheeler_PermutationDesLignesDeLaMatrice \
= malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines*sizeof(int)); \
ChaineR = malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines); \
/* Allocations memoire diverses... */ \
}
#define TransformationDeBurrowsWheeler_TransformationInverse_01(ChaineR,ChaineA) \
{ \
int IndexColonne; \
\
for (IndexColonne=INDEX0 ; IndexColonne <= BurrowsWheeler_INDEXN ; IndexColonne++) \
{ \
int IndexLigne; \
\
for (IndexLigne=INDEX0 ; IndexLigne <= BurrowsWheeler_INDEXN ; IndexLigne++) \
{ \
MATRICE(IndexLigne,IndexColonne) = 0; \
/* Initialisation de la matrice : ceci est en fait inutile car cette derniere est remplie */ \
/* colonne par colonne (en partant de la colonne de droite 'INDEXN') et que n'est utilise */ \
/* que le sous-ensemble de colonnes qui ont ete remplies. */ \
} \
} \
\
for (IndexColonne=BurrowsWheeler_INDEXN ; IndexColonne >= INDEX0 ; IndexColonne--) \
{ \
int IndexLigne; \
\
for (IndexLigne=INDEX0 ; IndexLigne <= BurrowsWheeler_INDEXN ; IndexLigne++) \
{ \
if (IndexColonne == BurrowsWheeler_INDEXN) \
{ \
PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne) = IndexLigne; \
/* Initialisation neutre a priori du tri de toutes les chaines... */ \
} \
else \
{ \
} \
\
MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne),IndexColonne) \
= ACCES_CHAINE(ChaineA,IndexLigne); \
/* La chaine permutee est introduite dans l'ordre du classement courant en tant que */ \
/* colonne courante de gauche ('IndexColonne'). */ \
} \
\
EDITION_DE_LA_MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE); \
\
TransformationDeBurrowsWheeler_TriRapideDeLEnsembleDesChaines(INDEX0,BurrowsWheeler_INDEXN \
,IndexColonne,BurrowsWheeler_INDEXN \
); \
\
EDITION_DE_LA_MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE); \
} \
\
GenerationDeLaChaineRetablie(ChaineR); \
/* La chaine Argment est retrouvee sur la ligne 'IndexDeLaChaineAPermuterDansLaMatrice' */ \
/* le la matrice 'Matrice'. */ \
\
BurrowsWheeler_EDITION_D_UNE_CHAINE({},ChaineR); \
}
#define TransformationDeBurrowsWheeler_DesinitialisationsTransformationInverse_01(ChaineA1,ChaineA2) \
{ \
free(ChaineA1); \
free(ChaineA2); \
\
free(TransformationDeBurrowsWheeler_PermutationDesLignesDeLaMatrice); \
free(TransformationDeBurrowsWheeler_Matrice); \
}
/*************************************************************************************************************************************/
/* */
/* T R A N S F O R M A T I O N D E B U R R O W S - W H E E L E R I N V E R S E ( V E R S I O N 02 ) : */
/* */
/*************************************************************************************************************************************/
#define TransformationDeBurrowsWheeler_InitialisationTransformationInverse_02(ChaineR) \
{ \
ChaineR = malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines); \
/* Allocations memoire diverses... */ \
}
#define TransformationDeBurrowsWheeler_echang(index1,index2) \
{ \
CHAR tempo=ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,index1); \
ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,index1) \
= ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,index2); \
ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,index2) = tempo; \
}
int TransformationDeBurrowsWheeler_reorg(int debut,int fin)
{
int j=debut;
int iter=VRAI;
while (iter==VRAI)
{
int gauche=2*j;
if (gauche>fin)
{
iter=FAUX;
}
else
{
int indmax=gauche;
int droite=gauche+1;
if (droite>fin)
{
}
else
{
if (ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,gauche)
< ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,droite)
)
{
indmax=droite;
}
else
{
}
}
if (ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,indmax)
<= ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,j)
)
{
iter=FAUX;
}
else
{
TransformationDeBurrowsWheeler_echang(j,indmax);
j=indmax;
}
}
}
return(VRAI);
}
int TransformationDeBurrowsWheeler_tri(int debut,int fin)
{
int index=fin/2;
while (index>=debut)
{
TransformationDeBurrowsWheeler_reorg(index,fin);
index=index-1;
}
index=fin;
while (index>debut)
{
TransformationDeBurrowsWheeler_echang(debut,index);
index=index-1;
TransformationDeBurrowsWheeler_reorg(debut,index);
}
return(VRAI);
}
#define TransformationDeBurrowsWheeler_TransformationInverse_02(ChaineR,ChaineA) \
{ \
int Index; \
\
TransformationDeBurrowsWheeler_ChainePermuteeTriee \
= malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines \
); \
TransformationDeBurrowsWheeler_CaracteresNombreOccurence \
= malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines*sizeof(int) \
); \
\
for (Index=INDEX0 ; Index <= BurrowsWheeler_INDEXN ; Index++) \
{ \
ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,Index) \
= ACCES_CHAINE(ChaineA,Index); \
} \
\
if (FAUX) \
/* Cas du tri en N^2 : */ \
{ \
int index_de_fin; \
\
for (index_de_fin=(BurrowsWheeler_INDEXN-1) ; index_de_fin>=INDEX0 ; index_de_fin=index_de_fin-1) \
{ \
int index_de_debut; \
\
for (index_de_debut=INDEX0 \
; index_de_debut<=index_de_fin \
; index_de_debut=index_de_debut+1 \
) \
{ \
if (ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee \
,index_de_debut \
) \
> ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee \
,index_de_debut+1 \
) \
) \
{ \
CHAR caractere_manoeuvre; \
caractere_manoeuvre \
= ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee \
,index_de_debut \
); \
ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee \
,index_de_debut \
) \
= ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee \
,index_de_debut+1 \
); \
ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee \
,index_de_debut+1 \
) \
= caractere_manoeuvre; \
/* Tri en N^2 de la chaine permutee... */ \
} \
else \
{ \
} \
} \
} \
} \
else \
{ \
/* Cas du tri en N.log(N) : */ \
TransformationDeBurrowsWheeler_tri(INDEX0,BurrowsWheeler_INDEXN); \
} \
\
int NombreOccurence=1; \
\
ACCES_CHAINE(TransformationDeBurrowsWheeler_CaracteresNombreOccurence,INDEX0) = NombreOccurence; \
\
for (Index=INDEX0+1 ; Index <= BurrowsWheeler_INDEXN ; Index++) \
{ \
if (ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,Index-1) \
== ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,Index) \
) \
{ \
NombreOccurence++; \
} \
else \
{ \
NombreOccurence=1; \
} \
ACCES_CHAINE(TransformationDeBurrowsWheeler_CaracteresNombreOccurence,Index)=NombreOccurence; \
} \
\
int index_caractere = TransformationDeBurrowsWheeler_IndexDeLaChaineAPermuterDansLaMatrice; \
\
for (Index=INDEX0 ; Index <= BurrowsWheeler_INDEXN ; Index++) \
{ \
CHAR caractere_courant \
=ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,index_caractere); \
int NombreOccurenceCourant \
=ACCES_CHAINE(TransformationDeBurrowsWheeler_CaracteresNombreOccurence,index_caractere); \
\
ACCES_CHAINE(ChaineR,Index) = caractere_courant; \
\
int index_recherche=INDEX0; \
int iterer=VRAI; \
\
NombreOccurence=1; \
\
while (iterer == VRAI) \
{ \
if (ACCES_CHAINE(ChaineA,index_recherche) == caractere_courant) \
{ \
if (NombreOccurenceCourant == NombreOccurence) \
{ \
index_caractere = index_recherche; \
iterer = FAUX; \
} \
else \
{ \
NombreOccurence++; \
} \
} \
else \
{ \
} \
\
if (index_recherche < BurrowsWheeler_INDEXN) \
{ \
index_recherche++; \
} \
else \
{ \
iterer = FAUX; \
} \
} \
} \
\
free(TransformationDeBurrowsWheeler_CaracteresNombreOccurence); \
free(TransformationDeBurrowsWheeler_ChainePermuteeTriee); \
}
#define TransformationDeBurrowsWheeler_DesinitialisationsTransformationInverse_02(ChaineA1,ChaineA2) \
{ \
}
/*************************************************************************************************************************************/
/* */
/* V E R I F I C A T I O N D U P R O C E S S U S C O M P L E T : */
/* */
/*************************************************************************************************************************************/
void TransformationDeBurrowsWheeler_Verifications(CHAR *ChaineA1,CHAR *ChaineA2)
{
int IndexCaractere;
for (IndexCaractere=INDEX0 ; IndexCaractere <= BurrowsWheeler_INDEXN ; IndexCaractere++)
{
if (ACCES_CHAINE(ChaineA1,IndexCaractere) != ACCES_CHAINE(ChaineA2,IndexCaractere))
{
fprintf(stderr
,"ERREUR(BurrowsWheeler) : chaine retablie ('0x%02x') # chaine a traiter ('0x%02x').\n"
,ACCES_CHAINE(ChaineA1,IndexCaractere)
,ACCES_CHAINE(ChaineA2,IndexCaractere)
);
}
else
{
}
}
}