Burrows Wheeler Transform (BWT)

Question

У меня возникают трудности с пониманием алгоритма декодирования для преобразования Берроуза Уилера (BWT). Я закончил читать онлайн и просмотрел некоторый пример кода, но все они, кажется, используют «первичный индекс» для декодированиязакодированная строка.

Мой вопрос заключается в том, как мы можем декодировать закодированную строку BWT, например 'rdacraaaabb', в ее исходную 'abracadabra'.

Некоторый пример кода был бы замечательным.

Answer 1

Обратная часть - это самая простая часть алгоритма: создавать кумулятивные гистограммы и извлекать значения на основе их ранга.

Здесь вы можете найти полный блок сжатия / декомпрессора на основе BWT: http://code.google.com/p/kanzi/source/browse/java/src/kanzi/transform/BWT.java

Answer 2

В моем коде: abracadabra -> ardcraaaabb, ключ = 0
Не 'rdacraaaabb'.

http://mlich.zam.slu.cz/js-bwt/js-cryptbwt.htm
http://mlich.zam.slu.cz/js-bwt/bwt_class.txt
- но мой php-декодер медленный
- и здесь необходимо использовать слэш для символа \ n \ c \ r для текстовой области

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;
    }

Answer 3

Вы хотите посмотреть на http://www.phpclasses.org/package/3559-PHP-Compress-and-decompress-data-using-BWT-and-MTF.html.