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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 31: Строка 31:
 
Функция a удовлетворяет '''неравенству четырехугольника(quadrangle inequation)''', если
 
Функция a удовлетворяет '''неравенству четырехугольника(quadrangle inequation)''', если
 
: <tex>\forall i \le i' \le j \le j' : a[i][j] + a[i'][j'] \le a[i'][j] + a[i][j']</tex>
 
: <tex>\forall i \le i' \le j \le j' : a[i][j] + a[i'][j'] \le a[i'][j] + a[i][j']</tex>
}}
 
 
{{Определение
 
| definition=
 
Функция a является '''монотонной(monotone)''', если
 
: <tex>\forall i \le i' < j \le j' : a[i][j'] \le a[i'][j] </tex>
 
 
}}
 
}}
  
Строка 52: Строка 46:
 
{{Лемма
 
{{Лемма
 
| statement=
 
| statement=
Если w удовлетворяет неравенству четырехугольника и монотонна, то D также удовлетворяет неравенству четырехугольника, то есть:
+
Если w удовлетворяет неравенству четырехугольника, то D также удовлетворяет неравенству четырехугольника, то есть:
  
 
<tex>\forall i \le i' \le j \le j' : D[i][j] + D[i'][j'] \le D[i'][j] + D[i][j'] </tex>
 
<tex>\forall i \le i' \le j \le j' : D[i][j] + D[i'][j'] \le D[i'][j] + D[i][j'] </tex>
 
| proof=
 
| proof=
При <tex> i = i' </tex> или <tex> j = j' </tex>, очевидно, неравенство выполняется.
+
База индукции: при <tex> i = i' </tex> или <tex> j = j' </tex>, очевидно, неравенство выполняется.
  
 
Рассмотрим два случая:
 
Рассмотрим два случая:
Строка 65: Строка 59:
 
## <tex> k \le j </tex>
 
## <tex> k \le j </tex>
 
##: <tex> D[i][j] + D[j][j'] \le w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] </tex> - по определению <tex> D[i][j] </tex>
 
##: <tex> D[i][j] + D[j][j'] \le w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] </tex> - по определению <tex> D[i][j] </tex>
##: <tex> \le w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] </tex> - по монотонности w
+
##: <tex> \le w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] </tex> - так как <tex> w[i][j'] >= w[i][j] </tex>
 
##: <tex> \le w[i][j'] + D[i][k-1] + D[k][j'] </tex> - по индукционному предположению для D
 
##: <tex> \le w[i][j'] + D[i][k-1] + D[k][j'] </tex> - по индукционному предположению для D
 
##: <tex> \le D[i][j'] </tex> - по определению <tex> D[i][j'] </tex>
 
##: <tex> \le D[i][j'] </tex> - по определению <tex> D[i][j'] </tex>
Строка 86: Строка 80:
 
Монотонность точки разреза
 
Монотонность точки разреза
 
| statement=
 
| statement=
Если w удовлетворяет неравенству четырехугольника и монотонна, то:
+
Если w удовлетворяет неравенству четырехугольника, то:
  
 
<tex> \forall i \le j : R[i][j] \le R[i][j+1] \le R[i+1][j+1] </tex>   
 
<tex> \forall i \le j : R[i][j] \le R[i][j+1] \le R[i+1][j+1] </tex>   
 
| proof=
 
| proof=
В случае i = j неравенство, очевидно, выполняется. Рассматриваем случай i < j и только случай R[i][j] \le R[i][j+1](вторая часть доказывается аналогично):
+
В случае <tex> i = j </tex> неравенство, очевидно, выполняется. Рассматриваем случай <tex> i < j </tex> и только случай <tex> R[i][j] \le R[i][j+1] </tex>(вторая часть доказывается аналогично):
  
Так как R[i][j] - максимальный индекс, в котором достигается минимум, достаточно показать, что:
+
Так как <tex> R[i][j] </tex> - максимальный индекс, в котором достигается минимум, достаточно показать, что:
: <tex> \forall i < k \le k' \le j: [D_{k'}[i][j] \le D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \le D_k[i][j+1]] </tex>
+
: <tex> \forall i < k \le k' \le j: [D_{k'}[i][j] \le D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \le 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 \le k' \le j: D_k[i][j] - D_{k'}[i][j] \le D_k[i][j+1] - D_{k'}[i][j+1] </tex>
 
: <tex> \forall i < k \le k' \le j: D_k[i][j] - D_{k'}[i][j] \le D_k[i][j+1] - D_{k'}[i][j+1] </tex>
Строка 101: Строка 95:
 
: <tex> (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \le (w[i][j+1] + D[i][k-1] + D[k][j+1]) + (w[i][j] + D[i][k'-1] + D[k'][j]) </tex> - по определению D
 
: <tex> (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \le (w[i][j+1] + D[i][k-1] + D[k][j+1]) + (w[i][j] + D[i][k'-1] + D[k'][j]) </tex> - по определению D
  
: <tex> D[k][j] + D[k'][j+1] \Rightarrow D[k][j+1] + D[k'][j] </tex> - получили неравенство четырехугольника для <tex> k \le k' \le j \le j+1 </tex>
+
: <tex> D[k][j] + D[k'][j+1] \le D[k][j+1] + D[k'][j] </tex> - получили неравенство четырехугольника для <tex> k \le k' \le j \le j+1 </tex>, что является верным из предыдущей леммы. Теорема доказана.
 
}}
 
}}

Версия 21:50, 20 декабря 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 \le i' \le j \le j' : a[i][j] + a[i'][j'] \le a[i'][j] + 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'] \le w[i'][j] + w[i][j'][/math]
[math] (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \le (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]\forall i \le i' \le j \le j' : D[i][j] + D[i'][j'] \le D[i'][j] + D[i][j'] [/math]
Доказательство:
[math]\triangleright[/math]

База индукции: при [math] i = i' [/math] или [math] j = j' [/math], очевидно, неравенство выполняется.

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

  1. [math] i' = j [/math]
    [math] i \lt i' = j \lt j' [/math]. Тогда неравенство четырехугольника сводится к:
    [math] D[i][j] + D[j][j'] \le D[i][j'] [/math]
    Пусть [math] k = R[i][j'] [/math]. Получили два симметричных случая:
    1. [math] k \le j [/math]
      [math] D[i][j] + D[j][j'] \le w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] [/math] - по определению [math] D[i][j] [/math]
      [math] \le w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] [/math] - так как [math] w[i][j'] \gt = w[i][j] [/math]
      [math] \le w[i][j'] + D[i][k-1] + D[k][j'] [/math] - по индукционному предположению для D
      [math] \le D[i][j'] [/math] - по определению [math] D[i][j'] [/math]
    2. [math] k \ge j [/math] - аналогичный предыдущему случай.
  2. [math] i' \lt j [/math]
    [math] i \lt i' \lt j \lt j' [/math]
    Пусть [math] y = R[i'][j] [/math] и [math] z = R[i][j'] [/math]. Получили два различных симметричных случая:
    1. [math] z \le y [/math]
      Получили [math] z \le y \le j [/math] (по определению y) и [math] i \lt z [/math](по определению z). Получим:
      [math] D[i'][j'] + D[i][j] \le 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] [/math]
      [math] \le w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] [/math] - по неравенству четырехугольника для [math] w [/math]
      [math] \le w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] [/math] - по индукционному предположению для D
      [math] \le D[i][j'] + D[i'][j] [/math] - по определению D.
    2. [math] z \ge y [/math] доказывается аналогично
Индукционный шаг завершен, лемма доказана.
[math]\triangleleft[/math]
Теорема (Монотонность точки разреза):
Если w удовлетворяет неравенству четырехугольника, то: [math] \forall i \le j : R[i][j] \le R[i][j+1] \le R[i+1][j+1] [/math]
Доказательство:
[math]\triangleright[/math]

В случае [math] i = j [/math] неравенство, очевидно, выполняется. Рассматриваем случай [math] i \lt j [/math] и только случай [math] R[i][j] \le R[i][j+1] [/math](вторая часть доказывается аналогично):

Так как [math] R[i][j] [/math] - максимальный индекс, в котором достигается минимум, достаточно показать, что:

[math] \forall i \lt k \le k' \le j: [D_{k'}[i][j] \le D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \le D_k[i][j+1]] [/math] - фактически, это означает что если на отрезке [math] i..j [/math] разрез оптимальнее по [math] k' [/math], чем по [math] k [/math], то он также будет оптимальнее и на отрезке [math] i..j+1 [/math].

Докажем более сильное неравенство:

[math] \forall i \lt k \le k' \le j: D_k[i][j] - D_{k'}[i][j] \le D_k[i][j+1] - D_{k'}[i][j+1] [/math]
[math] D_k[i][j] + D_{k'}[i][j+1] \le D_k[i][j+1] + D_{k'}[i][j] [/math]
[math] (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \le (w[i][j+1] + D[i][k-1] + D[k][j+1]) + (w[i][j] + D[i][k'-1] + D[k'][j]) [/math] - по определению D
[math] D[k][j] + D[k'][j+1] \le D[k][j+1] + D[k'][j] [/math] - получили неравенство четырехугольника для [math] k \le k' \le j \le j+1 [/math], что является верным из предыдущей леммы. Теорема доказана.
[math]\triangleleft[/math]