147 lines
21 KiB
Text
147 lines
21 KiB
Text
(phixonline)-->
|
|
<span style="color: #000080;font-style:italic;">-- demo\rosetta\burrows_wheeler.exw
|
|
--/*
|
|
The traditional method:
|
|
|
|
7 banana$ $banana 6
|
|
6 $banana ===> a$banan 5
|
|
5 a$banan ana$ban 3
|
|
4 na$bana sort anana$b 1
|
|
3 ana$ban banana$ 7
|
|
2 nana$ba ===> na$bana 4
|
|
1 anana$b nana$ba 2
|
|
^ desired answer == "annb$aa"
|
|
|
|
First ignore the numbers: the desired answer is found by creating a table of all
|
|
rotations of "banana$", sorting it, and then extracting the right-hand column.
|
|
|
|
However, there is no need to actually create such a table, which could be very
|
|
expensive for long strings, instead just number them logically (admittedly that
|
|
was somewhat arbitrarily chosen to get the indexes to work out nicely, I picked
|
|
the original index of the last character), and perform a custom sort on those.
|
|
|
|
The latter effectively just recreates the rotations one character at a time until
|
|
there is a mismatch (which there always will be since there is only one $).
|
|
The left hand column is my arbitrary numbering scheme and the right hand column
|
|
is those sorted into order, which is also the indexes to the original string of
|
|
the characters that we want.
|
|
|
|
The code below uses $ as the terminator, but eg 1 (== '\#01') should be fine,
|
|
except of course for the display of that on a console.
|
|
--*/</span>
|
|
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
|
|
<span style="color: #008080;">constant</span> <span style="color: #000000;">terminator</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'$'</span>
|
|
|
|
<span style="color: #008080;">function</span> <span style="color: #000000;">rot_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000080;font-style:italic;">-- i,j are indexes of the last character, so bump before first compare.
|
|
-- eg/ie rot_sort(i,j,s) should yield compare(rotate(s,i),rotate(s,j)),
|
|
-- as in rot_sort(7,6,"banana$") == compare("banana$","$banana")
|
|
-- - but one character at a time rather than constructing both.</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
|
|
<span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">c</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
|
|
|
|
<span style="color: #008080;">function</span> <span style="color: #000000;">burrows_wheeler_transform</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">terminator</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008000;">"error"</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">terminator</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #004080;">sequence</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">custom_sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">routine_id</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"rot_sort"</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">),{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">})</span>
|
|
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
|
|
|
|
<span style="color: #000080;font-style:italic;">--/*
|
|
Inversion. The traditional method is add column and sort, seven times,
|
|
to reconstruct the table above, then pick the entry that ends with the
|
|
marker. Showing that technique in full detail here is not helpful, and
|
|
like above that would be hideously inefficient for large strings.
|
|
|
|
$banana 1 $ (1 ) a 2
|
|
a$banan 2 a ( 1) n 6
|
|
ana$ban 3 a ( 2) n 7
|
|
anana$b 4 a ( 3) b 5
|
|
banana$ 5 b $ 1
|
|
na$bana 6 n (2 ) a 3
|
|
nana$ba 7 n (3 ) a 4
|
|
^ ^ ^ ^ ^
|
|
f l f l t
|
|
|
|
However, we already have the last column, and the first is just that
|
|
sorted alphabetically, and with just those two, we have all possible
|
|
character pairings of the original message. The trick is in figuring
|
|
out how to stitch them together in the right order. If you carefully
|
|
study the three that end in a, and the three that start in a, notice
|
|
the $banan,na$ban,nana$b parts are sorted in the same order, whether
|
|
they are prefixed with a or not. That is, the middle (parenthesised)
|
|
matching numbers are both 123, not 123 and say 231. It is quite hard
|
|
to see that being useful, but eventually the penny should drop. The
|
|
right-hand 1 with an a rotated right gives the left-hand 1, and the
|
|
same goes for 2 and 3: they are in fact links to the prior pairing.
|
|
|
|
In other words the first a in l always corresponds to the first in f,
|
|
the second to the second, and so on, and that (amazingly) forms the
|
|
order in which the pairings need to be daisy-chained together.
|
|
|
|
Try following (1->)2a->6n->3a->7n->4a->5b->$, == reverse("banana"),
|
|
in the above f and t tables.
|
|
|
|
The code below builds a queue of 'a' ({1,6,7}, built backwards) then
|
|
we pop {2,3,4} into those slots in t as we find 'a' in f, likewise
|
|
for all other letters, forming the links for each pairing as shown.
|
|
See the trivial step 3 scan below, then go back and stare at f and
|
|
t as shown above, and once again, eventually the penny should drop.
|
|
I will admit I had to read ten or so explanations before I got it.
|
|
--*/</span>
|
|
|
|
<span style="color: #008080;">function</span> <span style="color: #000000;">inverse_burrows_wheeler</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'\0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- (doable, but needs some +1s)</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">c</span>
|
|
<span style="color: #004080;">string</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #004080;">sequence</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">256</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- queue heads (per char)</span>
|
|
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- queue links</span>
|
|
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- reformed/pairing links
|
|
-- Step 1. discover/build queues (backwards)</span>
|
|
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
|
|
<span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span>
|
|
<span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
<span style="color: #000080;font-style:italic;">-- Step 2. reform/pop char queues into pairing links</span>
|
|
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
|
|
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
|
|
<span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]]</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
<span style="color: #000080;font-style:italic;">-- Step 3. rebuild (backwards)</span>
|
|
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">terminator</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008000;">"error"</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- (first time in, skip the end marker)</span>
|
|
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
|
|
|
|
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">src</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #004080;">string</span> <span style="color: #000000;">enc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">burrows_wheeler_transform</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">),</span>
|
|
<span style="color: #000000;">dec</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inverse_burrows_wheeler</span><span style="color: #0000FF;">(</span><span style="color: #000000;">enc</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000000;">src</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"characters"</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000000;">enc</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">enc</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"characters"</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000000;">dec</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dec</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"characters"</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"original: %s --> %s\n inverse: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span><span style="color: #000000;">enc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dec</span><span style="color: #0000FF;">})</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
|
|
|
|
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"banana"</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"dogwood"</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"TO BE OR NOT TO BE OR WANT TO BE OR NOT?"</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"</span><span style="color: #0000FF;">)</span>
|
|
<!--
|