Most compact data format for a shopping cart

Question

I'm trying to build a format that can represent the user's cart on my website in the most compact way. The website is related to computer parts and there are 23 product categories. Each product has an unsigned integer as the product id. The product ids can range from 0 to a couple of million maybe.

Here is my attempt at it (Typescript):

const categories = [
    'motherboard',
    'cpu',
    'cpu-cooler',
    'ram',
    'internal-ssd-hdd',
    'graphics-card',
    'power-supply',
    'case',
    'case-fan',
    'fan-controller',
    'thermal-paste',
    'optical-drive',
    'sound-card',
    'wired-network-card',
    'wifi-card',
    'monitor',
    'external-ssd-hdd',
    'headphones',
    'keyboard',
    'mouse',
    'speakers',
    'ups',
    'laptop',
];

// Serialize build data
const buildData = [
    { category: 'ups', product_id: 231973 },
    { category: 'keyboard', product_id: 92153 },
    { category: 'monitor', product_id: 98231 },
    { category: 'mouse', product_id: 92752 },
    { category: 'wired-network-card', product_id: 36789 },
    { category: 'speakers', product_id: 59871 },
    { category: 'laptop', product_id: 84963 },
];

function encodeBuildData(categories: string[], build: { category: string, product_id: number }[]) {
    const bitsPerProduct = 32; // 8 bits for category index + 24 bits for product_id
    const bufferSize = Math.ceil((build.length * bitsPerProduct) / 8) + 1;
    const buffer = Buffer.alloc(bufferSize);
    // write version number
    buffer.writeUInt8(1, 0);
    let bitOffset = 8;

    build.forEach(product => {
        const categoryIndex = categories.indexOf(product.category);
        const productID = product.product_id;

        // Write the 8 bits of the category index
        buffer.writeUInt8(categoryIndex, Math.floor(bitOffset / 8));
        bitOffset += 8;

        // Write the first 16 bits of the productID
        buffer.writeUInt16BE(productID & 0xFFFF, Math.floor(bitOffset / 8));
        bitOffset += 16;

        // Write the remaining 8 bits of the productID
        buffer.writeUInt8((productID >> 16) & 0xFF, Math.floor(bitOffset / 8));
        bitOffset += 8;
    });

    return buffer;
}


function decodeBuildData(categories: string[], buffer: Buffer): { Version: number, Build: { [key: string]: number[] } } {
    const bitsPerProduct = 32; // 8 bits for category index + 24 bits for product_id
    const numProducts = Math.floor((buffer.length * 8) / bitsPerProduct);
    const build: ReturnType<typeof decodeBuildData>['Build'] = {};
    let bitOffset = 8;
    const version = buffer.readUInt8(0);

    for (let i = 0; i < numProducts; i++) {
        // Read the 8 bits of categoryIndex from the buffer
        const categoryIndex = buffer.readUInt8(Math.floor(bitOffset / 8));
        bitOffset += 8;

        // Read the first 16 bits of productID
        const productIDLower16Bits = buffer.readUInt16BE(Math.floor(bitOffset / 8));
        bitOffset += 16;

        // Read the remaining 8 bits of productID
        const productIDUpper8Bits = buffer.readUInt8(Math.floor(bitOffset / 8));
        bitOffset += 8;

        // Combine the 16 lower bits and 8 upper bits of productID
        const productID = (productIDUpper8Bits << 16) | productIDLower16Bits;

        const category = categories[categoryIndex];
        build[category] = [...(build[category] || []), productID];
    }

    return { Version: version, Build: build };
}


const encoded = encodeBuildData(categories, buildData);
console.log(decodeBuildData(categories, Buffer.from(encoded.toString('base64url'), 'base64url')), encoded.toString('base64url'));

This approach has the benefit of allowing more than one product for each category, which I would prefer to retain. I tried to use 5 bits for category id but managing bit offset between different bytes was too much for me.

Can you improve upon this or maybe come up with a different format? Remember, the goal is to have the cart config represented in the shortest URL-compatible string.

Answer 1

The OP code allocates 8 bits for the 23 distinct product categories, and 24 bits for the significantly fewer than 2^24 different products.

build a format that can represent [cart items] in the most compact way.

Represent each item with a distinct integer. Then base64-encode the binary int when adding it to an URL.

The simplest thing to do is make this a database problem. Put a UNIQUE index on an accession_number or serial column which is 1:1 with product_id, and send that to represent the item. Those identifiers will be dense, requiring fewer bits to represent them than raw product IDs. For extra credit, sort some current snapshot so you assign "small" numbers to popular items, which can be sent with fewer base64 characters.

Given a serial you can SELECT to find its product category, plus other details like shipping weight and current inventory.

---

But perhaps "most compact" wasn't your true design criterion. Perhaps you need to see a (category, product_id) tuple without a database, or perhaps there is some collation requirement for products within a category to sort together. Ok. Define a parameter like MAX_CAT = 30, so you can add another seven categories. Encode integers in this fashion:

    return product_id * MAX_CAT + category_id;

Divide by MAX_CAT to recover the product ID, or use modulo for the category ID. Notice that, with access to a division operator, there's no need for bit alignment.

You will want to describe this as your v1 encoding scheme, so you can rev to v2 when you add a 31st category. Make the version part of the URL prefix. You might want to use SemVer.

---

Consider encoding one or more check bits, from crc32 or similar. ISBN book numbers allocate a little more than 3 bits (one "digit", log_2 eleven) for that purpose. You can do that per-item, or across the whole cart.

---

Do some frequent itemset mining on current shopping carts. If shoppers often buy bread + milk, it could be worth your while to allocate a serial number for that digram. Then we might have "12" to represent bread, "15" for milk, and "19" for the combo. Depending on shopping habits, that could shrink an URL component by 50%, or still more for trigrams.

---

EDIT 1

Hmmm, turns out we don't have a requirement to send category ID as initially suggested.

  dataView.setUint16(1, lowestProductIdBeforeTransformation
                        & 0b1111111111111111);

No, please don't do that. I ran out of fingers to count one one one one and you're asking me to start using my toes. Must I carefully highlight groups of one's to verify the code still matches the comment? Express it with 0xFFFF, or Math.pow(2, 16) - 1, or a MANIFEST_CONSTANT. On which topic...

  const lowestProductIdBeforeTransformation = Math.min(...build);

That's rather dynamic.

Apparently length of buildData is much greater than seven. And it will change as months go by.

Don't set up a time bomb, where any newly added product ID could invalidate the encoding scheme.

Define a manifest constant, and verify that product IDs have appropriate magnitude. If they don't, you will need to rev the encoding version.