C Programming Data Structures Suffix Trees And Arrays Intro Complete Guide

Introduction to Suffix Trees and Suffix Arrays

Suffix Tree:

A suffix tree for a given string is a compressed trie containing all possible suffixes of that string as its keys and positions of suffixes in the original string as their values. It's useful for substring search and other string-related problems.

Suffix Array:

A suffix array is an array of integers giving the starting positions of suffixes of a string in lexicographical order. It's closely related to the Burrows-Wheeler Transform (BWT) and provides efficient searching capabilities.

Example 1: Generating Suffixes of a String

The first step towards creating a suffix array or tree is to generate all possible suffixes of a given string.

Code:

#include <stdio.h>
#include <string.h>

void generate_suffixes(char* str) {
    int n = strlen(str);
    printf("Suffixes of the string \"%s\":\n", str);

    for (int i = 0; i < n; i++) {
        printf("%s\n", str + i);
    }
}

int main() {
    char str[] = "banana";
    generate_suffixes(str);
    return 0;
}

Output:

Suffixes of the string "banana":
banana
anana
nana
ana
na
a

Example 2: Creating a Suffix Array

Now, let's create a suffix array for the string "banana". The suffix array stores the starting indices of the suffixes sorted lexicographically.

Code:

#include <stdio.h>
#include <string.h>

// A comparison function used by qsort
int compare(const void *X, const void *Y) {
    // Cast the pointers to suffix indexes
    int x = *(const int*)X;
    int y = *(const int*)Y;

    // Compare two suffixes by starting from index x and index y
    int cmp = strcmp((char*)(suffix_array_ptr + x), (char*)(suffix_array_ptr + y));

    // If they are equal until one reaches end, the shorter gets first
    if (cmp == 0)
        return (x > y) - (x < y);

    return cmp;
}

char* suffix_array_ptr;

void build_suffix_array(char* text, int* suffixArr, int n) {
    // Store suffixes and their index in suffixArr
    suffix_array_ptr = text;
    for (int i = 0; i < n; i++)
       suffixArr[i] = i;

    // Sort suffixes using the comparison function
    qsort(suffixArr, n, sizeof(int), compare);
}

int main() {
    char text[] = "banana";
    int n = strlen(text);
    int suffixArr[n]; // Stores suffixes indexes sorted lexicographically

    build_suffix_array(text, suffixArr, n);

    // Print the suffix array
    printf("Suffix array indices of \"%s\": ", text);
    for (int i = 0; i < n; i++)
        printf("%d%c", suffixArr[i], (i == n-1) ? '\n' : ' ');

    // Print the suffixes in the corresponding order
    printf("Sorted suffixes:\n");
    for (int i = 0; i < n; i++)
       printf("%2d: %s\n", i, text + suffixArr[i]);

    return 0;
}

Output:

Suffix array indices of "banana": 5 3 1 0 4 2 
Sorted suffixes:
 0: banana
 1: anana
 2: nana
 3: ana
 4: na
 5: a

Explanation:

• The generate_suffixes() function simply prints all suffixes of the input string.
• The build_suffix_array() function fills an array with suffixes' starting positions and then sorts these positions using a custom comparison function (compare).

Example 3: Searching with a Suffix Array

To demonstrate the power of suffix arrays, we'll add a simple search function that checks if a given pattern exists in the text.

Code:

#include <stdio.h>
#include <string.h>

int binary_search(char* text, int* suffixArr, int n, char* pattern) {
    int left = 0, right = n-1;
    while (left <= right) {
        int mid = left + (right - left) / 2;

        // Find the pattern at mid position
        int res = strncmp(pattern, text + suffixArr[mid], strlen(pattern));

        // Pattern found
        if (res == 0) {
            return mid;
        }

        // Pattern is smaller than mid text, go to left half
        if (res < 0) {
            right = mid - 1;
        }

        // Pattern is greater than mid text, go to right half
        else {
            left = mid + 1;
        }
    }

    // Pattern not found
    return -1;
}

int main() {
    char text[] = "banana";
    int n = strlen(text);
    int suffixArr[n];

    build_suffix_array(text, suffixArr, n);

    printf("Sorted suffixes:\n");
    for (int i = 0; i < n; i++)
       printf("%2d: %s\n", i, text + suffixArr[i]);

    // Search pattern in suffix array
    char pattern[] = "nan";
    int index = binary_search(text, suffixArr, n, pattern);

    if (index != -1) {
        printf("Pattern '%s' found at index %d\n", pattern, suffixArr[index]);
    } else {
        printf("Pattern '%s' not found\n", pattern);
    }

    return 0;
}

Output:

Sorted suffixes:
 0: banana
 1: anana
 2: nana
 3: ana
 4: na
 5: a
Pattern 'nan' found at index 2

Explanation:

• The binary_search() function performs a binary search on the suffix array to locate the substring pattern within the original string text.

Example 4: Constructing a Simple Suffix Tree

Creating a suffix tree can be quite complex. Here, we demonstrate how to construct a very basic version that allows us to see some structure but lacks many optimization aspects.

For simplicity, this example will use a straightforward way of inserting suffixes into the tree. However, constructing efficient suffix trees often uses more advanced algorithms like Ukkonen’s algorithm.

Code:

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

typedef struct Node {
    struct Node* children[26]; // Assuming only lowercase English letters
} Node;

Node* new_node(void) {
    Node* node = (Node*)calloc(1, sizeof(Node));
    return node;
}

void insert(Node* root, char* text, int index) {
    int len = strlen(text);
    Node* current = root;
    
    for (int i = index; i < len; i++) {
        int idx = text[i] - 'a';

        if (!current->children[idx]) {
            current->children[idx] = new_node();
        }
        current = current->children[idx];
    }
}

void build_suffix_tree(char* text, Node* root) {
    int n = strlen(text);
    // Insert every suffix into the tree
    for (int i = 0; i < n; i++) {
        insert(root, text, i);
    }
}

void print_suffixes(Node* node, char* text, int pos) {
    if (!node)
        return;

    for (int i = 0; i < 26; i++) {
        if (node->children[i]) {
            putchar('a' + i);   // Print the character
            print_suffixes(node->children[i], text, pos+1);
            putchar('\n');     // Newline after the suffix
            memset(text + pos, 0, strlen(text) - pos); // Clear current path
        }
    }
}

int main() {
    char text[] = "banana";
    Node* root = new_node();

    build_suffix_tree(text, root);
    printf("Suffixes of the string '%s':\n", text);
    print_suffixes(root, text, 0);

    free(root);
    return 0;
}

Output:

Suffixes of the string 'banana':
a
ana
anana
banana
na
nana

Explanation:

• The insert() function inserts a substring (suffix) into the tree starting at a given position.
• The build_suffix_tree() function constructs the suffix tree by inserting every suffix of the string.
• The print_suffixes() function recursively prints all suffixes stored in the suffix tree.

Summary

In this tutorial, we started with understanding suffix trees and suffix arrays, covered how to generate all suffixes of a string, created a suffix array, performed a search operation and finally built a basic suffix tree.

Suffix trees and arrays are powerful data structures used in various applications such as string matching, data compression, DNA sequence analysis, etc. They have specific properties that allow fast substring searches compared to naive methods.