Нахождение минимальной длины RLE
https://stackoverflow.com/questions/2261318
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Классический алгоритм RLE сжимает данные, используя числа, чтобы определить, сколько раз символ, следующий за числом, появляется в тексте в этой позиции.Например:
АААББАААББЦЕ => 3A2B3A2B1C1E1C1E
Однако в приведенном выше примере этот метод приводит к тому, что сжатый текст использует еще больше места.Лучшей идеей было бы использовать числа для обозначения того, сколько раз подстрока следующий номер появляется в данном тексте.Например:
AAABBAAABBCECE => 2AAABB2CE («AAABB» дважды, затем «CE» дважды).
Теперь мой вопрос:как я могу реализовать эффективный алгоритм, который определяет минимальное количество символов в оптимальном RLE, используя этот метод?Методы грубой силы существуют, но мне нужно что-то более быстрое (максимум О(длина2)).Возможно, мы можем использовать динамическое программирование?
Решение
Это можно сделать в квадратичный кубический квадратичное время посредством динамического программирования.
Вот некоторый код 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]
Вы можете восстановить фактическую кодировку, запоминая свой выбор по пути.
Я упустил небольшую проблему: нам, возможно, придется использовать дополнительный байт для хранения C+1, если C велико.Если вы используете 32-битные целые числа, это не произойдет ни в каком контексте, где возможно выполнение этого алгоритма.Если вы иногда используете более короткие целые числа для экономии места, вам придется подумать об этом и, возможно, добавить в таблицу еще одно измерение, основанное на размере последней версии C.Теоретически это может добавить коэффициент log(N), но я не думаю, что это будет очевидно на практике.
Редактировать:Для удобства @Moron вот тот же код с большим количеством операторов печати, чтобы вам было легче увидеть, что думает алгоритм:
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!
Другие советы
Я не верю, что динамическое программирование здесь будет работать, поскольку в решении могут быть подстроки примерно в половину длины полной строки.Похоже, вам придется применить грубую силу.Для получения информации о соответствующей проблеме см. Алгоритм Лемпеля-Зива-Уэлча.Это эффективный алгоритм, который находит минимальную кодировку с помощью подстрок.
Очень распространенный способ кодирования сжатых данных RLE — обозначить специальный байт как «DLE» (извините, я не помню, что означает этот термин), что означает «следующий — это счетчик, за которым следует байт».
Таким образом, необходимо кодировать только повторяющиеся последовательности.Обычно символ DLE выбирается для минимизации вероятности его естественного появления в несжатых данных.
Для вашего исходного примера давайте установим точку (или точку) в качестве DLE. Это закодирует ваш пример следующим образом:
AAABBAAABBCECE => 3A2B3A2B1C1E1C1E <-- your encoding
AAABBAAABBCECE => .3ABB.3ABBCECE <-- my encoding
Вы будете кодировать последовательность только в том случае, если она действительно экономит место.Если вы ограничите длину последовательностей до 255, чтобы счетчик умещался в байт, последовательность, таким образом, займет 3 байта, DLE, счетчик и байт для повторения.Вероятно, вы также не будете кодировать 3-байтовые последовательности, поскольку их декодирование требует немного больше накладных расходов, чем некодированная последовательность.
В вашем тривиальном примере сохранение отсутствует, но если вы попытаетесь сжать растровое изображение, содержащее снимок экрана в основном белой программы, такой как Блокнот или браузер, то вы увидите реальную экономию места.
Если вы естественным образом встретите символ DLE, просто введите счетчик 0, поскольку мы знаем, что никогда не будем кодировать последовательность длиной 0, за DLE следует 0-байт, что означает, что вы декодируете его как один байт DLE.
Очень умные способы поиска совпадающих подстрок могут привести к рассмотрению суффиксных деревьев и суффиксных массивов.Размышления о суффиксных массивах и сжатии могут привести вас к следующему: http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform.Это, возможно, самый элегантный способ улучшить кодирование длины серии.
