如果字典中的键是其他任何键的子串，则移除该键

Question

我正在学习Python，遇到了一个性能问题。我想从一个字典中删除一些键，条件是：

• 某个键是另一个键的子串

但如果这个子串就是它自己，我就不想删除。

我的键都是独特的字符串，长度大多在3到50个字符之间。我现在处理的字典有10万个以上的项目，这样会进行数十亿次比较。由于这是一个O(n^2)的问题，我应该停止尝试优化这段代码吗？还是说还有改进的空间？

我更倾向于使用字典，但也愿意尝试其他类型。

举个例子：'hello'包含了'he'和'ell'。我想删除'he'和'ell'这两个键，但保留'hello'。我希望能删除前缀、后缀，以及其他键中间的子串。

这些键是一个一个生成并添加到字典中的。然后会运行reduce_dict(dictionary)。我认为在添加到字典时进行测试和在之后进行测试的速度是一样的，就像下面的代码所示。

def reduce_dict(dictionary):
    reduced = dictionary.copy()
    for key in dictionary:
        for key2 in dictionary:
            if key != key2:
                if key2 in key:
                    reduced.pop(key2, 0)
    return reduced

Answer 1

因为 keys 是字符串，所以你可以用 find 方法来找到 substring，然后通过这些键来 delete 它们。

如果 d 是一个字典，

d = {'hello': 1, 'he': 2, 'llo': 3, 'world': 4, 'wor': 5, 'ld': 6, 'python': 2.7}

for key in d.keys():
    for sub in d.keys():
        if key.find(sub) >= 0:
            if key == sub:
                continue
            else:
                del(d[sub])

那么 d 将会是，

{'python': 2.7, 'world': 4, 'hello': 1}

Answer 2

如果字典是静态的，我觉得优化操作是没什么意义的：它只会运行一次，而且所需的时间比你仔细优化和测试这些优化的时间要短。

如果字典是动态的，你可以考虑在值中加入一个时间戳，或者保持一个已经清理过的键的列表。这样，当你再次运行清理过程时，你就有两组键：一组是之前处理过的（大小为 n1），另一组是新的键（大小为 n2）。你只需要比较：

• 一个新键可能是旧键的子串
• 一个旧键可能是新键的子串
• 一个新键可能是另一个新键的子串

这样你就有 n2 * (n2 + 2 * n1) 次比较。如果 n 远大于 n2，那就是 O(n * n2 * 2)。

另外，如果向字典中添加元素的操作不是时间限制的（也不是交互式的），你可以在每次添加时以 O(2n) 的复杂度进行测试，而不需要其他的操作（比如保持键或时间戳）。

实际上，如果你用一个简单的 O(n²) 算法清理一次字典，然后在生成新元素时检查键，你可以安全地假设现有的键之间不会是子串关系。你只需要测试：

• 新键是否是现有键的子串 - 在最坏的情况下需要 n 次操作（但这可能是最常见的情况）
• 现有键是否是新键的子串 - 在所有情况下都需要 n 次操作。

唯一的要求是，你绝对不能在前一个清理操作完成之前尝试添加新键。如果只有一个线程在一个进程中访问字典，这一点可能很明显；如果不是，你就需要进行同步处理。

Answer 3

如果你把需求从 key2 in key（也就是“key2 是 key 的一部分”）改成“key2 是 key 的开头部分”（就像你的例子所示），那么你可以使用一种叫做 字典树 来高效地检查开头部分。可以参考 这个回答。

首先，像上面的回答那样定义 make_trie：

_end = '_end_'

def make_trie(*words):
    root = dict()
    for word in words:
        current_dict = root
        for letter in word:
            current_dict = current_dict.setdefault(letter, {})
        current_dict = current_dict.setdefault(_end, _end)
    return root

然后定义一个函数，类似于上面回答中的 in_trie，但要检查一个键是否是另一个键的 严格前缀：

def is_strict_prefix_of_word_in_trie(trie, word):
   current_dict = trie
   for letter in word:
       if letter in current_dict:
           current_dict = current_dict[letter]
       else:
           return False
   else:
       if _end in current_dict:
           return False # it's actually in the trie
       else:
           return True # it's a strict prefix of a word in the trie

最后，像这样进行删除操作：

def reduce_dict(dictionary):
    trie = make_trie(dictionary.keys())
    reduced = dictionary.copy()
    for key in dictionary:
       if is_strict_prefix_of_word_in_trie(trie, key):
           reduced.pop(key, 0)
    return reduced

或者你可以使用字典推导式来实现：

def reduce_dict(dictionary):
    trie = make_trie(dictionary.keys())
    return {key: value for (key, value) in dictionary \
            if not is_strict_prefix_of_word_in_trie(trie, key)}

Answer 4

假设你的字符串比较短，你可以为每个键存储一个所有可能子字符串的集合。这样的话，当你有一个子字符串时，就可以在O(N)的时间内找到所有包含这个子字符串的键。不过，这样做的代价是，你在插入新键的时候会增加时间复杂度，因为你需要为每个新键构建一个子字符串的集合。

Answer 5

我觉得你可以用一种稍微优化的方法来创建一个“好”的键的列表（也就是那些不是其他键的子串的键）：

# keys = yourDict.keys(), e.g.
keys = ['low', 'el', 'helloworld', 'something', 'ellow', 'thing', 'blah', 'thingy']

# flt is [[key, is_substring],...] sorted by key length reversed
flt = [[x, 0] for x in sorted(keys, key=len, reverse=True)]

for i in range(len(flt)):
    p = flt[i]
    if p[1]:  # already removed
        continue
    for j in range(i + 1, len(flt)): # iterate over shorter strings
        q = flt[j]
        if not q[1] and q[0] in p[0]: # if not already removed and is substring
            q[1] = 1  # remove

goodkeys = set(x[0] for x in flt if not x[1])
print goodkeys # e.g ['helloworld', 'something', 'thingy', 'blah']

现在，删除这些键就变得简单了：

newdict = {k:olddict[k] for k in goodkeys}