分类编码生成算法

        在做软件的时候常常会遇到商品分类、栏目、频道分类、权限级别的问题（以下统一称为分类问题），本文试图探讨通用分类算法的设计问题，旨在通过合理设计提高生成树形目录、查询某一分类（可能包含子分类）下所有内容（为了讨论方便暂且以商品为例）的效率。

        最常用的分类设计是通过增加一个父id的字段标识分类的父子关系，这样设计的优点是实现简单、可以无限极分类，不需要分类编码算法；但缺点也是很明显的，最明显的不足就是查询某一分类的所有子类及其商品效率低下，这点不足在生成分类树的时候可以在前台界面利用ajax技术异步获取或通过提前处理的方式把分类取出来放到内存或文件中得到弥补，在只取某一分类下所有商品而不需要得到分类信息时的效率将很难提升。

        在设计分类时如果引入分类编码的概念将有助于提高分类查询的效率。分类编码的关键是分类编码算法，这里提出两种分类编码算法：二进制位编码算法和十进制位编码算法。

        二进制位编码算法

        二进制位编码算法是用一定位数的二进制位对分类进行编码，比如用16（4+6+6）位来编码，第一级用4位表示，可表示2^4=16个编码，第二级、第三级分别用6位表示，可表示64个编码，可根据业务需要调整编码的总位数和每一级的位数。

        显然，如果我们得到一个分类的编码0010 000101 000001，我们就知道这是一个三级分类，其父类是             0010 00010 00000，父类的父类是0010 000000 000000。

        现在我们在一般情况下讨论二进制位编码问题，设类别的级数为k，第i层的编码位数为Ni（1=<i<=k），那么总的编码位数为N（N1+N2+……+Ni），则任何一个编码的形式为2^(N-(N1+N2+…+Ni))*j + pcode，其中i表示第i层分类，j表示第i层的第j个分类，pcode表示父编码的十进制值，这样一个分类的编码就可以分为两部分，一部分层编码2^(N-(N1+N2+…+Ni))*j，另一部分为其父编码。

        采用二进制位编码算法分类设计的优点是：

        分类层级清晰，一目了然

        查询效率高

        缺点是：

        每一级的位数固定，表示的分类个数有限，不太容易支持无限极分类

        分类达到最大数时扩展分类位数和调整每一级的分类位数困难

        总编码长度比较长

        十进制位编码算法

        十进制位编码是每一级采用一定位数十进制数作为编码，每级编码程度固定，用分隔符隔开，编码总长度不固定，比如用4位来编码用“_”作为分隔符。

        如果我们得到一个分类编码0020_1008_9800， 我们就知道这是一个三级分类，其父类是0020_1008，父类的父类是0020。

        这样编码的一般形式是：pcode_j，其中pcode表示父编码，j表示这一级的第j个编码。

        十进制位编码算法分类设计的优点是：

        分类层级清晰，一目了然

        查询效率高

        完美支持无限极分类

        缺点是：

        每一级的位数固定，表示的分类个数有限

        每一级分类个数达到最大数时的调整困难

 

        注：每级采用固定位数的编码是为了分类显示排序方便，如果不需要考虑这点便捷性可以采用不固定位数的编码，这样就真正实现了无限极分类，而且每级分类数量也没有限制。

 

        总结，二进制位编码算法和十进制位编码算法在分类结构设计上已经进步了很多，而且大部分的系统在设计之初就能遇见到系统的最大分类数量，可以在设计时预留空前量来弥补分类个数固定的缺陷。如采用十进制位编码方式，4位编码，每一级能表示9999个分类，这已经能满足大多数系统的要求了。