Representacin RUNSconversiones entre representaciones matriz binaria y secuencia

Juan Manuel Garca SnchezPablo de la Torre Moreno

Objetivos

Caractersticas de representacinOperacionesCaractersticas de compresin

Representacin en secuencia Ejemplo de matriz simple

101111111111100000011101110000000000111000000000011101110000001110000011100

Ejemplo de correspondencia runs

1 : 1 1 11 20 : 4 3 1 3 40 : 6 3 60 : 4 3 1 3 40 : 2 3 5 3 2Caractersticas de representacin

Algoritmo de paso a Runs (I)Definicin del tipo ArrayRuns como array de enteros sin signoEstructura de ArrayRuns:nmero filas y columnas de la matriz originalprimer bit de la primera filafrecuencias de la filaseparador de filas (0)primer bit de la segunda fila...Caractersticas de representacin

Algoritmo de paso a Runs (II)Ejemplo de matriz Runs

1 : 1 1 11 20 : 4 3 1 3 40 : 6 3 60 : 4 3 1 3 40 : 2 3 5 3 2Ejemplo de correspondencia ArrayRuns

5 15 1 1 1 11 2 0 0 4 3 1 3 4 0 0 63 6 0 0 4 3 1 3 40 0 2 3 5 3 2 0

Caractersticas de representacin

Algoritmo de paso a Runs (III)

Pasos del algoritmo:leer matriz en representacin simple (obtencin de nmero de filas y columnas)codificar matriz a ArrayRunscodificar ArrayRuns a bitsCaractersticas de representacin

Algoritmo de paso a Runs (IV)Pasos de la codificacin a bits:codificar cada elemento en tantos bits como los necesarios para codificar el nmero de columnas (existen codificaciones mucho ms eficientes)utilizar un TAD adecuado para trabajar con bitsse necesita guardar el nmero de filas y columnas de la matriz originalCaractersticas de representacin

Algoritmo de paso a Runs (V)Ejemplo de secuencia ArrayRuns

5 15 1 1 1 11 2 0 0 4 3 1 3 4 0 0 63 6 0 0 4 3 1 3 40 0 2 3 5 3 2 0

Ejemplo de correspondencia en bits (slo datos) 1 0001 0001 1011 0010 0 0100 0011 0001 0011 0100 0 0110 0011 0110 0 0100 0011 0001 0011 0100 0 0010 0011 0101 0011 0010Caractersticas de representacin

Algoritmo inversoPasos del algoritmo:tomar el conjunto de bits Runs y la informacin del nmero de filas y columnascon el nmero de columnas, calcular el nmero de bits con el que se codifica cada nmero y decodificar las frecuenciascodificar de bits a ArrayRunscodificar de ArrayRuns a representacin simpleCaractersticas de representacin

Esquema de representacin (resumen)Ejemplo de matriz simple

101111111111100000011101110000000000111000000000011101110000001110000011100

Ejemplo de correspondencia Runs en bits (slo datos) 1 0001 0001 1011 0010 0 0100 0011 0001 0011 0100 0 0110 0011 0110 0 0100 0011 0001 0011 0100 0 0010 0011 0101 0011 0010Caractersticas de representacin

OperacionesComplementariaUninInterseccinDiferenciaRotacinTraslacinOtras transformacionesOperaciones

Complementaria (I)Algoritmo en representacin simplepara cada bit de la matriz, invertirloes necesario recorrer toda la matrizAlgoritmo en representacin Runspor cada fila de la matriz, invertir el primer bitmuy eficienteOperaciones

Complementaria (II)Ejemplo de matriz en representacin simple

101111111111100000011101110000000000111000000000011101110000001110000011100Ejemplo complementaria

010000000000011111100010001111111111000111111111100010001111110001111100011Operaciones

Complementaria (III)Ejemplo de matriz en representacin Runs

1 : 1 1 11 20 : 4 3 1 3 40 : 6 3 60 : 4 3 1 3 40 : 2 3 5 3 2Ejemplo complementaria

0 : 1 1 11 21 : 4 3 1 3 41 : 6 3 61 : 4 3 1 3 41 : 2 3 5 3 2Operaciones

Unin (I)Algoritmo en representacin simplepara cada bit de la primera matriz, realizar la operacin or con el equivalente de la segundaes necesario recorrer toda la matrizAlgoritmo en representacin Runsse procesa de igual manera, pero tan slo las diferencias de frecuenciasms eficiente, puesto que recorre frecuencias, no bitsdifcil de comprobar visualmenteOperaciones

Unin (II)Ejemplo de matrices, representacin simple

101111111111100000011101110000

000011101110000000000111000000Ejemplo unin

101111111111100000011111110000

Operaciones

Unin (III)Ejemplo de matrices, representacin Runs

1 : 1 1 11 20 : 4 3 1 3 4

0 : 4 3 1 3 40 : 6 3 6Ejemplo unin

1 : 1 1 11 20 : 4 7 4

Operaciones

Interseccin (I)Algoritmo en representacin simplepara cada bit de la primera matriz, realizar la operacin and con el equivalente de la segundaes necesario recorrer toda la matrizAlgoritmo en representacin Runsse procesa de igual manera, pero tan slo las diferencias de frecuenciasms eficiente, puesto que recorre frecuencias, no bitsdifcil de comprobar visualmenteOperaciones

Interseccin (II)Ejemplo de matrices, representacin simple

101111111111100000011101110000

000011101110000000000111000000Ejemplo interseccin

000011101110000000000101000000Operaciones

Interseccin (III)Ejemplo de matrices, representacin Runs

1 : 1 1 11 20 : 4 3 1 3 4

0 : 4 3 1 3 40 : 6 3 6Ejemplo interseccin

0 : 4 3 1 3 40 : 6 1 1 1 6Operaciones

Diferencia (I)Algoritmo en representacin simplepara cada bit de la primera matriz, realizar la diferencia con el equivalente de la segundaes necesario recorrer toda la matrizAlgoritmo en representacin Runsse procesa de igual manera, pero tan slo las diferencias de frecuenciasms eficiente, puesto que recorre frecuencias, no bitsdifcil de comprobar visualmenteOperaciones

Diferencia (II)Ejemplo de matrices, representacin simple

101111111111100000011101110000

000011101110000000000111000000Ejemplo diferencia

101100010001100000011000110000

Operaciones

Diferencia (III)Ejemplo de matrices, representacin Runs

1 : 1 1 11 20 : 4 3 1 3 4

0 : 4 3 1 3 40 : 6 3 6Ejemplo diferencia

1 : 1 1 2 3 1 3 2 20 : 4 2 3 2 4

Operaciones

RotacinAlgoritmo en representacin simplepara cada bit de la matriz, existen transformaciones matemticas que modifican su posicinpueden ser funciones muy complejasAlgoritmo en representacin Runses necesario conocer exactamente los bits de los alrededores, por lo que resulta inevitable tener que transformar de nuevo a matriz simpleOperaciones

Traslacin (I)Algoritmo en representacin simpledependiendo de la direccin, se coloca la fila o columna primera tras la ltima o viceversamuy eficiente, pues slo hay que modificar los ndicesAlgoritmo en representacin Runsse procesa de igual manera al trasladar filas; con las columnas deben modificarse las frecuencias iniciales y finales de cada filaigual de eficiente en las filas, menos en las columnasOperaciones

Traslacin (II)Ejemplo de matrices, representacin simple

101111111111100000011101110000000000111000000000011101110000001110000011100Ejemplo traslacin (1 abajo, 2 izquierda)

111000001110000111111111110010001110111000000000011100000000001110111000000Operaciones

Traslacin (III)Ejemplo de matriz en representacin Runs

1 : 1 1 11 20 : 4 3 1 3 40 : 6 3 60 : 4 3 1 3 40 : 2 3 5 3 2Ejemplo traslacin (1 abajo, 2 izquierda)

1 : 3 5 3 41 : 11 2 1 10 : 2 3 1 3 60 : 4 3 80 : 2 3 1 3 6Operaciones

Otras transformacionesAlgoritmo en representacin simplepara cada grupos de bit de la matriz, se aplican las transformaciones matemticas dadas pueden ser funciones muy complejasAlgoritmo en representacin Runspara cualquier grupo de bits, salvo en transformaciones lineales muy simples de un solo elemento, es necesario transformar de nuevo a matriz simpleOperaciones