Реализация кода Хаффмана

Я ищу обзор кода, оптимизацию, лучшие практики.

/**
 * Huffman encoding obeys the huffman algorithm.
 * It compresses the input sentence and serializes the "huffman code"
 * and the "tree" used to generate  the huffman code
 * Both the serialized files are intended to be sent to client.
 * 
 */
public final class Huffman {

    private Huffman() {};

    private static class HuffmanNode {
        char ch;
        int frequency;
        HuffmanNode left;
        HuffmanNode right;

        HuffmanNode(char ch, int frequency,  HuffmanNode left,  HuffmanNode right) {
            this.ch = ch;
            this.frequency = frequency;
            this.left = left;
            this.right = right;
        }
    }

    private static class HuffManComparator implements Comparator<HuffmanNode> {
        @Override
        public int compare(HuffmanNode node1, HuffmanNode node2) {
            return node1.frequency - node2.frequency;
        }
    }

    /**
     * Compresses the string using huffman algorithm.
     * The huffman tree and the huffman code are serialized to disk
     * 
     * @param sentence                  The sentence to be serialized
     * @throws FileNotFoundException    If file is not found
     * @throws IOException              If IO exception occurs.
     */ 
    public static void compress(String sentence) throws FileNotFoundException, IOException {
        if (sentence == null) {
            throw new NullPointerException("Input sentence cannot be null.");
        }
        if (sentence.length() == 0) {
            throw new IllegalArgumentException("The string should atleast have 1 character.");
        }

        final Map<Character, Integer> charFreq = getCharFrequency(sentence); 
        final HuffmanNode root = buildTree(charFreq);
        final Map<Character, String> charCode = generateCodes(charFreq.keySet(), root);
        final String encodedMessage = encodeMessage(charCode, sentence);
        serializeTree(root);
        serializeMessage(encodedMessage);
    }

    private static Map<Character, Integer> getCharFrequency(String sentence) {
        final Map<Character, Integer> map = new HashMap<Character, Integer>();

        for (int i = 0; i < sentence.length(); i++) {
            char ch = sentence.charAt(i);
            if (!map.containsKey(ch)) {
                map.put(ch, 1);
            } else {
                int val = map.get(ch);
                map.put(ch, ++val);
            }
        }

        return map;
    }


    /** 
     * Map<Character, Integer> map
     * Some implementation of that treeSet is passed as parameter.
     * @param map
     */
    private static HuffmanNode buildTree(Map<Character, Integer> map) {
        final Queue<HuffmanNode> nodeQueue = createNodeQueue(map);

        while (nodeQueue.size() > 1) {
            final HuffmanNode node1 = nodeQueue.remove();
            final HuffmanNode node2 = nodeQueue.remove();
            HuffmanNode node = new HuffmanNode('\0', node1.frequency + node2.frequency, node1, node2);
            nodeQueue.add(node);
        }

        // remove it to prevent object leak.
        return nodeQueue.remove();
    }

    private static Queue<HuffmanNode> createNodeQueue(Map<Character, Integer> map) {
        final Queue<HuffmanNode> pq = new PriorityQueue<HuffmanNode>(11, new HuffManComparator());
        for (Entry<Character, Integer> entry : map.entrySet()) {
            pq.add(new HuffmanNode(entry.getKey(), entry.getValue(), null, null));
        }
        return pq;
    }

    private static Map<Character, String> generateCodes(Set<Character> chars, HuffmanNode node) {
       final Map<Character, String> map = new HashMap<Character, String>();
       doGenerateCode(node, map, "");
       return map;
    }


    private static void doGenerateCode(HuffmanNode node, Map<Character, String> map, String s) {
        if (node.left == null && node.right == null) {
            map.put(node.ch, s);
            return;
        }    
        doGenerateCode(node.left, map, s + '0');
        doGenerateCode(node.right, map, s + '1' );
    }


    private static String encodeMessage(Map<Character, String> charCode, String sentence) {
        final StringBuilder stringBuilder = new StringBuilder();

        for (int i = 0; i < sentence.length(); i++) {
            stringBuilder.append(charCode.get(sentence.charAt(i)));
        }
        return stringBuilder.toString();
    }

    private static void serializeTree(HuffmanNode node) throws FileNotFoundException, IOException {
        final BitSet bitSet = new BitSet();
        try (ObjectOutputStream oosTree = new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/tree"))) {
            try (ObjectOutputStream oosChar = new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/char"))) {
                IntObject o = new IntObject();
                preOrder(node, oosChar, bitSet, o);
                bitSet.set(o.bitPosition, true); // padded to mark end of bit set relevant for deserialization.
                oosTree.writeObject(bitSet);
            }
        }
    }

    private static class IntObject {
        int bitPosition;
    }

    /*
     * Algo:
     * 1. Access the node
     * 2. Register the value in bit set.
     * 
     * 
     * here true and false dont correspond to left branch and right branch.
     * there,
     * - true means "a branch originates from leaf"
     * - false mens "a branch originates from non-left".
     * 
     * Also since branches originate from some node, the root node must be provided as source 
     * or starting point of initial branches.
     *     
     * Diagram and how an bit set would look as a result.
     *              (source node)
     *             /             \
     *          true             true
     *           /                  \
     *       (leaf node)        (leaf node)
     *          |                     |
     *        false                  false 
     *          |                     |
     *          
     * So now a bit set looks like [false, true, false, true]          
     * 
     */
    private static void preOrder(HuffmanNode node, ObjectOutputStream oosChar, BitSet bitSet, IntObject intObject) throws IOException {
        if (node.left == null && node.right == null) {
            bitSet.set(intObject.bitPosition++, false);  // register branch in bitset
            oosChar.writeChar(node.ch);
            return;                                  // DONT take the branch.
        }
        bitSet.set(intObject.bitPosition++, true);           // register branch in bitset
        preOrder(node.left, oosChar, bitSet, intObject); // take the branch.

        bitSet.set(intObject.bitPosition++, true);               // register branch in bitset
        preOrder(node.right, oosChar, bitSet, intObject);    // take the branch.
    }

    private static void serializeMessage(String message) throws IOException {
        final BitSet bitSet = getBitSet(message);

        try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/encodedMessage"))){

            oos.writeObject(bitSet);
        } 
    }

    private static BitSet getBitSet(String message) {
        final BitSet bitSet = new BitSet();
        int i = 0;
        for (i = 0; i < message.length(); i++) {
            if (message.charAt(i) == '0') {
                bitSet.set(i, false);
            } else {
                bitSet.set(i, true);
            }
        }
        bitSet.set(i, true); // dummy bit set to know the length 
        return bitSet;
    }

    /**
     * Retrieves back the original string.
     * 
     * 
     * @return                          The original uncompressed string
     * @throws FileNotFoundException    If the file is not found
     * @throws ClassNotFoundException   If class is not found
     * @throws IOException              If IOException occurs
     */
    public static String expand() throws FileNotFoundException, ClassNotFoundException, IOException {
        final HuffmanNode root = deserializeTree();
        return decodeMessage(root);
    }

    private static HuffmanNode deserializeTree() throws FileNotFoundException, IOException, ClassNotFoundException {
        try (ObjectInputStream oisBranch = new ObjectInputStream(new FileInputStream("/Users/ap/Desktop/tree"))) {
            try (ObjectInputStream oisChar = new ObjectInputStream(new FileInputStream("/Users/ap/Desktop/char"))) {
                final BitSet bitSet = (BitSet) oisBranch.readObject();
                return preOrder(bitSet, oisChar, new IntObject());
            }
        }
    }

    /*
     * Construct a tree from: 
     * input [false, true, false, true, (dummy true to mark the end of bit set)]
     * The input is constructed from preorder traversal
     * 
     * Algo:
     * 1  Create the node.
     * 2. Read what is registered in bitset, and decide if created node is supposed to be a leaf or non-leaf 
     * 
     */
    private static HuffmanNode preOrder(BitSet bitSet, ObjectInputStream oisChar, IntObject o) throws IOException {   
        // created the node before reading whats registered.
        final HuffmanNode node = new HuffmanNode('\0', 0, null, null);

        // reading whats registered and determining if created node is the leaf or non-leaf.
        if (!bitSet.get(o.bitPosition)) {
            o.bitPosition++;              // feed the next position to the next stack frame by doing computation before preOrder is called.
            node.ch = oisChar.readChar();
            return node;
        } 

        o.bitPosition = o.bitPosition + 1;  // feed the next position to the next stack frame by doing computation before preOrder is called.
        node.left = preOrder(bitSet, oisChar, o); 

        o.bitPosition = o.bitPosition + 1; // feed the next position to the next stack frame by doing computation before preOrder is called.
        node.right = preOrder(bitSet, oisChar, o);

        return node;
    }

    private static String decodeMessage(HuffmanNode node) throws FileNotFoundException, IOException, ClassNotFoundException {
        try (ObjectInputStream ois = new ObjectInputStream(new FileInputStream("/Users/ameya.patil/Desktop/encodedMessage"))) {
            final BitSet bitSet = (BitSet) ois.readObject();
            final StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < (bitSet.length() - 1);) {
                HuffmanNode temp = node;
                // since huffman code generates full binary tree, temp.right is certainly null if temp.left is null.
                while (temp.left != null) {
                    if (!bitSet.get(i)) {
                        temp = temp.left;
                    } else {
                        temp = temp.right;
                    }
                    i = i + 1;
               }
                stringBuilder.append(temp.ch);
            }
            return stringBuilder.toString();
        }
    }

    public static void main(String[] args) throws FileNotFoundException, IOException, ClassNotFoundException {
        // even number of characters
        Huffman.compress("some");
        Assert.assertEquals("some", Huffman.expand());

        // odd number of characters
        Huffman.compress("someday");
        Assert.assertEquals("someday", Huffman.expand());

        // repeating even number of characters + space + non-ascii
        Huffman.compress("some some#");
        Assert.assertEquals("some some#", Huffman.expand());

        // odd number of characters + space + non-ascii
        Huffman.compress("someday someday&");
        Assert.assertEquals("someday someday&", Huffman.expand());
    }
}
11 голосов | спросил JavaDeveloper 16 MaramSun, 16 Mar 2014 02:07:16 +04002014-03-16T02:07:16+04:0002 2014, 02:07:16

3 ответа


7

Отличный старт

  • Очистить код
  • Короткие методы
  • JavaDoc
  • Тесты (хотя они нуждаются в реорганизации в качестве отмеченного palacsint)

Encapsulate

Разделите и инкапсулируйте часть логики в пользовательские классы, а не напрямую обходите коллекции. Это улучшает тестируемость и повторное использование. Одним из главных примеров является частотная карта символов, которую можно легко использовать во многих других программах.

Вот простая реализация, которая обеспечивает только то, что необходимо для этой программы, но она, безусловно, может выиграть от таких методов, как size(), getCount(Character c) и т. Д. Я также не беспокоился об обертывании открытой карты /набора в немодифицируемые коллекции, что было бы желательно (хотя см. Ниже для другого варианта) .

/**
 * Keeps a running count of how many times each unique character is seen.
 */
public class CharacterCounter
{
    private final HashMap<Character, Integer> counts = new HashMap<>();

    /**
     * Increments the count of the given character,
     * setting it to one on first appearance.
     *
     * @param c the character to count
     */
    public void increment(Character c) {
        Integer freq = counts.get(c);
        if (freq == null) {
            counts.put(c, 1);
        } else {
            counts.put(c, freq + 1);
        }
    }

    /**
     * Increments the count of each character in the given text.
     *
     * @param text contains the characters to count
     */
    public void increment(String text) {
        for (char c : text) {
            increment(c);
        }
    }

    /**
     * Returns the set of characters seen.
     *
     * @return set containing each character seen while counting
     */
    public Set<Character> getCharacters() {
        return counts.keySet();
    }

    /**
     * Returns the set of characters seen along with their counts.
     *
     * @return set containing each character seen while counting and its count
     */
    public Set<Map.Entry<Character, Integer>> getCharacterCounts() {
        return counts.entrySet();
    }
}

Чтобы избежать раскрытия базовой карты, вы можете пойти дальше, используя закрытие (Java 8) или анонимный класс посетителей:

public class CharacterCounter
{
    ...
    public interface Visitor {
        void visit(Character c, Integer count);
    }

    /**
     * Passes each character and its count to the given visitor.
     *
     * @param visitor receives characters and counts in an undefined order
     */
    public void apply(Visitor visitor) {
        for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
            visitor.visit(entry.getKey(), entry.getValue());
        }
    }
}

private static Queue<HuffmanNode> createNodeQueue(CharacterCounter counter) {
    final Queue<HuffmanNode> pq = new PriorityQueue<>(11, new HuffManComparator());
    counter.apply(new CharacterCounter.Visitor() {
        public void visit(Character c, Integer count) {
            pq.add(new HuffmanNode(c, count, null, null));
        }
    });
    return pq;
}

Я бы выполнил ту же инкапсуляцию с помощью HuffmanTree создания и управления узлами из CharacterCounter

Разное

  • Предоставьте конструктор с двумя аргументами для HuffmanNode, который по умолчанию присваивает другим параметрам null

  • Внедрить Comparable<HuffmanNode> непосредственно для естественного упорядочения вместо того, чтобы поставлять отдельный Comparator в очередь приоритетов.

  • Будьте внимательны, чтобы не включать слишком много деталей кода в комментарии. По мере изменения кода комментарии становятся некорректными. Пример:

    /** 
     * Map<Character, Integer> map
     * Some implementation of that treeSet is passed as parameter.
     * @param map
     */
    private static HuffmanNode buildTree(Map<Character, Integer> map) {
    

    Первая строка не нужна, поскольку она находится в сигнатуре метода, а вторая строка указывает, что параметр должен быть TreeSet, который не является правильный.

  • Благодаря сборщику мусора это совершенно не нужно:

    // remove it to prevent object leak.
    return nodeQueue.remove();
    

    Так как nodeQueue является локальным и никогда не отображается снаружи, он будет собран вместе со ссылкой на корневой узел.

ответил David Harkness 16 MaramSun, 16 Mar 2014 04:58:43 +04002014-03-16T04:58:43+04:0004 2014, 04:58:43
5
  1. В настоящее время оба compress() и expand() являются статическими методами в классе, которые ограничивают его удобство использования. Только один поток может сжимать /расширять только одну строку. Он может иметь лучший API, который хранит закодированные в памяти и позволяет создавать несколько закодированных данных одновременно.

  2. Код содержит много жестко закодированных путей, например /Users/ap/Desktop/tree. Тесты терпят неудачу с помощью FileNotFoundException, потому что в моей системе класс не смог создать эти файлы /каталоги из-за настроек разрешения файловой системы. Если это временные файлы, они должны быть созданы в java.io.tmpdir . Если нет, они должны быть установлены клиентами класса.

  3. Замечательно, что у вас есть тест самопроверки! Обычно они находятся в файле Test (HuffmanTest, в этом случае), выполняемый JUnit. Они также находятся в отдельной исходной папке, которая позволяет не упаковывать junit.jar (и другие тестовые зависимости) с производственным кодом.

    import static org.junit.Assert.assertEquals;
    
    import org.junit.Test;
    
    public class HuffmanTest {
    
        @Test
        public void testHuffman() throws Exception {
            Huffman.compress("some");
            assertEquals("some", Huffman.expand());
        }
    
        @Test
        public void testOddNumberOfCharacters() throws Exception {
            // odd number of characters
            Huffman.compress("someday");
            assertEquals("someday", Huffman.expand());
        }
    
        @Test
        public void testRepeatingEvenNumberOfCharactersAndSpaceAndNonAsciiCharacters() throws Exception {
            Huffman.compress("some some#");
            assertEquals("some some#", Huffman.expand());
    
        }
    
        @Test
        public void testOddNumberOfCharactersAndSpaceAndNonAscii() throws Exception {
            Huffman.compress("someday someday&");
            assertEquals("someday someday&", Huffman.expand());
        }
    }
    

    Несколько других модификаций:

    • статический импорт assertEquals за меньший беспорядок,
    • отдельные методы тестирования локализация дефектов (в исходный код, если первое утверждение выдаст исключение, вы не узнаете, что остальные потерпели неудачу или нет),
    • комментарии обратились к именам тестовых методов (см. Очистить код Robert C. Martin , Не используйте комментарий, когда вы можете использовать функцию или Переменная , p67),
    • изменил три исключения в сигнатуре только на throws Exception. JUnit поймает все исключения (а также JRE, вы можете сделать то же самое с методом main).
ответил palacsint 16 MaramSun, 16 Mar 2014 03:37:08 +04002014-03-16T03:37:08+04:0003 2014, 03:37:08
4

Считывая код, вы предполагаете, что:

  1. Данные всегда сериализуются в одно и то же место на диске.
  2. Данные всегда декодируются из одного и того же места на диске.
  3. Ваш исходный алфавит может состоять только из кодовых точек UTF-16.

Число 1 и 2 плохо по моему скромному мнению. В какой-то момент вы можете сделать что-то еще со сжатыми данными, например, закодировать его в base64 и передать на веб-страницу в текстовом режиме. Номер 3 является таким-то в зависимости от того, как вы используете кодировщик Хаффмана.

Я не согласен с принятым ответом на то, что код ясен.

Существует предел, когда небольшие функции становятся слишком много, и я считаю, что вы пересекли эту линию. Трудно следовать алгоритму, чтобы проверить правильную реализацию (я понимаю, что Хаффману просто сложно следовать, перепрыгивая через все функции).

Проверьте, что сжатые данные меньше исходных данных

Ваши тесты действительно должны быть модульными тестами, о которых говорит palacsint в своем ответе. Также, вероятно, самый важный тест, который вы должны сделать, - увидеть, что сжатые данные меньше исходных данных.

В частности, любой правильно реализованный кодер Хаффмана должен очень тесно взаимодействовать с Теорема кодирования исходного кода Шеннона . Для достаточно большого количества образцов вы должны быть в пределах 1% от лимита в этой ссылке.

Другие комментарии

Вы генерируете свои префиксные коды как строки и выполняете добавление строк. Я считаю, что этот код трудно следовать, поскольку вы скрываете тот факт, что вы выполняете бит-арифметику.

Я бы использовал естественный порядок для узлов вместо реализации класса компаратора.

Я не вижу упоминания символа остановки, который предотвращает случайное декодирование нежелательной информации, когда ваш выходной бит не является четным кратным 8 бит.

И это:

    try (ObjectOutputStream oosTree = new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/tree"))) {
        try (ObjectOutputStream oosChar = new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/char"))) {

Я бы сделал это так, чтобы избежать вложенности:

    try (ObjectOutputStream oosTree = 
             new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/tree"));
         ObjectOutputStream oosChar = 
             new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/char"))) {

Класс IntObject выглядит как работа вокруг проблемы с передачей целых чисел в качестве аргументов, я бы структурировал свой код так, чтобы это было не требуется.

ответил Emily L. 16 MarpmSun, 16 Mar 2014 18:14:35 +04002014-03-16T18:14:35+04:0006 2014, 18:14:35

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132