Huffman find path

[hellacious]

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.

	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.

 

[Joopie]

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.