Burrows Wheeler Transform (BWT)

Question

Burrows Wheeler transform (BWT.)에 대한 디코딩 알고리즘을 파악하는 데 어려움을 겪고 있습니다. 온라인으로 읽었으며 샘플 코드를 살펴 보았지만 모두 ' 인코딩 된 문자열을 디코딩하는 '기본 인덱스'.

제 질문은 'rdacraaaabb'와 같은 BWT 인코딩 문자열을 어떻게 원래의 'abracadabra'로 디코딩 할 수 있는가입니다.

일부 샘플 코드는 훌륭합니다.

Answer 1

http://www.phpclasses.org/package/3559-PHP-Compress-and-decompress-data-using-BWT-and-MTF.html을보고 싶습니다.

Answer 2

역 부분은 누적 히스토그램을 만들고 순위에 따라 값을 검색하는 알고리즘의 가장 쉬운 부분입니다. > ardcraaaabb,
되지 않음 'rdacraaaabb'0 = 키 - 아브라카 다 브라 : 내 코드에서 http://code.google.com/p/kanzi/source/browse/java/src/kanzi/transform/BWT.java

Answer 3

:

당신은 여기 BWT에 따라 완전한 블록 압축/압축 해제를 찾을 수 있습니다.

http://mlich.zam.slu.cz/js-bwt/js-cryptbwt.htm
http://mlich.zam.slu.cz/js-bwt/bwt_class.txt
-하지만 내 PHP는 디코드
느린 - 여기가해야 우데는

function bwtDeCode(&$data) 
    { 
    arr = array(); 
    $arr[0] = array(); 
    $arr[1] = array(); 
    $arr[2] = array(); 
    $len = strlen($data['out']); // !!! input source data (string) 
    for ($i=0;$i<$len;$i++) 
     { 
     $arr[2][$i] = $i;  //index row 
     $arr[1][$i] = $data['out'][$i]; //last col 
     $arr[0][$i] = $data['out'][$i]; //first col 
     } 
    usort($arr[0],array($this,'sortCmpDeCode')); //first col 
    // sort($arr[0]); //first col 
    $none = -1; 
    $i = $data['key'] * 1; // !!! input source key (number) 
    $key = $arr[1][$i]; 
    $out = $key; 
    $arr[2][$i] = $none; 
    for ($j=1;$j<$len;$j++) 
     { 
     for ($i=0;$i<$len;$i++) 
    //  foreach ($arr[0] as $i=>$value) 
      { 
      if ($arr[2][$i]===$none || $arr[0][$i]!==$key) 
    //    if ($arr[0][$i]!==$key) 
       {continue;} 
       $key = $arr[1][$i]; 
    //   $out = $key . $out; 
      $out .= $key; 
      $arr[2][$i] = $none; 
    //unset($arr[1][$i]); 
      break; 
      } 
     } 
    $out = strrev($out); 
    $data['in'] = $out; 
    }