1679
правок
Изменения
м
Новая страница: «печальная статья. Определение: Оптимальный префиксный код с сохранением порядка(англ. ''…»
печальная статья.
Определение: [[Оптимальный префиксный код]] с сохранением порядка(англ. ''order-preserving code'', ''alphabetic code'')
Пусть у нас есть алфавит <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>. То есть, если символ c_i лексикографически меньше символа c_j, его код также будет [[лексикографически | лексикографический порядок]] меньше, и наоборот.
# Условие оптимальности - <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> - минимально, где f_i - количество(или вероятность) встретить символ c_i в тексте, а |p_i| - длина его кода.
Определение: [[Оптимальный префиксный код]] с сохранением порядка(англ. ''order-preserving code'', ''alphabetic code'')
Пусть у нас есть алфавит <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>. То есть, если символ c_i лексикографически меньше символа c_j, его код также будет [[лексикографически | лексикографический порядок]] меньше, и наоборот.
# Условие оптимальности - <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> - минимально, где f_i - количество(или вероятность) встретить символ c_i в тексте, а |p_i| - длина его кода.
