Burrows–Wheeler transform: Difference between revisions

=={{header|RPL}}==

{{works with|HP|28}}

<code>SORT</code> is defined at [[Sorting_algorithms/Bubble_sort#RPL|Sorting algorithms/Bubble sort]]

{| class="wikitable" ≪

! RPL code

! Comment

|-

|

≪

{ } SWAP 1 OVER SIZE '''FOR''' j

SWAP OVER + SWAP

DUP 2 OVER SIZE SUB SWAP 1 1 SUB +

'''NEXT''' DROP

≫ ‘<span style="color:blue">→BWtable</span>’ STO

≪

DUP <span style="color:blue">→BWtable SORT </span> → string table

≪ table string POS

"" 1 string SIZE '''FOR''' j

'''IF''' OVER j == '''THEN''' 142 CHR + '''END'''

table j GET DUP SIZE DUP SUB +

'''NEXT''' SWAP DROP

≫ ≫ '<span style="color:blue">→BWT</span>' STO

≪ DUP 142 CHR POS

'''IF''' DUP 2 < '''THEN''' ""

'''ELSE''' DUP2 1 SWAP OVER - SUB '''END'''

ROT 3 PICK 1 + OVER SIZE SUB +

≫ ‘<span style="color:blue">IdxStr</span>’ STO

≪

<span style="color:blue">IdxStr</span> → idx BWstr

≪ { } 1 BWstr SIZE '''START''' "" + '''NEXT''' '<span style="color:green">TBL</span>' STO

1 BWstr SIZE '''FOR''' j 1 BWstr SIZE '''FOR''' k

BWstr k DUP SUB

'<span style="color:green">TBL</span>' k GET + '<span style="color:green">TBL</span>' k ROT PUT

'''NEXT'''

<span style="color:green">TBL</span> <span style="color:blue">SORT</span> '<span style="color:green">TBL</span>' STO '''NEXT'''

'<span style="color:green">TBL</span>' idx GET '<span style="color:green">TBL</span>' PURGE

≫ ≫ ‘<span style="color:blue">BWT→</span>’ STO

|

<span style="color:blue">→BWtable</span> ''( "string" → { "string" "trings" ... "gstrin" )''

initialize stack and loop n=len(string) times

add string to table

string = string[2..n]+string[1}

clean stack

<span style="color:blue">→BWT</span> ''( "string" → "transformed" )''

store input string and table to speed up execution

get position of string in table

loop to create transformed string:

if table[j]=string then add index to output string

add last character of table[j]

clean stack

<span style="color:blue">IdxStr</span> ''( "str←ing" → index "string" )''

if ← not at string beginning

get chars before

get chars after and concatenate

<span style="color:blue">→BWT</span> ''( "str←ing" → "transformed" )''

get index and store

initialize table as a global variable

loop len(string) times

add kth char of string

to kth table item

sort table

clean RAM

return appropriate string

|}

"banana" <span style="color:blue">→BWT</span>

DUP <span style="color:blue">BWT→</span>

Transforming "banana" takes 1.5 seconds on a basic HP-28S, but almost 15 for the inverse transform.

The wikipedia example ("SIX MIXED...BOXES") takes resp. 41 seconds to transform and... 47 minutes to inverse.

{{out}}

<pre>

2: "nnb←aaa"

1: "banana"

</pre>