1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
|
<?php
/*
+----------------------------------------------------------------------+
| PHP Version 4 |
+----------------------------------------------------------------------+
| Copyright (c) 1997-2004 The PHP Group |
+----------------------------------------------------------------------+
| This source file is subject to version 3.0 of the PHP license, |
| that is bundled with this package in the file LICENSE, and is |
| available through the world-wide-web at the following url: |
| http://www.php.net/license/3_0.txt. |
| If you did not receive a copy of the PHP license and are unable to |
| obtain it through the world-wide-web, please send a note to |
| license@php.net so we can mail you a copy immediately. |
+----------------------------------------------------------------------+
| Authors: Mitja Slenc <mitja@php.net> |
+----------------------------------------------------------------------+
$Id: prefixcompress.php,v 1.4 2004/12/20 15:56:01 goba Exp $
*/
$funcs=file("funclist.txt");
foreach($funcs as $key => $val)
$funcs[$key]=trim($val);
$result=DoCompress($funcs);
$outfile=fopen("prefixcompressed.txt", "w");
fwrite($outfile, DoCompress($funcs));
$cache=array();
function DoCompress($list, $level=0)
{
global $cache;
$key=implode(",",$list);
if (isset($cache[$key]))
return $cache[$key];
$result="";
while (sizeof($list)) {
if ($result && substr($result,-1)!=')' && substr($result,-1)!=']') $result.=",";
if (sizeof($list)==1) {
$result.=$list[0];
return ($cache[$key]=$result);
}
if (sizeof($list)==2) {
if (substr($list[1],0,strlen($list[0]))==$list[0]) {
$result.=$list[0]."[".substr($list[1],strlen($list[0]))."]";
return ($cache[$key]=$result);
} else {
if (substr($list[0],0,2)!=substr($list[1],0,2)) {
$result.=$list[0].",".$list[1];
} else {
$len=2;
while ($len<strlen($list[0]) && substr($list[0],0,$len+1)==substr($list[1],0,$len+1)) {
$len++;
}
$result.=substr($list[0],0,$len)."(".substr($list[0],$len).",".substr($list[1],$len).")";
}
return ($cache[$key]=$result);
}
}
if (@($list[0][0]!=$list[1][0] || ($list[0][1]!=$list[1][1] && $list[2][0]!=$list[0][0]))) {
$result.=array_shift($list);
continue;
}
$bestsave=0;
$bestremain=$list;
$bestresult=array_shift($bestremain);
if (substr($list[1],0,strlen($list[0]))==$list[0]) {
$tmplist=$list;
$prefix=array_shift($tmplist);
$subs=array();
while (@substr($tmplist[0],0,strlen($prefix))==$prefix) {
$subs[]=substr(array_shift($tmplist),strlen($prefix));
}
$tmpresult=$prefix."[";
$tmpresult.=DoCompress($subs);
$tmpresult.="]";
$bestsave=sizeof($subs)*strlen($prefix)-1;
if (sizeof($tmplist)) $bestsave++;
$bestremain=$tmplist;
$bestresult=$tmpresult;
}
for ($len=strlen($list[0])-1; $len>=1; $len--) {
$prefix=substr($list[0],0,$len);
$count=0;
while ($count<sizeof($list) && substr($list[$count],0,$len)==$prefix)
$count++;
$save=($count-1)*$len-2;
if ($count<sizeof($list))
$save++;
if ($save>$bestsave) {
$bestsave=$save;
$tmplist=$list;
$subs=array();
for ($a=0; $a<$count; $a++)
$subs[]=substr(array_shift($tmplist),$len);
$bestremain=$tmplist;
$bestresult=$prefix."(".DoCompress($subs).")";
}
}
$result.=$bestresult;
$list=$bestremain;
}
return ($cache[$key]=$result);
}
?>
|