http://qiita.com/Nabetani/items/24b9be4ee3bae4c89a95
http://nabetani.sakura.ne.jp/hena/ord8entco/

必ず一意に復元可能なので、^でマッチングするだけです。

<?php
	
	class ENTROPY{
	
		/**
		* 符号を解読して返す
		* @param  String 「16d9d4fbd」みたいな文字列
		* @return String 「ethanol:30」みたいな文字列
		*/
		public function get($input){
			
			// マッチ文字列
			$search = ['/^000/', '/^0010/', '/^0011/', '/^0100/', '/^01010/', '/^0101101/', '/^010111/', '/^0110/', '/^0111/', '/^10/', '/^1100/', '/^1101/', '/^111/'];
			$replace = ['t', 's', 'n', 'i', 'd', 'c', 'l', 'o', 'a', 'e', 'r', 'h', 'z'];
			
			// 入力値を2進数に
			$str = '';
			for($i=0; $i<strlen($input); $i++){
				$str.= strrev(str_pad(base_convert($input[$i], 16, 2), 4, '0', STR_PAD_LEFT));
			}
			
			// 内部使用
			$entropy = ''; // できあがる文字列
			$lastmatch = ''; // 最後にマッチした文字
			$strlen = strlen($str); // ビット数カウント用
			
			// マッチする限り繰り返し
			$str = preg_replace($search, $replace, $str, 1, $count);
			while($count>0){
				$lastmatch = $str[0];
				$str = substr($str, 1);
				
				// 引っかかったのがEOFだったら終了
				if($lastmatch === 'z'){
					break;
				}
				
				// 次のループ用
				$entropy .= $lastmatch;
				$str = preg_replace($search, $replace, $str, 1, $count);
			};
			
			// マッチしなかった / EOFがなかった
			if($entropy === '' || $lastmatch !== 'z'){
				return '*invalid*';
			}
			
			// 返却
			return $entropy . ':' . ($strlen - strlen($str));
		}
		
	}
	
	// テスト
	$test = [
		['16d9d4fbd', 'ethanol:30'],
		/* 省略 */
	];

	$entropy = new ENTROPY();
	foreach($test as $key=>$data){
		$answer = $entropy->get($data[0]);
		if($answer !== $data[1]){
			print('えらー');
		}
	}

2進数にするところで、通常"0x1"は"0001"になりますが、今回は"1000"にしないといけないので妙なことになってます。
検索ループはwhile(strpos()===0)とかwhile(preg_match())みたいにしたかったのですが、いまいちうまくいかなかったのでpreg_replaceを使って微妙なことに。
あとarray_shift()の文字列版ってないのだろうか。

かかった時間は2時間くらい。
どうマッチするかのところで相当時間をくってしまいました。
もうelseif繋げたほうが手っ取り早かったんじゃないかな。
http://qiita.com/shinak53/items/0e7899c0172655960d41