Python APTED algorithm for the Tree Edit Distance
=================================================
Information
-----------
This is a Python implementation of the APTED algorithm, the
state-of-the-art solution for computing the tree edit distance [1,2],
which supersedes the RTED algorithm [3].
It is a port of the original Java implementation available at
https://github.com/DatabaseGroup/apted. During the port, some changes
were made to reduce the duplication on symmetric operations and to make
it look more Pythonic.
You can find more information about APTED on the following website
http://tree-edit-distance.dbresearch.uni-salzburg.at/
Citing APTED
------------
If you want to refer to APTED in a publication, please cite [1] and [2].
Licence
-------
The source code is published under the **MIT licence** found in the root
directory of the project and in the header of each source file.
Input
-----
Currently, we support only the so-called bracket notation for the input
trees, for example, encoding ``{A{B{X}{Y}{F}}{C}}`` corresponds to the
following tree:
::
A
/ \
B C
/|\
X Y F
Output
------
Our tool computes two outputs: - tree edit **distance** value - the
minimum cost of transforming the source tree into the destination tree.
- tree edit **mapping** - a mapping between nodes that corresponds to
the tree edit distance value. Nodes that are not mapped are deleted
(source tree) or inserted (destination tree).
Getting started
---------------
This version were tested on Python 2.7, 3.4, 3.5, and 3.6.
First, install it with pip:
::
pip install apted
If you want to compare the trees {a{b}{c}} and {a{b{d}}}, please run:
::
python -m apted -t {a{b}{c}} {a{b{d}}} -mv
The output is:
::
distance: 2
runtime: 0.000270843505859
{a{b}{c}} -> {a{b{d}}}
{c} -> None
{b} -> {b{d}}
None -> {d}
For more information on running options, please run
::
python -m apted -h
Customizing
-----------
It is possible to customize the algorithm to run with custom trees with
labels different from simple strings or custom data-structures.
Additionally it is possible to customize it to use a more sophisticated
cost model than unit cost.
For customizing the algorithm, you can create a custom *Config* class:
.. code:: python
from apted import APTED, Config
class CustomConfig(Config):
def rename(self, node1, node2):
"""Compares attribute .value of trees"""
return 1 if node1.value != node2.value else 0
def children(self, node):
"""Get left and right children of binary tree"""
return [x for x in (node.left, node.right) if x]
apted = APTED(tree1, tree2, CustomConfig())
ted = apted.compute_edit_distance()
mapping = apted.compute_edit_mapping()
By default, the included *Config* class consider trees with the atribute
*name* as label and the atribute *children* as children in left to right
preorder.
In addition to the Config class, we also provide a
*PerEditOperationConfig* class that allows you to specify weights for
each operation:
.. code:: python
from apted import APTED, PerEditOperationConfig
apted = APTED(tree1, tree2, PerEditOperationConfig(.4, .4, .6))
ted = apted.compute_edit_distance()
mapping = apted.compute_edit_mapping()
If your main usage for APTED is to obtain the mapping, it is possible to
configure the algorith to keep track of the mapping during the
execution. To do so, we provide a function, *meta\_chained\_config*,
that modifies existing *Config* classes:
.. code:: python
from apted import APTED, PerEditOperationConfig, meta_chained_config
new_config = meta_chained_config(PerEditOperationConfig)
apted = APTED(tree1, tree2, new_config(.4, .4, .6))
ted = apted.compute_edit_distance()
mapping = apted.compute_edit_mapping()
Note that this approach uses much more memory and we didn't evaluate if
it is faster than the original algorithm for the mapping with huge
trees. The execution time for the mapping tests were about the same as
the original algorithm.
Contributing
------------
Feel free to submit pull resquests to this repository.
The codebase follows the PEP8 conventions. However it is not too strict.
For instance, it is okay to have lines with a little more than 79
characters, but try not to exceed too much.
Please, run ``python test.py`` during your changes to make sure
everything is working. It is also desirable to use coverage.py to check
test coverage: ``coverage run test.py``.
Original Authors
----------------
- Mateusz Pawlik
- Nikolaus Augsten
Implementation Author
---------------------
- Joao Felipe Pimentel
References
----------
1. M. Pawlik and N. Augsten. *Tree edit distance: Robust and memory-
efficient*. Information Systems 56. 2016.
2. M. Pawlik and N. Augsten. *Efficient Computation of the Tree Edit
Distance*. ACM Transactions on Database Systems (TODS) 40(1). 2015.
3. M. Pawlik and N. Augsten. *RTED: A Robust Algorithm for the Tree Edit
Distance*. PVLDB 5(4). 2011.
Raw data
{
"_id": null,
"home_page": "https://github.com/JoaoFelipe/apted",
"name": "apted",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "APTED TED tree edit distance",
"author": "Joao Pimentel",
"author_email": "joaofelipenp@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/e0/29/3a42b2fb26272a464a9fbf455928a7e4255efa2e6f56679e9c0adaaf798a/apted-1.0.3.tar.gz",
"platform": "",
"description": "Python APTED algorithm for the Tree Edit Distance\n=================================================\n\nInformation\n-----------\n\nThis is a Python implementation of the APTED algorithm, the\nstate-of-the-art solution for computing the tree edit distance [1,2],\nwhich supersedes the RTED algorithm [3].\n\nIt is a port of the original Java implementation available at\nhttps://github.com/DatabaseGroup/apted. During the port, some changes\nwere made to reduce the duplication on symmetric operations and to make\nit look more Pythonic.\n\nYou can find more information about APTED on the following website\nhttp://tree-edit-distance.dbresearch.uni-salzburg.at/\n\nCiting APTED\n------------\n\nIf you want to refer to APTED in a publication, please cite [1] and [2].\n\nLicence\n-------\n\nThe source code is published under the **MIT licence** found in the root\ndirectory of the project and in the header of each source file.\n\nInput\n-----\n\nCurrently, we support only the so-called bracket notation for the input\ntrees, for example, encoding ``{A{B{X}{Y}{F}}{C}}`` corresponds to the\nfollowing tree:\n\n::\n\n A\n / \\\n B C\n /|\\\n X Y F\n\nOutput\n------\n\nOur tool computes two outputs: - tree edit **distance** value - the\nminimum cost of transforming the source tree into the destination tree.\n- tree edit **mapping** - a mapping between nodes that corresponds to\nthe tree edit distance value. Nodes that are not mapped are deleted\n(source tree) or inserted (destination tree).\n\nGetting started\n---------------\n\nThis version were tested on Python 2.7, 3.4, 3.5, and 3.6.\n\nFirst, install it with pip:\n\n::\n\n pip install apted\n\nIf you want to compare the trees {a{b}{c}} and {a{b{d}}}, please run:\n\n::\n\n python -m apted -t {a{b}{c}} {a{b{d}}} -mv\n\nThe output is:\n\n::\n\n distance: 2\n runtime: 0.000270843505859\n {a{b}{c}} -> {a{b{d}}}\n {c} -> None\n {b} -> {b{d}}\n None -> {d}\n\nFor more information on running options, please run\n\n::\n\n python -m apted -h\n\nCustomizing\n-----------\n\nIt is possible to customize the algorithm to run with custom trees with\nlabels different from simple strings or custom data-structures.\nAdditionally it is possible to customize it to use a more sophisticated\ncost model than unit cost.\n\nFor customizing the algorithm, you can create a custom *Config* class:\n\n.. code:: python\n\n from apted import APTED, Config\n\n class CustomConfig(Config):\n def rename(self, node1, node2):\n \"\"\"Compares attribute .value of trees\"\"\"\n return 1 if node1.value != node2.value else 0\n\n def children(self, node):\n \"\"\"Get left and right children of binary tree\"\"\"\n return [x for x in (node.left, node.right) if x]\n\n apted = APTED(tree1, tree2, CustomConfig())\n ted = apted.compute_edit_distance()\n mapping = apted.compute_edit_mapping()\n\nBy default, the included *Config* class consider trees with the atribute\n*name* as label and the atribute *children* as children in left to right\npreorder.\n\nIn addition to the Config class, we also provide a\n*PerEditOperationConfig* class that allows you to specify weights for\neach operation:\n\n.. code:: python\n\n from apted import APTED, PerEditOperationConfig\n\n apted = APTED(tree1, tree2, PerEditOperationConfig(.4, .4, .6))\n ted = apted.compute_edit_distance()\n mapping = apted.compute_edit_mapping()\n\nIf your main usage for APTED is to obtain the mapping, it is possible to\nconfigure the algorith to keep track of the mapping during the\nexecution. To do so, we provide a function, *meta\\_chained\\_config*,\nthat modifies existing *Config* classes:\n\n.. code:: python\n\n from apted import APTED, PerEditOperationConfig, meta_chained_config\n\n new_config = meta_chained_config(PerEditOperationConfig)\n apted = APTED(tree1, tree2, new_config(.4, .4, .6))\n ted = apted.compute_edit_distance()\n mapping = apted.compute_edit_mapping()\n\nNote that this approach uses much more memory and we didn't evaluate if\nit is faster than the original algorithm for the mapping with huge\ntrees. The execution time for the mapping tests were about the same as\nthe original algorithm.\n\nContributing\n------------\n\nFeel free to submit pull resquests to this repository.\n\nThe codebase follows the PEP8 conventions. However it is not too strict.\nFor instance, it is okay to have lines with a little more than 79\ncharacters, but try not to exceed too much.\n\nPlease, run ``python test.py`` during your changes to make sure\neverything is working. It is also desirable to use coverage.py to check\ntest coverage: ``coverage run test.py``.\n\nOriginal Authors\n----------------\n\n- Mateusz Pawlik\n- Nikolaus Augsten\n\nImplementation Author\n---------------------\n\n- Joao Felipe Pimentel\n\nReferences\n----------\n\n1. M. Pawlik and N. Augsten. *Tree edit distance: Robust and memory-\n efficient*. Information Systems 56. 2016.\n\n2. M. Pawlik and N. Augsten. *Efficient Computation of the Tree Edit\n Distance*. ACM Transactions on Database Systems (TODS) 40(1). 2015.\n\n3. M. Pawlik and N. Augsten. *RTED: A Robust Algorithm for the Tree Edit\n Distance*. PVLDB 5(4). 2011.\n\n\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "APTED algorithm for the Tree Edit Distance",
"version": "1.0.3",
"split_keywords": [
"apted",
"ted",
"tree",
"edit",
"distance"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "b971c2bcf92376d3ae65d57111d33f577aca68d343e1b7b1914a3767bfbac18e",
"md5": "4ce5c24e3d81f16f9fc9887677e0f83f",
"sha256": "74193369d023649d335269e67c4df07f922959e5ac2597de1b79af4e694150e8"
},
"downloads": -1,
"filename": "apted-1.0.3-py3-none-any.whl",
"has_sig": false,
"md5_digest": "4ce5c24e3d81f16f9fc9887677e0f83f",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 40566,
"upload_time": "2017-11-08T13:03:21",
"upload_time_iso_8601": "2017-11-08T13:03:21.831300Z",
"url": "https://files.pythonhosted.org/packages/b9/71/c2bcf92376d3ae65d57111d33f577aca68d343e1b7b1914a3767bfbac18e/apted-1.0.3-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "e0293a42b2fb26272a464a9fbf455928a7e4255efa2e6f56679e9c0adaaf798a",
"md5": "e8649c623d27d057a91c73a4a2cba51a",
"sha256": "befa5181e2d4457fa88e54995a82604ee048bb2fbc781ea97d8e1856b4715ce9"
},
"downloads": -1,
"filename": "apted-1.0.3.tar.gz",
"has_sig": false,
"md5_digest": "e8649c623d27d057a91c73a4a2cba51a",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 24547,
"upload_time": "2017-11-08T13:03:23",
"upload_time_iso_8601": "2017-11-08T13:03:23.294550Z",
"url": "https://files.pythonhosted.org/packages/e0/29/3a42b2fb26272a464a9fbf455928a7e4255efa2e6f56679e9c0adaaf798a/apted-1.0.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2017-11-08 13:03:23",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "JoaoFelipe",
"github_project": "apted",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "apted"
}
JSON
