分類算法要解決的問(wèn)題
在網(wǎng)站建設(shè)中，分類算法的應(yīng)用非常的普遍。在設(shè)計(jì)一個(gè)電子商店時(shí)，要涉及到商品分類；在設(shè)計(jì)發(fā)布系統(tǒng)時(shí)，要涉及到欄目或者頻道分類；在設(shè)計(jì)軟件下載這樣的程序時(shí)，要涉及到軟件的分類；如此等等。可以說(shuō)，分類是一個(gè)很普遍的問(wèn)題。

我常常面試一些程序員，而且我?guī)缀鹾翢o(wú)例外地要問(wèn)他們一些關(guān)于分類算法的問(wèn)題。下面的舉幾個(gè)我常常詢問(wèn)的問(wèn)題。你認(rèn)為你可以很輕松地回答么^_^.

1、分類算法常常表現(xiàn)為樹(shù)的表示和遍歷問(wèn)題。那么，請(qǐng)問(wèn)：如果用數(shù)據(jù)庫(kù)中的一個(gè)Table來(lái)表達(dá)樹(shù)型分類，應(yīng)該有幾個(gè)字段？
2、如何快速地從這個(gè)Table恢復(fù)出一棵樹(shù)；
3、如何判斷某個(gè)分類是否是另一個(gè)分類的子類；
4、如何查找某個(gè)分類的所有產(chǎn)品；
5、如何生成分類所在的路徑。
6、如何新增分類；

在不限制分類的級(jí)數(shù)和每級(jí)分類的個(gè)數(shù)時(shí)，這些問(wèn)題并不是可以輕松回答的。本文試圖解決這些問(wèn)題。

分類的數(shù)據(jù)結(jié)構(gòu)
我們知道：分類的數(shù)據(jù)結(jié)構(gòu)實(shí)際上是一棵樹(shù)。在《數(shù)據(jù)結(jié)構(gòu)》課程中，大家可能學(xué)過(guò)Tree的算法。由于在網(wǎng)站建設(shè)中我們大量使用數(shù)據(jù)庫(kù)，所以我們將從Tree在數(shù)據(jù)庫(kù)中的存儲(chǔ)談起。

為簡(jiǎn)化問(wèn)題，我們假設(shè)每個(gè)節(jié)點(diǎn)只需要保留Name這一個(gè)信息。我們需要為每個(gè)節(jié)點(diǎn)編號(hào)。編號(hào)的方法有很多種。在數(shù)據(jù)庫(kù)中常用的就是自動(dòng)編號(hào)。這在Access、SQL Server、Oracle中都是這樣。假設(shè)編號(hào)字段為ID。

為了表示某個(gè)節(jié)點(diǎn)ID1是另外一個(gè)節(jié)點(diǎn)ID2的父節(jié)點(diǎn)，我們需要在數(shù)據(jù)庫(kù)中再保留一個(gè)字段，說(shuō)明這個(gè)分類是屬于哪個(gè)節(jié)點(diǎn)的兒子。把這個(gè)字段取名為FatherID。如這里的ID2，其FatherID就是ID1。

這樣，我們就得到了分類Catalog的數(shù)據(jù)表定義：

Create Table [Catalog](

        [ID] [int]  NOT NULL,

        [Name] [nvarchar](50) NOT NULL,

        [FatherID]  [int] NOT NULL

);

約定：我們約定用-1作為最上面一層分類的父親編碼。編號(hào)為-1的分類。這是一個(gè)虛擬的分類。它在數(shù)據(jù)庫(kù)中沒(méi)有記錄。

如何恢復(fù)出一棵樹(shù)
上面的Catalog定義的最大優(yōu)勢(shì)，就在于用它可以輕松地恢復(fù)出一棵樹(shù)—分類樹(shù)。為了更清楚地展示算法，我們先考慮一個(gè)簡(jiǎn)單的問(wèn)題：怎樣顯示某個(gè)分類的下一級(jí)分類。我們知道，要查詢某個(gè)分類FID的下一級(jí)分類，SQL語(yǔ)句非常簡(jiǎn)單：

select Name from catalog where FatherID=FID

顯示這些類別時(shí)，我們簡(jiǎn)單地用<LI>來(lái)做到：

    

<%

REM oConn---數(shù)據(jù)庫(kù)連接，調(diào)用GetChildren時(shí)已經(jīng)打開(kāi)

REM FID-----當(dāng)前分類的編號(hào)



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

%>

現(xiàn)在我們來(lái)看看如何顯示FID下的所有分類。這需要用到遞歸算法。我們只需要在GetChildren函數(shù)中簡(jiǎn)單地對(duì)所有ID進(jìn)行調(diào)用：GetChildren(oConn,Catalog(“ID”))就可以了。

<%

REM oConn---數(shù)據(jù)庫(kù)連接，已經(jīng)打開(kāi)

REM FID-----當(dāng)前分類的編號(hào)



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分類的所有子分類的任務(wù)。要顯示所有的分類，只需要如此調(diào)用就可以了：

<%

REM strConn--連接數(shù)據(jù)庫(kù)的字符串，請(qǐng)根據(jù)情況修改

set oConn = Server.CreateObject("ADODB.Connection")

oConn.Open strConn

=GetChildren(oConn,-1)

oConn.Close

%>



如何查找某個(gè)分類的所有產(chǎn)品；
現(xiàn)在來(lái)解決我們?cè)谇懊嫣岢龅牡谒膫�(gè)問(wèn)題。第三個(gè)問(wèn)題留作習(xí)題。我們假設(shè)產(chǎn)品的數(shù)據(jù)表如下定義：

Create Table Product(

            [ID] [int] NOT NULL,

            [Name] [nvchar] NOT NULL,

            [FatherID]  [int] NOT NULL

);

其中，ID是產(chǎn)品的編號(hào)，Name是產(chǎn)品的名稱，而FatherID是產(chǎn)品所屬的分類。

對(duì)第四個(gè)問(wèn)題，很容易想到的辦法是：先找到這個(gè)分類FID的所有子類，然后查詢所有子類下的所有產(chǎn)品。實(shí)現(xiàn)這個(gè)算法實(shí)際上很復(fù)雜。代碼大致如下：

<%

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 遞歸調(diào)用

         Loop

         rsCatalog.Close

         

         GetAllID = strTemp

End Function



REM strConn--連接數(shù)據(jù)庫(kù)的字符串，請(qǐng)根據(jù)情況修改

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

%>

這個(gè)算法有很多缺點(diǎn)。試列舉幾個(gè)如下：

1、            由于我們需要查詢FID下的所有分類，當(dāng)分類非常多時(shí)，算法將非常地不經(jīng)濟(jì)，而且，由于要構(gòu)造一個(gè)很大的strSQL，試想如果有1000個(gè)分類，這個(gè)strSQL將很大，能否執(zhí)行就是一個(gè)問(wèn)題。

2、            我們知道，在SQL中使用In子句的效率是非常低的。這個(gè)算法不可避免地要使用In子句，效率很低。



我發(fā)現(xiàn)80%以上的程序員鐘愛(ài)這樣的算法，并在很多系統(tǒng)中大量地使用。細(xì)心的程序員會(huì)發(fā)現(xiàn)他們寫(xiě)出了很慢的程序，但苦于找不到原因。他們反復(fù)地檢查SQL的執(zhí)行效率，提高機(jī)器的檔次，但效率的增加很少。

最根本的問(wèn)題就出在這個(gè)算法本身。算法定了，能夠再優(yōu)化的機(jī)會(huì)就不多了。我們下面來(lái)介紹一種算法，效率將是上面算法的10倍以上。

分類編碼算法
問(wèn)題就出在前面我們采用了順序編碼，這是一種最簡(jiǎn)單的編碼方法。大家知道，簡(jiǎn)單并不意味著效率。實(shí)際上，編碼科學(xué)是程序員必修的課程。下面，我們通過(guò)設(shè)計(jì)一種編碼算法，使分類的編號(hào)ID中同時(shí)包含了其父類的信息。一個(gè)五級(jí)分類的例子如下：




此例中，用32(4+7+7+7+7)位整數(shù)來(lái)編碼，其中，第一級(jí)分類有4位，可以表達(dá)16種分類。第二級(jí)到第五級(jí)分類分別有7位，可以表達(dá)128個(gè)子分類。

顯然，如果我們得到一個(gè)編碼為 1092787200 的分類，我們就知道：由于其編碼為

        0100 0001001 0001010 0111000 0000000

所以它是第四級(jí)分類。其父類的二進(jìn)制編碼是0100 0001001 0001010 0000000 0000000，十進(jìn)制編號(hào)為1092780032。依次我們還可以知道，其父類的父類編碼是0100 0001001 0000000 0000000 0000000，其父類的父類的父類編碼是0100 0000000 0000000 0000000 0000000。(我是不是太羅嗦了J，但這一點(diǎn)很重要。再回頭看看我們前面提到的第五個(gè)問(wèn)題。哈哈，這不就已經(jīng)得到了分類1092787200所在的分類路徑了嗎？)。

現(xiàn)在我們?cè)谝话愕那闆r下來(lái)討論類別編碼問(wèn)題。設(shè)類別的層次為k，第i層的編碼位數(shù)為Ni， 那么總的編碼位數(shù)為N(N1+N2+..+Nk)。我們就得到任何一個(gè)類別的編碼形式如下：

2^(N-(N1+N2+…+Ni))*j + 父類編碼

其中，i表示第i層，j表示當(dāng)前層的第j個(gè)分類。

這樣我們就把任何分類的編碼分成了兩個(gè)部分，其中一部分是它的層編碼，一部分是它的父類編碼。

由下面公式定一的k個(gè)編碼我們稱為特征碼：（因?yàn)閕可以取k個(gè)值，所以有k個(gè)）

2^N-2^(N-(N1+N2+…+Ni))

對(duì)于任何給定的類別ID，如果我們把ID和k個(gè)特征碼“相與”，得到的非0編碼，就是其所有父類的編碼！



位編碼算法
對(duì)任何順序編碼的Catalog表，我們可以設(shè)計(jì)一個(gè)位編碼算法，將所有的類別編碼規(guī)格化為位編碼。在具體實(shí)現(xiàn)時(shí)，我們先創(chuàng)建一個(gè)臨時(shí)表：

Create TempCatalog(

            [OldID] [int] NOT NULL,

            [NewID] [int] NOT NULL,

            [OldFatherID] [int] NOT NULL,

            [NewFatherID] [int] NOT NULL

);

在這個(gè)表中，我們保留所有原來(lái)的類別編號(hào)OldID和其父類編號(hào)OldFatherID，以及重新計(jì)算的滿足位編碼要求的相應(yīng)編號(hào)NewID、NewFatherID。

程序如下：

<%

REM oConn---數(shù)據(jù)庫(kù)連接，已經(jīng)打開(kāi)

REM OldFather---原來(lái)的父類編號(hào)

REM NewFather---新的父類編號(hào)

REM N---編碼總位數(shù)

REM Ni--每一級(jí)的編碼位數(shù)數(shù)組

REM Level--當(dāng)前的級(jí)數(shù)



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 寫(xiě)入臨時(shí)表

                                         strSQL = "Insert into TempCatalog (OldCatalogID , NewCatalogID , OldFatherID , NewFatherID)"

                                         strSQL = strSQL & " values(" & OldCatalog & " , " & NewCatalog & " , " & OldFather & " , " & NewFather & ")"



                                         Conn.Execute strSQL

                                         

                                         REM 遞歸調(diào)用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

%>



調(diào)用這個(gè)算法的一個(gè)例子如下：

<%

REM 定義編碼參數(shù)，其中N為總位數(shù)，Ni為每一級(jí)的位數(shù)。

                 Dim N,Ni(5)

                 

                 Ni(1) = 4

                 

                 N = Ni(1)

                 

                 for i=2 to 5

                                         Ni(i) = 7

                                         N = N + Ni(i)

                 next

                 

REM 打開(kāi)數(shù)據(jù)庫(kù)，創(chuàng)建臨時(shí)表   

                 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 調(diào)用規(guī)格化例程

                 FormatAllID Conn,-1,-1,N,Ni(1),Ni,0



REM ------------------------------------------------------------------------

REM 在此處更新所有相關(guān)表的類別編碼為新的編碼即可。

REM ------------------------------------------------------------------------



REM 關(guān)閉數(shù)據(jù)庫(kù)

                 strSQL= "drop table TempCatalog;"

                 Conn.Execute strSQL

                 Conn.Close

%>



第四個(gè)問(wèn)題
現(xiàn)在我們回頭看看第四個(gè)問(wèn)題：怎樣得到某個(gè)分類下的所有產(chǎn)品。由于采用了位編碼，現(xiàn)在問(wèn)題變得很簡(jiǎn)單。我們很容易推算：某個(gè)產(chǎn)品屬于某個(gè)類別的條件是Product.FatherID&（Catalog.ID的特征碼）=Catalog.ID。其中“&”代表位與算法。這在SQL Server中是直接支持的。

舉例來(lái)說(shuō)：產(chǎn)品所屬的類別為：1092787200，而當(dāng)前類別為1092780032。當(dāng)前類別對(duì)應(yīng)的特征值為：4294950912，由于1092787200&4294950912=8537400，所以這個(gè)產(chǎn)品屬于分類8537400。

我們前面已經(jīng)給出了計(jì)算特征碼的公式。特征碼并不多，而且很容易計(jì)算，可以考慮在Global.asa中Application_OnStart時(shí)間觸發(fā)時(shí)計(jì)算出來(lái)，存放在Application(“Mark”)數(shù)組中。

當(dāng)然，有了特征碼，我們還可以得到更加有效率的算法。我們知道，雖然我們采用了位編碼，實(shí)際上還是一種順序編碼的方法。表現(xiàn)出第I級(jí)的分類編碼肯定比第I+1級(jí)分類的編碼要小。根據(jù)這個(gè)特點(diǎn)，我們還可以由FID得到兩個(gè)特征碼，其中一個(gè)是本級(jí)位特征碼FID0，一個(gè)是上級(jí)位特征碼FID1。而產(chǎn)品屬于某個(gè)分類FID的充分必要條件是：

Product.FatherID>FID0 and Product.FatherID<FID1

下面的程序顯示分類FID下的所有產(chǎn)品。由于數(shù)據(jù)表Product已經(jīng)對(duì)FatherID進(jìn)行索引，故查詢速度極快：

<%

REM oConn---數(shù)據(jù)庫(kù)連接，已經(jīng)打開(kāi)

REM FID---當(dāng)前分類

REM FIDMark---特征值數(shù)組，典型的情況下為Application(“Mark”)

REM k---數(shù)組元素個(gè)數(shù)，也是分類的級(jí)數(shù)

Sub GetAllProduct(oConn,FID,FIDMark byref,k)

                 REM 根據(jù)FID計(jì)算出特征值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

%>

關(guān)于第5個(gè)問(wèn)題、第6個(gè)問(wèn)題，就留作習(xí)題吧。有了上面的位編碼，一切都應(yīng)該迎刃而解。