У меня возникают трудности с пониманием алгоритма декодирования преобразования Берроуза Уилера (BWT). Я читал в Интернете и просмотрел пример кода, но все они, похоже, используют «первичный индекс» для декодирования закодированной строки.
Мой вопрос в том, как мы можем декодировать закодированную строку BWT, такую как «rdacraaaabb», в ее исходную «абракадабру».
Некоторый пример кода был бы замечательным.
Вы хотите посмотреть на http://www.phpclasses.org/package/3559-PHP-Compress-and-decompress-data-using-BWT-and-MTF.html.
Обратная часть — самая простая часть алгоритма: создание кумулятивных гистограмм и извлечение значений на основе их ранга.
Полный блочный компрессор/декомпрессор на основе BWT можно найти здесь: http://code.google.com/p/kanzi/source/browse/java/src/kanzi/transform/BWT.java
В моем коде: абракадабра -> ardcraaaabb, key = 0
Не 'rdacraaaabb'.
http://mlich.zam.slu.cz/js-bwt/js-cryptbwt.htm
http://mlich.zam.slu.cz/js-bwt/bwt_class.txt
- но у меня медленное декодирование php
- и здесь нужно использовать косые черты для char \n \c \r для textarea
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;
}
