[ create a new paste ] login | about

Link: http://codepad.org/fOLQZk3y    [ raw code | output | fork | 1 comment ]

ninwa - PHP, pasted on Nov 12:
<?php
// PHP implementation of Burrows-Wheeler Transform
function bwt($text)
{
	$len = strlen($text);
	for($i = 0; $i < strlen($text); $i++)
	{
		if($i == 0)
			$dict[] = $text[$len-1] . substr($text, 0, $len-1);
		else
			$dict[] = $dict[$i-1][$len-1] . substr($dict[$i-1], 0, $len-1);
	}
	
	sort($dict);
	foreach ($dict as $row)
		$out .= $row[$len-1];
	
	return $out;
}

function inv_bwt($text)
{
	$len = strlen($text);
	for($i = 0; $i < $len; $i++)
	{
		for($j = 0; $j < $len; $j++)
		{
			$table[$j] = $text[$j] . $table[$j];
		}
		
		sort($table);
	}
	
	foreach($table as $row)
	{
		if( $row[$len-1] == '@' )
			return $row;
	}
}

$coded =  bwt("^BANANA@");
$decoded = inv_bwt($coded);

echo "Original string: ^BANANA@\n";
echo "String encoded: $coded \n";
echo "String decoded: $decoded \n";
?>


Output:
1
2
3
Original string: ^BANANA@
String encoded: ANNB^AA@ 
String decoded: ^BANANA@ 


Create a new paste based on this one


Comments:
posted by ninwa on Nov 12
Implementation of BWT in PHP.
reply