Рубрики

Алгоритм Касая для построения массива LCP из суффиксного массива

Фон
Массив суффиксов: Массив суффиксов — это отсортированный массив всех суффиксов данной строки.
Пусть данная строка будет «бананом».

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

Массив суффиксов для «банана»:

суффикс [] = {5, 3, 1, 0, 4, 2}

Мы обсудили массив суффиксов и его конструкцию O (nLogn) .

Как только массив суффиксов построен, мы можем использовать его для эффективного поиска шаблона в тексте. Например, мы можем использовать бинарный поиск, чтобы найти шаблон (полный код этого же обсуждается здесь )

LCP Array

Обсуждаемое здесь решение на основе бинарного поиска занимает время O (m * Logn), где m — длина искомого шаблона, а n — длина текста. С помощью массива LCP мы можем искать шаблон за O (m + Log n) времени. Например, если нашей задачей является поиск «ана» в «банане», m = 3, n = 5.

LCP Array — это массив размером n (как Suffix Array). Значение lcp [i] указывает длину самого длинного общего префикса суффиксов, исключая суффикс [i] и суффикс [i + 1]. Суффикс [n-1] не определен, так как после него нет суффикса.

txt[0..n-1] = "banana"
suffix[]  = {5, 3, 1, 0, 4, 2| 
lcp[]     = {1, 3, 0, 0, 2, 0}

Suffixes represented by suffix array in order are:
{"a", "ana", "anana", "banana", "na", "nana"}


lcp[0] = Longest Common Prefix of "a" and "ana"     = 1
lcp[1] = Longest Common Prefix of "ana" and "anana" = 3
lcp[2] = Longest Common Prefix of "anana" and "banana" = 0
lcp[3] = Longest Common Prefix of "banana" and "na" = 0
lcp[4] = Longest Common Prefix of "na" and "nana" = 2
lcp[5] = Longest Common Prefix of "nana" and None = 0

Как построить массив LCP?
Построение массива LCP выполняется двумя способами:
1) Вычислить массив LCP как побочный продукт для массива суффиксов (алгоритм Манбера и Майерса)
2) Используйте уже созданный массив суффиксов для вычисления значений LCP. Алгоритм Касаи.

Существуют алгоритмы, которые могут построить массив суффиксов за O (n) время, и поэтому мы всегда можем построить массив LCP за O (n) время. Но в приведенной ниже реализации обсуждается алгоритм O (n Log n).

Алгоритм Касая

В этой статье обсуждается алгоритм Касая. Алгоритм создает массив LCP из суффиксного массива и входного текста за O (n) времени. Идея основана на следующем факте:

Пусть lcp суффикса начинается с txt [i [be k. Если k больше 0, то lcp для суффикса, начинающегося с txt [i + 1], будет по крайней мере k-1. Причина в том, что относительный порядок символов остается неизменным. Если мы удаляем первый символ из обоих суффиксов, мы знаем, что будет соответствовать как минимум k символов. Например, для подстроки «ana» lcp равен 3, поэтому для строки «na» lcp будет не менее 2. Обратитесь к этому для доказательства.

Ниже приведена реализация алгоритма Касаи на С ++.

// C ++ программа для построения массива LCP для заданного текста
#include <bits/stdc++.h>

using namespace std;

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

struct suffix

{

    int index;  // Для сохранения исходного индекса

    int rank[2]; // Для сохранения рангов и пары следующих рангов

};

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

int cmp(struct suffix a, struct suffix b)

{

    return (a.rank[0] == b.rank[0])? (a.rank[1] < b.rank[1] ?1: 0):

           (a.rank[0] < b.rank[0] ?1: 0);

}

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

vector<int> buildSuffixArray(string txt, int n)

{

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

    struct suffix suffixes[n];

  

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

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

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

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

    {

        suffixes[i].index = i;

        suffixes[i].rank[0] = txt[i] - 'a';

        suffixes[i].rank[1] = ((i+1) < n)? (txt[i + 1] - 'a'): -1;

    }

  

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

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

    sort(suffixes, suffixes+n, cmp);

  

    // На этом этапе все суффиксы отсортированы по первому

    // 2 символа. Разберем суффиксы по первым 4

    // символы, затем первые 8 и т. д.

    int ind[n];  // Этот массив необходим для получения индекса в суффиксах []

    // из исходного индекса. Это отображение необходимо, чтобы получить

    // следующий суффикс.

    for (int k = 4; k < 2*n; k = k*2)

    {

        // Присвоение значений ранга и индекса первому суффиксу

        int rank = 0;

        int prev_rank = suffixes[0].rank[0];

        suffixes[0].rank[0] = rank;

        ind[suffixes[0].index] = 0;

  

        // Присвоение ранга суффиксам

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

        {

            // Если первый и следующий ранги такие же, как и в предыдущем

            // суффикс в массиве, присвоить этому суффиксу новый ранг

            if (suffixes[i].rank[0] == prev_rank &&

                    suffixes[i].rank[1] == suffixes[i-1].rank[1])

            {

                prev_rank = suffixes[i].rank[0];

                suffixes[i].rank[0] = rank;

            }

            else // Иначе увеличиваем ранг и присваиваем

            {

                prev_rank = suffixes[i].rank[0];

                suffixes[i].rank[0] = ++rank;

            }

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

        }

  

        // Назначаем следующий ранг каждому суффиксу

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

        {

            int nextindex = suffixes[i].index + k/2;

            suffixes[i].rank[1] = (nextindex < n)?

                                  suffixes[ind[nextindex]].rank[0]: -1;

        }

  

        // Сортировка суффиксов по первым k символам

        sort(suffixes, suffixes+n, cmp);

    }

  

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

    vector<int>suffixArr;

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

        suffixArr.push_back(suffixes[i].index);

  

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

    return  suffixArr;

}

  
/ * Для построения и возврата LCP * /

vector<int> kasai(string txt, vector<int> suffixArr)

{

    int n = suffixArr.size();

  

    // Хранить массив LCP

    vector<int> lcp(n, 0);

  

    // Вспомогательный массив для хранения обратного суффиксного массива

    // элементы. Например, если суффиксArr [0] равен 5,

    // invSuff [5] будет хранить 0. Это используется для получения следующего

    // строка суффикса из массива суффиксов.

    vector<int> invSuff(n, 0);

  

    // Заполняем значения в invSuff []

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

        invSuff[suffixArr[i]] = i;

  

    // Инициализируем длину предыдущего LCP

    int k = 0;

  

    // Обрабатываем все суффиксы один за другим, начиная с

    // первый суффикс в txt []

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

    {

        / * Если текущий суффикс равен n-1, то мы не

           есть следующая подстрока для рассмотрения. Так что lcp не

           определенный для этой подстроки, мы ставим ноль. * /

        if (invSuff[i] == n-1)

        {

            k = 0;

            continue;

        }

  

        / * j содержит индекс следующей подстроки

           считаться для сравнения с настоящим

           подстрока, т.е. следующая строка в массиве суффиксов * /

        int j = suffixArr[invSuff[i]+1];

  

        // Непосредственно начать сопоставление с k-го индекса как

        // будет соответствовать не менее k-1 символов

        while (i+k<n && j+k<n && txt[i+k]==txt[j+k])

            k++;

  

        lcp[invSuff[i]] = k; // lcp для настоящего суффикса.

  

        // Удаление начального символа из строки.

        if (k>0)

            k--;

    }

  

    // возвращаем построенный массив lcp

    return lcp;

}

  
// Сервисная функция для печати массива

void printArr(vector<int>arr, int n)

{

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

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

    cout << endl;

}

  
// Драйвер программы

int main()

{

    string str = "banana";

  

    vector<int>suffixArr = buildSuffixArray(str, str.length());

    int n = suffixArr.size();

  

    cout << "Suffix Array : \n";

    printArr(suffixArr, n);

  

    vector<int>lcp = kasai(str, suffixArr);

  

    cout << "\nLCP Array : \n";

    printArr(lcp, n);

    return 0;

}

Выход:

Suffix Array : 
5 3 1 0 4 2 

LCP Array : 
1 3 0 0 2 0

Иллюстрация:

txt[]     = "banana",  suffix[]  = {5, 3, 1, 0, 4, 2| 

Suffix array represents
{"a", "ana", "anana", "banana", "na", "nana"}

Inverse Suffix Array would be 
invSuff[] = {3, 2, 5, 1, 4, 0}

Значения LCP оцениваются в следующем порядке

Сначала мы вычисляем LCP первого суффикса в тексте, который является « бананом ». Нам нужен следующий суффикс в массиве суффиксов для вычисления LCP (помните, что lcp [i] определяется как самый длинный общий префикс суффикса [i] и суффикса [i + 1]). Чтобы найти следующий суффикс в суффиксе Arr [], мы используем SuffInv [] . Следующий суффикс — «на». Поскольку между «бананом» и «na» нет общего префикса, значение LCP для «банана» равно 0, а в суффиксном массиве оно имеет индекс 3, поэтому мы заполняем lcp [3] как 0.

Далее мы вычисляем LCP второго суффикса, который « анана ». Следующий суффикс «anana» в массиве суффиксов — «банан». Поскольку общего префикса не существует, значение LCP для «anana» равно 0, и оно находится в индексе 2 в массиве суффиксов, поэтому мы заполняем lcp [2] как 0.

Далее мы вычисляем LCP третьего суффикса, который « нана ». Поскольку следующего суффикса нет, значение LCP для «nana» не определено. Заполним lcp [5] как 0.

Следующий суффикс в тексте — «ана». Следующий суффикс « ana » в массиве суффиксов — «anana». Поскольку существует общий префикс длины 3, значение LCP для «ana» равно 3. Заполняем lcp [1] как 3.

Теперь мы lcp для следующего суффикса в тексте, который является « na ». Вот где алгоритм Касаи использует хитрость, согласно которой значение LCP должно быть не менее 2, поскольку предыдущее значение LCP было 3. Поскольку после «na» нет символа, конечное значение LCP равно 2. Заполняем lcp [4] как 2.

Следующий суффикс в тексте — « а ». Значение LCP должно быть не менее 1, потому что предыдущее значение было 2. Поскольку после «a» нет символа, конечное значение LCP равно 1. Заполняем lcp [0] как 1.

Вскоре мы обсудим реализацию поиска с помощью массива LCP и то, как массив LCP помогает сократить временную сложность до O (m + Log n).

Ссылки:
http://web.stanford.edu/class/cs97si/suffix-array.pdf
http://www.mi.fu-berlin.de/wiki/pub/ABI/RnaSeqP4/suffix-array.pdf
http://codeforces.com/blog/entry/12796

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

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

Алгоритм Касая для построения массива LCP из суффиксного массива

0.00 (0%) 0 votes