COMPRESOR LZ78

Iniciado por iretchai, 7 Noviembre 2020, 14:49 PM

0 Miembros y 1 Visitante están viendo este tema.

iretchai

Hola buenas!
Necesito ayuda con el algoritmo de un programa (en C++) que tiene que hacer lo siguiente:

Un programa que, en primer lugar, lea de la entrada estándar (cin) una cadena
de caracteres, formada por aes y bes únicamente, y escriba en la salida estándar (cout) el
resultado de comprimirla conforme al algoritmo LZ78; esto es, una secuencia de números
enteros y caracteres (a, b) alternados.

Ejemplos de ejecución:
CIN    >> ababbabaaabaaabba
COUT << 0a0b1b2a4a3a1a2b1

El esquema que he pensado es el siguiente:

Hacer que el cursor señale al primer carácter de la cadena de entrada
inicializar el diccionario con la palabra vacía: w(0) = "" y npal = 1

Mientras quedan caracteres por tratar (el cursor señala a un carácter)

-- buscar la palabra w(i) más larga del diccionario que coincide con los
   primeros caracteres de la cadena a partir del señalado por el cursor

-- escribir en la salida el entero i

-- si quedan caracteres por tratar,
    -- sea c el carácter señalado por el cursor
    -- escribir en la salida el carácter c
    -- añadir al diccionario la palabra w(npal) = w(i)c
    -- npal = npal+1

NOTAS: El diccionario es un array bidimensional dicc [100] [100], para simular un array unidimensional de palabras.
           Se incluye la biblioteca <cstring> y hay que usar las funciones: strstr, strcpy, strlen, strcat.
           El cursor puede ser un puntero char *cursor=cadena o también se puede usar directamente cadena(i)



AlbertoBSD

No se hacen tareas.

Saludos!
Donaciones
1Coffee1jV4gB5gaXfHgSHDz9xx9QSECVW