Encontrar la longitud mínima RLE
https://stackoverflow.com/questions/2261318
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
El algoritmo RLE clásica comprime los datos mediante el uso de números para representar el número de veces que aparezca el carácter que sigue a un número en el texto en esa posición. Por ejemplo:
AAABBAAABBCECE => 3A2B3A2B1C1E1C1E
Sin embargo, en el ejemplo anterior, que los resultados del método en aún más espacio siendo utilizados por el texto comprimido. Una mejor idea sería utilizar números para representar el número de veces que el subcadena después de un número aparece en el texto dado. Por ejemplo:
AAABBAAABBCECE => 2AAABB2CE ( "AAABB" dos veces, a continuación, "CE" dos veces).
Ahora, mi pregunta es: ¿cómo podría implementar un algoritmo eficiente que descubre el número mínimo de caracteres en una óptima RLE usando este método? Existen métodos de fuerza bruta, pero necesitan algo más rápido (como máximo O (longitud 2 ) ). Tal vez podemos utilizar la programación dinámica?
Solución
Se puede hacer en cuadrática cúbico tiempo cuadrática a través de la programación dinámica.
Aquí hay un código Python:
import sys
import numpy as np
bignum = 10000
S = sys.argv[1] #'AAABBAAABBCECE'
N = len(S)
# length of longest substring match bet s[i:] and s[j:]
maxmatch = np.zeros( (N+1,N+1), dtype=int)
for i in xrange(N-1,-1,-1):
for j in xrange(i+1,N):
if S[i] == S[j]:
maxmatch[i,j] = maxmatch[i+1,j+1]+1
# P[n,k] = cost of encoding first n characters given that last k are a block
P = np.zeros( (N+1,N+1),dtype=int ) + bignum
# Q[n] = cost of encoding first n characters
Q = np.zeros(N+1, dtype=int) + bignum
# base case: no cost for empty string
P[0,0]=0
Q[0]=0
for n in xrange(1,N+1):
for k in xrange(1,n+1):
if n-2*k >= 0:
# s1, s2 = S[n-k:n], S[n-2*k:n-k]
# if s1 == s2:
if maxmatch[n-2*k,n-k] >=k:
# Here we are incrementing the count: C x_1...x_k -> C+1 x_1...x_k
P[n,k] = min(P[n,k], P[n-k,k])
print 'P[%d,%d] = %d' % (n,k,P[n,k])
# Here we are starting a new block: 1 x_1...x_k
P[n,k] = min(P[n,k], Q[n-k] + 1 + k)
print 'P[%d,%d] = %d' % (n,k,P[n,k])
for k in xrange(1,n+1):
Q[n] = min(Q[n], P[n,k])
print
print Q[N]
Puede reconstruir la codificación real recordando sus opciones a lo largo del camino.
He dejado fuera una arruga de menor importancia, y es que podríamos tener que utilizar un byte adicional para sostener C + 1 si C es grande. Si está utilizando enteros de 32 bits, esto no va a llegar en cualquier contexto en tiempo de ejecución de este algoritmo es factible. Si está utilizando a veces enteros cortos para ahorrar espacio, entonces tendrá que pensar en ello, y tal vez añadir otra dimensión a su mesa en función del tamaño de la última C. En teoría, esto podría añadir un registro (N) factor, pero no creo que esto será evidente en la práctica.
Editar: Para el beneficio de @Moron, aquí es el mismo código con más declaraciones de impresión, por lo que se puede ver más fácilmente lo que el algoritmo está pensando:
import sys
import numpy as np
bignum = 10000
S = sys.argv[1] #'AAABBAAABBCECE'
N = len(S)
# length of longest substring match bet s[i:] and s[j:]
maxmatch = np.zeros( (N+1,N+1), dtype=int)
for i in xrange(N-1,-1,-1):
for j in xrange(i+1,N):
if S[i] == S[j]:
maxmatch[i,j] = maxmatch[i+1,j+1]+1
# P[n,k] = cost of encoding first n characters given that last k are a block
P = np.zeros( (N+1,N+1),dtype=int ) + bignum
# Q[n] = cost of encoding first n characters
Q = np.zeros(N+1, dtype=int) + bignum
# base case: no cost for empty string
P[0,0]=0
Q[0]=0
for n in xrange(1,N+1):
for k in xrange(1,n+1):
if n-2*k >= 0:
# s1, s2 = S[n-k:n], S[n-2*k:n-k]
# if s1 == s2:
if maxmatch[n-2*k,n-k] >=k:
# Here we are incrementing the count: C x_1...x_k -> C+1 x_1...x_k
P[n,k] = min(P[n,k], P[n-k,k])
print "P[%d,%d] = %d\t I can encode first %d characters of S in only %d characters if I use my solution for P[%d,%d] with %s's count incremented" % (n\
,k,P[n,k],n,P[n-k,k],n-k,k,S[n-k:n])
# Here we are starting a new block: 1 x_1...x_k
P[n,k] = min(P[n,k], Q[n-k] + 1 + k)
print 'P[%d,%d] = %d\t I can encode first %d characters of S in only %d characters if I use my solution for Q[%d] with a new block 1%s' % (n,k,P[n,k],n,Q[\
n-k]+1+k,n-k,S[n-k:n])
for k in xrange(1,n+1):
Q[n] = min(Q[n], P[n,k])
print
print 'Q[%d] = %d\t I can encode first %d characters of S in only %d characters!' % (n,Q[n],n,Q[n])
print
print Q[N]
Las últimas líneas de su salida en ABCDABCDABCDBCD son así:
Q[13] = 7 I can encode first 13 characters of S in only 7 characters!
P[14,1] = 9 I can encode first 14 characters of S in only 9 characters if I use my solution for Q[13] with a new block 1C
P[14,2] = 8 I can encode first 14 characters of S in only 8 characters if I use my solution for Q[12] with a new block 1BC
P[14,3] = 13 I can encode first 14 characters of S in only 13 characters if I use my solution for Q[11] with a new block 1DBC
P[14,4] = 13 I can encode first 14 characters of S in only 13 characters if I use my solution for Q[10] with a new block 1CDBC
P[14,5] = 13 I can encode first 14 characters of S in only 13 characters if I use my solution for Q[9] with a new block 1BCDBC
P[14,6] = 12 I can encode first 14 characters of S in only 12 characters if I use my solution for Q[8] with a new block 1ABCDBC
P[14,7] = 16 I can encode first 14 characters of S in only 16 characters if I use my solution for Q[7] with a new block 1DABCDBC
P[14,8] = 16 I can encode first 14 characters of S in only 16 characters if I use my solution for Q[6] with a new block 1CDABCDBC
P[14,9] = 16 I can encode first 14 characters of S in only 16 characters if I use my solution for Q[5] with a new block 1BCDABCDBC
P[14,10] = 16 I can encode first 14 characters of S in only 16 characters if I use my solution for Q[4] with a new block 1ABCDABCDBC
P[14,11] = 16 I can encode first 14 characters of S in only 16 characters if I use my solution for Q[3] with a new block 1DABCDABCDBC
P[14,12] = 16 I can encode first 14 characters of S in only 16 characters if I use my solution for Q[2] with a new block 1CDABCDABCDBC
P[14,13] = 16 I can encode first 14 characters of S in only 16 characters if I use my solution for Q[1] with a new block 1BCDABCDABCDBC
P[14,14] = 15 I can encode first 14 characters of S in only 15 characters if I use my solution for Q[0] with a new block 1ABCDABCDABCDBC
Q[14] = 8 I can encode first 14 characters of S in only 8 characters!
P[15,1] = 10 I can encode first 15 characters of S in only 10 characters if I use my solution for Q[14] with a new block 1D
P[15,2] = 10 I can encode first 15 characters of S in only 10 characters if I use my solution for Q[13] with a new block 1CD
P[15,3] = 11 I can encode first 15 characters of S in only 11 characters if I use my solution for P[12,3] with BCD's count incremented
P[15,3] = 9 I can encode first 15 characters of S in only 9 characters if I use my solution for Q[12] with a new block 1BCD
P[15,4] = 14 I can encode first 15 characters of S in only 14 characters if I use my solution for Q[11] with a new block 1DBCD
P[15,5] = 14 I can encode first 15 characters of S in only 14 characters if I use my solution for Q[10] with a new block 1CDBCD
P[15,6] = 14 I can encode first 15 characters of S in only 14 characters if I use my solution for Q[9] with a new block 1BCDBCD
P[15,7] = 13 I can encode first 15 characters of S in only 13 characters if I use my solution for Q[8] with a new block 1ABCDBCD
P[15,8] = 17 I can encode first 15 characters of S in only 17 characters if I use my solution for Q[7] with a new block 1DABCDBCD
P[15,9] = 17 I can encode first 15 characters of S in only 17 characters if I use my solution for Q[6] with a new block 1CDABCDBCD
P[15,10] = 17 I can encode first 15 characters of S in only 17 characters if I use my solution for Q[5] with a new block 1BCDABCDBCD
P[15,11] = 17 I can encode first 15 characters of S in only 17 characters if I use my solution for Q[4] with a new block 1ABCDABCDBCD
P[15,12] = 17 I can encode first 15 characters of S in only 17 characters if I use my solution for Q[3] with a new block 1DABCDABCDBCD
P[15,13] = 17 I can encode first 15 characters of S in only 17 characters if I use my solution for Q[2] with a new block 1CDABCDABCDBCD
P[15,14] = 17 I can encode first 15 characters of S in only 17 characters if I use my solution for Q[1] with a new block 1BCDABCDABCDBCD
P[15,15] = 16 I can encode first 15 characters of S in only 16 characters if I use my solution for Q[0] with a new block 1ABCDABCDABCDBCD
Q[15] = 9 I can encode first 15 characters of S in only 9 characters!
Otros consejos
No creo que la programación dinámica va a trabajar aquí, ya que podría tener sub-cuerdas alrededor de la mitad de la longitud de la cadena completa en la solución. Parece que es necesario utilizar la fuerza bruta. Para un problema relacionado, consulte el Lempel-Ziv- Welch algoritmo . Es un algoritmo eficiente que encuentra una codificación mínima mediante el uso de subcadenas.
Una forma muy común para codificar datos comprimidos RLE es designar un byte especial como el "DLE" (lo siento, no recuerdo lo que significa esa expresión a), que significa "el siguiente es un recuento seguido de un byte ".
De esta manera, solamente la repetición de secuencias necesita ser codificado. Normalmente se elige el símbolo DLE para reducir al mínimo la posibilidad de que se produce de manera natural en los datos sin comprimir.
Para su original ejemplo, vamos a configurar el punto (o puntos) como el DLE, esto sería codificar el ejemplo de la siguiente manera:
AAABBAAABBCECE => 3A2B3A2B1C1E1C1E <-- your encoding
AAABBAAABBCECE => .3ABB.3ABBCECE <-- my encoding
Usted sólo codificar una secuencia de si en realidad termina como el ahorro de espacio. Si se limita la longitud de las secuencias a 255, por lo que el recuento cabe en un byte, una secuencia por lo tanto tarda 3 bytes, el DLE, el recuento y el byte de repetir. Probablemente no codificar secuencias de 3 bytes o bien, porque la descodificación de los lleva ligeramente más sobrecarga de una secuencia no codificada.
En el ejemplo trivial, el ahorro es inexistente, pero si intenta comprimir un mapa de bits que contiene una captura de pantalla de un programa en su mayoría blancos, como el Bloc de notas, o un navegador, entonces usted verá un ahorro de espacio reales.
Si encuentra el carácter DLE, naturalmente, solo emiten un recuento de 0, ya que sabemos que nunca hubiéramos codificar una secuencia de longitud 0, el DLE seguido de un 0 bytes significa que decodificarlo como un solo byte DLE .
maneras muy inteligente de búsqueda de subcadenas coincidentes pueden conducir a considerar sufijo árboles y sufijo arrays. Pensando en sufijo arrays y compresión que puede llevar a la http: //en.wikipedia .org / wiki / Burrows% E2% 80% 93Wheeler_transform . Esa puede ser la forma más elegante de souping hasta la codificación de longitud de ejecución.
