String compression algorithm

9 posts / 0 new
Last post
heartin
String compression algorithm

Write an algorithm for string compression using counts of repeated characters

E.g. aaaaarrrrbbb will become a5r4b3

Additional note: if the new compressed string is is bigger than the original string, return original string.

Was it useful?
clalam
what should be the output if

what should be the output if the string is "aaabbaazz"?

Option1: a3b2a2z2

Option2: a5b2z2

Was it useful?
heartin
Good question, but I will

Good question, but I will make you only answer this.

Important property of any compression algorithm in real world is that it should be able to reconstruct the original string from the compressed form.

From which one of the above compressed forms (a3b2a2z2 and a5b2z2) do you think you can reconstruct the original string above (aaabbaazz) exactly as it is?

Note: Please answer even if you understood.

Was it useful?
clalam
Thanks for clearing my doubt.

Thanks for clearing my doubt.. We can reconstruct the string only when we construct like a5b2a2z2..

Was it useful?
clalam
Here is my solution:

Here is my solution:

The time complexity is O(n)...

Your suggestions to improve performance is highly appreciated..

public class StringCompression {

    public static void main(String[] args) {
        String input = "aaaaarraarrbbb";
        
        // SOLUTION 1
        char[] inputChArr = input.toCharArray();
        StringBuffer sb = new StringBuffer();
        boolean[] boolArr = new boolean[255];
        int count = 0;
        
        for(int i = 0 ;i<inputChArr.length;i++) {
            if(boolArr[inputChArr[i]]) {
                count++;
            }
            else {
                boolArr[inputChArr[i]] = true;
                if(i!=0 && inputChArr[i] != inputChArr[i-1]) {
                    boolArr[inputChArr[i-1]] = false;
                    sb.append(count + "" + inputChArr[i]);
                    //sb.append(inputChArr[i]);
                }else {
                    //For first Character alone
                    sb.append(inputChArr[i]);
                }
                count = 1;
            }    
        }
        sb.append(count);
        System.out.println("Input String: " + input + "\nCompressed String: " + sb);
        
        
        }

}

Was it useful?
huzefa
explain

clalam : can you please explain your first solution ?

Was it useful?
clalam
Please check the explanation

Please check the explanation below:

Reply me for any doubts..

1) I am just marking the first occurance of each unique character as "true"(255 unique char possiblities in ASCII). 

2) so, from second iteration onwards, it will check in the boolean array for the charcter is already present or not..

              a) if it is already present and repeating just increment the count.

              b) otherwise mark next char as "true" and previous char as "false"(as the it may come again) and                             construct your output by using stringbuffer append.

              c) repeat till end of the array.

3) Print the StringBuffer value outside the loop..

 

for this string: "aaaaarraarrbbb"

for first iteration 

    booleanArr[a(which is 97)] will be true and count will be 1.

    from second iteration onwards.. count will be incremented till 5th iteration as booleanArr[a] is true during these iterations.

    6th iteration, it will go to else part and mark booleanArr[r] as true and booleanArr[a] as false(since a may come after r as in the above input). At this point, your output string contains "a5r"

    the above steps will be repeated till end of the array and finally you will have the required result in your output string..

 

  

 

Was it useful?
huzefa
count

how does this :

sb.append(count);

after the for loop works .... means i know its correct but how you appended only count ?

Was it useful?
clalam
If you observe else if

If you observe else if condition, I am appending count of previous char and current char, that means when "r" comes first time, the SB will become "a5r". But we should also append count of last char of the string where as my condition work here since it comes out of for loop but I have the count of last char in my count variable. Simply append that to your output string..

If you wanna play with it,just try to remove that statement alone and you won't see the count of last character.

Was it useful?

Search the Web

Custom Search

Searches whole web. Use the search in the right sidebar to search only within javajee.com!!!