Рубрики

Суффикс Массив | Комплект 1 (Введение)

Мы настоятельно рекомендуем прочитать следующий пост на деревьях суффиксов в качестве предварительного условия для этого поста.

Поиск по шаблону | Набор 8 (Введение в Суффикс-дерево)

Суффиксный массив — это отсортированный массив всех суффиксов данной строки . Определение похоже на Suffix Tree, которое является сжатым набором всех суффиксов данного текста . Любой алгоритм, основанный на дереве суффиксов, может быть заменен алгоритмом, который использует массив суффиксов, дополненный дополнительной информацией и решающий ту же проблему в той же сложности времени (Source Wiki ).
Суффиксный массив может быть создан из дерева суффиксов путем выполнения обхода DFS дерева суффиксов. Фактически массив суффиксов и дерево суффиксов могут быть построены друг от друга за линейное время.
Преимущества массивов суффиксов перед деревьями суффиксов включают улучшенные требования к пространству, более простые алгоритмы построения линейного времени (например, по сравнению с алгоритмом Укконена) и улучшенную локальность кэша (Источник: Wiki )

Пример:

Let the given string be "banana".

0 banana                          5 a
1 anana     Sort the Suffixes     3 ana
2 nana      ---------------->     1 anana  
3 ana        alphabetically       0 banana  
4 na                              4 na   
5 a                               2 nana

So the suffix array for "banana" is {5, 3, 1, 0, 4, 2}

Наивный метод построения суффиксного массива
Простой метод построения массива суффиксов состоит в том, чтобы создать массив всех суффиксов и затем отсортировать массив. Ниже приведена реализация простого метода.

// Наивный алгоритм построения суффиксного массива заданного текста
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

  
// Структура для хранения информации суффикса

struct suffix

{

    int index;

    char *suff;

};

  
// Функция сравнения, используемая sort () для сравнения двух суффиксов

int cmp(struct suffix a, struct suffix b)

{

    return strcmp(a.suff, b.suff) < 0? 1 : 0;

}

  
// Это основная функция, которая принимает строку 'txt' размера n как
// аргумент, строит и возвращает массив суффиксов для данной строки

int *buildSuffixArray(char *txt, int n)

{

    // Структура для хранения суффиксов и их индексов

    struct suffix suffixes[n];

  

    // Сохраняем суффиксы и их индексы в массиве структур.

    // Структура нужна для сортировки суффиксов по алфавиту

    // и поддерживаем свои старые индексы при сортировке

    for (int i = 0; i < n; i++)

    {

        suffixes[i].index = i;

        suffixes[i].suff = (txt+i);

    }

  

    // Сортировка суффиксов с использованием функции сравнения

    // определено выше.

    sort(suffixes, suffixes+n, cmp);

  

    // Сохраняем индексы всех отсортированных суффиксов в массиве суффиксов

    int *suffixArr = new int[n];

    for (int i = 0; i < n; i++)

        suffixArr[i] = suffixes[i].index;

  

    // Возвращаем массив суффиксов

    return  suffixArr;

}

  
// Вспомогательная функция для печати массива заданного размера

void printArr(int arr[], int n)

{

    for(int i = 0; i < n; i++)

        cout << arr[i] << " ";

    cout << endl;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    char txt[] = "banana";

    int n = strlen(txt);

    int *suffixArr = buildSuffixArray(txt,  n);

    cout << "Following is suffix array for " << txt << endl;

    printArr(suffixArr, n);

    return 0;

}

Выход:

Following is suffix array for banana
5 3 1 0 4 2

Временная сложность описанного выше метода для построения суффиксного массива составляет O (n 2 Logn), если мы рассмотрим алгоритм O (nLogn), используемый для сортировки. Сам этап сортировки занимает время O (n 2 Logn), поскольку каждое сравнение представляет собой сравнение двух строк, а сравнение занимает время O (n).
Существует множество эффективных алгоритмов для построения суффиксного массива. Вскоре мы будем освещать их как отдельные посты.

Поиск шаблона с использованием встроенного суффиксного массива
Чтобы найти шаблон в тексте, мы предварительно обрабатываем текст и строим массив суффиксов текста. Поскольку у нас есть отсортированный массив всех суффиксов, для поиска можно использовать бинарный поиск. Ниже приводится функция поиска. Обратите внимание, что функция не сообщает обо всех вхождениях шаблона, она сообщает только об одном из них.

// Этот код содержит только search () и main. Чтобы сделать его полным ходом
// приведенный выше код или см. https://ide.geeksforgeeks.org/oY7OkD

  
// Функция поиска на основе суффиксного массива для поиска по заданному шаблону
// 'pat' в данном тексте 'txt' с использованием суффиксного массива suffArr []

void search(char *pat, char *txt, int *suffArr, int n)

{

    int m = strlen(pat);  // получаем длину шаблона, необходимую для strncmp ()

  

    // Выполняем простой бинарный поиск патча в txt, используя

    // встроенный массив суффиксов

    int l = 0, r = n-1;  // Инициализируем левый и правый индексы

    while (l <= r)

    {

        // Посмотрим, является ли 'pat' префиксом среднего суффикса в массиве суффиксов

        int mid = l + (r - l)/2;

        int res = strncmp(pat, txt+suffArr[mid], m);

  

        // Если совпадение найдено в середине, вывести его и вернуть

        if (res == 0)

        {

            cout << "Pattern found at index " << suffArr[mid];

            return;

        }

  

        // Переместимся в левую половину, если шаблон по алфавиту меньше

        // средний суффикс

        if (res < 0) r = mid - 1;

  

        // Иначе переместимся на правую половину

        else l = mid + 1;

    }

  

    // Мы достигаем здесь, если оператор возврата в цикле не выполняется

    cout << "Pattern not found";

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    char txt[] = "banana"// текст

    char pat[] = "nan";   // шаблон для поиска в тексте

  

    // Построить массив суффиксов

    int n = strlen(txt);

    int *suffArr = buildSuffixArray(txt, n);

  

    // поиск патча в txt с использованием встроенного массива суффиксов

    search(pat, txt, suffArr, n);

  

    return 0;

}

Выход:

Pattern found at index 2

Временная сложность вышеуказанной функции поиска составляет O (mLogn). Существуют более эффективные алгоритмы поиска по шаблону после построения массива суффиксов. Фактически для поиска в паттерне существует алгоритм на основе массива суффиксов O (m). Скоро мы обсудим эффективный алгоритм поиска.

Приложения Suffix Array
Суффиксный массив — чрезвычайно полезная структура данных, он может использоваться для решения широкого круга задач. Ниже приведены некоторые известные проблемы, где можно использовать массив Suffix.
1) Поиск по шаблону
2) Нахождение самой длинной повторяющейся подстроки
3) Нахождение самой длинной общей подстроки
4) Нахождение самого длинного палиндрома в строке

Посмотрите это для большего количества проблем, где могут использоваться массивы Суффикса.

Этот пост является простым введением. В суффиксных массивах есть, что покрывать. Мы обсудили алгоритм O (nLogn) для построения суффиксного массива здесь . Мы скоро будем обсуждать более эффективные алгоритмы суффиксного массива.

Ссылки:
http://www.stanford.edu/class/cs97si/suffix-array.pdf
http://en.wikipedia.org/wiki/Suffix_array

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Суффикс Массив | Комплект 1 (Введение)

0.00 (0%) 0 votes