Hi Eric, 13-Jul-2000 you wrote:
>The problem is in your sort-func all the return values are true. I think
>this'll give better results:
[...]
In fact, this _doesn't_ work. Just checked.
Have a look at the attached function (yes, 'input is redefined inside the
function, but since it isn't used there, it doesn't matter ;-) ). Just before
the first "print permutations" I do a sort/compare. The output here is not
what I expect.
Then I do a simple bubble-sort on the list, using the comparison function
exactly as I would expect sort/compare uses it (that is, I don't suspect that
sort uses bubble-sort, of course). Then the result is as expected.
In fact, according to the REBOL User's Guide, the comparison function should
return false when the two input values are equal. I've tried changing this
too, but it doesn't change the validity of the output of sort/compare.
Very strange.
BTW, if anybody has ideas on how to make the attached function smaller (but
still readable) or faster, I'd be very interested to know.
BTW2, JFYI: The function takes a normal text string, applies a transformation
on that text string, and returns the transformed string and a number. Using
the transformed string and the number, another function can recover the
original string. The transformed string will very likely consist of more
homogenous substrings than the original, thus making it a lot easier to
compress using more traditional approaches.
Kind regards,
--
Ole Friis <[EMAIL PROTECTED]>
Amiga is a trademark of Amiga Inc.
; Burrows-Wheeler transform
encode-bw: func [input] [
use [input-length sort-func permutations transformed-string
transformed-info] [
input-length: length? input
; Orders the n1'th and the n2'th permutations of the input
sort-func: func [n1 n2] [
loop input-length [
if n1 > input-length [n1: 1]
if n2 > input-length [n2: 1]
c1: pick input n1
c2: pick input n2
if c1 < c2 [return true]
if c1 > c2 [return false]
n1: n1 + 1
n2: n2 + 1
]
return true
]
; Build a representation of the permutations
permutations: make block! input-length
for i 1 input-length 1 [append permutations i]
; Sort the permutations in lexicographic order
sort/compare permutations :sort-func
print permutations
; A little bubble-sort :-(
sorted: no
while [sorted = no] [
sorted: yes
for i 2 input-length 1 [
if (sort-func pick permutations i - 1 pick permutations i) = false [
temp1: pick permutations i - 1
temp2: pick permutations i
poke permutations i - 1 temp2
poke permutations i temp1
sorted: no
]
]
]
print permutations
; Now, let's create the new string
transformed-string: make string! input-length
transformed-info: (index? find permutations 1)
foreach permutation permutations [
i: either permutation = 1 [input-length] [permutation - 1]
append transformed-string pick input i
]
return reduce [transformed-string transformed-info]
]
]
