6

我正在尝试找到一种快速算法来搜索多个位数组的最长前缀。在我的应用程序中，这些位数组可以无限长且长度可变。例如，如果我有这些位数组：

0b1011001
0b1001101
0b1001010
0b1010100

最长的前缀是 10。我目前正在对位数组进行 ORing 和 NAND 运算，以找到它们共同的 0 和 1，并将结果一起 XOR。

OR
0b1011111

NAND
0b0111111

XOR
0b1100000

有没有更快的解决方案？

4

4 回答 4

2

关于你的方法

它在位数组的数量上可以很好地缩放（线性）。

它不能很好地根据位数组的大小进行缩放，理想情况下，它应该根据公共前缀的长度而不是位数组的大小进行缩放。

在低水平

对位数组中单个字节/字的位操作应该比一次一个地沿着位走快得多。（但不确定 Python 可以为您提供多少低级控制）。

第一个建议

如果这是像 C 这样的低级语言，我会以与您类似的方式解决这个问题，但会从其他答案中获得一些想法。

在我的示例中，我将假设计算机是 64 位机器。

我从（OR NAND XOR）每个位数组的前 64 位开始，（这些是 64 位机器上的基本操作，复杂度仅为 O(# of arrays)）。

然后快速找到结果中第一个设置位的位置，（大多数计算机都有一些内置的快速方法，或者至少在优化的汇编代码中，对于 C，如果有设置位，则返回该值。

否则，在每个位数组的接下来的 64-127 位上重复。

（您将需要以某种方式处理不同长度的位数组，可能通过找到该组的最小长度位数组，然后将其用作最大值。）

这种方法的好处是它在位数组的数量上是线性的，并且是公共前缀的长度是线性的。

第二个建议

如果有大的位数组，您可以通过使用并行来获得加速。

首先，您可以在运行 NAND 的同时运行 OR。

有了更多的独创性，您可以应用以下内容：

如果我有 4 位数组 A、B、C、D

而不是 (((A OR B) OR C) OR D)

我可以做（A 或 B）或（C 或 D）。

在这两种情况下，都会执行相同数量的 OR。

但是第二种方法可以有效地并行化（实际上第二种方法在单核机器上可能更快，因为通常CPU实际上会有多个ALU。）

写出逻辑有点棘手，因为您不能使用单个 for 循环和单个临时变量来保存 OR 的结果。

您可以想象将子结果存储在一个长度为位数组数量一半的数组中。将 A OR B 的子结果存储在 array[0] 中，将 C OR D 的子结果存储在 array[1] 中，然后执行 array[0] OR array[1]。（并且您可以将该结果存储在一个长度为一半的新数组中，或者覆盖数组中的值以节省空间和内存分配）。

将工作划分为足够大的块，以使整个计算机保持忙碌而不会引入太多开销。

使用足够多的处理器，您可以接近位阵列数量的对数的复杂性，而不是线性的。但在实践中，在 6 核机器上获得 5 倍的加速可能会相当不错。

于 2012-08-04T07:56:48.173 回答
1

您不需要对所有阵列进行 ORing 或 NAND 运算（这将非常昂贵，因为它们的长度是任意的）。当您发现第一个 mismatch 时，您可以从左到右停止扫描阵列。这将是O(kn)，其中n是数组的数量，k是公共前缀的长度。

我的 python 很糟糕，所以我将只给出一个非常简单的示例，其中包含 2 个固定相等长度的数组，以便清楚地说明：

a = [1,0,1,1,0,0,1]
b = [1,0,1,1,0,1,1]

for x in xrange(0,7):
    if a[x] != b[x]:
        print a[0:x]
        break

output:
[1, 0, 1, 1, 0]

显然你必须解决这个问题，如果你理解代码背后的逻辑，我想我会很容易。

  • 在所有数组的第 x 位上迭代x，直到发现不匹配（即数组不具有所有相同的位值），或者直到最短数组的末尾
  • 输出 array1 的前x位。
于 2012-08-02T12:55:17.307 回答
0

在某些情况下，最佳解决方案是使用复杂度为 O(n) 的前缀树，其中 n 是二进制字符串的共享前缀的总和，但系数很大。

于 2012-08-02T11:51:21.540 回答
0

假设您有输入字符串 s1,s2,s3 ...

  1. 让 s = commonSubString(s1,s2)
  2. 对于 i=3..n
    1. s = commonSubString(s,s2)
  3. 返回

在最坏的情况下 s1 和 s2 可以相同，在这种情况下，您可以使用启发式方法（例如，首先将 s 的初始长度限制为 k=100。如果最终 s 的长度仍然为 k=100，则重复整个过程，但从每个字符串的位置 k+1 开始）。

于 2012-08-02T12:07:58.150 回答