Предисловие
Я думаю, что друзья, которые изучали структуры данных, должны знать Хаффмана. Этот великий Бог изобрел знаменитое «оптимальное бинарное дерево». Чтобы ознаменовать его, мы называем это «Дерево Хаффман». Дерево Huffman можно использовать для кодировки Хаффмана, и знание кодирования очень великолепно, например, для сжатия, криптографии и т. Д. Давайте посмотрим на то, что является сегодня.
концепция
Конечно, одна из процедур заключается в том, что нам нужно понять некоторые основные концепции.
1. Длина пути: путь, который образует два узла из одного узла в дереве до другого узла. Количество ветвей на пути называется длиной пути.
2. Длина пути дерева: сумма длины пути от корня дерева до каждого узла. То, что мы называем полным двоичным деревом, - это самая короткая длина пути такого рода.
3. Длина взвешенного пути дерева: если взвешенное значение присваивается каждому листовому узлу дерева, длина взвешенного пути дерева равна сумме продукта длины пути от корневого узла до всех узлов листьев и веса листового узла.
Итак, как мы определим, является ли дерево оптимальным бинарным деревом? Давайте посмотрим на следующие деревья:
Их длины мощности:
WPL1: 7*2+5*2+2*2+4*2 = 36
WPL2: 7*3+5*3+2*1+4*2 = 46
WPL3: 7*1+5*2+2*3+4*3 = 35
Очевидно, что третье дерево имеет самый короткий вес (вы не верите в это, вы можете попробовать. Если вы можете найти более короткую, вы, вероятно, выиграете награду Тьюринга). Это то, что мы называем «оптимальным бинарным деревом (деревом хафман)». Его метод строительства очень прост. Вы выбираете узел с наименьшим весом и помещаете его в нижнюю часть дерева и помещаете два наименьших соединения в новый узел. Следует отметить, что вес образованного нового узла должен быть равен сумме весов этих двух узлов. Затем поместите этот новый узел обратно в узел, где нам нужно сформировать дерево, чтобы продолжить сортировку. Таким образом, все узлы с информацией, хранящиеся в дереве Хафман, находятся на листьях.
После завершения концепции я могу быть немного "неясным".
Давайте приведем пример, чтобы построить его четко.
Есть строка: aaaaaaaabbbbaaaacccccccdddddddfff
На первом шаге мы сначала подсчитываем количество раз, когда появляется каждый символ, и называем его весом персонажа. A 15, B 5, C 8, D 6, F 3.
Второй шаг - найти два символа с наименьшим весом, B5 и F3 и построить узел.
Затем удалите F3 и B5, теперь A15, C8, D6, FB8.
Шаг 3, повторите второй шаг, пока не будет построен только один узел.
Теперь это DFB14, A15, C8.
наконец,
Хорошо, так что наше дерево Хаффман построено.
Шаги по строительству
Согласно вышеуказанной логике, чтобы суммировать ее, есть несколько шагов:
1. Статистика Количество символов и символов, появляющихся в строке;
2. Создать узлы в соответствии со структурой первого шага;
3. Сортировать узел веса
4. Уберите два узла с наименьшим весом и генерируйте новый родительский узел;
5. Удалить два узла с наименьшим весом и хранить родительский узел в списке;
6. Повторите шаг 4 или 5, пока не останется узел;
7. Назначьте последний узел корневому узлу.
Код Java
Принцип закончен, и следующим шагом является реализация кода.
Во -первых, есть класс узлов для хранения данных.
пакет huffman;/** * class * @author yuxiu * */public class node {public String Code; // hafman Кодирование узла public int codeSize; // длина узла Huffman, кодируя публичные строковые данные; // узлы данных public int count; // weight node public node lChild; общественный узел RCHILD; public node () {} public node (String Data, int count) {this.data = data; this.count = count; } public node (int count, node lchild, node rchild) {this.count = count; this.lchild = lChild; this.rchild = rchild; } public node (строковые данные, int count, node lchild, node rchild) {this.data = data; this.count = count; this.lchild = lChild; this.rchild = rchild; }}Тогда существует процесс реализации.
Пакет Huffman; импорт java.io.*; import java.util.*; public class huffman {private string str; // первоначально используется для Compression private String newstr = ""; // Строка, соединенная Huffman, кодирующим частный корень узла; // root node of the huffman byrare private flag; // уже есть личные символы riate ratelist <straylist <straylist <straylist <straylist <straylist <stray live -lemelire; это тот же символ в той же положении частного ArrayList <node> Nodelist; // Очередь для хранения узлов 15 16/ ** * Создайте дерево Huffman * * @param str */ public void creathfmtree (String str) {this.str = str; charlist = new Arraylist <string> (); Nodelist = new ArrayList <node> (); // 1. Статистика Количество символов и символов, появляющихся в строке // Основная идея состоит в том, чтобы поместить неупорядоченную строку, такую как Ababccdebed в харст, который является AA, BBB, CC, DD, EE // и длина строки в списке - соответствующий вес для (int i = 0; i <str.length (); i ++) {gar ch = strat. // Установите флаг персонажа = true; for (int j = 0; j <charlist.size (); j ++) {if (charlist.get (j) .Charat (0) == CH) {// Если тот же символ найден string s = charlist.get (j)+ch; charlist.set (j, s); flag = false; перерыв; }} if (flag) {charlist.add (charlist.size (), ch + ""); }} // 2. Создать узел в соответствии со структурой первого шага для (int i = 0; i <charlist.size (); i ++) {String data = charlist.get (i) .charat (0)+""; // Получить первый символ каждой строки в charlist int count = charlist.get (i) .length (); // Длина строки в списке является соответствующим узлом узла веса = новый узел (Data, Count); // Создание узла объекта nodelist.add (i, node); // Присоединяйтесь к очереди узла} // 3. sort (Nodelist); while (nodelist.size ()> 1) {// Когда количество узлов больше одного // 4. Выберите два узла с наименьшим весом и генерируйте новый родительский узел // 5. Удалить два узла с наименьшим весом и хранить родительский узел в списке узла слева = nodelist.remove (0); Узел справа = nodelist.remove (0); int parentweight = left.count + right.count; // Вес родительского узла равен сумме весов детского узла узеля дочернего узла = новый узел (родительский вес, слева, справа); Nodelist.Add (0, Parent); // Поместите родительский узел в первую позицию} // 6. Повторите четвертые и пятые шаги, чтобы быть циклом while // 7. Назначьте последний узел к корневому узлу root = nodelist.get (0); } / ** * Приказы восходящего * * @param nodelist * / public void sort (arraylist <node> nodelist) {for (int i = 0; i <nodelist.size () - 1; i ++) {for (int j = i+1; j <nodelist.size (); j ++) {node temp; if (nodelist.get (i) .count> nodelist.get (j) .count) {temp = nodelist.get (i); nodelist.set (i, nodelist.get (j)); nodelist.set (j, temp); }}}} / ** * Traversal * * @param node * node * / public void output (node node) {if (node.lchild! = Null) {output (node.lchild); } System.out.print (node.count + ""); // in-order traversal if (node.rchild! = Null) {output (node.rchild); }} public void output () {output (root); }/** * Основной метод * * @param args */public static void main (string [] args) {huffman huff = new huffman (); // Создать объект Havalman huff.creathfmtree ("sdfassvvvdfgsfdfsdfs"); // Конструировать дерево}Суммировать
Выше всего посвящено реализации дерева Хаффмана на основе Java. Я надеюсь, что эта статья будет полезна всем, чтобы научиться использовать Java. Если у вас есть какие -либо вопросы, пожалуйста, оставьте сообщение для обсуждения.