Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 57: Строка 57:
 
Рассмотрим два случая:
 
Рассмотрим два случая:
 
# i' = j
 
# i' = j
: i < i' = j < j'. Тогда неравенство четырехугольника
+
: i < i' = j < j'. Тогда неравенство четырехугольника сводится к:
 +
: D[i][j] + D[j][j'] \leq D[i][j']
 +
: Пусть k = R[i][j']. Получили два симметричных случая:
 +
## k \leq j
 +
:: D[i][j] + D[j][j'] \leq w[i][j] + D[i][k-1] + D[k][j] + D{j][j'] - по определению D[i][j].
 +
:: <= w[i][j'] + D[i][k-1] + D[k][j] + D{j][j'] - по монотонности w
 +
:: <= w[i][j'] + D[i][k-1] + D[k][j'] - по предположению индукции
 +
:: <= D[i][j'] - по определению D[i][j']
 +
## k \geq j - аналогичный предыдущему случай.
 +
# i' < j
 +
: i < i' < j < j'
 +
Пусть y = R[i'][j] и z = R[i][j]. Получили два различных симметричных случая:
 +
z \leq y или z \geq y. Рассмотрим первый из них.
 +
 
 +
Получили z \leq y \leq j (по определению y) и i < z(по определению z). Получим:
 +
 
 +
D[i'][j'] + D[i][j] \leq D_y[i'][j'] + D_z[i][j]
 
}}
 
}}
  

Версия 03:18, 18 декабря 2010

Определение

Определение:
Оптимальный префиксный код с сохранением порядка(англ. order-preserving code, alphabetic code).

Пусть у нас есть алфавит [math] \Sigma [/math]. Каждому символу [math]c_i [/math] сопоставим его код [math] p_i [/math]. Кодирование называется оптимальным префиксным с сохранением порядка, если соблюдаются:

  1. Условие порядка - [math] \forall i, j : c_i \lt c_j \iff p_i \lt p_j [/math]. То есть, если символ [math]c_i [/math] лексикографически меньше символа [math] c_j [/math], его код также будет лексикографически меньше, и наоборот.
  2. Условие оптимальности - [math] \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| [/math] - минимально, где [math] f_i [/math] - частота встречаемости символа [math] c_i [/math] в тексте, а [math]|p_i| [/math] - длина его кода.


Алгоритм

Алгоритм нахождения оптимального префиксного кода с сохранением порядка. Решим задачу, используя ДП на подотрезках. Пусть в ячейке [math] D[i][j] [/math] хранится минимальная стоимость кодового дерева для отрезка алфавита от i до j.

Тогда пересчет [math] D[i][j] [/math] будет происходить так:

[math] D[i][j] = \min\limits_{k = i}^{j - 1} \left ( D[i][k] + D[k + 1][j] \right ) + w[i][j][/math]

Базой динамики будет [math] D[i][i] = 0 [/math]

Добавочный член [math]w[i][j] = \sum\limits_{t = i}^{j} f_t [/math] возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на 1, а значит, и длины всех кодов символов [math] c_i .. c_j [/math] также увеличиваются на 1.

Тогда такое наибольшее k, на котором достигается этот минимум, называется точкой разреза для отрезка [math] [i, j] [/math]. Пусть в ячейке [math] R[i][j] [/math] хранится точка разреза на отрезке [math] [i, j] [/math].

Монотонность точки разреза

Для доказательства этого сперва докажем несколько лемм.


Определение:
Функция a удовлетворяет неравенству четырехугольника(quadrangle inequation), если
[math]\forall i \leq i' \leq j \leq j' : a[i][j] + a[i'][j'] \leq a[i'][j] + a[i][j'][/math]


Определение:
Функция a является монотонной(monotone), если
[math]\forall i \leq i' \lt j \leq j' : a[i][j'] \leq a[i'][j] [/math]


Лемма:
w удовлетворяет неравенству четырехугольника.
Доказательство:
[math]\triangleright[/math]

Заметим, что [math] w[i][j] = w[i][t] + w[t+1][j] [/math], так как [math] w[i][j] [/math] - простая арифметическая сумма. Тогда:

[math] w[i][j] + w[i'][j'] \leq w[i'][j] + w[i][j'][/math]
[math] (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \leq (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) [/math]
Получили [math] 0 \leq 0 [/math], что является верным. Лемма доказана.
[math]\triangleleft[/math]
Лемма:
Если w удовлетворяет неравенству четырехугольника и монотонна, то D также удовлетворяет неравенству четырехугольника.
Доказательство:
[math]\triangleright[/math]

При [math] i = i' [/math] или [math] j = j' [/math], очевидно, неравенство выполняется.

Рассмотрим два случая:

  1. i' = j
i < i' = j < j'. Тогда неравенство четырехугольника сводится к:
D[i][j] + D[j][j'] \leq D[i][j']
Пусть k = R[i][j']. Получили два симметричных случая:
    1. k \leq j
D[i][j] + D[j][j'] \leq w[i][j] + D[i][k-1] + D[k][j] + D{j][j'] - по определению D[i][j].
<= w[i][j'] + D[i][k-1] + D[k][j] + D{j][j'] - по монотонности w
<= w[i][j'] + D[i][k-1] + D[k][j'] - по предположению индукции
<= D[i][j'] - по определению D[i][j']
    1. k \geq j - аналогичный предыдущему случай.
  1. i' < j
i < i' < j < j'

Пусть y = R[i'][j] и z = R[i][j]. Получили два различных симметричных случая: z \leq y или z \geq y. Рассмотрим первый из них.

Получили z \leq y \leq j (по определению y) и i < z(по определению z). Получим:

D[i'][j'] + D[i][j] \leq D_y[i'][j'] + D_z[i][j]
[math]\triangleleft[/math]
Теорема (Монотонность точки разреза):
[math] R[i][j - 1] \leq R[i][j] \leq R[i + 1][j] [/math]
Доказательство:
[math]\triangleright[/math]
Для доказательства этого сперва докажем несколько лемм:
[math]\triangleleft[/math]