Anonymous user
Burrows–Wheeler transform: Difference between revisions
→{{header|Lua}}
Line 1,232:
--> ERROR: bwt.lua:6: String cannot contain STX
--></pre>
=={{header|Nim}}==
Translation of the Wikipedia Python algorithm. The program uses characters '¹' and '²' to display STX and ETX.
<lang Nim>import algorithm
from sequtils import repeat
import strutils except repeat
const
Stx = '\2'
Etx = '\3'
#---------------------------------------------------------------------------------------------------
func bwTransform*(s: string): string =
## Apply Burrows–Wheeler transform to input string.
doAssert(Stx notin s and Etx notin s, "Input string cannot contain STX and ETX characters")
let s = Stx & s & Etx # Add start and end of text marker.
# Build the table of rotated strings and sort it.
var table = newSeqOfCap[string](s.len)
for i in 0..s.high:
table.add(s[i + 1..^1] & s[0..i])
table.sort()
# Extract last column of the table.
for item in table:
result.add(item[^1])
#---------------------------------------------------------------------------------------------------
func invBwTransform*(r: string): string =
## Apply inverse Burrows–Wheeler transform.
# Build table.
var table = repeat("", r.len)
for _ in 1..r.len:
for i in 0..<r.len:
table[i] = r[i] & table[i]
table.sort()
# Find the correct row (ending in ETX).
var idx = 0
while not table[idx].endsWith(Etx):
inc idx
result = table[idx][1..^2]
#———————————————————————————————————————————————————————————————————————————————————————————————————
when isMainModule:
proc displaybleString(s: string): string =
## Build a displayable string from a string containing STX and ETX characters.
s.multiReplace(("\2", "¹"), ("\3", "²"))
for text in ["banana",
"appellee",
"dogwood",
"TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"]:
let transformed = text.bwTransform()
let invTransformed = transformed.invBwTransform()
echo ""
echo "Original text: ", text
echo "After transformation: ", transformed.displaybleString()
echo "After inverse transformation: ", invTransformed</lang>
{{out}}
<pre>
Original text: banana
After transformation: ²annb¹aa
After inverse transformation: banana
Original text: appellee
After transformation: ²e¹elplepa
After inverse transformation: appellee
Original text: dogwood
After transformation: ²do¹oodwg
After inverse transformation: dogwood
Original text: TO BE OR NOT TO BE OR WANT TO BE OR NOT?
After transformation: ²?OOORREEETTRTW BBB ATTT NNOOONOO¹
After inverse transformation: TO BE OR NOT TO BE OR WANT TO BE OR NOT?
Original text: SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
After transformation: ²STEXYDST.E.IXXIIXXSSMPPS.B..EE.¹.USFXDIIOIIIT
After inverse transformation: SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES</pre>
=={{header|Pascal}}==
| |||