最紧凑的购物车数据格式

Question

我试图建立一个格式，可以代表用户的购物车在我的网站上，以最紧凑的方式。该网站与计算机部件相关，共有23个产品类别。每个产品都有一个无符号整数作为产品id。产品ids可能在0到几百万之间。

这是我的尝试(打字本)：

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

这种方法的好处是允许为每个类别提供多个产品，我更愿意保留这些产品。我试图使用5位作为类别id，但是管理不同字节之间的位偏移对我来说太过了。

你能改进这一点，或者想出一种不同的格式吗？记住，我们的目标是用最短的URL兼容字符串来表示cart配置。

Answer 1

OP代码为23个不同的产品类别分配8位，为显著少于2^24种不同的产品分配24位。

构建一种可以以最紧凑的方式表示手推车项目的格式。

用不同的整数表示每个项目。然后base64 64-在将二进制int添加到URL时对其进行编码。

最简单的方法就是让这成为一个数据库问题。在accession_number或serial列(与product_id的比例为1:1 )上设置一个唯一的索引，并发送该索引来表示该项。这些标识符将是密集的，需要比原始产品ID更少的位来表示它们。为了获得额外的信用，对当前快照进行排序，以便将“小”数字分配给受欢迎的项目，可以用较少的base64字符发送这些数字。

给定一个系列，你可以选择找到它的产品类别，再加上其他细节，如运输重量和当前库存。

但也许“最紧凑”并不是你真正的设计标准。也许您需要看到一个(类别，product_id)元组而没有数据库，或者可能需要对某个类别中的产品进行排序。好的。定义一个像MAX_CAT = 30这样的参数，这样您就可以添加另外七个类别。以这种方式编码整数：

    return product_id * MAX_CAT + category_id;

除以MAX_CAT以恢复产品ID，或使用模作为类别ID。注意，通过对除法操作符的访问，不需要位对齐。

您将希望将此描述为您的v1编码方案，因此当您添加第31类时，您可以将其转换为v2。使URL前缀的版本部分。您可能需要使用SemVer。

考虑对crc32或类似的一个或多个校验位进行编码。ISBN图书编号为此分配了略多于3位(一位“数字”，log_2 11位)。你可以按项目做，也可以穿过整辆车。

在当前的购物车上做一些频繁的项目集挖掘。如果购物者经常购买面包和牛奶，那么为这个数字分配一个序列号是值得的。然后我们可能有"12“来代表面包，"15”代表牛奶，"19“代表组合。根据购物习惯，这可能会使URL组件减少50%，甚至更多。

编辑1

嗯，原来我们不需要像最初建议的那样发送类别ID。

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

不，请不要那样做。我一根手指都没了，而你却要我开始用脚趾。我必须仔细地突出显示一个人的组，以验证代码是否仍然与注释匹配？用0xFFFF或Math.pow(2，16) - 1或MANIFEST_CONSTANT表示。关于哪个话题..。

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

这是相当动态的。

显然，buildData的长度远远大于7。几个月过去了，情况会变的。

不要设置定时炸弹，任何新添加的产品ID都可能使编码方案失效。

定义一个清单常量，并验证产品ID具有适当的大小。如果它们没有，则需要重新编写编码版本。