我在查看最近的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,並認爲複雜,當涉及到這種事情,這是我的一個謬論,並表明有多大的想法可以得到方式,我可以深深地吸進去,並沒有看到正確的角度而被帶走!再次感謝! :)
最好的問候, 湯姆。
如何解決我自己的問題,因爲給出的答案是足夠的? – t0mm13b 2010-02-12 13:26:12
與bzip2算法一樣,初步的BWT + MTF可能有助於更多數據集上的RLE。 – ephemient 2010-02-28 06:59:27