Tree string to bracketed string

Question

Let's say I have a tree string for a sentence:

s = "(TOP (S (NP-TMP (NP (DT This) (NN time)) (ADVP (RP around))) (NP-SBJ (PRP they)) (VP (VBP 're) (VP (VBG moving) (ADVP (RB even) (RBR faster))))))"

I want to convert it into a bracketed structure like this:

"(((This time)(around))(they)(('re)((moving)(even faster))))"

I tried to do the following:

import nltk

s = "(TOP (S (NP-TMP (NP (DT This) (NN time)) (ADVP (RP around))) (NP-SBJ (PRP they)) (VP (VBP 're) (VP (VBG moving) (ADVP (RB even) (RBR faster))))))"
tree = nltk.Tree.fromstring(s)

out = "("
for subtrees in tree:
    # there are threee subtrees
    # print(len(subtree))
    for i, subtree in enumerate(subtrees):
        if len(subtree) > 1:
            out += "("
        for bracketing in range(len(subtree)):
            # print(subtree[bracketing])
            flattened_tree = subtree[bracketing].flatten()
            flattened_string = str(flattened_tree)
            flattened_string = flattened_string.replace(flattened_tree.label() + " ", "")
            print(flattened_string)
            out += flattened_string
        if len(subtree) > 1:
            out += ")"
        # break
out += ")"

print(out)
# (((This time)(around))(they)(('re)(moving even faster)))

Edit:

if you see, "This" and "time" are part of the same parent, "NP". So, they become contiguous constituents, i.e. (This time).

Whereas, "around" is a single word constituent although a part of the same left sub-tree. So, it becomes ((This time)(around)).

Similarly, for the case of the right-subtree - "'re" and "'moving even faster", we see that "moving" as well as "even faster" share the same parent, "VP".

So, it becomes, (('re)((moving)(even faster)).

user_5459839 · Answer

If I understand correctly you want to add brackets to an atomic string when it has a sibling that is not an atomic string, but already a bracketed combination, so that you would never have a pattern like this:

(moving (even faster))

Or in other words, a space can only be a separator between two atomic strings.

I would do this in two recursive passes:

A first one to convert the tree to a nested list. This will make it easier to make distinctions for the above mentioned rule.
A second pass to convert that nested list to the final bracketed string.

Code:

import nltk

def tolist(tree):
    if isinstance(tree[0], str):
        return tree[0]
    res = [tolist(subtree) for subtree in tree]
    leaves = sum(isinstance(child, str) for child in res)
    if 0 < leaves < len(res): # if there is a mix of leaves and subtrees....
        # ...then wrap every leaf in a list
        return [[child] if isinstance(child, str) else child for child in res]
    return res

def tostr(lst):
    if isinstance(lst[0], str):  # assume all list members are strings
        return "(" + " ".join(lst) + ")"
    return "(" + "".join([tostr(sub) for sub in lst]) + ")"

# run on sample data
s = "(TOP (S (NP-TMP (NP (DT This) (NN time)) (ADVP (RP around))) (NP-SBJ (PRP they)) (VP (VBP 're) (VP (VBG moving) (ADVP (RB even) (RBR faster))))))"
tree = nltk.Tree.fromstring(s)
res = tostr(tolist(tree[0]))
print(res)

Tree string to bracketed string

1 Answers