python - 任意长度子串的运行长度编码

Question

什么是高效的(就时间复杂度而言)run length encoding任意但有限长度的输入流的算法。长度为 1 的子串的算法可以在 C 中实现为:

void encoding(char *bytes)
{
    int c = 0; 
    char *s = bytes, ch;

    while(*s) {
       c=1;
       ch=*s;

       while(*s && *s== *(s+1)) {
          c++;
          s++;
       }
       printf("%d%c", c, ch);
       s++;
    }
}

但是，我正在寻找一种可以对任意长度的子字符串进行编码的更好算法。例如，对于输入 "abbabb"，上面的代码将打印:"1a2b1a2b"。但更好的算法可以将其编码为 "2abb"。

实现语言(C/Python 是我的选择)不是问题，因为我正在寻找一种算法。

Answer 1

任何可以找到一定长度重复子串的算法都可以用来实现具有该长度滑动窗口的 Lempel-Ziv 压缩。

所以我会研究 Lempel-Ziv 编码器并使用它。或者甚至更好:放弃运行长度编码并实现 Lempel-Ziv - 它只能提供更好的压缩。