-1

我尝试提出一种压缩算法。我对压缩理论做了一点，所以我知道我想出的这个方案很可能根本无法实现压缩。

目前它仅适用于没有连续重复字母/数字/符号的字符串。一旦正确建立，我希望将其推断为二进制数据等。但首先是算法：

假设只有 4 个字母：a,b,c,d；我们创建一个与字母对应的矩阵/数组。每当遇到一个字母时，相应的索引就会增加，以便遇到的最后一个字母的索引始终是最大的。如果索引最初为零，我们将索引增加 2。如果它最初不是零，那么我们将它增加 2+（矩阵中的第二大元素）。一个例子来澄清：

Array = [a,b,c,d]
Initial state = [0,0,0,0]
Letter = a
New state = [2,0,0,0]
Letter = b
New state = [2,4,0,0]
.
.c
.d
.
New state = [2,4,6,8]
Letter = a
New state = [12,4,6,8] 
//Explanation for the above state: 12 because Largest - Second Largest - 2 = Old value
Letter = d
New state = [12,4,6,22]
and so on...

解压就是这个逻辑的逆向。

压缩的基本实现（在python中）：

（这个函数非常初级，所以不是最好的代码......我知道。一旦我得到正确的核心算法，我就可以优化它。）

def compress(text):
    matrix = [0]*95     #we are concerned with 95 printable chars for now
    for i in text:
        temp = copy.deepcopy(matrix) 
        temp.sort()
        largest = temp[-1]
        if matrix[ord(i)-32] == 0:
            matrix[ord(i)-32] = largest+2
        else:
            matrix[ord(i)-32] = largest+matrix[ord(i)-32]+2
    return matrix

然后将返回的矩阵用于解压缩。现在是棘手的部分：

我根本不能真正调用这种压缩，因为从函数生成的矩阵中的每个数字对于长度为 50000 的字符串的数量级为 10**200。因此存储矩阵实际上比存储原始字符串占用更多空间。我知道……完全没用。但在做这一切之前，我曾希望我可以使用矩阵的数学属性以某种数学简写形式有效地表示它。我尝试了很多可能性，但都失败了。我尝试过的一些事情：

  1. 矩阵的秩。失败，因为不是唯一的。

  2. 表示使用 mod 函数。失败，因为商或余数

  3. 使用 pickle 将每个整数存储为生成器。

  4. 将矩阵存储为位图文件，但整数太大而无法存储为颜色代码。

让我再次迭代该算法可以优化。例如，我们可以添加 1 并继续，而不是添加 2。但不要真正导致任何压缩。代码也一样。稍后进行次要优化...首先我想改进主要算法。

更何况，像我这样一个平庸闲散的头脑的产物，很有可能永远也达不到压缩的效果。在这种情况下，我希望得到您的帮助和想法，了解这可能有用的地方。

TL;DR：检查描述压缩算法的编码部分。压缩结果比原始字符串长。这可以解决吗？如果是，如何？

PS：我的电脑上有完整的代码。将在 github 上创建一个 repo 并在一段时间内上传。

4

1 回答 1

3

压缩本质上是一个预测过程。在输入中寻找模式并使用它们比不太可能更有效地编码更有可能的下一个字符。我在你的算法中看不到任何试图建立预测模型的东西。

于 2012-11-06T12:21:27.797 回答