Java 中的遊程編碼和解碼
1. 概述
在計算機科學中，資料壓縮技術在優化儲存和傳輸效率方面發揮重要作用。一種經受住時間考驗的技巧是遊程編碼（RLE）。
在本教程中，我們將了解 RLE 並探索如何在 Java 中實作編碼和解碼。
2. 理解遊程編碼
遊程編碼是一種簡單而有效的無損資料壓縮形式。 RLE 背後的基本思想是透過單一值及其計數來表示連續的相同元素，稱為資料流中的“運行”，而不是作為原始運行。
這在處理重複序列時特別有用，因為它顯著減少了儲存或傳輸資料所需的空間量。
RLE 非常適合壓縮基於調色板的點陣圖影像，例如電腦圖示和動畫。一個著名的例子是 Microsoft Windows 3.x 啟動畫面，它是 RLE 壓縮的。
讓我們考慮以下範例：
String INPUT = "WWWWWWWWWWWWBAAACCDEEEEE";如果我們對上面的字串應用遊程編碼資料壓縮演算法，它可以呈現如下：
String RLE = "12W1B3A2C1D5E";在編碼序列中，每個字元遵循其連續出現的次數。這個規則使我們能夠在解碼過程中輕鬆地重建原始資料。
值得注意的是，標準 RLE 僅適用於「文字」輸入。如果輸入包含數字，RLE 無法以明確的方式對它們進行編碼。
在本教程中，我們將探索兩種遊程編碼和解碼方法。
3. 基於字元數組的解決方案
現在我們了解了 RLE 及其工作原理，實現遊程編碼和解碼的經典方法是將輸入字串轉換為char數組，然後將編碼和解碼規則應用於該數組。
3.1.建立編碼方法
實現遊程編碼的關鍵是識別每個遊程並計算其長度。我們首先看一下實現，然後再了解它是如何運作的：
String runLengthEncode(String input) {
StringBuilder result = new StringBuilder();
int count = 1;
char[] chars = input.toCharArray();
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (i + 1 < chars.length && c == chars[i + 1]) {
count++;
} else {
result.append(count).append(c);
count = 1;
}
}
return result.toString();
}接下來，讓我們快速瀏覽一下上面的程式碼並理解其中的邏輯。
首先，我們使用StringBuilder來儲存每個步驟的結果並將它們連接起來以獲得更好的效能。
初始化計數器並將輸入字串轉換為char陣列後，該函數將迭代輸入字串中的每個字元。
對於每個字元：
- 如果當前字元與下一個字元相同且不在字串的末尾，則計數會增加。
- 如果目前字元與下一個字元不同或位於字串末尾，則計數和目前字元將附加到結果
StringBuilder中。然後，對於下一個唯一字符，計數將重置為1。
最後，使用toString()將StringBuilder轉換為字串，並作為編碼過程的結果傳回。
當我們使用這種編碼方法測試INPUT時，我們得到了預期的結果：
assertEquals(RLE, runLengthEncode(INPUT));3.2.創建解碼方法
識別每次運行對於解碼 RLE 字串仍然至關重要。一個序列包括字元及其出現的次數，例如“ 12W ”或“ 2C ”。
現在，讓我們建立一個解碼方法：
String runLengthDecode(String rle) {
StringBuilder result = new StringBuilder();
char[] chars = rle.toCharArray();
int count = 0;
for (char c : chars) {
if (Character.isDigit(c)) {
count = 10 * count + Character.getNumericValue(c);
} else {
result.append(String.join("", Collections.nCopies(count, String.valueOf(c))));
count = 0;
}
}
return result.toString();
}接下來，讓我們分解程式碼並逐步了解其工作原理。
首先，我們建立一個StringBuilder物件來保存步驟結果，並將rle字串轉換為 char 陣列以供後續處理。
此外，我們也初始化了一個整數變數count來追蹤連續出現的次數。
然後，我們迭代 RLE 編碼字串中的每個字元。對於每個字元：
- 如果字元是數字，則它有助於計數。透過使用公式
10 * count + Character.getNumericValue(c)將數字附加到現有計數來更新計數。這樣做是為了處理多位數計數。 - 如果該字元不是數字，則遇到新字元。然後使用
Collections.nCopies()將目前字元追加到StringBuilder重複計數次數的結果中。然後，對於下一組連續發生的情況，計數將重設為0。
值得注意的是，如果我們使用 Java 11 或更高版本， String.valueOf(c).repeat(count)是重複字元c count次的更好替代方案。
當我們使用範例驗證解碼方法時，測試通過：
assertEquals(INPUT, runLengthDecode(RLE));4. 基於正規表示式的解決方案
正規表示式是處理字元和字串的強大工具。讓我們看看是否可以使用正規表示式執行遊程編碼和解碼。
4.1.建立編碼方法
我們先來看看輸入字串。如果我們可以將其拆分成一個“run數組”，那麼問題就很容易解決了：
Input : "WWWWWWWWWWWWBAAACCDEEEEE"
Run Array : ["WWWWWWWWWWWW", "B", "AAA", "CC", "D", "EEEEE"]我們無法透過字元分割輸入字串來實現此目的。相反，我們必須以零寬度位置進行分割，例如「 W 」和「 B 」、「 B 」和「 A 」之間的位置等。
不難發現這些位置的規律：位置前後的字元是不同的。因此，我們可以使用環視和反向引用來建立一個正規表示式來匹配所需的位置：" (?<=(\\D))(?!\\1) 」。讓我們快速理解這個正規表示式的意思：
-
(?<=(\\D))– 正向後向斷言可確保符合位於非數字字元之後（\\D表示非數字字元）。 -
(?!\\1)– 負lookahead斷言確保匹配位置不在正lookbehind中相同的字元之前。\\1指的是先前符合的非數字字元。
這些斷言的組合確保分割發生在同一字元的連續運行之間的邊界處。
接下來，讓我們建立編碼方法：
String runLengthEncodeByRegEx(String input) {
String[] arr = input.split("(?<=(\\D))(?!\\1)");
StringBuilder result = new StringBuilder();
for (String run : arr) {
result.append(run.length()).append(run.charAt(0));
}
return result.toString();
}正如我們所看到的，在獲得 run 數組後，剩下的任務只是將每個 run 的長度和字元附加到準備好的StringBuilder.
runLengthEncodeByRegEx()方法通過了我們的測試：
assertEquals(RLE, runLengthEncodeByRegEx(INPUT));4.2.創建解碼方法
我們可以遵循類似的想法來解碼 RLE 編碼的字串。首先，我們需要分割編碼後的字串並獲得以下數組：
RLE String: "12W1B3A2C1D5E"
Array : ["12", "W", "1", "B", "3", "A", "2", "C", "1", "D", "5", "E"]一旦我們得到這個數組，我們就可以透過輕鬆地重複每個字元來產生解碼後的字串，例如「 W 」 12次，「 B 」一次等。
我們將再次使用環視技術來建立正規表示式來分割輸入字串：「 (?<=\\D)|(?=\\D+) 」。
在這個正規表示式中：
-
(?<=\\D)– 正向後向斷言可確保分割發生在非數字字元之後。 -
|– 表示「或」關係 -
(?=\\D+)– 正向先行斷言可確保分割發生在一個或多個非數字字元之前。
這種組合允許在 RLE 編碼字串中的連續計數和字元之間的邊界處進行分割。
接下來，我們建構基於正規表示式分割的解碼方法：
String runLengthDecodeByRegEx(String rle) {
if (rle.isEmpty()) {
return "";
}
String[] arr = rle.split("(?<=\\D)|(?=\\D+)");
if (arr.length % 2 != 0) {
throw new IllegalArgumentException("Not a RLE string");
}
StringBuilder result = new StringBuilder();
for (int i = 1; i <= arr.length; i += 2) {
int count = Integer.parseInt(arr[i - 1]);
String c = arr[i];
result.append(String.join("", Collections.nCopies(count, c)));
}
return result.toString();
}如程式碼所示，我們在方法的開頭包含了一些簡單的驗證。然後，在迭代分割數組時，我們從數組中檢索計數和字符，並將重複計數次數的字符附加到result StringBuilder中。
最後，這種解碼方法適用於我們的範例：
assertEquals(INPUT, runLengthDecodeByRegEx(RLE));5. 結論
在本文中，我們首先討論了遊程編碼的工作原理，然後探討了實現遊程編碼和解碼的兩種方法。
與往常一樣，範例的完整原始程式碼可在 GitHub 上取得。