Algoritmo de transformación de datos Mover al frente

¿Qué es la transformación MTF?  
El MTF (Move to Front) es un algoritmo de transformación de datos que reestructura los datos de tal manera que el mensaje transformado es más comprimible y, por lo tanto, se usa como un paso adicional en la compresión. Técnicamente, es una transformación invertible de una secuencia de caracteres de entrada en una array de números de salida. 

¿Por qué MTF? 

1. En muchos casos, la array de salida proporciona índices inferiores de caracteres que se repiten con frecuencia, lo que es útil en los algoritmos de compresión de datos. 
2. Es el primero de los tres pasos que se realizarán en sucesión al implementar el algoritmo de compresión de datos de Burrows – Wheeler que forma la base de la utilidad de compresión bzip2 de Unix. 

La idea principal detrás de MTF: 

1. La idea principal detrás de MTF es mantener una lista ordenada de símbolos legales (de la A a la Z, en nuestro ejemplo). 
2. Lea un carácter a la vez desde la string de entrada. 
3. Imprime la posición en la que aparece ese carácter en la lista. 
4. Mueva ese carácter al frente de la lista y repita el proceso hasta obtener índices para todos los caracteres de entrada.

Illustration for "panama".  
List initially contains English alphabets in order. 
We one by one characters of input to front.

input_str chars   output_arr       list
  p              15               abcdefghijklmnopqrstuvwxyz
  a              15 1             pabcdefghijklmnoqrstuvwxyz
  n              15 1 14          apbcdefghijklmnoqrstuvwxyz
  a              15 1 14 1        napbcdefghijklmoqrstuvwxyz
  m              15 1 14 1 14     anpbcdefghijklmoqrstuvwxyz
  a              15 1 14 1 14     manpbcdefghijkloqrstuvwxyz

Inferencia: 

1. Si las letras aparecen muchas veces en la entrada, muchos de los valores de salida serán números enteros pequeños como 0, 1, 2, etc. 
2. Por lo tanto, la codificación de una frecuencia extremadamente alta de estas letras crea un escenario ideal para la codificación Huffman. 

Ejemplos:

Input : panama
Output : 15 1 14 1 14 1

Input : geeksforgeeks
Output : 6 5 0 10 18 8 15 18 6 6 0 6 6 

El siguiente es el código para la idea explicada anteriormente: 

// C program to find move to front transform of
// a given string
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
// Returns index at which character of the input text
// exists in the list
int search(char input_char, char* list)
{
    int i;
    for (i = 0; i < strlen(list); i++) {
        if (list[i] == input_char) {
            return i;
            break;
        }
    }
}
 
// Takes curr_index of input_char as argument
// to bring that character to the front of the list
void moveToFront(int curr_index, char* list)
{
    char* record = (char*)malloc(sizeof(char) * 26);
    strcpy(record, list);
 
    // Characters pushed one position right
    // in the list up until curr_index
    strncpy(list + 1, record, curr_index);
 
    // Character at curr_index stored at 0th position
    list[0] = record[curr_index];
}
 
// Move to Front Encoding
void mtfEncode(char* input_text, int len_text, char* list)
{
    int i;
    int* output_arr = (int*)malloc(len_text * sizeof(int));
 
    for (i = 0; i < len_text; i++) {
 
        // Linear Searches the characters of input_text
        // in list
        output_arr[i] = search(input_text[i], list);
 
        // Printing the Move to Front Transform
        printf("%d ", output_arr[i]);
 
        // Moves the searched character to the front
        // of the list
        moveToFront(output_arr[i], list);
    }
}
 
// Driver program to test functions above
int main()
{
    char* input_text = "panama";
    int len_text = strlen(input_text);
 
    // Maintains an ordered list of legal symbols
    char* list = (char*)malloc(sizeof(char) * 26);
    strcpy(list, "abcdefghijklmnopqrstuvwxyz");
 
    printf("Input text: %s", input_text);
    printf("\nMove to Front Transform: ");
 
    // Computes Move to Front transform of given text
    mtfEncode(input_text, len_text, list);
     
    return 0;
}

Input text: panama
Move to Front Transform: 15 1 14 1 14 1 

Complejidad del tiempo: O(n^2) 

Ejercicio: Implementar Transformación Inversa de Mover al Frente.