Patricia Trie 模板类

• 下载源文件 - 11.8 Kb
• 下载演示项目 - 13.9 Kb

引言

在我为一家生产软件开发工具的公司工作时，我需要编写一个应用程序，将整个文件系统封装在一个文件中。这个问题的一部分涉及到创建一个关联查找结构，其中字母数字键——在这种情况下是完整路径——既可以用于查找与这些键关联的数据（即 FAT 中的指针），也可以使用键作为公共路径前缀进行快速的 globbing（通配符匹配）。最重要的是，这种奇特的查找结构必须速度快，即：

• 其查找时间必须优于带有字符串键的普通哈希表。
• 在结构中查找所有具有公共前缀的元素必须以亚线性时间运行。
• 该结构必须提供元素删除操作。

我的方法是实现所谓的 Patricia 树，这是一种压缩的 Trie（前缀树），它利用了字符串键的某些特性，如下所述。这是为了折叠不必要的枝干。

背景

从历史角度来看，这个数据结构的名称就是一个缩写。它代表“用于检索编码在字母数字信息中的实用算法”（Practical Algorithm to Retrieve Information Coded in Alphanumeric）。该抽象数据类型（ADT）在 Donald R. Morrison 于 1968 年发表的一篇论文中进行了描述。

Patricia 树是一种压缩的 Trie，它利用唯一键中的公共子字符串作为折叠 Trie 枝干的起点。由于这种压缩，Patricia 树比常规 Trie 更“密集”。这也是为什么对该结构的操作——即添加、删除、查找、前缀查找——以及其内存消耗如此高效的原因。

Patricia 树是一种二叉树，其中每个节点都有一个“位索引”，指定了键（字符串）中的一个位位置。在我下面的实现中，树的层级具有越来越高的位索引，因此父节点的位索引总是低于其子节点的位索引。也就是说，除非节点有自环边或上行边，如下文所述。其他实现假设所有键的长度都相等，但在这里情况并非如此，因为文件名中可以有任意长的字符序列。它们从高位索引开始，通常等于键的长度，并且在进入树的更深层时，为节点分配递减的位索引。

Patricia 树中的键是位字符串，索引从左到右按升序标记。您也可以从字节字符串的角度来看待键，其中位索引 0 指定键的字节 0 的位 0。位索引 8 指定键的字节 1 的位 0，依此类推。

我应该指出的一点是，P-Tries 在叶子节点处有后向边。因此，如果二叉树的叶子节点“指向空”，那么 P-Tries 的叶子节点包含两条边，它们要么指向叶子节点本身，要么指向结构中的其他节点。

搜索从根节点开始。当查找算法在搜索特定键的过程中到达这些节点之一时，它会测试查找键中指定索引处的位。如果位是 0，算法会沿着左侧出边。如果位是 1，算法会沿着右侧出边到达下一个节点。Patricia 树上的搜索结束于算法沿着上行边，即从叶子节点返回到树中的边。无论上行边指向何处，那都是搜索的结果。在查找特定键时，在此最后一步必须进行键比较。如果该节点处的键与我们要查找的键匹配，则搜索成功。否则，搜索失败，因此该键不在我们的 Trie 中。

示例

假设您有以下键的集合

SOME
ABACUS
SOMETHING
B
ABRACADABRA
THIS
SOMERSET

Trie 将如下所示

每个节点都封装了一个键（例如，“SOME”）和一个位索引（0），以及其他内容。

简单情况：假设您想在 Trie 中查找键“B”。您从根节点（“SOME”，0）开始，其位索引为 0。所以您查看键中的位 0：是 0 还是 1？它是 0，所以您沿着左边到达下一个节点：（“B”，1）。您查看键中的位 1：它是 1，所以您沿着右边，它带您向后（即到一个位索引小于或等于当前节点的节点）到达节点（“B”，1）。您在您的键“B”和您最终所在的节点处的键之间进行字符串比较。它们匹配！所以您找到了您的节点，经过 2 + 1 步（2 次位比较 + 1 次 strcmp）。

更复杂的情况：假设您想查找“SOME”，其键恰好封装在结构的根节点中。您从根节点开始，其位索引为 0。查看键“SOME”中的位 0。它是 1，所以您沿着右边到达（“ABACUS”，1）。查看键中的位 1。它是 1，所以您沿着右边到达（“SOMERSET”，33）。查看键中的位 33。它是 0，所以您沿着左边到达（“SOMETHING”，34）。查看键中的位 34：它是 0，即它不存在，所以键被“填充”了必要的零。所以您再次沿着左边，它带您向后回到键为“SOME”的节点。进行字符串比较：您的键是否等于“SOME”？是的，所以您刚刚在结构中找到了“SOME”，经过 6 步（6 次位比较 + 1 次 strcmp）。

更进一步的复杂情况：假设您想查找 Trie 中所有以“AB”为公共前缀的元素。再次从根节点开始。查看键中的位 0。它是 1，所以您沿着右边到达（“ABACUS”，1）。查看键中的位 1。它是 0，所以您沿着左边到达（“ABRACADABRA”，16）。此时，该节点处的位索引是 16，它大于您搜索键的位数。所以您在此处停止，它将成为存储所有具有相同公共前缀“AB”的元素的子树的“根”。该节点经过 2 步（2 次位比较）到达。假设您想枚举所有键具有公共前缀“AB”的节点。您可以从该根节点开始执行深度优先搜索，在遇到后向边时停止。根节点有两个出边——都指向节点（“ABRACADABRA”，16），即自环边，以及（“ABACUS”，1）。所以这就是您拥有以“AB”为公共前缀的键的节点集合。

使用代码

我在这里提出的 Patricia Trie 实现由一个模板类组成。客户端可以实例化该模板的特定类型版本，基于该结构需要存储的信息类型。虽然我最初的实现需要存储 FAT 指针——本质上是 FILE* 指针——但我认识到其他应用程序可能最终会有完全不同的需求。模板类非常适合解决这个问题。

代码包含两个类：nPatriciaTrieNode 和 nPatriciaTrie。前者定义了一个 Trie 节点，并封装了以下内容：

• 位索引
• 一个键，即 Trie 中其他位置的上行边的目标
• 指向“左”子节点的指针
• 指向“右”子节点的指针

后者定义了 Trie 本身。它封装了指向 Trie 根的单个指针。任何查找、添加或删除操作都从根开始，沿着 Trie 下行，在访问的节点指定的索引处比较键的位。Trie 节点接口如下所示：

// Constructors & destructor
nPatriciaTrieNode();
nPatriciaTrieNode(nPatriciaTrieKey, T, int, 
    nPatriciaTrieNode<T>*, nPatriciaTrieNode<T>*);
virtual ~nPatriciaTrieNode();

// Name:    Initialize
// Args:    key, data, bit-index, left, right
// Return:  void
// Purpose: Initialize this node with the given data.
void        Initialize(nPatriciaTrieKey, T, int, 
    nPatriciaTrieNode<T>*, nPatriciaTrieNode<T>*);

// Name:    GetData/SetData
// Args:    data : T
// Return:  T | bool
// Purpose: Accessors for the data field.
T           GetData();
bool        SetData(T);
        
// Name:    GetKey
// Args:    none
// Return:  KeyType (templated)
// Purpose: Getter for the key field.
nPatriciaTrieKey GetKey();

// Name:    GetLeft/GetRight
// Args:    none
// Return:  nPatriciaTrieNode*
// Purpose: Getters for the left/right fields.
nPatriciaTrieNode<T>* GetLeft();
nPatriciaTrieNode<T>* GetRight();

Trie 接口如下所示：

// Constructor and destructor
nPatriciaTrie();
virtual ~nPatriciaTrie();

// Name:    Insert(key, data)
// Args:    key : nPatriciaTrieKey, data : T
// Return:  nPatriciaTrieNode*
// Purpose: Insert a new key+data pair in the Patricia structure, and
//          return the new node.
virtual nPatriciaTrieNode<T>* Insert(nPatriciaTrieKey, T);

// Name:    Lookup(key)
// Args:    key : nPatriciaTrieKey
// Return:  T
// Purpose: Search for the given key, and return the data associated
//          with it (or NULL).
virtual T Lookup(nPatriciaTrieKey);

// Name:    LookupNode(key)
// Args:    key : nPatriciaTrieKey
// Return:  T
// Purpose: Search for the given key, and return the node that
//          contains it (or NULL).
virtual nPatriciaTrieNode<T>* LookupNode(nPatriciaTrieKey);

// Name:    Delete(key)
// Args:    key : nPatriciaTrieKey
// Return:  bool
// Purpose: Remove the node containing the given key. Return
//          true if the operation succeeded, false otherwise.
virtual bool Delete(nPatriciaTrieKey);

软件包中包含的演示应用程序展示了如何实例化该类的 <int> 版本——即键与整数相关联——以及如何向结构中添加元素，以及如何删除元素和搜索选定的键。这些是 nPatriciaTrie<int>::nPatriciaTrie()、nPatriciaTrie::Insert、nPatriciaTrie::Delete 和 nPatriciaTrie::Lookup 的简单调用。例如：

// Create a trie
nPatriciaTrie* p = new nPatriciaTrie();

// Add an element
p->Insert("My first element", 1234);

// Look it up
printf("%d", p->Lookup("My first element"));

// Is some key in the trie?
printf("Foo is %s the trie", p->LookupNode("Foo") ? "in" : "not in");

// Remove an element
p->Delete("My first element");

我相信还有更多有趣的操作也是可能的。实际上，我这个 Trie 的商业实现比这个实现多了一些功能：它可以查找与给定公共前缀相关的元素，如上面的示例所述。我将把实现留给读者，但关键是所有这些元素都在一个子树中，包括后向边及其目标。可以使用给定的公共前缀访问该子树的根。

关注点

在编写此代码时，我注意到当时（即 2001 年）似乎没有人有元素删除操作的实现。所有关于该主题的文献都将删除操作描述为“微不足道”或“类似于添加操作”。因此，我自己的实现可能在概念上与其他人的实现有所不同，也可能没有。我只能说，删除操作并非完全微不足道，而且在许多方面肯定与添加操作不同。

对该代码的贡献始终受到赞赏。

历史

• 2005 年 3 月 2 日 - 首次公开领域发布
• 2005 年 7 月 2 日 - 澄清，感谢 WREY
• 2007 年 11 月 7 日 - 更改以处理任意模板化的键类型，并增加了 Christoph Mayer 的其他方法