位编码算法的类（分类算法）

夜猫子

按照前段时间说过的位编码算法实现了一个类（ http://www.chinaunix.net/forum/27/20031122/207556.html ），放出来大家看看，大家帮我改进。

1. 
   
2. <?php
   
3. Class BinTree
   
4. {
   
5.     //树结构
   
6.     /*************************************
   
7.     example:
   
8.     $Structure = array(4,7,7,7,7);
   
9.     树有4层，第一层4位编码，第二、第三、第四、第五层7位编码
   
10.     ************************************/
    
11.     var $Structure;
    
12.    
    
13.     /// 存储树的每层信息的数组
    
14.     /*************************************
    
15.     //特征码
    
16.     //2^N-2^(N-(N1+N2+…+Ni))
    
17.     example:
    
18.     $Layer = array(   层的二进制编码长度       层的特征码       每一层每节点的公差
    
19.                 1 =>; array('len' =>; 4, 'mark' =>; 4026531840, 'tolerance' =>; 268435456),
    
20.                 2 =>; array('len' =>; 7, 'mark' =>; 4292870144, 'tolerance' =>; 2097152),
    
21.                 3 =>; array('len' =>; 7, 'mark' =>; 4294950912, 'tolerance' =>; 16384),
    
22.                 4 =>; array('len' =>; 7, 'mark' =>; 4294967168, 'tolerance' =>; 128),
    
23.                 5 =>; array('len' =>; 7, 'mark' =>; 4294967295, 'tolerance' =>; 1)
    
24.                 );
    
25.     *************************************/
    
26.     var $Layer;
    
27.    
    
28.     //二进制编码总长度
    
29.     var $binMarkLen;
    
30.    
    
31.     //现在用来分析的目标节点，十进制
    
32.     var $_decCurrentNode;
    
33.    
    
34.     //现在用来分析的目标节点，二进制
    
35.     var $_binCurrentNode;
    
36.    
    
37.     //CurrentNodeID的所属的层
    
38.     var $_CurrentLayer;
    
39.    
    
40.     // 初始化树
    
41.     function BinTree($Structure)
    
42.     {
    
43.         $this->;binMarkLen = array_sum($Structure);
    
44.         
    
45.         $tmpLen = 0;
    
46.         foreach ( $Structure as $k =>; $v )
    
47.         {
    
48.             $this->;Layer[$k+1]['len'] = $v;
    
49.             
    
50.             $tmpLen += $v;
    
51.             $this->;Layer[$k+1]['mark'] = pow(2, $this->;binMarkLen) - pow(2, $this->;binMarkLen - $tmpLen);
    
52.             $this->;Layer[$k+1]['tolerance'] = pow(2, $this->;binMarkLen - $tmpLen);
    
53.         }
    
54.         
    
55.         return true;
    
56.     }
    
57.    
    
58.     // 解析当前节点
    
59.     function _parseNode($Node)
    
60.     {
    
61.         $this->;_decCurrentNode = $Node;
    
62.         //节点二进制编码
    
63.         $this->;_binCurrentNode = FillBit(base_convert($Node, 10, 2), $this->;binMarkLen);
    
64.         
    
65.         //节点处于树的第几层
    
66.         $start = 0;
    
67.         foreach ( $this->;Layer as $k =>; $v )
    
68.         {
    
69.             $binMark = substr($this->;_binCurrentNode, $start, $v['len']);
    
70.             $testMark = str_repeat('0', $v['len']);
    
71.             $start += $v['len'];
    
72.             
    
73.             if ( $binMark == $testMark )
    
74.             {
    
75.                 $this->;_CurrentLayer = $k - 1;
    
76.                 break;
    
77.             }
    
78.             $this->;_CurrentLayer = count($this->;Layer);
    
79.         }
    
80.     }
    
81.    
    
82.     // 清除上次解析的结果
    
83.     function _unparseNode()
    
84.     {
    
85.         $this->;_decCurrentNode = null;
    
86.         $this->;_binCurrentNode = null;
    
87.         $this->;_CurrentLayer = null;
    
88.     }
    
89.    
    
90.     // 获得父节点
    
91.     // 如果$all不为空则以数组格式返回所有父节点，否则仅返回上一层节点
    
92.     function getParent($Node, $all = '')
    
93.     {
    
94.         if ( $this->;_decCurrentNode != $Node )
    
95.         {
    
96.             $this->;_parseNode($Node);
    
97.         }
    
98.         
    
99.         if ( $this->;_CurrentLayer == 1 )
    
100.         {
     
101.             $ParentNode = 0;
     
102.         }
     
103.         else
     
104.         {
     
105.             if ( $all )
     
106.             {
     
107.                 for ( $i = 1; $i < $this->;_CurrentLayer; $i++ )
     
108.                 {
     
109.                     $ParentNode[$i] = $Node & $this->;Layer[$i]['mark'];
     
110.                 }
     
111.             }
     
112.             else
     
113.             {
     
114.                 $ParentNode = $Node & $this->;Layer[$this->;_CurrentLayer - 1]['mark'];
     
115.             }
     
116.         }
     
117.         
     
118.         return $ParentNode;
     
119.     }
     
120.    
     
121.     // 获得下级子节点值
     
122.     // 如果$j没有赋值则返回所有的子节点
     
123.     function getChild($Node, $j = '')
     
124.     {
     
125.         if ( $this->;_decCurrentNode != $Node )
     
126.         {
     
127.             $this->;_parseNode($Node);
     
128.         }
     
129.         
     
130.         if ( $this->;_CurrentLayer == count($this->;Layer) )
     
131.         {
     
132.             return false;
     
133.         }
     
134.         else
     
135.         {
     
136.             $ChildLayer = $this->;_CurrentLayer + 1;
     
137.             
     
138.             if ( $j >; 0 )
     
139.             {
     
140.                 if ( ($j >; 0 ) and ($j < pow(2, $this->;Layer[$ChildLayer]['len'])) )
     
141.                 {
     
142.                     $ChildNode = $this->;Layer[$ChildLayer]['tolerance'] * $j + $Node;
     
143.                 }
     
144.                 else
     
145.                 {
     
146.                     return false;
     
147.                 }
     
148.             }
     
149.             else
     
150.             {
     
151.                 for ( $i = 1; $i < pow(2, $this->;Layer[$ChildLayer]['len']); $i++ )
     
152.                 {
     
153.                     $ChildNode[] = $this->;Layer[$ChildLayer]['tolerance'] * $i + $Node;
     
154.                 }
     
155.             }
     
156.         }
     
157.         
     
158.         return $ChildNode;
     
159.     }
     
160.    
     
161.     // 得到同一层的下一个节点
     
162.     function getNextNode($Node)
     
163.     {
     
164.         if ( $this->;_decCurrentNode != $Node )
     
165.         {
     
166.             $this->;_parseNode($Node);
     
167.         }
     
168.         $thisLayer = $this->;_CurrentLayer;
     
169.         
     
170.         $ParentNode = $this->;getParent($Node);
     
171.         $this->;_unparseNode();
     
172.         
     
173.         $j = ($Node - $ParentNode)/$this->;Layer[$thisLayer]['tolerance'];
     
174.         
     
175.         if ( $j+1 < pow(2, $this->;Layer[$thisLayer]['len']) )
     
176.         {
     
177.             return $this->;Layer[$thisLayer]['tolerance'] + $Node;
     
178.         }
     
179.         else
     
180.         {
     
181.             return false;
     
182.         }
     
183.     }
     
184. }
     
185. 
     
186. Class DBBinTree extends BinTree
     
187. {
     
188.     //树实例所在的表
     
189.     var $Table;
     
190.    
     
191.     //树实例所在的字段
     
192.     var $Column;
     
193.    
     
194.     // 初始化
     
195.     function DBBinTree($Structure, $table, $column)
     
196.     {
     
197.         parent::BinTree($Structure);
     
198.         
     
199.         $this->;Table = $table;
     
200.         $this->;Column = $column;
     
201.         
     
202.         return true;
     
203.     }
     
204.    
     
205.     // 获得父节点
     
206.     // 如果$all不为空则以数组格式返回所有父节点，否则仅返回上一层节点
     
207.     function SelectParent($Node, $all = '')
     
208.     {
     
209.         global $db;
     
210.         
     
211.         $ParentNode = $this->;getParent($Node, $all);
     
212.         
     
213.         if ( is_array($ParentNode) )
     
214.         {
     
215.             $sql = "select * from ". $this->;Table ." where ". $this->;Column ." in (". implode(',', $ParentNode) .")";
     
216.         }
     
217.         else
     
218.         {
     
219.             $sql = "select * from ". $this->;Table ." where ". $this->;Column ." = ". $ParentNode;
     
220.         }
     
221.         
     
222.         $rowset = $db->;getAll($sql);
     
223.         if ( !$db->;isError($rowset) )
     
224.         {
     
225.             return $rowset;
     
226.         }
     
227.         else
     
228.         {
     
229.             return false;
     
230.         }
     
231.     }
     
232.    
     
233.     // 获得子节点
     
234.     // 如果$all不为空则以数组格式返回所有子节点，否则仅返回下一层节点
     
235.     function SelectChild($Node, $all = '')
     
236.     {
     
237.         global $db;
     
238.         
     
239.         $this->;_parseNode($Node);
     
240.         
     
241.         $sql = "select * from ". $this->;Table ." where ". $this->;Column ." >; ". $Node ." and ". $this->;Column ." < ". $this->;getNextNode($Node);
     
242.         
     
243.         $res = $db->;query($sql);
     
244.         if ( !$db->;isError($res) )
     
245.         {
     
246.             if ( $all )
     
247.             {
     
248.                 while ( $row = $res->;fetchRow() )
     
249.                 {
     
250.                     $rowset[] = $row;
     
251.                 }
     
252.             }
     
253.             else
     
254.             {
     
255.                 $Child = $this->;getChild($Node);
     
256.                
     
257.                 while ( $row = $res->;fetchRow() )
     
258.                 {
     
259.                     if ( in_array($row[$this->;Column], $Child) )
     
260.                     {
     
261.                         $rowset[] = $row;
     
262.                     }
     
263.                 }
     
264.             }
     
265.             
     
266.             return $rowset;
     
267.         }
     
268.         else
     
269.         {
     
270.             return false;
     
271.         }
     
272.     }
     
273. }
     
274. ?>;
     

复制代码

夜猫子

测试数据库：
INSERT INTO bintree (binMark,decMark) VALUES ('01000000000000000000000000000000',1073741824);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000000000000000000000',1092616192);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101000000000000000',1092780032);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000000000',1092787200);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001000',109278720;
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101100000000000000',1092796416);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000110000000000000000',1092812800);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000110100000000000000',1092829184);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000111000000000000000',109284556;
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000111100000000000000',1092861952);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110010000000',109278732;
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110100000000',1092787456);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110110000000',1092787584);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001111000000000',1092787712);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001111010000000',1092787840);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001111100000000',109278796;
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001111110000000',1092788096);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001001',1092787209);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001010',1092787210);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001011',1092787211);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001100',1092787212);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001101',1092787213);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001110',1092787214);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001111',1092787215);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000010000',1092787216);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101000000010000000',1092780160);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101011111110000000',109279628;

夜猫子

这种算法就是建立在事先规划好树的容量的基础上，层数和每层的数量事先都要有数，所以不适合那种无限分层的树
这种树结构比较死一点，我另外想了一个灵活些的树结构，打算先在我的项目里用用，如果好的话，再推荐给大家

夜猫子

其实也不是什么很新鲜的主意，就是普通的树加一个辅助字段而已，是在这个问题的讨论中吸收了别人的意见的结果。
node_id   parent    code
1             0             01
2             1             0102
3             2             010203
我分析了一下，如果层非常多的话，位编码的方式就不可行了，因为位是不定长的，只有普通的那种树结构能够轻松满足。但是普通的那种树最大的毛病就是基于递归的遍历，所以想到加一个辅助字段来解决这个递归的毛病。
code字段其实就是路径信息，但是采用36进制，以2位为一层的话，每层可以容纳(36^2)-1也就是1295个节点，假设code字段用varchar(255)的话，可以容纳127层36^(254)-1个节点，容量非常大了，当然很少会用到这么大的树，如果真要处理这么大的树，肯定需要更好的方法。
采用36进制以后，占用的存储空间相对小，编码比较短，在采用like查询子节点的时候效率会比用低进制编码存储的路径效率要高，而且我敢肯定，效率肯定是比递归高的。并且不是每次对树的查询都需要对这个字段查询，比如只是想查上一级节点，同一层节点，下一层节点就可以直接的利用原来的方法。
这种方式适用于不能确定长度的树，我觉得一般的情况来说，我不会碰到特别大的树，一般不会超过4到5层。根据不同的情况，这两种树结合着用就差不多了。
具体怎么样，我也不好说，所以打算先写出来自己用用才真正清楚效果，既然老兄你问到了，我就说说，请指正。

夜猫子

你的意见我想想，另外我有两点要说：
采用36进制是因为我用base_convert来换算进制，最高支持到36位，再高就不晓得怎么处理了，呵呵，longnetpro教我。
另外我发觉刚才在每层节点的容量上的记算是错误的，因为node_id是在数据库里用了auto_increment来实现的，因此，node_id是不可重复的，所以，编码里肯定不会出现0101或者0a0a这样的编码，这样实际上大大的降低了每层的容量，而且树越大，这个影响越明显，所以不能处理太大的树，不同的编码长度对应的上限之间的关系我还没有计算出来，估计应该是在可接受范围内的，太大的树现在不在考虑范围。

夜猫子

呵呵，刚发完上一个帖子就想清楚上限了。
编码的进制是m
每层编码的长度是n
那么整个树的总节点容量上限是(m^n)-1，树的层数理论上限也是(m^n)-1，所以如果要采用这种方法的话，事先也要先计划好容量的。

mikespook

恩~~~看看~~~

能不能改成16进制编码，这样编码比较短~~~