笙亿网络策划

后缀Trie怎么实现？数据结构与算法中的Suffix Tries详解

约 29 分钟读完 32 阅
文章导读
Previous Quiz Next 后缀 trie 是一种 trie，主要用于表示字符串的所有后缀。它是一个树形结构，其中每个节点代表字符串的一个后缀。根节点是整个字符串，每个子节点是比父节点后缀短一个字符的字符串后缀。
📋 目录
  1. Ⅰ 后缀 Trie 的特性
  2. Ⅱ 后缀 Trie 的操作
  3. Ⅲ 后缀 Trie 的插入操作
  4. Ⅳ 后缀 Trie 的删除和搜索操作
  5. Ⅴ 后缀 Trie 的时间复杂度
  6. Ⅵ 后缀 Trie 的应用
  7. Ⅶ 结论
A A

后缀 Trie

Previous
Quiz
Next

后缀 trie 是一种 trie，主要用于表示字符串的所有后缀。它是一个树形结构，其中每个节点代表字符串的一个后缀。根节点是整个字符串，每个子节点是比父节点后缀短一个字符的字符串后缀。

例如，考虑字符串 "banana"。该字符串的后缀 trie 如下所示：

             root
           /  | \
          b   a  n
         /    |   \
         a    n    a
        /     |     \
        n     a      n
       /      |       \
      a       n        a
     /        |         \
    n         a          $
   /          |
  a           $
 /
$

从根节点到叶节点的每条路径代表字符串的一个后缀。叶节点表示后缀的结束，美元符号 ($) 用于表示字符串的结束。

子节点存储整个单词而非单个字符。

后缀 Trie 的特性

后缀 Trie 的以下特性 −

    它是 trie，因此它以 trie 数据结构存储字符串的后缀。对于长度为 n 的字符串，有 n 个后缀。

    可以说它是字符串所有后缀的紧凑表示。为了节省空间，通过折叠只有一个子节点的节点，它会变成 Suffix Tree。

    后缀 trie 对于子字符串搜索、模式匹配以及其他字符串相关操作非常有效。

后缀 Trie 的操作

后缀 trie 的常见操作包括：

  • 插入： 将新后缀插入到 trie 中。
  • 删除： 从 trie 中移除后缀。
  • 搜索： 在 trie 中查找特定后缀。

后缀 Trie 的插入操作

我们可以通过以下步骤将一个新后缀插入到 Trie 中：

1. 从根节点开始。
2. 对于后缀中的每个字符：
    a. 如果当前节点的子节点中不存在该字符，则为该字符创建一个新节点。
    b. 然后移动到对应字符的子节点并重复该过程。
3. 对后缀中的所有字符重复该过程。
4. 将最后一个节点标记为叶子节点，以表示后缀的结束。

插入操作的代码

例如，要将后缀 "ana" 插入到 Trie 中，我们将按照以下步骤进行：

C C++ Java Python 

#include <stdio.h>
#include <stdlib.h>

#define ALPHABET_SIZE 26

// Trie 节点结构
struct TrieNode {
   struct TrieNode* children[ALPHABET_SIZE];
   int isEndOfWord;
};

// 创建新 Trie 节点函数
struct TrieNode* createNode() {
   struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
   node->isEndOfWord = 0;
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      node->children[i] = NULL;
   }
   return node;
}

// 将后缀插入到 Trie 中的函数
void insert(struct TrieNode* root, const char* suffix) {
   struct TrieNode* current = root;
   for (int i = 0; suffix[i] != '\0'; i++) {
      int index = suffix[i] - 'a';
      if (current->children[index] == NULL) {
         current->children[index] = createNode();
      }
      current = current->children[index];
   }
   current->isEndOfWord = 1;
}

// 显示 Trie
void display(struct TrieNode* root, char str[], int level) {
   if (root->isEndOfWord) {
      str[level] = '\0';
      printf("%s\n", str);
   }
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      if (root->children[i] != NULL) {
         str[level] = i + 'a';
         display(root->children[i], str, level + 1);
      }
   }
}

int main() {
   struct TrieNode* root = createNode();
   insert(root, "banana");
   insert(root, "ana");
   insert(root, "na");
   insert(root, "a");
   insert(root, "$");

   char str[20];  // 为字符串缓冲区分配内存
   display(root, str, 0);

   return 0;
}

输出

以上代码的输出如下：

a
ana
banana
na


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

#define ALPHABET_SIZE 26

// Trie 节点结构
struct TrieNode {
   TrieNode* children[ALPHABET_SIZE];
   bool isEndOfWord;
};

// 创建新 Trie 节点函数
TrieNode* createNode() {
   TrieNode* node = new TrieNode();
   node->isEndOfWord = false;
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      node->children[i] = NULL;
   }
   return node;
}

// 将后缀插入到 Trie 中的函数
void insert(TrieNode* root, const string& suffix) {
   TrieNode* current = root;
   for (char c : suffix) {
      int index = c - 'a';
      if (current->children[index] == NULL) {
         current->children[index] = createNode();
      }
      current = current->children[index];
   }
   current->isEndOfWord = true;
}

// 显示 Trie
void display(TrieNode* root, char str[], int level) {
   if (root->isEndOfWord) {
      str[level] = '\0';
      cout << str << endl;
   }
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      if (root->children[i] != NULL) {
         str[level] = i + 'a';
         display(root->children[i], str, level + 1);
      }
   }
}

int main() {
   TrieNode* root = createNode();
   insert(root, "banana");
   insert(root, "ana");
   insert(root, "na");
   insert(root, "a");
   insert(root, "$");

   char str[20];  // 为字符串缓冲区分配内存
   display(root, str, 0);

   return 0;
}

输出

以上代码的输出如下：

a
ana
banana
na



class TrieNode {
   TrieNode[] children;
   boolean isEndOfWord;

   TrieNode() {
      children = new TrieNode[26]; // 仅支持 'a' 到 'z'
      isEndOfWord = false;
   }
}

public class Main {
   static final int ALPHABET_SIZE = 26;

   // 将后缀插入到 Trie 中的函数
   static void insert(TrieNode root, String suffix) {
      TrieNode current = root;
      for (int i = 0; i < suffix.length(); i++) {
         char ch = suffix.charAt(i);

         // 忽略非字母字符
         if (ch < 'a' || ch > 'z') continue;

         int index = ch - 'a';
         if (current.children[index] == null) {
            current.children[index] = new TrieNode();
         }
         current = current.children[index];
      }
      current.isEndOfWord = true;
   }

   // 显示 Trie
   static void display(TrieNode root, char[] str, int level) {
      if (root.isEndOfWord) {
         System.out.println(new String(str, 0, level)); // 正确打印子字符串
      }
      for (int i = 0; i < ALPHABET_SIZE; i++) {
         if (root.children[i] != null) {
            str[level] = (char) (i + 'a');
            display(root.children[i], str, level + 1);
         }
      }
   }

   public static void main(String[] args) {
      TrieNode root = new TrieNode();
      insert(root, "banana");
      insert(root, "ana");
      insert(root, "na");
      insert(root, "a");
      insert(root, "$");  // '$' 将被安全忽略

      char[] str = new char[20];  // 为字符串缓冲区分配内存
      display(root, str, 0);
   }
}

输出

以上代码的输出如下：

a
ana
banana
na

# Python 程序：将后缀插入到 Trie 中
# Python Program to insert a suffix into a trie

class TrieNode:
    def __init__(self):
        self.children = [None] * 26  # 仅支持 'a' 到 'z'
        self.isEndOfWord = False

# 将后缀插入到 Trie 中的函数
def insert(root, suffix):
    current = root
    for c in suffix:
        # 忽略非字母字符
        if not ('a' <= c <= 'z'):
            continue  # 跳过无效字符

        index = ord(c) - ord('a')
        if current.children[index] is None:
            current.children[index] = TrieNode()
        current = current.children[index]
    current.isEndOfWord = True

# 显示 Trie
def display(root, str, level):
    if root.isEndOfWord:
        print(''.join(str[:level]))  # 打印有效单词

    for i in range(26):
        if root.children[i] is not None:
            str[level] = chr(i + ord('a'))
            display(root.children[i], str, level + 1)

if __name__ == '__main__':
    root = TrieNode()
    insert(root, "banana")
    insert(root, "ana")
    insert(root, "na")
    insert(root, "a")
    insert(root, "$")  # '$' 将被安全忽略

    str = [''] * 20  # 为字符串缓冲区分配内存
    display(root, str, 0)

输出

以上代码的输出如下：

a
ana
banana
na

后缀 Trie 的删除和搜索操作

后缀 Trie 的删除和搜索操作与插入类似。我们可以通过从 Trie 中移除对应的叶子节点来删除一个后缀。要搜索特定的后缀，可以从根节点遍历到对应后缀的叶子节点。

从 Trie 中删除后缀的步骤如下：

1. 从根节点开始。
2. 对于后缀中的每个字符：
    a. 移动到对应字符的子节点。
3. 将最后一个节点标记为非叶子节点以删除后缀。

在 Trie 中搜索特定后缀的步骤如下：

1. 从根节点开始。
2. 对于后缀中的每个字符：
    a. 移动到对应字符的子节点。
3. 检查最后一个节点是否为叶子节点以找到后缀。

删除和搜索操作的代码

以下是后缀 Trie 删除和搜索操作的代码：

C C++ Java Python 

#include <stdio.h>
#include <stdlib.h>

#define ALPHABET_SIZE 26

// Trie 节点结构
struct TrieNode {
   struct TrieNode* children[ALPHABET_SIZE];
   int isEndOfWord;
};

// 创建新 Trie 节点函数
struct TrieNode* createNode() {
   struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
   node->isEndOfWord = 0;
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      node->children[i] = NULL;
   }
   return node;
}

// 将后缀插入 Trie 的函数
void insert(struct TrieNode* root, const char* suffix) {
   struct TrieNode* current = root;
   for (int i = 0; suffix[i] != '\0'; i++) {
      int index = suffix[i] - 'a';
      if (current->children[index] == NULL) {
         current->children[index] = createNode();
      }
      current = current->children[index];
   }
   current->isEndOfWord = 1;
}

// 从 Trie 中删除后缀的函数
void delete(struct TrieNode* root, const char* suffix) {
   struct TrieNode* current = root;
   for (int i = 0; suffix[i] != '\0'; i++) {
      int index = suffix[i] - 'a';
      if (current->children[index] == NULL) {
         return;  // 后缀未找到
      }
      current = current->children[index];
   }
   current->isEndOfWord = 0;
}

// 在 Trie 中搜索后缀的函数
int search(struct TrieNode* root, const char* suffix) {
   struct TrieNode* current = root;
   for (int i = 0; suffix[i] != '\0'; i++) {
      int index = suffix[i] - 'a';
      if (current->children[index] == NULL) {
         return 0;  // 后缀未找到
      }
      current = current->children[index];
   }
   return current->isEndOfWord;
}

int main() {
   struct TrieNode* root = createNode();
   insert(root, "banana");
   insert(root, "ana");
   insert(root, "na");
   insert(root, "a");
   insert(root, "$");

   printf("Search for 'ana': %s\n", search(root, "ana") ? "Found" : "Not found");
   delete(root, "ana");
   printf("After deletion:\n");
   printf("Search for 'ana': %s\n", search(root, "ana") ? "Found" : "Not found");
   printf("Search for 'na': %s\n", search(root, "na") ? "Found" : "Not found");

   return 0;
}

输出

以上代码的输出如下：

Search for 'ana': Found
After deletion:
Search for 'ana': Not found
Search for 'na': Found


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

#define ALPHABET_SIZE 26

// Trie 节点结构
struct TrieNode {
   TrieNode* children[ALPHABET_SIZE];
   bool isEndOfWord;
};

// 创建新 Trie 节点函数
TrieNode* createNode() {
   TrieNode* node = new TrieNode();
   node->isEndOfWord = false;
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      node->children[i] = NULL;
   }
   return node;
}

// 将后缀插入 Trie 的函数
void insert(TrieNode* root, const string& suffix) {
   TrieNode* current = root;
   for (char c : suffix) {
      int index = c - 'a';
      if (current->children[index] == NULL) {
         current->children[index] = createNode();
      }
      current = current->children[index];
   }
   current->isEndOfWord = true;
}

// 从 Trie 中删除后缀的函数
void deleteN(TrieNode* root, const string& suffix) {
   TrieNode* current = root;
   for (char c : suffix) {
      int index = c - 'a';
      if (current->children[index] == NULL) {
         return;  // 后缀未找到
      }
      current = current->children[index];
   }
   current->isEndOfWord = false;
}

// 在 Trie 中搜索后缀的函数
bool search(TrieNode* root, const string& suffix) {
   TrieNode* current = root;
   for (char c : suffix) {
      int index = c - 'a';
      if (current->children[index] == NULL) {
         return false;  // 后缀未找到
      }
      current = current->children[index];
   }
   return current->isEndOfWord;
}

int main() {
   TrieNode* root = createNode();
   insert(root, "banana");
   insert(root, "ana");
   insert(root, "na");
   insert(root, "a");
   insert(root, "$");

   cout << "Search for 'ana': " << (search(root, "ana") ? "Found" : "Not found") << endl;
   deleteN(root, "ana");
   cout << "After deletion:\n";
   cout << "Search for 'ana': " << (search(root, "ana") ? "Found" : "Not found") << endl;
   cout << "Search for 'na': " << (search(root, "na") ? "Found" : "Not found") << endl;

   return 0;
}

输出

以上代码的输出如下：

Search for 'ana': Found
After deletion:
Search for 'ana': Not found
Search for 'na': Found



class TrieNode {
   TrieNode[] children;
   boolean isEndOfWord;

   TrieNode() {
      children = new TrieNode[26]; // 只支持 'a' 到 'z'
      isEndOfWord = false;
   }
}

public class Main {
   static final int ALPHABET_SIZE = 26;

   // 将后缀插入 Trie 的函数
   static void insert(TrieNode root, String suffix) {
      TrieNode current = root;
      for (int i = 0; i < suffix.length(); i++) {
         char ch = suffix.charAt(i);

         // 忽略非字母字符
         if (ch < 'a' || ch > 'z') continue;

         int index = ch - 'a';
         if (current.children[index] == null) {
            current.children[index] = new TrieNode();
         }
         current = current.children[index];
      }
      current.isEndOfWord = true;
   }

   // 从 Trie 中删除后缀的函数
   static void delete(TrieNode root, String suffix) {
      TrieNode current = root;
      for (int i = 0; i < suffix.length(); i++) {
         char ch = suffix.charAt(i);

         // 忽略非字母字符
         if (ch < 'a' || ch > 'z') return;

         int index = ch - 'a';
         if (current.children[index] == null) {
            return;  // 后缀未找到
         }
         current = current.children[index];
      }
      current.isEndOfWord = false;
   }

   // 在 Trie 中搜索后缀的函数
   static boolean search(TrieNode root, String suffix) {
      TrieNode current = root;
      for (int i = 0; i < suffix.length(); i++) {
         char ch = suffix.charAt(i);

         // 忽略非字母字符
         if (ch < 'a' || ch > 'z') return false;

         int index = ch - 'a';
         if (current.children[index] == null) {
            return false;  // 后缀未找到
         }
         current = current.children[index];
      }
      return current.isEndOfWord;
   }

   public static void main(String[] args) {
      TrieNode root = new TrieNode();
      insert(root, "banana");
      insert(root, "ana");
      insert(root, "na");
      insert(root, "a");
      insert(root, "$");

      System.out.println("Search for 'ana': " + (search(root, "ana") ? "Found" : "Not found"));
      delete(root, "ana");
      System.out.println("After deletion:");
      System.out.println("Search for 'ana': " + (search(root, "ana") ? "Found" : "Not found"));
      System.out.println("Search for 'na': " + (search(root, "na") ? "Found" : "Not found"));
   }
}

输出

以上代码的输出如下：

Search for 'ana': Found
After deletion:
Search for 'ana': Not found
Search for 'na': Found



class TrieNode:
    def __init__(self):
        self.children = [None] * 26  # 只支持 'a' 到 'z'
        self.isEndOfWord = False

# 将后缀插入 Trie 的函数
def insert(root, suffix):
    current = root
    for c in suffix:
        # 忽略非字母字符
        if not ('a' <= c <= 'z'):
            continue  # 跳过无效字符

        index = ord(c) - ord('a')
        if current.children[index] is None:
            current.children[index] = TrieNode()
        current = current.children[index]
    current.isEndOfWord = True

# 从 Trie 中删除后缀的函数
def delete(root, suffix):
    current = root
    for c in suffix:
        # 忽略非字母字符
        if not ('a' <= c <= 'z'):
            return  # 跳过无效字符

        index = ord(c) - ord('a')
        if current.children[index] is None:
            return  # 后缀未找到
        current = current.children[index]
    current.isEndOfWord = False

# 在 Trie 中搜索后缀的函数
def search(root, suffix):
    current = root
    for c in suffix:
        # 忽略非字母字符
        if not ('a' <= c <= 'z'):
            return False  # 跳过无效字符

        index = ord(c) - ord('a')
        if current.children[index] is None:
            return False  # 后缀未找到
        current = current.children[index]
    return current.isEndOfWord

if __name__ == '__main__':
   root = TrieNode()
   insert(root, "banana")
   insert(root, "ana")
   insert(root, "na")
   insert(root, "a")
   insert(root, "$")

   print("Search for 'ana':", "Found" if search(root, "ana") else "Not found")
   delete(root, "ana")
   print("After deletion:")
   print("Search for 'ana':", "Found" if search(root, "ana") else "Not found")
   print("Search for 'na':", "Found" if search(root, "na") else "Not found")

输出

以上代码的输出如下：

Search for 'ana': Found
After deletion:
Search for 'ana': Not found
Search for 'na': Found

后缀 Trie 的时间复杂度

后缀 Trie 的时间复杂度取决于执行的操作：

  • 插入：将长度为 n 的后缀插入 Trie，需要 O(n) 时间。
  • 删除：O(n)
  • 搜索：O(n)

后缀 Trie 的应用

后缀 Trie 被用于各种应用，包括：

  • 模式匹配和子串搜索算法
  • 文本索引和搜索
  • 基因组序列分析
  • 拼写检查和校正
  • 生物序列分析
  • 信息检索
  • 压缩算法

结论

在本章中，我们讨论了后缀 Trie，这是一种用于表示字符串所有后缀的 Trie 类型。我们探讨了后缀 Trie 的结构、特性、操作及其应用。后缀 Trie 是一种强大的数据结构，适用于子串搜索、模式匹配以及其他字符串相关操作。