IDC资讯中心
darkman·yesky
在网站建设中，分类算法的应用非常的普遍。在设计一个电子商店时，要涉及到商品分类；在设计发布系统时，要涉
及到栏目或者频道分类；在设计软件下载这样的程序时，要涉及到软件的分类；如此等等。可以说，分类是一个很普遍的
问题。
我常常面试一些程序员，而且我几乎毫无例外地要问他们一些关于分类算法的问题。下面的举几个我常常询问的问
题。你认为你可以很轻松地回答么^_^.
1、 分类算法常常表现为树的表示和遍历问题。那么，请问：如果用数据库中的一个table来表达树型分类，应该有几个字
段？
2、 如何快速地从这个table恢复出一棵树；
3、 如何判断某个分类是否是另一个分类的子类；
4、 如何查找某个分类的所有产品；
5、 如何生成分类所在的路径。
6、 如何新增分类；
在不限制分类的级数和每级分类的个数时，这些问题并不是可以轻松回答的。本文试图解决这些问题。
分类的数据结构
我们知道：分类的数据结构实际上是一棵树。在《数据结构》课程中，大家可能学过tree的算法。由于在网站建设中
我们大量使用数据库，所以我们将从tree在数据库中的存储谈起。
为简化问题，我们假设每个节点只需要保留name这一个信息。我们需要为每个节点编号。编号的方法有很多种。在数
据库中常用的就是自动编号。这在access、sql server、oracle中都是这样。假设编号字段为id。
为了表示某个节点id1是另外一个节点id2的父节点，我们需要在数据库中再保留一个字段，说明这个分类是属于哪个
节点的儿子。把这个字段取名为fatherid。如这里的id2，其fatherid就是id1。
这样，我们就得到了分类catalog的数据表定义：
create table [catalog](
[id] [int] not null,
[name] [nvarchar](50) not null,
[fatherid] [int] not null
);
约定：我们约定用-1作为最上面一层分类的父亲编码。编号为-1的分类。这是一个虚拟的分类。它在数据库中没有记
录。
如何恢复出一棵树
上面的catalog定义的最大优势，就在于用它可以轻松地恢复出一棵树-分类树。为了更清楚地展示算法，我们先考虑
一个简单的问题：怎样显示某个分类的下一级分类。我们知道，要查询某个分类fid的下一级分类，sql语句非常简单：
select name from catalog where fatherid=fid
显示这些类别时，我们简单地用<li>来做到：
<%
rem oconn—数据库连接，调用getchildren时已经打开
rem fid—–当前分类的编号
function getchildren(oconn,fid)
strsql = "select id,name from catalog where fatherid="&fid
set rscatalog = oconn.execute(strsql)
%>
<ul>
<%
do while not rscatalog.eof
%>
<li><%=rscatalog("name")%>
<%
loop
%>
</ul>
<%
rscatalog.close
end function
%>
现在我们来看看如何显示fid下的所有分类。这需要用到递归算法。我们只需要在getchildren函数中简单地对所有id
进行调用：getchildren(oconn,catalog("id"))就可以了。
<%
rem oconn—数据库连接，已经打开
rem fid—–当前分类的编号
function getchildren(oconn,fid)
strsql = "select name from catalog where fatherid="&fid
set rscatalog = oconn.execute(strsql)
%>
<ul>
<%
do while not rscatalog.eof
%>
<li><%=rscatalog("name")%>
<%=getchildren(oconn,catalog("id"))%>
<%
loop
%>
</ul>
<%
rscatalog.close
end function
%>
修改后的getchildren就可以完成显示fid分类的所有子分类的任务。要显示所有的分类，只需要如此调用就可以了：
<%
rem strconn–连接数据库的字符串，请根据情况修改
set oconn = server.createobject("adodb.connection")
oconn.open strconn
=getchildren(oconn,-1)
oconn.close
%>
如何查找某个分类的所有产品；
现在来解决我们在前面提出的第四个问题。第三个问题留作习题。我们假设产品的数据表如下定义：
create table product(
[id] [int] not null,
[name] [nvchar] not null,
[fatherid] [int] not null
);
其中，id是产品的编号，name是产品的名称，而fatherid是产品所属的分类。
对第四个问题，很容易想到的办法是：先找到这个分类fid的所有子类，然后查询所有子类下的所有产品。实现这个算
法实际上很复杂。代码大致如下：
<%
function getallid(oconn,fid)
dim strtemp
if fid=-1 then
strtemp = ""
else
strtemp =","
end if
strsql = "select name from catalog where fatherid="&fid
set rscatalog = oconn.execute(strsql)
do while not rscatalog.eof
strtemp=strtemp&rscatalog("id")&getallid(oconn,catalog("id")) rem 递归调用
loop
rscatalog.close
getallid = strtemp
end function
rem strconn–连接数据库的字符串，请根据情况修改
set oconn = server.createobject("adodb.connection")
oconn.open strconn
fid = request.querystring("fid")
strsql = "select top 100 * from product where fatherid in ("&getallid(oconn,fid)&")"
set rsproduct=oconn.execute(strsql)
%>
<ul><%
do while not rsproduct.eof
%>
<li><%=rsproduct("name")%>
<%
loop
%>
</ul>
<%rsproduct.close
oconn.close
%>
这个算法有很多缺点。试列举几个如下：
1、 由于我们需要查询fid下的所有分类，当分类非常多时，算法将非常地不经济，而且，由于要构造一个很大的
strsql，试想如果有1000个分类，这个strsql将很大，能否执行就是一个问题。
2、 我们知道，在sql中使用in子句的效率是非常低的。这个算法不可避免地要使用in子句，效率很低。
我发现80%以上的程序员钟爱这样的算法，并在很多系统中大量地使用。细心的程序员会发现他们写出了很慢的程序，
但苦于找不到原因。他们反复地检查sql的执行效率，提高机器的档次，但效率的增加很少。
最根本的问题就出在这个算法本身。算法定了，能够再优化的机会就不多了。我们下面来介绍一种算法，效率将是上面算
法的10倍以上。
分类编码算法
问题就出在前面我们采用了顺序编码，这是一种最简单的编码方法。大家知道，简单并不意味着效率。实际上，编码
科学是程序员必修的课程。下面，我们通过设计一种编码算法，使分类的编号id中同时包含了其父类的信息。一个五级分
类的例子如下：
此例中，用32(4+7+7+7+7)位整数来编码，其中，第一级分类有4位，可以表达16种分类。第二级到第五级分类分别有7
位，可以表达128个子分类。
显然，如果我们得到一个编码为 1092787200 的分类，我们就知道：由于其编码为
0100 0001001 0001010 0111000 0000000
所以它是第四级分类。其父类的二进制编码是0100 0001001 0001010 0000000 0000000，十进制编号为1092780032。
依次我们还可以知道，其父类的父类编码是0100 0001001 0000000 0000000 0000000，其父类的父类的父类编码是0100
0000000 0000000 0000000 0000000。(我是不是太罗嗦了j，但这一点很重要。再回头看看我们前面提到的第五个问题。哈
哈，这不就已经得到了分类1092787200所在的分类路径了吗？)。
现在我们在一般的情况下来讨论类别编码问题。设类别的层次为k，第i层的编码位数为ni， 那么总的编码位数为n
(n1+n2+..+nk)。我们就得到任何一个类别的编码形式如下：
2^(n-(n1+n2+…+ni))*j + 父类编码
其中，i表示第i层，j表示当前层的第j个分类。
这样我们就把任何分类的编码分成了两个部分，其中一部分是它的层编码，一部分是它的父类编码。
由下面公式定一的k个编码我们称为特征码：（因为i可以取k个值，所以有k个）
2^n-2^(n-(n1+n2+…+ni))
对于任何给定的类别id，如果我们把id和k个特征码"相与"，得到的非0编码，就是其所有父类的编码！
位编码算法
对任何顺序编码的catalog表，我们可以设计一个位编码算法，将所有的类别编码规格化为位编码。在具体实现时，我们先
创建一个临时表：
create tempcatalog(
[oldid] [int] not null,
[newid] [int] not null,
[oldfatherid] [int] not null,
[newfatherid] [int] not null
);
在这个表中，我们保留所有原来的类别编号oldid和其父类编号oldfatherid，以及重新计算的满足位编码要求的相应
编号newid、newfatherid。
程序如下：
<%
rem oconn—数据库连接，已经打开
rem oldfather—原来的父类编号
rem newfather—新的父类编号
rem n—编码总位数
rem ni–每一级的编码位数数组
rem level–当前的级数
sub formatallid(oconn,oldfather,newfather,n,nm,ni byref,level)
strsql = "select catalogid , fatherid from catalog where fatherid=" & oldfather
set rscatalog=oconn.execute( strsql )
j = 1
do while not rscatalog.eof
i = 2 ^(n – nm) * j
if level then i= i + newfather
oldcatalog = rscatalog("catalogid")
newcatalog = i
rem 写入临时表
strsql = "insert into tempcatalog (oldcatalogid , newcatalogid , oldfatherid , newfatherid)"
strsql = strsql & " values(" & oldcatalog & " , " & newcatalog & " , " & oldfather & " , " & newfather
& ")"
conn.execute strsql
rem 递归调用formatallid
nm = nm + ni(level+1)
formatallid oconn,oldcatalog , newcatalog ,n,nm,ni,level + 1
rscatalog.movenext
j = j+1
loop
rscatalog.close
end sub
%>
调用这个算法的一个例子如下：
<%
rem 定义编码参数，其中n为总位数，ni为每一级的位数。
dim n,ni(5)
ni(1) = 4
n = ni(1)
for i=2 to 5
ni(i) = 7
n = n + ni(i)
next
rem 打开数据库，创建临时表
strsql = "create tempcatalog( [oldid] [int] not null, [newid] [int] not null, [oldfatherid] [int] not
null, [newfatherid] [int] not null);"
set conn = server.createobject("adodb.connection")
conn.open application("strconn")
conn.execute strsql
rem 调用规格化例程
formatallid conn,-1,-1,n,ni(1),ni,0
rem ————————————————————————
rem 在此处更新所有相关表的类别编码为新的编码即可。
rem ————————————————————————
rem 关闭数据库
strsql= "drop table tempcatalog;"
conn.execute strsql
conn.close
%>
第四个问题
现在我们回头看看第四个问题：怎样得到某个分类下的所有产品。由于采用了位编码，现在问题变得很简单。我们很
容易推算：某个产品属于某个类别的条件是product.fatherid&（catalog.id的特征码）=catalog.id。其中"&"代表位与算
法。这在sql server中是直接支持的。
举例来说：产品所属的类别为：1092787200，而当前类别为1092780032。当前类别对应的特征值为：4294950912，由
于1092787200&4294950912=8537400，所以这个产品属于分类8537400。
我们前面已经给出了计算特征码的公式。特征码并不多，而且很容易计算，可以考虑在global.asa中application_onstart
时间触发时计算出来，存放在application("mark")数组中。
当然，有了特征码，我们还可以得到更加有效率的算法。我们知道，虽然我们采用了位编码，实际上还是一种顺序编
码的方法。表现出第i级的分类编码肯定比第i+1级分类的编码要小。根据这个特点，我们还可以由fid得到两个特征码，其
中一个是本级位特征码fid0，一个是上级位特征码fid1。而产品属于某个分类fid的充分必要条件是：
product.fatherid>fid0 and product.fatherid<fid1
下面的程序显示分类fid下的所有产品。由于数据表product已经对fatherid进行索引，故查询速度极快：
<%
rem oconn—数据库连接，已经打开
rem fid—当前分类
rem fidmark—特征值数组，典型的情况下为application("mark")
rem k—数组元素个数，也是分类的级数
sub getallproduct(oconn,fid,fidmark byref,k)
rem 根据fid计算出特征值fid0,fid1
for i=k to 1
if (fid and fidmark = fid ) then exit
next
strsql = "select name from product where fatherid>"fidmark(i)&" and fatherid<"fidmark(i-1)
set rsproduct=oconn.execute(strsql)%>
<ul><%
do while not rsproduct.eof%>
<li><%=rsproduct("name")
loop%>
</ul><%
rsproduct.close
end sub
%>
关于第5个问题、第6个问题，就留作习题吧。有了上面的位编码，一切都应该迎刃而解。
