Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Java программирование > Общие вопросы по Java, Java SE, Kotlin
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 05.12.2018, 17:18   #1
Katya_009
Пользователь
 
Регистрация: 05.12.2018
Сообщений: 16
По умолчанию Кодирование Хаффмана

Всем здравствуйте! Нужно реализовать кодирование Хаффмана и вывести построенное дереве, т.е. чтобы видно было что является корнем, что узлом. Сама реализация алгоритма есть, а вот как вывести дерево не понимаю вообще. Помогите пожалуйста, буду очень признательна)

Код:
import java.util.*;
 
abstract class HuffmanTree implements Comparable<HuffmanTree> {
    public final int frequency; // the frequency of this tree
    public HuffmanTree(int freq) { frequency = freq; }
 
    // compares on the frequency
    public int compareTo(HuffmanTree tree) {
        return frequency - tree.frequency;
    }
}
 
class HuffmanLeaf extends HuffmanTree {
    public final char value; // the character this leaf represents
 
    public HuffmanLeaf(int freq, char val) {
        super(freq);
        value = val;
    }
}
 
class HuffmanNode extends HuffmanTree {
    public final HuffmanTree left, right; // subtrees
 
    public HuffmanNode(HuffmanTree l, HuffmanTree r) {
        super(l.frequency + r.frequency);
        left = l;
        right = r;
    }
}
 
public class HuffmanCode {
    // input is an array of frequencies, indexed by character code
    public static HuffmanTree buildTree(int[] charFreqs) {
        PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>();
        // initially, we have a forest of leaves
        // one for each non-empty character
        for (int i = 0; i < charFreqs.length; i++)
            if (charFreqs[i] > 0)
                trees.offer(new HuffmanLeaf(charFreqs[i], (char)i));
 
        assert trees.size() > 0;
        // loop until there is only one tree left
        while (trees.size() > 1) {
            // two trees with least frequency
            HuffmanTree a = trees.poll();
            HuffmanTree b = trees.poll();
 
            // put into new node and re-insert into queue
            trees.offer(new HuffmanNode(a, b));
        }
        return trees.poll();
    }
 
    public static void printCodes(HuffmanTree tree, StringBuffer prefix) {
        assert tree != null;
        if (tree instanceof HuffmanLeaf) {
            HuffmanLeaf leaf = (HuffmanLeaf)tree;
 
            // print out character, frequency, and code for this leaf (which is just the prefix)
            System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + prefix);
 
        } else if (tree instanceof HuffmanNode) {
            HuffmanNode node = (HuffmanNode)tree;
 
            // traverse left
            prefix.append('0');
            printCodes(node.left, prefix);
            prefix.deleteCharAt(prefix.length()-1);
 
            // traverse right
            prefix.append('1');
            printCodes(node.right, prefix);
            prefix.deleteCharAt(prefix.length()-1);
        }
    }
 
    public static void main(String[] args) {
        String test = "this is an example for huffman encoding";
 
        // we will assume that all our characters will have
        // code less than 256, for simplicity
        int[] charFreqs = new int[256];
        // read each character and record the frequencies
        for (char c : test.toCharArray())
            charFreqs[c]++;
 
        // build tree
        HuffmanTree tree = buildTree(charFreqs);
 
        // print out results
        System.out.println("SYMBOL\tWEIGHT\tHUFFMAN CODE");
        printCodes(tree, new StringBuffer());
    }
}
______________________
Используйте тег [CODE] (кнопка с решеткой # в форме сообщения) при вставке кода на форум. Подробнее в FAQ

Последний раз редактировалось Alex11223; 05.12.2018 в 17:32.
Katya_009 вне форума Ответить с цитированием
Старый 05.12.2018, 17:36   #2
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

Так printCodes и делает практически задачу. Или вы не понимаете, что это за коды и что за дерево строится?
p51x вне форума Ответить с цитированием
Старый 05.12.2018, 19:12   #3
Katya_009
Пользователь
 
Регистрация: 05.12.2018
Сообщений: 16
По умолчанию

Да я не совсем понимаю по какому принципу символы из строки выводятся именно в таком порядке, это не совсем что нужно, потому что не понятно где листья, а где корни
Изображения
Тип файла: jpg Снимок.JPG (21.7 Кб, 55 просмотров)

Последний раз редактировалось Katya_009; 05.12.2018 в 20:33.
Katya_009 вне форума Ответить с цитированием
Старый 05.12.2018, 19:13   #4
Katya_009
Пользователь
 
Регистрация: 05.12.2018
Сообщений: 16
По умолчанию

Нужно наподобие такого вывода
Изображения
Тип файла: jpg Снимок2.JPG (12.8 Кб, 62 просмотров)
Katya_009 вне форума Ответить с цитированием
Старый 05.12.2018, 20:34   #5
Katya_009
Пользователь
 
Регистрация: 05.12.2018
Сообщений: 16
По умолчанию

Цитата:
Сообщение от p51x Посмотреть сообщение
Так printCodes и делает практически задачу. Или вы не понимаете, что это за коды и что за дерево строится?
Можете, пожалуйста, объяснить как printCodes строит дерево?
Katya_009 вне форума Ответить с цитированием
Старый 05.12.2018, 20:55   #6
Black Fregat
Программист
Участник клуба
 
Аватар для Black Fregat
 
Регистрация: 23.06.2009
Сообщений: 1,772
По умолчанию

Цитата:
Сообщение от Katya_009 Посмотреть сообщение
не понятно где листья, а где корни
Листья - это сами коды. И других листьев нет.
Корень один. По пути от корня к листьям на каждой единице вниз, на каждом нуле вверх
Верх примерно так будет выглядеть:
Код:
                +- 00000
             +--+
             |  +- 00001
          +--+
          |  +---- 0001
       +--+
       |  |  +---- 0010
       |  +--+
       |     |  +- 00110
    +--+     +--+
    |  |        +- 00111
Black Fregat вне форума Ответить с цитированием
Старый 05.12.2018, 21:22   #7
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

Цитата:
Сообщение от Katya_009 Посмотреть сообщение
Можете, пожалуйста, объяснить как printCodes строит дерево?
Никак. Засуньте хотя бы названия функций в переводчик.
p51x вне форума Ответить с цитированием
Старый 05.12.2018, 22:02   #8
Katya_009
Пользователь
 
Регистрация: 05.12.2018
Сообщений: 16
По умолчанию

Цитата:
Сообщение от Black Fregat Посмотреть сообщение
Листья - это сами коды. И других листьев нет.
Корень один. По пути от корня к листьям на каждой единице вниз, на каждом нуле вверх
Верх примерно так будет выглядеть:
Код:
                +- 00000
             +--+
             |  +- 00001
          +--+
          |  +---- 0001
       +--+
       |  |  +---- 0010
       |  +--+
       |     |  +- 00110
    +--+     +--+
    |  |        +- 00111
а как сделать такой иерархический вывод именно в консоли?
Katya_009 вне форума Ответить с цитированием
Старый 05.12.2018, 22:10   #9
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

Руками. Берете один из вариантов https://ru.wikipedia.org/wiki/%D0%9E...B5%D0%B2%D0%B0 , например, в ширину и строите - первый уровень - выводим элемент, дяльше несколько палочек туда-сюда и т.д.
p51x вне форума Ответить с цитированием
Старый 16.12.2018, 18:55   #10
Katya_009
Пользователь
 
Регистрация: 05.12.2018
Сообщений: 16
По умолчанию

Цитата:
Сообщение от Black Fregat Посмотреть сообщение
Листья - это сами коды. И других листьев нет.
Корень один. По пути от корня к листьям на каждой единице вниз, на каждом нуле вверх
Верх примерно так будет выглядеть:
Код:
                +- 00000
             +--+
             |  +- 00001
          +--+
          |  +---- 0001
       +--+
       |  |  +---- 0010
       |  +--+
       |     |  +- 00110
    +--+     +--+
    |  |        +- 00111

Здравствуйте я все с тем же алгоритмом Хаффмана) Можете, пожалуйста, показать в коде как сделать эти палочки для постороения такого дерева? Хотя бы для одного листа, думаю дальше по примеру разберусь, была бы очень признательна, спасибо)
Есть реализация более мне понятна, но все равно с трудом представляю как вывести в таком виде.
Код:
import java.io.File;
import java.io.FileNotFoundException;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;

public class Main {

    class Node implements Comparable<Node>{//узел

       final int sum;
       String code;

       void buildCode(String code) {
           this.code = code;
       }

       public Node(int sum){
           this.sum = sum;
       }

        @Override
        public int compareTo(Node o) {
           return Integer.compare(sum, o.sum);
        }
    }

    class InternalNode extends Node {//внутренний узел
        Node left;
        Node right;

        @Override
        void buildCode(String code) {
           super.buildCode(code);
           left.buildCode(code + "0");
           right.buildCode(code + "1");
        }

        public InternalNode (Node left, Node right) {
            super(left.sum+ right.sum);
            this.left = left;
            this.right = right;
        }
    }

    class LeafNode extends Node {//лист
        char symbol;

        @Override
        void buildCode(String code) {
            super.buildCode(code);
            System.out.println(symbol + ": " + code);
        }

        private LeafNode(char symbol, int count) {
            super(count);
            this.symbol = symbol;
        }
    }

    private void run() throws FileNotFoundException {
        Scanner input = new Scanner(new File("input.txt"));
        String s = input.next();
        Map<Character, Integer> count = new HashMap<>();
        for (int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (count.containsKey(c)){
                count.put(c, count.get(c) + 1);
            } else {
                count.put(c, 1);
            }
        }
        for (Map.Entry<Character, Integer> entry : count.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        Map<Character, Node> charNodes = new HashMap<>();
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(); //добавили в приоритетную очередь каждый листовой узел
        for (Map.Entry<Character, Integer> entry : count.entrySet()) {
            LeafNode node = (new LeafNode(entry.getKey(), entry.getValue()));
            charNodes.put(entry.getKey(), node);
            priorityQueue.add(node);
        }

        int sum = 0;
        while(priorityQueue.size() > 1) {
            Node first = priorityQueue.poll();
            Node second = priorityQueue.poll();
            InternalNode node = new InternalNode(first, second);
            sum += node.sum;
            priorityQueue.add(node);
        }
        System.out.println(count.size() + "  " + sum);
        Node root = priorityQueue.poll();
        root.buildCode("");
        String result = "";
        for (int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            result += charNodes.get(c).code;
        }
        System.out.println(result);
    }

    public static void main(String[] args) throws FileNotFoundException {
        long startTIME = System.currentTimeMillis();
        new Main().run();
        long finishTime = System.currentTimeMillis();
        System.out.println(finishTime - startTIME + "ms");
    }
}

Последний раз редактировалось Katya_009; 16.12.2018 в 19:01.
Katya_009 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Кодирование Модифицированным методом Хаффмана diallfam Visual C++ 1 28.01.2013 08:56
Коды Хаффмана (С++) FrostFire139 Помощь студентам 0 16.06.2012 19:17
Кодирование JEPG. Предсказать алгоритм Хаффмана. Pirotexnik Помощь студентам 9 11.05.2012 19:39
Кодирование изображений, предсказать алгоритм Хаффмана Pirotexnik Общие вопросы по программированию, компьютерный форум 0 08.05.2012 10:30
Эффективное кодирование информации методами Шеннона-Фано и Хаффмана в Delphi LoveCookies Помощь студентам 0 06.11.2011 01:19