问题标签 [run-length-encoding]

我编写了一个程序，它打开一个 bmp 文件并将其视为字符文件并对其执行运行长度编码。它生成一个有效的压缩编码文件，我再次读取该文件以执行解码。

当我制作应用程序时，我使用的是 Fedora，它运行得非常好。现在我在 ubuntu 上运行它，它拒绝工作。

知道有什么问题吗？我担心它与编码有关。

我编写了一个程序来执行运行长度编码。在典型情况下，如果文本是

运行长度编码将使它

但它为每个非重复字符添加了额外的 1。由于我正在使用它压缩 BMP 文件，因此我想放置一个标记“$”来表示重复字符的出现（假设图像文件具有大量重复文本）。

所以它看起来像

对于当前示例，它的长度是相同的，但 BMP 文件存在显着差异。现在我的问题在于解码。碰巧一些 BMP 文件具有模式，$<char><num>即$I9在原始文件中，所以在压缩文件中也包含相同的文本。$I9，但是在解码后它会将其视为重复的 I 重复 9 次！所以它会产生错误的输出。我想知道的是我可以使用哪个符号来标记重复字符（运行）的开始，这样它就不会与原始来源冲突。

我需要一个针对受限资源环境（如二进制（十六进制数据）上的嵌入式系统）优化的 FAST 解压缩例程，具有以下特征：

1. 数据面向 8 位（字节）（数据总线为 8 位宽）。
2. 字节值的范围不是从 0 到 0xFF，而是在每个 DataSet 中具有泊松分布（钟形曲线）。
3. 数据集是高级固定的（要刻录到 Flash 中），每组很少 > 1 - 2MB

压缩可能需要尽可能多的时间，但在最坏的情况下，一个字节的解压缩应该需要 23uS，并且内存占用最少，因为它将在嵌入式系统（3Mhz - 12Mhz 内核，2k 字节 RAM）等受限资源环境中完成.

什么是好的减压程序？

基本的运行长度编码似乎太浪费了——我可以立即看到，在压缩数据中添加一个标头集以使用未使用的字节值来表示经常重复的模式会带来惊人的性能！

对于只投入了几分钟的我来说，肯定已经存在来自喜欢这些东西的人的更好的算法吗？

我想有一些“准备就绪”的示例在 PC 上试用，以便我可以比较基本 RLE 的性能。

假设我有一个一维数组：

是否有一个内置的 Matlab 函数，它接受一个数组和一个整数n并将数组的每个元素复制 n 次？

例如调用replicate(a, 3)应该返回[1,1,1,2,2,2,3,3,3]。

请注意，这与repmat. 我当然可以replicate通过repmat对每个元素执行并连接结果来实现，但我想知道是否有一个更有效的内置函数。

我正在尝试使用“值”数组和“计数器”数组将多个值插入到数组中。例如，如果：

我想要一些函数的输出

成为

其中 a(1) 重复 b(1) 次，a(2) 重复 b(2) 次，等等...

MATLAB中有没有内置函数可以做到这一点？如果可能，我想避免使用 for 循环。我尝试了 'repmat()' 和 'kron()' 的变体，但无济于事。

这基本上是Run-length encoding。

我已经在这个问题上敲了很长时间

我在做成像。到目前为止，我已经对图像进行了二值化，这意味着从灰度图像中，某个值以下的每个像素都会被丢弃。这给了我原始图像中的一些区域，这些区域周围有很多“零像素”。

接下来，我将运行长度编码为“blob”。运行是一种数据压缩方法。例如，假设您已经对一个正方形进行了二值化，那么您将只有几次运行来描述整个图像。游程由 x,y 坐标和长度定义。

重新创建图像时，对于每次运行，转到 x,y 坐标并在 x 轴上添加像素作为运行长度。

现在我必须运行并从中创建一条链来描述该区域的轮廓。我不知道该怎么做。

我有一堆 x,y,length 运行，我必须在边缘“导航”以形成一个chain。通常在成像中，这个过程是用原始图像完成的，但我不能再在这里使用原始图像，所以我必须用运行来计算它。

我知道这看起来像一堵大墙，但我不知道如何更好地提出这个问题。

任何关于相同实现的提示或指针都会很棒。

编辑

感谢 unwind，我会链接一些图片：

_{（来源：tudelft.nl）}

在这个例子中，他们将图像 B 处理成轮廓 C（我称之为链）。但是我想从 D 生成轮廓，运行长度

经典的 RLE 算法通过使用数字来表示数字后面的字符在该位置出现在文本中的次数来压缩数据。例如：

AAABBAAABBCECE => 3A2B3A2B1C1E1C1E

但是，在上面的示例中，该方法会导致压缩文本使用更多空间。一个更好的主意是使用数字来表示数字后面的子字符串在给定文本中出现的次数。例如：

AAABBAAABBCECE => 2AAABB2CE（“AAABB”两次，然后“CE”两次）。

现在，我的问题是：如何实现一个有效的算法，使用这种方法找出最佳 RLE 中的最小字符数？存在蛮力方法，但我需要更快的方法（最多O(length ² )）。也许我们可以使用动态规划？

我的问题与这个问题类似，但我想根据在第二个相同大小的数组中指定的计数来复制每个元素。

举个例子，假设我有一个数组v = [3 1 9 4]，我想用它rep = [2 3 1 5]来复制第一个元素 2 次，第二个元素 3 次，依此类推得到[3 3 1 1 1 9 4 4 4 4 4].

到目前为止，我正在使用一个简单的循环来完成工作。这是我开始的：

我设法通过预先分配空间来改进：

但是我仍然觉得必须有一个更聪明的方法来做到这一点......谢谢

我有一个长字符串，例如它可能是“aaaaaabbccc”。需要将其表示为“a6b2c3”。最好的方法是什么？我可以在线性时间内通过比较字符和递增计数，然后替换数组中的计数，一次使用两个索引来做到这一点。你们能想出比这更好的方法吗？任何编码技术都可以在这里工作吗？

考虑“字符串”（将其视为数字数组）

RLE（“groupby”）是：

然后，我们用前面元素的运行长度之和来丰富上述 RLE。

因此，上述内容的丰富版本变为：

“字符串”拆分为 1：

RLE 拆分为 1

“字符串”拆分为 8：

RLE 拆分为 8

注意：在我的示例中，我引用了“Z 上的 RLE 拆分”列表，但没有丰富它们。事实并非如此。我把它们排除在外以减少混乱。例如，“RLE split on 1”实际上应该被视为：

如何在 Z 上实现这种“RLE 拆分”（= 1, 8; 在这种情况下）

可以省略空数组（在 split 之后）。

也许是一个聪明的列表组合。？（使用嵌套了追加的 for 循环似乎更容易解决）