Array

Run-length encoding

Pinterest LinkedIn Tumblr

Run-length encoding is a very simple form of data compression in which runs of data are stored as a single data value and count, rather than as the original run.

Algorithm Explanation

Initialize the run length encoding text and pass an argument to the utility function. Encode text utility function take the input string and count the number of characters.
It appends in the text for each character. The result string return and display the encoded text.
Decode text utility function takes the encoded string and check the character and find the count. It shows all the character and append only the characters without count.
Display the decode ( original text).

Source Code

package com.dsacode.DataStructre.array;
 
import java.util.regex.Matcher;
import java.util.regex.Pattern;
 
public class RunLengthEncoding {
    public static String encode(String source) {
        StringBuffer dest = new StringBuffer();
        for (int i = 0; i < source.length(); i++) {
            int runLength = 1;
            while (i+1 < source.length() && source.charAt(i) == source.charAt(i+1)) {
                runLength++;
                i++;
            }
            dest.append(runLength);
            dest.append(source.charAt(i));
        }
        return dest.toString();
    }
  
    public static String decode(String source) {
        StringBuffer dest = new StringBuffer();
        Pattern pattern = Pattern.compile("[0-9]+|[a-zA-Z]");
        Matcher matcher = pattern.matcher(source);
        while (matcher.find()) {
            int number = Integer.parseInt(matcher.group());
            matcher.find();
            while (number-- != 0) {
                dest.append(matcher.group());
            }
        }
        return dest.toString();
    }
  
    public static void main(String[] args) {
         
        String text = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW";
        System.out.println("Run Length Encoding Text: "+text);
        System.out.println("Encoded Text: "+encode(text));
        System.out.println("Decoded Text: "+decode("1W1B1W1B1W1B1W1B1W1B1W1B1W1B"));
    }
}
    

Output

Run Length Encoding Text: WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
Encoded Text: 12W1B12W3B24W1B14W
Decoded Text: WBWBWBWBWBWBWB

Write A Comment