Burrows–Wheeler transform: Difference between revisions
Add Seed7 example
m (→{{header|TXR}}: let* -> let) |
(Add Seed7 example) |
||
Line 2,555:
^ABC|
--> ERROR: String can't contain STX or ETX</pre>
=={{header|Seed7}}==
The example below was inspired by the [https://seed7.sourceforge.net/algorith/string.htm#burrowsWheelerTransformConcept Burrows-Wheeler transform] example from the [https://seed7.sourceforge.net/ Seed7 Homepage].
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i";
const string: START_MARKER is "\256;";
const string: END_MARKER is "\257;";
const func string: burrowsWheelerTransform (in var string: stri) is func
result
var string: encoded is "";
local
var integer: length is 0;
var integer: index is 0;
var array string: rotations is 0 times "";
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;
length := length(stri);
rotations := length times "";
for index range 1 to length do
rotations[index] := stri[index ..] & stri[.. pred(index)];
end for;
rotations := sort(rotations);
for index range 1 to length do
encoded &:= rotations[index][length];
end for;
end func;
const func string: inverseBurrowsWheelerTransform (in string: stri) is func
result
var string: decoded is "";
local
var integer: length is 0;
var integer: count is 0;
var integer: index is 0;
var array string: rotations is 0 times "";
begin
length := length(stri);
rotations := length times "";
for count range 1 to length do
for index range 1 to length do
rotations[index] := str(stri[index]) & rotations[index];
end for;
rotations := sort(rotations);
end for;
for index range 1 to length until decoded <> "" do
if endsWith(rotations[index], END_MARKER) then
decoded := rotations[index][2 .. pred(length)];
end if;
end for;
end func;
const proc: test(in string: stri) is func
local
var string: encoded is "";
var string: decoded is "";
begin
writeln;
writeln(" " <& stri);
encoded := burrowsWheelerTransform(stri);
writeln("---> " <& literal(encoded));
decoded := inverseBurrowsWheelerTransform(encoded);
writeln("---> " <& decoded);
end func;
const proc: main is func
begin
test("banana");
test("appellee");
test("dogwood");
test("TO BE OR NOT TO BE OR WANT TO BE OR NOT?");
test("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES");
end func;
</syntaxhighlight>
{{out}}
<pre>
banana
---> "bnn\256;aa\257;a"
---> banana
appellee
---> "\256;lpelepa\257;e"
---> appellee
dogwood
---> "\256;ooodwg\257;d"
---> dogwood
TO BE OR NOT TO BE OR WANT TO BE OR NOT?
---> "OOORREEETTRTW BBB ATTT NNOOONOO\256; \257;?"
---> TO BE OR NOT TO BE OR WANT TO BE OR NOT?
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
---> "TEXYDST.E.IXIXIXXSSMPPS.B..E.\256;.UESFXDIIOIIIT\257;S"
---> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
</pre>
=={{header|Sidef}}==
{{trans|Python}}
| |||