分类、层级与编码

在使用技术技术解决现实问题时,为了描述客观世界,有时候需要对一个集合中的对象进行分类、分层级。比如一群人,分类可以是男、女、老、友,分层级可以是按年龄少儿、青年、老人,少儿又可层级为新生儿、婴儿和小儿等。

为参与计算,通常会对这些分类和层级进行编码。常见的编码分为两类:一类是有限分类及层级,每层、每类的数量是有限的,比如常见的身份证编码,中国大陆的居民身份证号码由18位组成,前17位为数字,后一位多数人为数字,少数人为字母“X”;另外一类是无限分类及层级,比如计算机中常用的二叉树。

在有限分类及层级中,预先知道对象集合的规模,比如身份证的前6位是行政区编码,

110000    北京市
110100      市辖区
110101        东城区

这6位数分为三组,每两位为一层,如果只用数字来表示的话,意味着在每一层可以画出100个类别来,00-99。上面可以看到,北京市在省区的规划中代码是11,其中市辖区被记为01,也即1101,而东城区作为市辖区的下一级被记为01,也即110101。 这样计算机读取110101,展示给人们的就是北京市市辖区东城区,非直辖市的情况可以参考 -国家统计局 的 行政区划 -R/L2Sk 。与身份证类似,一些地理信息系统,也是采用这种编码的方式类记录地址信息到地址编码的。

如果某一层出现第101个类别怎么办?

有两种思路,一种是继续使用有限分类及层级,扩充每一级上的编码,比如上面的身份证编码,如果出现101个类别,则在每一层又2位扩增到3位,问题得以解决,但无法向前兼容,问题很大。

另外一个思路时,如无无法估量对象集合的数量,或者数量是动态变化调整的,就需要用无限分类及层级。这种分类不去规划每层的宽度和容量,而是扁平的设计成每层每个类别,只需记住自己的“父类”即可,这样各找个家,也可以将一个集合有机的串起来。

计算技术中的数据结构二叉树就是这样来设计,每层只知道parent是哪即可。同样的,我们常见的论坛(BBS)在设计论坛、子论坛和帖子编号时,也是基于这样的思路,因为无法估量某个论坛、子论坛到底会有多少个帖子。

boardId   parentBoardId
threadId  boardId
子    父
孙    子
曾孙   孙

使用这种对应关系即可串起来。

无限分类与层级结构简单,伸缩性极好,但也有不足,比如统计比较困难。比如在有限分类及层级中,只要按一定的分组就可以理出其下所有子类,如11开头的身份证都是北京的,而使用无限分类及层级的话,需要检索出所有parentId为11的记录。在参与进一步的计算时,前者可能是一步,而后者需要两步及以上才能完成。

宛如一个持有代码110101的人和一个持有01代码但直到其父是01的人同时站在面前,前者一看就知道其父、其祖,而后者只能回答其父,如果找其祖,需要使用后一个01再检索一次。

前者的优势是每次所携带的信息容量较大,但同时也耗费更多的空间,实现以空间换时间。

This entry was posted in 社会生活, 计算机技术 and tagged , , . Bookmark the permalink.

发表评论

电子邮件地址不会被公开。 必填项已用*标注