encodebwt.c

Burrows Wheeler Transform_Encoder and Decoder

#include <stdlib.h>
#include <string.h>
#include <stdio.h> 

typedef unsigned char byte; //declaramos nuevo tipo de dato: unsigned char al que llamamos byte <de 0 a 255> 
byte *rotlexcmp_buf = NULL;  //buffer para todas las posibles rotaciones del texto
int rottexcmp_bufsize = 0;  //tamano del buffer para la cadena a codificar

//funcion para ordenar alfabeticamente, usada por la funcion qsort, compara los indice li y ri
int rotlexcmp(const void *l, const void *r) 
{ 
int li = *(const int*)l; 
int ri = *(const int*)r; 
int ac = rottexcmp_bufsize; //acumulador
   
if(li == ri) return 0;
   while (rotlexcmp_buf[li] == rotlexcmp_buf[ri])
   {
       if (++li == rottexcmp_bufsize)
           li = 0;
       if (++ri == rottexcmp_bufsize)
           ri = 0;
       if (!--ac)
           return 0;
	
   }
  //comprueba que realmente se haya ordenado el array 
  if (rotlexcmp_buf[li] > rotlexcmp_buf[ri]) 
      return 1;
   else
      return -1;
} 

//funcion para codificar
void bwt_encode(byte *buf_in, byte *buf_out, int size, int *llave) {

   int indices[size];
   int i;

   for(i=0; i<size; i++)
       indices[i] = i;

   rotlexcmp_buf = buf_in;
   rottexcmp_bufsize = size;
  
   qsort (indices, size, sizeof(int), rotlexcmp);
   for (i=0; i<size; i++)
       buf_out[i] = buf_in[(indices[i]+size-1)%size];

   for (i=0; i<size; i++)
   {
       if (indices[i] == 0) {
           *llave = i;
	   printf ("llave: <%d>\n",i); //indica en que indice se encuentra la palabra original
           return;
       }
		
   }
}

int main() {

   byte buf1[255];
   byte buf2[255];
   int llave;
   printf ("Palabra a codificar: ");
   scanf("%s",buf1);	
   bwt_encode (buf1, buf2, strlen((const char*)buf1), &llave);
   printf ("Codificado: <%.*s>\n", strlen((const char*)buf1), buf2);
  
   return 0;

}