Алгоритм цифровой сортировки суффиксов циклической строки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Псевдокод)
м (Псевдокод)
Строка 31: Строка 31:
 
         //''преобразуем масив count''
 
         //''преобразуем масив count''
 
         '''for''' ('''int''' i = 1; i < count.size(); ++i)
 
         '''for''' ('''int''' i = 1; i < count.size(); ++i)
             count[i] += count[i - 1]
+
             count[i] += count[i - 1];
         '''rotate'''(count, 1)
+
         '''rotate'''(count, 1);
 
         //''сдвигаем массив на 1 вправо для удобства работы с индексами''
 
         //''сдвигаем массив на 1 вправо для удобства работы с индексами''
         count[0] = 0
+
         count[0] = 0;
 
         //''теперь он содержит позиции в массиве suffs с которых ''
 
         //''теперь он содержит позиции в массиве suffs с которых ''
 
         //''необходимо вставлять подстроки, начинающиеся с соответствующих символов''
 
         //''необходимо вставлять подстроки, начинающиеся с соответствующих символов''
 
     '''suff_array'''(string  &s)
 
     '''suff_array'''(string  &s)
         s += '#'
+
         s += '$';
         int alpha_size = 255
+
         int alpha_size = 255;
 
         //''На нулевом этапе сортируем подстроки длиной 1''
 
         //''На нулевом этапе сортируем подстроки длиной 1''
         '''vector''' count(max(alpha_size, s.length()))
+
         '''vector''' count(max(alpha_size, s.length()));
 
         //''count -- массив для сортировки подсчетом''
 
         //''count -- массив для сортировки подсчетом''
         '''fill'''(count, 0)
+
         '''fill'''(count, 0);
 
         '''for''' ('''int''' i = 0; i < s.length(); ++i)
 
         '''for''' ('''int''' i = 0; i < s.length(); ++i)
             ++count[ord(s[i])]
+
             ++count[ord(s[i])];
         '''calc_positions'''(count)
+
         '''calc_positions'''(count);
         '''vector''' suffs(s.length())
+
         '''vector''' suffs(s.length());
 
         //''suffs будет хранить индексы начал отсортированных подстрок текущей длины''
 
         //''suffs будет хранить индексы начал отсортированных подстрок текущей длины''
 
         '''for''' ('''int''' i = 0; i < s.length(); ++i)
 
         '''for''' ('''int''' i = 0; i < s.length(); ++i)
             suffs[count[ord(s[i])]++] = i
+
             suffs[count[ord(s[i])]++] = i;
 
         //''подстроки длиной 1 отсортированы''
 
         //''подстроки длиной 1 отсортированы''
 
         //''разобьем их на классы эквивалентности''
 
         //''разобьем их на классы эквивалентности''
         '''vector'''<'''int'''> classes(s.length())
+
         '''vector''' classes(s.length());
         '''int''' classes_count = 0
+
         '''int''' classes_count = 0;
         '''char''' last_char = '#'
+
         '''char''' last_char = '$';
 
         '''for''' ('''int''' i = 0; i < suffs.size(); ++i)
 
         '''for''' ('''int''' i = 0; i < suffs.size(); ++i)
 
             '''if''' s[suffs[i]] != last_char
 
             '''if''' s[suffs[i]] != last_char
                 last_char = s[suffs[i]]
+
                 last_char = s[suffs[i]];
                 ++classes_count
+
                 ++classes_count;
             classes[suffs[i]] = classes_count
+
             classes[suffs[i]] = classes_count;
 
         //''нулевой этап завершен''
 
         //''нулевой этап завершен''
 
         //''на следующих этапах сортируем подстроки длиной 2 * cur_len = 2^k''
 
         //''на следующих этапах сортируем подстроки длиной 2 * cur_len = 2^k''
 
         '''for''' ('''int''' cur_len = 1; cur_len <= s.length(); cur_len *= 2)
 
         '''for''' ('''int''' cur_len = 1; cur_len <= s.length(); cur_len *= 2)
 
             //''сортируем по второй половине подстроки''
 
             //''сортируем по второй половине подстроки''
             '''vector''' sorted_by2(s.length())
+
             '''vector''' sorted_by2(s.length());
 
             '''for''' ('''int''' i = 0; i < suffs.size(); ++i)
 
             '''for''' ('''int''' i = 0; i < suffs.size(); ++i)
 
                 '''if''' suffs[i] < cur_len
 
                 '''if''' suffs[i] < cur_len
                     sorted_by2[i] = suffs[i] + s.length() - cur_len
+
                     sorted_by2[i] = suffs[i] + s.length() - cur_len;
 
                 '''else'''
 
                 '''else'''
                     sorted_by2[i] = suffs[i] - cur_len
+
                     sorted_by2[i] = suffs[i] - cur_len;
 
             //''теперь сортируем по первой половине''
 
             //''теперь сортируем по первой половине''
 
             //''сортировка стабильна, значит получим целиком отсортированные подстроки''
 
             //''сортировка стабильна, значит получим целиком отсортированные подстроки''
             '''fill'''(count, 0)
+
             '''fill'''(count, 0);
 
             '''for''' ('''int''' i = 0; i < sorted_by2.size() ++i)
 
             '''for''' ('''int''' i = 0; i < sorted_by2.size() ++i)
                 ++count[classes[sorted_by2[i]]]
+
                 ++count[classes[sorted_by2[i]]];
             '''calc_positions'''(count)
+
             '''calc_positions'''(count);
 
             '''for''' ('''int''' i = 0; i < s.length(); ++i)
 
             '''for''' ('''int''' i = 0; i < s.length(); ++i)
                 suffs[count[classes[sorted_by2[i]]]++] = sorted_by2[i]
+
                 suffs[count[classes[sorted_by2[i]]]++] = sorted_by2[i];
 
             //''Подстроки текущей длины отсортированы''
 
             //''Подстроки текущей длины отсортированы''
 
             //''переcчитаем классы эквивалентности''
 
             //''переcчитаем классы эквивалентности''
             '''vector''' new_classes(s.length())
+
             '''vector''' new_classes(s.length());
             new_classes[suffs[0]] = 0
+
             new_classes[suffs[0]] = 0;
             classes_count = 0
+
             classes_count = 0;
 
             '''for''' ('''int''' i = 1; i < new_classes.size(); ++i)  
 
             '''for''' ('''int''' i = 1; i < new_classes.size(); ++i)  
                 '''int''' mid1 = (suffs[i] + cur_len) % suffs.size()
+
                 '''int''' mid1 = (suffs[i] + cur_len) % suffs.size();
                 '''int''' mid2 = (suffs[i-1] + cur_len) % suffs.size()
+
                 '''int''' mid2 = (suffs[i-1] + cur_len) % suffs.size();
 
                 '''if''' (classes[suffs[i]] != classes[suffs[i-1]] || classes[mid1] != classes[mid2])
 
                 '''if''' (classes[suffs[i]] != classes[suffs[i-1]] || classes[mid1] != classes[mid2])
                     ++classes_count
+
                     ++classes_count;
                 new_classes[suffs[i]] = classes_count
+
                 new_classes[suffs[i]] = classes_count;
             '''copy'''(new_classes, classes)//''сохраняем новые классы в classes''
+
             '''copy'''(new_classes, classes)//''сохраняем новые классы в classes'';
         '''return''' suffs
+
         '''return''' suffs;

Версия 14:50, 3 апреля 2012

Постановка задачи

Дана циклическая строка [math]s[/math]. Требуется отсортировать все её суффиксы. Поскольку строка циклическая, то и подстроки мы будем рассматривать циклические: под подстрокой [math]s[i..j][/math], когда [math]i \gt j[/math], понимается подстрока [math]s[i..n-1] + s[0..j][/math]. Кроме того, предварительно все индексы берутся по модулю длины строки.

Решение

Рассматриваемый алгоритм состоит из примерно [math]\log n[/math] фаз. На [math]k[/math]‐той фазе ([math]k=0..\lceil\log n\rceil [/math]) сортируются циклические подстроки длины [math]2^k[/math]. На последней, [math]\lceil\log n\rceil[/math]-ой фазе, будут сортироваться подстроки длины [math]2^{\lceil\log n\rceil} \ge n[/math], что эквивалентно сортировке циклических сдвигов.

На каждой фазе алгоритм помимо перестановки [math]p[0..n-1][/math] индексов циклических подстрок будет поддерживать для каждой циклической подстроки длиной [math]2^k[/math], начинающейся в позиции [math]i[/math], номер класса эквивалентности [math]c[i][/math], которому эта подстрока принадлежит. В самом деле, среди подстрок могут быть одинаковые, и алгоритму понадобится информация об этом. Кроме того, номера классов эквивалентности [math]c[i][/math] будем давать таким образом, чтобы они сохраняли и информацию о порядке: если один суффикс меньше другого, то и номер класса он должен получить меньший.

Описание алгоритма

На нулевой фазе мы должны отсортировать циклические подстроки длины [math]1[/math], т.е. отдельные символы строки, и разделить их на классы эквивалентности (одинаковые символы должны быть отнесены к одному классу эквивалентности). Это можно сделать сортировкой подсчётом. Для каждого символа посчитаем, сколько раз он встретился. Потом по этой информации восстановим массив [math]p[/math]. После этого проходом по массиву [math]p[/math] и сравнением символов строится массив [math]c[/math].

Далее, пусть мы выполнили [math]k-1[/math]-ю фазу (т.е. вычислили значения массивов [math]p[/math] и [math]c[/math] для неё). Научимся за [math]O(n)[/math] выполнять следующую, [math]k[/math]-ю, фазу. Поскольку фаз всего [math]O(\log n)[/math], это даст нам требуемый алгоритм с временем [math]O(n \log n)[/math].

Заметим, что циклическая подстрока длины [math]2^k[/math] состоит из двух подстрок длины [math]2^{k-1}[/math], которые мы можем сравнивать между собой за [math]O(1)[/math], используя информацию с предыдущей фазы — номера классов эквивалентности [math]c[/math]. Таким образом, для подстроки длины [math]2^k[/math], начинающейся в позиции [math]i[/math], вся необходимая информация содержится в паре чисел [math](c[i], c[i + 2^{k-1}])[/math].

Это даёт нам весьма простое решение: отсортировать подстроки длины [math]2^k[/math] просто по этим парам чисел, это и даст нам требуемый порядок, т.е. массив [math]p[/math]. Воспользуемся здесь приёмом, на котором основана цифровая сортировка: чтобы отсортировать пары, отсортируем их сначала по вторым элементам, а затем — по первым элементам (обязательно стабильной сортировкой). Однако отдельно вторые элементы уже упорядочены — этот порядок задан в массиве от предыдущей фазы. Тогда, чтобы упорядочить пары по вторым элементам, надо просто от каждого элемента массива [math]p[/math] отнять [math]2^{k-1}[/math] — это даст нам порядок сортировки пар по вторым элементам ([math]p[/math] даёт упорядочение подстрок длины [math]2^{k-1}[/math], и при переходе к строке вдвое большей длины эти подстроки становятся их вторыми половинками, поэтому от позиции второй половинки отнимается длина первой половинки).

Таким образом, мы производим сортировку по вторым элементам пар. Теперь надо произвести стабильную сортировку по первым элементам пар, её уже можно выполнить за [math]O(n)[/math] с помощью сортировки подсчётом.

Осталось только пересчитать номера классов эквивалентности [math]c[/math], просто пройдя по полученной новой перестановке [math]p[/math] и сравнивая соседние элементы (опять же, сравнивая как пары двух чисел).

Пример

s = abacaba$

Suffix-array2.png

Псевдокод

   calc_positions(vector &count)
        //преобразуем масив count
       for (int i = 1; i < count.size(); ++i)
           count[i] += count[i - 1];
       rotate(count, 1);
       //сдвигаем массив на 1 вправо для удобства работы с индексами
       count[0] = 0;
       //теперь он содержит позиции в массиве suffs с которых 
       //необходимо вставлять подстроки, начинающиеся с соответствующих символов
   suff_array(string  &s)
       s += '$';
       int alpha_size = 255;
       //На нулевом этапе сортируем подстроки длиной 1
       vector count(max(alpha_size, s.length()));
       //count -- массив для сортировки подсчетом
       fill(count, 0);
       for (int i = 0; i < s.length(); ++i)
           ++count[ord(s[i])];
       calc_positions(count);
       vector suffs(s.length());
       //suffs будет хранить индексы начал отсортированных подстрок текущей длины
       for (int i = 0; i < s.length(); ++i)
           suffs[count[ord(s[i])]++] = i;
       //подстроки длиной 1 отсортированы
       //разобьем их на классы эквивалентности
       vector classes(s.length());
       int classes_count = 0;
       char last_char = '$';
       for (int i = 0; i < suffs.size(); ++i)
           if s[suffs[i]] != last_char
               last_char = s[suffs[i]];
               ++classes_count;
           classes[suffs[i]] = classes_count;
       //нулевой этап завершен
       //на следующих этапах сортируем подстроки длиной 2 * cur_len = 2^k
       for (int cur_len = 1; cur_len <= s.length(); cur_len *= 2)
           //сортируем по второй половине подстроки
           vector sorted_by2(s.length());
           for (int i = 0; i < suffs.size(); ++i)
               if suffs[i] < cur_len
                   sorted_by2[i] = suffs[i] + s.length() - cur_len;
               else
                   sorted_by2[i] = suffs[i] - cur_len;
           //теперь сортируем по первой половине
           //сортировка стабильна, значит получим целиком отсортированные подстроки
           fill(count, 0);
           for (int i = 0; i < sorted_by2.size() ++i)
               ++count[classes[sorted_by2[i]]];
           calc_positions(count);
           for (int i = 0; i < s.length(); ++i)
               suffs[count[classes[sorted_by2[i]]]++] = sorted_by2[i];
           //Подстроки текущей длины отсортированы
           //переcчитаем классы эквивалентности
           vector new_classes(s.length());
           new_classes[suffs[0]] = 0;
           classes_count = 0;
           for (int i = 1; i < new_classes.size(); ++i) 
               int mid1 = (suffs[i] + cur_len) % suffs.size();
               int mid2 = (suffs[i-1] + cur_len) % suffs.size();
               if (classes[suffs[i]] != classes[suffs[i-1]] || classes[mid1] != classes[mid2])
                   ++classes_count;
               new_classes[suffs[i]] = classes_count;
           copy(new_classes, classes)//сохраняем новые классы в classes;
       return suffs;