您的位置:首页精文荟萃软件资讯 → 一种效率极高的分类算法

一种效率极高的分类算法

时间:2004/10/7 19:16:00来源:本站整理作者:蓝点我要评论(0)


            
             
              
             
            

               
               

            



            分类算法要解决的问题
在网站建设中,分类算法的应用非常的普遍。在设计一个电子商店时,要涉及到商品分类;在设计发布系统时,要涉及到栏目或者频道分类;在设计软件下载这样的程序时,要涉及到软件的分类;如此等等。可以说,分类是一个很普遍的问题。

我常常面试一些程序员,而且我几乎毫无例外地要问他们一些关于分类算法的问题。下面的举几个我常常询问的问题。你认为你可以很轻松地回答么^_^.


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

显示这些类别时,我们简单地用
  • 来做到:



    <%

    REM oConn---数据库连接,调用GetChildren时已经打开

    REM FID-----当前分类的编号



    Function GetChildren(oConn,FID)

    strSQL = "select ID,Name from catalog where FatherID="&FID

    set rsCatalog = oConn.Execute(strSQL)

    %>



      <%

      Do while not rsCatalog.Eof

      %>

    • <%=rsCatalog("Name")%>

      <%

      Loop

      %>



    <%

    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)

    %>



      <%

      Do while not rsCatalog.Eof

      %>

    • <%=rsCatalog("Name")%>

      <%=GetChildren(oConn,Catalog("ID"))%>



      <%

      Loop

      %>



    <%

    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)

    %>

      <%

      Do while not rsProduct.EOF

      %>

    • <%=rsProduct("Name")%>

      <%

      Loop

      %>



    <%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
    下面的程序显示分类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)%>

      <%

      Do While Not rsProduct.Eof%>

    • <%=rsProduct("Name")

      Loop%>

    <%

    rsProduct.Close

    End Sub

    %>

    关于第5个问题、第6个问题,就留作习题吧。有了上面的位编码,一切都应该迎刃而解。

  • 相关阅读 Windows错误代码大全 Windows错误代码查询激活windows有什么用Mac QQ和Windows QQ聊天记录怎么合并 Mac QQ和Windows QQ聊天记录Windows 10自动更新怎么关闭 如何关闭Windows 10自动更新windows 10 rs4快速预览版17017下载错误问题Win10秋季创意者更新16291更新了什么 win10 16291更新内容windows10秋季创意者更新时间 windows10秋季创意者更新内容kb3150513补丁更新了什么 Windows 10补丁kb3150513是什么

    文章评论
    发表评论

    热门文章 360快剪辑怎么使用 36金山词霸如何屏幕取词百度收购PPS已敲定!3

    最新文章 微信3.6.0测试版更新了微信支付漏洞会造成哪 360快剪辑怎么使用 360快剪辑软件使用方法介酷骑单车是什么 酷骑单车有什么用Apple pay与支付宝有什么区别 Apple pay与贝贝特卖是正品吗 贝贝特卖网可靠吗

    人气排行 xp系统停止服务怎么办?xp系统升级win7系统方电脑闹钟怎么设置 win7电脑闹钟怎么设置office2013安装教程图解:手把手教你安装与qq影音闪退怎么办 QQ影音闪退解决方法VeryCD镜像网站逐个数,电驴资料库全集同步推是什么?同步推使用方法介绍QQ2012什么时候出 最新版下载EDiary——一款好用的电子日记本