العثور على الحد الأدنى من طول RLE
https://stackoverflow.com/questions/2261318
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
الكلاسيكية RLE خوارزمية ضغط البيانات باستخدام الأرقام تمثل عدد مرات الحرف التالية عدد يظهر في النص في هذا الموقف.على سبيل المثال:
AAABBAAABBCECE => 3A2B3A2B1C1E1C1E
ومع ذلك ، في المثال أعلاه أن الأسلوب يؤدي إلى المزيد من المساحة المستخدمة من قبل مضغوط النص.فكرة أفضل استخدام الأرقام تمثل عدد مرات فرعية بعد عدد يظهر في النص.على سبيل المثال:
AAABBAAABBCECE => 2AAABB2CE ("AAABB" مرتين ، ثم "CE" مرتين).
الآن سؤالي هو:كيف يمكنني تنفيذ خوارزمية فعالة أن يكتشف الحد الأدنى لعدد الأحرف في الأمثل RLE باستخدام هذا الأسلوب ؟ أساليب القوة الغاشمة موجودة ، ولكن أنا بحاجة إلى شيء أسرع (على الأكثر O(طول2)).ربما يمكننا استخدام البرمجة الديناميكية?
المحلول
فإنه يمكن القيام به في الدرجة الثانية مكعب الدرجة الثانية من الوقت عن طريق البرمجة الديناميكية.
هنا بعض كود بايثون:
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]
يمكنك إعادة الترميز الفعلي بتذكر الخيارات الخاصة بك على طول الطريق.
لقد تركت قاصر التجاعيد ، وهو أننا قد تضطر إلى استخدام إضافية بايت عقد C+1 إذا كان C هو كبيرة.إذا كنت تستخدم 32 بت رجات ، وهذا لن يأتي في أي سياق هذه الخوارزمية وقت ممكن.إذا كنت في بعض الأحيان باستخدام أقصر رجات لتوفير مساحة ثم سيكون لديك للتفكير في الامر ، وربما تضيف بعدا آخر إلى الجدول الخاص بك استنادا إلى حجم آخر C.من الناحية النظرية ، هذا إضافة سجل(ن) عامل, ولكن أنا لا أعتقد أن هذا سيكون واضحا في الممارسة.
تحرير:لصالح @معتوه, هنا هو نفس الكود مع طباعة البيانات بحيث يمكنك أن ترى بسهولة ما خوارزمية التفكير:
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]
السطور الأخيرة من انتاجها على ABCDABCDABCDBCD مثل ذلك:
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!
نصائح أخرى
لا أعتقد أن البرمجة الديناميكية العمل هنا ، هل يمكن أن يكون السلاسل الفرعية عن نصف طول سلسلة كاملة في الحل.يبدو أنك بحاجة إلى استخدام القوة الغاشمة.عن ذات المشكلة ، تحقق Lempel-Ziv-ويلش الخوارزمية.وهو كفاءة الخوارزمية التي يجد الحد الأدنى من ترميز باستخدام سلاسل فرعية.
طريقة شائعة جدا لتشفير RLE البيانات المضغوطة إلى تعيين خاصة بايت باسم "DLE" (آسف, أنا لا أتذكر ما هذا المصطلح يرمز) الذي يعني "القادم هو عدد تليها بايت".
بهذه الطريقة فقط تكرار تسلسل يحتاج إلى ترميز.عادة DLE الرمز المختار لتقليل فرصة من التي تحدث بشكل طبيعي في البيانات غير المضغوطة.
بالنسبة الأصلي الخاص بك على سبيل المثال, دعونا تعيين وقف كامل (أو نقطة) كما DLE, هذا من شأنه أن ترميز المثال الخاص بك على النحو التالي:
AAABBAAABBCECE => 3A2B3A2B1C1E1C1E <-- your encoding
AAABBAAABBCECE => .3ABB.3ABBCECE <-- my encoding
كنت فقط ترميز سلسلة إذا كان في الواقع وينتهي إلى توفير مساحة.إذا كان يمكنك الحد من طول تسلسل إلى 255 ، بحيث عد يناسب في بايت تسلسل وبالتالي يأخذ 3 بايت, DLE, العد, و البايت إلى تكرار.ربما لن ترميز 3 بايت تسلسل إما لأن فك تلك يحمل أكثر قليلا من فوق غير المشفرة تسلسل.
في تافهة سبيل المثال ، توفير nonexistant, ولكن إذا كنت في محاولة لضغط صورة نقطية تحتوي على لقطة في الغالب بيضاء برنامج مثل المفكرة أو المتصفح ، ثم سترى الفضاء الحقيقي المدخرات.
إذا كان يجب أن تواجه DLE الشخصية بشكل طبيعي ، فقط تنبعث من العد 0, لأننا نعلم أننا لن ترميز 0-طول التسلسل ، DLE تليها 0 بايت يعني أن تترجم على أنها واحدة DLE بايت.
ذكي جدا سبل إيجاد مطابقة سلاسل فرعية قد يؤدي إلى النظر لاحقة الأشجار لاحقة المصفوفات.التفكير لاحقة المصفوفات و ضغط قد يؤدي إلى http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform.التي قد تكون الطريقة الأكثر أناقة من souping يصل ترميز طول التشغيل.
