Burrows–Wheeler transform: Difference between revisions
Content added Content deleted
(Add Seed7 example) |
(Improve Seed7 example) |
||
Line 2,559: | Line 2,559: | ||
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const string: |
const func string: burrowsWheelerTransform (in string: stri) is func |
||
const string: END_MARKER is "\257;"; |
|||
const func string: burrowsWheelerTransform (in var string: stri) is func |
|||
result |
result |
||
var string: encoded is ""; |
var string: encoded is ""; |
||
Line 2,570: | Line 2,567: | ||
var array string: rotations is 0 times ""; |
var array string: rotations is 0 times ""; |
||
begin |
begin |
||
⚫ | |||
if pos(stri, START_MARKER) <> 0 or pos(stri, END_MARKER) <> 0 then |
|||
raise RANGE_ERROR; # Input string cannot contain START_MARKER and END_MARKER characters. |
|||
end if; |
|||
stri := START_MARKER & stri & END_MARKER; |
|||
⚫ | |||
rotations := length times ""; |
rotations := length times ""; |
||
for index range 1 to length do |
for index range 1 to length do |
||
rotations[index] := stri[index ..] & stri[.. pred(index)]; |
rotations[index] := stri[index ..] & "\256;" & stri[.. pred(index)]; |
||
end for; |
end for; |
||
rotations := sort(rotations); |
rotations := sort(rotations); |
||
Line 2,602: | Line 2,595: | ||
rotations := sort(rotations); |
rotations := sort(rotations); |
||
end for; |
end for; |
||
decoded := rotations[1]; |
|||
for index range 1 to length until decoded <> "" do |
|||
index := pos(decoded, "\256;"); |
|||
if endsWith(rotations[index], END_MARKER) then |
|||
decoded := decoded[succ(index) ..] & decoded[.. pred(index)]; |
|||
end if; |
|||
end for; |
|||
end func; |
end func; |
||
Line 2,629: | Line 2,620: | ||
test("TO BE OR NOT TO BE OR WANT TO BE OR NOT?"); |
test("TO BE OR NOT TO BE OR WANT TO BE OR NOT?"); |
||
test("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"); |
test("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"); |
||
end func; |
end func;</syntaxhighlight> |
||
</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,654: | Line 2,644: | ||
---> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES |
---> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES |
||
</pre> |
</pre> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Python}} |
{{trans|Python}} |