BIJECTIVE BWTS PAPER
biject
on the BWTS. I did not write it but worked with a guy good at
writing.
It was rejected. I am not surprised! here is sentence from one of the
reviews.
"Of course one can easily achieve invertability in Burrows-Wheeler
transform, by appending a
special character to the input string. "
Golly Gee why didn't I think of that of course that's the solution to
every thing.
I suspect the best code that most could use is not mine but Yuta's at
http://cid-d435dc59d0b86781.skydrive.live.com/self.aspx/.Public/openbwt-v1.4.zip
I like his v1,4 better than v1.5 but thats me.
has library contains regular BWT along with BWTS and various after
stages
for building a bwt program.
The main advantage for the common user is that you can treat it like
data from a
normal BWT except that there is no INDEX which should make using it in
code
a lot easier.
David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
Thomas Richter
> Many of you know that a paper was submitted to the SODA conference
> on the BWTS. I did not write it but worked with a guy good at
> writing.
>
> It was rejected. I am not surprised! here is sentence from one of the
> reviews.
>
> "Of course one can easily achieve invertability in Burrows-Wheeler
> transform, by appending a
> special character to the input string. "
>
>
> Golly Gee why didn't I think of that of course that's the solution to
> every thing.
That's what I suspected, yes. You must make this *very clear* to the
reader why that isn't the solution you aim at, and what the problem is.
I think we had this discussion here in the group, and it is something
you must definitely change in the paper. I understand your point, but it
is easily lost, and you must catch the reader where he is, namely in the
existing setting and applications for BWT. IOW, describe your problem
clearly, do not try to affect the reader by stating that BWT is not
invertible etc.
Writing a good paper also requires some political insight, I afraid, but
that is how it goes. Try to understand what a typical reader would know,
and then make clear why you don't want to take the traditional position.
Anyhow, don't give up. Writing a good paper and getting it accepted
takes a while.
So long,
Thomas
Tom St Denis
The problem I had with the paper and I stated it weeks ago when this
first came up was that the paper has no competitive advantage
statement. Nowhere does the author compare BWTS to deflate, bzip,
lzma, in terms of ratio, memory used, speed, etc...
It's not enough that the codec works, or really even that it performs
marginally better [which from my reading of the paper it was only a
few percentage better anyways] but that it's actually worth the added
cost in terms of memory or speed.
I mean anyone can make LZ77 compress better by removing the hash list
and performing a full on memcmp over the entire window. But that
would make it ridiculously slow, so generally isn't worth the
tradeoff.
Tom
Thomas Pornin
> I mean anyone can make LZ77 compress better by removing the hash list
> and performing a full on memcmp over the entire window.
Does it ? I was under the impression that the whole hash list concept
was a way to speed up the lookups, but did not make the compressor miss
opportunities. At least that's how I implemented it for Jgz. What makes
compression better (and slower) is look-ahead. The basic LZ77 described
in RFC 1951 decides what to do with the current string with a look-ahead
of 1 byte (i.e. if the byte cannot be added to the current copied
string, then that string is encoded as a copy token, regardless of
whether subsequent bytes would have allowed a more efficient
compromise).
I remember having stumbled upon a presentation from researchers who had
spent quite some time trying to devise better compression within the
strict Zlib format. If I remember correctly, they could compress about
5% better on typical files, although at a cost.
(That's just nitpick, of course.)
--Thomas Pornin
Thomas Richter
> On Sep 11, 3:28 am, Thomas Richter <t...@math.tu-berlin.de> wrote:
>> biject schrieb:
>>
> The problem I had with the paper and I stated it weeks ago when this
> first came up was that the paper has no competitive advantage
> statement. Nowhere does the author compare BWTS to deflate, bzip,
> lzma, in terms of ratio, memory used, speed, etc...
It doesn't need to compare to "full fledged" compression programs, but
at least there must be some analysis of the modified "bijective" bwt
with the unmodified bwt with escape symbols. That is, the same back-end
entropy coding step must be used, even if that is not any of the formats
that are in use. It doesn't matter whether the output is bzip2 compliant
or not, but it does matter to compare the two approaches.
Greetings,
Thomas
Tom St Denis
Well that too. But I was considering their entire approach as one
ensemble... bwts + ari255 + whatever ... Point is it's a neat trick,
but unless they can successfully argue it's worth knowing about it'll
just keep getting rejected from conferences.
The reality is David is on a misguided voyage of ignorance about the
merits of bijectivity in encoding/padding schemes. So that's why he
keeps pushing this stuff regardless of its merits. I was at least
hoping that if he left sci.crypt behind for a bit he'd at least focus
on the codec as a codec, e.g. performance, efficiency, etc...
Tom