Struct lumberjack::Tree

pub struct Tree { /* fields omitted */ }

Tree

Trees represent constituency trees and consist of Nodes. The nodes are either Terminals or NonTerminals. Relations between nodes are expressed as Edges.

Methods

impl Tree

pub fn new(form: impl Into<String>, pos: impl Into<String>) -> Self

Construct a new Tree with a single Terminal.

use lumberjack::Tree;
use lumberjack::io::PTBFormat;

let tree = Tree::new("a", "A");
assert_eq!("(A a)", PTBFormat::Simple.tree_to_string(&tree).unwrap());

pub fn n_terminals(&self) -> usize

Get the number of terminals in the tree.

pub fn root(&self) -> NodeIndex

Get the index of the root of the tree.

pub fn terminals<'a>(&'a self) -> impl Iterator<Item = NodeIndex> + 'a

Get an iterator over the terminals in the constituency tree.

pub fn nonterminals<'a>(&'a self) -> impl Iterator<Item = NodeIndex> + 'a

Get an iterator over the terminal indices in the constituency tree.

pub fn parent(&self, node: NodeIndex) -> Option<(NodeIndex, EdgeIndex)>

Get the parent and corresponding edge of a tree node.

• Returns NodeIndex of immediately dominating node and corresponding EdgeIndex.
• Returns None if node doesn't exist or doesn't have incoming edges.

pub fn children<'a>(
    &'a self,
    node: NodeIndex
) -> impl Iterator<Item = (NodeIndex, EdgeIndex)> + 'a

Get an iterator over node's children.

pub fn move_terminal(&mut self, terminal: NodeIndex, index: usize)

Move a Terminal to a different position in the sentence.

This method does not reattach the Terminal and can change the Tree's projectivity.

Panics if index is out of bounds or the index of a NonTerminal is passed as argument.

pub fn insert_terminal(
    &mut self,
    parent: NodeIndex,
    terminal: Terminal
) -> NodeIndex

Insert a new terminal node.

Inserts a new terminal node with the given parent at the index specified in the Terminal's Span.

Panics if the specified parent node is a Terminal or if the index is out of bounds.

pub fn push_terminal(
    &mut self,
    form: impl Into<String>,
    pos: impl Into<String>
) -> Result<NodeIndex, Error>

Adds a Terminal to the end of the sentence.

This method adds a terminal to the end of the sentence and attaches it to the root node.

Returns Err if the root node is a Terminal.

use lumberjack::Tree;
use lumberjack::io::PTBFormat;

let mut tree = Tree::new("a", "A");
let root = tree.root();
let root = tree.insert_unary_above(root, "ROOT");
tree.push_terminal("b", "B").unwrap();
assert_eq!("(ROOT (A a) (B b))", PTBFormat::Simple.tree_to_string(&tree).unwrap());

pub fn insert_unary_above<S>(
    &mut self,
    child: NodeIndex,
    node_label: S
) -> NodeIndex where
    S: Into<String>, 

Insert a new unary node above a node.

Inserts a new unary node above child and returns the index of the inserted node.

pub fn insert_unary_below<S>(
    &mut self,
    node: NodeIndex,
    node_label: S
) -> Result<NodeIndex, Error> where
    S: Into<String>, 

Insert a new unary node below a node.

Insert a new node that is dominated by node and dominates all children of node.

Returns:

• NodeIndex of the new node
• Err if node is a terminal. The tree structure is unchanged when Err is returned.

pub fn remove_node(&mut self, node: NodeIndex) -> Result<Node, Error>

Remove a node.

This method will remove a node and attach all its children to the node above.

Returns Err without mutating the tree if the structure is broken by the removal:

• The last node can't be removed.
• The root can't be removed if it has more than one outgoing edge.
• Terminals can only be removed if they are not the last node in the branch.

Otherwise return Ok(node).

Panics if the node is not in the tree.

Removing a Terminal is fairly expensive since the spans for all nodes in the Tree will be recalculated. Removing a NonTerminal is cheaper, the outgoing edges of the removed node get attached to its parent, not changing the spans at all.

pub fn reattach_node(
    &mut self,
    new_parent: NodeIndex,
    edge: EdgeIndex
) -> Result<(EdgeIndex, Edge), Error>

Reattach a node.

Remove edge and reattach the node to new_parent with an empty edge weight. This method does not change the position of the reattached node wrt. linear order in the sentence.

Returns Err if:

• edge is the last outgoing edge of a node.
• new_parent is a Terminal node.

Returns Ok(old_edge) otherwise.

Panics if any of the indices is not present in the tree.

pub fn siblings<'a>(
    &'a self,
    node: NodeIndex
) -> Box<dyn Iterator<Item = (NodeIndex, EdgeIndex)> + 'a>

Get an iterator over node's siblings.

pub fn descendent_terminals(
    &self,
    node: NodeIndex
) -> TerminalDescendents<FixedBitSet>

Get an iterator over node's descendent.

pub fn are_siblings(&self, node_1: NodeIndex, node_2: NodeIndex) -> bool

Get sibling-relation of two tree nodes.

Returns whether two nodes are immediately dominated by the same node.

pub fn graph(&self) -> &StableGraph<Node, Edge>

Get an immutable reference to the underlying StableGraph.

pub fn is_projective(&self) -> bool

Returns whether the tree is projective.

pub fn project_nt_indices<F>(&self, match_fn: F) -> Vec<NodeIndex> where
    F: Fn(&Tree, NodeIndex) -> bool, 

Project indices of NonTerminals onto Terminals.

Projects the NodeIndex of NonTerminals matched by match_fn into a vector of length n_terminals. The method climbs the tree starting at each terminal and applies the closure at each step. If the closure returns true, the index of the currently considered NonTerminal is assigned to the corresponding slot in the vector.

Contrary to the other projection method, this method defaults to assigning the root node's index if no other NonTerminal was matched.

Returns a Vec<NodeIndex>.

pub fn map_climber_path<F>(&mut self, match_fn: F) where
    F: FnMut(&mut Tree, NodeIndex, NodeIndex) -> bool, 

Apply closure at each NonTerminal while climbing up the tree.

Climbs up the tree starting at each terminal and applies the closure at each step. If the closure returns true, climbing is stopped and the method advances to the next terminal.

Order of terminals does not necessarily correspond to linear order in the sentence.

The closure takes the Tree, the current NonTerminal's index and the current Terminal's index as arguments. The Tree structure can also be mutated in this method but it won't be reflected in the path if the mutation happens just above or below the current node.

E.g.

use lumberjack::Tree;

/// Remove all terminals' ancestors starting with `"A"`.
///
/// Terminates upon finding the first ancestor starting with `"B"`.
fn climb_map(tree: &mut Tree) {
    tree.map_climber_path(|tree, ancestor_idx, terminal_idx| {
        if tree[ancestor_idx].label().starts_with("A") {
            tree.remove_node(ancestor_idx).unwrap();
        } else if tree[ancestor_idx].label().starts_with("B") {
            let label = tree[ancestor_idx].label().to_owned();
            tree[terminal_idx]
                .features_mut()
                .insert(
                    "b_ancestor",
                    Some(label),
                );
            return true
        }
        false
    })
}

pub fn project_tag_set<F>(&mut self, feature_name: &str, match_fn: F) where
    F: Fn(&Tree, NodeIndex) -> bool, 

Project labels of NonTerminals onto Terminals.

Labels will be annotated under feature_name in each terminal's Features.

The method starts climbing the tree from each terminal and will stop climbing as soon as the match_fn returns true. If it never returns true no feature will be annotated.

E.g.

use lumberjack::Tree;

/// Annotate ancestor tags of the closest ancestor starting with `"A"` on terminals.
fn project_tags(tree: &mut Tree) {
    tree.project_tag_set("tag", |tree, ancestor_nt| {
        tree[ancestor_nt].label().starts_with("A")
    })
}

pub fn project_ids<F>(&mut self, feature_name: &str, match_fn: F) where
    F: Fn(&Tree, NodeIndex) -> bool, 

Project unique IDs for nodes with label in tag_set onto terminals.

IDs will be annotated under feature_name in each terminal's Features.

The method starts climbing the tree from each terminal and will stop climbing as soon as the match_fn returns true. If it never returns true no feature will be annotated.

E.g.

use lumberjack::Tree;

/// Add feature `"id"` with a unique identifiers on terminals.
///
/// Adds features with unique ID for the hierarchically closest NonTerminal starting with
/// `"A"` on the Terminal nodes.
fn project_unique_ids(tree: &mut Tree) {
    tree.project_ids("id", |tree, nonterminal| {
        tree[nonterminal].label().starts_with("A")
    });
}

Trait Implementations

impl ToConllx for Tree

fn to_conllx(&self) -> Sentence

Nonconsuming conversion to CONLLX.

impl TryFromConllx for Tree

fn try_from_conllx_with_absolute_encoding(
    sentence: &Sentence
) -> Result<Self, Error>

Attempt to construct a tree from labels annotated on a Sentence.

fn try_from_conllx_with_relative_encoding(
    sentence: &Sentence
) -> Result<Self, Error>

Attempt to construct a tree from labels annotated on a Sentence.

impl Encode for Tree

fn encode_absolute(&self) -> Result<AbsoluteEncoding, Error>

Absolute scale encoding.

fn annotate_absolute(&mut self) -> Result<(), Error>

Annotate absolute scale tags as features.

fn encode_relative(&self) -> Result<RelativeEncoding, Error>

Relative scale encoding.

fn annotate_relative(&mut self) -> Result<(), Error>

Annotate relative scale tags as features.

impl Decode for Tree

fn decode(encoding: AbsoluteEncoding, terminals: Vec<Terminal>) -> Self

Construct a tree from an absolute scale encoding.

fn remove_dummy_nodes(&mut self) -> Result<(), Error>

impl AnnotatePOS for Tree

fn annotate_pos<S>(
    &mut self,
    pos_iter: impl IntoIterator<Item = S>
) -> Result<(), Error> where
    S: Into<String>, 

impl TreeOps for Tree

fn annotate_parent_tag(&mut self, feature_name: &str) -> Result<(), Error>

Annotate the parent tag as a feature.

fn insert_intermediate<F>(&mut self, match_fn: F) -> Result<(), Error> where
    F: Fn(&Tree, NodeIndex) -> Option<String>, 

Insert an intermediate node above terminals.

fn filter_nonterminals<F>(&mut self, match_fn: F) -> Result<(), Error> where
    F: Fn(&Tree, NodeIndex) -> bool, 

Remove non-terminals not matched by the match function.

fn reattach_terminals<F>(&mut self, attachment: NodeIndex, match_fn: F) where
    F: Fn(&Tree, NodeIndex) -> bool, 

Reattach terminals matched by the match function.

impl UnaryChains for Tree

fn collapse_unary_chains(&mut self, delim: &str) -> Result<(), Error>

Collapse unary chains.

fn restore_unary_chains(&mut self, delim: &str) -> Result<(), Error>

Restore unary chains.

impl Projectivize for Tree

fn projectivize(&mut self)

impl PartialEq<Tree> for Tree

fn eq(&self, other: &Tree) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use]

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl From<Tree> for Sentence

fn from(tree: Tree) -> Self

Performs the conversion.

impl<'a> From<&'a Tree> for Sentence

fn from(tree: &'a Tree) -> Self

Performs the conversion.

impl Clone for Tree

fn clone(&self) -> Tree

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Tree

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl Index<NodeIndex<u32>> for Tree

type Output = Node

The returned type after indexing.

fn index(&self, index: NodeIndex) -> &Self::Output

Performs the indexing (container[index]) operation.

impl Index<EdgeIndex<u32>> for Tree

type Output = Edge

The returned type after indexing.

fn index(&self, index: EdgeIndex) -> &Self::Output

Performs the indexing (container[index]) operation.

impl IndexMut<NodeIndex<u32>> for Tree

fn index_mut(&mut self, index: NodeIndex) -> &mut Node

Performs the mutable indexing (container[index]) operation.

impl IndexMut<EdgeIndex<u32>> for Tree

fn index_mut(&mut self, index: EdgeIndex) -> &mut Edge

Performs the mutable indexing (container[index]) operation.