Chu-Liu-Edmonds Algorithm from TurpoParser.

This package wraps the Chu-Liu-Edmonds maximum spanning algorithm from TurboParser for use within Python.

The original package was made by https://github.com/andersjo/dependency_decoding .

Documentation

The package provides a function chu_liu_edmonds, which accepts an N×N score matrix as argument, where N is the sentence length including the artificial root node, which has index 0. The (i,j)-th cell is the score for the edge j→i. In other words, a row gives the scores for the different heads of a dependent.

A np.nan cell value informs the algorithm to skip the edge.

Example usage:

import numpy as np
from ufal.chu_liu_edmonds import chu_liu_edmonds

np.random.seed(42)
score_matrix = np.random.rand(3, 3)
heads, tree_score = chu_liu_edmonds(score_matrix)
print(heads, tree_score)

Install

Binary wheels of the package are provided, just run

pip install ufal.chu_liu_edmonds

Updating the Cython-generated Module

To update the Cython-generated module, run

cython --module-name ufal.chu_liu_edmonds._chu_liu_edmonds chu_liu_edmonds.pyx -o chu_liu_edmonds.cpp