Page 2 of 3 <123>
Topic Options
#97343 - 2002-12-29 11:47 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
MightyR1 Offline
MM club member
*****

Registered: 1999-09-09
Posts: 1264
Loc: The Netherlands
Bugs / Features reported:

http://www.kixtart.org/cgi-bin/ultimatebb.cgi?ubb=get_topic&f=3&t=000368
_________________________
Greetz,
Patrick Rutten

- We'll either find a way or make one...
- Knowledge is power; knowing how to find it is more powerful...
- Problems don't exist; they are challenges...

Top
#97344 - 2002-12-30 12:09 AM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
MightyR1 Offline
MM club member
*****

Registered: 1999-09-09
Posts: 1264
Loc: The Netherlands
To make the winning code more understandable:
code:
Function BWTDecode($sEncoded, $iOffset)

;Declare the variables
Dim $iStringCounter,$iCounter,$sTransformVector

;Loop for each possible ANSI character
For $iCounter=1 to 255

;Loop for each encoded character
For $iStringCounter=1 to Len($sEncoded)

;If current ANSI = current encoded then
;write down the position of the char (in encoded)
;This way the Transformation vector is determined
If $iCounter=ASC(SubStr($sEncoded,$iStringCounter))

;Use a space as a delimiter
$sTransformVector=$sTransformVector+" "+$iStringCounter

EndIf
Next
Next

;Raise the offset by one; substr starts with 1 and not 0 (array index)
$iOffset=$iOffset+1

;Loop to decode the encoded string
For $iCounter=2 to $iStringCounter

;The output = the encoded string decoded using the offsets
;in the Transformation vector
$BWTDecode=$BWTDecode+SubStr($sEncoded,$iOffset,1)

;Determine next offset
$iOffset=Split($sTransformVector)[$iOffset]
Next
EndFunction

{edit - PM from Howard:
quote:
Nice work documenting the code. You may also want to add that the TransformVector is also zero based like an ARRAY, but when we move to the string "one" base we need to increment the initial offset only. The TransformVector is already artificially high by one because of the initial space in $sTransformVector.

}

[ 01. January 2003, 13:22: Message edited by: MightyR1 ]
_________________________
Greetz,
Patrick Rutten

- We'll either find a way or make one...
- Knowledge is power; knowing how to find it is more powerful...
- Problems don't exist; they are challenges...

Top
#97345 - 2002-12-31 06:17 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
ok, as I came late here, I must wonder what is the code for 191?
_________________________
!

download KiXnet

Top
#97346 - 2002-12-31 06:42 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Howard Bullock Offline
KiX Supporter
*****

Registered: 2000-09-15
Posts: 5809
Loc: Harrisburg, PA USA
There is an apparent bug/feature in the ASC() function that allows it to return the ascii value of only the first character of a multi-character string. Because of this, ASC(substr($a,$b,1)) can be written as ASC(substr($a,$b)) saving 2 strokes.
_________________________
Home page: http://www.kixhelp.com/hb/

Top
#97347 - 2002-12-31 06:44 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
and this is not allowed?
_________________________
!

download KiXnet

Top
#97348 - 2002-12-31 07:46 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Shawn Administrator Offline
Administrator
*****

Registered: 1999-08-13
Posts: 8611
imho the ASC thing should stay as a feature ? after all when you really think about it the ASC value of a string can only be the value of the first character anyways ... so why not just leave as is - no harm done ? kinda like converting a string to numeric, it would only read the leading digits of the a string, fe:

? VAL("123ABC")

123

[ 31. December 2002, 19:50: Message edited by: Shawn ]

Top
#97349 - 2002-12-31 08:20 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Howard Bullock Offline
KiX Supporter
*****

Registered: 2000-09-15
Posts: 5809
Loc: Harrisburg, PA USA
MightyR1 claimed that score above by removing the ",1".
_________________________
Home page: http://www.kixhelp.com/hb/

Top
#97350 - 2002-12-31 08:42 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
his code was kinda more to change... how much I have time?
_________________________
!

download KiXnet

Top
#97351 - 2002-12-31 08:47 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Shawn Administrator Offline
Administrator
*****

Registered: 1999-08-13
Posts: 8611
Jooel ... think maybe the only way to improve on Howards score there is to come up with some radical new way to sort or parse the string ... a whole new shorter algorithm ... but like you say, the code is pretty tight.
Top
#97352 - 2002-12-31 08:56 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
daddy, I think I may have chance.
probably hoby is all the time generating all the possible ways to reduce it, but with pure luck it sometimes is possible.

and it will be scanned.

anyway, his code is so clean, I could even print it out in red color on A2 paper and put on me wall!
_________________________
!

download KiXnet

Top
#97353 - 2003-01-01 01:29 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
MightyR1 Offline
MM club member
*****

Registered: 1999-09-09
Posts: 1264
Loc: The Netherlands
Jooel,

How about your approach?? Can we see it??

Noticed that Howard and I are somehow using telepathy?? Our codes are a like... [Wink]
_________________________
Greetz,
Patrick Rutten

- We'll either find a way or make one...
- Knowledge is power; knowing how to find it is more powerful...
- Problems don't exist; they are challenges...

Top
#97354 - 2003-01-01 06:25 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Shawn Administrator Offline
Administrator
*****

Registered: 1999-08-13
Posts: 8611
Just wanted to congratulate and thank Jens for a great choice for Kixgolf this round, and a well done checker, etc ... this Burrows-Wheeler algorithm was a great choice because from what I can see, theres about a half dozen different algorithms and approaches to use. Plus speaking for myself - it really held my interest over the entire contest period ... must have changed my approach three or four times in the course of play ... I think that most of the other players did as well ... great one to be sure !
Top
#97355 - 2003-01-01 06:35 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Howard Bullock Offline
KiX Supporter
*****

Registered: 2000-09-15
Posts: 5809
Loc: Harrisburg, PA USA
I agree with Shawn. Thanks Jens for a well put together package. You probably spent more time and energy on providing the challenge than we we did on solving it.

I have to admit that I probably would not spent the time setting one of these up, but I really enjoy participating. Thanks again.

[ 01. January 2003, 18:35: Message edited by: Howard Bullock ]
_________________________
Home page: http://www.kixhelp.com/hb/

Top
#97356 - 2003-01-01 10:07 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
MightyR1 Offline
MM club member
*****

Registered: 1999-09-09
Posts: 1264
Loc: The Netherlands
Agreed,

was even dreaming of BWT... Dreamt of new approach, went out of bed and started scribbling the idea on paper... Talk about Golf addiction [Wink]

Therefore thnx Jens!!!

[ 01. January 2003, 22:38: Message edited by: MightyR1 ]
_________________________
Greetz,
Patrick Rutten

- We'll either find a way or make one...
- Knowledge is power; knowing how to find it is more powerful...
- Problems don't exist; they are challenges...

Top
#97357 - 2003-01-02 02:45 AM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11165
Loc: Boston, MA, USA
I think that most of the kudos should go to the PerlGolf people who just ran the same contest. See http://perlgolf.sourceforge.net/ under TPR(0,6). Their best code used about 50 characters.

I still hope to get the extended stats working by the end of the week, haven't found any time to work on it. This might make the next challenges a little bit more interesting if you e.g. ahve to consider memory usage, too, or execution speed. Total score would then be some kind of weighted average.
_________________________
There are two types of vessels, submarines and targets.

Top
#97358 - 2003-01-02 02:51 AM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
sure it was short...
I could think we getting of to 100 with removing sorting...

then the function tags.
they don't use those....
_________________________
!

download KiXnet

Top
#97359 - 2003-01-02 03:02 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
BrianTX Offline
Korg Regular

Registered: 2002-04-01
Posts: 895
I hate to bring this up, but in this particular function (BWT), it should be understood that in practical applications speed is of MUCH greater priority the priority than file size. Supposing someone decides to code a new compression/decompression utility with C++... it would be much more important that it be FAST!

Brian

Top
#97360 - 2003-01-02 03:12 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Howard Bullock Offline
KiX Supporter
*****

Registered: 2000-09-15
Posts: 5809
Loc: Harrisburg, PA USA
Yes, but the target for this challenge was small code. [Wink]

We got some good speed as well, compared with my first code that ran for 90+ hours before being killed. [Smile]

[ 02. January 2003, 15:14: Message edited by: Howard Bullock ]
_________________________
Home page: http://www.kixhelp.com/hb/

Top
#97361 - 2003-01-02 03:24 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
well, for compression, speed is not important.
when it comes to on-the-fly compression, like mpeg speed becomes a factor.

but for storage thingies, the speed has no meaning.

my quess.
_________________________
!

download KiXnet

Top
#97362 - 2003-01-02 03:29 PM Re: KiXGolf: Part 2: The Code: Burrows-Wheeler Transform
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11165
Loc: Boston, MA, USA
If you really want to develop this into a compression/decompression routine then you would have to add a run-length-encoder before and after the Burrows-Wheeler-encoder to achieve more effective compression.
_________________________
There are two types of vessels, submarines and targets.

Top
Page 2 of 3 <123>


Moderator:  Arend_, Allen, Jochen, Radimus, Glenn Barnas, ShaneEP, Ruud van Velsen, Mart 
Hop to:
Shout Box

Who's Online
0 registered and 657 anonymous users online.
Newest Members
M_Moore, BeeEm, min_seow, Audio, Hoschi
17883 Registered Users

Generated in 0.1 seconds in which 0.067 seconds were spent on a total of 13 queries. Zlib compression enabled.

Search the board with:
superb Board Search
or try with google:
Google
Web kixtart.org