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
114
|
<?php
/*
+----------------------------------------------------------------------+
| PHP Version 5 |
+----------------------------------------------------------------------+
| Copyright (c) 1997-2010 The PHP Group |
+----------------------------------------------------------------------+
| This source file is subject to version 3.01 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_01.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. |
+----------------------------------------------------------------------+
| Author: Mitja Slenc <mitja@php.net> |
+----------------------------------------------------------------------+
$Id: prefixcompress.php 293138 2010-01-05 10:21:11Z rquadling $
*/
$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);
}
?>
|
