面试中有一个关于压缩字符串的常见问题。我不是在寻找代码，我只需要一个解决问题的有效算法。
给定一个字符串（例如 aaabbccaaadd），压缩它（3a2b2c3a2d）。
我的解决方案：
在弦上旅行。每次我看到同一个字母时，我都会数数。当我看到不同的字母出现时（并重新开始），我将输出字母和计数器。
有没有更有效的方法来做到这一点？
谢谢
问问题
1967 次
3 回答
6
这称为运行长度编码，您命名的算法基本上是您将获得的最佳算法。它需要 O(1) 辅助存储（保存看到的最后一个符号，或等效地检查即将出现的元素；还保存一个计数器，记录您看到的相同符号的数量）并在 O(n) 时间内运行。由于您需要至少检查每个符号一次才能知道结果，因此无论如何您都不会比 O(n) 时间更好。更重要的是，它还可以一次处理一个符号的流，一次输出一个符号，因此您实际上只需要 O(1) RAM。
您可以使用许多技巧来更好地获得常数因子，但算法基本保持不变。这些技巧包括：
- 如果您流到慢速目的地（如磁盘或网络），请缓冲。广泛地。
- 如果您希望长时间运行相同的符号，您可以对循环计数它们进行矢量化，或者至少通过移出其他情况来使循环更紧密。
- 如果适用，请告诉您的编译器不要担心输入和输出指针之间的别名。
如果您的数据源很慢，那么这种微优化可能没有实际意义。对于我上面提到的一些优化水平，即使是 RAM 也可以算慢。
于 2012-10-26T19:57:17.597 回答
1
如果您的字符串足够长，请使用 Lempel Ziv 压缩。优点是：它不仅可以缩短不同的重复，而且可以有效地缩短重复的“组”。参见维基百科：Lempel-Ziv-Welch
一个模糊的例子 - 让你明白：
aaabqxyzaaatuoiaaabhaaabi 将被压缩为：
Abqxyz Atui Bh Bi
where [ A= aaa] & [ B= Ab = aaab]
于 2012-10-26T20:00:16.723 回答
0
许多压缩算法都基于霍夫曼编码。这就是我在采访中给出的答案
于 2012-10-26T19:51:27.253 回答