logo标签列表

寻找最小长度的RLE

algorithmdynamic-programmingrun-length-encoding
7
经典的 RLE 算法通过使用数字来表示在文本中该位置后面的字符出现的次数，从而压缩数据。例如：
AAABBAAABBCECE => 3A2B3A2B1C1E1C1E
然而，在上述示例中，该方法导致压缩文本使用更多的空间。更好的想法是使用数字来表示在给定文本中该数字后面的子字符串出现的次数。例如：
AAABBAAABBCECE => 2AAABB2CE（“AAABB”两次，然后“CE”两次）。
现在，我的问题是：如何实现一个有效的算法，使用这种方法找出最优 RLE 中的最小字符数？暴力方法存在，但我需要更快的方法（最多O(length^2)）。也许我们可以使用动态规划？
1981年，Rodeh、Pratt和Even提出了一种通过字符串匹配实现数据压缩的线性时间算法（使用相对于“指针”仅一个方向，利用引用来代表重复的字符串，并将其嵌入到纯文本中）。 - greybeard
4个回答
7

通过动态规划，可以在二次时间内完成，这里是一些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很大，我们可能需要使用额外的字节来保存C+1。如果你使用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!
你能详细说明一下如何索引输入字符串S和其他变量吗？当你说“到x”时，你是包括x还是只有x-1？ 此外，这个：如果S[n-k:n] == S[n-2*k:n-k] 对我来说看起来不太对。当n = 2且k = 1时，你测试S[1:2]与S[0:1]。难道你不应该测试没有字符重叠的情况吗？按照你的说法，我在实现这个算法时得到了一些错误的答案，例如在我发布的字符串上，我得到了长度为14，这是错误的。即使我加/减1以避免比较重叠的字符，我也得到了10。 - IVlad
1
  1. 这是一个立方体！呃！我想我可以摆脱它，但我不确定。
  2. 这是我提到的小问题。你可以像我说的那样扩展表格来处理它。你想如何编码这些数字？（十进制表示法似乎是一个奇怪的选择）
 - forefinger
谢谢，太好了 :). 无论如何，我通过使用log10函数来修复2号问题，以查看新步骤是否添加了额外的数字。不知道这是否是最好的方法，但它可以工作，并且不使用任何额外的内存，速度仍然相当快。你认为有没有办法只使用O（N）或至少少于O（N ^ 2）的内存？那将真的很棒 :P。 - IVlad
@Moron：尝试运行新代码。希望这至少能让算法变得可理解，即使不是确切的Python代码。 - forefinger
我知道这通常是不好的做法，但由于我看到其他人也非常感兴趣这个问题，我将我的电子邮件公开，以便有人有兴趣分享想法而不会污染解决方案线程：ivdorelian@yahoo.com - 如果您使用即时通讯，请给我发送一封电子邮件，并告诉我您的ID，如果您不介意的话。 - IVlad
显示剩余21条评论
1

我不认为动态规划在这里会起作用，因为你可能需要在解决方案中使用长度约为一半的子字符串。看起来你需要使用暴力破解。 对于相关问题，请查看Lempel-Ziv-Welch Algorithm。它是一种有效的算法，通过使用子字符串来找到最小编码。

你确定吗？最坏情况下，长度将为原始长度加一（“1”+给定字符串）。我不明白为什么这意味着动态编程行不通。我认为问题仍然表现出最优子结构：如果我们可以找到字符串的一部分的答案，我们可以在更大的部分的答案中使用它。我只是不确定如何做到这一点。 - IVlad
通过将每个字符替换为长度为一的链接，形成实际上是直线链接的图形。现在，在每个可以进行运行长度编码的点上，创建一个额外的链接，绕过运行长度编码扩展到的字符，并且其长度是编码所需的字符数。通过这个图形的最短路径是最短编码 - 但我没有看到快速找到哪些子字符串可以被运行长度编码的方法 - 到目前为止也没有其他人看到。 - mcdowella
肯定可以做到高效 - 我的意思是O(L^2)或O(L^2 log L)，或者绝对是O(L^3)以下，因为我第一次在一个编程比赛中看到这个问题时，长度L大约为5000，时间限制为几百毫秒。我认为使用图表是过度的，最终会比测试每个字符的某个长度的重复子字符串的数量（尝试所有长度）更慢，主要是因为仍然需要构建图表... - IVlad
1

一种常见的RLE压缩数据的编码方式是指定一个特殊字节作为“DLE”（抱歉，我不记得这个术语代表什么），它意味着“接下来是一个计数，后面跟着一个字节”。

通过这种方式，只需要对重复的序列进行编码。通常选择DLE符号时会尽量减小其在未压缩数据中出现的可能性。

对于你的原始示例，让我们将句号（或点）设为DLE，这样可以将你的示例编码如下：

AAABBAAABBCECE => 3A2B3A2B1C1E1C1E <-- your encoding
AAABBAAABBCECE => .3ABB.3ABBCECE   <-- my encoding

只有在编码后能够节省空间时，才会对序列进行编码。如果将序列长度限制为255，则计数适合一个字节，因此序列需要3个字节：DLE、计数和要重复的字节。您可能也不会对3字节的序列进行编码，因为解码这些序列比非编码序列多一些开销。

在您的简单示例中，没有节省空间，但是如果您尝试压缩包含大量白色区域的位图，例如记事本或浏览器的屏幕截图，则可以实现真正的空间节省。

如果您自然地遇到DLE字符，请发出0的计数，因为我们知道我们永远不会对长度为0的序列进行编码，DLE后跟0字节意味着您将其解码为单个DLE字节。

但是您仍然使用的字符比最佳情况下多。您的编码使用了14个字符，而我的第二个编码只使用了9个字符。连续重复子字符串的编码通常是最好的方法。我对一种算法感兴趣，它可以通过执行我在原始帖子中描述的操作来获得最少数量的字符。 - IVlad
数据链路转义 - “接下来的八位字节是原始数据”（这个答案似乎使用“下一个字节指示长度”的方式） - greybeard
0
我真的不明白BWT如何帮助我，甚至它与RLE有什么关系... 聪明的子字符串匹配方法可以等待。我该如何在解决我发布的问题时使用子字符串匹配？ - IVlad
BWT是一种“部分排序”算法 - 输出将具有比输入更多的字符运行，因此可以更好地进行RLE压缩。 - Nick Johnson
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接