Префикс-функция — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition = '''Префикс-функция''' ''(англ. prefix-function)'' от строки {{---}} длина наибольшего [[Период_и_бордер,_их_связь#Определения|бордера]] этой строки}}
+
|definition = '''Префикс-функция''' ''(англ. prefix-function)'' от строки {{---}} массив длин наибольших [[Период_и_бордер,_их_связь#Определения|бордеров]] для каждой позиции этой строки}}
 
Здесь и далее считаем, что символы в строках нумеруются с <tex>1</tex>.
 
Здесь и далее считаем, что символы в строках нумеруются с <tex>1</tex>.
  
Строка 9: Строка 9:
  
 
===Псевдокод===
 
===Псевдокод===
  '''Prefix_function''' (<tex>s</tex>)
+
  '''int'''[] Prefix_function(string s)
 
       fill(<tex>\pi</tex>, 0)
 
       fill(<tex>\pi</tex>, 0)
 
       '''for''' i = 1 '''to''' n
 
       '''for''' i = 1 '''to''' n
 
           '''for''' k = 1 '''to''' i
 
           '''for''' k = 1 '''to''' i
               '''if''' s[1..k] == s[i - k + 1..i])
+
               '''if''' s[1..k] == s[i - k + 1..i]
 
                   <tex>\pi</tex>[i] = k
 
                   <tex>\pi</tex>[i] = k
 
       '''return''' <tex>\pi</tex>
 
       '''return''' <tex>\pi</tex>
Строка 45: Строка 45:
 
*Избавимся от явных сравнений строк. Пусть мы вычислили <tex>\pi[i]</tex>, тогда, если <tex>s[i + 1] = s[\pi[i]]</tex>, то <tex>\pi[i + 1] = \pi[i] + 1</tex>. Если окажется, что <tex>s[i + 1] \ne s[\pi[i]]</tex>, то нужно попытаться попробовать подстроку меньшей длины. Хотелось бы сразу перейти к такому [[Период_и_бордер,_их_связь#Определения|бордеру]] наибольшей длины, для этого подберем такое <tex>k</tex>, что <tex>k = \pi(i) - 1</tex>. Делаем это следующим образом. За исходное <tex>k</tex> необходимо взять <tex>\pi(i - 1)</tex>, что следует из первого пункта. В случае, когда символы <tex>s[k+1]</tex> и <tex>s[i]</tex> не совпадают, <tex>\pi(k)</tex> {{---}} следующее потенциальное наибольшее значение <tex>k</tex>, что видно из рисунка. Последнее утверждение верно, пока <tex>k>0</tex>, что позволит всегда найти его следующее значение. Если <tex>k=0</tex>, то <tex>\pi(i)=1</tex> при <tex>s[i] = s[1]</tex> , иначе <tex>\pi(i)=0</tex>.
 
*Избавимся от явных сравнений строк. Пусть мы вычислили <tex>\pi[i]</tex>, тогда, если <tex>s[i + 1] = s[\pi[i]]</tex>, то <tex>\pi[i + 1] = \pi[i] + 1</tex>. Если окажется, что <tex>s[i + 1] \ne s[\pi[i]]</tex>, то нужно попытаться попробовать подстроку меньшей длины. Хотелось бы сразу перейти к такому [[Период_и_бордер,_их_связь#Определения|бордеру]] наибольшей длины, для этого подберем такое <tex>k</tex>, что <tex>k = \pi(i) - 1</tex>. Делаем это следующим образом. За исходное <tex>k</tex> необходимо взять <tex>\pi(i - 1)</tex>, что следует из первого пункта. В случае, когда символы <tex>s[k+1]</tex> и <tex>s[i]</tex> не совпадают, <tex>\pi(k)</tex> {{---}} следующее потенциальное наибольшее значение <tex>k</tex>, что видно из рисунка. Последнее утверждение верно, пока <tex>k>0</tex>, что позволит всегда найти его следующее значение. Если <tex>k=0</tex>, то <tex>\pi(i)=1</tex> при <tex>s[i] = s[1]</tex> , иначе <tex>\pi(i)=0</tex>.
  
[[Файл:Prfxx.png‎]]
+
[[Файл:Untitled-1.jpg|800px]]
 
===Псевдокод===
 
===Псевдокод===
  '''Prefix_function''' (<tex>s</tex>)
+
  '''int'''[] Prefix_function(string s)
 
       <tex>\pi</tex>[1] = 0
 
       <tex>\pi</tex>[1] = 0
 
       '''for''' i = 2 '''to''' n
 
       '''for''' i = 2 '''to''' n
 
           k = <tex>\pi</tex>[i-1]
 
           k = <tex>\pi</tex>[i-1]
           '''while''' k > 0 && s[i] != s[k + 1]  
+
           '''while''' k > 0 '''and''' s[i] != s[k + 1]  
 
               k = <tex>\pi</tex>[k]
 
               k = <tex>\pi</tex>[k]
 
           '''if''' s[i] == s[k + 1]
 
           '''if''' s[i] == s[k + 1]
Строка 91: Строка 91:
 
**  <tex>p[n] = 0</tex>. Тогда мы добавляем новый символ, поэтому <tex>q[n]</tex> тоже будет равно <tex>0</tex>.  
 
**  <tex>p[n] = 0</tex>. Тогда мы добавляем новый символ, поэтому <tex>q[n]</tex> тоже будет равно <tex>0</tex>.  
 
** <tex>p[n] > 0</tex>. По свойствам префикс-функции <tex> s'[p[n]] = s'[n] </tex> {{---}} суффикс и префикс строки <tex> s' </tex> длины <tex> p[n] </tex> продолжаются одним символом, значит, надо на текущую позицию строки <tex> s </tex> поставить символ <tex> s[p[n]] </tex>. Если значение префикс-функции увеличивается, значит, текущим символом продолжается префикс длины <tex> p[n - 1] </tex>, а из свойств следует, что <tex> p[n - 1] \geqslant p[n] - 1 </tex>. По предположению индукцию значение <tex> q[n - 1] </tex> будет вычислено верно. А если значение префикс-функции не увеличивается, значит, символ <tex> s[n] </tex> должен продолжить префикс меньшей длины, а в текущее значение префикс-функции запишется как раз длина нового [[Период_и_бордер,_их_связь#Определения|бордера]]. Для этого будут использованы значения префикс-функции с меньшими индексами, которые посчитаны верно, опять же по предположению индукции.
 
** <tex>p[n] > 0</tex>. По свойствам префикс-функции <tex> s'[p[n]] = s'[n] </tex> {{---}} суффикс и префикс строки <tex> s' </tex> длины <tex> p[n] </tex> продолжаются одним символом, значит, надо на текущую позицию строки <tex> s </tex> поставить символ <tex> s[p[n]] </tex>. Если значение префикс-функции увеличивается, значит, текущим символом продолжается префикс длины <tex> p[n - 1] </tex>, а из свойств следует, что <tex> p[n - 1] \geqslant p[n] - 1 </tex>. По предположению индукцию значение <tex> q[n - 1] </tex> будет вычислено верно. А если значение префикс-функции не увеличивается, значит, символ <tex> s[n] </tex> должен продолжить префикс меньшей длины, а в текущее значение префикс-функции запишется как раз длина нового [[Период_и_бордер,_их_связь#Определения|бордера]]. Для этого будут использованы значения префикс-функции с меньшими индексами, которые посчитаны верно, опять же по предположению индукции.
 +
 +
== См. также ==
 +
*[[Z-функция|Z-функция]]
 +
*[[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
 +
  
 
== Источники информации ==
 
== Источники информации ==
 
*[http://e-maxx.ru/algo/prefix_function Префикс-функция — e-maxx]
 
*[http://e-maxx.ru/algo/prefix_function Префикс-функция — e-maxx]
*[http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F Префикс-функция — Википедия]
+
*[[wikipedia:ru:Префикс-функция | Википедия {{---}} Префикс-функция]]
 
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296 ISBN 978-5-8459-0857-5
 
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296 ISBN 978-5-8459-0857-5
 
== См. также ==
 
*[[Z-функция|Z-функция]]
 
*[[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
 
  
  

Версия 21:24, 14 мая 2014

Определение:
Префикс-функция (англ. prefix-function) от строки — массив длин наибольших бордеров для каждой позиции этой строки

Здесь и далее считаем, что символы в строках нумеруются с [math]1[/math].

Определим префикс-функцию от строки [math]s[/math] в позиции [math]i[/math] следующим образом: [math]\pi(s, i) = \max\limits_{k = 1..i - 1} \{k : [/math] [math]s[1..k] = s[i - k + 1..i] \}[/math]. Если мы не нашли такого [math]k[/math], то [math]\pi(s, i)=0[/math].

Наивный алгоритм

Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк. Обозначим длину строки за [math]n[/math]

Псевдокод

int[] Prefix_function(string s)
     fill([math]\pi[/math], 0)
     for i = 1 to n
         for k = 1 to i
             if s[1..k] == s[i - k + 1..i]
                 [math]\pi[/math][i] = k
     return [math]\pi[/math]

Пример

Рассмотрим строку abcabcd, для которой значение префикс-функции равно [math][0,0,0,1,2,3,0][/math].

Шаг Строка Значение функции
[math]1[/math] a 0
[math]2[/math] ab 0
[math]3[/math] abc 0
[math]4[/math] abca 1
[math]5[/math] abcab 2
[math]6[/math] abcabc 3
[math]7[/math] abcabcd 0

Время работы

Всего [math]O(n^2)[/math] итераций цикла, на каждой из который происходит сравнение строк за [math]O(n)[/math], что дает в итоге [math]O(n^3)[/math].

Эффективный алгоритм

Вносятся несколько важных замечаний:

  • Заметим, что [math]\pi[i + 1] \leqslant \pi[i] + 1[/math]. Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции [math]i + 1[/math] и имеющий длину [math]\pi[i + 1][/math], удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции [math]i[/math] и имеющий длину [math]\pi[i + 1] - 1[/math], следовательно неравенство [math]\pi[i + 1] \gt \pi[i] + 1[/math] неверно.
  • Избавимся от явных сравнений строк. Пусть мы вычислили [math]\pi[i][/math], тогда, если [math]s[i + 1] = s[\pi[i]][/math], то [math]\pi[i + 1] = \pi[i] + 1[/math]. Если окажется, что [math]s[i + 1] \ne s[\pi[i]][/math], то нужно попытаться попробовать подстроку меньшей длины. Хотелось бы сразу перейти к такому бордеру наибольшей длины, для этого подберем такое [math]k[/math], что [math]k = \pi(i) - 1[/math]. Делаем это следующим образом. За исходное [math]k[/math] необходимо взять [math]\pi(i - 1)[/math], что следует из первого пункта. В случае, когда символы [math]s[k+1][/math] и [math]s[i][/math] не совпадают, [math]\pi(k)[/math] — следующее потенциальное наибольшее значение [math]k[/math], что видно из рисунка. Последнее утверждение верно, пока [math]k\gt 0[/math], что позволит всегда найти его следующее значение. Если [math]k=0[/math], то [math]\pi(i)=1[/math] при [math]s[i] = s[1][/math] , иначе [math]\pi(i)=0[/math].

Untitled-1.jpg

Псевдокод

int[] Prefix_function(string s)
     [math]\pi[/math][1] = 0
     for i = 2 to n
         k = [math]\pi[/math][i-1]
         while k > 0 and s[i] != s[k + 1] 
             k = [math]\pi[/math][k]
         if s[i] == s[k + 1]
             k++
         [math]\pi[/math][i] = k
     return [math]\pi[/math]

Время работы

Время работы алгоритма составит [math]O(n)[/math]. Для доказательства этого нужно заметить, что итоговое количество итераций цикла [math]while[/math] определяет асимптотику алгоритма. Теперь стоит отметить, что [math]k[/math] увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение [math]k = n - 1[/math]. Поскольку внутри цикла [math]while[/math] значение [math]k[/math] лишь уменьшается, получается, что [math]k[/math] не может суммарно уменьшиться больше, чем [math]n-1[/math] раз. Значит цикл [math]while[/math] в итоге выполнится не более [math]n[/math] раз, что дает итоговую оценку времени алгоритма [math]O(n)[/math].

Построение строки по префикс-функции

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

Восстановить строку по префикс-функции за [math]O(N)[/math], считая алфавит неограниченным.

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

Пусть в массиве [math]p[/math] хранятся значения префикс-функции, в [math]s[/math] будет записан ответ. Пойдем по массиву [math]p[/math] слева направо.

Пусть мы хотим узнать значение [math]s[i][/math]. Для этого посмотрим на значение [math]p[i][/math]: если [math]p[i] =0[/math] тогда в [math]s[i][/math] запишем новый символ, иначе [math]s[i] = s[p[i]][/math]. Обратим внимание, что [math]s[p[i]][/math] нам уже известно, так как [math]p[i] \lt i[/math].

Реализация

string buildFromPrefix(int[] p):
  s = "" 
  for i = 0 to p.length - 1
      if p[i] == 0     
          s += new character
      else
          s += s[p[i]]
  return s

Доказательство корректности алгоритма

Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией. Также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну из них.

Пусть [math]p[/math] данная префикс-функция, [math]s'[/math] правильная строка, строку [math]s[/math] построил наш алгоритм, [math] q [/math] массив значений префикс-функции для [math]s[/math].

Докажем корректность индукцией по длине массива префикс-функции полученной строки. Для начала заметим, что на предыдущие значения массива [math] q [/math] прибавление нового символа не влияет, так как при подсчёте префикс-функции на [math] i [/math]-ой позиции рассматриваются символы на позициях не больше [math] i [/math]. Поэтому достаточно показать, что очередное значение префикс-функции будет вычислено правильно.

  • База очевидна для строки длины [math]1[/math].
  • Переход: пусть до [math]n[/math]-ой позиции мы построили строку, что [math]p[1..n - 1] = q[1..n - 1][/math]. Возможны два случая:
    • [math]p[n] = 0[/math]. Тогда мы добавляем новый символ, поэтому [math]q[n][/math] тоже будет равно [math]0[/math].
    • [math]p[n] \gt 0[/math]. По свойствам префикс-функции [math] s'[p[n]] = s'[n] [/math] — суффикс и префикс строки [math] s' [/math] длины [math] p[n] [/math] продолжаются одним символом, значит, надо на текущую позицию строки [math] s [/math] поставить символ [math] s[p[n]] [/math]. Если значение префикс-функции увеличивается, значит, текущим символом продолжается префикс длины [math] p[n - 1] [/math], а из свойств следует, что [math] p[n - 1] \geqslant p[n] - 1 [/math]. По предположению индукцию значение [math] q[n - 1] [/math] будет вычислено верно. А если значение префикс-функции не увеличивается, значит, символ [math] s[n] [/math] должен продолжить префикс меньшей длины, а в текущее значение префикс-функции запишется как раз длина нового бордера. Для этого будут использованы значения префикс-функции с меньшими индексами, которые посчитаны верно, опять же по предположению индукции.

См. также


Источники информации