使用Trie树实现的MAP

时间：2023-01-13 10:22:04

最近看到一种基于Tire树的map结构，其键值类型为string类型，查找速度很快。文章[1]中分析了这种‘TrieMap’原理，对比了其和std::map，std::unordered_map的查找速度。基于Trie树和文章中提到的TrieMap设计，进行实践，给出自己构造的TrieMap以供参考学习。

Trie树，又称单词查找树、字典树。是一种哈希树的变种，是一种用于快速检索的多叉树结构。Trie树查找的时间复杂度在O(n)，实际上这是以消耗更多的内存空间为代价的。以本文构造的Trie树为例，每个节点都包含了128个(因为我们只接受ASCII码在0-127的之间的字符组成的字符串作为键值)子节点。这其实造成了极大的空间浪费，但是带来的好处是：可以使用直接定址的下标访问来判断某个节点是否为空。比如TrieNode *ptr指向的是某个节点，其含有128个子节点，那么对于string str = “hello”;可以直接用ptr->pChild[str[i]]来访问或判断该节点的状态。此外，作为一种树形数据结构，相邻兄弟节点可以存储在一个数组中，但父节点和子节点之间的连接还是通过链表的结构。
本文要讲的TrieMap，其本质不过是在Trie树的节点中增加了一块空间，用于存储对于的Value值，但这也带来了进一步的空间浪费,以test:test123这个键值对为例,前三个节点t->e->s实际上都分配了用于存储Value的空间，但只有t->e->s->t的最后一个节点t存储了对于的键值‘test123’。当插入test:test123后，从空间的角度来看，树的第一层共有128个节点，其中第117个节点t不为空，其余均为空；第二层共有128个节点，其中只有t对应的第二层中e的位置不为空，其余均为空…但是当再次插入新的键值对task:tasker时，第一层t节点位置与键值test共有存储位置，但是第二层会增加128个节点，却仍然只有a对应的存储位置不为空，这也是Trie树的特点，搜索引擎系统用于文本词频统计的原理也基于此。如果键值有公共的前缀，可以节省内存开销。
TrieMap的键值需为字符串类型，或是可以转换成字符串类型，存在一定的局限性。但通过模板类设计的TrieNode节点，可以保证Key对应的Value支持较为宽广的类型。TrieMap对外的接口中，提供了：
(1).用于实例化对象的构造函数;
(2).用于建立TrieMap结构的Insert()函数;
(3).用于查找键值对的函数Find()
(4).用于判断TrieMap是否为空的Empty()函数
其中建立和查找TrieMap的键可为c-style的字符串，以及string类型，实际上代码中只是将string类型统一转换为c-style的字符串。
下面给出实现，并使用CPPUNIT进行测试。

//triemap.h
#ifndef _TRIE_MAP_201612
#define _TRIE_MAP_201612
#include <string.h>
#include <string>
#include <stdlib.h> 
using namespace std;
//ASCII码0-127,不包括扩展的ASCII码,对应每个节点的叶子节点个数
const int NODESIZE = 128;

//节点的数据结构
template <class T>
class TrieNode
{
public:
    TrieNode()
    {
        isLeaf = false;
        ::memset(this->pChild, 0, NODESIZE * sizeof(TrieNode*));
    }
public:
    T value;//节点可以存储的数据类型
bool isLeaf;//标记该节点是否是叶子节点
    TrieNode* pChild[NODESIZE];//每个节点的子节点
};

template<class T>
class TrieMap
{
public:
//constructor
    TrieMap();
//deconstructor
    ~TrieMap();
//向Tire树中插入新节点
void Insert(const char *key, const T &value);
//向Tire树中插入新节点--string
void Insert(const string &key, const T &value);
//查找
bool Find(const char *key,T &value);
//查找--string
bool Find(const string &key,T &value);
//
bool Empty()const;
private:
//创建新的TrieNode节点
    TrieNode<T> *newTrieNode();
//用于删除某节点及其所有的子节点
void Delete(TrieNode<T> *&ptr);
private:
    TrieNode<T> *root;//Trie树的根节点
};
template<class T>
TrieMap<T>::TrieMap()
{
this->root = new TrieNode<T>;
if( NULL == this->root )
exit(-1);
}
template<class T>
TrieMap<T>::~TrieMap()
{
if(this->root != NULL)
this->Delete(root);
}

template<class T>
void TrieMap<T>::Insert(const char *key, const T &value)
{
    TrieNode<T> *ptr = this->root;
int idx;
int len = strlen(key);
for(int i = 0 ; i <  len ;++i)
    {
        idx = key[i];
//该子节点不存在
if(ptr->pChild[idx] == NULL)
        {
            ptr->pChild[idx] = this->newTrieNode();
        }
//指向该节点，继续遍历
        ptr = ptr->pChild[idx];
    }
    ptr->isLeaf = true;
    ptr->value = value;
}

template<class T>
void TrieMap<T>::Insert(const string &key, const T &value)
{
this->Insert(key.c_str(),value);
}

template<class T>
bool TrieMap<T>::Find(const char *key, T &value)
{
    TrieNode<T> *ptr = this->root;
int idx;
int len = strlen(key);
int i;
for( i = 0 ; i < len ;++i)
    {
        idx = key[i];
//输入的字符串，不在普通ASCII码范围
if(idx < 0 || idx >= NODESIZE)
return false;
//节点为空，可能是未找到，也可能是遍历结束了
if(ptr->pChild[idx] == NULL)
        {
break;
        }
//找到该节点，继续遍历 
else
        {
            ptr = ptr->pChild[idx];
        }
    }
if(i == len && ptr->isLeaf)
    {
        value = ptr->value;
return true;
    }
return false;
}

template<class T>
bool TrieMap<T>::Find(const string &key,T &value)
{
return this->Find(key.c_str(), value);
}
template<class T>
bool TrieMap<T>::Empty()const
{
bool flag = true;
for(int i = 0 ;i < NODESIZE ;++i)
    {
if(this->root->pChild[i] != NULL)
        {
            flag = false;
return flag;
        }       
    }
return flag;
}
template<class T>
TrieNode<T>* TrieMap<T>::newTrieNode()
{
    TrieNode<T> *ptr = new TrieNode<T>();
if(NULL == ptr)
    {
exit(-1);
    }
return ptr;
}

template<class T>
void TrieMap<T>::Delete(TrieNode<T> *&ptr)
{
if(NULL == ptr)
return;
for(int i = 0 ;i < NODESIZE ;++i)
    {
if(NULL != ptr->pChild[i] )
        {
this->Delete(ptr->pChild[i]);
        }
    }
if(NULL != ptr)
    {
delete ptr;
        ptr = NULL;
    }
}
#endif
//main.cpp
#include <iostream>
#include "triemap.h"
#include <cppunit/extensions/TestFactoryRegistry.h>
#include <cppunit/ui/text/TextTestRunner.h>
#include <cppunit/extensions/HelperMacros.h>

class myTest: public CppUnit::TestFixture 
{
public:
void  checkInsert()
    {
        triemap.Insert("root","123456");
bool flag = triemap.Empty();
        CPPUNIT_ASSERT_MESSAGE("TrieMap not Empty!", (!flag) );
    }

void checkFind() 
    {
        triemap.Insert("admin","admin123");
        triemap.Insert("tester","tester");
string value;
        triemap.Find("admin",value);
int len =  value.length();
        CPPUNIT_ASSERT_EQUAL_MESSAGE("Check Find:", len, 8);
    }

void checkFindNull() 
    {
string value;
bool flag = triemap.Find("test",value);
        CPPUNIT_ASSERT_MESSAGE("Could't find test!", (!flag) );
    }

    CPPUNIT_TEST_SUITE( myTest );
    CPPUNIT_TEST( checkInsert );
    CPPUNIT_TEST( checkFind );
    CPPUNIT_TEST( checkFindNull );
    CPPUNIT_TEST_SUITE_END();
private:
    TrieMap<string> triemap;
};

int main ()
{
//使用辅助宏注册测试套件
    CPPUNIT_TEST_SUITE_REGISTRATION ( myTest );
    CppUnit::Test *test =  CppUnit::TestFactoryRegistry::getRegistry().makeTest();
    CppUnit::TextTestRunner runner;
    runner.addTest(test);
//运行测试，自动显示进度和结果
    runner.run("",true);
return 0;
}

在示例中，我们插入了键值对tester:tester，但是没有插入键为test的键值对，虽然test为tester的前缀，在Trie树*用前缀节点，但是由于在TrieNode节点中用布尔变量isLeaf来标记节点的类型，所以即使test为tester的前缀，也无法查找到，这是符合MAP的定义的，也是与Trie树不同之处。
运行结果：
[root@localhost map]# ./run
…

OK (3 tests)

[1].Trie实践:一种比哈希表更快的数据结构.http://blog.csdn.net/stevenkylelee/article/details/38343985
[2].Trie树:应用于统计和排序.http://blog.csdn.net/hguisu/article/details/8131559
标签：

相关文章