ptree数据结构分析

2023-11-22 20:58
文章标签 分析 数据结构 ptree

本文主要是介绍ptree数据结构分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！



1.位置

使用时包含头文件ptree.h   还要编译ptree.c文件。


2.数据结构

2.1struct ptree

/* Patricia tree top structure. */
struct ptree
{/* Top node. */struct ptree_node *top;/* Maximum key size allowed (in bits). */u_int32_t max_key_len;/* Identifier of the FIB the tree is for - default is 0 */u_int32_t id;
};

/* Patricia tree node structure. */
struct ptree_node
{struct ptree_node *link[2];
#define  p_left      link[0]
#define  p_right     link[1]/* Tree link. */struct ptree *tree;struct ptree_node *parent;/* Lock of this radix. */u_int32_t lock;/* Each node of route. */void *info;/* Key len (in bits). */u_int32_t key_len;/* Key begins here. */u_int8_t key [1];
};



2.2struct ptree_node

3.1. PAT tree介绍

3.1.1. 应用
  1. PAT tree是目前信息检索领域应用十分成功的索引方法。主要在字符串子串匹配上有着非常优异的表现，采用半无限长字串作为字符串的查找结构。当有了一个文档的所有半无限长字串的集合，该文档的任何子串都可以定位为某一半无限长字串的前缀。
  2. 半无限长字串：就是一串字符的顺序子串(从一给定点到串的结尾)。
    比如一个字符串CUHK，它的半无限长字串：CUHK、UHK、HK和K。
3.1.2. 基本定义
  1. PAT tree是由所有可能的无限长字串所构成的一棵树。在PAT tree中通过逐个鉴别半无限长字串的二进制位来判断树中的分支，如果二进制位是0则产生左分支，是1则产生右分支，因此PAT tree是一棵二叉树，树的结点分为外部结点和内部结点。
  2. 外部结点：也就是树的叶子结点，用来记录半无限长字串的首字符在完整半无限长字串中的开始位置(字符索引)和半无限长字串出现的频次。
  3. 内部结点：除了叶子结点的所有结点，这个结点是自动添加的，用来记录索引的路径，它有三个基本的数据项：左指针、右指针、比较位。
  4. 左指针：指向该结点的左子树。
  5. 右指针：指向该结点的右子树。
  6. 比较位：记录的是从根结点到达该结点的所有位串最后一个不相同位的位置。用来指示下一步搜索的方向：当位串的比较位为0 时，搜索转向左子树，当该比较位为1时，搜索转向右子树。
3.1.3. 原理说明
  1. 将所有半无限长字串，用二进制位来表示。它们之间的比较也是以bit位为单位来进行比较。
  2. 规定所有半无限长字串的长度要一致，结尾没有的空字符用0来填充。
3.1.4. 举例说明
  • CUHK     01000011   01010101   01001000   01001011                                       
  • UHK0      01010101   01001000   01001011   00000000
  • HK00      01001000   01001011   00000000   00000000
  • K000       01001011   00000000   00000000   00000000

图 1  PAT tree示例图

3.1.5. 检索过程
  1. 检索过程就是根据查询字串在PAT tree中从根结点寻找路径的过程。当比较完查询字串所有位置后，搜索路径达到PAT tree的某一结点。
  2. 若该结点为叶子结点，则判断查询字串是否为叶子结点所指的半无限长字串的前缀，如果判断为真，则查询字串出现的频次即为叶子结点中记录的频次；否则，该查询字串不存在。
  3. 若该结点为内部结点，则判断查询字串是否为该结点所辖子树中任一叶子结点所指的半无限长字串的前缀。如果判断为真，该子树中所有叶子结点记录的频次之和即为查询字串的出现频次。否则，查询字串不存在。
  4. 这样，通过PAT tree可以检索原文中任意长度的字串及其出现频次。 

3.2.ptree.c文件中PAT tree与一般意义上PAT tree的差异

  1. 数据结构不同。
  2. ptree.c文件中存储的关键信息长度可以不同。
  3. 对于ptree.c文件中的PAT tree内部结点有可能是我们手动添加的结点。
  4. 利用ptree.c文件中的代码CUHK、UHK、HK和K的存储效果为2图。


图2 ptree.c示例图 

3.3. ptree.c文件中PAT tree的介绍

3.3.1. 数据结构
  • PAT tree头：即struct ptree，用来管理PAT tree。
  • 数据结点：即struct ptree_node。分为通配虚结点和信息结点。
    1. 通配虚结点：为了使整棵树链接起来，自动添加的结点，结点中的关键字为它左、右子树关键字的公共部分。
    2. 信息结点：用户手动添加的结点。

图 3 ptree.h数据结构图 

3.3.2. 设计原理
  1. 查找最长匹配的结点：
    a. 从头结点开始依次向下比较，取两个key_len中较小值为关键字的比较长度；
    b. 如果，比较到某结点不匹配，那么它的父结点为最长匹配结点(父结点为NULL表示没有匹配到结点)，直到把待匹配结点的key_len匹配完。
  2. 添加结点：
    a. 从头结点开始，查看是否有完全匹配的结点，如果有，不添加新结点。
    b. 如果没有，获取最长匹配的结点。
        如果该结点是第一个添加的结点，把该结点定义为头结点。
        如果最长匹配的结点为叶子结点，把待匹配结点添加为该叶子结点的孩子结点。
        如果最长匹配的结点的孩子结点为叶子结点，把待匹配的结点插入到最长匹配结点和它的孩子结点之间。
        否则，需要添加通配结点。
  3. 删除结点：
    待删除结点的lock属性应等于0，info为NULL且左、右子树不能都存在，才可进行删除操作。
  4. 结点的lock属性： 
    每个结点都包含一个lock成员，称为结点的访问计数。
    新创建的信息结点没有进行任何操作时，它的lock值等于1。
    自动添加的通配结点没有进行任何操作时，它的lock值等于0。
    添加新结点时，如果存在完全匹配的结点，不添加结点，但原结点的lock值会+1。
    每次访问(遍历、查找、添加)该结点时调用ptree_lock_node()函数使lock值+1，访问结束后调用ptree_unlock_node()函数lock值-1，使之恢复原值。 
3.3.3. 举例说明 
  1. 有三个结点，假设key_len都为3(bit)，关键字的前三个bit位分别是：010、100和101，其中结点1和结点2均为通配结点。
    结点1：key_len == 0(bit)；
    结点2：key_len == 1(bit)。
  • 向PAT tree中增加第一个结点010......，如右图4：

          图 4
  • 向PAT tree中增加第二个结点100......，如右图5：
  • 图 5
  • 说 明：当向PAT tree中增加结点100......时，由于和当前存在结点的第一个bit位就不匹配，所以在增加结点的同时，会自动产生一个key_len = 0(bit)的通配虚结点，逻辑图如上图所示，通配虚结点的p_left指针，指向不匹配的bit位为0的结点，p_right指针指向不匹配的bit位 为1的结点。 
  • 向PAT tree中增加第三个结点101......，如右图6：

 图 6
说明：向PAT tree中增加结点101......时，当匹配到第二bit位时，没有结点可以继续匹配，在增加结点的同时，会自动产生一个key_len = 2(bit)，key值为10(含有2个bit位)的通配虚结点，逻辑图如上图所示，通配结点的p_left指针，指向不匹配的bit位为0的结点100......，p_right指针指向不匹配的bit位为1的结点101......。

4. 接口

4.1 ptree_init

  • 原型
         struct ptree *ptree_init (u_int16_t max_key_len)
  • 功能
         初始化树结构
  • 参数
         max_key_len：树节点key的最大比特位长度
  • 返回值
         成功返回初始化好的树结构体指针，失败返回NULL

4.2 ptree_top

  • 原型
         struct ptree_node *ptree_top (struct ptree *tree)
  • 功能
         获得树的根节点并加锁
  • 说明
         主要用于遍历整个树的节点
  • 参数
         tree：树结构指针
  • 返回值
         成功返回加锁了的树根节点，失败返回NULL

4.3 ptree_next

  • 原型
         struct ptree_node *ptree_next (struct ptree_node *node)
  • 功能
         返回当前节点的下一个节点
  • 参数
         node：树节点指针
  • 返回值
         成功返回加锁了的当前节点的下一节点，失败返回NULL

4.4 ptree_next_until

  • 原型
        struct ptree_node *ptree_next_until (struct ptree_node *node1, struct ptree_node *node2)
  • 功能
        返回当前节点的下一个节点
  • 说明
        若找到下一节点前遇到node2，返回NULL
  • 参数
         node1：树节点指针1； node2：树节点指针2
  • 返回值
         成功返回加锁了的当前节点的下一节点，失败返回NULL

4.5 ptree_node_get

  • 原型
         struct ptree_node *ptree_node_get (struct ptree *tree, u_char *key, u_int16_t key_len)
  • 功能
         增加树节点到树
  • 说明
         若key被包含在已有树节点中，则返回相应节点
  • 参数
         tree：树结构指针； key：键值； key_len：key比特位长度
  • 返回值
         成功返回加了锁的树节点指针，失败返回NULL

4.6 ptree_node_lookup

  • 原型
         struct ptree_node *ptree_node_lookup (struct ptree *tree, u_char *key, u_int16_t key_len)
  • 功能
         查找节点
  • 说明
         根据key在树中查找相应节点，找到包含key值且info非空，key_len相等的则加锁并返回相应节点，找不到则返回NULL
  • 参数
         tree：树结构指针； key：键值； key_len：key比特位长度（key_len >= 树节点key长度）
  • 返回值
         成功返回加了锁的树节点指针，失败返回NULL

4.7 ptree_lock_node

  • 原型
         struct ptree_node *ptree_lock_node (struct ptree_node *node)
  • 功能
         对node加锁
  • 参数
         node：树节点指针
  • 返回值
         成功返回加了锁的树节点指针

4.8 ptree_node_match1

  • 原型
         struct ptree_node *ptree_node_match1 (struct ptree *tree, u_char *key, u_int16_t key_len)
  • 功能
         查找节点  
  • 说明
         根据key在树中查找相应节点，返回树节点中的key值匹配查找key值的树节点（不关心info），否则返回NULL
  • 参数
         tree：树结构指针； key：键值； key_len：key比特位长度
  • 返回值
         成功返回加了锁的匹配树节点指针（该节点key_len 不小于 搜索key_len），否则返回NULL

4.9 ptree_node_match

  • 原型
         struct ptree_node *ptree_node_match (struct ptree *tree, u_char *key, u_int16_t key_len)
  • 功能
         查找节点
     
  • 说明
         根据key在树中查找相应节点（查找key的值必须大于等于树节点的值，否则直接返回NULL），返回树节点中的key值匹配查找key值且数据节点（info指针）非空的树节点，否则返回NULL
  • 参数
          tree：树结构指针； key：键值； key_len：key比特位长度
  • 返回值
         成功返回加了锁的匹配树节点指针（该节点key_len 不大于 搜索key_len），否则返回NULL

4.10 ptree_node_free

  • 原型
         void ptree_node_free (struct ptree_node *node)
  • 功能
         释放树节点空间
  • 参数
         node：树节点指针
  • 返回值
         无

4.11 ptree_finish

  • 原型
         void ptree_finish (struct ptree *tree)
  • 功能
         释放树
  • 参数
         tree：树结构指针
  • 返回值
         无

4.11 ptree_unlock_node

  • 原型
         void ptree_unlock_node (struct ptree_node *node)
  • 功能
         释放树节点锁，如果锁值为0，删除此节点
  • 参数
         node：树节点指针
  • 返回值
         无

4.12 ptree_node_delete

  • 原型
         void ptree_node_delete (struct ptree_node *node)
  • 功能
         从树中删除节点
  • 参数
        node：树节点指针
  • 返回值
         无

4.13 ptree_node_delete_all

  • 原型
        void ptree_node_delete_all (struct ptree *tree)
  • 功能
         删除树中所有节点
  • 参数
         tree：树结构指针
  • 返回值
         无

4.14 ptree_has_info

  • 原型
    int ptree_has_info (struct ptree *tree)
  • 功能
         检查树中节点 info是否设置
  • 参数
         tree：树结构指针
  • 返回值
         1：info设置 0：树空或info未设置

4.15 ptree_key_copy

  • 原型
        void ptree_key_copy (struct ptree_node *node, u_char *key, u_int16_t key_len)
  • 功能
         为node设置key值
  • 参数
        node：树节点指针 key：键值 key_len：键值比特位长度
  • 返回值
         无

4.16 ptree_bit_to_octets

  • 原型
        int ptree_bit_to_octets (u_int16_t key_len)
  • 功能
         将比特位长度转换成字节长度
  • 参数
         key_len：比特位长度
  • 返回值
         字节长度

4.17 ptree_key_match

  • 原型
         int ptree_key_match (u_char *np, u_int16_t n_len, u_char *pp, u_int16_t p_len)
  • 功能
         key值匹配
  • 说明
        匹配key（n_len 不大于p_len），如果np的前n_len位与pp的前n_len位相等返回true，否则返回false
  • 参数
         np：key1 n_len; key1比特位长度 pp：key2; p_len:key2比特位长度
  • 返回值
         如果np包含pp返回true，否则返回false

4.18 ptree_check_bit

  • 原型
         int ptree_check_bit (struct ptree *tree, u_char *p, u_int16_t key_len)
  • 功能
         根据键值返回0或1
  • 说明
         根据key值返回0，1决定搜索或添加方向（左孩子或右孩子）
  • 参数
         tree：树结构指针； p：键值指针； ken_len：键值长度；
  • 返回值
         0， 1 （用于判断左孩子还是右孩子）

4.19 ptree_node_match_exclude

  • 原型
        struct ptree_node * ptree_node_match_exclude (struct ptree *pt, u_char *key1, u_int16_t key_len1, u_char *key2, u_int16_t key_len2)
  • 功能
         保留未用
  • 参数
         保留

使用说明

1.首先调用ptree_init初始化tree结构

2.然后调用ptree_node_get添加节点

3.通过调用ptree_node_lookup查找匹配key的节点

3调用ptree_node_delete删除指定节点

4.最后调用ptree_finish释放节点

备注：lock索引值在每次有返回节点时都会加一，在处理完该节点后记得ptree_unlock_node该节点！

示例

1.程序添加节点示意图如下：

2.运行结果

3.代码
#include <stdio.h>
#include "ptree.h"
#define BUF_SIZE 3
/*封装的信息打印函数*/
void my_printf(struct ptree_node *node);
/*封装的打印所有树节点信息函数*/
void show_all_node(struct ptree *tree);int main(void)
{struct ptree * tree;int i;char *str = "****str******";u_char buf[BUF_SIZE][3] = {{192, 168, 1},{20, 16, 5}, {10, 8, 26}} ;u_char buf_1[] = {10, 8};u_char buf_2[] = {16};struct ptree_node *node = NULL, *next = NULL;i= 0;/* 初始化树 */tree = ptree_init (32);if (NULL == tree)printf("tree is null \n");while(i < BUF_SIZE){	/* 将节点加入到树*/node = ptree_node_get (tree, buf[i], 24);if(NULL == node)goto finish;node->info = str;i++;show_all_node(tree);}/* 将节点加入到树*/ptree_node_get (tree, buf_1, 16);show_all_node(tree);/* 将节点加入到树*/ptree_node_get (tree, buf_2, 8);show_all_node(tree);/*查找节点 */node = ptree_node_lookup(tree, (u_char *)buf[1], 24);if (NULL != node){printf("-----------------del--------------\n");ptree_unlock_node(node);my_printf(node);		printf("-----------------del--------------\n");        }/* 从树中删除节点 */node->info = NULL;/*info为空才能删除*/ptree_unlock_node(node);/*遍历树节点*/show_all_node(tree);finish:/* 释放树 */ptree_finish (tree);return 0;	
}
void show_all_node(struct ptree *tree)
{/*遍历树节点*/int num;struct ptree_node *node = NULL, *next = NULL;num = 0;printf("-----------------traverse--------------\n");node = ptree_top (tree);while (NULL != node){   /* 获取下一个节点 */    next = ptree_next (node);my_printf(node);         node = next;num++;}printf("num = %d\n", num);
}void my_printf(struct ptree_node *node)
{int i, j;i = 0;j = ptree_bit_to_octets(node->key_len);while(i < j){printf("%d.", node->key[i]);i++;}printf("\tlock = %d\tkey_len = %d\n", node->lock, node->key_len);}






这篇关于ptree数据结构分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/412862。

相关文章

Python 迭代器和生成器概念及场景分析

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle
阅读更多...
C++ Sort函数使用场景分析

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序
阅读更多...
kotlin中const 和val的区别及使用场景分析

kotlin中const 和val的区别及使用场景分析

《kotlin中const和val的区别及使用场景分析》在Kotlin中,const和val都是用来声明常量的,但它们的使用场景和功能有所不同,下面给大家介绍kotlin中const和val的区别,... 目录kotlin中const 和val的区别1. val:2. const:二 代码示例1 Java
阅读更多...
Go标准库常见错误分析和解决办法

Go标准库常见错误分析和解决办法

《Go标准库常见错误分析和解决办法》Go语言的标准库为开发者提供了丰富且高效的工具,涵盖了从网络编程到文件操作等各个方面,然而,标准库虽好,使用不当却可能适得其反,正所谓工欲善其事,必先利其器,本文将... 目录1. 使用了错误的time.Duration2. time.After导致的内存泄漏3. jsO
阅读更多...
C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
Spring事务中@Transactional注解不生效的原因分析与解决

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3
阅读更多...
找不到Anaconda prompt终端的原因分析及解决方案

找不到Anaconda prompt终端的原因分析及解决方案

《找不到Anacondaprompt终端的原因分析及解决方案》因为anaconda还没有初始化,在安装anaconda的过程中,有一行是否要添加anaconda到菜单目录中,由于没有勾选,导致没有菜... 目录问题原因问http://www.chinasem.cn题解决安装了 Anaconda 却找不到 An
阅读更多...
Spring定时任务只执行一次的原因分析与解决方案

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况？这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次？3.1 未启用
阅读更多...
C++ 各种map特点对比分析

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map（如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现：基于红黑
阅读更多...
Spring、Spring Boot、Spring Cloud 的区别与联系分析

Spring、Spring Boot、Spring Cloud 的区别与联系分析

《Spring、SpringBoot、SpringCloud的区别与联系分析》Spring、SpringBoot和SpringCloud是Java开发中常用的框架,分别针对企业级应用开发、快速开... 目录1. Spring 框架2. Spring Boot3. Spring Cloud总结1. Sprin
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2