问题标题: 求一篇较好的关于Trie字典树和关于KMP匹配的文章

《字符串匹配的KMP算法》这本书上有

1

望采纳！！！

Trie树（c++实现）

技术mix呢 2017-11-09 18:02:00 浏览148 评论0

• c++
•  
• PTR
•  
• class
•  
• void
•  
• index
•  
• type
•  
• 存储

摘要： 原理 先看个例子，存储字符串abc、ab、abm、abcde、pm可以利用以下方式存储       上边就是Trie树的基本原理：利用字串的公共前缀来节省存储空间，最大限度的减少无谓的字串比较。 应用       Trie树又称单词查找树，典型的应用是用于统计，排序和保存大量的字符串（不仅用于字符串），所以经常被搜索引擎系统用于文本词频的统计。

原理

先看个例子，存储字符串abc、ab、abm、abcde、pm可以利用以下方式存储

      上边就是Trie树的基本原理：利用字串的公共前缀来节省存储空间，最大限度的减少无谓的字串比较。

应用

      Trie树又称单词查找树，典型的应用是用于统计，排序和保存大量的字符串（不仅用于字符串），所以经常被搜索引擎系统用于文本词频的统计。

设计

      trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

结点可以设计成这样：

class trieNode
{
    public:
        trieNode() : terminableSize(0), nodeSize(0) { for(int i = 0; i < Size; ++i) children[i] = NULL; }
        ~trieNode()
        {
            for(int i = 0; i < Size; ++i)
            {
                delete children[i];
                children[i] = NULL;
            }
        }
    public:
        int terminableSize;          //存储以此结点为结尾的字串的个数
        int nodeSize;                //记录此结点孩子的个数
        trieNode* children[Size];    //该数组记录指向孩子的指针
};

图示

树设计成这样：

template<int Size, class Type>
class trie
{
    public:
        typedef trieNode<Size> Node;
        typedef trieNode<Size>* pNode;
        trie() : root(new Node) {}

        template<class Iterator>
        void insert(Iterator beg, Iterator end);
        void insert(const char *str);

        template<class Iterator>
        bool find(Iterator beg, Iterator end);
        bool find(const char *str);

        template<class Iterator>
        bool downNodeAlone(Iterator beg);

        template<class Iterator>
        bool erase(Iterator beg, Iterator end);
        bool erase(const char *str);

        int sizeAll(pNode);
        int sizeNoneRedundant(pNode);
    public:
        pNode root;
    private:
        Type index;
};

index字串索引利用（char % 26） 得到，这样'a' % 26 = 19, 'b' % 26 = 20

实现

插入

以插入abc、ab为例

]

删除

删除结点，首先查找此字串是否在树中，如果在树中，再查找此结点以下的部分是不是都是只有一个孩子，并且每个结点只有叶子结点是结束结点，如果不是继续往下重复上边过程。

统计字串个数

分两种情况

1. 计算重复的字串的个数：是结束结点，此时加的是terminabel的个数
2. 计算不重复的字串的个数：是结束结点，此时加的是1(当terminabel>0）的个数

参考代码

#include <iostream>
#include <cstring>
using namespace std;

template<int Size>
class trieNode
{
    public:
        trieNode() : terminableSize(0), nodeSize(0) { for(int i = 0; i < Size; ++i) children[i] = NULL; }
        ~trieNode()
        {
            for(int i = 0; i < Size; ++i)
            {
                delete children[i];
                children[i] = NULL;
            }
        }
    public:
        int terminableSize;
        int nodeSize;
        trieNode* children[Size];
};

template<int Size, class Type>
class trie
{
    public:
        typedef trieNode<Size> Node;
        typedef trieNode<Size>* pNode;
        trie() : root(new Node) {}

        template<class Iterator>
        void insert(Iterator beg, Iterator end);
        void insert(const char *str);

        template<class Iterator>
        bool find(Iterator beg, Iterator end);
        bool find(const char *str);

        template<class Iterator>
        bool downNodeAlone(Iterator beg);

        template<class Iterator>
        bool erase(Iterator beg, Iterator end);
        bool erase(const char *str);

        int sizeAll(pNode);
        int sizeNoneRedundant(pNode);
    public:
        pNode root;
    private:
        Type index;
};

template<int Size, class Type>
template<class Iterator>
void trie<Size, Type>::insert(Iterator beg, Iterator end)
{
    pNode cur = root;
    pNode pre;
    for(; beg != end; ++beg)
    {
        if(!cur->children[index[*beg]])
        {
            cur->children[index[*beg]] = new(Node);
            ++cur->nodeSize;
        }
        pre = cur;
        cur = cur->children[index[*beg]];
    }
    ++pre->terminableSize;
}
template<int Size, class Type>
void trie<Size, Type>::insert(const char *str)
{
    return insert(str, str + strlen(str));
}

template<int Size, class Type>
template<class Iterator>
bool trie<Size, Type>::find(Iterator beg, Iterator end)
{
    pNode cur = root;
    pNode pre;
    for(; beg != end; ++beg)
    {
        if(!cur->children[index[*beg]])
        {
            return false;
            break;
        }
        pre = cur;
        cur = cur->children[index[*beg]];
    }
    if(pre->terminableSize > 0)
        return true;
    return false;
}

template<int Size, class Type>
bool trie<Size, Type>::find(const char *str)
{
    return find(str, str + strlen(str));
}

template<int Size, class Type>
template<class Iterator>
bool trie<Size, Type>::downNodeAlone(Iterator beg)
{
    pNode cur = root;
    int terminableSum = 0;
    while(cur->nodeSize != 0)
    {
        terminableSum += cur->terminableSize;
        if(cur->nodeSize > 1)
            return false;
        else          //cur->nodeSize = 1
        {
            for(int i = 0; i < Size; ++i)
            {
                if(cur->children[i])
                    cur = cur->children[i];
            }
        }
    }
    if(terminableSum == 1)
        return true;
    return false;
}
template<int Size, class Type>
template<class Iterator>
bool trie<Size, Type>::erase(Iterator beg, Iterator end)
{
    if(find(beg, end))
    {
        pNode cur = root;
        pNode pre;
        for(; beg != end; ++beg)
        {
            if(downNodeAlone(cur))
            {
                delete cur;
                return true;
            }
            pre = cur;
            cur = cur->children[index[*beg]];
        }
        if(pre->terminableSize > 0)
            --pre->terminableSize;
        return true;
    }
    return false;
}

template<int Size, class Type>
bool trie<Size, Type>::erase(const char *str)
{
    if(find(str))
    {
        erase(str, str + strlen(str));
        return true;
    }
    return false;
}

template<int Size, class Type>
int trie<Size, Type>::sizeAll(pNode ptr)
{
    if(ptr == NULL)
        return 0;
    int rev = ptr->terminableSize;
    for(int i = 0; i < Size; ++i)
        rev += sizeAll(ptr->children[i]);
    return rev;
}

template<int Size, class Type>
int trie<Size, Type>::sizeNoneRedundant(pNode ptr)
{
    if(ptr == NULL)
        return 0;
    int rev = 0;
    if(ptr->terminableSize > 0)
        rev = 1;
    if(ptr->nodeSize != 0)
    {
        for(int i = 0; i < Size; ++i)
            rev += sizeNoneRedundant(ptr->children[i]);
    }
    return rev;
}

template<int Size>
class Index
{
    public:
        int operator[](char vchar) 
        { return vchar % Size; }
};

int main()
{
    trie<26, Index<26> > t;
    t.insert("hello");
    t.insert("hello");
    t.insert("h");
    t.insert("h");
    t.insert("he");
    t.insert("hel");
    cout << "SizeALL:" << t.sizeAll(t.root) << endl;
    cout << "SizeALL:" << t.sizeNoneRedundant(t.root) << endl;
    t.erase("h");
    cout << "SizeALL:" << t.sizeAll(t.root) << endl;
    cout << "SizeALL:" << t.sizeNoneRedundant(t.root) << endl;
}

 结果 

 技术实现细节

1. 对树的删除，并不是树销毁结点，而是通过结点自身的析构函数实现

2. 模版类、模版函数、非类型模版可以参考：http://www.cnblogs.com/kaituorensheng/p/3601495.html

3. 字母的存储并不是存储的字母，而是存储的位置，如果该位置的指针为空，则说明此处没有字母；反之有字母。

4. terminableNum存储以此结点为结束结点的个数，这样可以避免删除时，不知道是否有多个相同字符串的情况。

望采纳！！！

字符串匹配KMP算法C++代码实现

2016年10月30日 10:21:03

阅读数：1813

看到了一篇关于《字符串匹配的KMP算法》（见下文）的介绍，地址：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html，这篇博客对KMP算法的解释很清晰，但缺点是没有代码的实现。所以本人根据这位大神的思路写了一下算法的C++实现。

C++代码如下：

1. #include <iostream>

2. #include<string.h>

3.  

4. using namespace std;

5.  

6. int kmp(const char *text, const char *find)

7. {

8. if (text == '\0' || find == '\0')

9. return -1;

10. int find_len = strlen(find);

11. int text_len = strlen(text);

12. if (text_len < find_len)

13. return -1;

14. int map[find_len];

15. memset(map, 0, find_len*sizeof(int));

16. map[0] = 0;

17. map[1] = 0;

18. int i = 2;

19. int j = 0;

20.  

21. //计算《部分匹配表》 map

22. for (i=2; i<=find_len; i++)

23. {

24. while (1)

25. {

26. if (find[i-1] == find[j])

27. {

28. j++;

29. map[i-1]=j;

30. break;

31. }

32. else

33. {

34. if (j == 0)

35. {

36. map[i] = 0;

37. break;

38. }

39. j = map[j];

40. }

41. }

42. }

43. /* for(int m=0; m<find_len; ++m)

44. {

45. cout << map[m]<<endl;

46. }*/

47. i = 0;

48. j = 0;

49.  

50. //KMP算法实现

51. for (i=0; i<text_len;)

52. {

53. if (text[i] == find[j])

54. {

55. i++;

56. j++;

57. continue;

58. }

59. if (j == (find_len))

60. return i-j;

61. else

62. {

63.  

64. if (j == 0)

65. i++;

66. else

67. j = map[j-1];

68. }

69. }

70. return -1;

71. }

72.  

73. int main()

74. {

75. char* str1="BBC ABCDAB ABCDABCDABDE";

76.  

77. char * str2 ="ABCDABD";

78. int temp =kmp(str1, str2);

79. cout << temp<<endl;

80. return 0;

81. }

转自《字符串匹配的KMP算法》

举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？

许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。

这种算法不太容易理解，网上有很多解释，但读起来都很费劲。直到读到Jake Boxer的文章，我才真正理解这种算法。下面，我用自己的语言，试图写一篇比较好懂的KMP算法解释。

1.

首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

2.

因为B与A不匹配，搜索词再往后移。

3.

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

4.

接着比较字符串和搜索词的下一个字符，还是相同。

5.

直到字符串有一个字符，与搜索词对应的字符不相同为止。

6.

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

7.

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

8.

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

9.

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：

　　移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4，所以将搜索词向后移动4位。

10.

因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

11.

因为空格与A不匹配，继续后移一位。

12.

逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

13.

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

14.

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

15.

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，

　　－　"A"的前缀和后缀都为空集，共有元素的长度为0；

　　－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；

　　－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

　　－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

　　－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；

　　－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；

　　－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

16.

"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。

（完）

ABCDEFGHIJKIMNOPQRSTUVWXYZ

1

1