×

Cài đặt thuật toán Suffix Tree trong lập trình

Avatar of admin
admin 1 Views

Trong quá trình lập trình, việc xử lý và phân tích chuỗi là một nhiệm vụ phổ biến và phức tạp. Một trong những cấu trúc dữ liệu mạnh mẽ giúp giải quyết bài toán này một cách hiệu quả là Suffix Tree (Cây Hậu Tố). Để triển khai thuật toán Suffix Tree, chúng ta cần hiểu rõ về khái niệm và cách xây dựng nó.

Khái Niệm

Suffix Tree là một cấu trúc dữ liệu chuyên dụng cho các chuỗi ký tự, giúp tổ chức và tìm kiếm các hậu tố của một chuỗi một cách hiệu quả. Nó có lợi thế trong việc hỗ trợ các thao tác như tìm kiếm chuỗi con, kiểm tra tần suất xuất hiện của một mẫu con, và so sánh các chuỗi.

Đặc Điểm Chính

  1. Tập trung vào hậu tố: Mỗi nút trong Suffix Tree đại diện cho một hậu tố của chuỗi.
  2. Tốc độ tìm kiếm: Việc tìm kiếm bất kỳ chuỗi con nào trong Suffix Tree diễn ra với thời gian tuyến tính.
  3. Bộ nhớ tiêu tốn: Mặc dù có lợi thế về tốc độ, Suffix Tree có thể chiếm nhiều bộ nhớ, đặc biệt là đối với các chuỗi dài.

Các Bước Xây Dựng

Việc xây dựng Suffix Tree thường được thực hiện qua các bước sau:

  1. Khởi tạo cây: Bắt đầu bằng việc tạo một cây trống.
  2. Thêm các hậu tố: Dần dần thêm từng hậu tố của chuỗi ban đầu vào cây.
  3. Tối ưu hóa: Có thể áp dụng các kỹ thuật nén để giảm bớt dung lượng sử dụng bộ nhớ.

Ví Dụ Minh Họa

Hãy xem xét việc xây dựng cây hậu tố cho chuỗi "banana". Các hậu tố của "banana" lần lượt là:

  • "banana"
  • "anana"
  • "nana"
  • "ana"
  • "na"
  • "a"

Bằng cách thêm từng hậu tố này vào cây, chúng ta có thể xây dựng được một cây hoàn chỉnh giúp tìm kiếm và phân tích chuỗi "banana" một cách hiệu quả.

Cài Đặt Trong C++

Dưới đây là một ví dụ về cách viết mã cài đặt Suffix Tree trong ngôn ngữ lập trình C++:

#include <bits/stdc++.h>
using namespace std;

struct SuffixTreeNode {
    map<char, SuffixTreeNode*> children;
    SuffixTreeNode* suffixLink;
    int start, *end, suffixIndex;

    SuffixTreeNode(int start, int* end) {
        this->start = start;
        this->end = end;
        suffixLink = NULL;
        suffixIndex = -1;
    }
};

class SuffixTree {
private:
    string text;
    SuffixTreeNode *root, *lastNewNode, *activeNode;
    int activeEdge, activeLength, remainingSuffixCount, leafEnd, *rootEnd, *splitEnd, size;

public:
    SuffixTree(string text) : text(text) {
        size = text.size();
        rootEnd = new int(-1);
        root = new SuffixTreeNode(-1, rootEnd);
        activeNode = root;
        buildSuffixTree();
    }
    
    void buildSuffixTree() {
        int i = 0;
        leafEnd = -1;
        
        for (; i < size; i++) extendSuffixTree(i);
    }

private:
    void extendSuffixTree(int pos) {
        leafEnd = pos;
        remainingSuffixCount++;

        lastNewNode = NULL;

        while(remainingSuffixCount > 0) {
            if (activeLength == 0) activeEdge = pos;

            if (activeNode->children.find(text[activeEdge]) == activeNode->children.end()) {
                activeNode->children[text[activeEdge]] = new SuffixTreeNode(pos, &leafEnd);

                if (lastNewNode != NULL) {
                    lastNewNode->suffixLink = activeNode;
                    lastNewNode = NULL;
                }
            } else {
                SuffixTreeNode* next = activeNode->children[text[activeEdge]];

                if (walkDown(next)) continue;

                if (text[next->start + activeLength] == text[pos]) {
                    if (lastNewNode != NULL && activeNode != root) {
                        lastNewNode->suffixLink = activeNode;
                        lastNewNode = NULL;
                    }
                    activeLength++;
                    break;
                }

                splitEnd = new int(next->start + activeLength - 1);
                SuffixTreeNode *split = new SuffixTreeNode(next->start, splitEnd);
                activeNode->children[text[activeEdge]] = split;

                split->children[text[pos]] = new SuffixTreeNode(pos, &leafEnd);
                next->start += activeLength;
                split->children[text[next->start]] = next;

                if (lastNewNode != NULL) lastNewNode->suffixLink = split;
                lastNewNode = split;
            }

            remainingSuffixCount--;

            if (activeNode == root && activeLength > 0) {
                activeLength--;
                activeEdge = pos - remainingSuffixCount + 1;
            } else if (activeNode != root) {
                activeNode = activeNode->suffixLink;
            }
        }
    }
    
    bool walkDown(SuffixTreeNode* currNode) {
        if (activeLength >= *(currNode->end) - currNode->start + 1) {
            activeEdge += *(currNode->end) - currNode->start + 1;
            activeLength -= *(currNode->end) - currNode->start + 1;
            activeNode = currNode;
            return true;
        }
        return false;
    }
};

Kết Luận

Suffix Tree là một cấu trúc dữ liệu mạnh mẽ giúp xử lý chuỗi hiệu quả trong lập trình. Việc hiểu và cài đặt Suffix Tree không chỉ cải thiện hiệu quả của các thuật toán xử lý chuỗi mà còn cung cấp một nền tảng mạnh mẽ cho các ứng dụng liên quan như nén dữ liệu, nhận diện mẫu, và phân tích cú pháp. Dù có thể phức tạp, nhưng với sự kiên trì và hiểu biết về cơ bản, lập trình viên có thể áp dụng Suffix Tree vào các dự án thực tế một cách hiệu quả.

Comments

Bài viết liên quan