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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 4: Строка 4:
 
# Условие порядка - <tex> \forall i, j : c_i < c_j \iff p_i < p_j </tex>. То есть, если символ c_i лексикографически меньше символа c_j, его код также будет [[лексикографический порядок | лексикографически]] меньше, и наоборот.
 
# Условие порядка - <tex> \forall i, j : c_i < c_j \iff p_i < p_j </tex>. То есть, если символ c_i лексикографически меньше символа c_j, его код также будет [[лексикографический порядок | лексикографически]] меньше, и наоборот.
 
# Условие оптимальности - <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> - минимально, где f_i - количество(или вероятность) встретить символ c_i в тексте, а |p_i| - длина его кода.
 
# Условие оптимальности - <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> - минимально, где f_i - количество(или вероятность) встретить символ c_i в тексте, а |p_i| - длина его кода.
 +
 +
Алгоритм нахождения оптимального префиксного кода с сохранением порядка.
 +
Решим задачу используя ДП на подотрезках. Пусть в ячейке D[i][j] хранится минимальная стоимость кодового дерева(???) для отрезка алфавита от i до j.
 +
Определение точки разреза:
 +
R[i][j]
 +
Пересчет:
 +
<tex> D[i][j] = \min\limits_{k = i}^{j - 1} D[i][k] + D[k + 1][j] + S </tex>

Версия 04:52, 16 декабря 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]. То есть, если символ c_i лексикографически меньше символа c_j, его код также будет лексикографически меньше, и наоборот.
  2. Условие оптимальности - [math] \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| [/math] - минимально, где f_i - количество(или вероятность) встретить символ c_i в тексте, а |p_i| - длина его кода.

Алгоритм нахождения оптимального префиксного кода с сохранением порядка. Решим задачу используя ДП на подотрезках. Пусть в ячейке D[i][j] хранится минимальная стоимость кодового дерева(???) для отрезка алфавита от i до j. Определение точки разреза: R[i][j] Пересчет: [math] D[i][j] = \min\limits_{k = i}^{j - 1} D[i][k] + D[k + 1][j] + S [/math]