Нахождение минимальной длины RLE
Классический алгоритм RLE сжимает данные при помощи чисел для представления, сколько раз символ после числа появляется в тексте в том положении. Например:
AAABBAAABBCECE => 3A2B3A2B1C1E1C1E
Однако в вышеупомянутом примере, тот метод приводит еще к большему количеству пространства, используемого сжатым текстом. Лучшая идея состояла бы в том, чтобы использовать числа для представления, сколько раз подстрока после числа появляется в данном тексте. Например:
AAABBAAABBCECE => 2AAABB2CE ("AAABB" дважды, затем "CE" дважды).
Теперь, мой вопрос: как я мог реализовать эффективный алгоритм, который узнает минимальное количество символов в оптимальном RLE, использующем этот метод? Методы грубой силы существуют, но мне нужно что-то быстрее (в большей части O (length2)). Возможно, мы можем использовать динамическое программирование?
4 ответа
Это можно сделать в квадратичном кубическом квадратичном времени с помощью динамического программирование.
Вот код 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. Теоретически это может добавить коэффициент журнала (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!
Как вы связываете код? Например, при создании общей библиотеки можно указать флаги компиляции для позиционно-независимого кода, например -fPIC (gcc/g + +).
-121--4043386- Как отмечает DVK, если мы запустим код с комментариями use vars , мы получим предупреждение об использовании переменных только один раз.
Другой способ подавления предупреждения - на стороне вызывающего абонента, т.е. в вызове уменьшить , а не в функции уменьшить . Это необходимо при использовании функций из List:: Util или List:: MureUtils , которые принимают ссылки на код (например, попарно ). Оба этих подхода работают на стороне вызывающего абонента:
my @sums = pairwise { no warnings 'once'; $a + $b } @x, @y;
my @sums = pairwise { our($a, $b); $a + $b } @x, @y;
Очень умные способы поиска соответствующих подстрок могут привести к рассмотрению суффиксных деревьев и массивов суффиксов. Анализ массивов суффиксов и сжатие может привести к http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform . Это может быть самым элегантным способом закодирования длины прогона.
Используйте grep или grepl, чтобы найти наблюдения с пробелами и под, чтобы избавиться от них.
names<-c("Ganga Din\t","Shyam Lal","Bulbul ")
grep("[[:space:]]+$",names)
[1] 1 3
grepl("[[:space:]]+$",names)
[1] TRUE FALSE TRUE
sub("[[:space:]]+$","",names)
[1] "Ganga Din" "Shyam Lal" "Bulbul"
Имеются как обоснованные, так и необоснованные случаи генерации кода. Однако правильная генерация кода может дать следующие преимущества:
- Оптимальный код времени выполнения - библиотеки обрабатывают материал во время выполнения, в то время как вы можете устранить множество механизмов времени выполнения, анализируя структуру кодов во время создания.
- Устранение ошибок, введенных при выполнении повторяющейся работы.
- Лучшее понимание вашего кода, генерация обычно приводит к более высокому уровню «модели»; где модель используется для представления того, что необходимо создать.
- Уменьшение LOC - тысячи строк могут привести к миллионам строк выходного кода.
Я не верю, что динамическое программирование будет работать здесь, так как вы можете иметь подстроки около половины длины полной последовательности в решении. Похоже, тебе нужно использовать грубую силу. Для устранения связанной проблемы ознакомьтесь с алгоритмом Lempel-Ziv-Welch . Это эффективный алгоритм, который находит минимальное кодирование с помощью подстрок.
Очень распространенным способом кодирования сжатых данных RLE является обозначение специального байта как "DLE" (извините, я не помню, что означает этот термин), что означает "следующим идет счет, за которым следует байт".
Таким образом, кодировать нужно только повторяющиеся последовательности. Обычно символ DLE выбирается так, чтобы минимизировать вероятность его естественного появления в несжатых данных.
Для вашего исходного примера, давайте установим полную остановку (или точку) в качестве DLE, это закодирует ваш пример следующим образом:
AAABBAAABBCECE => 3A2B3A2B1C1E1C1E <-- your encoding
AAABBAAABBCECE => .3ABB.3ABBCECE <-- my encoding
Вы будете кодировать последовательность только в том случае, если она действительно экономит место. Если ограничить длину последовательностей 255, чтобы счет умещался в байте, то последовательность займет 3 байта: DLE, счет и байт для повтора. Вероятно, вы также не будете кодировать 3-байтовые последовательности, потому что их декодирование несет немного больше накладных расходов, чем некодированная последовательность.
В вашем тривиальном примере экономия несущественна, но если вы попробуете сжать битовую карту, содержащую снимок экрана преимущественно белой программы, например, блокнота или браузера, то увидите реальную экономию места.
Если вы встретите символ DLE в естественном виде, просто выдайте счетчик 0, поскольку мы знаем, что никогда не будем кодировать последовательность длиной 0, DLE, за которым следует 0-байт, означает, что вы декодируете его как один байт DLE.