Recursive right-to-left segmenting (tokenizing) of strings in Python I want to segment a list of strings based on a custom list of words/forms, from right-to-left. Here I've illustrated it with made-up English examples, but the point is to segment/tokenize using a custom list of forms. (I was also wondering whether I could/should use NLTK tokenize for this, but it looked like that might be too complex for this use case).

What would be a good Pythonic way to do this (readable and efficient)? I managed to get something working, but I don't have much experience and I'm curious how this can be improved. The code below uses a recursive function to keep splitting the left element where possible, and a $ anchor in the regular expression to match the morphs only in string-final position.

phrases = ['greenhouse', 'flowering plants', 'ecosystemcollapse']
morphs = ['house', 'flower', 'system', 'collapse']

def segment(text):
    segmented_text = [match for match in re.split('(' + '|'.join(morphs) + ')' + '$', text) if match]
    if len(segmented_text) == 2:
        segmented_morphs.insert(0, segmented_text[1])
        segment(segmented_text[0])
    else:
        segmented_morphs.insert(0, segmented_text[0])

for phrase in phrases:
    segmented_morphs = []
    words = phrase.split()
    for word in reversed(words):
        segment(word)
    print(segmented_morphs)


Result (as desired):

['green', 'house']
['flowering', 'plants'] # here 'flower' should not be segmented
['eco', 'system', 'collapse']
Here are some general comments:


Having a function mutate a global variable is a bad practice. In this case, it may seem easy enough to reason about what is going on, but I guarantee that at some point it will lead to an insidious bug that is hard to track down because you have no idea who is changing the global variable and when.
Recursion is not necessary here; it over-complicates the solution and may make it difficult to change/update the code.


The code itself is rather concise, but the weird data-flow out of the function makes it difficult to understand what's going on. This is complicated because the function is recursive and so you then have to keep track of the calling stack when figuring out how segmented_morphs is being changed.

I don't think the re module is really necessary here, I bet that it is heavier that just searching for strings and doesn't seem to offer any benefit. I've kept it for now, but I might offer another solution without it.

Here's how I would approach the problem:

import re

def segment_word(word, morphs):
    regex = re.compile('(' + '|'.join(morphs) + ')' + '$')
    splitter = lambda s: (regex.split(s) + [None])[:2]

    segments = []
    word, end = splitter(word)
    while end is not None:
        segments.append(end)
        word, end = splitter(word)

    if word:
        segments.append(word)

    return segments[::-1]

def segment_phrase(phrase, morphs):
    return [s for w in phrase.split() for s in segment_word(w, morphs)]


Here's a version without re, I'm not super happy about either. Neither version seems particularly elegant.

def segment_word(word, morphs):
    segments = []
    previous_length = -1
    while len(word) != previous_length:
        previous_length = len(word)
        for morph in morphs:
            if word.endswith(morph):
                segments.append(morph)
                word = word[:-len(morph)]

    if word:
        segments.append(word)

    return segments[::-1]