壓縮字符串

有關壓縮字符串的採訪中有一個常見問題。我不在尋找代碼，我只需要一個高效的算法來解決問題。壓縮字符串

如果給定字符串（例如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

回答

相關問題