Métodos de diccionario-Byte pair encoding

Para este método se utiliza las repeticiones que sean iguales dentro de una cadena de manera que se sustituyen con variables para al final tener variables como referencia y una cadena más corta, para realizar este ejemplo hice en python una cadena aleatoria de la siguiente manera.

''.join(random.choice("abcde") for x in range(20))

De manera que tengamos una cadena de largo 20 y con un alfabeto A = {a, b, c, d, e}

Esta es la cadena que vamos a utilizar 'bbbeadbaaddadabceacb'

Encontramos los valores que podemos sustituir en la primera iteración

En la primera iteración buscamos caracteres que se repitan pero en bares diferentes por lo que primero voy a comprimir con la variable X a la repetición ea.

• bbbeadbaaddadabceacb
• X = ea

Luego en la segunda iteración encontramos caracteres repetidos como da.

• bbbXdbaaddadabcXcb
• Y = da

Ahora ya no tenemos caracteres diferentes que se repitan, por lo que empezamos a buscar caracteres del mismo tipo que se repitan en la cadena, encontramos bbb

• bbbXdbaadYYbcXcb
• Z = bbb

Encontramos al igual aa en la cuarta iteración.

• ZXdbaadYYbcXcb
• W= aa

Luego encontramos la letra YY repetida

• ZXdbWdYYbcXcb
• Q=YY

Ya no existen patrones de repetición por lo que esta sería nuestra cadena comprimida, junto con su diccionario.

• ZXdbWdQbcXcb
• X = ea
• Y = da
• Z = bbb
• W= aa
• Q=YY

Ahora para decomprimirlo, como ya tenemos el diccionario, en la primera iteración sustituimos la Q ya que esta contiene referencias al mismo diccionario.

• ZXdbWdQbcXcb
• ZXdbWdYYbcXcb

Luego sustituimos la W de la cadena que tenemos

• ZXdbaadYYbcXcb

Ahora, sustituimos la letra Z

• ZXdbaadYYbcXcb
• bbbXdbaadYYbcXcb

Luego, en la siguiente iteración, sustituimos las Y

• bbbXdbaadYYbcXcb
• bbbXdbaaddadabcXcb

Para después en la siguiente iteración y última con la variable X

• bbbXdbaaddadabcXcb
• bbbeadbaaddadabceacb

Entonces como resumen tenemos lo siguiente.

• Cadena = bbbeadbaaddadabceacb   
• largo = 20
• Cadena comprimida = ZXdbWdQbcXcb   
• largo = 12