algorithm - 有没有一种有效的方法来计算比特流中 1 的密度？

Question

我正在尝试想出一种比较二进制数组(从长度 1 到长度 1000)以确定 1 的相对“密度”的好方法。

01010101 的密度低于 00011011，因为 1 的分布更广。

同样，总数也很重要。因此，11111111 比 11 差(更高的值)，尽管两者都是 100% 1。 (将第二个填充为 00000011 可以解决此问题，但会导致以后出现问题)。

该算法将在嵌套循环中使用(遗传程序中的评分方法)，所以我目前的 O(n^2) 时间和 O(n) 空间的解决方案不会削减它!

将使用以下数据(来自将在第 1 代中剔除的糟糕算法)解释我目前使用的两种脏方法:

Stream      Result A   Result B (8+7+6+5+4+3+2)
A: 001000       1.17          7  1+1+1+1+1+1+1
B: 000          0.00          0  0+0+0+0+0+0+0
C: 1011011      5.57         25  5+5+4+4+3+2+2
D: 1011         4.25         19  3+3+3+3+3+2+2
E: 1            2.00          7  1+1+1+1+1+1+1
F: 1001010      2.29         16  3+3+3+2+2+2+1
G: 11111111    16.00         35  8+7+6+5+4+3+2
H: 1001001      2.29         14  3+3+2+2+2+1+1
I: 10101        2.80         17  3+3+3+3+2+2+1

结果 A: 计算方法是 1 的平方数除以总位数，再加上连续 1 的最大长度。所以对于 C，7 个中有 5 个是 1，最大分组为 2，所以 2+(5*5/7)。这种方法的问题是 F 和 H 是匹配的，尽管 F 更“聚集”。好处是它在 O(n) 中运行，并且通过保持运行总计具有 O(1) [4 个变量:num1s、totalnum、maxBunch、bunchSoFar] 的空间。

结果 B: 计算是从 n = 最大大小开始(在本例中为 8，但在我的程序中为 900)，并计算通过分组 n 可以捕获的 1 的最大数量连续的数字在一起。然后将其添加到通过将 n-1 个连续数字组合在一起捕获的最大值。我在 2 的分组处停止，因为 1 的分组对于任何非零数组总是返回 1。这有利于将 H 正确设置为低于 F 的分数，但需要时间 O(n^2) 和空间 O(n)，因为整个数组需要随着更多的数字被添加而被存储。 (压缩可以帮助空间，但会被时间成本所抵消)。

结论我正在寻找比结果 B 更有效的方法，但可以提供比结果 A 更详细的排序。我试图用谷歌搜索，但“位密度”指的是完全不同的东西!我将继续致力于此，但我认为，与此同时，我会询问是否有人碰巧知道一种我不知道其名称的算法。

Answer 1

代码在 python3 中，方法是在读取 0 时从最终值减去，在读取 1 时添加到最终值。考虑到 1 和 0 的接近程度，对于每个连续的 0，您减去一个更大的数字，对于每个连续的 1，您添加一个更大的数字。例如对于 5 位数:

00011 将计算 -1、-2、-3、+1 和 +2

同时

00101 将计算 -1。 -2、+1、-1 和 +1

不是用 0 填充，而是使用 str = str.lstrip("0") 删除前导 0

将总和初始化为 sum = 8 - len(bits)(在你的例子中是 sum = 900 - len(bits))。

然后 sum = -((sum * (sum + 1))/2)

然后您可以使用以下 for 循环遍历 O(n)，使用的额外空间为 O(1):

    prev = 0
    prev_a = '0'
    for x in str:
        if x == '0':
            prev -= 1
            if prev_a == '0':
                sum += prev
            else:
                sum += -1
                prev = -1
            prev_a = '0'
        else:
            prev += 1
            if prev_a == '1':
                sum += prev
            else:
                sum += 1
                prev = 1
            prev_a = '1'
    print(str, sum)  

输出如下:

10000000 :   -27.0
001000 :     -15.0
000 :        -36.0
1011011 :    4.0
1011 :       -7.0
1 :          -27.0
1001010 :    -3.0
11111111 :   36.0
1001001 :    -4.0
10101 :      -5.0

您可以在末尾的总和上加上 36 以获得所有正值。

数字越大表示 1 的密度越好。