Anonymous user
Burrows–Wheeler transform: Difference between revisions
→{{header|zkl}}: added code
m (→{{header|Sidef}}: added zkl header) |
(→{{header|zkl}}: added code) |
||
Line 72:
=={{header|zkl}}==
<lang zkl>
fcn init(chr="$"){ var special=chr; }
<lang zkl></lang>▼
fcn encode(str){
_assert_(not str.holds(special), "String cannot contain char \"%s\"".fmt(special) );
str=str.append(special);
str.len().pump(List,'wrap(n){ String(str[n,*],str[0,n]) }).sort()
.pump(String,T("get",-1)); // last char of each "permutation"
}
fcn decode(str){
table:=List.createLong(str.len(),""); // ("",""..), mutable
do(str.len()){
foreach n in (str.len()){ table[n]=str[n] + table[n] }
table.sort();
} // --> ("$dogwood","d$dogwoo","dogwood$",...)
table.filter1("%s*".fmt(special).glob)[1,*]; // str[0]==$, often first element
}
<lang zkl>BWT:=BurrowsWheelerTransform();
//BWT.encode("$"); // --> assert(bbb.zkl:25): String cannot contain char "$"
tests:=T(
"banana", "appellee", "dogwood", "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",);
foreach test in (tests){
enc:=BWT.encode(test);
println("%s --> %s --> %s".fmt(test,enc,BWT.decode(enc)));
}</lang>
{{out}}
<pre>
banana --> annb$aa --> banana
appellee --> e$elplepa --> appellee
dogwood --> do$oodwg --> dogwood
TO BE OR NOT TO BE OR WANT TO BE OR NOT?
--> OOORREEETTR?TW BBB ATTT NNOOONOO$
--> TO BE OR NOT TO BE OR WANT TO BE OR NOT?
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
--> STEXYDST.E.IXXIIXXSSMPPS.B..EE.$.USFXDIIOIIIT
--> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
</pre>
| |||