Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза — различия между версиями
м |
м (rollbackEdits.php mass rollback) |
||
(не показано 15 промежуточных версий 7 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
− | |||
{{Определение | {{Определение | ||
| definition = | | definition = | ||
− | [[Оптимальный префиксный код]] с сохранением порядка(англ. ''order-preserving code'', ''alphabetic code''). | + | '''[[Оптимальный префиксный код с длиной кодового слова не более L бит|Оптимальный префиксный код]] с сохранением порядка''' (англ. ''order-preserving code'', ''alphabetic code''). |
− | + | ||
− | Пусть у нас есть алфавит <tex> \Sigma </tex>. Каждому символу <tex>c_i </tex> сопоставим его код <tex> p_i </tex>. Кодирование называется оптимальным префиксным с сохранением порядка, если соблюдаются: | + | Пусть у нас есть алфавит <tex> \Sigma </tex>. Каждому символу <tex>c_i </tex> сопоставим его код <tex> p_i </tex>. Кодирование называется оптимальным префиксным с сохранением порядка (алфавитным), если соблюдаются: |
− | # Условие порядка - <tex> \forall i, j : c_i < c_j \iff p_i < p_j </tex>. То есть, если символ <tex>c_i </tex> лексикографически меньше символа <tex> c_j </tex>, его код также будет [[лексикографический порядок | лексикографически]] меньше, и наоборот. | + | # Условие порядка {{---}} <tex> \forall i, j : c_i < c_j \iff p_i < p_j </tex>. То есть, если символ <tex>c_i </tex> лексикографически меньше символа <tex> c_j </tex>, его код также будет [[лексикографический порядок | лексикографически]] меньше, и наоборот. |
− | # Условие оптимальности - <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> - минимально, где <tex> f_i </tex> - частота встречаемости символа <tex> c_i </tex> в тексте, а <tex>|p_i| </tex> - длина его кода. | + | # Условие оптимальности {{---}} <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> {{---}} минимально, где <tex> f_i </tex> {{---}} частота встречаемости символа <tex> c_i </tex> в тексте, а <tex> |p_i| </tex> {{---}} длина его кода. |
}} | }} | ||
+ | __TOC__ | ||
== Алгоритм == | == Алгоритм == | ||
− | + | Решим задачу, используя ДП на подотрезках. Пусть в ячейке <tex> D[i][j] </tex> хранится минимальная стоимость кодового дерева для отрезка алфавита от <tex> i </tex> до <tex> j </tex>. | |
− | Решим задачу, используя ДП на подотрезках. Пусть в ячейке <tex> D[i][j] </tex> хранится минимальная стоимость кодового дерева для отрезка алфавита от i до j. | ||
Тогда пересчет <tex> D[i][j] </tex> будет происходить так: | Тогда пересчет <tex> D[i][j] </tex> будет происходить так: | ||
Строка 20: | Строка 18: | ||
Базой динамики будет <tex> D[i][i] = 0 </tex> | Базой динамики будет <tex> D[i][i] = 0 </tex> | ||
− | Добавочный член <tex>w[i][j] = \sum\limits_{t = i}^{j} f_t </tex> возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на 1, а значит, и длины всех кодов символов <tex> c_i .. c_j </tex> также увеличиваются на 1. | + | Добавочный член <tex>w[i][j] = \sum\limits_{t = i}^{j} f_t </tex> возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на <tex> 1 </tex>, а значит, и длины всех кодов символов <tex> c_i .. c_j </tex> также увеличиваются на <tex> 1 </tex>. |
− | Тогда такое ''наибольшее'' k, на котором достигается этот минимум, называется точкой разреза для отрезка <tex> | + | Тогда такое ''наибольшее'' <tex> k </tex>, на котором достигается этот минимум, называется точкой разреза для отрезка <tex> i..j </tex>. Пусть в ячейке <tex> R[i][j] </tex> хранится точка разреза на отрезке <tex> i..j </tex>. |
− | Если разрез происходит по какому - то определенному индексу <tex> q </tex> , такой разрез обозначим <tex> D_q[i][j] </tex>. | + | Если разрез происходит по какому-то определенному индексу <tex> q </tex> , такой разрез обозначим <tex> D_q[i][j] </tex>. |
+ | |||
+ | Таким образом, получили алгоритм, работающий за <tex> O(n^3) </tex>. Коды каждого символа можно легко получить так же, как в алгоритме Хаффмана {{---}} обходом по построенному дереву. | ||
+ | |||
+ | Если доказать монотонность точки разреза, то можно уменьшить асимптотику алгоритма до <tex> O(n^2) </tex>. | ||
== Монотонность точки разреза == | == Монотонность точки разреза == | ||
Строка 31: | Строка 33: | ||
{{Определение | {{Определение | ||
| definition= | | definition= | ||
− | Функция a удовлетворяет '''неравенству четырехугольника(quadrangle inequation | + | Функция <tex> a </tex> удовлетворяет '''неравенству четырехугольника''' (англ. ''quadrangle inequation''), если |
− | : <tex>\forall i \ | + | : <tex>\forall i \leqslant i' \leqslant j \leqslant j' : a[i][j] + a[i'][j'] \leqslant a[i'][j] + a[i][j']</tex>. |
}} | }} | ||
+ | |||
{{Лемма | {{Лемма | ||
| statement= | | statement= | ||
− | w удовлетворяет неравенству четырехугольника. | + | <tex> w </tex> удовлетворяет неравенству четырехугольника. |
| proof= | | proof= | ||
− | Заметим, что <tex> w[i][j] = w[i][t] + w[t+1][j] </tex>, так как <tex> w[i][j] </tex> - простая арифметическая сумма. Тогда: | + | Заметим, что <tex> w[i][j] = w[i][t] + w[t+1][j] </tex>, так как <tex> w[i][j] </tex> {{---}} простая арифметическая сумма. Тогда: |
− | : <tex> w[i][j] + w[i'][j'] \ | + | : <tex> w[i][j] + w[i'][j'] \leqslant w[i'][j] + w[i][j']</tex> |
− | : <tex> (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \ | + | : <tex> (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \leqslant (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) </tex> |
− | Получили <tex> 0 \ | + | Получили <tex> 0 \leqslant 0 </tex>. |
}} | }} | ||
Строка 48: | Строка 51: | ||
{{Лемма | {{Лемма | ||
| statement= | | statement= | ||
− | Если w удовлетворяет неравенству четырехугольника, то D также удовлетворяет неравенству четырехугольника, то есть: | + | Если <tex> w </tex> удовлетворяет неравенству четырехугольника и монотонна по включению (то есть $w[i'][j] \le w[i][j']$ при $i \leqslant i' \leqslant j \leqslant j'$), то <tex> D </tex> также удовлетворяет неравенству четырехугольника, то есть: |
− | <tex>\forall i \ | + | <tex>\forall i \leqslant i' \leqslant j \leqslant j' : D[i][j] + D[i'][j'] \leqslant D[i'][j] + D[i][j'] </tex>. |
| proof= | | proof= | ||
− | + | При <tex> i = i' </tex> или <tex> j = j' </tex>, очевидно, неравенство выполняется. | |
Рассмотрим два случая: | Рассмотрим два случая: | ||
# <tex> i' = j </tex> | # <tex> i' = j </tex> | ||
#: <tex> i < i' = j < j' </tex>. Тогда неравенство четырехугольника сводится к: | #: <tex> i < i' = j < j' </tex>. Тогда неравенство четырехугольника сводится к: | ||
− | #: <tex> D[i][j] + D[j][j'] \ | + | #: <tex> D[i][j] + D[j][j'] \leqslant D[i][j'] </tex> |
#: Пусть <tex> k = R[i][j'] </tex>. Получили два симметричных случая: | #: Пусть <tex> k = R[i][j'] </tex>. Получили два симметричных случая: | ||
− | ## <tex> k \ | + | ## <tex> k \leqslant j </tex> |
− | ##: <tex> D[i][j] + D[j][j'] \ | + | ##: <tex> D[i][j] + D[j][j'] \leqslant w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{---}} по определению <tex> D[i][j] </tex> |
− | ##: <tex> \ | + | ##: <tex> \leqslant w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{---}} так как <tex> w[i][j'] \geqslant w[i][j] </tex> по монотонности |
− | ##: <tex> \ | + | ##: <tex> \leqslant w[i][j'] + D[i][k-1] + D[k][j'] </tex> {{---}} по индукционному предположению для <tex> D </tex> |
− | ##: <tex> \ | + | ##: <tex> \leqslant D[i][j'] </tex> {{---}} по определению <tex> D[i][j'] </tex> |
− | ## <tex> k \ | + | ## <tex> k \geqslant j </tex> {{---}} аналогичный предыдущему случай. |
# <tex> i' < j </tex> | # <tex> i' < j </tex> | ||
#: <tex> i < i' < j < j' </tex> | #: <tex> i < i' < j < j' </tex> | ||
− | #: Пусть <tex> y = R[i'][j] </tex> и <tex> z = R[i][j'] </tex>. Получили два | + | #: Пусть <tex> y = R[i'][j] </tex> и <tex> z = R[i][j'] </tex>. Получили два симметричных случая: |
− | ## <tex> z \ | + | ## <tex> z \leqslant y </tex> |
− | ##: Получили <tex> z \ | + | ##: Получили <tex> i \leqslant z \leqslant y \leqslant j </tex>. Запишем: |
− | ##: <tex> D[i'][j'] + D[i][j] \ | + | ##: <tex> D[i'][j'] + D[i][j] \leqslant D_y[i'][j'] + D_z[i][j] = w[i'][j'] + D[i'][y-1] + D[y][j'] + w[i][j] + D[i][z-1] + D[z][j] </tex> |
− | ##: <tex> \ | + | ##: <tex> \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] </tex> {{---}} по неравенству четырехугольника для <tex> w </tex> |
− | ##: <tex> \ | + | ##: <tex> \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] </tex> {{---}} по индукционному предположению для <tex> D </tex> |
− | ##: <tex> \ | + | ##: <tex> \leqslant D[i][j'] + D[i'][j] </tex> {{---}} по определению <tex> D </tex> |
− | ## <tex> z \ | + | ## <tex> z \geqslant y </tex> доказывается аналогично. |
− | |||
}} | }} | ||
+ | |||
{{Теорема | {{Теорема | ||
Строка 82: | Строка 85: | ||
Монотонность точки разреза | Монотонность точки разреза | ||
| statement= | | statement= | ||
− | Если w удовлетворяет неравенству четырехугольника, то: | + | Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то: |
− | <tex> \forall i \ | + | <tex> \forall i \leqslant j : R[i][j] \leqslant R[i][j+1] \leqslant R[i+1][j+1] </tex>. |
| proof= | | proof= | ||
− | В случае <tex> i = j </tex> неравенство, очевидно, выполняется. Рассматриваем случай <tex> i < j </tex> и только случай <tex> R[i][j] \ | + | В случае <tex> i = j </tex> неравенство, очевидно, выполняется. Рассматриваем случай <tex> i < j </tex> и только случай <tex> R[i][j] \leqslant R[i][j+1] </tex> (вторая часть доказывается аналогично): |
− | Так как <tex> R[i][j] </tex> - максимальный индекс, в котором достигается минимум, достаточно показать, что: | + | Так как <tex> R[i][j] </tex> {{---}} максимальный индекс, в котором достигается минимум, достаточно показать, что: |
− | : <tex> \forall i < k \ | + | : <tex> \forall i < k \leqslant k' \leqslant j: [D_{k'}[i][j] \leqslant D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \leqslant D_k[i][j+1]] </tex> {{---}} фактически, это означает что если на отрезке <tex> i..j </tex> разрез оптимальнее по <tex> k' </tex>, чем по <tex> k </tex>, то он также будет оптимальнее и на отрезке <tex> i..j+1 </tex>. |
Докажем более сильное неравенство: | Докажем более сильное неравенство: | ||
− | : <tex> \forall i < k \ | + | : <tex> \forall i < k \leqslant k' \leqslant j: D_k[i][j] - D_{k'}[i][j] \leqslant D_k[i][j+1] - D_{k'}[i][j+1] </tex> |
− | : <tex> D_k[i][j] + D_{k'}[i][j+1] \ | + | : <tex> D_k[i][j] + D_{k'}[i][j+1] \leqslant D_k[i][j+1] + D_{k'}[i][j] </tex> |
− | : <tex> (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \ | + | : <tex> (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \leqslant (w[i][j+1] + D[i][k-1] + D[k][j+1]) + (w[i][j] + D[i][k'-1] + D[k'][j]) </tex> {{---}} по определению <tex> D </tex> |
− | : <tex> D[k][j] + D[k'][j+1] \ | + | : <tex> D[k][j] + D[k'][j+1] \leqslant D[k][j+1] + D[k'][j] </tex> {{---}} получили неравенство четырехугольника для <tex> k \leqslant k' \leqslant j \leqslant j+1 </tex>, что является верным из предыдущей леммы. |
}} | }} | ||
+ | |||
+ | == Объяснение квадратичной асимптотики == | ||
+ | Рассмотрим матрицу <tex> R </tex>. Так как отрезки <tex> i..j </tex>, где <tex> i > j </tex> мы не рассматриваем, она будет верхнетреугольной. Вначале она будет заполнена так, что <tex> R[i][i] = i </tex> (так как для отрезка, состоящего из одного элемента, он же и является точкой разреза). Далее, для любого элемента <tex> R[i][j] </tex> его значения лежат между <tex> R[i][j-1] </tex> (левый элемент в матрице) и <tex> R[i+1][j] </tex> (нижний элемент в матрице). Так как мы используем динамику по подотрезкам, то сначала мы рассчитаем <tex> R </tex> для отрезков длины <tex> 2 </tex>, затем <tex> 3 </tex>, и так далее до <tex> n </tex>. Фактически, мы будем обходить диагонали матрицы, количество которых равно <tex> n </tex>. | ||
+ | |||
+ | Рассмотрим элемент <tex> R[i][j] </tex>. Для него выполняется <tex> R[i][j-1] \leqslant R[i][j] \leqslant R[i+1][j] </tex>. Следующий элемент, который мы будем пересчитывать {{---}} <tex> R[i+1][j+1] </tex>. Для него выполняется <tex> R[i+1][j] \leqslant R[i+1][j+1] \leqslant R[i+2][j+1] </tex>. Таким образом, заполняя одну диагональ, алгоритм сделает не более <tex> n </tex> шагов, а так как диагоналей <tex> n </tex>, получили асимптотику <tex> O(n^2) </tex>. | ||
+ | |||
+ | ==Источники информации == | ||
+ | * [http://www.sciencedirect.com/science/article/pii/S0304397596003209 S.V. Nagaraj {{---}} Tutorial: Optimal binary search trees] | ||
+ | * ''Кнут Д.Э.'' {{---}} Искусство программирования, том 3. Сортировка и поиск. — М.: «Вильямс», 2005, стр. 486 - 488 | ||
+ | |||
+ | [[Категория:Дискретная математика и алгоритмы]] | ||
+ | [[Категория:Динамическое программирование]] | ||
+ | [[Категория:Способы оптимизации методов динамического программирования]] |
Текущая версия на 19:12, 4 сентября 2022
Определение: |
Оптимальный префиксный код с сохранением порядка (англ. order-preserving code, alphabetic code).
Пусть у нас есть алфавит . Каждому символу сопоставим его код . Кодирование называется оптимальным префиксным с сохранением порядка (алфавитным), если соблюдаются:
|
Алгоритм
Решим задачу, используя ДП на подотрезках. Пусть в ячейке
хранится минимальная стоимость кодового дерева для отрезка алфавита от до .Тогда пересчет
будет происходить так:
Базой динамики будет
Добавочный член
возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на , а значит, и длины всех кодов символов также увеличиваются на .Тогда такое наибольшее
, на котором достигается этот минимум, называется точкой разреза для отрезка . Пусть в ячейке хранится точка разреза на отрезке .Если разрез происходит по какому-то определенному индексу
, такой разрез обозначим .Таким образом, получили алгоритм, работающий за
. Коды каждого символа можно легко получить так же, как в алгоритме Хаффмана — обходом по построенному дереву.Если доказать монотонность точки разреза, то можно уменьшить асимптотику алгоритма до
.Монотонность точки разреза
Для доказательства этого сперва докажем несколько лемм.
Определение: |
Функция
| удовлетворяет неравенству четырехугольника (англ. quadrangle inequation), если
Лемма: |
удовлетворяет неравенству четырехугольника. |
Доказательство: |
Заметим, что , так как — простая арифметическая сумма. Тогда: |
Лемма: |
Если удовлетворяет неравенству четырехугольника и монотонна по включению (то есть $w[i'][j] \le w[i][j']$ при $i \leqslant i' \leqslant j \leqslant j'$), то также удовлетворяет неравенству четырехугольника, то есть:
. |
Доказательство: |
При или , очевидно, неравенство выполняется.Рассмотрим два случая:
|
Теорема (Монотонность точки разреза): |
Если удовлетворяет неравенству четырехугольника, то:
. |
Доказательство: |
В случае неравенство, очевидно, выполняется. Рассматриваем случай и только случай (вторая часть доказывается аналогично):Так как — максимальный индекс, в котором достигается минимум, достаточно показать, что:
Докажем более сильное неравенство:
|
Объяснение квадратичной асимптотики
Рассмотрим матрицу
. Так как отрезки , где мы не рассматриваем, она будет верхнетреугольной. Вначале она будет заполнена так, что (так как для отрезка, состоящего из одного элемента, он же и является точкой разреза). Далее, для любого элемента его значения лежат между (левый элемент в матрице) и (нижний элемент в матрице). Так как мы используем динамику по подотрезкам, то сначала мы рассчитаем для отрезков длины , затем , и так далее до . Фактически, мы будем обходить диагонали матрицы, количество которых равно .Рассмотрим элемент
. Для него выполняется . Следующий элемент, который мы будем пересчитывать — . Для него выполняется . Таким образом, заполняя одну диагональ, алгоритм сделает не более шагов, а так как диагоналей , получили асимптотику .Источники информации
- S.V. Nagaraj — Tutorial: Optimal binary search trees
- Кнут Д.Э. — Искусство программирования, том 3. Сортировка и поиск. — М.: «Вильямс», 2005, стр. 486 - 488