Введение
Алгоритмы сжатия данных
В области сжатия данных кодирование Шеннона — Фано, названное в честь Клода Шеннона и Роберта Фано, является одним из двух связанных методов построения префиксного кода на основе набора символов и их вероятностей (оцененных или измеренных). Метод Шеннона выбирает префиксный код, в котором исходному символу присваивается длина кодового слова. Один из распространенных способов выбора кодовых слов использует двоичное представление кумулятивных вероятностей. Этот метод был предложен в статье Шеннона «Математическая теория связи» (1948), в которой он представил область теории информации. Метод Фано делит символы источника на два набора («0» и «1») с вероятностями, максимально близкими к 1/2. Затем эти наборы делятся пополам, и так далее, пока каждый набор не будет содержать только один символ. Кодовым словом для этого символа является строка из «0» и «1», которая фиксирует, на какую половину деления он попал. Этот метод был предложен в более позднем (опубликованном) техническом отчете Фано (1949). Коды Шеннона — Фано неоптимальны в том смысле, что они не всегда достигают минимальной возможной ожидаемой длины кодового слова, как это делает кодирование Хаффмана. Однако ожидаемая длина кодового слова у кодов Шеннона — Фано отличается от оптимальной не более чем на 1 бит. Метод Фано обычно обеспечивает кодирование с более короткими ожидаемыми длинами, чем метод Шеннона. Однако метод Шеннона легче анализировать теоретически. Кодирование Шеннона — Фано не следует путать с кодированием Шеннона — Фано — Элиаса (также известным как кодирование Элиаса), которое является предшественником арифметического кодирования.
In the field of data compression, Shannon–Fano coding, named after Claude Shannon and Robert Fano, is one of two related techniques for constructing a prefix code based on a set of symbols and their probabilities (estimated or measured). Shannon's method chooses a prefix code where a source symbol is given the codeword length One common way of choosing the codewords uses the binary expansion of the cumulative probabilities. This method was proposed in Shannon's "A Mathematical Theory of Communication" (1948), his article introducing the field of information theory. Fano's method divides the source symbols into two sets ("0" and "1") with probabilities as close to 1/2 as possible. Then those sets are themselves divided in two, and so on, until each set contains only one symbol. The codeword for that symbol is the string of "0"s and "1"s that records which half of the divides it fell on. This method was proposed in a later (in print) technical report by Fano (1949). Shannon–Fano codes are suboptimal in the sense that they do not always achieve the lowest possible expected codeword length, as Huffman coding does. However, Shannon–Fano codes have an expected codeword length within 1 bit of optimal. Fano's method usually produces encoding with shorter expected lengths than Shannon's method. However, Shannon's method is easier to analyse theoretically. Shannon–Fano coding should not be confused with Shannon–Fano–Elias coding (also known as Elias coding), the precursor to arithmetic coding.
Именование
Что касается путаницы с двумя различными кодами, именуемыми одним и тем же названием, Krajči et al. пишут:
Около 1948 года Клод Э. Шеннон (1948) и Роберт М. Фано (1949) независимо друг от друга предложили два различных алгоритма кодирования источника для эффективного описания дискретного источника без памяти. К сожалению, несмотря на то, что они различны, обе схемы стали известны под одним и тем же названием – кодирование Шеннона–Фано. Существует несколько причин для этой путаницы. Во-первых, в обсуждении своей схемы кодирования Шеннон упоминает схему Фано и называет ее «по существу одинаковой» (Шеннон, 1948, с. 17 [переиздание]). Во-вторых, схемы кодирования Шеннона и Фано схожи в том смысле, что обе являются эффективными, но не оптимальными префиксными кодами с сопоставимой производительностью. Метод Шеннона (1948), использующий заранее заданные длины слов, называется кодированием Шеннона–Фано у Ковера и Томаса, Голди и Пинча, Джонса и Джонса, а также Хана и Кобаяси. Йенг называет его кодированием Шеннона. Метод Фано (1949), использующий двоичное деление вероятностей, называется кодированием Шеннона–Фано у Соломона и Гупты. Krajči et al. называют его кодированием Фано.
Around 1948, both Claude E. Shannon (1948) and Robert M. Fano (1949) independently proposed two different source coding algorithms for an efficient description of a discrete memoryless source. Unfortunately, in spite of being different, both schemes became known under the same name Shannon–Fano coding. There are several reasons for this mixup. For one thing, in the discussion of his coding scheme, Shannon mentions Fano’s scheme and calls it “substantially the same” (Shannon, 1948, p. 17 [reprint]). For another, both Shannon’s and Fano’s coding schemes are similar in the sense that they both are efficient, but suboptimal prefix free coding schemes with a similar performance. Shannon's (1948) method, using predefined word lengths, is called Shannon–Fano coding by Cover and Thomas, Goldie and Pinch, Jones and Jones, and Han and Kobayashi. It is called Shannon coding by Yeung. Fano's (1949) method, using binary division of probabilities, is called Shannon–Fano coding by Salomon and Gupta. It is called Fano coding by Krajči et al.
Дерево Шеннон-Фано
Дерево Шеннона — Фано строится в соответствии со спецификацией, предназначенной для определения эффективной таблицы кодов. Сам алгоритм прост:
Для заданного списка символов разработайте соответствующий список вероятностей или подсчет частот, чтобы была известна относительная частота появления каждого символа. Отсортируйте список символов по частоте, поместив наиболее часто встречающиеся символы слева, а наименее распространенные — справа. Разделите список на две части так, чтобы суммарная частота левой части была максимально близка к суммарной частоте правой части. Левой части списка присваивается двоичная цифра 0, а правой части — цифра 1. Это означает, что коды символов в первой части будут начинаться с 0, а коды во второй части — с 1. Рекурсивно применяйте шаги 3 и 4 к каждой из двух полученных половин, подразделяя группы и добавляя биты к кодам, пока каждый символ не станет соответствующим листом кода на дереве.