Segmenting strings with a dictionary

Word segmentation splits a string written without spaces, such as a hashtag, into words from a dictionary. Two questions come with it: can the string be split at all, and in which ways? Both have a table over the cut positions between letters, where each position asks whether, or in how many ways, the rest of the string can be split. Listing every way is different, because the number of segmentations can grow exponentially with the length, so the listing must check its size before it builds anything. This lesson poses both questions on original hashtags.

Two problems: can a hashtag be split, and in which ways?

Problem A, can it be split? Given a string of lowercase letters and a dictionary, decide whether the string can be cut into dictionary words, each word usable any number of times. Limits: 1 ≤ len(text) ≤ 10,000, up to 1,000 words of 1 to 20 letters.

Problem B, every segmentation. Return every way to cut the string into words, each as words separated by spaces. The inputs are promised to have at most 10,000 segmentations.

• monsoonsale with the words mon, monsoon, soon, so, on, sale, sal and ale can be split in 3 ways: mon so on sale, mon soon sale and monsoon sale.
• goldencoin with gold, golden, coins and den cannot be split: coin is not a word, only coins is.

The brute force, and why it fails

Try every dictionary word that the rest of the string starts with, and every way on from there:

def splits_brute(text, words):
    """Tries every dictionary word that the rest of the text starts with, and every way on from there."""
    calls = 0

    def split_from(i):
        nonlocal calls
        calls += 1
        if i == len(text):
            return [[]]  # the empty rest has one segmentation: no more words
        found = []
        for word in words:
            if text.startswith(word, i):
                found += [[word] + rest for rest in split_from(i + len(word))]
        return found

    return split_from(0), calls


tags = [
    ("monsoonsale", ["mon", "monsoon", "soon", "so", "on", "sale", "sal", "ale"]),
    ("goldencoin", ["gold", "golden", "coins", "den"]),
]
for text, words in tags:
    found, calls = splits_brute(text, words)
    shown = "; ".join(" ".join(s) for s in found) or "no segmentation"
    print(f"{text}: {shown} ({calls} calls)")

for n in (10, 15, 20):
    found, calls = splits_brute("a" * n + "b", ["a", "aa", "aaa"])
    print(f"{n} a's and a b, words a, aa, aaa: {len(found)} segmentations after {calls:,} calls")

monsoonsale: mon soon sale; mon so on sale; monsoon sale (12 calls)
goldencoin: no segmentation (3 calls)
10 a's and a b, words a, aa, aaa: 0 segmentations after 600 calls
15 a's and a b, words a, aa, aaa: 0 segmentations after 12,640 calls
20 a's and a b, words a, aa, aaa: 0 segmentations after 266,079 calls

The hashtags are quick, but a string of a’s ending in b, with the words a, aa and aaa, has no segmentation at all and still makes the search try every way to cut the a’s: 600 calls for 10 a’s, 12,640 for 15 and 266,079 for 20, about 21 times more for every five letters. At 10,000 letters that is hopeless.

What to notice

• Whether the rest can be split depends only on where it starts. In the diagram, three different paths reach position 7, and each continues the same way.
• A word ends at most 20 letters after it starts, so each position has at most 20 candidate words, whatever the length of the string.
• The output of Problem B can be exponential. Thirty a’s with the words a, aa and aaa have more than 50 million segmentations, so a listing has to know its size before it starts.

Can it be split: the table over cut positions Pro: opens with a Pro, Premium or Ultimate pass