Run-length encoding (RLE) of stream segments ...
lbrtchx_gemalekom
~
I know this is not a newsgroup about algorithms, but you may know of a java library or some API doing this.
~
There are versions of character-based Run length encoding (RLE)
~
http://en.wikipedia.org/wiki/Run-length_encoding
~
http://rosettacode.org/wiki/Run-length_encoding
~
But say instead of basing the encoding on single characters you consider sequences. Let's take as an example the one used and cannibalized on the web:
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
RLE is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. This is most useful on data that contains many such runs: for example, relatively simple graphic images such as icons, line drawings, and animations. It is not recommended for use with files that don't have many runs as it could potentially double the file size.
For example, consider a screen containing plain black text on a solid white background. There will be many long runs of white pixels in the blank space, and many short runs of black pixels within the text. Let us take a hypothetical single scan line, with B representing a black pixel and W representing white:
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
If we apply the run-length encoding (RLE) data compression algorithm to the above hypothetical scan line, we get the following:
12W1B12W3B24W1B14W
Interpret this as twelve W's, one B, twelve W's, three B's, etc.
While: WBWBWBWBWBWBWB would be: 1W1B1W1B1W1B1W1B1W1B1W1B1W1B
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
The encoding data is actually longer! It could simple be 7[WB]
~
Also, the longest non overlapping segments should be prioritized over shorter repeated ones:
~
WBXAWBXWBXQWBPWBQ
~
Instead of encoding that sequence as (something like ;-)):
~
{0,4,7,11,14}[WB],{2,6,9}X,{3}A,{10,16}Q,{13}P
~
It should be encoded like:
~
{0,4,7}[WBX],{3}A,{10,16}Q,{11,14},WB,{13}P
~
Any theories on these kinds of encodings? Ideally implemented in Java?
~
Thanks
lbrtchx
Arne Vajhøj
RLE performs so poorly compared to modern compression algorithms, that
I don't think there is much interest in them today.
Why don't you just use regular zip (deflate) algorithm, which is
build into Java.
Arne
lbrtchx_gemalekom
Because I need some sort of Run-length encoding to get the "finger" (characteristic) of those mistyping/proof reading texts and re-encode the RLE as a regexp. (So I know what some editors/proofreaders "mean" when they litter texts in their own ways ...)
~
lbrtchx
Arne Vajhøj
That could just as well have been in Chinese - I completely don't get it.
Arne
Lew
>>> Why don't you just use regular zip (deflate) algorithm, which is build into
>>> Java.
>> ~
>> Because I need some sort of Run-length encoding to get the "finger"
>> (characteristic) of those mistyping/proof reading texts and re-encode the
>> RLE as a regexp. (So I know what some editors/proofreaders "mean" when they
>> litter texts in their own ways ...)
Arne Vajhøj wrote:
> That could just as well have been in Chinese - I completely don't get it.
+1
Also, librtchx, please use "reply" to answer posts instead of beginning a new
thread each time. And quit with the tildes if that's not too much to request.
--
Lew
Ceci n'est pas une pipe.
lbrtchx_gemalekom
> > > Why don't you just use regular zip (deflate) algorithm, which is build into Java.
~
> > Because I need some sort of Run-length encoding to get the "finger" (characteristic) of those mistyping/proof reading texts and re-encode the RLE as a regexp. (So I know what some editors/proofreaders "mean" when they litter texts in their own ways ...)
OK. The technical term (someone's) "finger" (or was it "hand"?) was coined during WW2 by "intelligence" services wiretapping each other's morse code messages. They didn't know the actual persons on the other end but they did know "their finger" by the slight, but very much identifying, difference in which they tapped on their telegraph, the time of day they worked, ...
~
The thing is that, due to various reasons, each particular proof reader has a characteristic footprint/way to mess with texts, say, to some people a new paragraph is two CRLF sequences to other a CRLF + SP one ...
~
lbrtchx
Lew
> On 26-12-2010 14:02, lbrt chx _ gemale kom wrote:
>>>> Why don't you just use regular zip (deflate) algorithm, which is build into Java.
Again, you couldn't use "reply" to keep the thread intact?
Why not?
Lew
ATTRIBUTE YOUR CITATIONS!
Arne Vajhøj wrote:
>> That could just as well have been in Chinese - I completely don't get it.
lbrt chx _ gemale kom wrote:
> OK. The technical term (someone's) "finger" (or was it "hand"?)
> was coined during WW2 by "intelligence" services wiretapping each
> other's morse [sic] code messages. They didn't know the actual persons
> on the other end but they did know "their finger" by the slight, but
> very much identifying, difference in which they tapped on their telegraph,
The term is "fist", not "finger".
http://en.wikipedia.org/wiki/Fist
http://en.wiktionary.org/wiki/fist #3
Perhaps you're thinking of
http://en.wikipedia.org/wiki/Finger_(gesture)
Arne Vajhøj
It is not clear what value RLE provide in this context.
Arne
lbrtchx_gemalekom
~
Isn't java.lang.StringBuffer supposed to do its internal buffering by itself?
~
lbrtchx
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 16
at java.lang.AbstractStringBuilder.insert(AbstractStringBuilder.java:979)
at java.lang.StringBuffer.insert(StringBuffer.java:446)
at AUtils00Test.main(AUtils00Test.java:104)
~
/java/lang/StringBuffer.java's insert should "ensureCapacity_unsynchronized" before doing its business as it does for all other methods; which you can see from:
~
http://www.opensource.apple.com/source/gccfast/gccfast-1622/libjava/java/lang/StringBuffer.java
~
/** Insert the <code>String</code> argument into this <code>StringBuffer</code>.
* @param offset the place to insert.
* @param str the <code>String</code> to insert.
* @return this <code>StringBuffer</code>.
* @exception IndexOutOfBoundsException if <code>offset</code> is out
* of range for this <code>StringBuffer</code>.
*/
public synchronized StringBuffer insert (int offset, String str)
{
if (offset < 0 || offset > count)
throw new StringIndexOutOfBoundsException (offset);
// Note that using `null' is from JDK 1.2.
if (str == null)
str = "null";
int len = str.length();
ensureCapacity_unsynchronized (count+len);
System.arraycopy(value, offset, value, offset+len, count-offset);
str.getChars(0, len, value, offset);
count += len;
return this;
}
~
Lew
Still having trouble mastering that "reply" button, hm? I know - it's a tough
one!
On 12/26/2010 09:32 PM, lbrt chx _ gemale kom wrote:
> Actually, I just coded an implementation myself, but as I was testing my code, I got an Exception that to me looks like a bug more than an error from myself
> ~
Stupid tildes.
Since you don't show the code "from yourself" we have to remain suspicious of
your conclusion.
> Isn't java.lang.StringBuffer supposed to do its internal buffering by itself?
As it does, but one question - why are you using 'StringBuffer' instead of
'StringBuilder' instead of letting the JVM handle it?
> ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
> ~
You sure do love your tildes, don't'cha there, sport?
> Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 16
> at java.lang.AbstractStringBuilder.insert(AbstractStringBuilder.java:979)
> at java.lang.StringBuffer.insert(StringBuffer.java:446)
> at AUtils00Test.main(AUtils00Test.java:104)
Show us your code. USE REPLY! If it isn't /too/ much trouble. Yeesh!
Lew
> Still having trouble mastering that "reply" button, hm? I know - it's a tough
> one!
lbrt chx _ gemale kom wrote:
>> Actually, I just coded an implementation myself, but as I was testing my
>> code, I got an Exception that to me looks like a bug more than an error from
>> myself
>> ~
Lew wrote:
> Since you don't show the code "from yourself" we have to remain suspicious of
> your conclusion.
lbrt chx _ gemale kom wrote:
>> Isn't java.lang.StringBuffer supposed to do its internal buffering by itself?
Had you actually read the API documentation for the 'StringBuffer#insert()'
family of methods, you'd've noticed that they're *documented* to throw
'IndexOutOfBoundsException' under certain usage patterns. Does your code use
those patterns?
Lew wrote:
> As it does, but one question - why are you using 'StringBuffer' instead of
> 'StringBuilder' instead of letting the JVM handle it?
...
Arne Vajhøj
> Actually, I just coded an implementation myself, but as I was testing my code, I got an Exception that to me looks like a bug more than an error from myself
> ~
> Isn't java.lang.StringBuffer supposed to do its internal buffering by itself?
It is supposed to increase the buffer size by itself when you append.
> Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 16
> at java.lang.AbstractStringBuilder.insert(AbstractStringBuilder.java:979)
> at java.lang.StringBuffer.insert(StringBuffer.java:446)
> at AUtils00Test.main(AUtils00Test.java:104)
> ~
> /java/lang/StringBuffer.java's insert should "ensureCapacity_unsynchronized" before doing its business as it does for all other methods; which you can see from:
It should expand the buffer if necessary to hold the extra
characters being pushed out by the insert.
If you try and insert beyond the end it is supposed to throw
an exception.
> http://www.opensource.apple.com/source/gccfast/gccfast-1622/libjava/java/lang/StringBuffer.java
> ~
> /** Insert the<code>String</code> argument into this<code>StringBuffer</code>.
> * @param offset the place to insert.
> * @param str the<code>String</code> to insert.
> * @return this<code>StringBuffer</code>.
> * @exception IndexOutOfBoundsException if<code>offset</code> is out
> * of range for this<code>StringBuffer</code>.
which is documented here!
> */
> public synchronized StringBuffer insert (int offset, String str)
> {
> if (offset< 0 || offset> count)
> throw new StringIndexOutOfBoundsException (offset);
and done here!
> // Note that using `null' is from JDK 1.2.
> if (str == null)
> str = "null";
> int len = str.length();
> ensureCapacity_unsynchronized (count+len);
And making this call *after* the test means that the
implementation follow what it is documented to do (and
not your expectations).
> System.arraycopy(value, offset, value, offset+len, count-offset);
> str.getChars(0, len, value, offset);
> count += len;
> return this;
> }
Arne
Wanja Gayk
kom says...
RLE is quite easy to implement in Java.
You might look into a more sophisticated version using controlbytes or
control sequences.
You chose the byte that is the least likely to occur in the data stream
as control byte and encode runs like follows ("#" being the
controlbyte):
#12WB#12W#3B#24WB#14W
instead of: 12W1B12W3B24W1B14W
That approach will waste some bytes for each run, but it will save on
random data, because you'd get:
WBWBWBWBWBWBWB
Instead of: 1W1B1W1B1W1B1W1B1W1B1W1B1W1B
Controlbytes itself can be encoded like: "#1").
An even shorter method is to substitute the controlbytes by using the
first two characters of a run to act as control sequence, so you'd get:
WW10BWW10BB1WW22BWW12
Any time your decoder finds two subsequent characters, it assumes the
next byte is a count for the same characters to follow.
Controls bytes offer more flexibility though, because for 2-byte-runs
you might introduce a second controlbyte for another coding scheme.
Imagine 2-byte runs:
$7WB
Anyway, since it's hard to know the optimum chunk-size, which may be
locally different, you're usually better off with using an LZSS
(Lempel,Ziv,Storer,Szymanski variant of LZ77 with controlbyte)
for anything else but simple runs.
LZSS encodes using references to previous ocurrences, using a
controlbyte:
The whiskymixer mixes whisky in a whiskymixer.
becomes
The whiskymixer $6,4s$18,7 in a$30,12.
where
$6,4
reads: copy from cursor position minus 6, 4 characters.
Any sequence smaller than 3 bytes gets ignored, any controlbyte gets
encoded as $1.
The end of file can be denoted by a zero offset or a zero run length:
#0 or $0 respectively.
Please note that all numbers in the schemes are raw values, no text, and
that the comma I used in the LZSS sequences is just a separator for the
human eye.
So you could imagine a hybrid approach using different controlbytes (or
"escapes", as they are also called) for different encodings:
#=RLE (run length, byte)
$=RLE2 (run length, 2 bytes)
%=LZSS (displacement, n)
&=LZSS+run (displacement, n, run length)
There have been several compressors which use a hybrid approach and more
sophisticated encoding of the encoding sequence, for example with Elias
Gamma codes, which encode near sequences with less bits than far
sequences.
Be warned that LZSS is not quite the fastest way to compress data, but
it's rather easy to implement and decompression is tivial.
This could be an interesting read on a hybrid approach, there is:
http://www.cs.tut.fi/~albert/Dev/pucrunch/
http://www.cs.tut.fi/~albert/Dev/pucrunch/packing.html
The latter being a link with good explainations to different algorithms.
As as alternative you might like to dive into arithmetic coding:
http://en.wikipedia.org/wiki/Arithmetic_coding
http://www.dogma.net/markn/articles/arith/part1.htm
http://www.colloquial.com/ArithmeticCoding/
With the first link being a more abstract explanation, the second link
being a very good introduction with some c-sourcecode and the last one
some Java implementation.
Kind regards,
Wanja
--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---
Arne Vajhøj
Why LZSS and not LZH?
I would expect LZH to always give better compression and LZH comes
with Java so no need for a third party library.
(OK - deflate is a not a simple LZH but has some tweaks, but those
tweaks should not be a problem)
Arne
Wanja Gayk
says...
> Why LZSS and not LZH?
>
> I would expect LZH to always give better compression and LZH comes
> with Java so no need for a third party library.
>
> (OK - deflate is a not a simple LZH but has some tweaks, but those
> tweaks should not be a problem)
LZH ist, as far as I know, a hybrid of LZSS and adaptive Huffman coding,
which means that the escape sequence, the reference and the message
itself are decoded from an apadptive huffman tree. Since I guess the
original poster is quite new to the topic, I would not recommend to try
this for a start.
LZH is, as far as I know, implemented in Winzip. Java already knows the
ZipOutputStream and the ZipInputStream. No need to reinvent the wheel.
;-)
Kind Regards,
Arne Vajhøj
> In article<4d1928ec$0$23755$1472...@news.sunsite.dk>, ar...@vajhoej.dk
> says...
>> Why LZSS and not LZH?
>>
>> I would expect LZH to always give better compression and LZH comes
>> with Java so no need for a third party library.
>>
>> (OK - deflate is a not a simple LZH but has some tweaks, but those
>> tweaks should not be a problem)
>
> LZH ist, as far as I know, a hybrid of LZSS and adaptive Huffman coding,
> which means that the escape sequence, the reference and the message
> itself are decoded from an apadptive huffman tree. Since I guess the
> original poster is quite new to the topic, I would not recommend to try
> this for a start.
>
> LZH is, as far as I know, implemented in Winzip. Java already knows the
> ZipOutputStream and the ZipInputStream. No need to reinvent the wheel.
Exactly.
Even a new to the topic could use it.
Arne
lbrtchx_gemalekom
~
The thing about having to use a customized version of some sort of RLE relates to the fact that when you work on corpora of millions of texts which are continually updated and must be kept transactionally stable you are forced to strike a balance between accessibility,
indexability, size and transactional consistency within individual texts and corpora at large
~
I have an idea that I have implemented and put through implementation and severe stress testing, but I may have to read up some more on compression strategies
~
> and done here!
> > // Note that using `null' is from JDK 1.2.
> > if (str == null)
> > str = "null";
> > int len = str.length();
> > ensureCapacity_unsynchronized (count+len);
> And making this call *after* the test means that the
> implementation follow what it is documented to do (and
> not your expectations).
~
Arne you tease me (as many other people) telling me I code java as if I was coding C, but here I think you are talking like a politician ;-)
~
I do understand it is per spec as part of the implementation of java.lang.StringBuffer being append("...") its primary method, but to me it comes as more natural to do the buffering strategy first in any case if possible or throw a run time exception if is not. But then again it is my opinion. To me StringBuffer is just a facade to an underlying character buffering strategy
~
I just went ahead and coded the buffering myself in a C-style way
~
lbrtchx
Lew
Why do you not answer the questions pertaining to your posts?
lbrt chx _ gemale kom wrote:
(Why did you not attribute the citation? Especially without the threading
provided by "reply", it's nearly impossible to follow the thread the way you
post.)
[attribution restored] Arne Vajhøj wrote:
>> And making this call *after* the test means that the
>> implementation follow what it is documented to do (and
>> not your expectations).
lbrt chx _ gemale kom:
> Arne you tease me (as many other people) telling me I code java [sic]
> ~as if I was coding C, but here I think you are talking like a politician ;-)
What does that mean, "talking like a politician"? He's telling you that the
code works as it's documented to do. That's talking like an engineer.
> I do understand it is per spec as part of the implementation of
> ~java.lang.StringBuffer being append("...") its primary method,
> but to me it comes as more natural to do the buffering strategy first
> in any case if possible or throw a run time exception if is not.
It's vital that the code work as documented, hence why it's coded that way.
> But then again it is my opinion. To me StringBuffer is just a facade to an
> underlying character buffering strategy
And what is 'StringBuilder' to you?
> ~I just went ahead and coded the buffering myself in a C-style way
Sure, because re-inventing the wheel is always better, particularly when you
cannot bring yourself to use the standard API as it's documented to work.
You never did show us your code that had the bug, despite our requests. Now
that's participatory!
Lars Enderin
> Why do you not use "reply"?
>
himself? I found the header X-Newsreader: NetComponents.
When I google that, the first hit refers to a Java example on using
PostMessage.java. Whatever program he's using may not be able to post a
proper reply.
Lew
>> Why do you not use "reply"?
Lars Enderin wrote:
> He doesn't seem to use a normal newsreader. Maybe he's written it
> himself? I found the header X-Newsreader: NetComponents.
> When I google that, the first hit refers to a Java example on using
> PostMessage.java. Whatever program he's using may not be able to post a
> proper reply.
Interesting speculation. I wonder if the OP would confirm that if he ever
/actually answered the question/.
If true, then it's incumbent on the OP to use one of the plethora of readers,
many free, that do support "reply". It ain't much of a newsreader if it
doesn't, and librtchx would be well-advised in their own interest to find a
way to keep the threads connected.
Between that and refusal to answer germane questions, the OP might find
themself alone on the playing field. This is a discussion group, not a bunch
of lackeys whose job it is to hunt around for connected messages to help a
non-participatory librtchx.
Wanja Gayk
says...
> >> Why LZSS and not LZH?
[..]
> > LZH is, as far as I know, implemented in Winzip. Java already knows
the
> > ZipOutputStream and the ZipInputStream. No need to reinvent the wheel.
>
> Exactly.
>
> Even a new to the topic could use it.
Well, but that's boring isn't it? If you like to get into the topic, why
not start with something simple?
I find teh compression stuff really interesting!
Cheers,
-Wanja-
Arne Vajhøj
> In article<4d1a19d9$0$23753$1472...@news.sunsite.dk>, ar...@vajhoej.dk
> says...
>>>> Why LZSS and not LZH?
> [..]
>>> LZH is, as far as I know, implemented in Winzip. Java already knows the
>>> ZipOutputStream and the ZipInputStream. No need to reinvent the wheel.
>>
>> Exactly.
>>
>> Even a new to the topic could use it.
>
> Well, but that's boring isn't it? If you like to get into the topic, why
> not start with something simple?
> I find teh compression stuff really interesting!
I did too. 20 years ago. Implementing LZW and LZSS in Fortran
is so fun.
:-)
Arne
Eric Sosman
> [...]
> I find teh compression stuff really interesting!
Perhaps comp.compression or comp.compression.research would be more
useful to you than comp.lang.java.programmer or alt.undersea.baking ...
--
Eric Sosman
eso...@ieee-dot-org.invalid
Wanja Gayk
org.invalid says...
> On 12/31/2010 12:46 PM, Wanja Gayk wrote:
> > [...]
> > I find teh compression stuff really interesting!
>
> Perhaps comp.compression or comp.compression.research would be more
> useful to you than comp.lang.java.programmer or alt.undersea.baking ...
I know comp.compression, no worries.
Kind regards
Wanja
Eric Sosman
> In article<ifo3bv$gmm$1...@news.eternal-september.org>, esosman@ieee-dot-
> org.invalid says...
>> On 12/31/2010 12:46 PM, Wanja Gayk wrote:
>>> [...]
>>> I find teh compression stuff really interesting!
>>
>> Perhaps comp.compression or comp.compression.research would be more
>> useful to you than comp.lang.java.programmer or alt.undersea.baking ...
>
> I know comp.compression, no worries.
Then what are you doing here? No, don't explain: Just go away.
--
Eric Sosman
eso...@ieee-dot-org.invalid
Arne Vajhøj
I believe that he answered a question that somebody posted
at cljp.
An answer that did talk about Java.
The thread then drifted a little bit off topic, but that
is seen before.
Arne
Chris Uppal
> Then what are you doing here? No, don't explain: Just go away.
Eric, have you been taking Lew's pills ?!
-- chris
Lew
>> Then what are you doing here? No, don't explain: Just go away.
Chris Uppal wrote:
> Eric, have you been taking Lew's pills ?!
I have no beef with Wanja. Nor would I say that algorithm discussions are off
topic here. Don't Java programmers need to know about algorithms?
I am a little disappointed in you, Chris.
Wanja Gayk
org.invalid says...
> >>> [...]
> >>> I find teh compression stuff really interesting!
> >>
> >> Perhaps comp.compression or comp.compression.research would be more
> >> useful to you than comp.lang.java.programmer or alt.undersea.baking ...
> >
> > I know comp.compression, no worries.
>
> Then what are you doing here? No, don't explain: Just go away.
Well, Eric, I guess other readers of this newsgroup will judge better
whose manners are inappropriate here.
As for me, I've had enough of you. "Thank you" for wasting my time.
*plonk*
-Wanja-
Arne Vajhøj
> In article<ig8i07$9dh$1...@news.eternal-september.org>, esosman@ieee-dot-
> org.invalid says...
>>>>> [...]
>>>>> I find teh compression stuff really interesting!
>>>>
>>>> Perhaps comp.compression or comp.compression.research would be more
>>>> useful to you than comp.lang.java.programmer or alt.undersea.baking ...
>>>
>>> I know comp.compression, no worries.
>>
>> Then what are you doing here? No, don't explain: Just go away.
>
> Well, Eric, I guess other readers of this newsgroup will judge better
> whose manners are inappropriate here.
> As for me, I've had enough of you. "Thank you" for wasting my time.
>
> *plonk*
Mistake.
Eric is not like that in general and often provides
good information.
I suspect that he got you mixed up with somebody else.
Arne