5
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Are the product ids not globally unique but only unique within each product category? \$\endgroup\$ Commented Mar 26, 2023 at 19:13
  • \$\begingroup\$ They are actually, globally unique. This means that we probably don't even need to store the category id in the URL. Just the product ids \$\endgroup\$ Commented Mar 26, 2023 at 22:14
  • 1
    \$\begingroup\$ Yeah, if you're looking for absolutely greatest compactness/compression, get rid of them. \$\endgroup\$ Commented Mar 27, 2023 at 0:20
  • \$\begingroup\$ Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered. \$\endgroup\$ Commented Mar 27, 2023 at 3:33
  • \$\begingroup\$ If you want to update the code for a second review please ask a new question with a link back to this question. \$\endgroup\$ Commented Mar 27, 2023 at 3:35

1 Answer 1

Reset to default
4
\$\begingroup\$

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.

\$\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.