Universal code (data compression) (original) (raw)
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 ?
| Property | Value |
|---|---|
| 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) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Fibonacci,_Elias_Gamm..._Delta_encoding_schemes.gif?width=300 |
| dbo:wikiPageExternalLink | http://www.inference.phy.cam.ac.uk/mackay/itila/ http://www.compression.ru/download/articles/int/levenstein_1968_on_the_redundancy_and_delay.pdf https://web.archive.org/web/20070214150309/http:/www-lat.compression.ru/download/integers.html https://web.archive.org/web/20080807041150/http:/www.cs.tut.fi/~albert/Dev/pucrunch/ https://web.archive.org/web/20150606201418/http:/scholar.google.com/scholar%3Fcluster=13442560459874106744 http://www.ics.uci.edu/~dan/pubs/DC-Sec3.html |
| dbo:wikiPageID | 2522009 (xsd:integer) |
| dbo:wikiPageLength | 7416 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1076519758 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Power_law dbr:Probability_distribution dbr:Elias_delta_coding dbr:Elias_gamma_coding dbr:Elias_omega_coding dbr:Base_16 dbr:Block_code dbr:University_of_California,_Irvine dbr:‡ dbr:Levenshtein_coding dbc:Data_compression dbr:Gauss–Kuzmin_distribution dbr:Geometric_distribution dbr:Golden_ratio dbr:Golomb_coding dbr:Arithmetic_coding dbr:Comma_code dbc:Lossless_compression_algorithms dbr:Data_compression dbr:Expected_value dbr:FLAC dbr:Base_15 dbr:Prefix_code dbr:Asterisk dbr:Zeta_distribution dbr:Audio_codec dbr:Fibonacci_coding dbr:Huffman_coding dbr:H.264/MPEG-4_AVC dbr:Kullback–Leibler_divergence dbr:Nibble dbr:Unary_coding dbr:Exponential-Golomb_coding dbr:Lexicographical_order dbr:Variable-length_quantity dbr:Arithmetic_encoding dbr:Fibonacci_code dbr:Independent_identically-distributed_random_variables dbr:David_MacKay_(scientist) dbr:Zipf_distribution dbr:Information_entropy dbr:Byte_coding dbr:File:Fibonacci,_Elias_Gamma,_and_Elias_Delta_encoding_schemes.GIF dbr:File:RiceEncodingScheme.GIF dbr:Optimal_code dbr:Universal_source_coding |
| dbp:date | August 2019 (en) |
| dbp:reason | How is this trivially restated in lexicographical order? (en) |
| dbp:wikiPageUsesTemplate | dbt:Compression_Methods dbt:Explain dbt:Math dbt:Refimprove dbt:Short_description |
| dct:subject | dbc:Data_compression dbc:Lossless_compression_algorithms |
| gold:hypernym | dbr:Code |
| rdf:type | yago:WikicatLosslessCompressionAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity dbo:Film yago:Rule105846932 |
| 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) |
| rdfs:label | Code universel (fr) 범용 부호 (ko) Универсальный код (ru) Universal code (data compression) (en) |
| owl:sameAs | freebase:Universal code (data compression) dbpedia-ru:Universal code (data compression) yago-res:Universal code (data compression) wikidata:Universal code (data compression) dbpedia-fr:Universal code (data compression) dbpedia-ko:Universal code (data compression) https://global.dbpedia.org/id/3srku |
| prov:wasDerivedFrom | wikipedia-en:Universal_code_(data_compression)?oldid=1076519758&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Fibonacci,_Elias_Gamma,_and_Elias_Delta_encoding_schemes.gif wiki-commons:Special:FilePath/RiceEncodingScheme.gif |
| foaf:isPrimaryTopicOf | wikipedia-en:Universal_code_(data_compression) |
| is dbo:knownFor of | dbr:Peter_Elias |
| is dbo:wikiPageDisambiguates of | dbr:Universal_code |
| is dbo:wikiPageRedirects of | dbr:Universal_Code_(DataCompression) dbr:Universal_coding_(data_compression) |
| is dbo:wikiPageWikiLink of | dbr:Elias_delta_coding dbr:Elias_gamma_coding dbr:Elias_omega_coding dbr:Entropy_coding dbr:List_of_algorithms dbr:Peter_Elias dbr:Incremental_encoding dbr:Elias_coding dbr:Levenshtein_coding dbr:Lossless_compression dbr:Data_compression dbr:Prefix_code dbr:Fibonacci_coding dbr:Minimum_description_length dbr:Universal_code dbr:Negafibonacci_coding dbr:Exponential-Golomb_coding dbr:Even–Rodeh_coding dbr:Variable-length_quantity dbr:Universal_Code_(DataCompression) dbr:Universal_coding dbr:Universal_coding_(data_compression) |
| is dbp:knownFor of | dbr:Peter_Elias |
| is foaf:primaryTopic of | wikipedia-en:Universal_code_(data_compression) |
