| dbo:abstract
|
- En compression de données, un code universel est un code préfixe dont les mots ont une longueur dont l'espérance mathématique ne dépasse pas celle de la longueur des mots du code optimal à un facteur constant près. Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ? (fr)
- In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is monotonic (i.e., p(i) ≥ p(i + 1) for all positive i), the expected lengths of the codewords are within a constant factor of the expected lengths that the for that probability distribution would have assigned. A universal code is asymptotically optimal if the ratio between actual and optimal expected lengths is bounded by a function of the information entropy of the code that, in addition to being bounded, approaches 1 as entropy approaches infinity. In general, most prefix codes for integers assign longer codewords to larger integers. Such a code can be used to efficiently communicate a message drawn from a set of possible messages, by simply ordering the set of messages by decreasing probability and then sending the index of the intended message. Universal codes are generally not used for precisely known probability distributions, and no universal code is known to be optimal for any distribution used in practice. A universal code should not be confused with , in which the data compression method need not be a fixed prefix code and the ratio between actual and optimal expected lengths must approach one. However, note that an asymptotically optimal universal code can be used on independent identically-distributed sources, by using increasingly large blocks, as a method of universal source coding. (en)
- 데이터 압축에서 범용 부호(Universal code)는 양의 정수를 구분자 없이 서로 구별되는 이진 부호로 대응시키는 이며, 그 중 정수의 실제 확률 분포와 상관 없이 분포가 단조적이면 (즉 모든 정수 에 대해 이 성립) 부호 길이의 기댓값이 길이의 기댓값보다 최대 상수배보다 작은 것을 가리킨다. 특히 두 기댓값의 비율의 한계가 부호의 정보 엔트로피의 함수로 주어지며, 엔트로피가 무한대로 접근하면 함수값이 1이 될 때 그 부호를 점근적으로 최적이라고 한다. 일반적으로 대부분의 범용 부호는 정수가 클수록 더 긴 부호를 대응시킨다. 이러한 부호는 가능한 메시지의 종류가 정해져 있을 때 효과적으로 이용할 수 있는데, 메시지를 확률이 큰 것부터 배열해서 번호를 붙인 뒤 원하는 메시지의 번호를 전송하는 방법을 쓸 수 있다. 범용 부호는 일반적으로 확률 분포가 잘 알려져 있을 때는 쓰이지 않으며, 아직 실용적으로 쓰이는 확률 분포에 대해 최적으로 알려져 있는 범용 부호는 없다. 양의 정수가 아닌 정수 전체를 대응시키는 부호는 부호화 전에 정수 (0, 1, -1, 2, -2, 3, -3, …)를 양의 정수 (1, 2, 3, 4, 5, 6, 7, …)로 대응시켜서 범용 부호로부터 만들어 낼 수 있다. (ko)
- Универсальный код для целых чисел в сжатии данных — префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределении вероятностей на целых числах, пока распределение — монотонно (то есть для любого ), ожидаемые длины двоичных слов находятся в пределах постоянного фактора ожидаемых длин, которые оптимальный код назначил бы для этого распределения вероятностей. Универсальный код асимптотически оптимален, если коэффициент между фактическими и оптимальными ожидаемыми длинами связывает функция информационной энтропии кода, которая приближается к 1, так как энтропия приближается к бесконечности. Большинство префиксных кодов для целых чисел назначает более длинные ключевые слова большим целым числам. Такой код может использоваться, чтобы эффективно закодировать сообщение, тянущееся из набора возможных сообщений, просто упорядочивая набор сообщений по уменьшению вероятности а затем пересылая индекс предназначаемого сообщения. Универсальные коды в общем не используются для точно известных распределений вероятностей. Универсальные коды включают в себя:
* Унарное кодирование
* Гамма-код Элиаса
* Дельта-код Элиаса
* Омега-код Элиаса
*
* Кодирование Фибоначчи
* Экспоненциальный код Голомба Некоторые неуниверсальные коды:
* , используется в кодах Элиаса
* Кодирование Райса
* Кодирование Голомба Их неуниверсальность проявляется в том, что если любые из них использовать, чтобы закодировать распределение Гаусса-Кузьмина или с параметром s=2, то ожидаемая длина ключевого слова бесконечена. Например, используя одноместное кодирование на дзета-распределение, имеем следующую ожидаемую длину: (ru)
|
| rdfs:comment
|
- En compression de données, un code universel est un code préfixe dont les mots ont une longueur dont l'espérance mathématique ne dépasse pas celle de la longueur des mots du code optimal à un facteur constant près. Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ? (fr)
- In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is monotonic (i.e., p(i) ≥ p(i + 1) for all positive i), the expected lengths of the codewords are within a constant factor of the expected lengths that the for that probability distribution would have assigned. A universal code is asymptotically optimal if the ratio between actual and optimal expected lengths is bounded by a function of the information entropy of the code that, in addition to being bounded, approaches 1 as entropy approaches infinity. (en)
- 데이터 압축에서 범용 부호(Universal code)는 양의 정수를 구분자 없이 서로 구별되는 이진 부호로 대응시키는 이며, 그 중 정수의 실제 확률 분포와 상관 없이 분포가 단조적이면 (즉 모든 정수 에 대해 이 성립) 부호 길이의 기댓값이 길이의 기댓값보다 최대 상수배보다 작은 것을 가리킨다. 특히 두 기댓값의 비율의 한계가 부호의 정보 엔트로피의 함수로 주어지며, 엔트로피가 무한대로 접근하면 함수값이 1이 될 때 그 부호를 점근적으로 최적이라고 한다. 일반적으로 대부분의 범용 부호는 정수가 클수록 더 긴 부호를 대응시킨다. 이러한 부호는 가능한 메시지의 종류가 정해져 있을 때 효과적으로 이용할 수 있는데, 메시지를 확률이 큰 것부터 배열해서 번호를 붙인 뒤 원하는 메시지의 번호를 전송하는 방법을 쓸 수 있다. 범용 부호는 일반적으로 확률 분포가 잘 알려져 있을 때는 쓰이지 않으며, 아직 실용적으로 쓰이는 확률 분포에 대해 최적으로 알려져 있는 범용 부호는 없다. (ko)
- Универсальный код для целых чисел в сжатии данных — префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределении вероятностей на целых числах, пока распределение — монотонно (то есть для любого ), ожидаемые длины двоичных слов находятся в пределах постоянного фактора ожидаемых длин, которые оптимальный код назначил бы для этого распределения вероятностей. Универсальные коды включают в себя: Некоторые неуниверсальные коды:
* , используется в кодах Элиаса
* Кодирование Райса
* Кодирование Голомба (ru)
|
