Das Finden der Mindestlänge RLE
https://stackoverflow.com/questions/2261318
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Der klassische RLE-Algorithmus komprimiert die Daten von Zahlen unter Verwendung darzustellen, wie oft die Zeichen nach einer Nummer im Text erscheinen an dieser Position. Zum Beispiel:
AAABBAAABBCECE => 3A2B3A2B1C1E1C1E
jedoch in dem obigen Beispiel, dass die Methode führt zu noch mehr Platz durch den komprimierten Text verwendet wird. Eine bessere Idee wäre Zahlen zu verwenden, um darzustellen, wie oft die Teilzeichenfolge nach einer Reihe erscheint im gegebenen Text. Zum Beispiel:
AAABBAAABBCECE => 2AAABB2CE ( "AAABB" zweimal, dann "CE" zweimal).
Nun, meine Frage ist: Wie kann ich einen effizienten Algorithmus, dass Funde aus der minimalen Anzahl von Zeichen in einem optimalen RLE implementieren diese Methode? Brute-Force-Methoden existieren, aber ich brauche etwas schneller (in den meisten O (Länge 2 ) ). Vielleicht können wir die dynamische Programmierung verwenden?
Lösung
Es kann in quadratischen kubischer quadratische Zeit über dynamische Programmierung.
Hier finden Sie einige Python-Code:
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]
Sie können die tatsächliche Codierung rekonstruieren, indem Sie Ihre Auswahl auf dem Weg zu erinnern.
Ich habe eine kleine Falten ausgelassen, das ist, dass wir haben könnten, ein zusätzliches Byte verwenden C + 1 zu halten, wenn C groß ist. Wenn Sie mit 32-Bit ints, wird dies nicht in jedem Kontext kommen, wo dieser Algorithmus Laufzeit möglich ist. Wenn Sie manchmal kürzer Ints mit Platz zu sparen, dann werden Sie es denken, und vielleicht eine neue Dimension in Ihre Tabelle hinzufügen auf der Größe der neuesten C. In der Theorie basiert, könnte dies ein Protokoll (N) Faktor hinzufügen, aber ich glaube nicht, dies in der Praxis offensichtlich sein wird.
Edit: Zum Wohle @Moron, hier ist der gleiche Code mit mehr print-Anweisungen, so dass Sie leichter sehen kann, was der Algorithmus denkt:
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]
Die letzten Zeilen seiner Ausgabe auf ABCDABCDABCDBCD sind wie folgt:
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!
Andere Tipps
Ich glaube nicht, dynamische Programmierung hier arbeiten, wie Sie Unterketten etwa die Hälfte der Länge der vollständigen Zeichenfolge in der Lösung haben könnten. Sieht aus wie Sie benötigen Brute-Force zu verwenden. Für ein verwandtes Problem Besuche den Lempel-Ziv- Welch Algorithmus . Es ist ein effizienter Algorithmus, der durch die Verwendung von Teil eine minimale Codierung findet.
Eine sehr häufige Art und Weise zu kodieren RLE komprimierten Daten ein spezielles Byte als „DLE“ zu bezeichnen (sorry, ich weiß nicht mehr, was dieser Begriff steht für), die Mittel „die nächsten eine Zählung gefolgt von einem Byte ist “.
Auf diese Weise nur Sequenzen zu wiederholen muss codiert werden. Typischerweise wird das DLE Symbol gewählt, um die Chance, es natürlich in den unkomprimierten Daten auftritt, zu minimieren.
Für Ihr ursprüngliches Beispiel, lassen Sie sich stellen Sie den Punkt (oder Punkt) als DLE, das Ihr Beispiel kodieren würde wie folgt:
AAABBAAABBCECE => 3A2B3A2B1C1E1C1E <-- your encoding
AAABBAAABBCECE => .3ABB.3ABBCECE <-- my encoding
Sie würden nur eine Sequenz kodieren, wenn sie als platzsparend tatsächlich endet. Wenn Sie die Länge der Sequenzen auf 255 zu begrenzen, so dass die Zählung fits in einem Byte, also eine Folge 3 Bytes in Anspruch nimmt, DLE, der Graf, und das Byte zu wiederholen. Sie würden wahrscheinlich nicht kodieren 3-Byte-Sequenzen entweder, weil die Decodierung trägt etwas mehr Aufwand als eine nicht-codierte Sequenz.
In Ihrem trivialen Beispiel, die Einsparung ist noch nicht existiert, aber wenn Sie versuchen, eine Bitmap zu komprimieren, einen Screenshot von einem meist weiß-Programm enthält, wie Notepad oder einen Browser, dann werden Sie echte Raumeinsparungen sehen.
Wenn Sie die Zeichen DLE natürlich begegnen sollten, emittieren nur eine Zählung von 0, da wir wissen, dass wir nie eine 0 Längen-Sequenz kodieren, gefolgt die DLE durch einen 0-Byte bedeutet, dass Sie es als ein DLE Byte dekodieren .
Sehr clevere Möglichkeiten der Anpassung Teil finden können unter Berücksichtigung Suffix Bäume und Suffixarray führen. Das Nachdenken über Suffixarray und Kompression können Sie auf der http: //en.wikipedia .org / wiki / Burrows% E2% 80% 93Wheeler_transform . Das mag die eleganteste Art und Weise von Ausbauen von Lauflängencodierung sein.
