DatabaseGroup / tree-similarity

Library for tree similarity algorithms and queries.
MIT License
75 stars 14 forks source link

Tree Similarity Library

We actively develop this library and things change continuously.

The goal of this repository is to be the home of all code corresponding to tree similarity. This code base is a starting point for new research ideas and students project. Implementation of new features should be consistent with this code base.

Currently this README serves everyone, users and contributors. It is disorganised with an idea that having disorganised and correct content is better than no content. It should be expanded on a regular basis and possibly split into README.md and README_CONTRIBUTOR.md.

Please find additional information at our project website.

Licence

All code in this repository is currently under the MIT licence. Each source file must contain the licence and the list of copyright holders (contributors to the source).

Building process

Install CMake for building and testing.

Clone the repository. To build the project, execute the following from the root directory (this will build all targets).

mkdir build
cd build
cmake ..
make

Execute make test to run all tests (currently there are only correctness tests).

In the build directory you find the binary ted that executes the algorithms from command line. Currently there is no help or documentation for this binary.

Installing the library with VCPKG

This library has been ported to VCPKG package manager. To include in your project, install with ./vcpkg install tree-similarity, then include the library in your project's CMakeFile

find_path(TREE_SIMILARITY_INCLUDE_DIRS "tree-similiarity/CMakeLists.txt")
target_include_directories(main PRIVATE ${TREE_SIMILARITY_INCLUDE_DIRS})

Input format

The library supports only the so-called bracket notation as the input format. For example, {A{B{X}{Y}{F}}{C}} corresponds to the following tree:

    A
   / \
  B   C
 /|\
X Y F

The curly braces encode labeled nodes. A label can be any string. If part of a label, curly braces must be escaped as \{ or \}.

{a{\{[b],\{key:"value"\}\}{}}} is an example input with complex labels, where:

Input string Target label
a a
\{[b],\{key:"value"\}\} {[b],{key:"value"}}
{} a node with empty label

Test cases for label parsing are in ./test/parser/parser_labels_test_data.txt

The parse_single() function of the bracket_notation_parser validates the input and throws an exception on incorrect syntax.

Applications rarely use the bracket notation. Therefore, we have implemented various converters.

JSON converter

The json-to-bracket.py script converts an input JSON document into a bracket notation.

Format converters

It is a generic converter implemented with ANTLR parser generator. The currently supported input formats are listed in the documentation.

Usage

The command_line program allows you to measure the Tree Edit Distance between 2 tree structures (using the Bracket Notation Format) using APTED.

The trees can be passed as string arguments:

./ted string {x{a}{b}} {x{a}{c}}

or read from files:

./ted file treeA.txt treeB.txt

Implemented algorithms

The library implements many tree similarity algorithms. We categorize them based on the use case. Note that sometimes the class name is different to the algorithm's name used in a paper. The recommended, state-of-the-art algorithm is marked bold.

Exact tree edit distance

Given two trees, $T$ and $T'$, compute the exact tree edit distance (TED) between $T$ and $T'$.

Short name C++ class Paper titles and DOIs
APTED apted_tree_index.h Tree edit distance: robust and memory-efficient
ZhangShasha zhang_shasha_tree_index.h Simple fast algorithms for the editing distance between trees and related problems

APTED supersedes older exact TED algorithms, like RTED, Demaine, and Klein. We evaluated them experimentally before this library was born. If interested, refer to their old Java implementations.

JSON similarity

Given two JSON trees, $T$ and $T'$, compute the JSON edit distance (JEDI) between $T$ and $T'$.

Short name C++ class Paper title and doi
QuickJEDI quickjedi_index.h JEDI: These aren't the JSON documents you're looking for?

Tree similarity self join

Given a collection of trees $\mathcal{T}$ and a tree edit distance threshold $\tau$. The TED join is defined as the set of all distinct tree pairs in $\mathcal{T}$ that are within edit distance $\tau$.

$\mathcal{T}\bowtie_{\tau}\mathcal{T}={T,T'}\in\mathcal{T}\times\mathcal{T}:T\ne T'\wedge\delta(T,T')\le\tau.$

Short name C++ class Paper title and doi
TJoin t_join.ti.h Effective filters and linear time verification for tree similarity joins
Tang tang_join_ti.h Scaling similarity joins over tree-structured data
Guha guha_join_ti.h Approximate XML joins
Binary bb_join_ti.h Similarity evaluation on tree-structured data
Histo histo_join_ti.h A survey on tree edit distance lower bound estimation techniques for similarity join on XML data

Exact tree edit distance with a known upper bound

Given two trees, $T$ and $T'$, and a true TED upper bound $\tau$ between $T$ and $T'$ compute the exact tree edit distance (TED) between $T$ and $T'$. These algorithms are faster than the classic TED algorithms thanks to pruning based on $\tau$.

Short name C++ class Paper title and doi
TopDiff touzet_kr_set_tree_index.h Minimal edit-based diffs for large trees
TopDiff+ implemented only in experiments Minimal edit-based diffs for large trees
Touzet (baseline) touzet_baseline_tree_index.h Comparing similar ordered trees in linear-time
Touzet (depth pruning) touzet_depth_pruning_truncated_tree_fix_tree_index.h Comparing similar ordered trees in linear-time

These algorithms can be also executed without a known upper bound by using the ted() function from ted_algorithm_touzet.h. The details of this technique are explained in Minimal edit-based diffs for large trees.

Tree edit distance lower bounds

These algorithms have a lower runtime complexity than TED algorithms and return a value less than or equal to the exact TED.

Short name C++ class Paper title and doi
SED (string edit distance) sed_tree_index.h A linear space algorithm for computing maximal common subsequences
Label intersection label_intersection.h

Tree edit distance upper bounds

These algorithms have lower runtime complexity than TED algorithms and return a value greater than or equal to the exact TED.

Short name C++ class Paper title and doi
CTED (constrained TED) cted_tree_index.h Algorithms for the constrained editing distance between ordered labeled trees and related problems
LGM (label guided mapping) lgm_tree_index.h Effective filters and linear time verification for tree similarity joins

Generating documentation

Install Doxygen for generating the documentation.

Execute the following (in the project's root directory) to generate the documentation.

doxygen doxygen.config

Then, open doc/html/index.html in your browser.

Notes on user workflow

  1. Convert the input data into the Bracket Notation Format or implement a new parser (e.g., http://www.antlr.org/).
  2. If necessary, implement custom Label class and/or custom CostModel class.
  3. Modify the types of Parser, Label, and CostModel inside tree_similarity.cc if you do not want to use the default types.
  4. Call make to (re-)build the framework.

TODOs

This is a list of of all TODOs split into a few categories.

Features.

README.md

README_CONTRIBUTOR.md

Random: