Huffman coding (original) (raw)

About DBpedia

في نظرية المعلومات والمعلوماتية، ترميز هوفمان (بالإنجليزية: Huffman coding)‏ يعتبر من ترميز انتروبي يستخدم في الضغط غير الفاقد للبيانات، حيث يعتمد على ترميز متغير الطول لرموز المصدر بما يتناسب مع احتمال ظهورها.طور ديفيد هوفمان هذا الترميز عندما كان طالب دكتوراه في جامعة MIT ونشره عام 1952 في ورقة بحث بعنوان A Method for the Construction of Minimum-Redundancy Codes (طريقة إنشاء ترميز بفائض أصغري).

thumbnail

Property Value
dbo:abstract A ciències de la computació i teoria de la informació, la codificació Huffman és un algorisme utilitzat per compressió de dades. El terme es refereix a l'ús d'una taula de codis de longitud variable per a codificar un determinat símbol (com pot ser un caràcter en un fitxer), on la taula ha estat emplenada d'una manera específica basant-se en la probabilitat estimada d'aparició de cada possible valor d'aquest símbol. Va ser desenvolupat per David A. Huffman mentre era estudiant de doctorat en el MIT, i publicat a "A Method for the Construction of Minimum-Redundancy Codes". La codificació Huffman fa servir un mètode específic per a triar la representació de cada símbol, que dona lloc a un (és a dir, la cadena de bits que representa un símbol en particular mai és prefix de la cadena de bits d'un símbol diferent) que representa els caràcters més comuns utilitzant les cadenes de bits més curtes, i viceversa. Huffman va ser capaç de dissenyar el mètode de compressió més eficient d'aquest tipus: cap representació alternativa d'un conjunt de símbols d'entrada produeix una sortida mitjana més petita quan les freqüències dels símbols coincideixen amb les utilitzades per crear el codi. Posteriorment es va trobar un mètode per dur això a terme en un temps lineal si les probabilitats dels símbols d'entrada (és a dir "pesos") estan ordenades. Per a un grup de símbols amb una i un nombre de membres que és potència de dos, la codificació Huffman és equivalent a una codificació en bloc binària, per exemple, la codificació ASCII. La codificació Huffman és un mètode per crear codis prefix tan estès que el terme "codificació Huffman" és àmpliament usat com a sinònim de "codi prefix", fins i tot quan aquest codi no s'ha produït amb l'algorisme de Huffman. Encara que la codificació de Huffman és òptima per a una codificació símbol a símbol donada una distribució de probabilitat, la seva optimalitat de vegades es pot veure accidentalment exagerada. Per exemple, la i la codificació LZW normalment ofereixen major capacitat de compressió. Aquests dos mètodes poden agrupar un nombre arbitrari de símbols per a una codificació més eficient, i, en general, s'adapten a les estadístiques d'entrada reals, i aquest últim és útil quan les probabilitats no es coneixen de manera precisa o varien sinificativamente dins del flux de dades. (ca) Huffmanovo kódování je algoritmus využívaný pro bezeztrátovou kompresi dat. Konvertuje znaky vstupního souboru do bitových řetězců různé délky. Znaky, které se ve vstupním souboru vyskytují nejčastěji, jsou konvertovány do bitových řetězců s nejkratší délkou (nejfrekventovanější znak tak může být konvertován do jediného bitu), zatímco znaky, které se vyskytují velmi zřídka, jsou konvertovány do delších řetězců (mohou být i delší než 8 bitů). Nejjednodušší metoda komprese touto metodou probíhá ve dvou fázích. První projde soubor a vytvoří statistiku četností každého znaku. Ve druhé fázi se využije této statistiky pro vytvoření binárního stromu a k následné kompresi vstupních dat. Dekomprese naopak pomocí rekonstruovaného binárního stromu dekóduje řetězce proměnlivé délky. (cs) في نظرية المعلومات والمعلوماتية، ترميز هوفمان (بالإنجليزية: Huffman coding)‏ يعتبر من ترميز انتروبي يستخدم في الضغط غير الفاقد للبيانات، حيث يعتمد على ترميز متغير الطول لرموز المصدر بما يتناسب مع احتمال ظهورها.طور ديفيد هوفمان هذا الترميز عندما كان طالب دكتوراه في جامعة MIT ونشره عام 1952 في ورقة بحث بعنوان A Method for the Construction of Minimum-Redundancy Codes (طريقة إنشاء ترميز بفائض أصغري). (ar) Η κωδικοποίηση Χούφμαν είναι μια μέθοδος συμπίεσης που δημοσιεύτηκε το 1952 από τον και έμελλε να γίνει πασίγνωστη. Εκδοχές του αλγορίθμου Χούφμαν χρησιμοποιούνται στη μετάδοση αντιγράφων και στις απεικονίσεις εγγράφων. Το πρότυπο JPEG ενσωματώνει την κωδικοποίηση Χούφμαν ως τελικό βήμα στη διαδικασία συμπίεσης εικόνας. Η κωδικοποίηση Χούφμαν αποδεικνύεται βέλτιστη για ένα δεδομένο κείμενο, αν και ο πίνακας κωδικοποίησης πρέπει να μεταδίδεται μαζί με τα δεδομένα. (el) Die Huffman-Kodierung ist eine Form der Entropiekodierung, die 1952 von David A. Huffman entwickelt und in der Abhandlung A Method for the Construction of Minimum-Redundancy Codes publiziert wurde. Sie ordnet einer festen Anzahl an Quellsymbolen jeweils Codewörter mit variabler Länge zu. In der Informationstechnik ist sie ein Präfixcode, der üblicherweise für verlustfreie Kompression benutzt wird. Wie bei anderen Entropiekodierungen werden häufiger vorkommende Zeichen mit weniger Bits repräsentiert als seltener vorkommende Zeichen. (de) Huffman kodifikazioa algoritmo bat da, konputazio-zientzia eta informazioaren teorian erabiltzen dena datuen konpresiorako. oinarritzen den metodo bat da, agertzen diren sinbolo edo karaktereen maiztasunaren arabera, hauei kode zehatz bat esleitzeko erabiltzen dena. David A. Huffmanek garatutako metodo bat da, MITen doktoretza gauzatzen zuen bitartean garatutakoa. Hau A Method for the Construction of Minimum-Redundancy Codes delako artikuluan argitaratu zen. (eu) In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes". The output from Huffman's algorithm can be viewed as a variable-length code table for encoding a source symbol (such as a character in a file). The algorithm derives this table from the estimated probability or frequency of occurrence (weight) for each possible value of the source symbol. As in other entropy encoding methods, more common symbols are generally represented using fewer bits than less common symbols. Huffman's method can be efficiently implemented, finding a code in time linear to the number of input weights if these weights are sorted. However, although optimal among methods encoding symbols separately, Huffman coding among all compression methods - it is replaced with arithmetic coding or asymmetric numeral systems if a better compression ratio is required. (en) En ciencias de la computación y teoría de la información, la codificación Huffman es un algoritmo usado para compresión de datos. El término se refiere al uso de una tabla de códigos de longitud variable para codificar un determinado símbolo (como puede ser un carácter en un archivo), donde la tabla ha sido rellenada de una manera específica basándose en la probabilidad estimada de aparición de cada posible valor de dicho símbolo. Fue desarrollado por David A. Huffman mientras era estudiante de doctorado en el MIT, y publicado en "A Method for the Construction of Minimum-Redundancy Codes". La codificación Huffman usa un método específico para elegir la representación de cada símbolo, que da lugar a un código prefijo (es decir, la cadena de bits que representa a un símbolo en particular nunca es prefijo de la cadena de bits de un símbolo distinto) que representa los caracteres más comunes usando las cadenas de bits más cortas, y viceversa. Huffman fue capaz de diseñar el método de compresión más eficiente de este tipo: ninguna representación alternativa de un conjunto de símbolos de entrada produce una salida media más pequeña cuando las frecuencias de los símbolos coinciden con las usadas para crear el código. Posteriormente se encontró un método para llevar esto a cabo en un tiempo lineal si las probabilidades de los símbolos de entrada (también conocidas como "pesos") están ordenadas. Para un grupo de símbolos con una distribución de probabilidad uniforme y un número de miembros que es potencia de dos, la codificación Huffman es equivalente a una codificación en bloque binaria, por ejemplo, la codificación ASCII. La codificación Huffman es un método para crear códigos prefijo tan extendido que el término "codificación Huffman" es ampliamente usado como sinónimo de "código prefijo", incluso cuando dicho código no se ha producido con el algoritmo de Huffman. Aunque la codificación de Huffman es óptima para una codificación símbolo a símbolo dada una distribución de probabilidad, su optimalidad a veces puede verse accidentalmente exagerada. Por ejemplo, la codificación aritmética y la codificación LZW normalmente ofrecen mayor capacidad de compresión. Estos dos métodos pueden agrupar un número arbitrario de símbolos para una codificación más eficiente, y en general se adaptan a las estadísticas de entrada reales. Este último es útil cuando las probabilidades no se conocen de forma precisa o varían significativamente dentro del flujo de datos. (es) Le codage de Huffman est un algorithme de compression de données sans perte. Le codage de Huffman utilise un code à longueur variable pour représenter un symbole de la source (par exemple un caractère dans un fichier). Le code est déterminé à partir d'une estimation des probabilités d'apparition des symboles de source, un code court étant associé aux symboles de source les plus fréquents. Un code de Huffman est optimal au sens de la plus courte longueur pour un codage par symbole, et une distribution de probabilité connue. Des méthodes plus complexes réalisant une modélisation probabiliste de la source permettent d'obtenir de meilleurs ratios de compression. Il a été inventé par David Albert Huffman, et publié en 1952. (fr) Dalam ilmu komputer dan teori informasi, Huffman coding adalah sebuah tipe code yang optimal yang biasanya digunakan untuk lossless data compression. Algoritme Huffman Coding ditemukan oleh David A. Huffman pada saat ia masih seorang mahasiswa di MIT, ia menerbitkan karyanya pada tahun 1952 yang berjudul "A Method for the Construction of Minimum Redundancy Codes". Hasil dari algoritme Huffman bisa dipandang sebagai sebuah tabel kode variabel-panjang untuk pengkodean simbol sumber (seperti sebuah karakter dalam sebuah file). Algoritme ini memperoleh dari tabel tersebut berdasarkan dari estimasi probabilitas atau frekuensi munculnya untuk setiap nilai yang mungkin dari simbol sumber. Seperti dalam metode pengkodean entropi lainnya, simbol yang lebih umum diwakili dengan bit yang lebih sedikit daripada simbol kurang umum. (in) 전산학과 정보 이론에서 허프먼 부호화(Huffman coding)는 무손실 압축에 쓰이는 엔트로피 부호화의 일종으로, 데이터 문자의 등장 빈도에 따라서 다른 길이의 부호를 사용하는 알고리즘이다. 1952년 당시 박사과정 학생이던 이 《A Method for the Construction of Minimum-Redundancy Codes》란 제목의 논문으로 처음 발표했다. 허프먼 부호화는 문자들의 빈도로부터 (어떤 한 문자에 대한 부호가 다른 부호들의 접두어가 되지 않는 부호)를 만들어 내는 알고리즘으로, 적게 나오는 문자일수록 더 긴 부호를 쓰고 많이 나올수록 더 짧은 부호를 쓴다. 허프먼 부호화는 주어진 빈도에 대해서 항상 최적의 접두 부호를 만들어 내며, 이 과정은 빈도가 정렬되어 있을 경우 O(n)만에 가능하다. 각 문자들의 빈도가 2의 거듭제곱 꼴이거나 모두 같을 경우 이 접두 부호는 간단한 이진 블록 부호와 동일하다. 허프먼 부호화가 항상 최적의 접두 부호를 만들어 내기는 하지만, 접두 부호가 아닌 다른 종류의 부호가 더 효율적일 수도 있다. 예를 들어 여러 문자를 하나의 부호로 묶어 표현할 수 있는 산술 부호화나 LZW 등이 허프먼 부호보다 효율적인 경우가 많으며, 이것은 대부분 하나의 기호를 정수개의 길이를 가진 부호로서 표현하도록 되어 있는 한계에서 기인한다. 위에서 아래로 진행하는 샤논파노방법과는 달리 허프먼 알고리즘의 부호화 순서는 아래에서 위로 진행한다. (ko) Nella teoria dell'informazione, per codifica di Huffman si intende un algoritmo di codifica dei simboli usato per la compressione di dati, basato sul principio di trovare il sistema ottimale per codificare stringhe basato sulla frequenza relativa di ciascun carattere. Essa è stata sviluppata nel 1952 da David A. Huffman, uno studente dottorando presso il MIT, e pubblicata su A Method for the Construction of Minimum-Redundancy Codes (lett. "Un metodo per la costruzione di codici a ridondanza minima"). La codifica di Huffman usa un metodo specifico per scegliere la rappresentazione di ciascun simbolo, risultando in un codice senza prefissi (cioè in cui nessuna stringa binaria di nessun simbolo è il prefisso della stringa binaria di nessun altro simbolo) che esprime il carattere più frequente nella maniera più breve possibile. È stato dimostrato che la codifica di Huffman è il più efficiente sistema di compressione di questo tipo: nessun'altra mappatura di simboli in stringhe binarie può produrre un risultato più breve nel caso in cui le frequenze di simboli effettive corrispondono a quelle usate per creare il codice. Per un insieme di simboli la cui cardinalità è una potenza di due e con una distribuzione probabilistica uniforme, la codifica di Huffman equivale alla semplice codifica a blocchi binari. (it) ハフマン符号（ハフマンふごう、英: Huffman coding）とは、1952年にデビッド・ハフマンによって開発された符号で、文字列をはじめとするデータの可逆圧縮などに使用される。 ほかのエントロピー符号と同様、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることで、メッセージ全体の符号化に使われるデータ量を削減することを狙っている。 コンパクト符号やエントロピー符号の一つ。JPEGやZIP (Deflate) などの圧縮フォーマットで使用されている。 シャノン符号化が最適ではない場合が存在する不完全な符号であったのに対し、ハフマン符号は（整数の符号語長という制約のもとでは、）常に最適な符号を構成できる。擬似的に実数の符号語長を割り振る算術符号と比較すれば、データ圧縮効率は劣る。ただし、算術符号やその他の高効率の符号化法と異なり、特許の問題が無い。 (ja) Алгоритм Хаффмана — жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных. В отличие от алгоритма Шеннона — Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m2 с более чем двумя символами. Этот метод кодирования состоит из двух основных этапов: 1. * Построение оптимального кодового дерева. 2. * Построение отображения код-символ на основе построенного дерева. (ru) Kodowanie Huffmana (ang. Huffman coding) – jedna z najprostszych i łatwych w implementacji metod kompresji bezstratnej. Została opracowana w 1952 roku przez Amerykanina Davida Huffmana. Algorytm Huffmana nie należy do najefektywniejszych obliczeniowo systemów bezstratnej kompresji danych, dlatego też praktycznie nie używa się go samodzielnie. Często wykorzystuje się go jako ostatni etap w różnych systemach kompresji, zarówno bezstratnej, jak i stratnej, np. MP3 lub JPEG. Pomimo że nie jest doskonały, stosuje się go ze względu na prostotę oraz brak ograniczeń patentowych. Jest to przykład wykorzystania algorytmu zachłannego. (pl) Huffmancodering is een methode om gegevens die bestaan uit een rij van symbolen, optimaal en verliesloos te comprimeren. De codering wordt onder andere toegepast bij datacommunicatie en voor . Huffmancodering is vernoemd naar David Huffman, die de codering in 1952 voor het eerst beschreef. Elk symbool wordt gecodeerd als een bitstring, zodanig dat de code van een symbool nooit het eerste deel is van de code van een ander symbool. Dit maakt het mogelijk een rij symbolen te coderen door de codes van de afzonderlijke symbolen achter elkaar te plaatsen zonder scheidingsteken. Bij het decoderen van een bitstring volgt na iedere herkenbare code het begin van een volgende eenduidig herkenbare code. Dit wordt een prefixcodering of prefixvrije codering genoemd. Het principe van huffmancodering is eenvoudig. Van een reeks symbolen worden de veel voorkomende symbolen weergegeven door een kortere code, dan de weinig voorkomende. Zo kan de hele reeks op een kortere manier gecodeerd worden. (nl) Huffmankodning är en datakomprimeringsalgoritm uppfunnen 1952 av doktoranden . I Huffmankodning byts sekvenser av symboler av fix längd entydigt ut mot andra sekvenser av tecken och koder av olika längd beroende på symbolens relativa frekvens. Relativ frekvens kan ses som sannolikheten att en viss symbol ska sändas.Ofta förekommande symboler ges kortare koder än sällan förekommande, så att den totala kodsekvensen blir så kort som möjligt.Det finns två metoder för att uppskatta den relativa frekvensen för symbolerna: * Symbolernas relativa frekvenser är kända på förhand. Antingen har detta gjorts genom att analysera hela filen som ska kodas, eller så använder man kunskap man har om källan. T.ex. kan man kanske anta att bokstaven "e" ska vara ungefär lika vanlig i alla tidningsartiklar på ett visst språk. Metoden kallas statisk huffmankodning. * Symbolernas sannolikhet uppskattas samtidigt som filen kodas. Kodningstabellen förändras under kodningens gång. Detta kallas adaptiv huffmankodning. En algoritm för att finna en binär (statisk) Huffmankodning är den följande: 1. * Ta de två ovanligaste tecknen och tilldela dem en nolla respektive en etta. 2. * Slå samman de två tecknen och deras frekvenser. 3. * Börja om från 1 om det finns fler än ett tecken kvar. Varje huffmankod kan representeras som ett huffmanträd, där symbolerna är lövnoder.Koden är sekvensen av ettor och nollor räknad från den sista tilldelningen. (sv) A codificação de Huffman é um método de compressão que usa as probabilidades de ocorrência dos símbolos no conjunto de dados a ser comprimido para determinar códigos de tamanho variável para cada símbolo. Ele foi desenvolvido em 1952 por David A. Huffman que era, na época, estudante de doutorado no MIT, e foi publicado no artigo "A Method for the Construction of Minimum-Redundancy Codes". Uma árvore binária completa, chamada de árvore de Huffman é construída recursivamente a partir da junção dos dois símbolos de menor probabilidade, que são então somados em símbolos auxiliares e estes símbolos auxiliares recolocados no conjunto de símbolos. O processo termina quando todos os símbolos forem unidos em símbolos auxiliares, formando uma árvore binária. A árvore é então percorrida, atribuindo-se valores binários de 1 ou 0 para cada aresta, e os códigos são gerados a partir desse percurso. A codificação de Huffman tem desempenho ótimo quando as probabilidades dos símbolos são potências negativas de dois. A codificação gerada tem também a garantia de ser não ambígua, pois nenhum código pode ser o prefixo de outro código. O resultado do algoritmo de Huffman pode ser visto como uma tabela de códigos de tamanho variável para codificar um símbolo da fonte. Assim como em outros métodos de codificação, os símbolos mais comuns são geralmente representados usando-se menos dígitos que os símbolos que aparecem com menos frequência. (pt) Алгоритм Гаффмана (або коди Гафмена) — адаптивний жадібний алгоритм оптимального префіксного кодування алфавіту з мінімальною надмірністю. Був розроблений аспірантом Массачусетського технологічного інституту Девідом Гаффманом при написанні ним курсової роботи та надрукований в статті 1952 року «A Method for the Construction of Minimum-Redundancy Codes». В даний час[коли?] використовується в багатьох програмах стиснення даних без втрат. На відміну від алгоритму Шеннона — Фано, алгоритм Гаффмана залишається завжди оптимальним і для m2 з більш ніж двома символами. Цей метод кодування складається з двох основних етапів: 1. * Побудова оптимального кодового дерева 2. * Побудова відображення код-символ на основі побудованого дерева (uk) 霍夫曼編碼（英語：Huffman Coding），又譯為哈夫曼编码、赫夫曼编码，是一種用於无损数据压缩的熵編碼（權編碼）演算法。由美國計算機科學家大衛·霍夫曼（David Albert Huffman）在1952年發明。 (zh)
dbo:thumbnail wiki-commons:Special:FilePath/Huffman_tree_2.svg?width=300
dbo:wikiPageExternalLink https://demo.tinyray.com/huffman http://rosettacode.org/wiki/Huffman_coding https://gist.github.com/jasonrdsouza/1c9c895f43497d15eb2e http://ieeexplore.ieee.org/xpl/articleDetails.jsp%3Farnumber=1057615&newsearch=true&queryText=Minimum-redundancy%20coding%20for%20the%20discrete%20noiseless%20channel http://ieeexplore.ieee.org/xpl/articleDetails.jsp%3Farnumber=705558&queryText=dynamic%20programming%20golin%20constructing%20optimal%20prefix-free&newsearch=true
dbo:wikiPageID 13883 (xsd:integer)
dbo:wikiPageLength 35261 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1117474402 (xsd:integer)
dbo:wikiPageWikiLink dbr:Canonical_Huffman_code dbr:Power_of_two dbr:Proportionality_(mathematics) dbr:Binary_search_tree dbr:Binary_tree dbr:Block_code dbr:David_A._Huffman dbr:Deflate dbr:Dyadic_distribution dbr:Introduction_to_Algorithms dbr:Thomas_H._Cormen dbr:Massachusetts_Institute_of_Technology dbr:Claude_Shannon dbr:Clifford_Stein dbr:Entropy_encoding dbr:Golomb_coding dbr:Monoid dbr:Morse_code dbr:Arithmetic_coding dbr:Bernoulli_process dbr:Linear_time dbr:MIT dbr:MP3 dbr:Computer_science dbr:Patent dbr:Priority_queue dbr:Term_paper dbc:Lossless_compression_algorithms dbr:Adaptive_Huffman_coding dbc:1952_in_computing dbr:Time_complexity dbr:Total_order dbr:Doctor_of_Science dbr:Garsia–Wachs_algorithm dbr:Leaf_node dbr:Package-merge_algorithm dbr:ASCII dbr:Adriano_Garsia dbr:Expected_value dbr:Prefix_code dbr:Quantization_(signal_processing) dbr:Run-length_encoding dbr:Asymmetric_numeral_systems dbr:JPEG dbr:Array_data_type dbr:A_Mathematical_Theory_of_Communication dbc:Binary_trees dbr:Charles_E._Leiserson dbr:Alan_Tucker dbr:Big_O_notation dbr:Codec dbr:Modified_Huffman_coding dbr:Greedy_algorithm dbr:Polynomial_time dbr:Information_theory dbr:Internal_node dbr:Michelle_L._Wachs dbr:Shannon's_source_coding_theorem dbr:Probability_mass_function dbr:Variable-length_code dbr:Exam dbr:Shannon–Fano_coding dbr:PKZIP dbr:Shannon_entropy dbr:Frequency_table dbr:Linear-time dbr:Lossless_data_compression dbr:Independent_and_identically_distributed dbr:Queue_(data_structure) dbr:Information_entropy dbr:Robert_M._Fano dbr:Ronald_L._Rivest dbr:File:HuffmanCodeAlg.png dbr:File:Huffman_coding_example.svg dbr:File:Huffman_coding_visualisation.svg dbr:File:Huffman_tree_2.svg dbr:T._C._Hu dbr:Weighted_path_length_from_the_root
dbp:cs1Dates y (en)
dbp:date May 2019 (en)
dbp:wikiPageUsesTemplate dbt:Compression_Methods dbt:Anchor dbt:Break dbt:Citation_needed dbt:Commons_category dbt:Main dbt:Math dbt:More_citations_needed dbt:Mvar dbt:Reflist dbt:See_also dbt:Short_description dbt:Use_dmy_dates dbt:Isbn
dcterms:subject dbc:Lossless_compression_algorithms dbc:1952_in_computing dbc:Binary_trees
gold:hypernym dbr:Type
rdf:type owl:Thing yago:WikicatCompressionAlgorithms yago:WikicatLosslessCompressionAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932
rdfs:comment في نظرية المعلومات والمعلوماتية، ترميز هوفمان (بالإنجليزية: Huffman coding)‏ يعتبر من ترميز انتروبي يستخدم في الضغط غير الفاقد للبيانات، حيث يعتمد على ترميز متغير الطول لرموز المصدر بما يتناسب مع احتمال ظهورها.طور ديفيد هوفمان هذا الترميز عندما كان طالب دكتوراه في جامعة MIT ونشره عام 1952 في ورقة بحث بعنوان A Method for the Construction of Minimum-Redundancy Codes (طريقة إنشاء ترميز بفائض أصغري). (ar) Η κωδικοποίηση Χούφμαν είναι μια μέθοδος συμπίεσης που δημοσιεύτηκε το 1952 από τον και έμελλε να γίνει πασίγνωστη. Εκδοχές του αλγορίθμου Χούφμαν χρησιμοποιούνται στη μετάδοση αντιγράφων και στις απεικονίσεις εγγράφων. Το πρότυπο JPEG ενσωματώνει την κωδικοποίηση Χούφμαν ως τελικό βήμα στη διαδικασία συμπίεσης εικόνας. Η κωδικοποίηση Χούφμαν αποδεικνύεται βέλτιστη για ένα δεδομένο κείμενο, αν και ο πίνακας κωδικοποίησης πρέπει να μεταδίδεται μαζί με τα δεδομένα. (el) Die Huffman-Kodierung ist eine Form der Entropiekodierung, die 1952 von David A. Huffman entwickelt und in der Abhandlung A Method for the Construction of Minimum-Redundancy Codes publiziert wurde. Sie ordnet einer festen Anzahl an Quellsymbolen jeweils Codewörter mit variabler Länge zu. In der Informationstechnik ist sie ein Präfixcode, der üblicherweise für verlustfreie Kompression benutzt wird. Wie bei anderen Entropiekodierungen werden häufiger vorkommende Zeichen mit weniger Bits repräsentiert als seltener vorkommende Zeichen. (de) Huffman kodifikazioa algoritmo bat da, konputazio-zientzia eta informazioaren teorian erabiltzen dena datuen konpresiorako. oinarritzen den metodo bat da, agertzen diren sinbolo edo karaktereen maiztasunaren arabera, hauei kode zehatz bat esleitzeko erabiltzen dena. David A. Huffmanek garatutako metodo bat da, MITen doktoretza gauzatzen zuen bitartean garatutakoa. Hau A Method for the Construction of Minimum-Redundancy Codes delako artikuluan argitaratu zen. (eu) ハフマン符号（ハフマンふごう、英: Huffman coding）とは、1952年にデビッド・ハフマンによって開発された符号で、文字列をはじめとするデータの可逆圧縮などに使用される。 ほかのエントロピー符号と同様、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることで、メッセージ全体の符号化に使われるデータ量を削減することを狙っている。 コンパクト符号やエントロピー符号の一つ。JPEGやZIP (Deflate) などの圧縮フォーマットで使用されている。 シャノン符号化が最適ではない場合が存在する不完全な符号であったのに対し、ハフマン符号は（整数の符号語長という制約のもとでは、）常に最適な符号を構成できる。擬似的に実数の符号語長を割り振る算術符号と比較すれば、データ圧縮効率は劣る。ただし、算術符号やその他の高効率の符号化法と異なり、特許の問題が無い。 (ja) Kodowanie Huffmana (ang. Huffman coding) – jedna z najprostszych i łatwych w implementacji metod kompresji bezstratnej. Została opracowana w 1952 roku przez Amerykanina Davida Huffmana. Algorytm Huffmana nie należy do najefektywniejszych obliczeniowo systemów bezstratnej kompresji danych, dlatego też praktycznie nie używa się go samodzielnie. Często wykorzystuje się go jako ostatni etap w różnych systemach kompresji, zarówno bezstratnej, jak i stratnej, np. MP3 lub JPEG. Pomimo że nie jest doskonały, stosuje się go ze względu na prostotę oraz brak ograniczeń patentowych. Jest to przykład wykorzystania algorytmu zachłannego. (pl) 霍夫曼編碼（英語：Huffman Coding），又譯為哈夫曼编码、赫夫曼编码，是一種用於无损数据压缩的熵編碼（權編碼）演算法。由美國計算機科學家大衛·霍夫曼（David Albert Huffman）在1952年發明。 (zh) A ciències de la computació i teoria de la informació, la codificació Huffman és un algorisme utilitzat per compressió de dades. El terme es refereix a l'ús d'una taula de codis de longitud variable per a codificar un determinat símbol (com pot ser un caràcter en un fitxer), on la taula ha estat emplenada d'una manera específica basant-se en la probabilitat estimada d'aparició de cada possible valor d'aquest símbol. Va ser desenvolupat per David A. Huffman mentre era estudiant de doctorat en el MIT, i publicat a "A Method for the Construction of Minimum-Redundancy Codes". (ca) Huffmanovo kódování je algoritmus využívaný pro bezeztrátovou kompresi dat. Konvertuje znaky vstupního souboru do bitových řetězců různé délky. Znaky, které se ve vstupním souboru vyskytují nejčastěji, jsou konvertovány do bitových řetězců s nejkratší délkou (nejfrekventovanější znak tak může být konvertován do jediného bitu), zatímco znaky, které se vyskytují velmi zřídka, jsou konvertovány do delších řetězců (mohou být i delší než 8 bitů). Dekomprese naopak pomocí rekonstruovaného binárního stromu dekóduje řetězce proměnlivé délky. (cs) In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes". (en) En ciencias de la computación y teoría de la información, la codificación Huffman es un algoritmo usado para compresión de datos. El término se refiere al uso de una tabla de códigos de longitud variable para codificar un determinado símbolo (como puede ser un carácter en un archivo), donde la tabla ha sido rellenada de una manera específica basándose en la probabilidad estimada de aparición de cada posible valor de dicho símbolo. Fue desarrollado por David A. Huffman mientras era estudiante de doctorado en el MIT, y publicado en "A Method for the Construction of Minimum-Redundancy Codes". (es) Dalam ilmu komputer dan teori informasi, Huffman coding adalah sebuah tipe code yang optimal yang biasanya digunakan untuk lossless data compression. Algoritme Huffman Coding ditemukan oleh David A. Huffman pada saat ia masih seorang mahasiswa di MIT, ia menerbitkan karyanya pada tahun 1952 yang berjudul "A Method for the Construction of Minimum Redundancy Codes". (in) Le codage de Huffman est un algorithme de compression de données sans perte. Le codage de Huffman utilise un code à longueur variable pour représenter un symbole de la source (par exemple un caractère dans un fichier). Le code est déterminé à partir d'une estimation des probabilités d'apparition des symboles de source, un code court étant associé aux symboles de source les plus fréquents. Il a été inventé par David Albert Huffman, et publié en 1952. (fr) Nella teoria dell'informazione, per codifica di Huffman si intende un algoritmo di codifica dei simboli usato per la compressione di dati, basato sul principio di trovare il sistema ottimale per codificare stringhe basato sulla frequenza relativa di ciascun carattere. Essa è stata sviluppata nel 1952 da David A. Huffman, uno studente dottorando presso il MIT, e pubblicata su A Method for the Construction of Minimum-Redundancy Codes (lett. "Un metodo per la costruzione di codici a ridondanza minima"). (it) 전산학과 정보 이론에서 허프먼 부호화(Huffman coding)는 무손실 압축에 쓰이는 엔트로피 부호화의 일종으로, 데이터 문자의 등장 빈도에 따라서 다른 길이의 부호를 사용하는 알고리즘이다. 1952년 당시 박사과정 학생이던 이 《A Method for the Construction of Minimum-Redundancy Codes》란 제목의 논문으로 처음 발표했다. 허프먼 부호화는 문자들의 빈도로부터 (어떤 한 문자에 대한 부호가 다른 부호들의 접두어가 되지 않는 부호)를 만들어 내는 알고리즘으로, 적게 나오는 문자일수록 더 긴 부호를 쓰고 많이 나올수록 더 짧은 부호를 쓴다. 허프먼 부호화는 주어진 빈도에 대해서 항상 최적의 접두 부호를 만들어 내며, 이 과정은 빈도가 정렬되어 있을 경우 O(n)만에 가능하다. 각 문자들의 빈도가 2의 거듭제곱 꼴이거나 모두 같을 경우 이 접두 부호는 간단한 이진 블록 부호와 동일하다. 위에서 아래로 진행하는 샤논파노방법과는 달리 허프먼 알고리즘의 부호화 순서는 아래에서 위로 진행한다. (ko) Huffmancodering is een methode om gegevens die bestaan uit een rij van symbolen, optimaal en verliesloos te comprimeren. De codering wordt onder andere toegepast bij datacommunicatie en voor . Huffmancodering is vernoemd naar David Huffman, die de codering in 1952 voor het eerst beschreef. Het principe van huffmancodering is eenvoudig. Van een reeks symbolen worden de veel voorkomende symbolen weergegeven door een kortere code, dan de weinig voorkomende. Zo kan de hele reeks op een kortere manier gecodeerd worden. (nl) A codificação de Huffman é um método de compressão que usa as probabilidades de ocorrência dos símbolos no conjunto de dados a ser comprimido para determinar códigos de tamanho variável para cada símbolo. Ele foi desenvolvido em 1952 por David A. Huffman que era, na época, estudante de doutorado no MIT, e foi publicado no artigo "A Method for the Construction of Minimum-Redundancy Codes". (pt) Huffmankodning är en datakomprimeringsalgoritm uppfunnen 1952 av doktoranden . I Huffmankodning byts sekvenser av symboler av fix längd entydigt ut mot andra sekvenser av tecken och koder av olika längd beroende på symbolens relativa frekvens. Relativ frekvens kan ses som sannolikheten att en viss symbol ska sändas.Ofta förekommande symboler ges kortare koder än sällan förekommande, så att den totala kodsekvensen blir så kort som möjligt.Det finns två metoder för att uppskatta den relativa frekvensen för symbolerna: En algoritm för att finna en binär (statisk) Huffmankodning är den följande: (sv) Алгоритм Хаффмана — жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных. В отличие от алгоритма Шеннона — Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m2 с более чем двумя символами. Этот метод кодирования состоит из двух основных этапов: (ru) Алгоритм Гаффмана (або коди Гафмена) — адаптивний жадібний алгоритм оптимального префіксного кодування алфавіту з мінімальною надмірністю. Був розроблений аспірантом Массачусетського технологічного інституту Девідом Гаффманом при написанні ним курсової роботи та надрукований в статті 1952 року «A Method for the Construction of Minimum-Redundancy Codes». В даний час[коли?] використовується в багатьох програмах стиснення даних без втрат. На відміну від алгоритму Шеннона — Фано, алгоритм Гаффмана залишається завжди оптимальним і для m2 з більш ніж двома символами. (uk)
rdfs:label ترميز هوفمان (ar) Codificació de Huffman (ca) Huffmanovo kódování (cs) Huffman-Kodierung (de) Κωδικοποίηση Χούφμαν (el) Codificación Huffman (es) Huffman kodifikazio (eu) Pengodean Huffman (in) Huffman coding (en) Codage de Huffman (fr) Codifica di Huffman (it) 허프먼 부호화 (ko) ハフマン符号 (ja) Huffmancodering (nl) Kodowanie Huffmana (pl) Codificação de Huffman (pt) Huffmankodning (sv) Код Хаффмана (ru) 霍夫曼编码 (zh) Код Гаффмана (uk)
rdfs:seeAlso dbr:Arithmetic_coding
owl:sameAs freebase:Huffman coding yago-res:Huffman coding wikidata:Huffman coding dbpedia-ar:Huffman coding dbpedia-az:Huffman coding dbpedia-ca:Huffman coding dbpedia-cs:Huffman coding dbpedia-da:Huffman coding dbpedia-de:Huffman coding dbpedia-el:Huffman coding dbpedia-es:Huffman coding dbpedia-et:Huffman coding dbpedia-eu:Huffman coding dbpedia-fa:Huffman coding dbpedia-fi:Huffman coding dbpedia-fr:Huffman coding dbpedia-he:Huffman coding dbpedia-hu:Huffman coding dbpedia-id:Huffman coding dbpedia-it:Huffman coding dbpedia-ja:Huffman coding dbpedia-ka:Huffman coding dbpedia-ko:Huffman coding dbpedia-lmo:Huffman coding http://ml.dbpedia.org/resource/ഹഫ്‌മാൻ_കോഡിങ് dbpedia-nl:Huffman coding dbpedia-no:Huffman coding dbpedia-pl:Huffman coding dbpedia-pt:Huffman coding dbpedia-ru:Huffman coding dbpedia-sr:Huffman coding dbpedia-sv:Huffman coding dbpedia-th:Huffman coding dbpedia-tr:Huffman coding dbpedia-uk:Huffman coding dbpedia-vi:Huffman coding dbpedia-zh:Huffman coding https://global.dbpedia.org/id/2UhRx
prov:wasDerivedFrom wikipedia-en:Huffman_coding?oldid=1117474402&ns=0
foaf:depiction wiki-commons:Special:FilePath/HuffmanCodeAlg.png wiki-commons:Special:FilePath/Huffman_coding_example.svg wiki-commons:Special:FilePath/Huffman_coding_visualisation.svg wiki-commons:Special:FilePath/Huffman_tree_2.svg
foaf:isPrimaryTopicOf wikipedia-en:Huffman_coding
is dbo:knownFor of dbr:David_A._Huffman
is dbo:wikiPageDisambiguates of dbr:Huffman
is dbo:wikiPageRedirects of dbr:Applications_of_Huffman_coding dbr:Alphabetic_Huffman_coding dbr:Alphabetic_Huffman_tree dbr:Data_compression/Huffman_coding dbr:Hu-Tucker_coding dbr:Fixed-length_Huffman_code dbr:Limited-length_Huffman_code dbr:Huffman_Coding dbr:Huffmann_decoding dbr:Length-limited_Huffman_code dbr:Length-limited_Huffman_coding dbr:Hoffman_coding dbr:Minimum_variance_Huffman_code dbr:Minimum_variance_Huffman_coding dbr:Hu-Tucker dbr:Huffman's_algorithm dbr:Huffman-Shannon-Fano_coding dbr:Huffman_Code dbr:Huffman_Compression dbr:Huffman_Compression_algorithm dbr:Huffman_Decoding dbr:Huffman_Encoding dbr:Huffman_algorithm dbr:Huffman_code dbr:Huffman_codes dbr:Huffman_encoding dbr:Huffman_tree dbr:Huffmann_code dbr:Huffmann_coding dbr:Huffmann_encoding dbr:Huffman’s_algorithm dbr:Hufman_coding dbr:Hufman_encoding dbr:Static_Huffman_coding dbr:Coding_tree dbr:K-ary_Huffman_coding dbr:K-ary_Huffman_encoding dbr:K-ary_Hufman_encoding
is dbo:wikiPageWikiLink of dbr:Entropy_coding dbr:List_of_University_of_California,_Santa_Cruz_people dbr:List_of_algorithms dbr:List_of_amateur_radio_modes dbr:List_of_binary_codes dbr:List_of_computer_scientists dbr:MIT_Electrical_Engineering_and_Computer_Science_Department dbr:Binary_tree dbr:David_A._Huffman dbr:Algorithm dbr:Arabic_letter_frequency dbr:List_of_archive_formats dbr:List_of_important_publications_in_theoretical_computer_science dbr:List_of_pioneers_in_computer_science dbr:Perl dbr:DNA_database dbr:Video_Acceleration_API dbr:Deflate dbr:Index_of_information_theory_articles dbr:Inductive_probability dbr:Intel_Management_Engine dbr:Letter_frequency dbr:List_of_programmers dbr:Lossless_JPEG dbr:Comparison_of_video_codecs dbr:CrypTool dbr:Rzip dbr:General-purpose_computing_on_graphics_processing_units dbr:Timeline_of_algorithms dbr:Timeline_of_information_theory dbr:Entropy_(information_theory) dbr:Freeview_(New_Zealand) dbr:Musepack dbr:Constant_bitrate dbr:Convention_over_Code dbr:Photo_CD dbr:Range_query_(data_structures) dbr:Applications_of_Huffman_coding dbr:Arithmetic_coding dbr:Alphabetic_Huffman_coding dbr:Alphabetic_Huffman_tree dbr:Alphabetic_code dbr:Libjpeg dbr:Lossless_compression dbr:MPEG-1 dbr:Comma_code dbr:Comparison_of_Direct_Connect_software dbr:Comparison_of_graphics_file_formats dbr:Comparison_of_instruction_set_architectures dbr:Compression_of_genomic_sequencing_data dbr:Computer_chess dbr:Zlib dbr:Zstd dbr:Fax dbr:Data_compression/Huffman_coding dbr:Pack_(compression) dbr:Priority_queue dbr:Hu-Tucker_coding dbr:BMP_file_format dbr:Brotli dbr:Bzip2 dbr:Adaptive_Binary_Optimization dbr:Adaptive_Huffman_coding dbr:Data_compression dbr:WebP dbr:Windows_Media_Audio dbr:Garsia–Wachs_algorithm dbr:Package-merge_algorithm dbr:7z dbr:Normal_number dbr:Dichotomic_search dbr:Dictionary_coder dbr:DigiCipher_2 dbr:DirectX_Video_Acceleration dbr:Graph_(abstract_data_type) dbr:Graphics_processing_unit dbr:Lempel–Ziv–Stac dbr:Lempel–Ziv–Storer–Szymanski dbr:Lempel–Ziv–Welch dbr:List_of_Intel_graphics_processing_units dbr:List_of_Massachusetts_Institute_of_Technology_alumni dbr:Wedderburn–Etherington_number dbr:Prefix_code dbr:Radix_tree dbr:Gzip dbr:H.262/MPEG-2_Part_2 dbr:H.263 dbr:Asymmetric_numeral_systems dbr:Isaak_Yaglom dbr:JPEG dbr:JPEG_XL dbr:Fixed-length_Huffman_code dbr:ARC_(file_format) dbr:LHA_(file_format) dbr:LZ4_(compression_algorithm) dbr:LZ77_and_LZ78 dbr:Bit_array dbr:TIFF dbr:Code dbr:JSONP dbr:Tunstall_coding dbr:Mod_deflate dbr:Modified_Huffman_coding dbr:August_9 dbr:CRAM_(file_format) dbr:Pngcrush dbr:Portable_Network_Graphics dbr:Greedy_algorithm dbr:Huffman_(surname) dbr:Huffyuv dbr:Id_Tech_3 dbr:Image_segmentation dbr:Indeo dbr:Kullback–Leibler_divergence dbr:OpenEXR dbr:Huffman dbr:SQ_(program) dbr:Universal_code_(data_compression) dbr:Variable-length_code dbr:Image_compression dbr:Limited-length_Huffman_code dbr:Smacker_video dbr:X-Video_Motion_Compensation dbr:Huffman_Coding dbr:Huffmann_decoding dbr:Shannon–Fano_coding dbr:Node-to-node_data_transfer dbr:Length-limited_Huffman_code dbr:Length-limited_Huffman_coding dbr:Shannon_coding dbr:Range_coding dbr:Word2vec dbr:Hoffman_coding dbr:Minimum_variance_Huffman_code dbr:Minimum_variance_Huffman_coding dbr:Hu-Tucker dbr:Huffman's_algorithm dbr:Huffman-Shannon-Fano_coding dbr:Huffman_Code dbr:Huffman_Compression dbr:Huffman_Compression_algorithm dbr:Huffman_Decoding dbr:Huffman_Encoding dbr:Huffman_algorithm dbr:Huffman_code dbr:Huffman_codes dbr:Huffman_encoding dbr:Huffman_tree dbr:Huffmann_code dbr:Huffmann_coding dbr:Huffmann_encoding dbr:Huffman’s_algorithm dbr:Hufman_coding dbr:Hufman_encoding dbr:Static_Huffman_coding dbr:Coding_tree dbr:K-ary_Huffman_coding dbr:K-ary_Huffman_encoding dbr:K-ary_Hufman_encoding
is dbp:knownFor of dbr:David_A._Huffman
is rdfs:seeAlso of dbr:Morse_code
is foaf:primaryTopic of wikipedia-en:Huffman_coding