1
$\begingroup$

I am facing the following problem in a script I am trying to develop:

Given a string and a set of tokens, where the tokens are known and are overlapping (the set can contain the tokens 'a', 'b' and 'ab'), I need to split the string into a list of tokens from the set. I know there can be multiple ones, I don't need all of them, just a random one (obviously it is trivial to get an arbitrary one if I have all possible token lists).

The token set is known and guaranteed to have all possible characters of the input string, there is at a token which is equal to a single character for each possible input character.

Is it a known problem? If so, does it have known solutions? I am happy with adjacent literature I can use to jump-start my research.

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you really mean 'random' or do you mean 'arbitrary'? If 'random', what distribution on valid solutions do you require? I'm wondering if you just want to know one tokenization and you don't care which one. Also, what does 'guaranteed to have all possible characters of the input string' mean? Does it mean that, for every character that occurs in the string, there is a token containing just that single token in the set of tokens? Please edit your question accordingly. $\endgroup$
    – D.W. ♦
    Commented Oct 9, 2023 at 18:14
  • $\begingroup$ @D.W. added more details, but yes, your assumptions are correct. $\endgroup$
    – bracco23
    Commented Oct 10, 2023 at 11:27
  • 1
    $\begingroup$ Please don't use "EDIT:" or just append stuff at the end. Instead, revise your question to read well for someone who encounters it for the first time. For instance, you can remove use of the word "random" and replace it with what you actually mean. See cs.meta.stackexchange.com/q/657/755 $\endgroup$
    – D.W. ♦
    Commented Oct 10, 2023 at 16:36

1 Answer 1

Reset to default
1
$\begingroup$

This problem is often called the Word Break problem and is a classic exercise for dynamic programming.

Base case: if you don't have a string, it's a yes instance.

For every token, if the string ends with that token, remove that suffix from the string and recurse.

If no token is a suffix of your (non-empty) string, return false.

The running time is cubic (or more accurately the length of the string times number of tokens times length of the longest token). Perhaps.

A very simple recursive function with memoization in Python is given:

@cache
def wordbreak(string, tokens):
    if not string:
        return True
    canbreak = False
    for token in tokens:
        if string.endswith(token):
            if wordbreak(string.removesuffix(token), tokens):
                return True
    return False

Beware that it's slower than necessary.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, that's a good start! i'll try and find a way to get an arbitrary tokenization without having to get all of them, as I was hoping it would be a bit less intensive. $\endgroup$
    – bracco23
    Commented Oct 10, 2023 at 16:58
  • $\begingroup$ You obviously don't have to iterate through all tokens. In fact, if construct a prefix trie of your reversed tokens, you can iterate backwards in the text looking only at actual hits. The above code snippet is for educational purposes only. $\endgroup$
    – John Kemeny
    Commented Oct 10, 2023 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.