Cây Trie của các Hậu tố (Suffix Trie)

Giới thiệu

Từ văn bản, ta sinh ra tất cả hậu tố để xây dựng cấu trúc cây Trie. Mọi mẫu xuất hiện trong văn bản đều là tiền tố của một hậu tố nào đó. Xây dựng Trie các hậu tố cho phép tìm kiếm chuỗi con trong thời gian tuyến tính.

Mỗi hậu tố kết thúc bằng ký tự kết thúc chuỗi. Từ mỗi nút, nếu có đường đi phù hợp thì tiến tiếp, ngược lại báo không tìm thấy.

Độ phức tạp: O(m + k), với m là độ dài chuỗi, k là tần suất xuất hiện của mẫu.

Đầu vào và Đầu ra

Đầu vào: Văn bản: "ABAAABCDBBABCDDEBCABC", Mẫu: "ABC"
Đầu ra: Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

Thuật toán

Sử dụng nút đặc biệt trieNode chứa chỉ số các hậu tố và con trỏ đến các nút con.

createTrie(root: trieNode, text)

Đầu vào: Nút gốc kiểu trieNode.

Đầu ra: Cây hậu tố từ chuỗi chính.

Begin
  với i := 0 đến độ dài text làm:
    lấy chuỗi con từ vị trí i đến cuối làm hậu tố, thêm chỉ số i vào trie
  done
End

findPat(pattern, node)

Đầu vào: Mẫu cần tìm và nút để kiểm tra trong cây con hậu tố

Đầu ra: Danh sách chỉ số nơi tìm thấy mẫu

Begin
  nếu kích thước pattern = 0 thì trả về suffIndex của node
  nếu node.suff[pattern[0]] ≠ ∅ thì
    trả về node.suff[pattern[0]].findPat(chuỗi con từ 1 đến cuối pattern)
  ngược lại trả về ∅
End

searchPat(pattern)

Đầu vào: Mẫu sẽ được tìm kiếm

Đầu ra: Danh sách chỉ số nơi mẫu được tìm thấy

Begin
  định nghĩa res là danh sách
  res := findPat(pattern)
  nếu res ≠ ∅ thì
    patLen := độ dài pattern
    với i := 0 đến cuối res làm:
      in tất cả chỉ số nơi pattern được tìm thấy
    done
End

Ví dụ (C++)

#include <iostream>
#include <list>
#define MAXCHAR 256
using namespace std;

class trieNode {
  trieNode *suff[MAXCHAR];
  list<int> *suffIndex;
public:
  trieNode() {
    suffIndex = new list<int>();
    for (int i = 0; i < MAXCHAR; i++) suff[i] = NULL;
  }
  void addSuffix(string suffix, int sIndex);
  list<int>* searchPattern(string pat);
};

void trieNode::addSuffix(string suffix, int sIndex) {
  suffIndex->push_back(sIndex);
  if (suffix.size() > 0) {
    char cIndex = suffix[0];
    if (suff[cIndex] == NULL) suff[cIndex] = new trieNode();
    suff[cIndex]->addSuffix(suffix.substr(1), sIndex + 1);
  }
}

list<int>* trieNode::searchPattern(string pattern) {
  if (pattern.size() == 0) return suffIndex;
  if (suff[pattern[0]] != NULL)
    return (suff[pattern[0]])->searchPattern(pattern.substr(1));
  else return NULL;
}

class trieSuffix {
  trieNode root;
public:
  trieSuffix(string mainString) {
    for (int i = 0; i < mainString.length(); i++)
      root.addSuffix(mainString.substr(i), i);
  }
  void searchPat(string pattern, int *locArray, int *index);
};

void trieSuffix::searchPat(string pattern, int *locArray, int *index) {
  list<int> *res = root.searchPattern(pattern);
  if (res != NULL) {
    list<int>::iterator it;
    int patLen = pattern.length();
    for (it = res->begin(); it != res->end(); it++) {
      (*index)++;
      locArray[(*index)] = *it - patLen;
    }
  }
}

int main() {
  string mainString = "ABAAABCDBBABCDDEBCABC";
  string pattern = "ABC";
  int locArray[mainString.size()];
  int index = -1;
  trieSuffix trie(mainString);
  trie.searchPat(pattern, locArray, &index);
  for(int i = 0; i <= index; i++) {
    cout << "Pattern found at position: " << locArray[i] << endl;
  }
}

Kết quả đầu ra

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18