Source code for hydra.utils.hybrid_tree

"""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')