/*************************************************************************************************************************************/
/* */
/* 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 ' BWT ' E T I N V E R S E : */
/* */
/* */
/* Nota : */
/* */
/* Ce module est inspire de 'v $xtc/BurrowsWheeler.11$I' */
/* qui a servi a sa mise au point... */
/* */
/* */
/* Author of '$xrC/CompressionDeCompression_BurrowsWheeler.01$vv$I' : */
/* */
/* Jean-Francois Colonna (LACTAMME, 20151227143647). */
/* */
/*************************************************************************************************************************************/
/*************************************************************************************************************************************/
/* */
/* D E F I N I T I O N G E N E R A L E S : */
/* */
/*************************************************************************************************************************************/
Logical BWT_Utiliser=VRAI;
Logical BWT_EditerLaMatrice=FAUX;
Logical BWT_EditerLesChaines=FAUX;
/* Indicateurs de controle des editions... */
Argument BWT_TailleDesPaquets=8192;
/* On notera que 512 est egal a la moitie de '$dimXSdu'... */
/* */
/* Le 20160129123333, avec le passage a la version '02' cette taille est passee de 512 */
/* a 8192 soit huit fois '$dimXSdu'... */
#define BWT_INDEXN \
NombreVersIndex(BWT_LongueurDeToutesLesChaines)
Entier BWT_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'... */
Entier BWT_Directe_LongueurAvant;
Entier BWT_Directe_LongueurApres;
Entier BWT_Inverse_LongueurAvant;
Entier BWT_Inverse_LongueurApres;
/* Afin de faciliter des verifications de coherence... */
CHAR *BWT_ChaineA;
#define BWT_TYPE_IndexDeLaChaineAPermuterDansLaMatrice \
Entier
#define BWT_SIZE_IndexDeLaChaineAPermuterDansLaMatrice \
COND((BWT_Utiliser == VRAI) \
,(SIZEOF(BWT_NombreDePaquets)+(BWT_NombreDePaquets*SIZEOF(BWT_TYPE_IndexDeLaChaineAPermuterDansLaMatrice))) \
,0 \
)
BWT_TYPE_IndexDeLaChaineAPermuterDansLaMatrice BWT_IndexDeLaChaineAPermuterDansLaMatrice;
Entier BWT_NombreDePaquets;
BWT_TYPE_IndexDeLaChaineAPermuterDansLaMatrice *BWT_ListeIndexDeLaChaineA;
/* Definition de la chaine Argument a permuter... */
CHAR *BWT_ChaineP;
/* Definition de la version permutee de 'ChaineAPermuter'... */
CHAR *BWT_ChainePT;
int *BWT_ChainePT_NumeroDOccurence;
/* Definition de la version permutee et triee de 'ChaineAPermuter'... */
CHAR *BWT_ChaineR;
/* Definition de la chaine "depermutee" qui doit donc etre identique a 'ChaineAPermuter'... */
#define MATRICEd(IndexLigne,IndexColonne) \
mINDX(BWT_Matrice,((((LEntier)IndexLigne)*((LEntier)BWT_LongueurDeToutesLesChaines))+((LEntier)IndexColonne)))
#define MATRICE(IndexLigne,IndexColonne) \
*MATRICEd(IndexLigne,IndexColonne)
CHAR *BWT_Matrice;
/* Definition de la matrice contenant 'ChaineAPermuter' et toutes ses permutations */
/* circulaires possibles. */
#define PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne) \
*mINDX(BWT_PermutationDesLignesDeLaMatrice,IndexLigne)
Entier *BWT_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. */
Entier F_BWT_ComparaisonDeDeuxChaines(Entier IndexLigne_1
,Entier IndexLigne_2
,Entier IndexColonneMinimal
,Entier IndexColonneMaximal
)
{
Entier IndexColonne;
Entier PoursuivreLaComparaison;
Entier ResultatDeLaComparaisonDeDeuxChaines;
mEGAL(IndexColonne,IndexColonneMinimal);
mEGAL(PoursuivreLaComparaison,VRAI);
mEGAL(ResultatDeLaComparaisonDeDeuxChaines,INFERIEUR);
Tant(mIFEQ(PoursuivreLaComparaison,VRAI))
{
CHAR caractere_1;
CHAR caractere_2;
mEGAL(caractere_1,MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_1),IndexColonne));
mEGAL(caractere_2,MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_2),IndexColonne));
/* Afin d'optimiser ce qui suit... */
Test(mIFLT(caractere_1,caractere_2))
{
mEGAL(ResultatDeLaComparaisonDeDeuxChaines,INFERIEUR);
mEGAL(PoursuivreLaComparaison,FAUX);
}
ATes
{
Test(mIFGT(caractere_1,caractere_2))
{
mEGAL(ResultatDeLaComparaisonDeDeuxChaines,SUPERIEUR);
mEGAL(PoursuivreLaComparaison,FAUX);
}
ATes
{
mEGAL(ResultatDeLaComparaisonDeDeuxChaines,EGAL);
}
ETes
}
ETes
Test(mIFEQ(PoursuivreLaComparaison,VRAI))
{
Test(mIFLT(IndexColonne,IndexColonneMaximal))
{
mINCR(IndexColonne);
}
ATes
{
mEGAL(PoursuivreLaComparaison,FAUX);
}
ETes
}
ATes
{
}
ETes
}
ETan
return(ResultatDeLaComparaisonDeDeuxChaines);
}
#define D_BWT_EchangeDeDeuxChaines(IndexLigne_1,IndexLigne_2) \
{ \
Entier VariableDeManoeuvre; \
\
mEGAL(VariableDeManoeuvre,PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_1)); \
mEGAL(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_1),PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_2)); \
mEGAL(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_2),VariableDeManoeuvre); \
/* Permutation "virtuelle" des lignes de la matrice... */ \
}
Entier F_BWT_Reorganisation_01(Entier IndexLigneDebut
,Entier IndexLigneFin
,Entier IndexColonneMinimal
,Entier IndexColonneMaximal
)
{
Entier IndexLigne;
Entier ItererLaReorganisation;
mEGAL(IndexLigne,IndexLigneDebut);
mEGAL(ItererLaReorganisation,VRAI);
Tant(mIFEQ(ItererLaReorganisation,VRAI))
{
Entier IndexLigneGauche;
mEGAL(IndexLigneGauche,mMUL2(2,IndexLigne));
Test(mIFGT(IndexLigneGauche,IndexLigneFin))
{
mEGAL(ItererLaReorganisation,FAUX);
}
ATes
{
Entier IndexMaximal;
Entier IndexLigneDroite;
mEGAL(IndexMaximal,IndexLigneGauche);
mEGAL(IndexLigneDroite,mADD2(IndexLigneGauche,1));
Test(mIFGT(IndexLigneDroite,IndexLigneFin))
{
}
ATes
{
Test(mIFLT(F_BWT_ComparaisonDeDeuxChaines(IndexLigneGauche
,IndexLigneDroite
,IndexColonneMinimal
,IndexColonneMaximal
)
,EGAL
)
)
{
mEGAL(IndexMaximal,IndexLigneDroite);
}
ATes
{
}
ETes
}
ETes
Test(mIFLE(F_BWT_ComparaisonDeDeuxChaines(IndexMaximal
,IndexLigne
,IndexColonneMinimal
,IndexColonneMaximal
)
,EGAL
)
)
{
mEGAL(ItererLaReorganisation,FAUX);
}
ATes
{
D_BWT_EchangeDeDeuxChaines(IndexLigne,IndexMaximal);
mEGAL(IndexLigne,IndexMaximal);
}
ETes
}
ETes
}
ETan
return(VRAI);
}
void F_BWT_TriRapideDeLEnsembleDesChaines(Entier IndexLigneDebut
,Entier IndexLigneFin
,Entier IndexColonneMinimal
,Entier IndexColonneMaximal
)
{
Entier IndexLigne;
mEGAL(IndexLigne,mDIVI(IndexLigneFin,2));
Tant(mIFGE(IndexLigne,IndexLigneDebut))
{
CALL(F_BWT_Reorganisation_01(IndexLigne
,IndexLigneFin
,IndexColonneMinimal
,IndexColonneMaximal
)
);
mDECR(IndexLigne);
}
ETan
mEGAL(IndexLigne,IndexLigneFin);
Tant(mIFGT(IndexLigne,IndexLigneDebut))
{
D_BWT_EchangeDeDeuxChaines(IndexLigneDebut,IndexLigne);
mDECR(IndexLigne);
CALL(F_BWT_Reorganisation_01(IndexLigneDebut
,IndexLigne
,IndexColonneMinimal
,IndexColonneMaximal
)
);
}
ETan
}
/*************************************************************************************************************************************/
/* */
/* E D I T I O N S D I V E R S E S : */
/* */
/*************************************************************************************************************************************/
#define D_BWT_EDITION_D_UNE_CHAINE(Message,EditionPreliminaire,ChaineA) \
{ \
if (BWT_EditerLesChaines == VRAI) \
{ \
Entier IndexCaractere; \
\
printf("BWT/%s : ",Message); \
\
EditionPreliminaire; \
\
for (IndexCaractere=INDEX0 ; IndexCaractere <= BWT_INDEXN ; IndexCaractere++) \
{ \
printf(FORMAT_CARACTERE,ACCES_CHAINE(ChaineA,IndexCaractere)); \
} \
\
printf("\n"); \
} \
else \
{ \
} \
}
#define D_BWT_EDITION_DE_LA_MATRICE(operateur) \
{ \
if (BWT_EditerLaMatrice == VRAI) \
{ \
Entier IndexLigne; \
\
printf("\n"); \
\
for (IndexLigne=INDEX0 ; IndexLigne <= BWT_INDEXN ; IndexLigne++) \
{ \
Entier IndexColonne; \
\
for (IndexColonne=0 ; IndexColonne <= BWT_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 D_BWT________Debut(ChaineR,ChaineA,LongueurChaineA) \
{ \
Entier IndexCaractere; \
\
BWT_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 parametre de longueur 'LongueurChaineA' doit apparaitre explicitement... */ \
\
ChaineR = MALLOC(BWT_LongueurDeToutesLesChaines*sizeof(CHAR)); \
\
DoIn(IndexCaractere,INDEX0,BWT_INDEXN) \
{ \
ACCES_CHAINE(ChaineR,IndexCaractere) = ACCES_CHAINE(ChaineA,IndexCaractere); \
} \
EDoI \
}
#define D_BWT________Fin__(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 D_BWT_GenerationDeLaChainePermutee(ChaineR) \
{ \
Entier IndexLigne; \
\
for (IndexLigne=INDEX0 ; IndexLigne <= BWT_INDEXN ; IndexLigne++) \
{ \
ACCES_CHAINE(ChaineR,IndexLigne) \
= MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne),BWT_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) \
{ \
BWT_IndexDeLaChaineAPermuterDansLaMatrice = IndexLigne; \
/* Memorisation de l'index de la ligne de la matrice 'Matrice' contenant dans le bon */ \
/* ordre la chaine Argument... */ \
} \
else \
{ \
} \
} \
\
D_BWT_EDITION_D_UNE_CHAINE("GenerationDeLaChainePermutee" \
,{ \
printf("%08"For10" " \
,BWT_IndexDeLaChaineAPermuterDansLaMatrice \
); \
} \
,ChaineR \
); \
}
#define D_BWT_DirecteDebut(ChaineA) \
{ \
BWT_Directe_LongueurAvant = BWT_LongueurDeToutesLesChaines; \
\
ChaineA = MALLOC(BWT_LongueurDeToutesLesChaines*sizeof(CHAR)); \
/* Allocations memoire diverses... */ \
}
#define D_BWT_Directe(ChaineR,ChaineA) \
{ \
if (BWT_Utiliser == VRAI) \
{ \
Entier SaveBWT_LongueurDeToutesLesChaines \
=BWT_LongueurDeToutesLesChaines; \
\
CHAR *SousChaineR=ChaineR; \
CHAR *SousChaineA=ChaineA; \
\
Entier NombreDOctetsEncoreATraiter=BWT_LongueurDeToutesLesChaines; \
Entier NumeroDuPaquetCourant=1; \
\
BWT_NombreDePaquets = DIVISION_PAR_EXCES(BWT_LongueurDeToutesLesChaines,BWT_TailleDesPaquets); \
\
BWT_ListeIndexDeLaChaineA \
= MALLOC(BWT_NombreDePaquets*sizeof(BWT_TYPE_IndexDeLaChaineAPermuterDansLaMatrice)); \
\
while (NombreDOctetsEncoreATraiter > 0) \
{ \
Entier LongueurDeSousChaineAMesurer=MIN2(BWT_TailleDesPaquets,NombreDOctetsEncoreATraiter); \
Entier IndexLigne; \
\
BWT_LongueurDeToutesLesChaines = LongueurDeSousChaineAMesurer; \
\
BWT_Matrice \
= MALLOC(BWT_LongueurDeToutesLesChaines*BWT_LongueurDeToutesLesChaines*sizeof(CHAR)); \
BWT_PermutationDesLignesDeLaMatrice \
= MALLOC(BWT_LongueurDeToutesLesChaines*sizeof(Entier)); \
\
for (IndexLigne=INDEX0 ; IndexLigne <= BWT_INDEXN ; IndexLigne++) \
{ \
Entier IndexColonne; \
\
PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne) = IndexLigne; \
/* Initialisation neutre a priori du tri de toutes les chaines... */ \
\
for (IndexColonne=0 ; IndexColonne <= BWT_INDEXN ; IndexColonne++) \
{ \
Entier IndexCaractere=IndexColonne-IndexLigne; \
\
if (IndexCaractere < 0) \
{ \
IndexCaractere = IndexCaractere+BWT_LongueurDeToutesLesChaines; \
} \
else \
{ \
} \
\
MATRICE(IndexLigne,IndexColonne) \
= ACCES_CHAINE(SousChaineA,IndexCaractere); \
/* Permutations circulaires de 'ChaineAPermuter'... */ \
} \
} \
\
D_BWT_EDITION_DE_LA_MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE); \
\
F_BWT_TriRapideDeLEnsembleDesChaines(INDEX0,BWT_INDEXN \
,INDEX0,BWT_INDEXN \
); \
\
D_BWT_EDITION_DE_LA_MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE); \
\
D_BWT_GenerationDeLaChainePermutee(SousChaineR); \
\
ACCES_CHAINE(BWT_ListeIndexDeLaChaineA,NombreVersIndex(NumeroDuPaquetCourant)) \
= BWT_IndexDeLaChaineAPermuterDansLaMatrice; \
\
SousChaineA = SousChaineA+LongueurDeSousChaineAMesurer; \
SousChaineR = SousChaineR+LongueurDeSousChaineAMesurer; \
\
NombreDOctetsEncoreATraiter = NombreDOctetsEncoreATraiter-LongueurDeSousChaineAMesurer; \
NumeroDuPaquetCourant++; \
\
free(BWT_Matrice); \
free(BWT_PermutationDesLignesDeLaMatrice); \
} \
\
BWT_LongueurDeToutesLesChaines = SaveBWT_LongueurDeToutesLesChaines; \
} \
else \
{ \
Entier IndexCaractere; \
\
for (IndexCaractere=INDEX0 ; IndexCaractere <= BWT_INDEXN ; IndexCaractere++) \
{ \
ACCES_CHAINE(ChaineR,IndexCaractere) = ACCES_CHAINE(ChaineA,IndexCaractere); \
} \
} \
\
BWT_Directe_LongueurApres = BWT_LongueurDeToutesLesChaines; \
}
#define D_BWT_DirecteFin__() \
{ \
}
/*************************************************************************************************************************************/
/* */
/* 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 D_BWT_GenerationDeLaChaineRetablie(ChaineR) \
{ \
Entier IndexCaractere; \
\
DoIn(IndexCaractere,INDEX0,BWT_INDEXN) \
{ \
mEGAL(ACCES_CHAINE(ChaineR,IndexCaractere) \
,MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(BWT_IndexDeLaChaineAPermuterDansLaMatrice) \
,IndexCaractere \
) \
); \
} \
EDoI \
}
#define D_BWT_InverseDebut_01(ChaineR) \
{ \
BWT_Inverse_LongueurAvant = BWT_LongueurDeToutesLesChaines; \
\
ChaineR = MALLOC(BWT_LongueurDeToutesLesChaines*sizeof(CHAR)); \
/* Allocations memoire diverses... */ \
}
#define D_BWT_Inverse_Debut(ChaineR,ChaineA) \
{ \
Test(mIFEQ(BWT_Utiliser,VRAI)) \
{ \
CHAR *SousChaineR=ChaineR; \
CHAR *SousChaineA=ChaineA; \
Entier NombreDOctetsEncoreATraiter; \
Entier NumeroDuPaquetCourant; \
Entier SaveBWT_LongueurDeToutesLesChaines=BWT_LongueurDeToutesLesChaines; \
\
mEGAL(NombreDOctetsEncoreATraiter,BWT_LongueurDeToutesLesChaines); \
mEGAL(BWT_NombreDePaquets,DIVISION_PAR_EXCES(LongueurDeChaineAMesurer,BWT_TailleDesPaquets)); \
mEGAL(NumeroDuPaquetCourant,1); \
\
Tant(mIFGT(NombreDOctetsEncoreATraiter,0)) \
{ \
Entier LongueurDeSousChaineAMesurer=MIN2(BWT_TailleDesPaquets,NombreDOctetsEncoreATraiter); \
Entier IndexColonne; \
\
mEGAL(BWT_IndexDeLaChaineAPermuterDansLaMatrice \
,ACCES_CHAINE(BWT_ListeIndexDeLaChaineA,NombreVersIndex(NumeroDuPaquetCourant)) \
); \
BWT_LongueurDeToutesLesChaines = LongueurDeSousChaineAMesurer;
#define D_BWT_Inverse_Milieu_01(SousChaineR,SousChaineA) \
{ \
BWT_Matrice \
= MALLOC(BWT_LongueurDeToutesLesChaines*BWT_LongueurDeToutesLesChaines*sizeof(CHAR)); \
BWT_PermutationDesLignesDeLaMatrice \
= MALLOC(BWT_LongueurDeToutesLesChaines*sizeof(Entier)); \
\
\
Test(FAUX) \
{ \
DoIn(IndexColonne,INDEX0,BWT_INDEXN) \
{ \
Entier IndexLigne; \
\
DoIn(IndexLigne,INDEX0,BWT_INDEXN) \
{ \
mEGAL(MATRICEd(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. Cette sequence est malgre tout */ \
/* conservee (sans etre utilisee), on ne sait jamais... */ \
} \
EDoI \
} \
EDoI \
} \
ATes \
{ \
} \
ETes \
\
DoDe(IndexColonne,INDEX0,BWT_INDEXN) \
{ \
Entier IndexLigne; \
\
DoIn(IndexLigne,INDEX0,BWT_INDEXN) \
{ \
Test(mIFEQ(IndexColonne,BWT_INDEXN)) \
{ \
mEGAL(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne) \
,IndexLigne \
); \
/* Initialisation neutre a priori du tri de toutes les chaines... */ \
} \
ATes \
{ \
} \
ETes \
\
mEGAL(MATRICEd(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne) \
,IndexColonne \
) \
,ACCES_CHAINE(SousChaineA,IndexLigne) \
); \
/* La chaine permutee est introduite dans l'ordre du classement courant en tant que */ \
/* colonne courante de gauche ('IndexColonne'). */ \
} \
EDoI \
\
D_BWT_EDITION_DE_LA_MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE); \
\
F_BWT_TriRapideDeLEnsembleDesChaines(INDEX0 \
,BWT_INDEXN \
,IndexColonne \
,BWT_INDEXN \
); \
\
D_BWT_EDITION_DE_LA_MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE); \
} \
EDoD \
\
D_BWT_GenerationDeLaChaineRetablie(SousChaineR); \
/* La chaine Argment est retrouvee sur la ligne 'IndexDeLaChaineAPermuterDansLaMatrice' */ \
/* de la matrice 'Matrice'. */ \
\
CALLs(free(BWT_PermutationDesLignesDeLaMatrice)); \
CALLs(free(BWT_Matrice)); \
}
#define D_BWT_Inverse_Fin(ChaineR,SousChaineR,ChaineA,SousChaineA) \
D_BWT_EDITION_D_UNE_CHAINE("TransformationInverse",{},SousChaineR); \
\
mEGAL(SousChaineA,mADD2(SousChaineA,LongueurDeSousChaineAMesurer)); \
mEGAL(SousChaineR,mADD2(SousChaineR,LongueurDeSousChaineAMesurer)); \
mEGAL(NombreDOctetsEncoreATraiter \
,mSOUS(NombreDOctetsEncoreATraiter,LongueurDeSousChaineAMesurer) \
); \
mINCR(NumeroDuPaquetCourant); \
} \
ETan \
\
mEGAL(BWT_LongueurDeToutesLesChaines \
,SaveBWT_LongueurDeToutesLesChaines \
); \
CALLs(free(BWT_ListeIndexDeLaChaineA)); \
} \
ATes \
{ \
Entier IndexCaractere; \
\
DoIn(IndexCaractere,INDEX0,BWT_INDEXN) \
{ \
mEGAL(ACCES_CHAINE(ChaineR,IndexCaractere),ACCES_CHAINE(ChaineA,IndexCaractere)); \
} \
EDoI \
} \
ETes \
}
#define D_BWT_Inverse_01(ChaineR,ChaineA) \
{ \
D_BWT_Inverse_Debut(ChaineR,ChaineA); \
D_BWT_Inverse_Milieu_01(SousChaineR,SousChaineA); \
D_BWT_Inverse_Fin(ChaineR,SousChaineR,ChaineA,SousChaineA); \
\
BWT_Inverse_LongueurApres = BWT_LongueurDeToutesLesChaines; \
}
#define D_BWT_InverseFin___01(ChaineA1,ChaineA2) \
{ \
CALLs(free(ChaineA1)); \
CALLs(free(ChaineA2)); \
}
/*************************************************************************************************************************************/
/* */
/* 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 D_BWT_InverseDebut_02(ChaineR) \
{ \
BWT_Inverse_LongueurAvant = BWT_LongueurDeToutesLesChaines; \
\
ChaineR = MALLOC(BWT_LongueurDeToutesLesChaines*sizeof(CHAR)); \
/* Allocations memoire diverses... */ \
}
#define D_BWT_EchangeDeDeuxCaracteres(Index_1,Index_2) \
{ \
CHAR CaractereIntermediaire; \
\
mEGAL(CaractereIntermediaire,ACCES_CHAINE(BWT_ChainePT,Index_1)); \
mEGAL(ACCES_CHAINE(BWT_ChainePT,Index_1),ACCES_CHAINE(BWT_ChainePT,Index_2)); \
mEGAL(ACCES_CHAINE(BWT_ChainePT,Index_2),CaractereIntermediaire); \
}
Entier F_BWT_Reorganisation_02(Entier IndexDebut,Entier IndexFin)
{
Entier Index;
Logical ItererLaReorganisation;
mEGAL(Index,IndexDebut);
mEGAL(ItererLaReorganisation,VRAI);
Tant(IFEQ(ItererLaReorganisation,VRAI))
{
Entier IndexGauche;
mEGAL(IndexGauche,mMUL2(2,Index));
Test(mIFGT(IndexGauche,IndexFin))
{
mEGAL(ItererLaReorganisation,FAUX);
}
ATes
{
Entier IndexMaximal;
Entier IndexDroite;
mEGAL(IndexMaximal,IndexGauche);
mEGAL(IndexDroite,mADD2(IndexGauche,1));
Test(mIFGT(IndexDroite,IndexFin))
{
}
ATes
{
Test(mIFLT(ACCES_CHAINE(BWT_ChainePT,IndexGauche),ACCES_CHAINE(BWT_ChainePT,IndexDroite)))
{
mEGAL(IndexMaximal,IndexDroite);
}
ATes
{
}
ETes
}
ETes
Test(mIFLE(ACCES_CHAINE(BWT_ChainePT,IndexMaximal),ACCES_CHAINE(BWT_ChainePT,Index)))
{
mEGAL(ItererLaReorganisation,FAUX);
}
ATes
{
D_BWT_EchangeDeDeuxCaracteres(Index,IndexMaximal);
mEGAL(Index,IndexMaximal);
}
ETes
}
ETes
}
ETan
return(VRAI);
}
Entier F_BWT_TriRapideDUneChaine(Entier IndexDebut,Entier IndexFin)
{
Entier Index;
mEGAL(Index,mDIVI(IndexFin,2));
Tant(mIFGE(Index,IndexDebut))
{
CALL(F_BWT_Reorganisation_02(Index,IndexFin));
mDECR(Index);
}
ETan
mEGAL(Index,IndexFin);
Tant(Index > IndexDebut)
{
D_BWT_EchangeDeDeuxCaracteres(IndexDebut,Index);
mDECR(Index);
CALL(F_BWT_Reorganisation_02(IndexDebut,Index));
}
ETan
return(VRAI);
}
#define D_BWT_Inverse_Milieu_02(SousChaineR,SousChaineA) \
{ \
Entier Index; \
\
BWT_ChainePT = MALLOC(BWT_LongueurDeToutesLesChaines*sizeof(CHAR)); \
BWT_ChainePT_NumeroDOccurence = MALLOC(BWT_LongueurDeToutesLesChaines*sizeof(Entier)); \
\
DoIn(Index,INDEX0,BWT_INDEXN) \
{ \
mEGAL(ACCES_CHAINE(BWT_ChainePT,Index),ACCES_CHAINE(SousChaineA,Index)); \
} \
EDoI \
\
Test(FAUX) \
/* Cas du tri en N^2 : */ \
{ \
Entier IndexDeFinDeChaine; \
\
DoDe(IndexDeFinDeChaine,INDEX0,mSOUS(BWT_INDEXN,1)) \
{ \
Entier IndexDeDebutDeChaine; \
\
DoIn(IndexDeDebutDeChaine,INDEX0,IndexDeFinDeChaine) \
{ \
Test(mIFGT(ACCES_CHAINE(BWT_ChainePT,IndexDeDebutDeChaine) \
,ACCES_CHAINE(BWT_ChainePT \
,mADD2(IndexDeDebutDeChaine,1) \
) \
) \
) \
{ \
CHAR CaractereDeManoeuvre; \
\
mEGAL(CaractereDeManoeuvre \
,ACCES_CHAINE(BWT_ChainePT,IndexDeDebutDeChaine) \
); \
mEGAL(ACCES_CHAINE(BWT_ChainePT,IndexDeDebutDeChaine) \
,ACCES_CHAINE(BWT_ChainePT \
,mADD2(IndexDeDebutDeChaine,1) \
) \
); \
mEGAL(ACCES_CHAINE(BWT_ChainePT \
,mADD2(IndexDeDebutDeChaine,1) \
) \
,CaractereDeManoeuvre \
); \
/* Tri en N^2 de la chaine permutee... */ \
} \
ATes \
{ \
} \
ETes \
} \
EDoI \
} \
EDoD \
} \
ATes \
{ \
/* Cas du tri en N.log(N) : */ \
CALL(F_BWT_TriRapideDUneChaine(INDEX0,BWT_INDEXN)); \
} \
ETes \
\
{ \
Entier NombreDOccurences; \
\
mEGAL(NombreDOccurences,1); \
\
mEGAL(ACCES_CHAINE(BWT_ChainePT_NumeroDOccurence,INDEX0),NombreDOccurences); \
\
DoIn(Index,mADD2(INDEX0,1),BWT_INDEXN) \
{ \
Test(mIFEQ(ACCES_CHAINE(BWT_ChainePT,mSOUS(Index,1)) \
,ACCES_CHAINE(BWT_ChainePT,Index) \
) \
) \
{ \
mINCR(NombreDOccurences); \
} \
ATes \
{ \
mEGAL(NombreDOccurences,1); \
} \
ETes \
\
mEGAL(ACCES_CHAINE(BWT_ChainePT_NumeroDOccurence,Index),NombreDOccurences); \
} \
EDoI \
\
{ \
Entier IndexCaractere; \
\
mEGAL(IndexCaractere,BWT_IndexDeLaChaineAPermuterDansLaMatrice); \
\
DoIn(Index,INDEX0,BWT_INDEXN) \
{ \
CHAR CaractereCourant; \
Entier NombreDOccurencesCourant; \
\
Entier IndexDeRecherche; \
Logical ItererLaRecherche; \
\
mEGAL(CaractereCourant \
,ACCES_CHAINE(BWT_ChainePT,IndexCaractere) \
); \
mEGAL(NombreDOccurencesCourant \
,ACCES_CHAINE(BWT_ChainePT_NumeroDOccurence,IndexCaractere) \
); \
\
mEGAL(ACCES_CHAINE(SousChaineR,Index),CaractereCourant); \
\
mEGAL(IndexDeRecherche,INDEX0); \
mEGAL(ItererLaRecherche,VRAI); \
\
mEGAL(NombreDOccurences,1); \
\
Tant(mIFEQ(ItererLaRecherche,VRAI)) \
{ \
Test(mIFEQ(ACCES_CHAINE(SousChaineA,IndexDeRecherche) \
,CaractereCourant \
) \
) \
{ \
Test(mIFEQ(NombreDOccurencesCourant \
,NombreDOccurences \
) \
) \
{ \
mEGAL(IndexCaractere \
,IndexDeRecherche \
); \
mEGAL(ItererLaRecherche,FAUX); \
} \
ATes \
{ \
mINCR(NombreDOccurences); \
} \
ETes \
} \
ATes \
{ \
} \
ETes \
\
Test(mIFLT(IndexDeRecherche,BWT_INDEXN)) \
{ \
mINCR(IndexDeRecherche); \
} \
ATes \
{ \
mEGAL(ItererLaRecherche,FAUX); \
} \
ETes \
} \
ETan \
} \
} \
EDoI \
} \
\
CALLs(free(BWT_ChainePT_NumeroDOccurence)); \
CALLs(free(BWT_ChainePT)); \
}
#define D_BWT_Inverse_02(ChaineR,ChaineA) \
{ \
D_BWT_Inverse_Debut(ChaineR,ChaineA); \
D_BWT_Inverse_Milieu_02(SousChaineR,SousChaineA); \
D_BWT_Inverse_Fin(ChaineR,SousChaineR,ChaineA,SousChaineA); \
\
BWT_Inverse_LongueurApres = BWT_LongueurDeToutesLesChaines; \
}
#define D_BWT_InverseFin___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 F_BWT_Verifications(CHAR *ChaineA1,CHAR *ChaineA2)
{
Entier IndexCaractere;
for (IndexCaractere=INDEX0 ; IndexCaractere <= BWT_INDEXN ; IndexCaractere++)
{
if (ACCES_CHAINE(ChaineA1,IndexCaractere) != ACCES_CHAINE(ChaineA2,IndexCaractere))
{
fprintf(stderr
,"ERREUR(BWT) : chaine R ('0x%02x') # chaine A ('0x%02x').\n"
,ACCES_CHAINE(ChaineA1,IndexCaractere)
,ACCES_CHAINE(ChaineA2,IndexCaractere)
);
}
else
{
}
}
}