9

我想将一系列数字转换为单个数字，该数字将保留各个值及其位置。例如，提供了以下序列-

1,6,7,8,9,45,67

在这里，例如，如果我应用简单的加法，即 1+6+7+8+9+45+67，那么将生成一个数字。但从那个没有。我们无法通过它们的顺序提取单个数字[即 1,6,7,8,9,...]。

有没有什么方法可以在不进行任何模棱两可的扣除的情况下实现此功能[即从一个数字中只提取一组唯一的数字。]？是否有任何数学函数有助于从该数字中取回单个元素？

4

8 回答 8

10

您可以将其转换为以 N 为底的数字，其中 N 比输入序列中出现的最大值大一。

更新

根据各种评论，我想提供一个可能更容易实施的替代解决方案。您可以将序列视为 UTF-8 编码字符串，并使用Huffman 编码和自定义字典来实现紧凑表示。

自定义字典允许您用很少的位存储非常常见的字符（例如，序列分隔符 ',' 和单个字符 '0'..'9' 可以存储低至 3 位，但也可以存储其他数字您发现统计上可能发生的可以存储在一个短的位序列中。例如，如果您发现“42”经常出现，您可以将“42”存储在几个位中。

如果只为“,”和“0”到“9”分配特殊代码，则输入字符串中的每个字符平均少于 4 位，同时保留逗号分隔的序列成员。查找常见的多字符子字符串并将它们添加到字典中只会提高该比率。

使用自定义字典还意味着您不必将字典存储在压缩数据的标头中，因为它对您来说是众所周知的。

我使用 SharpZipLib 做了这样的事情

http://www.icsharpcode.net/opensource/sharpziplib/

http://community.sharpdevelop.net/forums/p/8255/23219.aspx

用zlib也很容易做到

压缩小块数据

于 2012-09-01T16:19:12.193 回答
4

在数学上可以为有限序列做到这一点，但不是很实用，因为所需的数字很快就会变得非常大：从 1 ... 67 有 67 7（大约 2 42）个不同的长度为 7 的整数序列，更不用说更长了序列和更大的整数。

对于此类函数的简单示例，将序列 [1,6,7,8,9,45,67] 映射到值 2 1 * 3 6 * 5 7 * 7 8 * 11 9 * 13 45 * 17 67 . 基数是素数，幂是数列中的元素。

反向映射是通过除法计算的 - 您可以将值除以2序列中的第一个元素等的次数。该值的最大素数告诉您序列的长度。

如果要0在序列中允许正数，则在将质数提高到幂时将所有元素加 1。或者使用 的幂2来给出序列的长度，然后开始对以 开头的元素进行编码3。

Goedel 在他的不完备性定理证明中使用了这样的编码。

正如 Kendall Frey 所说，不可能定义一个函数将每个无限的整数序列映射到不同的整数。这是康托尔证明自然数的幂集不可数的结果：您甚至不能将所有无限的元素序列从整数映射{true, false}到整数，更不用说整数的所有无限元素序列了。

对于更实用的方法，请考虑将整数序列编码为字节序列，而不是数字。一个有限的字节序列可以很容易地被认为是一个二进制值，因此它是一个数字，你只是没有真正使用它。您的示例序列的常见表示是字节序列：[1,6,7,8,9,45,67]，例如在 JSON 中使用。这是一个 136 位的数字。反转此映射的数学函数涉及 256 的算术模幂、数字 48 的减法、10 的乘法等:-)

于 2012-09-01T18:28:13.723 回答
2

假设您的序列被调用s ，我将定义len(n)为 n 中的位数。

那么你的结果的第一位数字是len(s[0])，后面的len(s[0])数字是数字s[0]；然后你追加len(s[1])and s[1]，依此类推。

这适用于最多 9 位数字的数字。

于 2012-09-01T16:23:42.277 回答
1

你不能，如果你的数字范围是无限的。

不可数自然数的幂集。这意味着您无法提供数字集和数字之间的映射。

如果您的数字被限制为 32 位，您可以做的是将这些数字连接成一个长二进制数，并将它们存储为字节序列，可能作为 BigNum。

于 2012-09-01T16:20:34.390 回答
1

这是上面 Steve Jessop 描述的Godel 编号的基本 PHP 实现：

<?php

$sec = array(5,9,8,4);

$n = count($sec);
$max = max($sec);

$enc = encode($sec);
$dec = decode($enc, $n, $max);

echo "Input sequence:  " . implode(",", $sec) . "\n";
echo "Output sequence: " . implode(",", $dec) . "\n";
echo "Godel number:    " . $enc;
echo (PHP_INT_MAX/$enc < 20 ? " - too big to decode.\n" : "\n");

function encode($sec) {
    $primes = array(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53);
    $enc = 1;
    $i = 0;
    foreach ($sec as $v) {
        $enc = $enc * pow($primes[$i], $v+1);
        $i++;
    }
    return $enc;
}

function decode($enc, $n, $max) {
    $primes = array(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53);
    $sec = array();
    for ($i = 0; $i < $n; $i++) {
        for ($v = 2; $v <= $max+1; $v++) {
            if ($enc/pow($primes[$i], $v) != round($enc/pow($primes[$i], $v))) {
                break;
            }
        }
        $sec[] = $v-2;
    }
    return $sec;
}

?>

此脚本仅适用于小序列中的小数字。它不能处理非常大的数字，我想与任何其他实现相同。存储连接它们的数字更加容易和高效：[01,05,15,17] -> 1051517。

于 2013-10-25T00:38:15.853 回答
0

更新以检查 0,1 案例。

用 001 分隔不同的数字。

为避免与号码中的 00 混淆，每次号码中出现 0 时，将其替换为 01。

要解码，除以 001。将所有 01 替换为 0。

于 2012-09-01T16:19:46.437 回答
0

这使用通用代码，例如Elias omega 编码（或任何前缀代码——但通用代码是具有一些理想属性的前缀代码）。前缀代码将位序列（即数字）编码为前缀，该前缀基本上提供了必要的信息来确定有多少位构成数字的其余部分。

1）用代码表示序列中的元素个数。2）然后使用代码来表示每个元素。

于 2014-08-14T03:31:23.517 回答
0

我想到的另一个答案。将每个数字编码为平衡的三进制，每个三元组有两位（例如，0=00；+1=01；-1=10）。剩余的位对（例如，11）是元素结束标记，重复用于序列结束。缺点：当预期值较大时，空间效率低于前缀代码；优点：1）空间效率更高，价值大多较小；2）编码/解码更简单；3) 直接表示负值。

于 2014-08-14T14:49:05.900 回答