2
\$\begingroup\$

Intro

In this post, I will present three (3) non-negative integer encoding techniques:

Code

io.github.coderodde.encoding.IntegerCoding.java:

package io.github.coderodde.encoding;

import java.util.BitSet;

/**
 * This class provides facilities for encoding <b>non-negative</b> integers 
 * using
 * <ul>
 *   <li>Elias gamma code,</li>
 *   <li>Elias delta code,</li>
 *   <li>Golomb-Rice code.</li>
 * </ul>
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Nov 2, 2025)
 * @since 1.0.0 (Nov 2, 2025)
 */
public final class IntegerCoding {

    private IntegerCoding() {
        
    }
    
    /**
     * Encodes the non-negative integer {@code n} using 
     * <a href="https://en.wikipedia.org/wiki/Elias_gamma_coding">Elias gamma code</a>.
     * 
     * @param n the integer to encode.
     * @return a codeword.
     */
    public static CodeWord encodeWithGammaCode(int n) {
        checkNonNegative(n, "n");
        int k = getK(n);
        CodeWord codeword = new CodeWord(getGammaCodeLength(k));
        CodeWord unary = unary(k);
        
        // Add the unary prefix:
        for (int i = 0; i < unary.length(); ++i) {
            if (unary.get(i)) {
                codeword.set(i);
            }
        }
        
        // Add the binary :
        CodeWord binary = binary(n, k);
        
        for (int i = 0; i < k; ++i) {
            if (binary.get(i)) {
                codeword.set(k + 1 + i);
            }
        }
        
        return codeword;
    }
    
    /**
     * Encodes the non-negative integer {@code n} using 
     * <a href="https://en.wikipedia.org/wiki/Elias_delta_coding">Elias delta code</a>.
     * 
     * @param n the integer to encode.
     * @return a codeword.
     */
    public static CodeWord encodeWithDeltaCode(int n) {
        checkNonNegative(n, "n");
        int k = getK(n);
        CodeWord prefix = encodeWithGammaCode(k);
        CodeWord suffix = binary(n, k);
        CodeWord result = new CodeWord(prefix.length() + suffix.length());
        
        for (int i = 0; i < prefix.length(); ++i) {
            if (prefix.get(i)) {
                result.set(i);
            }
        }
        
        for (int i = 0; i < suffix.length(); ++i) {
            if (suffix.get(i)) {
                result.set(prefix.length() + i);
            }
        }
        
        return result;
    }
    
    /**
     * Encodes the non-negative integer {@code n} using Golomb-Rice code 
     * {@code GR_k(n)}.
     * 
     * @param n the integer to encode
     * @param k the degree of the encoder.
     * @return a codeword.
     */
    public static CodeWord encodeWithGolombRice(int n, int k) {
        checkNonNegative(n, "n");
        checkNonNegative(k, "k");
        int q = getQ(n, k);
        
        CodeWord prefix = unary(q);
        CodeWord suffix = binary(n, q, k);
        CodeWord result = new CodeWord(prefix.length() + suffix.length());
        
        for (int i = 0; i < prefix.length(); ++i) {
            if (prefix.get(i)) {
                result.set(i);
            }
        }
        
        for (int i = 0; i < suffix.length(); ++i) {
            if (suffix.get(i)) {
                result.set(prefix.length() + i);
            }
        }
        
        return result;
    }
    
    private static int getQ(int n, int k) {
        return n / pow(2, k);
    }
    
    private static CodeWord unary(int k) {
        CodeWord codeword = new CodeWord(k + 1);
        
        for (int i = 0; i < k; ++i) {
            codeword.set(i);
        }
        
        return codeword;
    }
    
    private static CodeWord binary(int n, int k) {
        int arg = n - pow(2, k) + 1;
        BitSet bits = BitSet.valueOf(new long[] { arg & 0xFFFF_FFFF });
        CodeWord codeword = new CodeWord(k);
        
        for (int i = 0; i < k; ++i) {
            if (bits.get(i)) {
                codeword.set(i);
            }
        }
        
        return codeword.reverse();
    }
    
    private static CodeWord binary(int n, int q, int k) {
        int arg = n - q * pow(2, k);
        BitSet bits = BitSet.valueOf(new long[] { arg & 0xFFFF_FFFF });
        CodeWord codeword = new CodeWord(k);
        
        for (int i = 0; i < k; ++i) {
            if (bits.get(i)) {
                codeword.set(i);
            }
        }
        
        return codeword.reverse();
    }
    
    private static int getGammaCodeLength(int k) {
        return 2 * k + 1;
    }
    
    private static int getK(int n) {
        return (int) log2(n + 1);
    }
    
    private static double log2(int n) {
        return Math.log(n) / Math.log(2.0);
    }
    
    private static int pow(int base, int power) {
        return (int) Math.pow(base, power);
    }
    
    private static void checkNonNegative(int n, String name) {
        if (n < 0) {
            throw new IllegalArgumentException(
                    String.format("%n(%d) < 0", name, n));
        }
    }
    
    public static void main(String[] args) {
        System.out.println("--- Gamma ---");
        System.out.println(encodeWithGammaCode(100));
        System.out.println(encodeWithGammaCode(400));
        
        System.out.println("--- Delta ---");
        System.out.println(encodeWithDeltaCode(100));
        System.out.println(encodeWithDeltaCode(400));
        
        System.out.println("--- Golomb-Rice (k = 4) ---");
        System.out.println(encodeWithGolombRice(100, 4));
        System.out.println(encodeWithGolombRice(400, 4));
    }
}

io.github.coderodde.encoding.CodeWord.java:

package io.github.coderodde.encoding;

import java.util.BitSet;

/**
 * This class implements a <b>binary</b> code word in data compression 
 * scenarios.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Oct 28, 2025)
 * @since 1.0.0 (Oct 28, 2025)
 */
public class CodeWord {

    private final int length;
    private final BitSet bits;
    
    public CodeWord(final int length) {
        checkLength(length);
        this.length = length;
        this.bits = new BitSet(length);
    }
    
    public int length() {
        return length;
    }
    
    public boolean get(final int index) {
        checkIndex(index);
        return bits.get(index);
    }
    
    public void set(final int index) {
        checkIndex(index);
        bits.set(index);
    }
    
    public void unset(final int index) {
        checkIndex(index);
        bits.set(index, false);
    }
    
    public CodeWord reverse() {
        int length = length();
        CodeWord reversed = new CodeWord(length);
        
        for (int i = 0; i < length; ++i) {
            boolean bit = get(i);
            
            if (bit) {
                reversed.set(length - 1 - i);
            }
        }
        
        return reversed;
    }
    
    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder(length);
        
        for (int i = 0; i < length; ++i) {
            sb.append(get(i) ? "1" : "0");
        }
        
        return sb.toString();
    }
    
    private void checkIndex(final int index) {
        if (index < 0) {
            throw new IndexOutOfBoundsException(
                    String.format("index(%d) < 0", index));
        }
        
        if (index >= this.length) {
            throw new IndexOutOfBoundsException(
                    String.format("index(%d) >= length(%d)", 
                                  index, 
                                  length));
        }
    }
    
    private static void checkLength(final int length) {
        if (length < 1) {
            throw new IllegalArgumentException(
                    String.format("length(%d) < 1", length));
        }
    }
}

Critique request

As always, tell me whatever comes to mind.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Should the title of this post be "encoding" and not "coding"? In another context they might be synonymous, but "coding" in the title of a "Code Review" question sounds like it means "programming" \$\endgroup\$ Commented yesterday
  • 1
    \$\begingroup\$ Is it voluntary that the input is limited to 31-bit integers? Once of the main reasons to use those encodings is to allow integers of any size. Unless what you are interested in is the potential size reduction if you have a majority of (very) small integers. \$\endgroup\$ Commented yesterday
  • \$\begingroup\$ @jcaron I just started studying data compression, and so, I am an amateur writing amateur code. \$\endgroup\$ Commented yesterday
  • \$\begingroup\$ @Stef You are correct. \$\endgroup\$ Commented yesterday

2 Answers 2

Reset to default
4
\$\begingroup\$ 
private static int getQ(int n, int k) {
    return n / pow(2, k);
}

private static int getK(int n) {
    return (int) log2(n + 1);
}

private static double log2(int n) {
    return Math.log(n) / Math.log(2.0);
}

private static int pow(int base, int power) {
    return (int) Math.pow(base, power);
}

I would not use any of these for bit-manipulation, which is what they're used for here (Golomb encoding could use the non-binary variants). Java has a decent set of bit-manipulation operators and built-in functions such as Integer.numberOfLeadingZeros.

Gamma encoding is actually trivial in a sense: the encoding of the integer n is n itself - the only complication is how many leading zeroes to give it. But that's not the encoding your code does, it prepends ones and does some mysterious manipulation inside binary (besides converting an int, which is already its own bits anyway, into bits) which I'm not convinced is correct: adding 1 at this point can carry into the k'th bit but that bit needs to have the opposite value of the unary prefix otherwise the decoder gets confused about where the prefix ends (but I may have misunderstood what's going on through all the complications). If this change is to be able to encode 0, how about adding 1 at the start, and then encoding it as normal (ie encoding a value as itself, padded with a specific number of leading zeroes).

I believe that this CodeWord as an abstraction has done more harm than good, causing code that could have been trivial to be anything but, causing a lot of bit-by-bit work that would be simple integer operations. It also won't serve you well when you try to serialize code words into a stream of bytes, with this CodeWord that can only be done bit-by-bit which is not great (or through an extra detour through a String but also bit-by-bit and even less great). A pair of long (to hold the bits) and int (to hold the length of the codeword) would serve you better for almost all cases, unless you're serious about having code words longer than 64 bits (non-negative int values fit in 64 bits or fewer, using either gamma or delta encoding).

\$\endgroup\$
3
  • \$\begingroup\$ The whole goal of those encodings is to be able to store numbers with no upper bound, so using a fixed-sized storage would probably not be the right solution. But it would probably make more sense to make CodeWord a subclass of a BitSet rather than encapsulate one with little added value. \$\endgroup\$ Commented yesterday
  • 1
    \$\begingroup\$ @jcaron that's theoretical, these functions only encode an int which then implies an upper bound on the output size as well. Even for larger values a BitSet would be annoying to use, encouraging bit-by-bit loops. \$\endgroup\$ Commented yesterday
  • \$\begingroup\$ Ah indeed I hadn't looked at the input. That's probably another point to raise in the code review though: the limited input range. \$\endgroup\$ Commented yesterday
3
\$\begingroup\$

As another review says, I'm not convinced [it] is correct. Suitable conviction could be assured by providing actual unit tests. These would differ from the sample usage shown in a number of ways:

  • They illustrate the expected result directly in the code.
  • They check whether the actual result matches expectation, and reflect that in the exit status.
  • They exercise the limit cases and any other "edge" values likely to be problematic.

You might be able to also include a "battery" test to demonstrate that a large sample of possible inputs successfully round-trip to a CodeWord and back to the original value. If doing this, I suggest using a pseudo-random generator with a fixed seed, or a user-specifiable seed, so that results can be reproducible.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.