TCS Alignment Toolbox Version 3.1.0

Version 3.1.0 now supports edit distances for sets, trees, and forests
Added by Benjamin Paassen 3 months ago

Version 3.1.0 of the TCSAlignmentToolbox now supports edit distances on new data structures, in particular:
  • sets via the new sets module. A set alignment is performed via the Hungarian algorithm and requires O(n³) operations where n is the number of elements in the larger set
  • trees via the new trees module. For the tree edit distance we support the Algorithm by Zhang and Shasha (1989). We also implement backtracing, both crisp and soft.
  • forests via the new trees module. Forests can be either ordered lists of trees, in which case we perform a standard string edit distance based on the tree edit distances between all pairwise tree assignments; or forests can be defined as unordered lists of trees, in which case we perform a set edit distance via the Hungarian algorithm.