@ 2014-10-18T23:24:43Z <?
// A simple implementation of lossless compression and decompression using
// Huffman coding.
$asciiMap = array();
$symbolMap = array();
define('SYMBOL_SIZE', 8);
for ($i = 0; $i < 256; ++$i) {
$binary = decbin($i);
while (strlen($binary) < SYMBOL_SIZE)
$binary = "0$binary";
$asciiMap[chr($i)] = array_map(function($i) {
return (int)$i;
}, str_split($binary));
$symbolMap[$binary] = chr($i);
}
class Node {
public $left;
public $right;
public $parent;
public $symbol;
public $weight;
function __construct($symbol, $weight) {
$this->left = null;
$this->right = null;
$this->parent = null;
$this->symbol = $symbol;
$this->weight = $weight;
}
function __toString() {
return "Node ($this->symbol)";
}
function priority() {
return -$this->weight;
}
function dump($tabs) {
$prefix = "";
for ($i = 0; $i < $tabs; ++$i)
$prefix .= " ";
print($prefix . "(" . $this->symbol . ", " . $this->weight . ")\n");
}
}
class Tree {
public $root;
public $leaves;
function __construct() {
$this->root = null;
$this->leaves = array();
}
function dump() {
if (!$this->root) {
print("empty");
return;
}
$tabs = 0;
$q = array();
array_push($q, array($this->root, false));
while (count($q)) {
$next = array_pop($q);
if ($next[1]) {
$tabs -= 1;
continue;
}
$node = $next[0];
$node->dump($tabs);
$tabs++;
array_push($q, array($node, true));
if ($node->right)
array_push($q, array($node->right, false));
if ($node->left)
array_push($q, array($node->left, false));
}
}
}
class PriorityQueue {
public $heap;
private $size;
function __construct() {
$this->heap = array();
$this->size = 0;
}
function size() {
return $this->size;
}
function enqueue($e) {
$this->heap[$this->size++] = $e;
$this->bubbleUp();
}
function bubbleUp() {
$currentLocation = $this->size - 1;
while ($currentLocation > 0) {
$parentLocation = $currentLocation >> 1;
$currentNode = $this->heap[$currentLocation];
$parentNode = $this->heap[$parentLocation];
if ($currentNode->priority() <= $parentNode->priority())
break;
$this->heap[$parentLocation] = $currentNode;
$this->heap[$currentLocation] = $parentNode;
$currentLocation = $parentLocation;
}
}
function dequeue() {
if ($this->size() == 0)
return null;
$result = $this->heap[0];
$this->heap[0] = null;
$this->filterDown();
$this->size--;
return $result;
}
function filterDown() {
if (!$this->size)
return;
$holeLocation = 0;
$last = $this->heap[$this->size - 1];
while (true) {
$child1Location = 2 * $holeLocation + 1;
$child2Location = 2 * $holeLocation + 2;
$child1 = null;
$child2 = null;
if ($child1Location < $this->size)
$child1 = $this->heap[$child1Location];
if ($child2Location < $this->size)
$child2 = $this->heap[$child2Location];
if (($child1
&& $child2
&& $child1->priority() > $child2->priority())
|| ($child1 && !$child2)) {
$this->heap[$holeLocation] = $child1;
$this->heap[$child1Location] = null;
$holeLocation = $child1Location;
} else if ($child2) {
$this->heap[$holeLocation] = $child2;
$this->heap[$child2Location] = null;
$holeLocation = $child2Location;
} else {
break;
}
}
// We filtered down to the last element, so we don't need to do
// anything else.
if ($holeLocation == $this->size - 1)
return;
// We need to fill in the hole that we created in the middle of the
// final level.
$this->heap[$holeLocation] = $last;
$this->heap[$this->size - 1] = null;
}
}
class Huffman {
public static function buildTree($s)
{
$t = new Tree();
$seenSymbols = array();
$pq = new PriorityQueue();
// Add leaf nodes for each symbol to the priority queue.
for ($i = 0; $i < strlen($s); ++$i) {
$c = $s[$i];
if (array_key_exists($c, $seenSymbols))
continue;
$occurrences = 0;
for ($j = $i; $j < strlen($s); ++$j) {
if ($s[$j] != $c)
continue;
$occurrences++;
}
$node = new Node($c, $occurrences);
$pq->enqueue($node);
$t->leaves[$c] = $node;
$seenSymbols[$c] = true;
}
if ($pq->size() == 0)
return $t;
// While there is more than one node left in the priority queue:
while ($pq->size() > 1) {
// Remove the two nodes of highest priority (lowest probability).
$node1 = $pq->dequeue();
$node2 = $pq->dequeue();
// Create a new internal node with the two nodes as children with
// p_total = p_1 + p_2
$newNode = new Node(null, $node1->weight + $node2->weight);
$newNode->left = $node1;
$newNode->right = $node2;
$node1->parent = $newNode;
$node2->parent = $newNode;
// Add the new node to the queue.
$pq->enqueue($newNode);
}
// The final node in the priority queue is the root.
$t->root = $pq->dequeue();
return $t;
}
private static function encodeTree($t)
{
global $asciiMap;
// Emit how big each leaf symbol is.
// Emit a 0 for an internal node and a 1 for each leaf.
$treeBits = array();
$q = array();
array_push($q, $t->root);
while (count($q)) {
$next = array_pop($q);
if ($next->left && $next->right) {
array_push($treeBits, 0);
// Visit the left side first, so push the right side before
// the left.
array_push($q, $next->right);
array_push($q, $next->left);
} else {
if ($next->left || $next->right)
throw new Exception("Leaf nodes do not have children.");
array_push($treeBits, 1);
$symbolBits = $asciiMap[$next->symbol];
for ($i = 0; $i < count($symbolBits); ++$i) {
array_push($treeBits, $symbolBits[$i]);
}
}
}
return $treeBits;
}
public static function encode($s, $t)
{
if (!$t->root)
return;
// Encode the tree first.
$allBits = Huffman::encodeTree($t);
for ($i = 0; $i < strlen($s); ++$i) {
$c = $s[$i];
$current = $t->leaves[$c];
$bits = array();
while (true) {
$parent = $current->parent;
if (!$parent)
break;
if ($current === $parent->left)
array_push($bits, 0);
else
array_push($bits, 1);
$current = $parent;
}
$allBits = array_merge($allBits, array_reverse($bits));
}
return $allBits;
}
private static function decodeTree($treeBits) {
$t = new Tree();
if (!count($treeBits))
return $t;
$leaves = array();
$helper = function($treeBits, $i) use (&$helper, &$leaves) {
global $symbolMap;
if ($treeBits[$i] == 1) {
$i++;
// TODO: Refactor Node so that it doesn't store the weight
// internally.
$symbolBits = array();
for ($j = 0; $j < SYMBOL_SIZE; ++$j)
array_push($symbolBits, $treeBits[$i + $j]);
$i += SYMBOL_SIZE;
$symbol = $symbolMap[join("", $symbolBits)];
$node = new Node($symbol, 0);
$leaves[$symbol] = $node;
return array($i, $node);
} else {
$leftResult = $helper($treeBits, $i + 1);
$leftChild = $leftResult[1];
$rightResult = $helper($treeBits, $leftResult[0]);
$rightChild = $rightResult[1];
$node = new Node(null, 0);
$node->left = $leftChild;
$node->right = $rightChild;
$leftChild->parent = $node;
$rightChild->parent = $node;
return array($rightResult[0], $node);
}
};
$result = $helper($treeBits, 0);
$t->root = $result[1];
$t->leaves = $leaves;
return array($result[0], $t);
}
public static function decode($bits) {
$result = Huffman::decodeTree($bits);
$startIndex = $result[0];
$tree = $result[1];
$current = $tree->root;
$s = "";
$i = $startIndex;
while ($i < count($bits)) {
if ($current->left && $current->right) {
if ($bits[$i++])
$current = $current->right;
else
$current = $current->left;
} else {
if ($current->left || $current->right)
throw new Exception("Leaf must not have any children.");
$s .= $current->symbol;
$current = $tree->root;
}
}
if ($current->left || $current->right) {
throw new Exception("Leaf expected at end of input.");
}
$s .= $current->symbol;
return $s;
}
}
$s = join("\n", array(
"4 Minute Warning - Radiohead",
"",
"This is just a nightmare",
"Soon I'm gonna wake up",
"Someone's gonna bring me 'round",
"",
"Running from the bombers",
"Hiding in the forest",
"Running through the fields",
"Laying flat on the ground",
"",
"Just like everybody",
"Stepping over hills",
"Running from the underground",
"",
"This is your warning",
"4 minute warning",
"",
"I don't wanna hear it",
"I don't wanna know",
"I just wanna run and hide",
"",
"This is just a nightmare",
"But soon I'm gonna wake up",
"Someone's gonna bring me 'round",
"",
"This is our warning",
"4 minute warning"
));
$RunHuffman = function() {
global $s;
$t = Huffman::buildTree($s);
$bits = Huffman::encode($s, $t);
$s2 = Huffman::decode($bits);
if ($s2 != $s) {
echo "Expected:\n$s\n";
echo "Actual:\n$s2\n";
throw new Exception("Incorrect result");
}
};
$Huffman = new BenchmarkSuite('Huffman', [100000], [
new Benchmark('Huffman', true, false, 100000, $RunHuffman)
]);
?>
Enable javascript to submit You have javascript disabled. You will not be able to edit any code.
Here you find the average performance (time & memory) of each version. A grayed out version indicates it didn't complete successfully (based on exit-code).
Version System time (s) User time (s) Memory (MiB) 8.3.4 0.017 0.000 18.63 8.3.3 0.007 0.007 19.04 8.3.2 0.000 0.007 20.29 8.3.1 0.008 0.000 23.65 8.3.0 0.007 0.003 19.06 8.2.17 0.011 0.004 22.96 8.2.16 0.008 0.006 19.13 8.2.15 0.004 0.004 24.18 8.2.14 0.008 0.000 24.66 8.2.13 0.000 0.007 26.16 8.2.12 0.002 0.005 22.26 8.2.11 0.004 0.008 20.29 8.2.10 0.008 0.004 17.72 8.2.9 0.000 0.008 18.03 8.2.8 0.005 0.003 17.97 8.2.7 0.009 0.000 17.38 8.2.6 0.000 0.008 17.92 8.2.5 0.006 0.003 18.07 8.2.4 0.006 0.003 19.95 8.2.3 0.004 0.004 18.01 8.2.2 0.007 0.000 17.57 8.2.1 0.000 0.007 17.95 8.2.0 0.000 0.008 17.71 8.1.27 0.000 0.008 21.95 8.1.26 0.007 0.000 26.35 8.1.25 0.004 0.004 28.09 8.1.24 0.000 0.009 22.20 8.1.23 0.011 0.000 20.97 8.1.22 0.005 0.003 17.74 8.1.21 0.004 0.004 18.91 8.1.20 0.006 0.003 17.10 8.1.19 0.004 0.004 16.98 8.1.18 0.000 0.007 18.10 8.1.17 0.000 0.008 18.30 8.1.16 0.000 0.007 21.89 8.1.15 0.000 0.007 18.70 8.1.14 0.000 0.007 17.38 8.1.13 0.003 0.003 17.65 8.1.12 0.000 0.008 17.42 8.1.11 0.007 0.000 17.33 8.1.10 0.000 0.007 17.35 8.1.9 0.004 0.004 17.26 8.1.8 0.007 0.000 17.31 8.1.7 0.008 0.000 17.35 8.1.6 0.004 0.004 17.48 8.1.5 0.003 0.006 17.45 8.1.4 0.010 0.003 17.41 8.1.3 0.000 0.008 17.59 8.1.2 0.004 0.004 17.47 8.1.1 0.002 0.005 17.45 8.1.0 0.004 0.004 17.26 8.0.30 0.005 0.003 20.11 8.0.29 0.004 0.004 16.63 8.0.28 0.007 0.000 18.32 8.0.27 0.000 0.007 17.25 8.0.26 0.005 0.003 17.21 8.0.25 0.006 0.000 16.82 8.0.24 0.000 0.006 16.86 8.0.23 0.007 0.000 16.80 8.0.22 0.007 0.000 16.78 8.0.21 0.000 0.007 16.80 8.0.20 0.006 0.000 16.83 8.0.19 0.004 0.004 16.75 8.0.18 0.002 0.005 16.79 8.0.17 0.004 0.004 16.80 8.0.16 0.000 0.007 16.82 8.0.15 0.000 0.007 16.65 8.0.14 0.002 0.005 16.63 8.0.13 0.003 0.003 13.65 8.0.12 0.004 0.004 16.70 8.0.11 0.000 0.008 16.79 8.0.10 0.007 0.000 16.80 8.0.9 0.000 0.007 16.65 8.0.8 0.006 0.009 16.77 8.0.7 0.005 0.002 16.83 8.0.6 0.004 0.004 16.75 8.0.5 0.000 0.008 16.75 8.0.3 0.012 0.009 17.06 8.0.2 0.007 0.011 17.40 8.0.1 0.000 0.007 16.97 8.0.0 0.007 0.010 16.79 7.4.33 0.000 0.006 15.09 7.4.32 0.003 0.003 16.52 7.4.30 0.000 0.007 16.34 7.4.29 0.000 0.007 16.51 7.4.28 0.003 0.005 16.28 7.4.27 0.003 0.003 16.37 7.4.26 0.002 0.005 16.47 7.4.25 0.005 0.003 16.45 7.4.24 0.001 0.006 16.45 7.4.23 0.007 0.000 16.23 7.4.22 0.011 0.007 16.43 7.4.21 0.003 0.010 16.45 7.4.20 0.004 0.004 16.31 7.4.16 0.016 0.000 16.44 7.4.15 0.010 0.010 17.40 7.4.14 0.012 0.006 17.86 7.4.13 0.010 0.011 16.42 7.4.12 0.011 0.007 16.43 7.4.11 0.015 0.003 16.50 7.4.10 0.010 0.007 16.29 7.4.9 0.011 0.007 16.24 7.4.8 0.013 0.004 19.39 7.4.7 0.009 0.009 16.44 7.4.6 0.004 0.014 16.34 7.4.5 0.003 0.005 16.25 7.4.4 0.013 0.010 16.19 7.4.3 0.011 0.005 16.27 7.4.0 0.003 0.014 14.54 7.3.33 0.000 0.006 13.68 7.3.32 0.000 0.007 13.61 7.3.31 0.007 0.000 16.13 7.3.30 0.000 0.007 16.19 7.3.29 0.012 0.008 16.25 7.3.28 0.007 0.009 16.13 7.3.27 0.012 0.012 17.40 7.3.26 0.011 0.005 16.30 7.3.25 0.008 0.013 16.15 7.3.24 0.013 0.003 16.14 7.3.23 0.004 0.013 16.42 7.3.21 0.009 0.006 16.24 7.3.20 0.007 0.016 19.39 7.3.19 0.015 0.006 16.15 7.3.18 0.010 0.007 16.39 7.3.17 0.008 0.008 16.61 7.3.16 0.010 0.006 16.60 7.2.33 0.012 0.005 16.59 7.2.32 0.011 0.005 16.50 7.2.31 0.010 0.013 16.37 7.2.30 0.013 0.003 16.66 7.2.29 0.009 0.006 16.46 7.2.6 0.008 0.008 16.49 7.2.0 0.000 0.014 19.58 7.1.20 0.004 0.011 15.60 7.1.10 0.003 0.009 17.96 7.1.7 0.000 0.008 17.24 7.1.6 0.010 0.017 19.32 7.1.5 0.004 0.018 16.90 7.1.0 0.007 0.073 22.44 7.0.20 0.005 0.005 16.70 7.0.14 0.003 0.073 21.99 7.0.10 0.007 0.070 20.39 7.0.9 0.013 0.087 20.23 7.0.8 0.020 0.077 20.08 7.0.7 0.007 0.077 20.09 7.0.6 0.010 0.087 20.18 7.0.5 0.007 0.070 20.51 7.0.4 0.007 0.080 20.13 7.0.3 0.010 0.050 20.10 7.0.2 0.020 0.073 20.14 7.0.1 0.010 0.067 20.13 7.0.0 0.007 0.080 20.04 5.6.28 0.000 0.080 21.12 5.6.25 0.020 0.073 21.15 5.6.24 0.017 0.073 20.93 5.6.23 0.003 0.093 20.84 5.6.22 0.010 0.047 21.04 5.6.21 0.010 0.077 20.98 5.6.20 0.007 0.050 21.29 5.6.19 0.007 0.053 21.27 5.6.18 0.017 0.050 21.34 5.6.17 0.013 0.083 21.43 5.6.16 0.017 0.043 21.44 5.6.15 0.003 0.053 21.44 5.6.14 0.003 0.073 21.35 5.6.13 0.007 0.073 21.46 5.6.12 0.010 0.087 21.37 5.6.11 0.017 0.077 21.34 5.6.10 0.010 0.057 21.39 5.6.9 0.007 0.060 21.26 5.6.8 0.007 0.050 20.77 5.6.7 0.023 0.080 20.76 5.6.6 0.010 0.077 20.73 5.6.5 0.003 0.043 20.66 5.6.4 0.013 0.067 20.62 5.6.3 0.010 0.053 20.83 5.6.2 0.017 0.073 20.69 5.6.1 0.013 0.067 20.69 5.6.0 0.010 0.067 20.84 5.5.38 0.007 0.047 20.75 5.5.37 0.007 0.083 20.88 5.5.36 0.000 0.047 20.68 5.5.35 0.020 0.077 20.68 5.5.34 0.007 0.047 21.27 5.5.33 0.010 0.073 21.14 5.5.32 0.017 0.060 21.16 5.5.31 0.010 0.070 21.25 5.5.30 0.007 0.040 21.21 5.5.29 0.003 0.077 20.98 5.5.28 0.013 0.083 21.11 5.5.27 0.007 0.090 21.22 5.5.26 0.003 0.093 21.21 5.5.25 0.013 0.077 21.02 5.5.24 0.017 0.077 20.52 5.5.23 0.007 0.070 20.55 5.5.22 0.007 0.073 20.61 5.5.21 0.013 0.043 20.45 5.5.20 0.003 0.087 20.49 5.5.19 0.007 0.040 20.52 5.5.18 0.007 0.067 20.41 5.5.16 0.010 0.073 20.59 5.5.15 0.000 0.087 20.44 5.5.14 0.007 0.080 20.31 5.5.13 0.010 0.077 20.50 5.5.12 0.007 0.070 20.60 5.5.11 0.010 0.080 20.54 5.5.10 0.013 0.047 20.32 5.5.9 0.013 0.070 20.40 5.5.8 0.003 0.087 20.41 5.5.7 0.007 0.043 20.47 5.5.6 0.003 0.070 20.27 5.5.5 0.003 0.050 20.39 5.5.4 0.013 0.073 20.50 5.5.3 0.007 0.077 20.29 5.5.2 0.020 0.040 20.43 5.5.1 0.003 0.060 20.30 5.5.0 0.013 0.073 20.39 5.4.45 0.007 0.083 19.61 5.4.44 0.003 0.043 19.63 5.4.43 0.010 0.083 19.69 5.4.42 0.010 0.063 19.71 5.4.41 0.020 0.067 19.42 5.4.40 0.007 0.073 19.33 5.4.39 0.007 0.080 19.12 5.4.38 0.010 0.073 19.16 5.4.37 0.007 0.063 19.32 5.4.36 0.007 0.050 19.30 5.4.35 0.017 0.067 19.39 5.4.34 0.007 0.080 19.37 5.4.32 0.007 0.057 19.29 5.4.31 0.010 0.073 19.32 5.4.30 0.003 0.063 19.29 5.4.29 0.007 0.077 19.46 5.4.28 0.013 0.073 19.32 5.4.27 0.000 0.053 19.33 5.4.26 0.017 0.057 19.45 5.4.25 0.010 0.040 19.29 5.4.24 0.003 0.073 19.38 5.4.23 0.003 0.080 19.36 5.4.22 0.007 0.067 19.35 5.4.21 0.003 0.047 19.47 5.4.20 0.003 0.080 19.11 5.4.19 0.013 0.063 19.29 5.4.18 0.010 0.073 19.16 5.4.17 0.007 0.070 19.15 5.4.16 0.000 0.050 19.35 5.4.15 0.020 0.070 19.46 5.4.14 0.017 0.067 16.72 5.4.13 0.003 0.080 16.60 5.4.12 0.007 0.067 16.55 5.4.11 0.000 0.050 16.74 5.4.10 0.007 0.050 16.60 5.4.9 0.007 0.063 16.78 5.4.8 0.007 0.070 16.66 5.4.7 0.017 0.067 16.57 5.4.6 0.007 0.073 16.59 5.4.5 0.007 0.057 16.62 5.4.4 0.003 0.047 16.79 5.4.3 0.000 0.080 16.63 5.4.2 0.003 0.070 16.63 5.4.1 0.003 0.080 16.60 5.4.0 0.007 0.070 16.02
preferences:dark mode live preview
40.09 ms | 400 KiB | 5 Q