Word bucketing in Python

Question

First I'm not sure what this is called formally but whatever.

Basically I need to form "wildcard buckets". I think the best way to explain what I need to do is to take an example. For instance, say I have the three words "aaa", "aab", and "baa".

Let me use * as the wildcard. Then from aaa I can form -aa, a-a, aa-, --a, a--, a-a, and ---. I then add these to a dictionary where the keys are the buckets and values are sets of (complete) words that fit these buckets. I repeat for all my words. So in the end I get that, for instance, -a- fits all three of the example words that I have above.

I have working code, but it is very slow in forming these buckets when I have a word list that has hundreds of thousands of words.

for numberSpaces in range(0, len(word) + 1):  # loop through all spaces of word
    buckets = itertools.combinations(range(0, len(word)), numberSpaces)
    for indicesToReplace in buckets:  # for each index in this combination
        newWord = word  
        for index in indicesToReplace:  # replace character with "*"
            newWord = newWord[0:index] + "*" + newWord[index + 1:]
        if newWord not in bucketDictionary.keys(): # Add to dictionary
            bucketDictionary[newWord] = set()
        bucketDictionary[newWord].add(word)

I would like to know how to best optimize this code. I've tried recursion but I'm not sure if that is any better than this iterative method.

Thank you!

Answer 1

I think the way to optimize it is to try an entirely different approach -- given a pattern that matches all the words in a set, and a new word to add to the set, how do you modify the pattern to match the new word as well? Simple answer: as long as the non-wild characters in the pattern match the new word, leave them; otherwise change the pattern to have a wildcard at that position. You could implement this either recursively or iteratively.

from typing import List

WILD = "*"

def build_common_pattern(words: List[str]) -> str:
    """Build a pattern matching all input words.
    WILD matches any single character."""
    pattern = words[0]
    for word in words:
        assert len(word) == len(pattern)
        for i in range(len(word)):
            assert word[i] != WILD
            if pattern[i] != word[i]:
                pattern = pattern[:i] + WILD + pattern[i+1:]
    return pattern

print(build_common_pattern(["aaa", "aab", "baa"]))

This is also a potential use case for functools.reduce:

def build_common_pattern(words: List[str]) -> str:
    """Build a pattern matching all input words.
    WILD matches any single character."""
    def union(a: str, b: str) -> str:
        result = ""
        assert len(a) == len(b)
        for i in range(len(a)):
            result += a[i] if a[i] == b[i] else WILD
        return result

    return reduce(union, words)

Answer 2

Starting with the answer by @SamStafford, you could take this even further and make it a nice inheritance exercise by using a sub-class of str that compares true to any other character:

class WildCard(str):
    def __eq__(self, other):
        # all other strings are equal to the wildcard
        return isinstance(other, str)

STAR = WildCard("*")

def build_common_pattern(words):
    """Build a pattern matching all input words.
    WILD matches any single character."""
    pattern = list(words[0])
    for word in words:
        assert len(word) == len(pattern)
        pattern = [p if c == p else STAR for c, p in zip(word, pattern)]
    return "".join(pattern)

This way you avoid having to do many string slices, although this makes it only perform better for really large strings (patterns with each character having a 50% chance to be a wildcard and a length of more than 1k characters):

---

However, this does not solve the exact problem your code solves, since it does not build a dictionary mapping patterns to words that match it. For this I can only give you some stylistic advice on how to improve your code.

• Python has an official style-guide, PEP8, which recommends lower_case for functions and variables.

• You can use collections.defaultdict(set) to avoid having to check if you have seen a pattern before.

• range starts by default at 0, and so do slices.

• Use the same way I used above to avoid string slices and iterate over the word/pattern instead.

from collections import defaultdict
from itertools import combinations

def build_buckets(words):
    buckets_dict = defaultdict(set)
    for word in words:
        for number_spaces in range(len(word) + 1):  # loop through all spaces of word
            buckets = combinations(range(len(word)), number_spaces)
            for indices in map(set, buckets):  # for each index in this combination
                new_word = "".join(c if i not in indices else "*"
                                   for i, c in enumerate(word))
                buckets_dict[new_word].add(word)
    return buckets_dict

Note that this is probably a futile effort, since if there were no wordlist, the number of patterns grows exponentially. Since you do have a wordlist it does not, but the number of patterns will still increase rapidly. For 15 words of length 15, your code already takes almost 2 seconds.