Burrows–Wheeler transform: Difference between revisions
Content added Content deleted
m (→{{header|TXR}}: let* -> let) |
(Add Seed7 example) |
||
Line 2,555: | Line 2,555: | ||
^ABC| |
^ABC| |
||
--> ERROR: String can't contain STX or ETX</pre> |
--> 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}}== |
=={{header|Sidef}}== |
||
{{trans|Python}} |
{{trans|Python}} |