Huffman find path

Results 1 to 2 of 2
  1. #1
    Hardcore Member hellacious is offline
    MemberRank
    Jun 2009 Join Date
    LithuaniaLocation
    125Posts

    idea Huffman find path

    Hello,

    I have two arrays:

    short[] LEAFS = new short[length]
    short[] INTERNAL_NODES = new short[length - 1][2]

    I read dicitonary and fill LEAFS with item ids and I fill INTERNAL_NODES array with left and right nodes which are positive and/or negative.

    Code:
    	public void loadDictionary()
    	{
            if (LEAF_NODES != null && INTERNAL_NODES != null)
                return;
    
            Path path = Paths.get("./dictionary.dat");
    
            try (DataInputStream bis = new DataInputStream(new ByteArrayInputStream(Files.readAllBytes(path))))
            {
    	        final short numIds = (short)((bis.readByte() & 0xFF) | bis.readByte() << 8);
    	        this.LEAF_NODES = new short[numIds];
    	        for (short n2 = 0; n2 < numIds; ++n2) {
    	            this.LEAF_NODES[n2] = (short)(bis.readByte() << 8 | (short)(bis.readByte() & 0xFF));
    	        }
    	        this.INTERNAL_NODES = new short[numIds - 1][2];
    
    	        for (short n3 = 0; n3 < numIds - 1; n3++) {
    	            this.INTERNAL_NODES[n3][0] = (short)((bis.readByte() & 0xFF) | bis.readByte() << 8);
    	            this.INTERNAL_NODES[n3][1] = (short)((bis.readByte() & 0xFF) | bis.readByte() << 8);
    	        }
            }
            catch (IOException e)
            {
    			_log.log(Level.SEVERE, "WARNING: The Server coud not load dictionary. Reason: "
    					+ e.getMessage(), e);
            }
    	}

    How can I find binary path for needed (short) item id ? I spent all day trying to implement this, but without success.

    I can decompress data just fine, but I have no idea how to find path for compression.
    Learning C#


  2. #2
    Deep thoughts Huffman find path Joopie is offline
    Alpha MaleRank
    Jun 2010 Join Date
    The NetherlandsLocation
    2,637Posts

    Re: Huffman find path

    Is the tree sorted by any change or is it just a random tree?

    The implementation can depend heavily on that (performance wish too)!

    Best way to find the path of your item id is by making a recursive method. One of the parameters is a stack. You can use this to keep of your path. When you enter a node with that resursive method, add it to the stack. When you didn't find the wanted item id, remove it from the stack. And when you do find your wanted item id. The stack contains the path to it.



Advertisement