Infinitus の分類原理と実装

前書き

Infinitus 分類は私がずっと前に学んだものですが、今日あるプロジェクトに取り組んでいたときに、その概念が少し曖昧であることに気づきました。そこで、今日は Infinitus 分類について話します。

まず、無限分類とは何かについて話しましょう。私の理解によれば、同じ木と同じように、根から幹、枝、葉に至るまで、データの複数の分類を完了することです...

無限の分類を完了するには、2 つの主な方法が使用されます。は再帰的方法、2 つ目は反復的方法です。 Infinitus 分類が使用される主な場所には、アドレス解決、ブレッドクラム ナビゲーションなどが含まれます。以下に、2 つの方法の原理と実装方法を詳しく紹介します。

家系図と子孫木

家系図はInfinitus分類の表現の1つであり、もう1つは子孫木です。最初に Infinitus 分類について学び始めたとき、これら 2 つのツリーを混同することがよくありましたが、今ではかなり理解できるようになりました。違いは中国語の意味からもわかります。

家系図は現在多くの場所で人気があります。では、家系図を構築するにはどうすればよいでしょうか? 私の理解によれば、それは自分自身の先祖を見つけて、それを世代から世代へと見つけてシステムを形成することです。家系図と呼ばれます。家系図も同様で、ノードから開始してその親ノードを上に探し、次に親ノードの親ノードが見つからなくなるまで探します。この探索により形成される樹状構造を家系図と呼ぶ。

子孫ツリーはその逆で、生物学の本の遺伝図に似ています。ノードから開始して、その子ノードを検索し、その子ノードの子ノードを検索します。完成しました。このようにして形成されたツリー構造を子孫ツリーと呼びます。

上記の家系図と子孫ツリーの説明から、コードに変換するときの第一印象は、家系図では親ノードの親ノードを見つけ、子孫ツリーでは再帰を使用するということです。子ノードの子ノード。再帰的思考と完全に一致しています。それではまず、再帰を使用して家系図と子孫ツリーを完成させる方法について話しましょう。

再帰的方法

家系図ツリーの実装

より明確に説明するために、まず以下に分類するデータを貼り付けます。これは住所に関するデータです:

$address = array(    array('id'=>1  , 'address'=>'安徽' , 'parent_id' => 0),    array('id'=>2  , 'address'=>'江苏' , 'parent_id' => 0),    array('id'=>3  , 'address'=>'合肥' , 'parent_id' => 1),    array('id'=>4  , 'address'=>'庐阳区' , 'parent_id' => 3),    array('id'=>5  , 'address'=>'大杨镇' , 'parent_id' => 4),    array('id'=>6  , 'address'=>'南京' , 'parent_id' => 2),    array('id'=>7  , 'address'=>'玄武区' , 'parent_id' => 6),    array('id'=>8  , 'address'=>'梅园新村街道', 'parent_id' => 7),    array('id'=>9  , 'address'=>'上海' , 'parent_id' => 0),    array('id'=>10 , 'address'=>'黄浦区' , 'parent_id' => 9),    array('id'=>11 , 'address'=>'外滩' , 'parent_id' => 10)    array('id'=>12 , 'address'=>'安庆' , 'parent_id' => 1)    );

上記の紹介に従って、家系図を作成します。上記のデータ Infinitus 分類に基づいて、ダヤンタウンの家系図を見つけたいとします。まず、それに関連する情報を見つけます。

'id'=>5  , 'address'=>'大杨镇' , 'parent_id' => 4

親ノードの ID (parent_id == 4) が表示され、id == 4 のノードがその親ノードとなり、Luyang District を見つけます:

'id'=>4  , 'address'=>'庐阳区' , 'parent_id' => 3

上記と同様に、 id=3 のノードを検索して、大陽鎮の家系図を見つけます

大陽鎮-> 合肥->

では、コードで完成させるにはどうすればよいでしょうか?実際、これは非常に簡単です。探している親 ID がノードの ID と等しいかどうかを判断するだけです。つまり、parent_id ?= id が等しい場合、それが探している親ノードです。 、ノードのparent_idを探しているIDとして使用し、再帰的に検索します。以下のフローチャートに示すように:

家系図を見つけるための再帰的メソッド

コードの記述を開始します:

/** * 获取家谱树 * @param   array        $data   待分类的数据 * @param   int/string   $pid    要找的祖先节点 */function Ancestry($data , $pid) {    static $ancestry = array();    foreach($data as $key => $value) {        if($value['id'] == $pid) {            $ancestry[] = $value;            Ancestry($data , $value['parent_id']);        }    }    return $ancestry;}

フローチャートに従って、コードが記述されます。上記のノードを格納する配列、つまり $ancestry には静的キーワード static を追加する必要があることに注意してください。追加しない場合、配列は再帰されるたびに初期化されます。もちろん、array_merge を使用して、返された各配列を前の配列とマージすることもできます。

家系図を見つけるための鍵は、探しているparent_idが特定のノードのID値に等しいという条件判断です。明らかに、このノードが探している親ノードです。

コードが書かれています。ダヤンタウンの家系図を探してみましょう:

Ancestry($address , 4);

結果:

Array(    [0] => Array        (            [id] => 4            [address] => 庐阳区            [parent_id] => 3        )    [1] => Array        (            [id] => 3            [address] => 合肥            [parent_id] => 1        )    [2] => Array        (            [id] => 1            [address] => 安徽            [parent_id] => 0        ))

結果が期待と一致していることがわかります。これで家系図の再帰的メソッドが完成しました。子孫ツリーの実装について話しましょう。

子孫ツリーの実装

上記のデータを引き続き使用すると、子孫ツリーは、親ノードから開始して子孫ノードを下方向に見ることによって形成されるツリー形状です。

id=0 の子孫ノードを探していると仮定すると、parent_id=0 のすべてのノードに注意する必要があります。これらのノードはすべて id=0 の子ノードです。次に、parent_id=0 ノードの ID をクエリ ID として使用し、子ノードが見つからなくなるまで下方向にクエリを続けます。

子孫ツリー

フローチャートは次のとおりです:

子孫ツリー フローチャート

プロセスは家系図と似ていますが、相違点と重要な点は条件文の実行です。ファミリーツリーは現在のノードのidが前のノードのparent_idと等しいかどうかを判断し、子孫ツリーは現在のノードのparent_idが前のノードのidと等しいかどうかを判断します。子孫ツリーには複数の子孫ノードを含めることができ、家系ツリーには 1 つの祖先のみを含めることができます。コードは次のとおりです。

/** * 获取子孙树 * @param   array        $data   待分类的数据 * @param   int/string   $id     要找的子节点id * @param   int          $lev    节点等级 */ function getSubTree($data , $id = 0 , $lev = 0) {     static $son = array();     foreach($data as $key => $value) {         if($value['parent_id'] == $id) {             $value['lev'] = $lev;             $son[] = $value;             getSubTree($data , $value['id'] , $lev+1);         }     }     return $son; }

この関数では、子孫ツリーの構造が簡単にわかるように、保存されたノードのレベルをマークする変数 lev を追加しました。以下の結果をテストしてみましょう:

getSubTree($data , 0 , 0);

スペースが限られているため、結果は部分的に処理されています:

foreach($tree as $k => $v) {    echo str_repeat('--' , $v['lev']) . $v['address'] . '<br/>';}

結果:

安徽--合肥----庐阳区------大杨镇--安庆江苏--南京----玄武区------梅园新村街道上海--黄浦区----外滩

递归方式的家谱树与子孙树比较容易理解，只要对递归思想比较了解，一步步写下来不是很难。比起递归方式，迭代方式可能更加让人难以理解。下面就来介绍迭代方式的家谱树与子孙树编写。

迭代方式

家谱树

完成跌代方式的家谱树之前，首先说一下寻找祖先节点的终止条件。虽然叫无限极分类，它不是绝对的无限，只是理论的无限。

如同我国上下五千年历史，任一个大的姓氏，向上找其祖先，不是找到炎帝就是找到黄帝，在往前就没有历史记载了。所以在家谱树的寻找中也有终止条件，就是在分类数据中再也找不到它的父节点时，表现在实例数据上，就是不存在parent_id < 0的节点。

这也是完成迭代的关键，以其作为迭代条件，对数据进行循环判断，并把每次找到的节点的parent_id再次作为迭代条件，直到不满足迭代条件。流程图如下：

家谱树迭代流程

理清流程，现在开始完成代码编写：

function Ancestry($data , $pid) {    $ancestry = array();    while($pid > 0) {        foreach($data as $v) {            if($v['id'] == $pid) {                $ancestry[] = $v;                $pid = $v['parent_id'];            }        }    }    return $ancestry;}

迭代条件$pid>0，当pid>0时说明还有祖先存在，可以继续迭代，否则说明没有祖先，迭代终止。$pid = $v['parent_id']是迭代继续进行的关键，每次找到祖先节点，就将祖先节点的父id传递给pid，进行下一次迭代。

运行这个函数，结果与使用递归方式的结果一致。

子孙树的实现

使用迭代方式完成子孙树，更为复杂，需要运用的栈的思想。在进行迭代的过程中，将每次寻找的id入栈，找到一个节点，就将该节点从原数据中删除，当寻找到叶子节点时，即不存在子孙节点时，就将该叶子节点对应的id从栈中弹出，再寻找栈顶id的子孙节点，直到栈清空为止，迭代结束。下面用一个例子来说明：

$address = array(    array('id'=>1  , 'address'=>'安徽' , 'parent_id' => 0),    array('id'=>2  , 'address'=>'江苏' , 'parent_id' => 0),    array('id'=>3  , 'address'=>'合肥' , 'parent_id' => 1),    array('id'=>4  , 'address'=>'庐阳区' , 'parent_id' => 3),    array('id'=>5  , 'address'=>'大杨镇' , 'parent_id' => 4),    array('id'=>6  , 'address'=>'南京' , 'parent_id' => 2),    array('id'=>7  , 'address'=>'玄武区' , 'parent_id' => 6),    array('id'=>8  , 'address'=>'梅园新村街道', 'parent_id' => 7),    array('id'=>9  , 'address'=>'上海' , 'parent_id' => 0),    array('id'=>10 , 'address'=>'黄浦区' , 'parent_id' => 9),    array('id'=>11 , 'address'=>'外滩' , 'parent_id' => 10)    array('id'=>12 , 'address'=>'安庆' , 'parent_id' => 1)    );

寻找id=0的子孙节点，id=0入栈，寻找到该节点，为

array('id'=>1  , 'address'=>'安徽' , 'parent_id' => 0)

此时栈为[0]，并且将该节点从原数据中删除，再将id=1入栈，寻找id=1的子孙节点，找到为：

array('id'=>3  , 'address'=>'合肥' , 'parent_id' => 1),

此时栈[0][1],将该节点删除，id=3入栈，寻找id=3的子孙节点，找到：

array('id'=>4  , 'address'=>'庐阳区' , 'parent_id' => 3)

栈[0][1][3]，将该节点删除，id=4入栈，寻找id=4的子孙节点，找到：

array('id'=>5  , 'address'=>'大杨镇'         , 'parent_id' => 4),

栈[0][1][3][4]，将该节点删除，id=5入栈，栈[0][1][3][4][5]，并寻找id=5的子节点，遍历后未找到，于是将id=5出栈，再次寻找id=4的子孙节点，依次进行。最后完成整个迭代。

期间，栈的情况如下：

[0][0][1][0][1][3][0][1][3][4][0][1][3][4][5][0][1][3][4][0][1][3][0][1][0][1][12][0][1][0]……

代码如下：

function getSubTree($data , $id = 0) {    $task = array($id);                          # 栈 任务表    $son = array();    while(!empty($task)) {        $flag = false;                           # 是否找到节点标志        foreach($data as $k => $v) {            # 判断是否是子孙节点的条件 与 递归方式一致            if($v['parent_id'] == $id) {                $son[] = $v;                     # 节点存入数组                array_push($task , $v['id']);    # 节点id入栈                $id = $v['id'];                  # 判断条件切换                unset($data[$k]);                # 删除节点                $flag = true;                    # 找到节点标志            }        }        # flag == false说明已经到了叶子节点 无子孙节点了        if($flag == false) {            array_pop($task);                    # 出栈            $id = end($task);                    # 寻找栈顶id的子节点        }    }    return $son;}

这里找到节点后必须把该节点从原数据中删除，否则会造成每次都找到该节点，形成无限迭代的bug。在这里利用数组函数array_push与array_pop模拟进栈与出栈操作。

利用迭代完成子孙树比较复杂，且我没有测试过这个与递归方式谁的效率高，不过利用迭代完成家谱树明显比起递归方法效率高。

应用

面包屑导航

说完了无限极分类的实现原理与方法，现在来说说在网站中对无限极分类的应用。最常用的就是面包屑导航了。

什么是面包屑导航，这个称呼来自于童话故事"汉赛尔和格莱特"，具体什么故事就不叙述了，有兴趣的可以去谷歌一下。面包屑导航的作用就是告诉访问者他们目前在网站中的位置以及如何返回。下图就是一个典型的面包屑导航。

面包屑导航

面包屑是一个典型家谱树的应用，不要看它是从左到右，分类级数越来越低，就认为它是子孙树应用，要知道子孙树是可能存在多个分支，而面包屑导航要求的是一条主干。

将上面家谱树代码做一定修改，就能够完成面包屑导航。我们采用递归方式的家谱树。代码如下：

function Ancestry($data , $pid) {    static $ancestry = array();    foreach($data as $key => $value) {        if($value['id'] == $pid) {            Ancestry($data , $value['parent_id']);            $ancestry[] = $value;                        }    }    return $ancestry;}

如果先进行递归调用，在递归结束再将找到的节点存入数组中，就能够使祖先节点排列在数组前列，子孙节点排列在数组后列，方便进行提取数据。

简化演示步骤，不从数据库中取出数据，改为模拟数据：

 $tmp = array(    array('cate_id'=1 , 'name'=>'首页' , 'parent_id'=>'0'),    array('cate_id'=2 , 'name'=>'新闻中心' , 'parent_id'=>'1'),    array('cate_id'=3 , 'name'=>'娱乐新闻' , 'parent_id'=>'2'),    array('cate_id'=4 , 'name'=>'军事要闻' , 'parent_id'=>'2'),    array('cate_id'=5 , 'name'=>'体育新闻' , 'parent_id'=>'2'),    array('cate_id'=6 , 'name'=>'博客' , 'parent_id'=>'1'),    array('cate_id'=7 , 'name'=>'旅游日志' , 'parent_id'=>'6'),    array('cate_id'=8 , 'name'=>'心情' , 'parent_id'=>'6'),    array('cate_id'=9 , 'name'=>'小小说' , 'parent_id'=>'6'),    array('cate_id'=9 , 'name'=>'明星' , 'parent_id'=>'3'),    array('cate_id'=9 , 'name'=>'网红' , 'parent_id'=>'3')    );

假设用户点进明星导航，那么在网站显示的导航为：

$tree = Ancestry($tmp , 10);foreach ($tree as $key => $value) {    echo $value['name'] . '>';}

面包屑导航

防止设置父类为子类

在网站建立中，可能会碰到用户进行编辑时出现误操作，将某个栏目的父节点设置成了该栏目的子节点，进行这样的设置后会导致数据库中的数据丢失，因此在进行数据更新之前应该注意这一点。

利用家谱树，就能够避免发生这种错误。在用户提交表单时，我们将即将修改栏目的父节点的家谱树取出，并对家谱树进行遍历，如果发现该家谱树中发现了要修改的节点，就说明是错误操作。有点绕，举个例子来说明：

修改栏目新闻中心的父节点为娱乐新闻，就把娱乐新闻的家谱树取出来：

娱乐新闻 新闻中心 首页

在该家谱树中发现要修改的节点，新闻中心，那么说明出现了错误。具体代码如下：

$data = Ancestry($tmp , 3);foreach ($data as $key => $value) {    if($value['cate_id'] == 3) {        echo  'Error';        break;    }}

结语

对无限极分类的讲解就写到这儿，希望能够给对无限极分类存在迷惑的同学一定的灵感。在下才疏学浅，可能在描述中存在错漏，希望看到的同学能够指出。

同时在此，感谢布尔教育的刘道成，即燕十八老师，从他的教学视频中学到很多，这次重新看无限极分类，燕老师的视频给了我很多帮助。再次感谢燕老师。