Dependency Syntax and Universal Dependencies › Code: Analyzing a Dependency Treebank
Language AI HandbookAll chapters Dependency Syntax and Universal Dependencies › Code: Analyzing a Dependency TreebankSection view · Sections in this chapter10 / 13 ↓
Reading tools Definitions, links & notes
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
The following cells load a CoNLL-U sample, validate the structural axioms, draw two example trees, and check projectivity. Each step turns an earlier definition into an executable check on supplied annotations. The cells do not infer a tree from raw text.
Setup
The examples use the book's scientific Python environment and a small standard-library reader. No corpus or pretrained model is downloaded. The reader preserves all ten CoNLL-U fields as text, except for the integer ID and HEAD values used by the tree computations. It supports this chapter's basic integer-ID word records only: it explicitly rejects range IDs and empty-node IDs. It is not a general CoNLL-U parser or validator.
Loading CoNLL-U
We define a small three-sentence treebank in the CoNLL-U format. It includes a coordination example, a ditransitive example, and the non-projective relative clause example from earlier. Building the sample by hand keeps the chapter self-contained and lets us focus on structure rather than download mechanics.
PythonIn [3]Expand
CONLLU_SAMPLE = """
# sent_id = 1
# text = They buy and sell books.
1\tThey\tthey\tPRON\tPRP\tCase=Nom|Number=Plur\t2\tnsubj\t_\t_
2\tbuy\tbuy\tVERB\tVBP\tNumber=Plur\t0\troot\t_\t_
3\tand\tand\tCCONJ\tCC\t_\t4\tcc\t_\t_
4\tsell\tsell\tVERB\tVBP\tNumber=Plur\t2\tconj\t_\t_
5\tbooks\tbook\tNOUN\tNNS\tNumber=Plur\t2\tobj\t_\tSpaceAfter=No
6\t.\t.\tPUNCT\t.\t_\t2\tpunct\t_\t_
# sent_id = 2
# text = She gave him a book.
1\tShe\tshe\tPRON\tPRP\tCase=Nom|Gender=Fem|Number=Sing|Person=3|PronType=Prs\t2\tnsubj\t_\t_
2\tgave\tgive\tVERB\tVBD\tMood=Ind|Tense=Past|VerbForm=Fin\t0\troot\t_\t_
3\thim\the\tPRON\tPRP\tCase=Acc|Gender=Masc|Number=Sing|Person=3|PronType=Prs\t2\tiobj\t_\t_
4\ta\ta\tDET\tDT\tDefinite=Ind|PronType=Art\t5\tdet\t_\t_
5\tbook\tbook\tNOUN\tNN\tNumber=Sing\t2\tobj\t_\tSpaceAfter=No
6\t.\t.\tPUNCT\t.\t_\t2\tpunct\t_\t_
# sent_id = 3
# text = I saw a dog yesterday which was a Yorkshire Terrier.
1\tI\tI\tPRON\tPRP\tCase=Nom|Number=Sing|Person=1|PronType=Prs\t2\tnsubj\t_\t_
2\tsaw\tsee\tVERB\tVBD\tMood=Ind|Tense=Past|VerbForm=Fin\t0\troot\t_\t_
3\ta\ta\tDET\tDT\tDefinite=Ind|PronType=Art\t4\tdet\t_\t_
4\tdog\tdog\tNOUN\tNN\tNumber=Sing\t2\tobj\t_\t_
5\tyesterday\tyesterday\tNOUN\tNN\tNumber=Sing\t2\tobl:unmarked\t_\t_
6\twhich\twhich\tPRON\tWDT\tPronType=Rel\t10\tnsubj\t_\t_
7\twas\tbe\tAUX\tVBD\tMood=Ind|Number=Sing|Tense=Past|VerbForm=Fin\t10\tcop\t_\t_
8\ta\ta\tDET\tDT\tDefinite=Ind|PronType=Art\t10\tdet\t_\t_
9\tYorkshire\tYorkshire\tPROPN\tNNP\tNumber=Sing\t10\tcompound\t_\t_
10\tTerrier\tterrier\tNOUN\tNN\tNumber=Sing\t4\tacl:relcl\t_\tSpaceAfter=No
11\t.\t.\tPUNCT\t.\t_\t2\tpunct\t_\t_
"""The executable sample supplies basic dependency annotations only; DEPS is unspecified. Enhanced coordination and relative-clause links were introduced above, but this reader neither infers them nor validates a complete enhanced graph. The breed-denoting head Terrier is treated as the common noun NOUN, with lemma terrier and Penn-style tag NN; its capitalization does not establish a proper name. Keeping the supplied linguistic choices separate from the graph checks makes their limits explicit.
We now read the three sentence blocks. Blank lines terminate sentences, comments are ignored for the tree computations, and every word row must have ten nonempty tab-separated fields. Morphological features and enhanced dependencies remain literal field strings; this reader does not interpret or validate their internal syntax.
PythonIn [4]Expand
FIELDS = (
"id",
"form",
"lemma",
"upos",
"xpos",
"feats",
"head",
"deprel",
"deps",
"misc",
)
def read_basic_conllu(text):
sentences, rows = [], []
for line in text.splitlines() + [""]:
if not line.strip():
if rows:
sentences.append(rows)
rows = []
continue
if line.startswith("#"):
continue
values = line.split("\t")
if len(values) != 10 or any(value == "" for value in values):
raise ValueError("Expected ten nonempty tab-separated fields")
row = dict(zip(FIELDS, values))
if not row["id"].isdigit() or not row["head"].isdigit():
raise ValueError(
"This teaching reader supports integer word IDs and HEADs only"
)
row["id"], row["head"] = int(row["id"]), int(row["head"])
rows.append(row)
return sentences
parsed = read_basic_conllu(CONLLU_SAMPLE)Let's inspect seven selected fields of the second sentence, She gave him a book, as a DataFrame. The reader also retains XPOS, FEATS, and MISC; this display concentrates on the words and their attachments.
ConsoleOut [5]Expand
Loaded 3 sentences into CoNLL-U records ID FORM LEMMA UPOS HEAD DEPREL DEPS 1 She she PRON 2 nsubj _ 2 gave give VERB 0 root _ 3 him he PRON 2 iobj _ 4 a a DET 5 det _ 5 book book NOUN 2 obj _ 6 . . PUNCT 2 punct _
The output shows the seven selected CoNLL-U fields. HEAD is an integer index into the same sentence, not a word form. Word 3 (him) has HEAD 2, meaning gave is its head. The row stores that index rather than repeating the form gave. A program can resolve the index against the word records of the same sentence.
Structural Validation
The axioms of a dependency tree are simple enough to check programmatically. We build a directed graph with a virtual node 0 for the artificial root, add one edge from each head to its dependent, and then check the basic-tree constraints together with word IDs and root labels.
PythonIn [6]Expand
def build_graph(tokens):
G = nx.DiGraph()
G.add_node(0)
for t in tokens:
G.add_node(t["id"])
for t in tokens:
G.add_edge(t["head"], t["id"])
return G
def validate_tree(tokens):
ids = [t["id"] for t in tokens]
well_formed = ids == list(range(1, len(tokens) + 1))
valid_heads = all(
t["head"] in {0, *ids} and t["head"] != t["id"] for t in tokens
)
root_labels = all(
(t["head"] == 0) == (t["deprel"] == "root") for t in tokens
)
G = build_graph(tokens)
return {
"word_ids": well_formed,
"valid_heads": valid_heads,
"single_head": well_formed and all(G.in_degree(i) == 1 for i in ids),
"single_root": sum(t["head"] == 0 for t in tokens) == 1,
"root_labels": root_labels,
"acyclic": nx.is_directed_acyclic_graph(G),
"connected": set(nx.descendants(G, 0)) | {0} == set(G.nodes()),
}ConsoleOut [7]Expand
Sentence 1: {'word_ids': True, 'valid_heads': True, 'single_head': True, 'single_root': True, 'root_labels': True, 'acyclic': True, 'connected': True}
Sentence 2: {'word_ids': True, 'valid_heads': True, 'single_head': True, 'single_root': True, 'root_labels': True, 'acyclic': True, 'connected': True}
Sentence 3: {'word_ids': True, 'valid_heads': True, 'single_head': True, 'single_root': True, 'root_labels': True, 'acyclic': True, 'connected': True}All three hand-written examples satisfy these checks. Counting rows with HEAD=0 is essential: the graph with arcs 0 -> 1 and 0 -> 2 is an arborescence rooted at the artificial node, but it has two sentence roots and violates the basic UD single-root requirement. The root_labels check also enforces the correspondence between HEAD=0 and DEPREL=root. These checks do not replace UD's full annotation and format validators.
The validation step is worth running even when you trust the data source. Annotation errors can occur in a treebank; importing, converting, or generating head assignments is also an opportunity to check the basic-tree constraints. A quick structural check catches cycles, multiple roots, and disconnected tokens before those errors propagate into training or evaluation.
Drawing Trees
A diagram makes the head-dependent choices easier to inspect. We build a small helper that places each word on a horizontal line and draws each arc above it, labelled with its relation. Word spacing accounts for word length. Arc heights increase with their horizontal span so that nested attachments remain legible; the height is a drawing choice, not a linguistic measurement.
PythonIn [8]Expand
def draw_dep_tree(tokens, ax, highlight=None):
# Word spacing accounts for word length; the arcs encode attachment only.
positions = [0.0]
for left, right in zip(tokens, tokens[1:]):
positions.append(
positions[-1] + (len(left["form"]) + len(right["form"])) / 2 + 2.5
)
pos = {t["id"]: x for t, x in zip(tokens, positions)}
ink = PALETTE["ink"]
max_height = 0.0
for t in tokens:
ax.text(pos[t["id"]], 0, t["form"], ha="center", va="center", color=ink)
if t["head"] == 0:
ax.text(
pos[t["id"]], -0.55, "root", ha="center", va="top", color=ink
)
continue
xh, xd = pos[t["head"]], pos[t["id"]]
height = 0.075 * abs(xd - xh)
max_height = max(max_height, height)
color = (
PALETTE["amber"]
if (t["head"], t["id"]) in (highlight or set())
else ink
)
path = MatplotlibPath(
[(xh, 0.25), ((xh + xd) / 2, 2 * height + 0.25), (xd, 0.25)],
[
MatplotlibPath.MOVETO,
MatplotlibPath.CURVE3,
MatplotlibPath.CURVE3,
],
)
ax.add_patch(
FancyArrowPatch(
path=path,
arrowstyle="-|>",
mutation_scale=10,
lw=1.1,
color=color,
)
)
ax.text(
(xh + xd) / 2,
height + 0.32,
t["deprel"],
ha="center",
va="bottom",
fontsize=8,
color=color,
bbox={
"facecolor": PALETTE["paper"],
"edgecolor": "none",
"alpha": 0.92,
"pad": 0.6,
},
)
ax.set_xlim(-3, positions[-1] + 3)
ax.set_ylim(-1, max_height + 1.15)
ax.axis("off")Now we draw the projective sentence She gave him a book. Its local determiner attachment gives us a visual baseline for the later crossing example.
VisualizationOut [9]Expand
The arcs fan out from gave: nsubj to She, iobj to him, obj to book, and punct to the period. The only arc headed by a nonroot word is det from book to a, and it sits entirely inside the span of obj.
Now the non-projective sentence. We highlight the offending arc from dog to Terrier in amber so the crossing is visible.
VisualizationOut [10]Expand
The highlighted arc violates projectivity because yesterday belongs to the main clause. A parser restricted to projective outputs must change at least one attachment. A parser that allows non-projective outputs can represent the supplied analysis, but it still needs evidence to choose the intended attachments.
Checking Projectivity
Visual inspection is nice, but we need a computation. The definition translates directly into a loop: for every arc, look at every token strictly between the head and dependent, and check whether it belongs to the head's subtree. If any intervening token is outside, the arc is a violation.
PythonIn [11]Expand
def projectivity_violations(tokens):
children = defaultdict(list)
for t in tokens:
if t["head"] != 0:
children[t["head"]].append(t["id"])
subtree = {}
def collect(tid):
s = {tid}
for c in children[tid]:
s |= collect(c)
subtree[tid] = s
return s
for t in tokens:
if t["head"] == 0:
collect(t["id"])
pos = {t["id"]: i for i, t in enumerate(tokens)}
violations = []
for t in tokens:
h, d = t["head"], t["id"]
if h == 0:
continue
lo, hi = min(pos[h], pos[d]), max(pos[h], pos[d])
for k in range(lo + 1, hi):
k_id = tokens[k]["id"]
if k_id not in subtree[h]:
violations.append((h, d, k_id))
return violationsConsoleOut [12]Expand
Sentence 1: projective Sentence 2: projective Sentence 3: non-projective (1 non-projective arc(s)) offending arcs: [(4, 10)]
The first two sentences return no violation tuples. The third returns exactly [(4, 10, 5)]: the acl:relcl from dog to Terrier has the outside intervening word yesterday. The output loop reduces tuples to distinct (head, dependent) pairs before counting, so it reports one offending arc, (4, 10). In general, one arc can produce several tuples if several intervening words are outside its head's subtree. This counts arcs violating the descendant condition, rather than every arc that participates in a crossing. Here, 2→5 participates in the visible crossing but is itself projective: tokens 3 and 4 are descendants of 2.
The numerical check can also be read as a picture. The next cell turns each non-root arc into a horizontal segment from head to dependent. Amber segments are the arcs that violate projectivity. The map uses every non-root arc in all three sample sentences and performs no random sampling.
PythonIn [13]Expand
projectivity_arc_rows = []
for sent_i, tokens in enumerate(parsed, 1):
violations = {(h, d) for h, d, _ in projectivity_violations(tokens)}
sent_rows = []
for t in tokens:
h, d = t["head"], t["id"]
if h == 0:
continue
sent_rows.append(
{
"sentence": f"S{sent_i}",
"head": h,
"dep": d,
"span": abs(d - h),
"projective": (h, d) not in violations,
"label": t["deprel"],
}
)
sent_rows.sort(key=lambda row: (row["span"], row["head"], row["dep"]))
n_arcs = len(sent_rows)
for rank, row in enumerate(sent_rows):
row["y"] = sent_i + (rank - (n_arcs - 1) / 2) * 0.08
projectivity_arc_rows.append(row)
projectivity_sentence_labels = [f"S{i}" for i in range(1, len(parsed) + 1)]
projectivity_max_token = max(t["id"] for tokens in parsed for t in tokens)VisualizationOut [14]Expand
For a valid tree with consecutively indexed words, this teaching implementation has worst-case time under the usual constant-time set-membership assumption. The nested arc-and-intervening-word loop can inspect quadratically many pairs. The stored descendant sets can also contain entries across a chain-shaped tree, so constructing and retaining those sets takes worst-case work and space. Recursive depth can reach , which is another reason to keep this implementation to short examples. These bounds describe the algorithm; they do not supply a typical operation count for natural-language sentences.
A more memory-efficient check is possible when the input is already known to be a valid tree. For each word , a postorder traversal can retain only the smallest descendant position , the largest position , and the number of words in its subtree, including . That subtree occupies a contiguous interval exactly when
Here counts the word positions from the leftmost member to the rightmost member. Equality says that every position in that interval belongs to the subtree, with no gap. A dependency tree is projective exactly when this holds for every word's subtree: contiguity ensures that any position between a head and its dependent is dominated by that head, and projectivity ensures that the positions along each descendant path leave no outside word inside the subtree's span. For example, the subtree of dog in our third analysis has positions , so while . The missing position is yesterday, at 5. Combining these three quantities once per edge gives an whole-tree check and storage, rather than an additional scan for every arc.
Annotation Checks Are Not Parsing
The code above inspects a supplied analysis. It does not infer a tree from raw text. That distinction matters: a structurally valid tree can still attach a phrase to the wrong word or choose a relation inconsistent with the sentence's interpretation. Acyclicity and projectivity are mathematical properties; annotation correctness also requires linguistic judgment.
Consider I saw the man with a telescope. If with a telescope describes the instrument used for seeing, telescope can depend on saw with obl. If it describes the man, telescope can depend on man with nmod. In both analyses, with is a case dependent of telescope. Both structures can be single-headed, connected, acyclic, and projective. The sentence alone may not settle which interpretation the writer intended.
That is why a validation routine should state what it proves. Our routine checks the chosen basic-tree constraints. It does not certify relation definitions, morphological features, the interpretation of an ambiguous sentence, or all of the CoNLL-U specification. Parser training and decoding appear in the next chapter; comparison with reference annotations and attachment metrics follow in the chapter on structured prediction and parsing evaluation.
Comments
Add to the conversation
A question, a correction, or an example from your own work.
No comments yet. Be the first to share your thoughts!