在有限字符允許的情況下壓縮java中的字符串

我的一個朋友得到了這個interview question。另外，他被告知他可以假設人物是字母a到z（大寫或小寫）。我寫了以下內容，但我無法弄清楚如何使用關於字符串包含的有限字符（a到z）的假設。我是否在沒有意識到的情況下使用這種假設，還是可以利用它？在有限字符允許的情況下壓縮java中的字符串

public static String compress(String str){ 
    int count = 1; 
    char c = str.charAt(0); 
    StringBuffer result = new StringBuffer(); 

    for (int i = 1; i < str.length();i++){ 
     if (str.charAt(i) == c){ 
     count++; 
     } 
     else{ 
     String to_add = c + String.valueOf(count); 
     result.append(to_add); 
     count = 1; 
     c = str.charAt(i); 
     } 
    } 
    // last character 
    String to_add = c + String.valueOf(count); 
    result.append(to_add); 

    String result_str = result.toString(); 

    // Check whether the compressed string is 
    // actually smaller than the original one 
    if (result_str.length() < str.length()){ 
     return result_str; 
    } 
    else{ 
     return str; 
    } 
    }

來源

2014-12-28 giulio

由於知道有限字符a-z（26），因此可以使用26個字節對32個字符進行編碼，而無需使用更高級的壓縮算法。 – mac

什麼應該混合的情況下輸出 - 說AAAaaaBBBcc == 5A3B2C？ – user1428716

@ user1428716它應該是A3a3B3c2 – giulio

將每個字符分配給一個數字，例如a = 1，z = 26。因此，要表示這26個字符，您至少需要5位。

您現在可以使用2個字節（16位）來存儲三個字符。這需要比每個字符的最初一個字節少三分之一的字節（如果是ascii）。要存儲三字符字符，請從您的字節中讀取位（例如，從左到右）。

的第一字節的前5個比特將代表第一個字符
第一字節的接下來的三個比特，第二個字節的前兩個位串接表示第二
下一五個位從第二個字節表示第三個字符
有一個位左（忽略）

*要略微提高壓縮尺寸，如果您的字符串的長度％3 = 1，則對最後一個字符你的字符串只能使用一個字節，因爲你沒有另一個三元組。

**如果特定位設置使用的算法從this後一個字節，這是你可以得到：

public byte getBit(byte b, int position) 
{ 
    return (b >> position) & 1; 
}

***您可以使用從算法位設置爲一個字節this後，它們是：

設置一個位（其設置爲1）

b = b | (1 << position);

要取消一個位（它設置爲零）：

b = b & ~(1 << position);

****使用數學（5和8的最小公倍數），如果使用5個字節= 40位，可以表示8個字符（8x5 = 40），則甚至可以稍微提高壓縮大小。

然後您將存儲字符的八位字節，並且現在沒有位可以忽略。對於字符串的最後一個字符，根據（字符串大小％8），您可以再次使用較少的字節。

*****使用最後一個5字節的方法可以減少3/8的尺寸，這比3字節方法的1/3要好。

來源

2014-12-28 12:22:39

'a' 到 'Z' 是2*26=52明顯不同的字符，並將其在6位（2^6=64）配合。您可以將代碼點打包成六分音符。

OTOH，RLE（你已經編碼）只適用於重複。如果你有像abcde那樣的輸入，它會變成1a1b1c1d1e或類似的東西，這是非常低效的，你很難稱之爲壓縮。

來源

2014-12-28 11:24:02 milan

在有限字符允許的情況下壓縮java中的字符串

回答

相關問題