==================================================
 Burrows Wheeler Transform (BWT)
==================================================
Michael Burrows と David J. Wheeler によって考えられた可逆変換の一種．

素朴な方法
~~~~~~~~~~~~~~~~~~~~~~~~~
入力文字列を循環させた文字列から成る表を考える．

例）： :math:`S=banana`

   ======= == == == == == == 
   i       0  1  2  3  4  5  
   ======= == == == == == == 
   0    　  b  a  n  a  n  a  
   ------- -- -- -- -- -- --
   1    　  a  n  a  n  a  b 
   ------- -- -- -- -- -- --
   2    　  n  a  n  a  b  a
   ------- -- -- -- -- -- --
   3    　  a  n  a  b  a  n
   ------- -- -- -- -- -- --
   4    　  n  a  b  a  n  a
   ------- -- -- -- -- -- --
   5    　  a  b  a  n  a  n  
   ======= == == == == == == 

:math:`S` を巡回させた文字列から成る表を辞書順にソート

   ======= == == == == == == 
   i       0  1  2  3  4  5  
   ======= == == == == == == 
   0    　  a  b  a  n  a  n  
   ------- -- -- -- -- -- --
   1    　  a  n  a  b  a  n　
   ------- -- -- -- -- -- --
   2    　  a  n  a  n  a  b 
   ------- -- -- -- -- -- --
   3    　  b  a  n  a  n  a  
   ------- -- -- -- -- -- --
   4    　  n  a  b  a  n  a
   ------- -- -- -- -- -- --
   5    　  n  a  n  a  b  a
   ======= == == == == == ==    

この表の :math:`i=n` 番目( :math:`n=|S|` )の文字をつなげたものが
BWTを行った文字列":math:`nnbaaa`"となる．  
  
接尾辞配列を用いる方法
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. literalinclude:: /Scripts/Python/BWT.py
   :pyobject: BWT

	

入力を変換
---------------------------------------
元のテキストとBWTを行ったテキストの圧縮率の違いを比較
 
.. raw:: html
        
		 
		<script type="text/javascript"  src="../../_static/BWT.js"></script>
		
		<form onsubmit="return false;" autocomplete="off">
        <div>
           text = <input id="text" type="text" size="64" value="a"/>
 		</div>
 		</form>
 		<div style="word-wrap:break-word;"> ・元テキスト = <before>dummy</before>  </div>
 		<div style="word-wrap:break-word;"> ・圧縮テキスト = <after>dummy</after>   </div>
 		<div style="word-wrap:break-word;"> ・圧縮率 = <ratio>dummy</ratio> </div>
		<BR>
		<div style="word-wrap:break-word;"> ・BWTテキスト = <BWTstring>dummy</BWTstring>  </div>
 		<div style="word-wrap:break-word;"> ・圧縮テキスト = <BWTafter>dummy</BWTafter>   </div>
 		<div style="word-wrap:break-word;"> ・圧縮率 = <BWTratio>dummy</BWTratio> </div>
		
		
参考文献
---------------------------------------
.. raw:: html

	M. Burrows, D.J. Wheeler, A block sorting data compression algorithm, Technical Report, DIGITAL System Research Center,1994
	<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.6177" target="_blank">link</a>

.. M. Burrows, D.J. Wheeler, A block sorting data compression algorithm, Technical Report, DIGITAL System Research Center,1994　- `link <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.6177>`_