"""Hybrid syntactic tree utilities."""
from __future__ import annotations
from collections import defaultdict
from itertools import chain
from typing import Any
from numpy import array
from scipy.special import softmax
from datasets.features import Features
from morfeusz2 import Morfeusz
# https://aclanthology.org/2021.emnlp-main.823.pdf
# https://github.com/stanojevic/Fast-MST-Algorithm
from mst import fast_parse
from .constants import (
EMPTY,
TOKENS,
LEMMAS,
ALL_UPPER,
ALL_LOWER,
FIRST_UPPER,
KEEP,
TAGS,
NONTERMINALS,
SPINES,
ANCHORS,
ANCHOR_HS,
HEADS,
DEPRELS,
MASK_VALUE,
EAGER,
MST,
)
from .types import TokenList, IntLabelList, StrLabelList, NestedIntLabelList, NestedStrLabelList, LabelDict, DatasetInstance
# TODO what should be the EMPTY_VAL?
EMPTY_VAL = '_'
[docs]
class TreeNode(object):
"""A hybrid synactic tree node."""
def __init__(
self,
nid: int,
category: str | None,
terminal: tuple[str, str | None, str | None] | None,
is_head: bool,
from_index: int | None,
to_index: int | None,
head_index: int | None = None,
attributes: dict[str, Any] | None = None,
children: list[TreeNode] | None = None
) -> None:
self.nid = nid
self.parent: TreeNode | None = None
self.category = category
self.terminal = terminal
self.is_head = is_head
self.from_index = from_index
self.to_index = to_index
self.head_index = head_index
self.attributes = attributes if attributes is not None else {}
self.children = children if children is not None else []
for child in self.children:
child.parent = self
[docs]
def add_child(self, child: TreeNode) -> None:
"""Append as the given node as rightmost child."""
self.children.append(child)
child.parent = self
[docs]
def get_yield(self) -> list[TreeNode]:
"""Return the list of terminal nodes as read from left to right.
Returns:
the terminals.
"""
if not self.children:
return [self]
return list(chain.from_iterable(child.get_yield() for child in self.children))
[docs]
def is_continuous(self) -> bool:
"""Return `True` iff all constituents are continuous.
Returns:
a boolean value.
"""
idx = [token.from_index for token in self.get_yield()]
return (idx == sorted(idx)) # type: ignore[type-var] # at this point, all from_index’s are not None
[docs]
def get_root(self) -> TreeNode:
"""Return the root of the tree containing this node.
Returns:
the root.
"""
root = self
while root.parent is not None:
root = root.parent
return root
[docs]
def to_brackets(
self,
nonterminal_features: list[str] | None = None,
mark_head: bool = True,
morph_tags: bool = False,
dummy_pre: bool = False
) -> str:
"""Create an EVALB-style bracketed representation.
Terminals’ order will get scrambled in case of discontinuous trees.
Args:
nonterminal_features: nonterminal features to include.
mark_head: mark head nonterminals with asterisks (`'*'`).
morph_tags: include inflectional tags.
dummy_pre: make all terminals single children by adding dummy preterminals where needed.
Returns:
the bracketed representation.
"""
if nonterminal_features is None:
nonterminal_features = []
if not self.children:
assert (self.terminal is not None)
assert (self.parent is not None) # we’re a leaf and therefore do have a parent
cat = _make_evalb_friendly(self.terminal[0])
if morph_tags:
cat = f'({_make_evalb_friendly(self.terminal[2])} {cat})'
if len(self.parent.children) == 1 or not dummy_pre:
return cat
else:
return f'(DUMMY_PRE {cat})'
else:
assert (self.category is not None)
cat = '_'.join([self.category] + [self.attributes.get(f, EMPTY_VAL) for f in nonterminal_features])
if mark_head and self.is_head:
cat = '*' + cat
cat = _make_evalb_friendly(cat)
return f'({cat} {" ".join(child.to_brackets(
nonterminal_features=nonterminal_features,
mark_head=mark_head,
morph_tags=morph_tags,
dummy_pre=dummy_pre) for child in self.children)})'
[docs]
def pretty_print(self, tab: str = '', features: list[str] | None = None) -> None:
"""Print the tree’s representation to the standard output."""
if features is None:
features = []
cat = self.category if self.category is not None else self.terminal
print(f'{tab}[{self.nid}] {"*" if self.is_head else ""}{cat}{[self.attributes.get(f, EMPTY_VAL) for f in features]}')
for child in self.children:
child.pretty_print(tab=tab + ' ', features=features)
[docs]
def make_lemma(token: str, case: str, rule: str, legacy_casing: bool = False) -> str:
"""Generate a lemma from text form by applying model-predicted rules.
Returns:
the lemma.
"""
_cut_prefix, _cut, suffix = rule.split('_', maxsplit=2)
cut_prefix, cut = int(_cut_prefix), int(_cut)
lemma = token.lower()
if cut_prefix:
lemma = lemma[cut_prefix:]
if cut:
lemma = lemma[:-cut]
lemma += suffix
# failsafe
if not lemma:
return token
# ‘X’ used to mean ‘first upper’
if (legacy_casing and case == ALL_UPPER) or case == FIRST_UPPER:
lemma = lemma[0].upper() + lemma[1:]
elif case == ALL_UPPER:
lemma = lemma.upper()
elif case == KEEP:
new_lemma = ''
for i, (t, l) in enumerate(zip(token, lemma)):
new_lemma += (lemma[i].upper() if token[i].isupper() else lemma[i])
lemma = new_lemma
return lemma
[docs]
def drop_rozpodabniacz(lemma: str, tag: str) -> str:
"""Remove Morfeusz lemma identifier (‘rozpodabniacz’) if present.
Returns:
the stripped lemma.
"""
if tag in ['interp', 'emo', 'sym', 'xxx'] or tag.startswith('xxs:'):
return lemma
return lemma.split(':')[0]
'''
def correct_lemma(token, lemma, tag, morfeusz):
match = [interp[2] for interp in morfeusz.analyse(token) if interp[2][0] == token and interp[2][2] == tag]
match_lemmas = set(drop_rozpodabniacz(interp[1], interp[2]) for interp in match)
if match_lemmas and lemma[0].lower() + lemma[1:] not in [l[0].lower() + l[1:] for l in match_lemmas]:
#if len(match_lemmas) != 1:
# print(token, lemma, tag, '->', sorted(match_lemmas))
# print(' ---> >1 matching lemma, will take alphabetically first!')
return sorted(match_lemmas)[0]
return lemma
'''
EXC = (
('r', 'rok', 'brev:pun'),
)
X = {'perf', 'imperf', 'agl', 'nagl', 'neg', 'aff'}
[docs]
def correct_lemma(token: str, lemma: str, tag: str, morfeusz: Morfeusz) -> tuple[str, str]:
"""Use Morfeusz to try correcting the model-predicted lemma and inflectional tag.
Returns:
possibly corrected lemma and tag.
"""
if tag.startswith('xx'):
return lemma, tag
if (token, lemma, tag) in EXC:
return lemma, tag
candidates = defaultdict(set)
for i in morfeusz.analyse(token):
o, b, t = i[2][0], drop_rozpodabniacz(i[2][1], i[2][2]), i[2][2]
if (o, b, t) == (token, lemma, tag):
return lemma, tag
# daw. dziś xyz -> daw.
kwal = [k.split(' ')[0] for k in i[2][4]]
if kwal == []:
kwal_rank = 0
elif not {'daw.', 'przest.', 'rzad.', 'środ.', 'gwar.', 'indyw.'}.intersection(kwal):
kwal_rank = 1
else:
kwal_rank = 2
if o == token and (b[0].isupper() == lemma[0].isupper() or sum(x.isupper() for x in token) > 1):
t1 = set(tag.split(':'))
t2 = set(t.split(':'))
k = len(t1 - t2)
if t1.symmetric_difference(t2).issubset(X) and k <= 1:
candidates[k, kwal_rank].add((b, t))
if candidates:
min_key = min(candidates.keys())
cands = candidates[min_key]
if len(cands) == 1 or min_key[0] == 0:
return sorted(cands)[0]
return lemma, tag
def _add_root(chart: list[list[float]]) -> list[list[float]]:
N = len(chart)
chartr = [[0.0 for j in range(N + 1)] for i in range(N + 1)]
for i in range(N):
for j in range(N):
if i == j:
chartr[i + 1][0] = chart[i][i]
else:
chartr[i + 1][j + 1] = chart[i][j]
return chartr
def _true_mst(chart: list[list[float]]) -> list[int]:
# takes transposed matrix: m[i][j] is the i-->j edge’s weight
heads = list(fast_parse(array(chart).transpose(), one_root=True))
# heads: first element is -1 for root, tokens are indexed from 1 (root is 0)
return heads[1:]
def _eager_mst(chart: list[list[float]]) -> list[int]:
edges = []
N = len(chart)
paths = {(i, i) for i in range(N)}
for i, row in enumerate(chart):
edges += [(weight, j, i) for j, weight in enumerate(row)]
edges = list(reversed(sorted(edges)))
tree: dict[int, int] = dict()
while edges and len(tree) < N - 1:
w, i, j = edges[0]
if w == 0:
break
assert(j not in tree)
tree[j] = i
# there can be only one root!
if i == 0:
edges = [e for e in edges if e[1] != 0]
new_paths = {(i, j)}
for p1 in paths:
for p2 in paths:
if p1[1] == i and p2[0] == j:
new_path = (p1[0], p2[1])
new_paths.add(new_path)
paths.update(new_paths)
edges = [e for e in edges if e[2] != j and (e[2], e[1]) not in paths]
assert(len(tree) == N - 1)
# tokens are indexed from 1 (root is 0)
return [tree[i] for i in range(1, N)]
#return tree
def _do_mark_heads(tree: TreeNode, dependency_heads: IntLabelList, deprels: StrLabelList | None = None) -> int:
if not tree.children:
assert (tree.from_index is not None)
return tree.from_index
child_head_idx = [_do_mark_heads(child, dependency_heads, deprels=deprels) for child in tree.children]
heads = []
for child, child_head_id in zip(tree.children, child_head_idx):
if dependency_heads[child_head_id] not in child_head_idx:
child.is_head = True
heads.append(child_head_id)
elif deprels:
child.attributes['deprel'] = deprels[child_head_id]
assert(len(heads) == 1)
return heads[0]
def _mark_heads(tree: TreeNode, dependency_heads: IntLabelList, deprels: StrLabelList | None = None) -> None:
_do_mark_heads(tree, dependency_heads, deprels)
tree.is_head = True
def _rearrange(tree: TreeNode) -> TreeNode:
if tree.children:
children = [_rearrange(child) for child in tree.children]
tree.children = sorted(children, key=lambda child: child.from_index) # type: ignore[arg-type, return-value] # at this point, all from_index’s are not None
tree.from_index = tree.children[0].from_index
tree.to_index = max(child.to_index for child in tree.children) # type: ignore[type-var]
return tree
[docs]
def tree_from_dataset_instance(instance: DatasetInstance, dataset_features: Features) -> TreeNode | None:
"""Build a hybrid syntactic tree from a dataset instance encoding it.
Returns:
the constructed tree.
"""
nonterminals = instance[NONTERMINALS]
if nonterminals is None:
return None
nodes = []
# create a node for each nonterminal
for i, nonterminal in enumerate(nonterminals):
category = nonterminal['cat']
if category is None:
assert(len(nonterminal['children']) == 1)
token_idx = nonterminal['children'][0]
orth = instance[TOKENS][token_idx]
lemma = instance[LEMMAS][token_idx] if LEMMAS in instance else None
tag = None
if TAGS in instance:
tag_idx = instance[TAGS][token_idx]
if tag_idx not in (None, MASK_VALUE):
tag = dataset_features[TAGS].feature.int2str(instance[TAGS][token_idx])
nodes.append(TreeNode(i, None, (orth, lemma, tag), False, token_idx, token_idx + 1))
else:
nodes.append(TreeNode(i, category, None, False, 0, 0))
# link the nodes with parent-head relations
for nonterminal, x in list(zip(nonterminals, nodes)):
if nonterminal['cat'] is not None:
for child_idx in nonterminal['children']:
x.add_child(nodes[child_idx])
tree = nodes[0]
# mark the heads according to dependency relations
deprels : StrLabelList = [dataset_features[DEPRELS].feature.int2str(d) if d != MASK_VALUE else None for d in instance[DEPRELS]]
_mark_heads(tree, instance[HEADS], deprels=deprels)
return _rearrange(tree)
[docs]
def get_heads(matrix: list[list[float]], mst: str = MST) -> IntLabelList:
"""Decode a dependency adjacency matrix into a list of token head indices.
Args:
matrix: edge weights matrix.
mst: dependency tree decoding algorithm to use: :const:`~hydra.utils.constants.MST` or :const:`~hydra.utils.constants.EAGER`.
Returns:
the head indices.
"""
#already softmax-ed in label processing step
chart_r = _add_root(matrix)
heads = (_true_mst if mst == MST else _eager_mst)(chart_r)
# tokens indexed from 1 (root is 0) -> index tokens from 0 (root is None)
return [int(hd - 1) if hd > 0 else None for hd in heads]
[docs]
def get_graph_edges(matrix: NestedIntLabelList, deprel_matrix: NestedStrLabelList) -> tuple[NestedIntLabelList, NestedStrLabelList]:
"""Read edges from graph adjacency and label matrices.
Returns:
lists of heads and labels for each token.
"""
#already rounded and sigmoid-ed in label processing step
# tokens indexed from 0 (root is ’its own head’)
ret_m: NestedIntLabelList = [[] for _ in matrix]
ret_d: NestedStrLabelList = [[] for _ in matrix]
for i, heads in enumerate(matrix):
for j, edge in enumerate(heads):
if edge:
ret_m[i].append(j if j != i else None)
ret_d[i].append(deprel_matrix[i][j])
return ret_m, ret_d
def _make_head_path(path: str, token: str, lemma: str, tag: str, index: int) -> TreeNode:
node = TreeNode(0, None, (token, lemma, tag), False, index, index + 1)
if path == EMPTY:
return node
for cat in reversed(path.split('_')):
node.is_head = True
node = TreeNode(0, cat, None, False, None, None, children=[node])
return node
def _append_dependent(
head_path: TreeNode,
dep_path: TreeNode,
anchor_cat: str,
anchor_h: int,
decompress: bool = False
) -> tuple[TreeNode, str | None]:
problem = None
anchor_node = head_path
head_chain = [head_path]
while head_chain[-1].children:
heads = [child for child in head_chain[-1].children if child.is_head]
try:
assert len(heads) == 1
head_chain.append(heads[0])
except:
head_path.pretty_print()
head_chain[-1].pretty_print()
raise
matching_heads = [hd for hd in head_chain if hd.category == anchor_cat]
if not matching_heads:
anchor_node = head_path
#problem = (dep_path, anchor_cat)
problem = 'ATTACH: no matching anchor category'
else:
# fallback: take the highest
if anchor_h is None:
anchor_h = len(matching_heads)
problem = 'ATTACH: fallback'
elif anchor_h > len(matching_heads) and not decompress:
anchor_h = len(matching_heads)
elif anchor_h > len(matching_heads) and decompress:
expand = anchor_h - len(matching_heads)
for i in range(expand):
problem = 'ATTACH: expand'
child = matching_heads[0]
parent = child.parent
new_node = TreeNode(0, anchor_cat, None, child.is_head, None, None, children=[child], attributes=child.attributes)
child.is_head = True
child.attributes = {}
if parent:
parent.children.remove(child)
parent.add_child(new_node)
if head_path == child:
head_path = new_node
matching_heads.insert(0, new_node)
anchor_node = matching_heads[-anchor_h]
anchor_node.add_child(dep_path)
dep_path.is_head = False
return head_path, problem
POS2PRE: dict[str, str] = {}
def _add_dummy_pre(path: TreeNode) -> TreeNode:
assert (path.terminal is not None)
pos = path.terminal[2].split(':')[0] if path.terminal[2] is not None else '_'
return TreeNode(0, f'{POS2PRE[pos]}', None, True, None, None, children=[path])
def _check_no_cycles(heads: IntLabelList) -> bool:
children_dict = defaultdict(set)
for i, hd in enumerate(heads):
children_dict[hd].add(i)
visited = {-1}
queue = [-1]
while queue:
children = children_dict.pop(queue[0], set())
if children.intersection(visited):
return False
visited.update(children)
queue = queue[1:] + list(children)
return not children
# find any <EMPTY>’s children and reattach them to <EMPTY>’s head
def _try_to_reattach(heads: IntLabelList, spines: StrLabelList, tokens: TokenList) -> IntLabelList:
to_reattach = [i for i, spine in enumerate(spines) if spine == EMPTY and i in heads]
k = 0
while to_reattach:
k += 1
if k == 50:
raise RuntimeError('Can’t reattach <EMPTY>’s children: too many attempts!')
tr = to_reattach[0]
hd_idx = heads[tr]
try:
assert(hd_idx is not None)
except:
print(tokens)
print(heads)
print(spines)
raise
new_heads = heads.copy()
for i, hd in enumerate(heads):
if hd == tr:
new_heads[i] = hd_idx
if _check_no_cycles(new_heads):
heads = new_heads
else:
raise RuntimeError('Can’t reattach <EMPTY>’s children: cycle detected!')
to_reattach = [i for i, spine in enumerate(spines) if spine == EMPTY and i in heads]
return heads
def _reconstruct_tree(
tokens: TokenList,
labels: LabelDict,
nonterminal_features: list[str],
decompress: bool = False,
root_label: str | None = None,
force_root_label: bool = False
) -> tuple[TreeNode, list[str], IntLabelList]:
morph_tags = labels.get(TAGS, ['_' for _ in tokens])
lemmas = labels.get(LEMMAS, ['_' for _ in tokens])
heads = labels[HEADS]
deprels = labels[DEPRELS]
spines = labels[SPINES]
anchors = labels[ANCHORS]
anchor_hs = labels[ANCHOR_HS]
problems = []
spines = list(spines)
if root_label is not None:
for i, (head, spine) in enumerate(zip(heads, spines)):
assert(spine is not None)
if (head is None and root_label not in spine):
if spine == EMPTY:
spines[i] = root_label
problems.append('SPINE: EMPTY->ROOT')
elif force_root_label:
spines[i] = (f'{root_label}_{spine}').replace(f'_{EMPTY}', '')
problems.append('SPINE: force ROOT')
if (head is not None and root_label in spine):
assert(spine.startswith(root_label))
spines[i] = EMPTY if spine == root_label else spine.replace(f'{root_label}_', '')
problems.append('SPINE: remove ROOT')
new_heads = _try_to_reattach(heads, spines, tokens)
if new_heads != heads:
heads = new_heads
problems.append('REATTACH')
head_paths = [
_make_head_path(p, tok, lemma, tag, i) for i, (p, tok, lemma, tag) # type: ignore[arg-type] # all args are not None
in enumerate(zip(spines, tokens, lemmas, morph_tags))
]
# if a spine is some other spine’s head and consists of a terminal only, add a dummy preterminal to append to
head_paths = [_add_dummy_pre(hp) if (hp.terminal is not None and i in heads) else hp for i, hp in enumerate(head_paths)]
# add nonterminal features
for ntf in nonterminal_features:
for hp, feat in zip(head_paths, labels[ntf]): # type: ignore[literal-required]
hp.attributes[ntf] = feat
int_anchor_hs = [int(h) if h != '<ROOT>' else None for h in anchor_hs] # type: ignore[arg-type] # h is not None
root = None
for i, head in enumerate(heads):
if deprels[i] is not None:
head_paths[i].attributes['deprel'] = deprels[i]
if head is None:
root = i
else:
head_paths[head], problem = _append_dependent(
head_paths[head], head_paths[i], anchors[i], int_anchor_hs[i], decompress=decompress) # type: ignore[arg-type] # all args are not None
if problem:
problems.append(problem)
assert (root is not None)
tree = _rearrange(head_paths[root])
tree.is_head = True
return tree, problems, heads
[docs]
def make_tree(
tokens: TokenList,
labels: LabelDict,
nonterminal_features: list[str],
root_label: str | None = None,
force_root_label: bool = False,
decompress: bool = True
) -> tuple[TreeNode, list[str], IntLabelList]:
"""Build a hybrid syntactic tree from model-predicted labels.
Args:
tokens: the sentence being processed.
labels: model-prdicted token labels.
nonterminal_features: nonterminal features to include.
root_label: used by `force_root_label`.
force_root_label: enforce a specific root label.
decompress: expand same-category node chains where required by attachment predictions.
Returns:
the constructed tree, info about used heuristics if any, dependency head indices
may have been changed wrt. model-predicted labels by heuristics).
"""
tree, info, heads = _reconstruct_tree(
tokens, labels, nonterminal_features,
root_label=root_label,
force_root_label=force_root_label,
decompress=decompress,
)
return tree, info, heads
def _node2dict(tree: TreeNode, replace_quotes: bool) -> dict[str, Any]:
children = [_node2dict(child, replace_quotes) for child in tree.children]
leaves = tree.get_yield()
node = {
'is_head' : tree.is_head,
'span' : {'from' : tree.from_index, 'to' : tree.to_index},
}
if tree.attributes:
node['attributes'] = tree.attributes.copy()
if 'deprel' in tree.attributes:
node['deprel'] = tree.attributes['deprel']
node['attributes'].pop('deprel') # type: ignore[attr-defined] # we know it’s a dict and has 'pop'
if children:
node.update({
'category' : tree.category,
'children' : children,
})
else:
assert (tree.terminal is not None)
node['orth'], node['base'], node['tag'] = tree.terminal
if replace_quotes:
node['orth'] = node['orth'].replace('"', '”') # type: ignore[attr-defined] # we know it’s a str and has 'replace'
node['base'] = node['base'].replace('"', '”') # type: ignore[attr-defined]
return node
[docs]
def tree2dict(tree: TreeNode, metadata: dict[str, Any] | None = None, replace_quotes: bool = False) -> dict[str, Any]:
"""Create a JSON-serialisable dictionary representation of a tree object .
Args:
tree: a hybrid syntactic tree.
metadata: any metadata to include in the tree dictionary.
replace_quotes: replace `'"'` quotation characters in terminals (text forms and lemmata) with `'”'`.
Returns:
a dictionary representation of the tree.
"""
if not metadata:
metadata = {}
return {'tree' : _node2dict(tree, replace_quotes), 'metadata' : metadata}
def _get_tree_dict_yield(tree: dict[str, Any]) -> list[dict[str, Any]]:
if 'children' not in tree:
return [tree]
else:
return list(chain.from_iterable(_get_tree_dict_yield(child) for child in tree['children']))
[docs]
def get_tree_dict_yield(tree: dict[str, Any]) -> list[dict[str, Any]]:
"""Return the list of terminal nodes of a tree’s dictionary representation, as read from left to right.
Returns:
dictionary representation of the terminals.
"""
return _get_tree_dict_yield(tree['tree'])
def _make_evalb_friendly(s: str | None) -> str:
if s is None:
return 'None'
else:
return s.replace(' ', '_').replace('(', 'LPAR').replace(')', 'RPAR')