Remove a dictionary key if it is a substring in any other key

Question

I'm learning Python. I've got a performance issue. For a single dictionary, I want to remove keys if

• The a key is a substring in another key

I don't want to remove keys if

• The key substring is itself

My keys are unique strings mostly between 3-50 characters in length. The dictionary I'm working with has 100,000 or more items, making billions of comparisons. Since this is an O(n^2) problem, should I stop trying to optimize this code? Or is there room to make headway here?

A dictionary is preferable, but I'm open to other types.

For example: 'hello' contains 'he' and 'ell'. I want to remove the keys 'he' and 'ell' while keeping 'hello'. I'd like to remove prefixes, suffixes, and key-substrings in the middle of other keys.

The keys are generated one-by-one and added to a dictionary. Then reduce_dict(dictionary) runs. My assumption is: a test while they're added to a dictionary would be as slow as a function testing after, as in the code below.

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

Given that your strings are somewhat small, you could store a hashset of all possible substrings for each key. That would enable you to, for a given substring, find all keys that have matching substrings in O(N) time, however the tradeoff is you'd be increasing thr time complexity of your insertions since you'd be constructing a set of substrings for each new key.

Answer 2

I think you can create a list of "good" keys (=those that are not substrings of others) in a slightly optimized way:

# 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']

Now the removal is trivial:

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

Answer 3

If instead of key2 in key (that is, "key2 is a substring of key") you change your requirement to "key2 is a prefix of key" (as your examples demonstrate), you can use a trie for efficient prefix checks. See this answer.

First define make_trie as in the answer above:

_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

Then define a function like in_trie from the answer above, but checking whether a key is a strict prefix of another key:

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

Finally, perform your deletions like so:

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

Or you can use dictionary comprehension:

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

If the dictionnary is static, IMHO it is no use optimising the operation : it will run only once, and in less time than you need to carefully optimise and test the optimisations.

If the dictionnary is dynamic, you could try to put a timestamp in value if it make sense of keep a list of keys that have already be cleaned. So when you run again your cleaning process, you have 2 sets of keys : the one that was processed one (size n1), and new keys size (n2). You only compare :

• a new key may be substring of old key
• a old key may be substring of new key
• a new key may be substring of new key

So you have n2 * (n2 + 2 * n1) comparisons. If n >> n2 it is O(n * n2 * 2).

Alternatively, if the addition of an element in dictionary is not in a time bounded operation (nor in a interactive one), you could test at each addition in O(2n) without nothing else to add (neither keeping keys, nor timestamp).

Indeed, if you cleanup your dictionnary once with a trivial O(n²) algorythm, and then control the keys whenever a new element is generated, you can safely assume that none of the existing keys can be a substring of another one. You just have to test :

• is the new key a substring of an existing key - n operations in worst case (but probably the most common one)
• is an existing key a substring of the new key - n operations in all cases.

The only requirement, is that you must never try to add a key, before the full operation of cleaning for the previous one is over. That may be evident if there only one thread in one process acceding to the dictionnary, if not you will need synchronization.

Answer 5

As the keys are string, you can use the find method to get the substring and delete them by keys.

If d is a dictionary,

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 will be then,

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