一種效率極高的分類算法-ShareBody資訊站

一種效率極高的分類算法

分類算法要解決的問題
在網站建設中，分類算法的應用非常的普遍。在設計一個電子商店時，要涉及到商品分類；在設計發布系統時，要涉及到欄目或者頻道分類；在設計軟件下載這樣的程序時，要涉及到軟件的分類；如此等等。可以說，分類是一個很普遍的問題。

我常常面試一些程序員，而且我幾乎毫無例外地要問他們一些關于分類算法的問題。下面的舉幾個我常常詢問的問題。你認為你可以很輕松地回答么^_^.

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

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

<%=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

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)

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

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個問題，就留作習題吧。有了上面的位編碼，一切都應該迎刃而解。

※以上資訊由網路資料整理而成，若有遺誤概以來源為準，本站不負任何相關責任。

※如果您認為網站上資訊侵犯了您的版權，請告訴我們按這裡，我們將即時將您的版權資料移除。

網頁語言教學

程式語言教學

移動端教學

資料庫

生活資訊

法拍資訊

實價登錄