Викиконспекты - Вклад участника [ru]

Параллельный алгоритм нахождения выпуклой оболочки

2021-11-29T13:03:47Z

77.234.203.142: /* Параллельный алгоритм */

{{Задача
|definition = Пусть нам даны точки на плоскости. Нужно найти выпуклую оболочку на этих точках.
}}

{{Определение|definition='''Выпуклая оболочка''' {{---}} минимальная последовательность точек такая, что последовательное соединение этих точек дает выпуклый многоугольник, и в этом многоугольнике содержатся все точки.}}

==Последовательный алгоритм==

[[Файл:Parallel-convexhull-not-parallel-1.png|300px|thumb|right|Как мы будем двигаться]]

Давайте первым делом найдем самую левую A (при нескольких таких выбрать нижнюю) и самую правую B (при нескольких таких выбрать самую верхнюю) точку на плоскости.

Мы определенно знаем, что через них будет идти выпуклая оболочка, так как если она не будет идти через них, то это значит, что есть какой то отрезок между точками, который ниже и правее A, но это не так. Аналогично для правой верхней точки. Теперь будем строить от A до B верхнюю выпуклую оболочку для всех точек выше AB, и от B до A нижнюю выпуклую оболочку для всех точек ниже AB.

Теперь рассмотрим верхнюю половину. Нижняя будет выполняться аналогично. Берем середину из самое левой точки и правой точки по координате x и делим наше множество точек на две части каким то образом. Теперь нам нужно сделать объединение двух выпуклых оболочек за <tex>O(n)</tex>, для того, что бы итоговая асимптотика была <tex>O(n\log(n))</tex>

Прежде чем решать эту задачу, давайте решим такую задачу:

{{Задача
|definition = Нам дан выпуклый многоугольник, который был разрезан отрезком X, и взята верхняя часть. Так же дана точка, находящаяся выше X. Нужно провести касательную из точки к многоугольнику.
}}

[[Файл:Parallel-convex-hull-tangent.png|300px|thumb|right|Касательные]]

Мысленно представим соединение всех точек многоугольника с данной нам точкой. Заметим, что если мы воспользуемся [[Предикат_"левый_поворот"|предикатом "левый поворот"]], то сможем понять, находится ли точка, являющаяся касательной правее или левее, просто взяв предикат по точке куда ведем пересечение, данной точкой и следующей за точкой пересечения точкой. Проще говоря, нам нужно понять, "выше" ли находится прямая со следующей точкой или нет. Если оказалось, что она выше, то касательная находится выше. Если ниже, то касательная находится ниже.

Таким образом, мы можем за <tex>O(1)</tex> понимать для точки, дальше ли ее точка касательной или она была раньше. То есть у нас есть унимодальная функция, и нам нужно найти переход от <tex>0</tex> до <tex>1</tex>. Похоже на задачу бинарного поиска. Давайте опишем шаги:

'''int''' l = 0, r = n - 2
'''while''' 1 < r - l:
m = (l + r) / 2
'''if''' left_turn(a[m], K, a[m + 1]) > 0:
l = m
else:
r = m

Нахождение касательной из точки на многоугольник работает за <tex>O(\log(n))</tex>

{{Задача
|definition = Нам дано два выпуклых многоугольника A и B, которые были разрезаны отрезком X, и взята верхняя часть. Нужно провести такую касательную через 2 точки многоугольника, что все точки находятся либо на касательной либо ниже.
}}

[[Файл:Parallel-convex-hull-tangent-tangent.png|300px|thumb|right|Касательные из каждой точки]]

Давайте мысленно проведем касательные из каждой точки A на многоугольник B. Только одна из них является истинной. Здесь будет работать примерно такая же стратегия, что и в прошлом. Если мы понимаем с помощью предиката левого поворота, что касательная выше, то правильная точка находится до нашей, иначе дальше нашей. Снова сделаем бинпоиск. Только на сей раз проверка на то, что точка находится левее/правее нужной будет требовать от нас <tex>O(log(n))</tex>. Таким образом, алгоритм нахождения общей касательной будет работать за <tex>O(log^2(n))</tex>.

Теперь мы можем соединять две выпуклые оболочки в одну просто проводя касательную между ними и выпиливая у первого многоугольника все, что дальше точки касания, а у второго многоугольника все, что находится до точки касания за <tex>O(n)</tex>. Задача решена.

==Параллельный алгоритм==

[[Файл:Parallel-convex-hull-sqrt.png|300px|thumb|right|Касательные]]

Теперь нам нужно это как то ускорить. Давайте посмотрим, что же мы можем делать параллельно, и при этом не ухудшим асимптотику. Конечно же, у нас был поиск касательной за <tex>O(log^2(n))</tex>, а можно сделать его за <tex>work = O(n)</tex>, при этом уменьшив span

Посмотрим на каждую фазу бинпоиска. Заметим, что мы можем просто не брать бинпоиск, а разделить массив рассмотрения на <tex>\sqrt{n}</tex> частей.

Для каждого элемента посмотрим его результат (поймем, выше ли реальная касательная), и, если оказалось, что у нас и у точки, которая находится на <tex>\sqrt{n}</tex> различные результаты, то мы поймем, что правильный результат находится между нами. То есть мы возьмем все точки, которые находятся между нами, если у нас с соседом разные результаты и снова у каждой точки посмотрим, где находится верный результат. В этот раз мы уже точно узнаем результат, ведь теперь недостающих точек нет. То есть алгоритм будет такой:

1) Берем <tex>\sqrt{n}</tex>, <tex>2\sqrt{n}</tex>, <tex>3\sqrt{n}</tex>, ..., <tex>\sqrt{n}\sqrt{n}</tex> и параллельно проверяем, подходят ли они под условие. Каждая из них возвращает <tex>0</tex> или <tex>1</tex> - левее или правее они результата. Каждый результат считает за себя <tex>k\sqrt{n}</tex> и за соседа <tex>(k + 1)\sqrt{n}</tex>.

2) Если оказалось, что результаты разные, то мы берем <tex>k\sqrt{n}</tex>, <tex>k\sqrt{n} + 1</tex>, <tex>k\sqrt{n} + 2</tex>, ..., <tex>(k + 1)\sqrt{n}</tex>, и смотрим параллельно подходят ли они под условия. Каждое их них возвращает 0 или 1 - левее или правее находится результат. В точке, где меняет 0 и 1 и есть верный ответ.

Таким образом, у нас выходит примерно такой алгоритм -

1) Создаем функцию, которая находит касательную для точки из первого многоугольника на второй многоугольник.

fun getFromPoint(K):
'''int''' startAfter
'''pfor''' i = 0...sqrt(n):
'''int''' startCurrent = sqrt(n) * i
'''int''' startNext = sqrt(n) * i + 1
'''int''' finishCurrent = sqrt(n) * i
'''int''' finishNext = sqrt(n) * i + 1
'''boolean''' isStartBeforeAnswer = left_turn(startCurrent, K, startNext) > 0
'''boolean''' isFinishBeforeAnswer = left_turn(finishCurrent, K, finishNext) > 0
if (isStartBeforeAnswer != isFinishBeforeAnswer) startAfter = startCurrent
'''pfor''' i = 0..sqrt(n):
'''int''' start = i + startAfter
'''int''' middle = i + startAfter + 1
'''int''' finish = i + startAfter + 2
if (left_turn(start, K, middle) != left_turn(middle, K, finish)) return middle

Его <tex>work = \sqrt{n}</tex>, <tex>span = \log{n}</tex>

2) Создадим функцию, которая находит касательную $AB$ между двумя многоугольниками (она будет сильно похожа на предыдущую функцию)

{{Теорема
|about=
|statement=Если предыдущая точка $prev$ и следующая точка $next$ лежат по одну сторону (в нашем случае ниже) от касательной на второй многоугольник, то эта точка $x$ является точкой искомой касательной. Иначе - если $prev$ находится выше касательной, то мы дальше $A$, иначе - до $A$.
|proof=

Многоугольник выпуклый, значит, что если одна точка лежит на прямой, а две соседние по одну сторону от нее, значит, что эта прямая является касательной.

Если $prev$ находится выше касательной, то это значит, что его касательная находится выше, значит, что AB тоже находится выше, а значит, что A находится раньше. Аналогично для обратного случая.
}}

Здесь у нас совершенно тот же код, просто мы вместо предиката левый поворот смотрим, где будет находиться предыдущая точка и следующая.

<tex>work = \sqrt{n}</tex>, <tex>span = \log{n}</tex>

Итоговое время работы: <tex>work = n</tex>, <tex>span = \log{n}</tex>

Параллельный алгоритм нахождения выпуклой оболочки

2021-11-29T13:01:35Z

77.234.203.142: /* Параллельный алгоритм */

{{Задача
|definition = Пусть нам даны точки на плоскости. Нужно найти выпуклую оболочку на этих точках.
}}

{{Определение|definition='''Выпуклая оболочка''' {{---}} минимальная последовательность точек такая, что последовательное соединение этих точек дает выпуклый многоугольник, и в этом многоугольнике содержатся все точки.}}

==Последовательный алгоритм==

[[Файл:Parallel-convexhull-not-parallel-1.png|300px|thumb|right|Как мы будем двигаться]]

Давайте первым делом найдем самую левую A (при нескольких таких выбрать нижнюю) и самую правую B (при нескольких таких выбрать самую верхнюю) точку на плоскости.

Мы определенно знаем, что через них будет идти выпуклая оболочка, так как если она не будет идти через них, то это значит, что есть какой то отрезок между точками, который ниже и правее A, но это не так. Аналогично для правой верхней точки. Теперь будем строить от A до B верхнюю выпуклую оболочку для всех точек выше AB, и от B до A нижнюю выпуклую оболочку для всех точек ниже AB.

Теперь рассмотрим верхнюю половину. Нижняя будет выполняться аналогично. Берем середину из самое левой точки и правой точки по координате x и делим наше множество точек на две части каким то образом. Теперь нам нужно сделать объединение двух выпуклых оболочек за <tex>O(n)</tex>, для того, что бы итоговая асимптотика была <tex>O(n\log(n))</tex>

Прежде чем решать эту задачу, давайте решим такую задачу:

{{Задача
|definition = Нам дан выпуклый многоугольник, который был разрезан отрезком X, и взята верхняя часть. Так же дана точка, находящаяся выше X. Нужно провести касательную из точки к многоугольнику.
}}

[[Файл:Parallel-convex-hull-tangent.png|300px|thumb|right|Касательные]]

Мысленно представим соединение всех точек многоугольника с данной нам точкой. Заметим, что если мы воспользуемся [[Предикат_"левый_поворот"|предикатом "левый поворот"]], то сможем понять, находится ли точка, являющаяся касательной правее или левее, просто взяв предикат по точке куда ведем пересечение, данной точкой и следующей за точкой пересечения точкой. Проще говоря, нам нужно понять, "выше" ли находится прямая со следующей точкой или нет. Если оказалось, что она выше, то касательная находится выше. Если ниже, то касательная находится ниже.

Таким образом, мы можем за <tex>O(1)</tex> понимать для точки, дальше ли ее точка касательной или она была раньше. То есть у нас есть унимодальная функция, и нам нужно найти переход от <tex>0</tex> до <tex>1</tex>. Похоже на задачу бинарного поиска. Давайте опишем шаги:

'''int''' l = 0, r = n - 2
'''while''' 1 < r - l:
m = (l + r) / 2
'''if''' left_turn(a[m], K, a[m + 1]) > 0:
l = m
else:
r = m

Нахождение касательной из точки на многоугольник работает за <tex>O(\log(n))</tex>

{{Задача
|definition = Нам дано два выпуклых многоугольника A и B, которые были разрезаны отрезком X, и взята верхняя часть. Нужно провести такую касательную через 2 точки многоугольника, что все точки находятся либо на касательной либо ниже.
}}

[[Файл:Parallel-convex-hull-tangent-tangent.png|300px|thumb|right|Касательные из каждой точки]]

Давайте мысленно проведем касательные из каждой точки A на многоугольник B. Только одна из них является истинной. Здесь будет работать примерно такая же стратегия, что и в прошлом. Если мы понимаем с помощью предиката левого поворота, что касательная выше, то правильная точка находится до нашей, иначе дальше нашей. Снова сделаем бинпоиск. Только на сей раз проверка на то, что точка находится левее/правее нужной будет требовать от нас <tex>O(log(n))</tex>. Таким образом, алгоритм нахождения общей касательной будет работать за <tex>O(log^2(n))</tex>.

Теперь мы можем соединять две выпуклые оболочки в одну просто проводя касательную между ними и выпиливая у первого многоугольника все, что дальше точки касания, а у второго многоугольника все, что находится до точки касания за <tex>O(n)</tex>. Задача решена.

==Параллельный алгоритм==

[[Файл:Parallel-convex-hull-sqrt.png|300px|thumb|right|Касательные]]

Теперь нам нужно это как то ускорить. Давайте посмотрим, что же мы можем делать параллельно, и при этом не ухудшим асимптотику. Конечно же, у нас был поиск касательной за <tex>O(log^2(n))</tex>, а можно сделать его за <tex>work = O(n)</tex>, при этом уменьшив span

Посмотрим на каждую фазу бинпоиска. Заметим, что мы можем просто не брать бинпоиск, а разделить массив рассмотрения на <tex>\sqrt{n}</tex> частей.

Для каждого элемента посмотрим его результат (поймем, выше ли реальная касательная), и, если оказалось, что у нас и у точки, которая находится на <tex>\sqrt{n}</tex> различные результаты, то мы поймем, что правильный результат находится между нами. То есть мы возьмем все точки, которые находятся между нами, если у нас с соседом разные результаты и снова у каждой точки посмотрим, где находится верный результат. В этот раз мы уже точно узнаем результат, ведь теперь недостающих точек нет. То есть алгоритм будет такой:

1) Берем <tex>\sqrt{n}</tex>, <tex>2\sqrt{n}</tex>, <tex>3\sqrt{n}</tex>, ..., <tex>\sqrt{n}\sqrt{n}</tex> и параллельно проверяем, подходят ли они под условие. Каждая из них возвращает <tex>0</tex> или <tex>1</tex> - левее или правее они результата. Каждый результат считает за себя <tex>k\sqrt{n}</tex> и за соседа <tex>(k + 1)\sqrt{n}</tex>.
2) Если оказалось, что результаты разные, то мы берем <tex>k\sqrt{n}</tex>, <tex>k\sqrt{n} + 1</tex>, <tex>k\sqrt{n} + 2</tex>, ..., <tex>(k + 1)\sqrt{n}</tex>, и смотрим параллельно подходят ли они под условия. Каждое их них возвращает 0 или 1 - левее или правее находится результат. В точке, где меняет 0 и 1 и есть верный ответ.

Таким образом, у нас выходит примерно такой алгоритм -

1) Создаем функцию, которая находит касательную для точки из первого многоугольника на второй многоугольник.

fun getFromPoint(K):
'''int''' startAfter
'''pfor''' i = 0...sqrt(n):
'''int''' startCurrent = sqrt(n) * i
'''int''' startNext = sqrt(n) * i + 1
'''int''' finishCurrent = sqrt(n) * i
'''int''' finishNext = sqrt(n) * i + 1
'''boolean''' isStartBeforeAnswer = left_turn(startCurrent, K, startNext) > 0
'''boolean''' isFinishBeforeAnswer = left_turn(finishCurrent, K, finishNext) > 0
if (isStartBeforeAnswer != isFinishBeforeAnswer) startAfter = startCurrent
'''pfor''' i = 0..sqrt(n):
'''int''' start = i + startAfter
'''int''' middle = i + startAfter + 1
'''int''' finish = i + startAfter + 2
if (left_turn(start, K, middle) != left_turn(middle, K, finish)) return middle

Его <tex>work = \sqrt{n}</tex>, <tex>span = \log{n}</tex>

2) Создадим функцию, которая находит касательную $AB$ между двумя многоугольниками (она будет сильно похожа на предыдущую функцию)

{{Теорема
|about=
|statement=Если предыдущая точка $prev$ и следующая точка $next$ лежат по одну сторону (в нашем случае ниже) от касательной на второй многоугольник, то эта точка $x$ является точкой искомой касательной. Иначе - если $prev$ находится выше касательной, то мы дальше $A$, иначе - до $A$.
|proof=

Многоугольник выпуклый, значит, что если одна точка лежит на прямой, а две соседние по одну сторону от нее, значит, что эта прямая является касательной.

Если $prev$ находится выше касательной, то это значит, что его касательная находится выше, значит, что AB тоже находится выше, а значит, что A находится раньше. Аналогично для обратного случая.
}}

Здесь у нас совершенно тот же код, просто мы вместо предиката левый поворот смотрим, где будет находиться предыдущая точка и следующая.

<tex>work = \sqrt{n}</tex>, <tex>span = \log{n}</tex>

Итоговое время работы: <tex>work = n</tex>, <tex>span = \log{n}</tex>

Параллельный алгоритм нахождения выпуклой оболочки

2021-11-29T12:32:01Z

77.234.203.142:

{{Задача
|definition = Пусть нам даны точки на плоскости. Нужно найти выпуклую оболочку на этих точках.
}}

{{Определение|definition='''Выпуклая оболочка''' {{---}} минимальная последовательность точек такая, что последовательное соединение этих точек дает выпуклый многоугольник, и в этом многоугольнике содержатся все точки.}}

==Последовательный алгоритм==

[[Файл:Parallel-convexhull-not-parallel-1.png|300px|thumb|right|Как мы будем двигаться]]

Давайте первым делом найдем самую левую A (при нескольких таких выбрать нижнюю) и самую правую B (при нескольких таких выбрать самую верхнюю) точку на плоскости.

Мы определенно знаем, что через них будет идти выпуклая оболочка, так как если она не будет идти через них, то это значит, что есть какой то отрезок между точками, который ниже и правее A, но это не так. Аналогично для правой верхней точки. Теперь будем строить от A до B верхнюю выпуклую оболочку для всех точек выше AB, и от B до A нижнюю выпуклую оболочку для всех точек ниже AB.

Теперь рассмотрим верхнюю половину. Нижняя будет выполняться аналогично. Берем середину из самое левой точки и правой точки по координате x и делим наше множество точек на две части каким то образом. Теперь нам нужно сделать объединение двух выпуклых оболочек за <tex>O(n)</tex>, для того, что бы итоговая асимптотика была <tex>O(n\log(n))</tex>

Прежде чем решать эту задачу, давайте решим такую задачу:

{{Задача
|definition = Нам дан выпуклый многоугольник, который был разрезан отрезком X, и взята верхняя часть. Так же дана точка, находящаяся выше X. Нужно провести касательную из точки к многоугольнику.
}}

[[Файл:Parallel-convex-hull-tangent.png|300px|thumb|right|Касательные]]

Мысленно представим соединение всех точек многоугольника с данной нам точкой. Заметим, что если мы воспользуемся [[Предикат_"левый_поворот"|предикатом "левый поворот"]], то сможем понять, находится ли точка, являющаяся касательной правее или левее, просто взяв предикат по точке куда ведем пересечение, данной точкой и следующей за точкой пересечения точкой. Проще говоря, нам нужно понять, "выше" ли находится прямая со следующей точкой или нет. Если оказалось, что она выше, то касательная находится выше. Если ниже, то касательная находится ниже.

Таким образом, мы можем за <tex>O(1)</tex> понимать для точки, дальше ли ее точка касательной или она была раньше. То есть у нас есть унимодальная функция, и нам нужно найти переход от <tex>0</tex> до <tex>1</tex>. Похоже на задачу бинарного поиска. Давайте опишем шаги:

'''int''' l = 0, r = n - 2
'''while''' 1 < r - l:
m = (l + r) / 2
'''if''' left_turn(a[m], K, a[m + 1]) > 0:
l = m
else:
r = m

Нахождение касательной из точки на многоугольник работает за <tex>O(\log(n))</tex>

{{Задача
|definition = Нам дано два выпуклых многоугольника A и B, которые были разрезаны отрезком X, и взята верхняя часть. Нужно провести такую касательную через 2 точки многоугольника, что все точки находятся либо на касательной либо ниже.
}}

[[Файл:Parallel-convex-hull-tangent-tangent.png|300px|thumb|right|Касательные из каждой точки]]

Давайте мысленно проведем касательные из каждой точки A на многоугольник B. Только одна из них является истинной. Здесь будет работать примерно такая же стратегия, что и в прошлом. Если мы понимаем с помощью предиката левого поворота, что касательная выше, то правильная точка находится до нашей, иначе дальше нашей. Снова сделаем бинпоиск. Только на сей раз проверка на то, что точка находится левее/правее нужной будет требовать от нас <tex>O(log(n))</tex>. Таким образом, алгоритм нахождения общей касательной будет работать за <tex>O(log^2(n))</tex>.

Теперь мы можем соединять две выпуклые оболочки в одну просто проводя касательную между ними и выпиливая у первого многоугольника все, что дальше точки касания, а у второго многоугольника все, что находится до точки касания за <tex>O(n)</tex>. Задача решена.

==Параллельный алгоритм==

[[Файл:Parallel-convex-hull-sqrt.png|300px|thumb|right|Касательные]]

Теперь нам нужно это как то ускорить. Давайте посмотрим, что же мы можем делать параллельно, и при этом не ухудшим асимптотику. Конечно же, у нас был поиск касательной за <tex>O(log^2(n))</tex>, а можно сделать его за <tex>work = O(n)</tex>, при этом уменьшив span

Посмотрим на каждую фазу бинпоиска. Заметим, что мы можем просто не брать бинпоиск, а разделить массив рассмотрения на <tex>\sqrt(n)</tex> частей.

Для каждого элемента посмотрим его результат (поймем, выше ли реальная касательная), и, если оказалось, что у нас и у точки, которая находится на <tex>\sqrt(n)</tex> различные результаты, то мы поймем, что правильный результат находится между нами. То есть мы возьмем все точки, которые находятся между нами, если у нас с соседом разные результаты и снова у каждой точки посмотрим, где находится верный результат. В этот раз мы уже точно узнаем результат, ведь теперь недостающих точек нет. То есть алгоритм будет такой:

1) Берем <tex>\sqrt{n}</tex>, <tex>2\sqrt{n}</tex>, <tex>3\sqrt{n}</tex>, ..., <tex>\sqrt{n}\sqrt{n}</tex> и параллельно проверяем, подходят ли они под условие. Каждая из них возвращает <tex>0</tex> или <tex>1</tex> - левее или правее они результата. Каждый результат считает за себя <tex>k\sqrt{n}</tex> и за соседа <tex>(k + 1)\sqrt{n}</tex>.
2) Если оказалось, что результаты разные, то мы берем <tex>k\sqrt{n}</tex>, <tex>k\sqrt{n} + 1</tex>, <tex>k\sqrt{n} + 2</tex>, ..., <tex>(k + 1)\sqrt{n}</tex>, и смотрим параллельно подходят ли они под условия. Каждое их них возвращает 0 или 1 - левее или правее находится результат. В точке, где меняет 0 и 1 и есть верный ответ.

Таким образом, у нас выходит примерно такой алгоритм -

1) Создаем функцию, которая находит касательную для точки из первого многоугольника на второй многоугольник.

fun get(K):
'''int''' startAfter
'''pfor''' i = 0...sqrt(n):
'''int''' startCurrent = sqrt(n) * i
'''int''' startNext = sqrt(n) * i + 1
'''int''' finishCurrent = sqrt(n) * i
'''int''' finishNext = sqrt(n) * i + 1
'''boolean''' isStartBeforeAnswer = left_turn(startCurrent, K, startNext) > 0
'''boolean''' isFinishBeforeAnswer = left_turn(finishCurrent, K, finishNext) > 0
if (isStartBeforeAnswer != isFinishBeforeAnswer) startAfter = startCurrent
'''pfor''' i = 0..sqrt(n):
'''int''' start = i + startAfter
'''int''' middle = i + startAfter + 1
'''int''' finish = i + startAfter + 2
if (left_turn(start, K, middle) != left_turn(middle, K, finish)) return middle

мы запускаем pfor по <tex>\sqrt{n}</tex> точек равных <tex>i \cdot \sqrt{n}</tex>

Энтропия случайного источника

2020-10-31T11:18:50Z

77.234.203.142: /* Свойства */ Сделал скобочки побольше

__TOC__
== Определение ==

{{Определение
|definition = '''Энтропия случайного источника''' (англ. ''Shannon entropy'') {{---}} функция от вероятностей исходов: <tex>H: \bigcup\limits_{i=1}^{\infty} \mathbb{R}^i \rightarrow \mathbb{R} </tex>, характеризующая количество информации, приходящейся на одно сообщение источника.
}}

== Свойства ==

'''Энтропия должна удовлетворять следующим требованиям:'''

* Функция <tex>H(p_1, p_2, \dots, p_n)</tex> определена и непрерывна для всех таких наборов <tex>p_i\in[0,\;1]</tex>, что <tex> \sum\limits_{i = 1}^{n} p_i = 1</tex>

* <tex dpi ="130">H \underbrace{ \left( \dfrac{1}{n}, \dfrac{1}{n}, \dots, \dfrac{1}{n} \right)}_\text{n} < H \underbrace{ \left( \dfrac{1}{n+1}, \dfrac{1}{n+1}, \dots, \dfrac{1}{n+1} \right) }_\text{n+1}</tex>

* <tex dpi ="130"> H(p_{1}q_{11}, p_{1}q_{12}, \dots, p_{n}q_{nk_n}) = H(p_1, p_2, \dots, p_n) + \sum\limits_{i=1}^{n} p_iH(q_{i1}, \dots, q_{ik_i})</tex>
<tex>\rhd</tex>

Рассмотрим схему <tex>\mathcal{P}_m</tex> c <tex>m</tex> исходами и вероятностями <tex>\{p_1, p_2, \dots, p_m\}</tex> и схему <tex>\mathcal{R}_k</tex> с <tex>k</tex> исходами и вероятностями <tex>\{q_1, q_2, \dots, q_k\}</tex>.

Образуем комбинированную схему c <tex>m + k - 1</tex> исходами следующим образом:

Выбирается случайным образом один из исходов схемы <tex>\mathcal{P}_m</tex>, и если произошел <tex>m</tex>-й исход, выбирается случайно один из исходов схемы <tex>\mathcal{R}_k</tex>, а остальные <tex>m - 1</tex> исходов схемы <tex>\mathcal{P}_m</tex> считаются окончательными.

В этой комбинированной схеме <tex>\mathcal{PR}</tex> мы получаем исходы <tex>1, 2, \dots, m - 1, (m, 1), (m, 2), \dots, (m, k)</tex> с вероятностями <tex>p_1, p_2, \dots, p_{m-1}, p_mq_1, p_mq_2, \dots, p_mq_k</tex>

Легко видеть, что <tex>H(\mathcal{PR}) = H(\mathcal{P}_m) + p_mH(\mathcal{R}_k)</tex>.

Потребуем выполнения этого свойства для любой меры неопределенности.
<tex>\lhd</tex>

==Вычисление энтропии==

Для доказательства формулы вычисления энтропии сначала докажем лемму.
{{Лемма
|statement = <tex dpi="140">g(n) = H(\dfrac{1}{n}, \dfrac{1}{n}, \dots, \dfrac{1}{n}) = -k \log_2 \dfrac{1}{n} = k \log_2n</tex>
|proof =
Будем рассматривать для <tex>k=1</tex> (бит).

Рассмотрим функцию <tex>g(mn)</tex>:
: <tex>g(mn)=g(m)+ \sum\limits_{i=1}^{m} \dfrac{1}{m} g(n) = g(m)+g(n)</tex>

Пусть: <tex>g(2)=1 \quad</tex>, тогда <tex>g(2^t)=t</tex> и <tex> \quad g(n^t)=t \cdot g(n)</tex>

Рассмотрим такое <tex> i </tex>, что <tex>2^i \leqslant n^t < 2^{i+1}</tex>

Можно заметить, что если <tex> i=[ \log_2 n^t ] </tex>, то неравенство останется верным.

По предыдущим рассуждениям получаем, что:
:<tex>g(2^i) \leqslant g(n^t) < g(2^{i+1})</tex>

: <tex> i \leqslant t \cdot g(n) <i+1 \quad \quad </tex>

Делим неравенство на <tex>t</tex>:
: <tex dpi="140">\dfrac{i}{t} \leqslant g(n) < \dfrac{i+1}{t}</tex>, то есть <tex dpi="140">\dfrac{[ \log_2 n^t ]}{t} \leqslant g(n) < \dfrac{[ \log_2 n^t ]+1}{t}</tex>

Отсюда ясно, что если <tex> t\rightarrow \infty</tex>, то получаем <tex>g(n) = \log_2n</tex>
}}

{{Теорема
|statement= <tex dpi="140">H(p_1, p_2, \dots, p_n) = -k \sum\limits_{i=1}^{n} p_i\log_2p_i = k \sum\limits_{i=1}^{n} p_i\log_2\dfrac{1}{p_i}</tex>
|proof =

Теперь рассмотрим функцию <tex dpi="140">H(\dfrac{a_1}{b_1}, \dfrac{a_2}{b_2}, \dots, \dfrac{a_n}{b_n})</tex>

Приведем дроби внутри функции к одному знаменателю, получаем: <tex dpi="140"> H(\dfrac{a_1}{b_1}, \dfrac{a_2}{b_2}, \dots, \dfrac{a_n}{b_n}) = H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b})</tex>

Далее по свойству энтропии и доказанной лемме:
: <tex dpi="140">g(b)= H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b}) + \sum\limits_{i=1}^{n} \dfrac{x_i}{b} g(x_i)</tex>

: <tex dpi="140">H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b}) = \log_2b - \sum\limits_{i=1}^{n} \dfrac{x_i}{b} \log_2x_i = -\sum\limits_{i=1}^{n} \dfrac{x_i}{b} \log_2 \dfrac{x_i}{b}</tex>
При <tex dpi="140"> p_i = \dfrac{x_i}{b} </tex> получаем, что <tex dpi="140">H(p_1, p_2, \dots, p_n) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = \sum\limits_{i=1}^{n} p_i \log_2 \dfrac{1}{p_i}</tex>
}}

== Примеры ==
=== Энтропия честной монеты ===
Рассмотрим [[Вероятностное пространство, элементарный исход, событие|вероятностное пространство]] {{---}} честная монета.
Найдем для нее энтропию:
:<tex dpi="140">H(X) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = -\sum\limits_{i=1}^{2} {\dfrac{1}{2} \cdot \log_2 \dfrac{1}{2}} = -\sum\limits_{i=1}^{2} {\dfrac{1}{2} \cdot (-1)} = 1</tex>
Это означает что после броска честной монеты мы получим информацию в размере <tex>1</tex> бит, уменьшив степень неопределенности вдвое.

=== Энтропия нечестной монеты ===
Найдем энтропию для [[Вероятностное пространство, элементарный исход, событие|вероятностного пространства]] нечестная монета с [[Схема Бернулли| распределением Бернулли]] <tex>\{0,2; 0,8\}</tex>:
:<tex dpi="140">H(X) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = -0.2\log_2(0.2)-0.8\log_2(0.8) \approx 0.722 < 1 </tex>

== Ограниченность энтропии ==
{{Теорема
|statement= <tex>0 \leqslant H(p_1, p_2, \dots, p_n) \leqslant \log_2n </tex>
|proof =
1) Докажем первую часть неравенства:

Так как <tex> p_i\in[0,\;1]</tex>, тогда <tex dpi="140">\log_2\dfrac{1}{p_i} \geqslant 0 </tex>. Таким образом <tex dpi="140"> H(p_1, p_2, \dots, p_n) = \sum\limits_{i=1}^{n} p_i\log_2 \dfrac{1}{p_i} \geqslant 0 </tex>

2) Докажем вторую часть неравенства:

<tex dpi="140"> f(x)=\log_2x </tex> {{---}} выпуклая вверх функция, <tex> p_1,p_2,\ldots,p_n>0</tex> и <tex> \sum \limits_{i=1}^{n} p_i = 1 </tex>, тогда для нее выполняется неравенство Йенсена:
<tex dpi="140"> \sum\limits_{i=1}^{n} p_i f(\dfrac{1}{p_i}) \leqslant f(\sum\limits_{i=1}^{n} (p_i \cdot\dfrac{1}{p_i})) </tex>
Таким образом получаем, что <tex> H(p_1, p_2, \dots, p_n) \leqslant \log_2n </tex>
}}
Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны.
== Условная и взаимная энтропия ==
{{Определение
|definition = '''Условная энтропия''' (англ. ''conditional entropy'') {{---}} определяет количество остающейся энтропии (то есть, остающейся неопределенности) события <tex>A</tex> после того, как становится известным результат события <tex>B</tex>. Она называется ''энтропия <tex>A</tex> при условии <tex>B</tex>'', и обозначается <tex>H(A|B)</tex>
}}
<tex>H(A|B)= - \sum\limits_{i=1}^{m}p(b_i)\sum\limits_{j=1}^{n} p(a_j|b_i)\log_2p(a_j|b_i) </tex>
{{Определение
|definition = '''Взаимная энтропия''' (англ. ''joint entropy'') {{---}} энтропия объединения двух событий <tex>A</tex> и <tex>B</tex>.
}}
<tex> H(A \cap B) = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(a_j \cap b_i) </tex>
{{Утверждение
|statement= <tex> H(A \cap B) = H(A|B)+H(B)=H(B|A)+H(A) </tex>
|proof= По формуле условной вероятности <tex dpi="130"> p(a_j|b_i)=\dfrac{p(a_j \cap b_i)}{p(b_i)} </tex>

<tex dpi="140"> H(A|B)=-\sum\limits_{i=1}^{m}p(b_i)\sum\limits_{j=1}^{n} p(a_j|b_i)\log_2p(a_j|b_i) </tex> <tex dpi="140">= - \sum\limits_{i=1}^{m}p(b_i) \sum\limits_{j=1}^{n} \dfrac{p(a_j \cap b_i)}{p(b_i)}\log_2 \dfrac {p(a_j \cap b_i)}{p(b_i)} = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2 \dfrac {p(a_j \cap b_i)}{p(b_i)} = </tex>
<tex dpi="140"> = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(a_j \cap b_i) + \sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(b_i) </tex><tex dpi="140">= H(A \cap B) +\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(b_i) = </tex>

<tex dpi="140"> = H(A \cap B) +\sum\limits_{i=1}^{m} \log_2p(b_i)\sum\limits_{j=1}^{n} p(a_j \cap b_i) = H(A \cap B) +\sum\limits_{i=1}^{m} \log_2p(b_i)p(b_i) = </tex><tex dpi="140">H(A \cap B) - H(B) </tex>

Таким образом получаем, что: <tex> H(A \cap B)= H(A|B)+H(B) </tex>

Аналогично: <tex>H(B \cap A)= H(B|A)+H(A) </tex>

Из двух полученных равенств следует, что <tex> H(A|B)+H(B)=H(B|A)+H(A) </tex>
}}

== См. также ==
*[[Вероятностное пространство, элементарный исход, событие|Вероятностное пространство, элементарный исход, событие]]
*[[Условная вероятность|Условная вероятность]]

== Источники информации ==
* И.В. Романовский "Дискретный анализ"
* [http://ru.wikipedia.org/wiki/Информационная_энтропия Википедия {{---}} Информационная энтропия]
* [https://en.wikipedia.org/wiki/Entropy_(information_theory) Wkipedia {{---}} Entropy(information_theory)]
[[Категория:Дискретная математика и алгоритмы]]

[[Категория: Теория вероятности ]]

Участник:Gaporf

2020-09-20T19:09:42Z

77.234.203.142:

Николай Акимов, группа M33381

Алгоритм Карккайнена-Сандерса

2020-03-21T11:04:36Z

77.234.203.142: Лишняя буква c в примере

'''Алгоритм Карккайнена-Сандерса''' (Kärkkäinen, Sanders) — алгоритм построения [[суффиксный массив | суффиксного массива]] за линейное время.

__TOC__

== Используемые обозначения ==
* В данном конспекте используется 0-индексация.
* <tex>S[i..j] </tex> — подстрока строки <tex> S </tex> с <tex>i</tex>-го по <tex>j</tex>-й символы включительно.
* Пусть длина строки <tex> S </tex> равна <tex> n </tex>. Обозначим <tex> S^*[i..j] </tex>, где <tex> j \geqslant n </tex> как строку <tex> S[i..n-1] </tex>, дополненную защитными символами <tex> \$ </tex> до длины <tex> n </tex>.

== Алгоритм «разделяй и властвуй» ==

{{Определение
|definition=
'''Четным суффиксом''' назовем суффикс, начинающийся в четной позиции. <br>
'''Нечетным суффиксом''' — суффикс, начинающийся в нечетной позиции.
}}

# Строим суффиксный массив для нечетных суффиксов, рекурсивно сведя задачу к построению суффиксного массива для строки половинной длины.
# Строим суффиксный массив для четных суффиксов за линейное время, используя результат первого шага.
# Сливаем суффиксные массивы за линейное время.

Получили асимптотическое уравнение <tex> T(n) = T\left( \dfrac{n}{2}\right) + O(n) </tex>, решением которого является <tex> T(n) = O(n) </tex>.

Для упрощения алгоритма вначале дополним нашу строку до четной длины (например, добавлением <tex>\$</tex> в конец). На шаге слияния мы сможем избавиться от него.

=====База рекурсии=====
Если длина текущей строки <tex> S </tex> равна двум, надо выполнить обычное сравнение суффиксов.

=====Суффиксный массив для нечетных суффиксов=====

# Отобразим исходную строку <tex> S^* </tex> длины <tex> n </tex> в строку <tex> S' </tex> длины <tex> \dfrac{n}{2} </tex> следующим образом:
#* Сделаем список, состоящий из пар символов вида <tex> S^*[i..i + 1] </tex>, где <tex> i \bmod 2 = 1 </tex>.
#* Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит <tex> \Sigma' </tex>.
#* Перекодируем строку <tex> S^*[1..n] </tex> в алфавит <tex> \Sigma' </tex>, получив строку <tex> S' </tex> половинной длины.
# Рекурсивно построим суффиксный массив <tex> A_{S'} </tex>.
# Построим суффиксный массив <tex> A_{S_o} </tex>. Очевидно, <tex> A_{S_o}[i] = 2 A_{S'}[i] + 1 </tex>, так отношение упорядоченности любых двух строк в старом алфавите <tex> \Sigma </tex> эквивалентно отношению упорядоченности в новом алфавите <tex> \Sigma' </tex> по его построению.

=====Суффиксный массив для четных суффиксов=====
На этом шаге мы за линейное время получим суффиксный массив <tex> A_{S_e} </tex> для четных суффиксов, используя уже построенный <tex> A_{S_o} </tex>.

Заметим, что сортировка множества четных суффиксов <tex> \{ S^*[i..n] \mid i \bmod 2 = 0 \} </tex> аналогична сортировке множества пар <tex> \{ (S^*[i], S^*[i+1..n]) \mid i \bmod 2 = 0 \} </tex>. Однако <tex> S^*[i+1..n] </tex> — нечетный суффикс, и его относительную позицию мы уже узнали на шаге 1.

Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив <tex> A_{S_o} </tex>), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. После этого легко можно восстановить массив <tex> A_{S_e} </tex>:
M = []
'''for''' i = 0 '''to''' n / 2 - 1
M.add(Pair(S[<tex> A_{S_o}</tex>[i] - 1], <tex> A_{S_o}</tex>[i]))
quick_stable_sort(M)
<tex> A_{S_e} </tex> = []
'''for''' i = 0 '''to''' n/2 - 1:
<tex> A_{S_e} </tex>.add(M[i].second - 1)

Заметим, что массив <tex> M </tex> перед сортировкой подсчетом не был явно отсортирован по вторым элементам, и хранил не суффиксы, а их позиции в строке <tex> S </tex>, но важно, что он был отсортирован по возрастанию соответствующих этим позициям нечетных суффиксов.

Получили, что весь второй шаг требует <tex> O(n) </tex> времени.

=====Слияние суффиксных массивов=====
Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам<ref>M. Farach. Optimal suffix tree construction with large alphabets. http://www.cs.rutgers.edu/~farach/pubs/FarFerrMuthu00.pdf </ref> .
В случае [[Суффиксный массив|суффиксного массива]] слияние становится очень сложным, но все же оно было реализовано в алгоритме Ким-Сим-Парк-Парка<ref> D. K. Kim, J. S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays. http://www.springerlink.com/content/568156021q45r320/</ref>. Однако простой модификацией алгоритма можно значительно упростить его.

=== Пример ===
Покажем первые два шага агоритма для строки '''ababbbaa'''.

Во-первых, добавив защитный символ '''$''', получив строку '''ababbbaa$''' (для этого алгоритма он не требуется, но может понадобиться в применениях суффиксного массива). Во-вторых, дополним ее до четной длины, получив '''ababbbaa$$'''.

=====Суффиксный массив для нечетных суффиксов=====
# В новом алфавите <tex> \Sigma' </tex> будет четыре элемента — '''ba''', '''bb''', '''a$''', '''$$'''. После сортировки они получат номера 2, 3, 1 и 0 соответственно.
# Переводим строку <tex>S^*[1..n]</tex> = '''babbbaa$$$''' в новый алфавит. Сжатой строкой <tex> S' </tex> будет '''23210'''.
# После рекурсивного вызова получим, что <tex> A_{S'} </tex> = [4, 3, 2, 0, 1], и <tex> A_{S_o} </tex> = [9, 7, 5, 1, 3].

=====Суффиксный массив для четных суффиксов=====
# Обойдя массив <tex> A_{S_o} </tex>, получим <tex> M </tex> = [(<tex>\$</tex>, 9), (<tex>a</tex>, 7), (<tex>b</tex>, 5), (<tex>a</tex>, 1), (<tex>a</tex>, 3)].
# После сортировки подсчетом по первому элементу, получим <tex> M </tex>= [(<tex>\$</tex>, 9), (<tex>a</tex>, 7), (<tex>a</tex>, 1), (<tex>a</tex>, 3), (<tex>b</tex>, 5)].
# Восстановив массив <tex> A_{S_e} </tex>, получаем [8, 6, 0, 2, 4], что действительно является суффиксным массивом для четных суффиксов.

=====Слияние суффиксных массивов=====
Если бы мы умели сливать <tex> A_{S_o} </tex> и <tex> A_{S_e} </tex> за линейное время, получили бы:

{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| №
!style="background-color:#EEE"| Подстрока
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 9 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> \$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 8 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> \$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 7 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> a\$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 6 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> aa\$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 0 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> ababbbaa\$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 2 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> abbbaa\$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 5 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> baa\$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 1 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> babbbaa\$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 4 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> bbaa\$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 3 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> bbbaa\$\$ </tex>
|}

Как и было сказано вначале, избавиться от лишних '''$''' легко, так как суффиксы, им соответствующие, будут первыми в суффиксном массиве (в данном случае достаточно выбросить "9" из суффиксного массива).

== Алгоритм Карккайнена-Сандерса ==
Изменим изначальный алгоритм следующим образом:
# Построим суффиксный массив для суффиксов, соответствующих позициям, не кратным трем. Рекурсивно сведем это к построению суффиксного массива для строки длиной в две трети исходной.
# Построим суффиксный массив для суффиксов, соответствующих кратным трем позициям, используя результат первого шага, за линейное время.
# Сольем эти суффиксные массивы в один за линейное время.

Получили асимптотическое уравнение <tex> T(n) = T\left(\dfrac23 n\right) + O(n) </tex>, решением которого также является <tex> T(n) = O(n) </tex> (это видно из того, что сумма геометрической прогрессии с основанием <tex> \dfrac23 </tex> равна <tex> 3 </tex>).

Аналогично первой версии алгоритма, дополним строку <tex> S </tex> до длины, кратной трем, защитными символами <tex> \$ </tex> и получим <tex>S^*</tex>.

* '''База рекурсии'''
Для этого алгоритма минимальной базой рекурсии будет строка длиной 4, так как она дополняется до длины 6, после чего вновь следует рекурсивный вызов строки длиной 4, и, если бы база была меньше 4, алгоритм вошел бы в бесконечную рекурсию. На этом этапе также можно применить обычную сортировку суффиксов, так как это потребует <tex> O(1) </tex> действий.

* '''Суффиксный массив для позиций не кратных 3'''
На этом шаге строится суффиксный массив <tex> A_{S_{12}} </tex> для множества суффиксов <tex> \{ S^*[i..n-1] \mid i \bmod 3 \ne 0 \} </tex>.
# Получим строку <tex> S' </tex> аналогично предыдущему алгоритму:
#* Сделаем список, состоящий из троек <tex> S^*[i..i+2]</tex> , где <tex> i \bmod 3 \ne 0 </tex>.
#* Отсортируем его за линейное время цифровой сортировкой и получим новый алфавит <tex> \Sigma' </tex>.
#* Перекодируем строку <tex> S^*[1..n]S^*[2..n+1] </tex> в строку <tex> S' </tex> длиной <tex> \dfrac23 n </tex> в алфавите <tex> \Sigma' </tex>. Тогда суффиксу <tex> S^*[i..n-1] </tex> в старом алфавите, где <tex> i \bmod 3 = 1 </tex>, в новом алфавите будет соответствовать строка <tex> S'\left[\dfrac{i-1}{3}..\dfrac{n}{3} - 1\right] </tex>, а если <tex> i\bmod 3 = 2 </tex>, то строка <tex> S'\left[\dfrac{n}{3} + \dfrac{i-2}{3}..\dfrac{2n}{3} - 1\right] </tex>.
# Вызовем алгоритм рекурсивно для строки <tex> S' </tex>, получив суффиксный массив <tex> A_{S'} </tex>.
# Пройдем по массиву <tex> A_{S'} </tex>. Если <tex> A_{S'}[i] < \dfrac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3A_{S'}[i] + 1 </tex> в строке <tex> S </tex>, если же <tex> A_{S'}[i] \geqslant \dfrac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3\left(A_{S'}[i] - \dfrac{n}{3}\right) + 2 </tex> в строке <tex> S^* </tex>. Псевдокод получения <tex> A_{S_{12}} </tex>:
<tex> A_{S_{12}} </tex> = []
'''for''' i = 0 '''to''' <tex>A_{S'}</tex>.length - 1:
'''if''' <tex>A_{S'}</tex>[i] < n/3:
<tex>A_{S_{12}}</tex>.add(3 * <tex>A_{S'}</tex>[i] + 1)
'''else''':
<tex>A_{S_{12}}</tex>.add(3 * (<tex>A_{S'}</tex>[i] - n/3) + 2)

* '''Суффиксный массив для позиций кратных 3'''
Этот шаг также аналогичен первой версии алгоритма. Сортировка множества <tex> \{ S^*[i..n-1] \mid i \bmod 3 = 0 \} </tex> аналогична сортировке пар <tex> \{ (S^*[i], S^*[i+1..n-1]) \mid i \bmod 3 = 0 \} </tex>, где <tex> S^*[i+1..n-1] </tex> — суффиксы в позициях, равных 1 по модулю 3, относительный порядок которых уже известен. Выпишем эти пары в порядке вхождения их в <tex> A_{S_{12}} </tex> и отсортируем по первому элементу устойчивой сортировкой подсчетом, получив суффиксный массив <tex> A_{S_0} </tex>. Псевдокод этого шага:

<tex>A_{S_0}</tex> = []
M = []
'''for''' i = 0 '''to''' 2n/3 - 1:
'''if''' <tex> A_{S_{12}}</tex>[i] % 3 == 1:
M.add(Pair(S*[<tex>A_{S_{12}}</tex>[i] - 1], <tex>A_{S_{12}}</tex>[i]))
stable_sort(M)
'''for''' i = 0 '''to''' n/3 - 1:
<tex>A_{S_0}</tex>.add(M[i].second - 1)
Аналогично, второй шаг требует <tex> O(n) </tex> времени.

* '''Слияние суффиксных массивов'''
На этом шаге мы должны слить суффиксные массивы <tex> A_{S_0} </tex> и <tex> A_{S_{12}} </tex>, чтобы получить суффиксный массив <tex> A_{S} </tex> для всей строки <tex> S </tex>.

Применим стандартный алгоритм слияния двух отсортированных массивов. Заметим, что явно массивы не отсортированы, но соответствующие элементам массива суффиксы — отсортированы.

Пусть на какой-то итерации слияния мы сравниваем суффиксы, соответствующие позициям <tex> i </tex>, равной 1 по модулю 3, и <tex> j </tex> (она всегда будет равна 0 по модулю 3). Это аналогично сравнению пар <tex> (S^*[i], S^*[i+1..n-1]) </tex> и <tex> (S^*[j], S^*[j+1..n-1]) </tex>. Сравнить первые элементы пар мы можем за <tex> O(1) </tex>, а относительный порядок вторых элементов пар нам уже известен, так как они соответствуют позициям, равным 2 и 1 по модулю 3 соответственно.

Аналогично, пусть на какой-то итерации слияния мы сравниваем суффиксы, соответствующие позициям <tex> i </tex>, равной 2 по модулю 3, и <tex> j </tex> (она всегда будет равна 0 по модулю 3). Тогда это аналогично сравнению троек <tex> (S^*[i], S^*[i+1], S^*[i+2..n-1]) </tex> и <tex> (S^*[j], S^*[j+1], S^*[j+2..n-1]) </tex>, что также можно делать за <tex> O(1) </tex>.

Псевдокод этой фазы:

<tex>A_{S}</tex> = []
<font color=green>// Вначале предподсчитаем за O(n) обратную перестановку для суффиксного массива <tex> A_{S_{12}}</tex>, то есть массив rank такой, что <tex> A_{S_{12}}</tex>[rank[i]] = i.
// Тогда мы сможем за O(1) сравнивать суффиксы по их позиции. </font>
rank = inverse(<tex>A_{S_{12}}</tex>)
'''while''' i < 2 * n/3 '''and''' j < n/3:
pos12 = <tex> A_{S_{12}} </tex>[i]
pos0 = <tex> A_{0} </tex>[j]
'''if''' pos12 % 3 == 1:
''' if''' Pair(S*[pos12], rank[pos12 + 1]) < Pair(S*[pos0], rank[pos0 + 1]):
<tex>A_{S}</tex>.add(pos12)
i++
'''else''':
<tex>A_{S}</tex>.add(pos0)
j++
'''else''':
'''if''' Triple(S*[pos12], S*[pos12 + 1], rank[pos12 + 2]) < Triple(S*[pos0], S*[pos0 + 1], rank[pos0 + 2]):
<tex>A_{S}</tex>.add(pos12)
i++
'''else''':
<tex>A_{S}</tex>.add(pos0)
j++
'''while''' i < 2 * n/3:
<tex>A_{S}</tex>.add(<tex> A_{S_{12}} </tex>[i])
i++
'''while''' j < n/3:
<tex>A_{S}</tex>.add(<tex> A_{S_{0}} </tex>[j])
j++

Таким образом, получили простой метод слияния за <tex> O(n) </tex>.

=== Пример ===
Построим суффиксный массив для строки '''abbacab'''. После добавления защитного символа и дополнения до кратной трем длины, получим '''abbacab$$'''.
* '''Суффиксный массив для позиций не кратных 3'''
# Тройками, соответствующими равными 1 по модулю 3 позициям, будут: '''bba''', '''cab''', '''$$$''', соответствующими равным 2 по модулю 3 — '''bac''', '''ab$''', '''$$$'''. Новый алфавит <tex> \Sigma' </tex> будет содержать элементы '''bba''', '''cab''', '''$$$''', '''bac''', '''ab$''', которые после сортировки получат номера 3, 4, 0, 2, 1 соответственно.
# Строкой '''bbacab$$$bacab$$$$''' в новом алфавите <tex> \Sigma' </tex> будет <tex> S' </tex> = 340210.
# После рекурсивного вызова получим <tex> A_{S'} </tex> = [5, 2, 4, 3, 0, 1]. Пересчитав <tex> A_{S_{12}} </tex>, получим [(5 - 3)*3 + 2, 2 * 3 + 1, (4 - 3) * 3 + 2, (3 - 3) * 3 + 2, 0 * 3 + 1, 1 * 3 + 1] = [8, 7, 5, 2, 1, 4].

* '''Суффиксный массив для позиций кратных 3'''
# Обойдя массив <tex> A_{S_{12}} </tex> и выбрав в нем элементы, равные 1 по модулю 3, получим массив пар <tex>M</tex> = [(<tex>b</tex>, 7), (<tex>a</tex>, 1), (<tex>a</tex>, 4)]
# После устойчивой сортировки подсчетом по первому элементу, получим <tex> M </tex> = [('''a''', 1), ('''a''', 4), ('''b''', 7)]
# Восстановив <tex> A_{S_0} </tex>, получаем [0, 3, 6].
* '''Слияние суффиксных массивов'''
Рассмотрим, к примеру, третью итерацию слияния, к этой итерации массив <tex> A_{S} </tex> = [8, 7], <tex> i </tex> = 2, <tex> j </tex> = 0, на ней мы сливаем суффиксы, соответствующие позициям 5 и 0.
# Образуем тройки <tex>(S^*[5], S^*[6], S^*[7..8])</tex> и <tex>(S^*[0], S^*[1], S^*[2..8])</tex>.
# После получения относительного порядка суффиксов, получим тройки ('''a''', '''b''', 1) и ('''a''', '''b''', 3). Первая тройка меньше второй, поэтому добавляем суффикс, соответствующий позиции 5 в массив <tex> A_{S} </tex>.
# В конце итерации получаем <tex> A_{S} </tex> = [8, 7, 5], <tex> i </tex> = 3, <tex> j </tex> = 0.
К концу слияния получим <tex> A_{S} </tex> = [8, 7, 5, 0, 3, 6, 2, 1, 4]. Так как мы добавляли один символ <tex>\$</tex> в начале алгоритма для дополнения строки до длины, кратной трем, выбросим последний суффикс из <tex> A_{S} </tex>, получим в итоге, что <tex> A_{S} </tex> = [7, 5, 0, 3, 6, 2, 1, 4].

{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| №
!style="background-color:#EEE"| Подстрока
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 8 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> \$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 7 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> \$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 5 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> ab\$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 0 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> abbacab\$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 3 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> acab\$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 6 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> b\$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 2 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> bacab\$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 1 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> bbacab\$\$ </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex> 4 </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> cab\$\$ </tex>
|}
Заметим, что № 9 будет выброшен, так как в начале алгоритма был добавлен один <tex> \$ </tex> к строке

{|
| [[Файл:Kark_sanders_stage1.png|325px|thumb| Фаза 1]]
| [[Файл:Kark_sanders_stage2.png|325px|thumb| Фаза 2]]
| [[Файл:Kark_sanders_stage3.png|325px|thumb| Фаза 3]]
|}

== Обобщение алгоритма ==
Массив LCP можно получить за линейное время [[Алгоритм_Касаи_и_др. | алгоритмом Касаи]].

На самом деле, алгоритм можно обобщить<ref name="generalisation"> Juha Kärkkäinen, Peter Sanders and Stefan Burkhardt. Linear work suffix array construction. http://www.cs.helsinki.fi/juha.karkkainen/publications/jacm05-revised.pdf </ref>, взяв на первом шаге, к примеру, суффиксы, позиции которых по модулю 7 дают 3, 5 и 6. Для этого потребуются некоторое усложнение алгоритма, например, сортировка оставшихся суффиксов в нескольких группах на шаге 2 и слияние нескольких групп на шаге 3, но основная идея алгоритма остается той же. Множества, которые можно выбрать, на первом шаге определяются '''разностным покрытием''' (''difference cover'').
{{Определение
|definition=
'''Разностное покрытие''' (англ. ''difference cover'') <tex> D </tex> по модулю <tex>m </tex> — множество чисел от <tex>0</tex> до <tex>m - 1 </tex> таких, что <tex> \forall i \in [0, m-1]: \exists j, k \in D: i \equiv k - j \pmod m </tex>.
}}
Например, <tex> \{1, 2\} </tex> является разностным покрытием по модулю <tex> 3 </tex>, <tex> \{3, 5, 6\} </tex> является разностным покрытием по модулю <tex> 7 </tex>, а <tex> \{1\} </tex> — не является разностным покрытием по модулю <tex> 2 </tex>, поэтому этот алгоритм не применим к нему. Подробнее узнать, как вычислять разностное покрытие для заданного модуля можно также здесь<ref name="generalisation"/>.

== См. также ==
* [[Суффиксный массив]]

== Примечания ==
<references/>

== Источники информации==
* [[Суффиксный массив]]
* [http://www.cs.helsinki.fi/juha.karkkainen/publications/icalp03.pdf Juha Kärkkäinen and Peter Sanders. Simple linear work suffix array construction]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Суффиксный массив]]