具有恒定数字和的整数的有效编码



如何对一个大的整数集进行编码,这些整数集都有一个已知的常量数字和和和一个常量数字。

以10为基数的整数示例,数字和为5,数字为3:

014, 041, 104, 113, 122, 131, 140, 203 ....

最重要的因素是空间,但计算时间并非完全不重要。

最简单的方法是存储数字和本身,并保持不变。

但我可能误解了这个问题。

编辑:这是我的收获:你想对集合本身进行编码;是 啊

对集合本身进行编码就像存储基数、数字和和位数一样简单,例如您给出的示例中的{10, 5, 3}

然而,大多数时候,你会发现一个数字最紧凑的表示是数字本身,除非它很大。

此外,由于数字和通常被认为是递归的;1至9岁(含1至9);203具有与500、140或950相同的数字和。这意味着该集合对于任何数字组合都是巨大的,并且任何集合(除了某些退化情况)都使用与它们相关的基数中的每个可用数字。

所以,你知道,当单独存储时,对数字本身最有效的编码变成了数字本身,特别是考虑到±2 147 483 648之间的每个数字通常在内存中占用相同的空间,而且通常在存储中。

当你有一组定义明确的可能值要编码时,直接编码的理论方法是对所有可能的值进行顺序编号,然后根据需要存储这个数字。如果单个值的频率相同或未知,这显然是最优的。如果你对频率分布有所了解,你就必须使用霍夫曼代码来获得真正的最佳结果,但这相当复杂,我只处理其他情况。

对于均匀分布(或未知)的情况,方法如下:想象一下(您可以预生成并存储它,或者动态生成它)一个按字典顺序排序的所有输入(用于编码)值的列表。例如,在您的情况下,列表的开头为(除非您的数字和是递归的):005、023、032、050、104、113、122、131、140、203、212、221、230、401、410、500。然后根据列表中的每个项目在列表中的位置为其分配一个整数:005变为0,023变为1,032变为2,依此类推。列表中有16个值(除非我犯了错误,如果是,请适当调整),为此,您需要4位来将任何索引编码到列表中。这个索引是您的编码值,编码和解码变得显而易见。

至于首先生成列表的算法:最简单的方法是从000到999计数,然后扔掉所有不符合标准的东西。通过复制计数和溢出(例如104如何跟随050),可以更聪明地做到这一点,但这可能不值得付出努力。

最新更新