趣谈分类检索算法

Author: Date: 1996-05-10

        你的电话号码是七位数吧,那好,我就电话号码向你提问题,你用是或否来回答。你可能觉得难以相信,我最多提24次问题就能准确无误地猜出你差不多有1000万种可能性的电话号码!我的方法是对分法,类似这样提问:电话号码是否大于500万?是否大于750万(或是否大于250万)等等,每一个提问将可能的情况压缩一半,这样问了24次后就一定能找到你的电话号码。这种方法就是所谓的对分查找法。其实,对分24次能够找出1到224(16777216)之间的任意一个数字,远大于七位电话号码数。
        对分法是将对象分成两部分,当将对象分成三部分查找时即所谓的三分法,三分法可以用一个小戏法来生动也演示:取任意33=27张扑克牌,你记住其中的任意一张,我把牌平均分成3堆,每堆9张,你告诉我哪一堆中藏有你记住的那张牌。然后我把所有牌收起来,再均分成3堆,你再指出哪一堆中有你记住的牌,我再收起来分成3堆,你再指出,如此共三次,最后一次收牌后,我翻开最上面的一张牌,此即你选中的那张牌!这个戏法的奥秘很简单,我每次收牌时总是把包含有你选中牌的那一堆牌放在最上面(背面朝上),然后再一张一张轮流地分成3堆,这样第一次收牌后,你选的那张牌肯定在前9张之内;第二次收牌后肯定在前3张之内;第三次肯定在第1张的位置!对于27个数字,如果用对分法的话,需要5次(25=32,24=16)才能找出,用三分法只需要3次,这个例子说明三分法在某种情况下比对分法更为有效,可以少提问几次,当然提问的形式就不再是简单的“是”、“否”这种形式了。计算机正是利用上述几种分类检索算法将对象进行分类来检索的,在信息检索中发挥了相当重要的作用。