Discontinuous Data-Oriented Parsing
Branch: master
Clone or download
Latest commit 5202afd Dec 28, 2018
Type Name Latest commit message Commit time
Failed to load latest commit information.
bin re-factor CLI Feb 28, 2017
cpp-btree @ cac5dcb
docs treesearch: add --no-filename option Oct 17, 2018
gheap @ 67fc83b
sparsepp @ 605ebb9 update grammar with new rules / weights Dec 19, 2017
web set linespacing to avoid gaps in unicode line drawing characters of t… Oct 30, 2018
.editorconfig collect FTB compounds &c. Jan 8, 2018
.gitignore collect FTB compounds &c. Jan 8, 2018
CODINGSTYLE.rst code formatting Mar 23, 2018
LICENSE license Oct 17, 2011
MANIFEST.in fix installation wo/cython Dec 23, 2016
README.rst add link to demo Sep 26, 2018
Vagrantfile use Python 3 by default &c. Jan 17, 2016
alpino.headrules Add heuristic head assignment rules Aug 24, 2013
alpinosample.export support coindexed nodes with AlpinoXML input and Negra export output Apr 22, 2016
ftb.headrules head rules for french treebank Feb 20, 2014
ftb.modifierrules add explanation Jul 4, 2018
negra.headrules tweak head finding Oct 24, 2013
proper.prm Expand evaluation parameters to cover PTB, Alpino Aug 24, 2013
ptb.headrules Update PTB head rules Apr 28, 2015
sample.prm improve smoothing of unseen open class (word, tag) combinations Mar 23, 2018
setup.py update docs Jul 4, 2018
valgrind-python.supp Update Makefile. Oct 12, 2014


Discontinuous DOP

contrived discontinuous constituent for expository purposes.

The aim of this project is to parse discontinuous constituents in natural language using Data-Oriented Parsing (DOP), with a focus on global world domination. The grammar is extracted from a treebank of sentences annotated with (discontinuous) phrase-structure trees. Concretely, this project provides a statistical constituency parser with support for discontinuous constituents and Data-Oriented Parsing. Discontinuous constituents are supported through the grammar formalism Linear Context-Free Rewriting System (LCFRS), which is a generalization of Probabilistic Context-Free Grammar (PCFG). Data-Oriented Parsing allows re-use of arbitrary-sized fragments from previously seen sentences using Tree-Substitution Grammar (TSG).


General statistical parsing:

  • grammar formalisms: PCFG, PLCFRS
  • extract treebank grammar: trees decomposed into productions, relative frequencies as probabilities
  • exact k-best list of derivations
  • coarse-to-fine pruning: posterior threshold, k-best coarse-to-fine

DOP specific (parsing with tree fragments):

  • implementations: Goodman's DOP reduction, Double-DOP, DOP1.
  • estimators: relative frequency estimate (RFE), equal weights estimate (EWE).
  • objective functions: most probable parse (MPP), most probable derivation (MPD), most probable shortest derivation (MPSD), most likely tree with shortest derivation (SL-DOP), most constituents correct (MCC).

screenshot of parse tree produced by parser



Debian, Ubuntu based systems

The following instructions employ the --user option which means that Python packages will be installed to your home directory. Make sure that ~/.local/bin is in your PATH, or add it as follows (and restart terminal for it to take effect):

echo export PATH=$HOME/.local/bin:$PATH >> ~/.bashrc

To compile the latest development version of discodop, issue the following commands:

sudo apt-get install build-essential python3-dev python3-pip git
git clone --recursive git://github.com/andreasvc/disco-dop.git
cd disco-dop
pip3 install --user -r requirements.txt
make install

Other Linux systems

This assumes no root access, but assumes that gcc is installed.

Set environment variables so that software can be installed to the home directory (replace with equivalent for your shell if you do not use bash):

mkdir -p ~/.local
echo export PATH=$HOME/.local/bin:$PATH >> ~/.bashrc
echo export LD_LIBRARY_PATH=$HOME/.local/lib:/usr/lib64:/usr/lib >> ~/.bashrc
echo export PYTHONIOENCODING="utf-8" >> ~/.bashrc

After this, re-login or restart the shell to activate these settings. Install Python 3 from source, if not installed already. Python may require some libraries such as zlib and readline; installation steps are similar to the ones below:

wget http://www.python.org/ftp/python/3.6.1/Python-3.6.1.tgz
tar -xzf Python-*.tgz
cd Python-*
./configure --prefix=$HOME/.local --enable-shared
make install && cd ..

Check by running python3 that version 3.6.1 was installed successfully and is the default.

Install the latest development version of discodop:

wget https://github.com/andreasvc/disco-dop/archive/master.zip
unzip disco-dop-master.zip
cd disco-dop-master
pip3 install --user -r requirements.txt
make install

Mac OS X

  • Install Xcode and Homebrew

  • Install dependencies using Homebrew:

    brew install gcc python3 git
    git clone --recursive git://github.com/andreasvc/disco-dop.git
    cd disco-dop
    sudo pip3 install -r requirements.txt
    env CC=gcc sudo python3 setup.py install

Windows 10

Install the Windows subsystem for Linux (you may need to install a Windows update first), install Ubuntu from the Windows Store, and proceed with the steps above for Ubuntu-based systems.

Other systems

If you do not run Linux, it is possible to run the code inside a virtual machine. To do that, install Docker or Virtualbox and download a minimal Ubuntu image and follow the above installation instructions.

Usage, documentation

discodop can be used in three ways:

  1. through the command line; cf. the manual pages for the discodop command installed as part of the installation: man discodop.
  2. as a library, cf. the API reference and example notebooks
  3. Web interfaces

NB: avoid running discodop from within the source tree, to ensure that the installed versions of modules are imported.

The documentation can be found at http://discodop.readthedocs.io

Grammars, demo

A interactive demo of the parser is available at: https://lang.science.uva.nl/parser/

The pretrained grammars used in this demo are available at: https://lang.science.uva.nl/grammars/

The English, German, and Dutch grammars are described in van Cranenburgh et al., (2016); the French grammar appears in Sangati & van Cranenburgh (2015). For comparison, there is also an English grammar without discontinuous constituents (ptb-nodisc).


The Tree data structures in tree.py and the simple binarization algorithm in treetransforms.py were taken from NLTK. The Zhang-Shasha tree-edit distance algorithm in treedist.py was taken from https://github.com/timtadh/zhang-shasha Elements of the PLCFRS parser and punctuation re-attachment are based on code from rparse. Various other bits inspired by the Stanford parser, Berkeley parser, Bubs parser, &c.


Please cite the following paper if you use this code in the context of a publication:

    title={Data-Oriented Parsing with discontinuous constituents and function tags},
    author={van Cranenburgh, Andreas and Remko Scha and Rens Bod},
    journal={Journal of Language Modelling},