Рубрики

Суффикс Массив | Набор 2 (алгоритм nLogn)

Поиск по шаблону, Продвинутые Структуры данных

Суффиксный массив — это отсортированный массив всех суффиксов данной строки. Определение похоже на Suffix Tree, которое является сжатым набором всех суффиксов данного текста.

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

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

Мы обсудили наивный алгоритм построения суффиксного массива . Наивный алгоритм состоит в том, чтобы рассмотреть все суффиксы, отсортировать их с помощью алгоритма сортировки O (nLogn) и при сортировке поддерживать исходные индексы. Временная сложность алгоритма Наивный составляет O (n 2 Logn), где n — количество символов во входной строке.

В этом посте обсуждается алгоритм O (nLogn) для построения массива суффиксов. Давайте сначала обсудим алгоритм O (n * Logn * Logn) для простоты. Идея состоит в том, чтобы использовать тот факт, что строки, которые должны быть отсортированы, являются суффиксами одной строки.
Сначала мы сортируем все суффиксы по первому символу, затем по первым 2 символам, затем по первым 4 символам и т. Д., В то время как количество символов, которые нужно рассмотреть, меньше 2n. Важным моментом является то, что если мы отсортировали суффиксы по первым 2 символам i , то мы можем отсортировать суффиксы по первым 2 i + 1 символам за O (nLogn), используя алгоритм сортировки nLogn, такой как Merge Sort. Это возможно, поскольку два суффикса можно сравнить за время O (1) (нам нужно сравнить только два значения, см. Пример и код ниже).
Функция сортировки называется O (Logn) раз (обратите внимание, что мы увеличиваем количество символов, которое должно учитываться в степени 2). Поэтому общая временная сложность становится O (nLognLogn). См. Http://www.stanford.edu/class/cs97si/suffix-array.pdf для получения дополнительной информации.

Давайте построим суффиксный массив в примере строки «банан», используя приведенный выше алгоритм.

Сортировка по первым двум символам. Присвойте ранг всем суффиксам, используя значение ASCII первого символа. Простой способ присвоить ранг — сделать «str [i] — 'a'» для i-го суффикса strp []

Index     Suffix            Rank
 0        banana             1   
 1        anana              0 
 2        nana               13 
 3        ana                0
 4        na                 13
 5        a                  0

Для каждого символа мы также сохраняем ранг следующего смежного символа, т. Е. Ранг символа в str [i + 1] (это необходимо для сортировки суффиксов по первым 2 символам). Если символ является последним, мы сохраняем следующий ранг как -1

Index    Suffix            Rank          Next Rank 
 0       banana             1              0
 1       anana              0              13    
 2       nana               13             0
 3       ana                0              13
 4       na                 13             0 
 5       a                  0             -1

Сортировка всех суффиксов в соответствии с рангом и смежным рангом. Ранг считается первой цифрой или MSD, а соседний ранг считается второй цифрой.

Index    Suffix            Rank          Next Rank 
 5        a                  0              -1
 1        anana              0               13    
 3        ana                0               13
 0        banana             1               0
 2        nana               13              0
 4        na                 13              0

Сортировать по первым четырем символам
Присвойте новые ранги всем суффиксам. Чтобы назначить новые ранги, мы рассмотрим отсортированные суффиксы один за другим. Присвойте 0 как новый ранг первому суффиксу. Для присвоения рангов оставшимся суффиксам мы рассматриваем пару рангов суффикса непосредственно перед текущим суффиксом. Если предыдущая пара рангов суффикса такая же, как предыдущий ранг суффикса непосредственно перед ним, тогда присвойте ему тот же ранг. В противном случае присваивайте ранг предыдущего суффикса плюс один.

Index       Suffix          Rank       
  5          a               0     [Assign 0 to first]        
  1          anana           1     (0, 13) is different from previous
  3          ana             1     (0, 13) is same as previous     
  0          banana          2     (1, 0) is different from previous      
  2          nana            3     (13, 0) is different from previous      
  4          na              3     (13, 0) is same as previous

Для каждого суффикса str [i] также храните ранг следующего суффикса в str [i + 2]. Если в i + 2 нет следующего суффикса, мы сохраняем следующий ранг как -1

Index       Suffix          Rank        Next Rank
  5          a               0             -1
  1          anana           1              1      
  3          ana             1              0 
  0          banana          2              3
  2          nana            3              3 
  4          na              3              -1

Сортировка всех суффиксов в соответствии с рангом и следующим рангом.

Index       Suffix          Rank        Next Rank
  5          a               0             -1
  3          ana             1              0 
  1          anana           1              1      
  0          banana          2              3
  4          na              3             -1
  2          nana            3              3

C ++

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

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 как
// аргумент, строит и возвращает массив суффиксов для данной строки

int *buildSuffixArray(char *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);

    }

  

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

    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;

}

Джава

// Java-код для реализации вышеуказанного подхода

import java.util.*;

class GFG

{

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

    public static class Suffix implements Comparable<Suffix>

    {

        int index;

        int rank;

        int next;

  

        public Suffix(int ind, int r, int nr) 

        {

            index = ind;

            rank = r;

            next = nr;

        }

          

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

        // сравнить два суффикса.

        // Сравнивает две пары, возвращает 1

        // если первая пара меньше

        public int compareTo(Suffix s) 

        {

            if (rank != s.rank) return Integer.compare(rank, s.rank);

            return Integer.compare(next, s.next);

        }

    }

      

    // Это основная функция, которая принимает строку 'txt'

    // размером n в качестве аргумента, строит и возвращает

    // суффиксный массив для заданной строки

    public static int[] suffixArray(String s) 

    {

        int n = s.length();

        Suffix[] su = new Suffix[n];

          

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

        // массив классов. Нужен класс

        // сортировать суффиксы по алфавиту и

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

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

        {

            su[i] = new Suffix(i, s.charAt(i) - '$', 0);

        }

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

            su[i].next = (i + 1 < n ? su[i + 1].rank : -1);

  

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

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

        Arrays.sort(su);

  

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

        // в соответствии с первыми 2 символами.

        // Давайте отсортируем суффиксы по первым 4

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

        int[] ind = new int[n];

          

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

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

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

        for (int length = 4; length < 2 * n; length <<= 1) 

        {

              

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

            int rank = 0, prev = su[0].rank;

            su[0].rank = rank;

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

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

            {

                // Если первый и следующий ряды совпадают с

                // тот из предыдущего суффикса в массиве,

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

                if (su[i].rank == prev &&

                    su[i].next == su[i - 1].next)

                {

                    prev = su[i].rank;

                    su[i].rank = rank;

                } 

                else 

                { 

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

                    prev = su[i].rank;

                    su[i].rank = ++rank;

                }

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

            }

              

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

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

            {

                int nextP = su[i].index + length / 2;

                su[i].next = nextP < n ? 

                   su[ind[nextP]].rank : -1;

            }

              

            // Сортировка суффиксов по

            // до первых k символов

            Arrays.sort(su);

        }

  

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

        // суффиксы в массиве суффиксов

        int[] suf = new int[n];

          

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

            suf[i] = su[i].index;

  

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

        return suf;

    }    

      

    static void printArr(int arr[], int n)

    {

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

            System.out.print(arr[i] + " ");

        System.out.println();

    }

      

    // Код драйвера

    public static void main(String[] args)

    {

        String txt = "banana";

        int n = txt.length();

        int[] suff_arr = suffixArray(txt);

        System.out.println("Following is suffix array for banana:");

        printArr(suff_arr, n);

    }

}

  
// Этот код предоставлен AmanKumarSingh

Выход:

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

Обратите внимание, что в приведенном выше алгоритме используется стандартная функция сортировки, поэтому временная сложность равна O (nLognLogn). Мы можем использовать Radix Sort, чтобы уменьшить сложность времени до O (nLogn).

Обратите внимание, что суффиксные массивы также могут быть созданы за O (n) время. Мы скоро будем обсуждать O (n) алгоритмы.

Ссылки:
http://www.stanford.edu/class/cs97si/suffix-array.pdf
http://www.cbcb.umd.edu/confcour/Fall2012/lec14b.pdf

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

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

Суффикс Массив | Набор 2 (алгоритм nLogn)

0.00 (0%) 0 votes