TCS Alignment Toolbox Version 3.1.0

Version 3.1.0 now supports edit distances for sets, trees, and forests
Added by Benjamin Paassen 12 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.