[](https://badge.fury.io/py/node-distance)
[](https://img.shields.io/pypi/dm/node-distance)
[](https://zenodo.org/badge/latestdoi/433801845)
# node-distance: Tree node distances as features
Compute distance between all nodes of a tree, and estimate an histogram that can be used as features for other models.
### Toy Text Corpus
```py
corpus = "Als Ada Lovelace auf einem Ball den Mathematiker Charles Babbage traf, der sie einlud, die von ihm erfundene „Differenzmaschine“ anzusehen, war sie hellauf begeistert. Die Maschine konnte selbstständig addieren und subtrahieren, doch Ada war klar, dass die Möglichkeiten damit noch lange nicht erschöpft waren. Sie träumte davon, dass eine solche Maschine eines Tages sogar Musik abspielen könnte, und ersann so die Idee eines modernen Computers. 1845 legte sie den ersten Algorithmus zur maschinellen Berechnung der Bernoulli-Zahlen vor und wird daher von vielen als erste Computerprogrammiererin der Welt gefeiert."
```
(Source: DWDS, Wort des Tages, "Algorithmus, der", 27.11.2021, URL: https://www.dwds.de/adt )
### Extract the graph edges from a dependency tree with SpaCy/Stanza/Trankit
- We assume that NodeIDs are numbers `[1,2,3,...]` starting with 1.
The NodeIDs are equivalent to the TokenIDs in Conll-U.
- An graph edge is a tuple `(ParentID, NodeID)`
Example, SpaCy:
```py
# load the SpaCy model
import de_dep_news_trf
model = de_dep_news_trf.load()
# extract the edges for each sentence
import node_distance as nd
all_edges, num_nodes = nd.extract_edges_from_spacy(corpus, model)
```
Example, stanza:
```py
# load the stanza model
import stanza
model = stanza.Pipeline(
lang='de', processors='tokenize,mwt,pos,lemma,depparse',
tokenize_pretokenized=False)
# extract the edges for each sentence
import node_distance as nd
all_edges, num_nodes = nd.extract_edges_from_stanza(corpus, model)
```
Example, trankit:
```py
# load the trankit model
import trankit
model = trankit.Pipeline(lang='german', gpu=False, cache_dir='./cache')
# extract the edges for each sentence
import node_distance as nd
all_edges, num_nodes = nd.extract_edges_from_trankit(corpus, model)
```
`num_nodes` with the number of tokens/nodes in each sentence.
`all_edges` contains lists of edges for each sentence, e.g.
```py
# Edges of the 3rd sentence
edges = all_edges[2]
# Edge between the 6th token/node and its parent node
edge = edges[6]
parent_id, node_id = edge
```
### Compute Shortest Paths between Nodes
Compute node distances and the corresponding token distances
```py
import node_distance as nd
nodedist, tokendist, indicies = nd.node_token_distances(all_edges, num_nodes, cutoff=25)
```
### Histograms as Features
The Distribution of node distances:
```py
import node_distance as nd
xobs, pdf, _ = nd.nodedist_distribution(nodedist, xmin=1, xmax=12)
import matplotlib.pyplot as plt
plt.bar(xobs, pdf);
plt.title("distribution of node distances");
plt.xlabel("node distance");
plt.ylabel("PDF");
plt.show();
```
Distribution of token distance vs node distance:
```py
import node_distance as nd
xobs, pdf, _ = nd.tokenvsnode_distribution(tokendist, nodedist, xmin=-5, xmax=15)
import matplotlib.pyplot as plt
plt.bar(xobs, pdf);
plt.title("Distribution of token distance vs node distance");
plt.xlabel("token distance minus node distance");
plt.ylabel("PDF");
plt.show();
```
## Appendix
### Installation
The `node-distance` [git repo](http://github.com/ulf1/node-distance) is available as [PyPi package](https://pypi.org/project/node-distance)
```sh
pip install node-distance
pip install git+ssh://git@github.com/ulf1/node-distance.git
```
### Install a virtual environment
It is recommended to install python packages into a seperate virtual environement. (If your git repo is stored in a folder with whitespaces, then don't use the subfolder `.venv`. Use an absolute path without whitespaces.)
```sh
python3 -m venv .venv
source .venv/bin/activate
pip install --upgrade pip
pip install -r requirements.txt --no-cache-dir
pip install -r requirements-dev.txt --no-cache-dir
pip install -r requirements-demo.txt --no-cache-dir
```
The usage example and demo notebooks might require spacy, stanza and trankit to be installed. You should download the pretrained models beforehand, e.g. pretrained models for German:
```sh
python -m spacy download de_dep_news_trf
python -c "import stanza; stanza.download(lang='de')"
python -c "import trankit; trankit.Pipeline(lang='german', gpu=False, cache_dir='./cache')"
```
### Python commands
* Jupyter for the examples: `jupyter lab`
* Check syntax: `flake8 --ignore=F401 --exclude=$(grep -v '^#' .gitignore | xargs | sed -e 's/ /,/g')`
* Run Unit Tests: `PYTHONPATH=. pytest`
Publish
```sh
python setup.py sdist
twine upload -r pypi dist/*
```
### Clean up
```sh
find . -type f -name "*.pyc" | xargs rm
find . -type d -name "__pycache__" | xargs rm -r
rm -r .pytest_cache
rm -r .venv
```
### Support
Please [open an issue](https://github.com/ulf1/node-distance/issues/new) for support.
### Contributing
Please contribute using [Github Flow](https://guides.github.com/introduction/flow/). Create a branch, add commits, and [open a pull request](https://github.com/ulf1/node-distance/compare/).
### Acknowledgements
The "Evidence" project was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - [433249742](https://gepris.dfg.de/gepris/projekt/433249742) (GU 798/27-1; GE 1119/11-1).
### Maintenance
- till 31.Aug.2023 (v0.1.0) the code repository was maintained within the DFG project [433249742](https://gepris.dfg.de/gepris/projekt/433249742)
- since 01.Sep.2023 (v0.2.0) the code repository is maintained by Ulf Hamster.
### Citation
You can cite the following paper if you want to use this repository in your research work.
```
@inproceedings{hamster-2022-everybody,
title = "Everybody likes short sentences - A Data Analysis for the Text Complexity {DE} Challenge 2022",
author = "Hamster, Ulf A.",
booktitle = "Proceedings of the GermEval 2022 Workshop on Text Complexity Assessment of German Text",
month = sep,
year = "2022",
address = "Potsdam, Germany",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/2022.germeval-1.2",
pages = "10--14",
}
```
Raw data
{
"_id": null,
"home_page": "http://github.com/ulf1/node-distance",
"name": "node-distance",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.6",
"maintainer_email": "",
"keywords": "",
"author": "Ulf Hamster",
"author_email": "554c46@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/eb/a0/938ff1c9efba446fe32648a6540afab950bcf9f200498d0c11877b05c1c9/node-distance-0.2.0.tar.gz",
"platform": null,
"description": "[](https://badge.fury.io/py/node-distance)\n[](https://img.shields.io/pypi/dm/node-distance)\n[](https://zenodo.org/badge/latestdoi/433801845)\n\n\n# node-distance: Tree node distances as features\nCompute distance between all nodes of a tree, and estimate an histogram that can be used as features for other models.\n\n### Toy Text Corpus\n\n```py\ncorpus = \"Als Ada Lovelace auf einem Ball den Mathematiker Charles Babbage traf, der sie einlud, die von ihm erfundene \u201eDifferenzmaschine\u201c anzusehen, war sie hellauf begeistert. Die Maschine konnte selbstst\u00e4ndig addieren und subtrahieren, doch Ada war klar, dass die M\u00f6glichkeiten damit noch lange nicht ersch\u00f6pft waren. Sie tr\u00e4umte davon, dass eine solche Maschine eines Tages sogar Musik abspielen k\u00f6nnte, und ersann so die Idee eines modernen Computers. 1845 legte sie den ersten Algorithmus zur maschinellen Berechnung der Bernoulli-Zahlen vor und wird daher von vielen als erste Computerprogrammiererin der Welt gefeiert.\"\n```\n(Source: DWDS, Wort des Tages, \"Algorithmus, der\", 27.11.2021, URL: https://www.dwds.de/adt )\n\n\n### Extract the graph edges from a dependency tree with SpaCy/Stanza/Trankit\n- We assume that NodeIDs are numbers `[1,2,3,...]` starting with 1. \n The NodeIDs are equivalent to the TokenIDs in Conll-U.\n- An graph edge is a tuple `(ParentID, NodeID)`\n\n\nExample, SpaCy:\n```py\n# load the SpaCy model\nimport de_dep_news_trf\nmodel = de_dep_news_trf.load()\n# extract the edges for each sentence\nimport node_distance as nd\nall_edges, num_nodes = nd.extract_edges_from_spacy(corpus, model)\n```\n\nExample, stanza:\n```py\n# load the stanza model\nimport stanza\nmodel = stanza.Pipeline(\n lang='de', processors='tokenize,mwt,pos,lemma,depparse',\n tokenize_pretokenized=False)\n# extract the edges for each sentence\nimport node_distance as nd\nall_edges, num_nodes = nd.extract_edges_from_stanza(corpus, model)\n```\n\nExample, trankit:\n```py\n# load the trankit model\nimport trankit\nmodel = trankit.Pipeline(lang='german', gpu=False, cache_dir='./cache')\n# extract the edges for each sentence\nimport node_distance as nd\nall_edges, num_nodes = nd.extract_edges_from_trankit(corpus, model)\n```\n\n`num_nodes` with the number of tokens/nodes in each sentence.\n`all_edges` contains lists of edges for each sentence, e.g.\n```py\n# Edges of the 3rd sentence\nedges = all_edges[2]\n# Edge between the 6th token/node and its parent node\nedge = edges[6]\nparent_id, node_id = edge\n```\n\n### Compute Shortest Paths between Nodes\nCompute node distances and the corresponding token distances\n\n```py\nimport node_distance as nd\nnodedist, tokendist, indicies = nd.node_token_distances(all_edges, num_nodes, cutoff=25)\n```\n\n### Histograms as Features\n\nThe Distribution of node distances:\n```py\nimport node_distance as nd\nxobs, pdf, _ = nd.nodedist_distribution(nodedist, xmin=1, xmax=12)\n\nimport matplotlib.pyplot as plt\nplt.bar(xobs, pdf);\nplt.title(\"distribution of node distances\");\nplt.xlabel(\"node distance\");\nplt.ylabel(\"PDF\");\nplt.show();\n```\n\nDistribution of token distance vs node distance:\n```py\nimport node_distance as nd\nxobs, pdf, _ = nd.tokenvsnode_distribution(tokendist, nodedist, xmin=-5, xmax=15)\n\nimport matplotlib.pyplot as plt\nplt.bar(xobs, pdf);\nplt.title(\"Distribution of token distance vs node distance\");\nplt.xlabel(\"token distance minus node distance\");\nplt.ylabel(\"PDF\");\nplt.show();\n```\n\n\n## Appendix\n\n### Installation\nThe `node-distance` [git repo](http://github.com/ulf1/node-distance) is available as [PyPi package](https://pypi.org/project/node-distance)\n\n```sh\npip install node-distance\npip install git+ssh://git@github.com/ulf1/node-distance.git\n```\n\n### Install a virtual environment\nIt is recommended to install python packages into a seperate virtual environement. (If your git repo is stored in a folder with whitespaces, then don't use the subfolder `.venv`. Use an absolute path without whitespaces.)\n\n```sh\npython3 -m venv .venv\nsource .venv/bin/activate\npip install --upgrade pip\npip install -r requirements.txt --no-cache-dir\npip install -r requirements-dev.txt --no-cache-dir\npip install -r requirements-demo.txt --no-cache-dir\n```\n\nThe usage example and demo notebooks might require spacy, stanza and trankit to be installed. You should download the pretrained models beforehand, e.g. pretrained models for German:\n\n```sh\npython -m spacy download de_dep_news_trf\npython -c \"import stanza; stanza.download(lang='de')\"\npython -c \"import trankit; trankit.Pipeline(lang='german', gpu=False, cache_dir='./cache')\"\n```\n\n### Python commands\n\n* Jupyter for the examples: `jupyter lab`\n* Check syntax: `flake8 --ignore=F401 --exclude=$(grep -v '^#' .gitignore | xargs | sed -e 's/ /,/g')`\n* Run Unit Tests: `PYTHONPATH=. pytest`\n\nPublish\n\n```sh\npython setup.py sdist \ntwine upload -r pypi dist/*\n```\n\n### Clean up \n\n```sh\nfind . -type f -name \"*.pyc\" | xargs rm\nfind . -type d -name \"__pycache__\" | xargs rm -r\nrm -r .pytest_cache\nrm -r .venv\n```\n\n### Support\nPlease [open an issue](https://github.com/ulf1/node-distance/issues/new) for support.\n\n\n### Contributing\nPlease contribute using [Github Flow](https://guides.github.com/introduction/flow/). Create a branch, add commits, and [open a pull request](https://github.com/ulf1/node-distance/compare/).\n\n### Acknowledgements\nThe \"Evidence\" project was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - [433249742](https://gepris.dfg.de/gepris/projekt/433249742) (GU 798/27-1; GE 1119/11-1).\n\n### Maintenance\n- till 31.Aug.2023 (v0.1.0) the code repository was maintained within the DFG project [433249742](https://gepris.dfg.de/gepris/projekt/433249742)\n- since 01.Sep.2023 (v0.2.0) the code repository is maintained by Ulf Hamster.\n\n### Citation\nYou can cite the following paper if you want to use this repository in your research work.\n\n```\n@inproceedings{hamster-2022-everybody,\n title = \"Everybody likes short sentences - A Data Analysis for the Text Complexity {DE} Challenge 2022\",\n author = \"Hamster, Ulf A.\",\n booktitle = \"Proceedings of the GermEval 2022 Workshop on Text Complexity Assessment of German Text\",\n month = sep,\n year = \"2022\",\n address = \"Potsdam, Germany\",\n publisher = \"Association for Computational Linguistics\",\n url = \"https://aclanthology.org/2022.germeval-1.2\",\n pages = \"10--14\",\n}\n```\n\n\n",
"bugtrack_url": null,
"license": "Apache License 2.0",
"summary": "Compute distance between all nodes of a tree, and estimate an histogram that can be used as features for other models.",
"version": "0.2.0",
"project_urls": {
"Homepage": "http://github.com/ulf1/node-distance"
},
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "eba0938ff1c9efba446fe32648a6540afab950bcf9f200498d0c11877b05c1c9",
"md5": "a5fd741232b051c0f97fbdf252e41a6c",
"sha256": "a1a271d85f80d590efc34622e9d50903e1d8a3f584dc11f06c1498b84e34c631"
},
"downloads": -1,
"filename": "node-distance-0.2.0.tar.gz",
"has_sig": false,
"md5_digest": "a5fd741232b051c0f97fbdf252e41a6c",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.6",
"size": 10508,
"upload_time": "2023-07-10T15:36:39",
"upload_time_iso_8601": "2023-07-10T15:36:39.374392Z",
"url": "https://files.pythonhosted.org/packages/eb/a0/938ff1c9efba446fe32648a6540afab950bcf9f200498d0c11877b05c1c9/node-distance-0.2.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-07-10 15:36:39",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "ulf1",
"github_project": "node-distance",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"requirements": [
{
"name": "numpy",
"specs": [
[
"<",
"2"
],
[
">=",
"1.19.5"
]
]
},
{
"name": "networkx",
"specs": [
[
"<",
"3"
],
[
">=",
"2.5.1"
]
]
}
],
"lcname": "node-distance"
}
JSON
