$show=/label

Java Program to "Run Length Encoding (RLE)" - String Compression

SHARE:

Java Program to "Run Length Encoding (RLE)" String Compression Technique and Step by step explanation algorithm.

1. Introduction


In today's article, You will learn What is the "Run Length Encoding" technique which is heavily used in string data compression. This is an experienced java interview question for 4-6 years developers. Earlier days this is used to compress the black and white photos.


Run Length Encoding is abbreviated as "RLE".

Run-length encoding (RLE) is a form of lossless data compression in which runs/flows of data are stored as a single data value and count, rather than as the original run.
Java Program to "Run Length Encoding (RLE)" - String Compression



This works for only sequences in which the same data value occurs in many consecutive data elements.

Examples:

Input: aaabbccccd
Output:a3b2c4d1

Input: xxxyyziiii
Output: x3y2z1i4

Input: kkkkkkiiiiiiuuuuasdfgllll
Output: k6i6u4a1s1d1f1l4

All of the above examples are valid. If the string "aaabba" is invalid because character 'a' is repeated in non-consecutive which is appeared after character 'b'. If the string is invalid then it may produce unexpected results. Please keep in mind this note before implementing it in real-time applications.



2. Algorithm


Now it's time to think about the algorithm that produces the desired output.

Follow these steps to learn and understand the algorithm.

A) Create the output string which is empty and count variable which value is 0 for now.
B) Take the first character and compare it with the next character. If matches, increment count by 1. For each successful match, the count will be incremented by 1. Then take the next character and do compare until it finds no match.
C) Once you find the no match, add the current character and count to the output string.
D) Take the next unmatched character and repeat steps B and C.
F) After completing all characters finally, the output string will have the compressed string.

3. Java Program on String Compression using Run Length Encoding


package com.java.w3schools.blog.java.programs;

public class StringCompression {

 public static void main(String[] args) {

  String inputString = "aaabbccccd";
  String outputString = "";

  int count = 1;
  for (int i = 0; i < inputString.length(); i++) {

   // resetting to 1 for every new character (counting current character).
   count = 1;
   while (i < inputString.length() - 1 && inputString.charAt(i) == inputString.charAt(i + 1)) {
    count++;
    i++;
   }
   outputString = outputString + inputString.charAt(i) + count;
  }
  System.out.println("Input data string : " + inputString);
  System.out.println("Output data string after applying data compression technique : " + outputString);

 }

}

Output:

Input data string : aaabbccccd
Output data string after applying data compression technique : a3b2c4d1

This works well for longer inputs.

Input data string : jjjjjjjjjdddddddddiiiuusskkpppuuutttrewqnbhyj
Output data string after applying data compression technique : j9d9i3u2s2k2p3u3t3r1e1w1q1n1b1h1y1j1

4. Time Complexity


This program runs a loop from index 0 to length on the input string. You have seen that the above program has one for loop and nested while loop. Looks time complexity O(n2) but it is not. Actually, it is O(n) only. The reason behind this is the outer loop run for unique character and inner loop for repeated characters.

So in our example, input string "aaabbccccd" outer for loop runs for the character a,b,c,d and inner while loop runs for only repeated characters such as "aa b ccc".

Outer loop: 4 times
Inner loop: 6 times

Input String length: 10

input length = outer loop length + inner loop length. So it is O(n). 

5. Conclusion


In this article, you have learned how to use the "Run Length Encoding" compression technique on a string. But this compression is applicable only for the inputs which as many consecutive data elements.

Share this article with your friends and post your questions to me.

COMMENTS

BLOGGER: 3
  1. Hello! Why would it be (i < inputString.length() - 1) in the inner loop? Why is it not (i < inputString.length()) ? Thanks!

    ReplyDelete
    Replies
    1. Hello KB, Nice question.

      It should be i < inputString.length() - 1 because doing the i + 1 in the next step as below.

      inputString.charAt(i) == inputString.charAt(i + 1)

      If you use i < inputString.length() this, then it will throw IndexOutOfBoundsException at runtime.

      Hope, this helpful.

      Delete
  2. Hi, how would you create a run length decoder?

    ReplyDelete
Please do not add any spam links in the comments section.

About Us

Author: Venkatesh - I love to learn and share the technical stuff.
Name

accumulo,1,ActiveMQ,2,Adsense,1,API,37,ArrayList,18,Arrays,24,Bean Creation,3,Bean Scopes,1,BiConsumer,1,Blogger Tips,1,Books,1,C Programming,1,Collection,8,Collections,37,Collector,1,Command Line,1,Comparator,1,Compile Errors,1,Configurations,7,Constants,1,Control Statements,8,Conversions,6,Core Java,149,Corona India,1,Create,2,CSS,1,Date,3,Date Time API,38,Dictionary,1,Difference,2,Download,1,Eclipse,3,Efficiently,1,Error,1,Errors,1,Exceptions,8,Fast,1,Files,17,Float,1,Font,1,Form,1,Freshers,1,Function,3,Functional Interface,2,Garbage Collector,1,Generics,4,Git,9,Grant,1,Grep,1,HashMap,2,HomeBrew,2,HTML,2,HttpClient,2,Immutable,1,Installation,1,Interview Questions,6,Iterate,2,Jackson API,3,Java,32,Java 10,1,Java 11,6,Java 12,5,Java 13,2,Java 14,2,Java 8,128,Java 8 Difference,2,Java 8 Stream Conversions,4,java 8 Stream Examples,12,Java 9,1,Java Conversions,14,Java Design Patterns,1,Java Files,1,Java Program,3,Java Programs,114,Java Spark,1,java.lang,4,java.util. function,1,JavaScript,1,jQuery,1,Kotlin,11,Kotlin Conversions,6,Kotlin Programs,10,Lambda,2,lang,29,Leap Year,1,live updates,1,LocalDate,1,Logging,1,Mac OS,3,Math,1,Matrix,6,Maven,1,Method References,1,Mockito,1,MongoDB,3,New Features,1,Operations,1,Optional,6,Oracle,5,Oracle 18C,1,Partition,1,Patterns,1,Programs,1,Property,1,Python,2,Quarkus,1,Read,1,Real Time,1,Recursion,2,Remove,2,Rest API,1,Schedules,1,Serialization,1,Servlet,2,Sort,1,Sorting Techniques,8,Spring,2,Spring Boot,23,Spring Email,1,Spring MVC,1,Streams,31,String,61,String Programs,28,String Revese,1,StringBuilder,1,Swing,1,System,1,Tags,1,Threads,11,Tomcat,1,Tomcat 8,1,Troubleshoot,26,Unix,3,Updates,3,util,5,While Loop,1,
ltr
item
JavaProgramTo.com: Java Program to "Run Length Encoding (RLE)" - String Compression
Java Program to "Run Length Encoding (RLE)" - String Compression
Java Program to "Run Length Encoding (RLE)" String Compression Technique and Step by step explanation algorithm.
https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhmwOExZQzlLybXp9WMkLrZlU9AtZebede2-iQRCONlVwvn-Jlq238pho_TV-6nbBoYlqjO2ZzfOSDWvmKMlPcZAm9SiCQUikuZ_skc9vFDjNnRnHOf_lKr3uuhrIOvBPakI8iIUkt8iy8/s640/Java+Program+to+%2522Run+Length+Encoding+%2528RLE%2529%2522+-+String+Compression.png
https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhmwOExZQzlLybXp9WMkLrZlU9AtZebede2-iQRCONlVwvn-Jlq238pho_TV-6nbBoYlqjO2ZzfOSDWvmKMlPcZAm9SiCQUikuZ_skc9vFDjNnRnHOf_lKr3uuhrIOvBPakI8iIUkt8iy8/s72-c/Java+Program+to+%2522Run+Length+Encoding+%2528RLE%2529%2522+-+String+Compression.png
JavaProgramTo.com
https://www.javaprogramto.com/2019/12/string-run-length-encoding.html
https://www.javaprogramto.com/
https://www.javaprogramto.com/
https://www.javaprogramto.com/2019/12/string-run-length-encoding.html
true
3124782013468838591
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS PREMIUM CONTENT IS LOCKED STEP 1: Share to a social network STEP 2: Click the link on your social network Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy Table of Content