aspose file tools*
The moose likes Java in General and the fly likes String compression Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "String compression" Watch "String compression" New topic
Author

String compression

ramakrishna ranga
Greenhorn

Joined: Sep 22, 2007
Posts: 3
How to compress and decompress String like

compress:
Input = AAAABBSXXZZZZ
Output = 4A2BS2X4Z

decompress:
Input = 4A2BS2X4Z
Output=AAAABBSXXZZZZ
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18896
    
  40

Well, what have you done so far? And what problems are you having / seeing?

As far as homework assignment goes, this looks like one of the easier ones.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Rich Nelson
Greenhorn

Joined: Sep 22, 2007
Posts: 15
I have the exact same assignment. We're not allowed to use loops though, and the extent of what we ARE allowed to do is really just if statements and switch cases.

Basically, we need to input something like =6-=10+=9j=24$ where = is the delimiter. The output should be:

------++++++++++jjjjjjjjj$$$$$$$$$$$$$$$$$$$$$$$$

Edit: I guess I just need to know where to start. I honestly have no idea.

Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Hey, welcome to the ranch, twice! This place works best when you take a shot at something and show us what you have. That way we can see exactly what parts you figured out and where you are stuck.

Say you were pulling cards off a deck and you couldn't see ahead. If you pulled a card that didn't match the previous one, what would you write down? If it did match the previous one, what would you write? See if you can write that logic down in "structured English" like

So first step: no Java, just explain how you'd count cards.


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Nicholas Jordan
Ranch Hand

Joined: Sep 17, 2006
Posts: 1282
We're not allowed to use loops though

Well how do we do it then ? The approach Stan takes is called Tiny, and it grows like the Chia pet you see on Television. The loop approach was described by Alan Turing awhile back while working for a while for the British Government. The other approach, called Duff's device just lets the compiler do the unrolling for you. You still code a loop - note Stan's simplified plain language problem statement has the word while in it.

In computer science, a while is a loop: No other way. You can unroll the loop, but then by Alan's description of the problem, the machine then has to be as big as the problem is. So if you have a way to read the numbers into a machine readable number,......

You do have that, don't you ?


[ September 22, 2007: Message edited by: Nicholas Jordan ]

"The differential equations that describe dynamic interactions of power generators are similar to that of the gravitational interplay among celestial bodies, which is chaotic in nature."
Rich Nelson
Greenhorn

Joined: Sep 22, 2007
Posts: 15
That's a good hint, I'll try it out . Thanks.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19720
    
  20

Well technically you could do it without loops but using recursion instead:

Using this technique just to avoid using loops is quite bad though. If possible, loops should always get the preference, because with recursion all method local variables get put on the stack for each call.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18896
    
  40

Using this technique just to avoid using loops is quite bad though. If possible, loops should always get the preference, because with recursion all method local variables get put on the stack for each call.


Also keep in mind that someone who hasn't learned loops yet, is unlikely to know what recursion is.

Henry
[ September 23, 2007: Message edited by: Henry Wong ]
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Using recursion to avoid loops sounds like a bar bet to me. Possible, but it might get you punched in the schnoz. I sometimes wish for a compiler that would actually punch the coder in the beezer for something like that.

BTW: The example given above =6-=10+=9j=24$ where = is the delimiter is a bit ambiguous because it has either one or two digits of repeat count. How do you know how many digits to use? What if you were repeating 5s? =35a means what?

I made one of these in COBOL years ago where the minimum number of repeats to be worth escaping and the number of digits were both configurable. Our mainframe data tended to have repeating zeros and spaces and it paid off quite nicely in network time vs cpu time.
[ September 23, 2007: Message edited by: Stan James ]
Nicholas Jordan
Ranch Hand

Joined: Sep 17, 2006
Posts: 1282
Well, gee folks, OO sounds like a solution in search of problem to me. Using recursion to avoid loops sounds like what the instructor is intending the poster will do, but since I enjoy all-night hair pullers where I   really   figure out how to do it, you know, how the Krell would do it, this triggers a memory of my first approach to the problem:

1: Write and compile a file that has something along the lines of:



2: Open the file in the text editor and copy paste it over to the source code file.

It ran ! Isn't that a joy for the first time programmer ?

You should see stl vector/map add I wrote shortly after that, I stiill have it. Want to see it ?



[ to the Poster: Look up Towers of Hanoi - recursion is a loop ]
[ September 23, 2007: Message edited by: Nicholas Jordan ]
Pat Farrell
Rancher

Joined: Aug 11, 2007
Posts: 4659
    
    5

I would think you could use a regex to identify repeats, and use length() on the specific match subsets. This would not be obvious, but could probably be smashed into working.

I'd be tempted to use a loop, but I rarely listen to the professors even when I was one.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: String compression