压缩字符串

有关压缩字符串的采访中有一个常见问题。我不在寻找代码，我只需要一个高效的算法来解决问题。压缩字符串

如果给定字符串（例如aaabbccaaadd），压缩它（3a2b2c3a2d）。

我的解决办法：在字符串

旅游。每当我看到同一封信时，我都会记下它。当我看到一封不同的信件来了（并重新开始）时，我将输出字母和计数器。

有没有更有效的方法来做到这一点？

感谢

来源

2012-10-26 Maroun

霍夫曼编码？ – Wug

@Wug - Huffman编码不会给出问题中指定的结果。 –

你是要求一个好的压缩算法，还是要求算法产生一个特定的压缩（运行长度编码，这就是你的示例输出）？ – delnan

这就是所谓的运行长度编码，并且您命名的算法基本上是最好的。它需要O（1）辅助存储器（保存最后看到的符号，或等同检查即将到来的元素;还可以保存一个计数器，看看你看过多少个相同的符号）并在O（n）时间内运行。由于您至少需要检查一次符号以了解结果，因此无论如何您都不会比O（n）更好。更重要的是，它也可以一次处理一个符号流，并且一次输出一个符号，所以实际上只需要O（1）RAM。

你可以拉一些技巧来获得更好的常数因子，但算法基本保持不变。这些技巧包括：

如果您流缓存到缓存目标（如磁盘或网络），缓冲区。广泛开展。
如果您期望长时间运行相同的符号，您可能可以对向其计数的循环进行向量化，或者至少通过移出其他情况来使该循环更紧密。
如果适用，请告诉编译器不要担心输入和输出指针之间的混叠。

如果您的数据源很慢，此类微观优化可能没有意义。对于我上面的一些要点的优化级别，即使RAM可以计算为慢。

来源

2012-10-26 19:57:17 delnan

许多压缩算法都基于Huffman Coding。这就是我在采访中给出的答案

来源

2012-10-26 19:51:27 Landon

他们是？当今广泛传播的档案中使用的算法似乎是显着不同的野兽。 – delnan

如果你在采访中告诉我，我仍然会看着你困惑。再次，AFAIK所有使用最广泛的压缩算法都与它无关，虽然有几个哈夫曼编码变种，它是学习的一个很好的例子（它非常有启发性，我喜欢解剖它），它基本上只是一个小家庭在一个巨大的压缩算法树中。 – delnan

如果您的字符串足够长，请使用Lempel Ziv压缩。优点是：它不仅可以缩短明显的重复次数，而且可以有效地重复“重复”组。见wikipedia: Lempel-Ziv-Welch

一个模糊的例子 - 让你的想法：
aaabqxyzaaatuoiaaabhaaabi将被压缩为：
A bqxyz A TUI B^h B我
其中[A = AAA] & [B = A B = aaab]

来源

2012-10-26 20:00:16

回答

相关问题