仅过滤包含给定数字集的数字序列

Question

我有一个很大的数字字符串列表,就像这一个.单个字符串相对较短(比如小于50位).

data = [
  '300303334',
  '53210234',
  '123456789',
  '5374576807063874'
]

我需要找到一个有效的数据结构(速度优先,内存秒)和算法,它只返回由给定的一组数字组成的字符串.

示例结果:

filter(data, [0,3,4]) = ['300303334']
filter(data, [0,1,2,3,4,5]) = ['300303334', '53210234']

数据列表通常适合内存.

Answer 1

考虑一个函数 f，它为每个字符串构造一个位掩码，如果数字 i 在字符串中，则设置位 i。

例如，

f('0')    = 0b0000000001
f('00')   = 0b0000000001
f('1')    = 0b0000000010
f('1100') = 0b0000000011

然后我建议为每个位掩码存储一个字符串列表。

例如，

Bitmask 0b0000000001 -> ['0','00']

一旦准备好此数据结构（与原始列表的大小相同），您就可以通过访问其中位掩码是过滤器中数字子集的所有列表来轻松访问特定过滤器的所有字符串。

因此，对于过滤器 [0,3,4] 的示例，您将从以下位置返回列表：

Strings containing just 0
Strings containing just 3
Strings containing just 4
Strings containing 0 and 3
Strings containing 0 and 4
Strings containing 3 and 4
Strings containing 0 and 3 and 4

Python 代码示例

from collections import defaultdict
import itertools

raw_data = [
  '300303334',
  '53210234',
  '123456789',
  '5374576807063874'
]

def preprocess(raw_data):
    data = defaultdict(list)
    for s in raw_data:
        bitmask = 0
        for digit in s:
            bitmask |= 1<<int(digit)
        data[bitmask].append(s)
    return data

def filter(data,mask):
    for r in range(len(mask)):
        for m in itertools.combinations(mask,r+1):
            bitmask = sum(1<<digit for digit in m)
            for s in data[bitmask]:
                yield s

data = preprocess(raw_data)

for a in filter(data, [0,1,2,3,4,5]):
    print a