Most effective search algorithm for guessing list of strings via function returning bool if substring is in list using Python

Question

I trying to figure out the most effective way to accomplish this task:

A function, check(), contains a list of strings. Calling the function with a string as argument, will return True if the argument string is part of any of the strings in the list. False if not.

I want to guess the content of that list in as few checks as possible, using the check() function, knowing only the charset (alphanumeric + -_@.[space]) and displaying the progress (I'm using tqdm).

My code does accomplish this, but it is very inefficient. For example if "strings" is in the list, it performs checks for both "tring", "string" and "trings", which I feel like could be optimized.

Here's my code:

import string
from tqdm import tqdm


def check(text):
    """Returns True if input text is part of any of the strings in the list"""
    strings = ["we ", "_want", "t0", "gu@ess", "these-", "str1ngs"]
    return any(text in substring for substring in strings)


def remove_partials(input_list):
    """Removes strings from the input list they are a substring of any other string in the list"""
    substrings = []
    for item in input_list:
        for item_2 in input_list:
            if item != item_2 and item_2 in item:
                substrings.append(item_2)

    for partial in substrings:
        try:
            input_list.remove(partial)
        except ValueError:
            pass

    return input_list


charset = f"{string.ascii_lowercase}{string.digits}@-_. "
known = charset
tried = []
result = []


while len(known) > 0:
    found = []

    for prefix in (pbar_2 := (tqdm(known, leave=False))):
        pbar_2.set_description(prefix)

        for char in (pbar := (tqdm(charset, leave=False))):

            substring = f"{prefix}{char}"
            pbar.set_description(char)

            if substring not in tried:

                if check(substring) and substring not in found:
                    tqdm.write(f"{substring}")
                    found.append(substring)
                    result.append(substring)

            tried.append(substring)

    known = found

print()
print(remove_partials(result))

Answer 1

You can do this more efficiently by using a trie.

Let's start from the beginning. Imagine the solution is ['we', 'these'].

You can call your check method with all of your initial characters, and it will tell you that only the characters: 'weths' are in the solution.

Then you can check for two character sequences, at the moment you're currently going back to the full set of initial characters, but you don't need to do this, you know that only the characters 'weths' are possible (+ the empty case where you've found a suffix. So you can just search for 'ww, we, wt, wh, ws, ew, ...' and so on.

After this you'll have the following combinations:

• 'we', 'e$', 'th', 'he', 'es', 'se' (where $ means no extension matched - i.e. a suffix)

Now we can try and extend again. But here we have a bit more of an advantage. When we look at the word 'we' we know that it must end in a valid two-letter sequence starting with 'e', i.e. 'es' or 'e$', so we can just try 'wes', and then when that doesn't work we know we have 'we$', part of the solution. We can repeat this logic with all the remaining sequences:

• 'we' -> either 'wes' or 'we$'
• 'th' -> either 'the' or 'th$
• 'he' -> either 'hes' or 'he$'
• 'es' -> either 'ese' or 'es$'
• 'se' -> either 'ses' or 'se$'

Once finished we're left with the following:

'we$', 'e$', 'the', 'hes', 'ese', 'se$'

We can drop the 'e$' as it's a substring of 'we$' and 'se$' and you're only looking for a minimal set of strings (I assume).

This brings us onto our third round, and at this point we can go through again, skipping complete words like 'we$'. But this time we can look at the last two letters of each word to find our next options:

• 'we$' Complete
• 'the' -> 'thes' or 'the$'
• 'hes' -> 'hese' or 'hes$'
• 'ese' -> 'ese$' only

This gives us: 'we$', 'e$', 'thes', 'hese', 'ese$', 'se$'

Now our fourth round:

• 'thes' -> 'these' or 'thes$'
• 'hese' -> 'hese$' only

And finally:

• 'these' -> 'these$' only

This gives us a list of valid suffices:

['we$', 'e$', 'these$', 'hese$', 'ese$', 'se$']

Which we can deduplicate as you did above.

In terms of implementation - I'd create a trie as a nested dictionary structure, with methods to add words and identify which possible continuations words have:

from collections import defaultdict


def recursive_factory():
    return defaultdict(recursive_factory)


class Trie:
    def __init__(self):
        self._lookup = defaultdict(recursive_factory)
    
    def _add_string(self, string):
        lookup = self._lookup
        for char in string:
            lookup = lookup[char]
            
    def add_word(self, word):
        for offset in range(len(word)):
            self._add_string(word[offset:])
    
    def add_words(self, words):
        for word in words:
            self.add_word(word)
    
    def get_valid_next_chars(self, prefix=''):
        lookup = self._lookup
        for char in prefix:
            lookup = lookup[char]
        return set(lookup.keys())
    

Then we just need to go through the steps above (I created a helper class to store the final result).

class WordList:
    def __init__(self):
        self._suffices = set()
    
    def add_suffix(self, suffix):
        to_drop = set()
        for old_suffix in self._suffices:
            if old_suffix in suffix:
                to_drop.add(old_suffix)
        self._suffices -= to_drop
        self._suffices.add(suffix)
    
    def add_suffices(self, suffices):
        for suffix in suffices:
            self.add_suffix(suffix)
        
    def words(self):
        return tuple(self._suffices)


def next_guesses(valid_guesses, trie):
    for guess in valid_guesses:
        for char in trie.get_valid_next_chars(prefix=guess[1:]):
            yield guess + char

def solve(initial_guesses, check, trie=None, word_list=None):
    if trie is None:
        trie = Trie()
    if word_list is None:
        word_list = WordList()
    
    valid_guesses = [guess for guess in initial_guesses if check(guess)]
    if valid_guesses:
        trie.add_words(valid_guesses)
        word_list.add_suffices(valid_guesses)
        solve(next_guesses(valid_guesses, trie), check, trie=trie, word_list=word_list)
    return word_list.words()

All in all this algorithm is about 200x faster on my machine. It can be made faster still by increasing the speed of the check function (which can also be very efficiently solved with a trie). But at this point we're only calling check ~360 times compared to over 4000.

Answer 2

This is my first answer on this site.

Without changing the algorithm itself, we can improve performance by using set instead of list to hold and check for an existing item. On my machine, that cut about 33% off execution time.

Also, worth noting that while len(known) > 0 add while known will do the same; the latter is faster and more pythonic.

import string
from tqdm import tqdm


def check(text):
    """Returns True if input text is part of any of the strings in the list"""
    strings = ["we ", "_want", "t0", "gu@ess", "these-", "str1ngs"]
    return any(text in substring for substring in strings)


def remove_partials(input_list):
    """
    Removes strings from the input list they are a substring of any other string in the list
    """
    substrings = set()
    for item in input_list:
        for item_2 in input_list:
            if item != item_2 and item_2 in item:
                substrings.add(item_2)

    return input_list - substrings


charset = f"{string.ascii_lowercase}{string.digits}@-_. "
known = charset
tried = set()
result = set()


while len(known) > 0:
    found = set()

    for prefix in (pbar_2 := (tqdm(known, leave=False))):
        pbar_2.set_description(prefix)

        for char in (pbar := (tqdm(charset, leave=False))):

            substring = f"{prefix}{char}"
            pbar.set_description(char)

            if substring not in tried:
                tried.add(substring)
                if check(substring) and substring not in found:
                    tqdm.write(f"{substring}")
                    found.add(substring)
                    result.discard(prefix)
                    result.add(substring)

    known = found

print()
print(remove_partials(result))

Edit 1

We can reduce the number of checks of chars that never used by adding charset = "".join(char for char in charset if check(char)) before the loop.

Edit 2

while being faster using python's dis

We can look what python does on while len(x) > 0 compare to while x by using dis. As we know, fewer operation means faster code :)

In [1]: import dis

In [2]: def x1(l):
   ...:     while l:
   ...:         pass
   ...:

In [3]: def x2(l):
   ...:     while len(l) > 0:
   ...:         pass
   ...:

In [4]: dis.dis(x1)
  2     >>    0 LOAD_FAST                0 (l)
              2 POP_JUMP_IF_FALSE        6

  3           4 JUMP_ABSOLUTE            0
        >>    6 LOAD_CONST               0 (None)
              8 RETURN_VALUE

In [5]: dis.dis(x2)
  2     >>    0 LOAD_GLOBAL              0 (len)
              2 LOAD_FAST                0 (l)
              4 CALL_FUNCTION            1
              6 LOAD_CONST               1 (0)
              8 COMPARE_OP               4 (>)
             10 POP_JUMP_IF_FALSE       14

  3          12 JUMP_ABSOLUTE            0
        >>   14 LOAD_CONST               0 (None)
             16 RETURN_VALUE

Edit 3

I decided to try implement this solution using DFS instead of the BFS that your code does here. To test the code more accurate, I removed all prints (They are slowing the code a lot!).

The results are a little bit better but I think will be different with different words.

In [1]: %timeit %run codereview281798_dfs.py
3.06 ms ± 10.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [2]: %timeit %run codereview281798_bfs.py
3.24 ms ± 9.13 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

And here is the code:

import string
from tqdm import tqdm


def check(text):
    """Returns True if input text is part of any of the strings in the list"""
    strings = ["we ", "_want", "t0", "gu@ess", "these-", "str1ngs"]
    return any(text in substring for substring in strings)


def remove_partials(input_list):
    """
    Removes strings from the input list they are a substring of any other string in the list
    """
    substrings = set()
    for item in input_list:
        for item_2 in input_list:
            if item != item_2 and item_2 in item:
                substrings.add(item_2)

    return input_list - substrings


CHARSET = f"{string.ascii_lowercase}{string.digits}@-_. "


def find_words():
    charset = "".join(char for char in CHARSET if check(char))
    return remove_partials(dfs_find_words("", charset))


def dfs_find_words(prefix, charset):
    found_words = set()
    is_end_of_word = True
    for char in charset:
        substring = f"{prefix}{char}"
        if check(substring):
            is_end_of_word = False
            words = dfs_find_words(substring, charset)
            found_words = found_words.union(words)
    if is_end_of_word:
        found_words.add(prefix)
    return found_words


def find_words_1():
    charset = "".join(char for char in CHARSET if check(char))
    known = charset
    tried = set()
    result = set()

    while known:
        found = set()
        for prefix in known:
            for char in charset:
                substring = f"{prefix}{char}"
                if substring not in tried:
                    tried.add(substring)
                    if check(substring) and substring not in found:
                        found.add(substring)
                        result.discard(prefix)
                        result.add(substring)

        known = found
    return remove_partials(result)

---

Note: I think that Trie would be a good use here, but I don't see the immediate use of it

Answer 3

Here are a couple of hints to help you out:

1. The list of strings is not changing, so you can define it globally
2. Comparing a string of length n against m strings of length n each will have O(n*m) complexity
3. You can preprocess and create a trie for the strings. That will reduce the searching complexity to O(n), since you just need to check for a match.