Problems to solve the classification algorithm
In the construction of the website, the application of the classification algorithm is very common. When designing an electronic store, you should involve a commodity classification; when designing a publishing system, it is related to the column or channel classification; when the design software downloads such a program, it is related to the software classification; so, wait. It can be said that classification is a very common problem.
Classification coding algorithm
The problem is in front of us using the order code, which is the simplest encoding method. Everyone knows that it doesn't mean efficiency. In fact, coding science is a programmer compulsory course. Below, we use an encoding algorithm to enable the information of the category number to simultaneously contain its parent classes. Examples of a five-level classification are as follows:
In this case, encoded with 32 (4 7 7 7 7) bits, wherein the first stage classification has 4 bits, and 16 classifications can be expressed. The second level to the fifth class is 7 bits, and 128 subclass can be expressed.
Obviously, if we get a classification encoded to 1092787200, we know: due to its encoding
0100 0001001 0001010 0111000 0000000
So it is the fourth class classification. The binary code of its parent class is 0100 0001001 0001010 0000000 0000000, and the decimal number is 1092780032. In turn, we can also know that the parent class code of its parent class is 0100 0001001 0000000 0000000 0000000, the parent class of the parent class of his parent class is 0100 0000000 0000000 0000000 0000000. (I am too arrogant, but this is very important. I look back to see the fifth question we mentioned earlier. Haha, this is not the classification path of the category 1092787200?).
Now we discuss the category code in general. The level of the category is K, the number of encoding bits of the i-th layer is Ni, then the total number of encoding bits is n (N1 N2 . NK). We get any category of codes as follows:
2 ^ (N- (N1 N2 Ni)) * J Parent Code
Wherein, i represents the clip, j represents the JR code of the current layer.
In this way, we divide any coded encoding into two parts, some of which are its layer coding, part of its parent class code.
K a K code we set by the following formula: (because i can take K value, so there is k)
2 ^ n-2 ^ (N- (N1 N2 ... NI)))
For any given category ID, if we "phase with K", "the non-0 encoding is the code of all the parent class!
Bit coding algorithm
For any order encoded Catalog table, we can design a bit coding algorithm that encodes all category codes. When implementing, let's create a temporary table:
Create Tempcatalog
[Oldid] [INT] NOT NULL,
[Newid] [int] Not null,
[Oldfatherid] [int] not null,
[Newfatherid] [int] Not null
);
In this table, we reserve all the original category number Oldid and its parent class number OldfatherID, and the corresponding number NEWID, NewFatherId that satisfies bit coding requirements.
The procedure is as follows:
<%
Rem Oconn --- Database connection, already opened
REM oldfather --- the original parent class number
Rem newfather --- new parent class number
Rem N --- Code REM NI - Code Bits Each Level Number
Rem level - current 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 writes a temporary table
Strsql = "INSERT INTO TEMPCATALOG (Oldcatalog, Newcatalog, NewfatherID"
Strsql = strsql & "VALUES (" & Oldcatalog & "," & Newfather & "," & newfather & "
"
Conn.execute strsql
REM recursive call 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
%>
An example of calling this algorithm is as follows:
<%
REM Defines the encoding parameters, where n is the total number, ni is the number of bits per level.
DIM N, NI (5)
Ni (1) = 4
N = ni (1)
For i = 2 TO 5
Ni (i) = 7
N = n ni (i)
NEXT
REM Opens the database, create a temporary table
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 call specifications routine
Formatallid CONN, -1, -1, N, Ni (1), Ni, 0
Rem ------------------------------------- -----------------------
REM updates the category of all related tables here to new encoding.
Rem ------------------------------------- -----------------------
REM Close Database
strsql = "Drop Table Tempcatalog;"
Conn.execute strsqlconn.close
%>
Fourth problem
Now let's look back at the fourth question: How to get all the products under certain categories. Due to the use of bitcodes, the problem is now simple. We are easy to estimate: a product belongs to a category is Product.fatherID & (Specifier of Catalog.ID) = Catalog.ID. Where "&" represents the bit and algorithm. This is directly supported in SQL Server.
For example: the category belongs to: 1092787200, and the current category is 1092780032. The current category corresponds to: 4294950912, because 1092787200 & 4294950912 = 8537400, this product belongs to classification 8537400.
We have given a formula for calculating the feature code. There are not many features, and it is easy to calculate, consider calculating when the Application_onstart time trigger in Global.asa is triggered, stored in an APPLICATION ("Mark") array.
Of course, there is a signature, we can also get more efficient algorithms. We know, although we use bit coding, it is actually a way to encode. The classification coding of Group I is definitely smaller than the coding of the i 1 class. According to this feature, we can also get two signatures from the FID, one of which is the characteristic code FID0 of this level, one is the upper level feature code FID1. The full essential condition that the product belongs to a classification FID is:
Product.fatherID> FID0 and product.fatherid The following program shows all products under the classification FID. Since the data table product has indexed FatherID, the query speed is extremely fast: <% Rem Oconn --- Database connection, already opened REM FID --- Current classification REM FIDMARK --- The characteristic value array, typical case is Application ("Mark") REM K - the number of array elements, is also the classification of classification Sub getAllProduct (Oconn, Fid, Fidmark Byref, K) 'Calculate the characteristic value FID0, FID1 according to FID For i = k to 1 IF (FID and FIDMARK = FID) THEN EXIT NEXT strsql = "Select Name from Product Where Father>" Fidmark (i) & "and FatherId <" FIDMARK (I-1) Set RsProduct = Oconn.execute (strsql)%> <%
Do While Not RsProduct.eof%>
LOOP%>
<%
Rsproduct.close
End Sub
%>
