Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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

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

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

Код:

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 в 18:32.
Katya_009 вне форума   Ответить с цитированием
Старый 05.12.2018, 18:36   #2
p51x
Профессионал
 
Регистрация: 15.02.2010
Сообщений: 13,109
Репутация: 2237
По умолчанию

Так printCodes и делает практически задачу. Или вы не понимаете, что это за коды и что за дерево строится?
__________________
Запомните раз и навсегда: помочь != "решите за меня"!
p51x вне форума   Ответить с цитированием
Старый 05.12.2018, 20:12   #3
Katya_009
Пользователь
 
Регистрация: 05.12.2018
Сообщений: 14
Репутация: -8
По умолчанию

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

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

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

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

Цитата:
Сообщение от Katya_009 Посмотреть сообщение
не понятно где листья, а где корни
Листья - это сами коды. И других листьев нет.
Корень один. По пути от корня к листьям на каждой единице вниз, на каждом нуле вверх
Верх примерно так будет выглядеть:
Код:

                +- 00000
             +--+
             |  +- 00001
          +--+
          |  +---- 0001
       +--+
       |  |  +---- 0010
       |  +--+
       |     |  +- 00110
    +--+     +--+
    |  |        +- 00111

Black Fregat на форуме   Ответить с цитированием
Старый 05.12.2018, 22:22   #7
p51x
Профессионал
 
Регистрация: 15.02.2010
Сообщений: 13,109
Репутация: 2237
По умолчанию

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

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

                +- 00000
             +--+
             |  +- 00001
          +--+
          |  +---- 0001
       +--+
       |  |  +---- 0010
       |  +--+
       |     |  +- 00110
    +--+     +--+
    |  |        +- 00111

а как сделать такой иерархический вывод именно в консоли?
Katya_009 вне форума   Ответить с цитированием
Старый 05.12.2018, 23:10   #9
p51x
Профессионал
 
Регистрация: 15.02.2010
Сообщений: 13,109
Репутация: 2237
По умолчанию

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

Цитата:
Сообщение от 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 в 20:01.
Katya_009 вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Кодирование Модифицированным методом Хаффмана 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


22:54.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru