【数据结构与算法】【字符串匹配】Trie树

野性酷女 2022-11-25 00:35 176阅读 0赞

1.  单模式串匹配  
    BF 算法和 RK 算法  
    BM 算法和 KMP 算法
2.  多模式串匹配算法  
    **Trie 树**和 AC 自动机

### 一、 什么是“Trie树”？ ###

#### 1. 他是一种树形结构，是一种专门处理字符串匹配的数据结构，解决在一组字符串集合中快速查找某个字符串的问题。 ####

#### 2. Trie树的本质是利用字符串之间公共前缀，将重复的前缀合并在一起 ####

Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

how，hi，her，hello，so，see  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

其中，根节点不包含任何信息，每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（红色节点并不都是叶子节点）。

#### 3. 查找 ####

当在Trie树中查找一个字符串时，如“her”,就将要查找的字符串分割成单个的字符h，e，r，然后从Trie树的根节点开始匹配。但，假若要查找的字符串是“he”，用上面同样的方法，从根节点开始，沿着某条路径来匹配，发现路径的最后一个节点“e”不是红色的，即“he”是某个字符串的前缀，但不能完全匹配任何字符串。

### 二 、如何实现一课Trie树？ ###

#### 1，Trie树主要有两个操作，一个是将字符串集合构造成Trie树。这个程可分解为： ####

*  将一个字符串插入到Trie树的过程
 *  在Trie树中查询一个字符串

#### 2，如何存储一个Trie树 ####

①：Trie树是一个多叉树，需要存储一个节点的所有子节点的指针。  
②：一种经典的存储方式：借助散列表额思想，通过一个下标与字符一一映射的数组，来存储子节点的指针。

class TrieNode { 
      char data;
      TrieNode children[26];
    }

**借助散列表的思想，我们通过一个下标与字符一一映射的数组，来存储子节点的指针。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
假设字符串中只有从a到z这26个小写字母，从数组中下标为0的位置，存储指向子节点a的指针，下标为1的位置存储指向子节点b的指针，以此类推，下标为25的位置，储存的是指向的子节点z的指针。如果某个字符的子节点不存在，就在对应的下标的位置存储null。  
当在Trie树中查找字符串的时候，就可以通过字符的ASCII码减去“a”的ASCII码，迅速找到匹配的子节点的指针。

public class Trie { 
      private TrieNode root = new TrieNode('/'); // 存储无意义字符
    
      // 往Trie树中插入一个字符串
      public void insert(char[] text) { 
        TrieNode p = root;
        for (int i = 0; i < text.length; ++i) { 
          int index = text[i] - 'a';
          if (p.children[index] == null) { 
            TrieNode newNode = new TrieNode(text[i]);
            p.children[index] = newNode;
          }
          p = p.children[index];
        }
        p.isEndingChar = true;
      }
    
      // 在Trie树中查找一个字符串
      public boolean find(char[] pattern) { 
        TrieNode p = root;
        for (int i = 0; i < pattern.length; ++i) { 
          int index = pattern[i] - 'a';
          if (p.children[index] == null) { 
            return false; // 不存在pattern
          }
          p = p.children[index];
        }
        if (p.isEndingChar == false) return false; // 不能完全匹配，只是前缀
        else return true; // 找到pattern
      }
    
      public class TrieNode { 
        public char data;
        public TrieNode[] children = new TrieNode[26];
        public boolean isEndingChar = false;
        public TrieNode(char data) { 
          this.data = data;
        }
      }
    }

#### 3，时间复杂度： ####

构建 Trie 树 时间复杂度 O(n)（n 表示所有字符串的长度和）  
在 Trie 树中，查找某个字符串的时间复杂度 O(k)，k 表示要查找的字符串的长度  
在一组字符串中，频繁的查询某些字符串，用Trie树非常高效。

#### 4，Trie树很耗内存吗? ####

Trie树是使用数组来储存一个节点的子节点的指针的，即便一节点只有很少的子节点，远小于26个，比如2，3个，也要维护一个长度为26的数组。  
Trie的本质是避免重复存储一组字符串的相同前缀子串，但现在每个字符（对应一个节点）的存储远远大于1个字节。  
如果字符串中不仅包含小写字母，还包含大写字母，数字，甚至是中文，那需要的存储空间就更多了。所以在重复前缀并不多的情况下，Trie树不但不节省内存，还有可能浪费更多的内存。

###### 5，Tri树的优化方案： ######

*  牺牲一点查询的效率，将每个节点中的数组换成其他数据结构，来存储一个节点指针。如：**有序数组，跳表，散列表，红黑树**等。  
    假设用有序数组，数组中的指针按照指向的子节点中的字符大小顺序排序。查询时，可以通过二分查找的方法，快速查找到某个字符应该匹配的子节点的指针。
 *  缩点优化，就是对只有一个子节点的节点，而且此节点不是一个串的结束节点，可以将此子节点合并。这样可以节省空间，但却增加了编码难度。

### 三 、Trie数与散列表的，红黑树的比较（应用与局限 ） ###

#### 1，字符串的匹配问题，笼统上讲，其实就是数据的查找问题。 ####

#### 2，在一组字符串中查找字符串，Trie数实际上表现的并不好，他对要处理的字符串有极其严苛的要求： ####

*  第一，字符中包含的字符集不能太大，如果字符集太大，那么存储空间就可能浪费很多。即便优化也要付出牺牲查询，插入效率的代价。
 *  第二，要求字符串的前缀重合比较到，不然空间消耗会变大很多。
 *  第三，如果要用Trie树解决问题，就需要自己从零开始实现一个Trie树，还要保证没有bug，这在工程上是把简单问题复杂化。
 *  第四，通过指针串起来的数据是不连续的，而Trie树用到了指针，所以，对缓存并不友好。性能上会打个折扣。

### 综上：Trie树不适合精确匹配查找，这种问题更适合用散列表或红黑树来解决。Trie树比较适合的是查找前缀匹配的字符串。Trie的这个特点可以扩展到更加广泛的一个应用上：自动输入补全。比如输入法自动补全功能、IDE 代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等。 ###

[笔记整理来源： 王争 数据结构与算法之美][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20221124/7ffa4c4af3964e44b27f67a70b74bb89.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20221124/40df3892f9cb40ddaab2a9ce18b6f085.png
[Link 1]: https://s1.ax1x.com/2020/08/03/aUh2TS.png