28 lines
1.1 KiB
Text
28 lines
1.1 KiB
Text
F bwt(String =s)
|
||
‘Apply Burrows-Wheeler transform to input string.’
|
||
assert("\002" !C s & "\003" !C s, ‘Input string cannot contain STX and ETX characters’)
|
||
s = "\002"s"\003"
|
||
V table = sorted((0 .< s.len).map(i -> @s[i..]‘’@s[0 .< i]))
|
||
V last_column = table.map(row -> row[(len)-1..])
|
||
R last_column.join(‘’)
|
||
|
||
F ibwt(String r)
|
||
‘Apply inverse Burrows-Wheeler transform.’
|
||
V table = [‘’] * r.len
|
||
L 0 .< r.len
|
||
table = sorted((0 .< r.len).map(i -> @r[i]‘’@table[i]))
|
||
V s = table.filter(row -> row.ends_with("\003"))[0]
|
||
R s.rtrim("\003").trim("\002")
|
||
|
||
L(text) [‘banana’,
|
||
‘appellee’,
|
||
‘dogwood’,
|
||
‘TO BE OR NOT TO BE OR WANT TO BE OR NOT?’,
|
||
‘SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES’]
|
||
V transformed = bwt(text)
|
||
V invTransformed = ibwt(transformed)
|
||
|
||
print(‘Original text: ’text)
|
||
print(‘After transformation: ’transformed.replace("\2", ‘^’).replace("\3", ‘|’))
|
||
print(‘After inverse transformation: ’invTransformed)
|
||
print()
|