Хаффман Кодирует введение
Кодирование Хаффмана имеет дело с задачей символов кодирования и бинарным, соответствующим символам, которые делятся на кодирование и декодирование, с целью сжатия длина двоичных данных, соответствующей символам. Мы знаем, что когда персонажи хранятся и передаются, они двоичные (компьютер знает только 0/1), поэтому между символами и бинарным языком существуют отношения отображения. Персонажи принадлежат к набору символов (Charset). Персонажи должны храниться и передаваться в двоичном коде. При отображении их необходимо декодировать обратно к персонажам. Методы набора символов и кодировки-это отношения от одного ко многим (Unicode может быть кодирован с UTF-8, UTF-16 и т. Д.). После понимания набора персонажей, кодирования и декодирования проблема искаженного кода, летящего по всему небу, может быть легко решена. Принимая строчную Английскую букву в качестве примера в кодировании ASCII, десятичный десятичный цвет составляет 97, а бинар - 01100001. Каждый персонаж в ASCII кодируется с 8 битами (1 лаб). Если нужно передавать 1000 символов, то необходимо передавать 8000 бит. Проблема заключается в том, что частота использования буквы E на английском языке составляет 12,702%, в то время как Z составляет 0,074%. Первый более чем в 100 раз больше, чем у последнего, но он использует бинарку с одинаковыми цифрами. Это может быть сделано лучше, метод является кодировкой переменной длины. Руководящий принцип состоит в том, чтобы кодировать более высокую частоту с более короткими цифрами и с низкой частотой с более длинными цифрами. Алгоритм кодирования Хаффмана касается таких проблем.
Huffman, кодируя реализацию Java
Структуры данных, в основном используемые алгоритмом кодирования Хаффмана, являются полными двоичными деревьями и приоритетными очередями. Последний использует java.util.priorityqueue, а первое реализует себя (все это внутренние классы). Код заключается в следующем:
Статическое дерево классов {частный узел корень; public node getRoot () {return root; } public void setroot (node root) {this.root = root; }} Статический узел класса реализует сопоставимые <node> {private String chars = ""; частная частота = 0; Частный узел родитель; частный узел LeftNode; Приватный узел RightNode; @Override public int compareto (node n) {return Частота - n.frequency; } public boolean isleaf () {return chars.length () == 1; } public boolean isroot () {return parent == null; } public boolean isleftchild () {return parent! = null && this == parent.leftnode; } public int getFrequence () {return Частота; } public void setFrequence (int -частота) {this.frequency = частота; } public String getChars () {return chars; } public void setChars (String chars) {this.Chars = chars; } public node getParent () {return parent; } public void setParent (node parent) {this.parent = parent; } public node getleftnode () {return leftnode; } public void setleftNode (node leftnode) {this.leftnode = LealthNode; } public node getrightNode () {return rightNode; } public void setrightNode (node rightnode) {this.rightnode = rightnode; }} Статистика
Поскольку таблица кодирования должна быть расположена в соответствии с частотой, конечно, вы должны получить статистическую информацию частоты. Я реализовал метод для решения такой проблемы. Если уже есть статистика, то преобразуйте в карту <символ, целое число>. Если информация, которую вы получаете, составляет процент, умножьте на 100 или 1000 или 10000. Она всегда может быть преобразована в целое число. Например, 12,702%, умноженные на 1000 - это 12702, а Хаффман кодирует только проблемы с размерами. Статистический метод реализован следующим образом:
Общественная статическая карта <символ, целое число> статистика (char [] chararray) {map <символ, целое число> map = new hashmap <символ, Integer> (); for (charc c: chararray) {символ персонажа = новый символ (c); if (map.containskey (символ)) {map.put (символ, map.get (символ) + 1); } else {map.put (символ, 1); }} return Map; } Строительство дерева
Построение дерева является основным шагом в алгоритме кодирования Хаффмана. Идея состоит в том, чтобы повесить все символы на листовом узле полностью бинарного дерева, а частота левого узла любого нестраничного дочернего узла не появляется больше, чем правый узел. Алгоритм преобразует статистику в узлы и хранит их в приоритетной очереди. Каждый раз, когда из очереди появляется два узла с минимальной частотой, строится новый родительский узел (нелистный узел). Сумма двух узлов, содержимое персонажа, просто появляется, и частота также является их суммой. Первое всплывающее окно используется в качестве левого дочернего узла, а следующий используется в качестве правого дочернего узла, а недавно сконструированный родительский узел помещается в очередь. Повторите приведенные выше действия n-1 раз, n-это количество разных символов (число в очереди уменьшается на 1 каждый раз). Завершите вышеуказанные шаги, в очереди остается узел, и корневой узел дерева появляется. Код заключается в следующем:
Частное статическое дерево Buildtree (map <символ, целое число> статистика, список <узел> листья) {символ [] keys = statistics.keyset (). toarray (новый символ [0]); Приоритет quiewue <node> privationQueue = new DrivetoryQueue <node> (); for (символ символов: keys) {node node = new Node (); node.chars = parment.tostring (); node.frequency = statistics.get (символ); Приоритет листья. Адд (узел); } int size = privationqueue.size (); for (int i = 1; i <= size - 1; i ++) {node node1 = privationqueue.poll (); Node node2 = privationQueue.poll (); Node sumnode = new Node (); sumnode.chars = node1.chars + node2.chars; sumnode.fretency = node1.fraquence + node2.fraquence; sumnode.leftnode = node1; sumnode.rightnode = node2; node1.parent = sumnode; node2.parent = sumnode; Приоритет } Дерево дерева = новое дерево (); tree.root = priorityqueue.poll (); возвращение дерева; } кодирование
Соответствующее кодирование символа состоит в том, чтобы искать в листовом узле, где находится символ. Если узел символов является левым узлом родительского узла, добавьте 0 перед кодируемым символом, в противном случае, если это правый узел, добавьте 1 до корневого узла. До тех пор, пока взаимосвязь между символами и бинарным кодом получена, кодирование очень проста. Код заключается в следующем:
public Static String Encode (String OriginalStr, Map <символ, Integer> Statistics) {if (OriginalStr == null || OriginalStr.Equals ("")) {return ""; } char [] chararray = OriginalStr.toChararray (); Список <node> Leafnodes = new ArrayList <node> (); Buildtree (статистика, листовые досы); Карта <символ, string> encodinfo = buildencodinginfo (листья); StringBuffer Buffer = new StringBuffer (); для (char c: chararray) {символ символа = новый символ (c); buffer.append (encodinfo.get (символ)); } return buffer.toString (); } частная статическая карта <символ, строка> buildencodinginfo (list <node> leafnodes) {map <символ, строка> кодовыечия = new hashmap <символ, string> (); for (Node Leafnodes: Leafnodes) {символ символа = новый символ (Leafnode.getChars (). Charat (0)); String codeword = ""; Node CurrentNode = Leafnode; do {if (currentnode.isleftchild ()) {codeword = "0" + codeadord; } else {codeword = "1" + codeadord; } currentNode = currentNode.parent; } while (currentNode.parent! = null); Codeadords.put (символ, кодовой код); } вернуть кодовые слова; } декодирование
Поскольку алгоритм кодирования Хаффмана может гарантировать, что любой бинарный код не будет префиксом другого кода, декодирование очень проста. Выберите каждый бинарную последовательность, поищите вниз по корне дерева, 1 справа, 0 влево, достигните узел листа (удар), вернитесь к корневому узлу и продолжайте повторять вышеуказанные действия. Код заключается в следующем:
Общедоступная статическая строковая декод (String binarystr, map <символ, integer> statistics) {if (binarystr == null || binarystr.equals ("")) {return ""; } char [] binaryCharraray = binaryStr.toChararray (); LinkedList <marly> binaryList = new LinkedList <Carment> (); int size = binaryCharrary.length; for (int i = 0; i <size; i ++) {binarylist.addlast (новый символ (BinaryCharraray [i])); } List <node> leafnodes = new ArrayList <node> (); Дерево дерева = Buildtree (статистика, листовые досы); StringBuffer Buffer = new StringBuffer (); while (binarylist.size ()> 0) {node node = tree.root; do {символ c = binarylist.removefirst (); if (c.charvalue () == '0') {node = node.leftNode; } else {node = node.rightNode; }} while (! node.isleaf ()); buffer.append (node.chars); } return buffer.toString (); } Тест и сравнение
Следующие тесты на правильность кодирования Хаффмана (сначала кодируются, затем декодированы, включая китайский), и сравнение Хаффмана, кодирующего с общими символами, кодирующими бинарные строки. Код заключается в следующем:
Public Static void Main (String [] args) {String oristr = "Коды Huffman сдатывают данные очень эффективно: экономия от 20% до 90% типична" + "в зависимости от характеристик сжатых данных. Рост Китая"; Карта <символ, целое число> статистика = статистика (oristr.thararray ()); String oncodedbinaristr = encode (oristr, statistics); String decodedstr = decode (oncodedbinaristr, statistics); System.out.println ("Original String:" + oristr); System.out.println ("Huffman Encoed Бинарная строка:" + oncodedbinaristr); System.out.println ("Декодированная строка из Binariy String:" + decodedstr); System.out.println («двоичная строка UTF-8:" + getStringofbyte (oristr, charset.forname ("utf-8"))); System.out.println («двоичная строка UTF-16:« + getStringofbyte (oristr, charset.forname ("UTF-16"))); System.out.println («двоичная строка US-ASCII:« + getStringofbyte (oristr, charset.forname ("us-assii"))); System.out.println («двоичная строка GB2312:« + getStringofbyte (oristr, charset.forname ("GB2312"))); } public Static String getStringOfByte (String Str, Charset charset) {if (str == null || str.equals ("")) {return ""; } byte [] bytearray = str.getbytes (charset); int size = bytearray.length; StringBuffer Buffer = new StringBuffer (); for (int i = 0; i <size; i ++) {byte temp = bytearray [i]; buffer.append (getstringofbyte (temp)); } return buffer.toString (); } public Static String getStringOfByte (byte b) {StringBuffer buffer = new StringBuffer (); for (int i = 7; i> = 0; i--) {byte temp = (byte) ((b >> i) & 0x1); buffer.append (string.valueof (temp)); } return buffer.toString (); }Выше всего содержание этой статьи. Я надеюсь, что это будет полезно для каждого обучения, и я надеюсь, что все будут поддерживать Wulin.com больше.