Trouver la longueur minimale RLE
https://stackoverflow.com/questions/2261318
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
L'algorithme RLE classique compresse les données en utilisant des nombres pour représenter combien de fois le caractère suivant un numéro apparaît dans le texte à cette position. Par exemple:
AAABBAAABBCECE => 3A2B3A2B1C1E1C1E
Cependant, dans l'exemple ci-dessus, que les résultats de la méthode dans l'espace encore plus utilisés par le texte compressé. Une meilleure idée serait d'utiliser des chiffres pour représenter le nombre de fois sous-chaîne après un numéro apparaît dans le texte donné. Par exemple:
AAABBAAABBCECE => 2AAABB2CE ( "CE" deux fois "AAABB" deux fois, puis).
Maintenant, ma question est: comment pourrais-je mettre en œuvre un algorithme efficace qui trouve le nombre minimum de caractères dans une RLE optimale en utilisant cette méthode? méthodes de force brute existent, mais je besoin de quelque chose plus rapide (au plus O (longueur 2 ) ). Peut-être que nous pouvons utiliser la programmation dynamique?
La solution
Il peut être fait dans quadratique cube temps quadratique par programmation dynamique.
Voici un code 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]
Vous pouvez reconstruire le codage réel en se souvenant de vos choix le long du chemin.
Je l'ai laissé un détail mineur, qui est que nous pourrions avoir à utiliser un octet supplémentaire pour maintenir C + 1 si C est grande. Si vous utilisez ints 32 bits, cela ne viendra pas dans un contexte où l'exécution de cet algorithme est possible. Si vous utilisez parfois ints plus courtes pour économiser de l'espace, alors vous devrez penser, et peut-être ajouter une autre dimension à votre table en fonction de la taille de la dernière C. En théorie, cela pourrait ajouter un facteur log (N), mais Je ne pense pas que cela ressortira dans la pratique.
Edit: Pour le bénéfice de @Moron, voici le même code avec plusieurs instructions d'impression, de sorte que vous pouvez voir plus facilement ce que l'algorithme pense:
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]
Les dernières lignes de sa sortie sur ABCDABCDABCDBCD sont comme ceci:
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!
Autres conseils
Je ne fonctionnera ici crois pas une programmation dynamique, comme vous pourriez avoir des sous-chaînes environ la moitié de la longueur de la chaîne complète dans la solution. On dirait que vous avez besoin d'utiliser la force brute. Pour un problème, consultez le Lempel-Ziv- Welch algorithme . Il est un algorithme efficace qui trouve un codage minimal en utilisant des sous-chaînes.
Une façon très courante pour coder les données compressées RLE est de désigner un octet spécial comme « DLE » (désolé, je ne me souviens pas de ce que ce terme signifie), qui signifie « l'autre est un nombre suivi d'un octet ».
De cette façon, seule la répétition des séquences doit être codé. En général, le symbole DLE est choisi pour minimiser le risque de celui-ci dans l'état naturel les données non compressées.
Pour votre exemple original, nous allons régler le point (ou point) comme DLE, cela encoder votre exemple comme suit:
AAABBAAABBCECE => 3A2B3A2B1C1E1C1E <-- your encoding
AAABBAAABBCECE => .3ABB.3ABBCECE <-- my encoding
Vous n'encoder une séquence si elle finit effectivement comme un gain de place. Si vous limitez la longueur des séquences à 255, de sorte que le nombre correspond à un octet, une séquence prend ainsi 3 octets, le DLE, le comte, et l'octet à répéter. On pourrait probablement pas coder pour des séquences de 3 octets, soit parce que le décodage les porte un peu plus au-dessus d'une séquence non codée.
Dans votre exemple trivial, l'économie est couinent, mais si vous essayez de compresser un bitmap contenant une capture d'écran d'un programme essentiellement blanc, comme le Bloc-notes ou d'un navigateur, vous verrez de vraies économies d'espace.
Si vous rencontrez le caractère DLE naturellement, juste émettre un nombre de 0, puisque nous savons que nous ne pourrions jamais encoder une séquence 0 longueur, le DLE suivi d'un 0 octet signifie que vous décodez comme un seul octet DLE .
façons de trouver des sous-chaînes correspondant très intelligent peut conduire à envisager des arbres de suffixe et des tableaux de suffixe. Penser à des réseaux de suffixe et la compression peut vous conduire à la http: //en.wikipedia .org / wiki / Burrows% E2% 80% 93Wheeler_transform . Cela peut être la façon la plus élégante de souping l'encodage de longueur d'exécution.
