Comparing gamma-encoding against GR_2.

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));
        }
    }
}

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) {
        for (int i = 1; i <= 1_000; ++i) {
            CodeWord gamma = encodeWithGammaCode(i);
            CodeWord gr    = encodeWithGolombRice(i, 2);
            
            int gammaLength = gamma.length();
            int grLength    = gr.length();
            
            String cmp = cmpstr(gammaLength,
                                grLength);
            
            System.out.printf("%4d: %s -> gamma = %s (%d), GR = %s (%d)\n",
                              i, 
                              cmp,
                              gamma,
                              gamma.length(),
                              gr,
                              gr.length());
        }
    }
    
    private static String cmpstr(int a, int b) {
        if (a < b) {
            return "<";
        }
        
        if (a > b) {
            return ">";
        }
        
        return "=";
    }
}