RLE算法是否有缺陷？

我在查看最近的Code Golf刪除字符串中的重複字符。所以尋思過來，認爲RLE算法將解決這個問題，其實，我也相信這將解決刪除重複，我用C寫在這裏實現，要看看我能走多遠吧RLE算法是否有缺陷？

 
char *rle(const char *src){ 
    char *p=(char *)src; 
    char *q=(char *)src+1; 
    char *rle_enc=NULL, *tmp_rle, buf[10]; 
    int run=1; 
    while (*p){ 
     while(*q){ 
      if (*p==*q++) run++,p++; 
     } 
     sprintf(buf,"%d%c",run,*(p-1)); 
     p++; 
     if (!rle_enc){ 
      if ((rle_enc=malloc(strlen(buf)+1))!=NULL){ 
       strcpy(rle_enc,buf); 
      } 
     }else{ 
      if ((tmp_rle=realloc(rle_enc,(strlen(rle_enc)+strlen(buf)+1)))!=NULL){ 
       rle_enc=tmp_rle; 
       strcat(rle_enc,buf); 
      } 
     } 
     q=(p+1); 
     run=1; 
    } 
    return rle_enc; 
}

去果然，這裏的主要爲這樣的：

 
int main(int argc, char **argv){ 
    char *test1 = "HHHHHHeeeeeelllllloooooooo"; 
    char *test2 = "nbHHkRvrXbvkn"; 
    char *p = rle(test1); 
    printf("s = %s\n", test1); 
    printf("p = %s\n", p); 
    if (p) free(p); 
    return 0; 
}

據Code Golf上元，應該是可重複使用的，並解決一系列的問題，但是在最短的字符集，夠公平我想我只是改變變量爲1個字母和緊湊的代碼，使它很小..但有些東西不完全正確，因爲這導致我想到RLE算法thm本身，這裏是關於它的說明以及在Java中的實現的一個頁面Wikipedia。

的代碼確實出現了做什麼應該，所以我想，現在，它只是一個通過編碼字符串結果會從rle尋找那些有1後跟字母事..

但是我注意到RLE算法的侷限性，它只適用於那些有一組相鄰的重複字符的算法。但是Code Golf的測試案例不合格，看起來很簡單，這讓我想到了這個問題：

RLE算法是否有缺陷？現在在哪裏使用？塵封我相信，由於數據和流動圍繞RLE不再適合爲目的的信息的音量...

編輯：由於月影，約翰和史蒂夫張貼自己的答案。

有一個基本的教訓，我仍然沒有學到 - 從來沒有去OTT，並認爲複雜，當涉及到這種事情，這是我的一個謬論，並表明有多大的想法可以得到方式，我可以深深地吸進去，並沒有看到正確的角度而被帶走！再次感謝！ :)

最好的問候，湯姆。

來源

2010-02-12 t0mm13b

如何解決我自己的問題，因爲給出的答案是足夠的？ – t0mm13b 2010-02-12 13:26:12

與bzip2算法一樣，初步的BWT + MTF可能有助於更多數據集上的RLE。 – ephemient 2010-02-28 06:59:27

RLE不會爲您解決該代碼高爾夫問題。

代碼高爾夫問題要求您去除在輸入中出現多次的所有字符，而不管出現的位置在哪裏。然而，RLE「遊程長度編碼」編碼「遊程」 - 重複相同字符的序列;相同字符的多次運行可以出現在一個字符串中，並且RLE將按照設計單獨編碼這些字符。

RLE旨在通過用一個元素替換序列，然後重複其次數來更緊湊地編碼重複數據元素的序列。爲此目的它是完全足夠的。任何「缺陷」不在算法中，而是在決定將它用於不適合的目的。

來源

2010-02-12 13:11:44 moonshadow

@Moonshadow：謝謝！我在昨天敲我的頭之後才意識到這一點，我的想法不適合這個目的！ :)你得到一個被接受的答案，它表明要小心不要去OTT，並認爲複雜... – t0mm13b 2010-02-12 13:19:32

RLE通常用於8位位圖，因爲它們通常會長時間運行相同的字符。 Windows仍支持以類似方式使用的RLE視頻編解碼器。目前，LZW + Huffman編碼已經取代了RLE作爲「簡單」壓縮算法。

RLE已經使用了多年，所以我們很難說它是「有缺陷的」，但它肯定效率不高。

大多數RLE格式將有一個「轉義字符」，這樣就不會對輸出產生混淆。

例如，如果我們使用「E」作爲轉義字符...

這將產生一個litteral 「E」：

ee

這將是字母「a」重複兩次：

ea2

來源

2010-02-12 13:08:32

@約翰：謝謝，但它仍然不回答我的問題，它有瑕疵... – t0mm13b 2010-02-12 13:09:35

@ tommieb75：你的意思是什麼有缺陷？它做它應該做的事情。用相同值的連續塊壓縮數據是可用的，例如，具有大的恆定顏色區域的低彩色圖像。但是，它不能產生足夠的信息（關於重複但不相鄰的字符）來解決這個高爾夫問題。 – Anssi 2010-02-12 13:27:41

你爲什麼認爲它有缺陷？ RLE用於壓縮重複的字符。它不打算做任何事情，並不會幫助壓縮數據沒有運行長度> 1。

在這個問題的上下文中，我會說，RLE只是不正確的答案，它沒有缺陷，它在這種情況下沒有幫助。

來源

2010-02-12 13:13:37

@Steve：謝謝！看到我的評論下面的月影！ :) – t0mm13b 2010-02-12 13:20:48

RLE算法是否有缺陷？

回答

相關問題