Module edit_distance 

Schedule-alignment and edit-distance algorithms shared by Hermit tools.

Structs

BubbleSortIter

The states a bubble sort of a permutation passes through, one adjacent swap at a time: cursor 0 is the permutation itself and cursor Self::swap_distance is sorted order.

ExpandedPermResult

Result of generating a permutation from the source vec to the target while maintaining the position of values by marking unmatched values in the target with None instead of just removing them

NeedlemanWunsch

Perm

PermutationResult

Output from generating a permutation between two vecs of items. It provides the actual permutation generated as well as information about unmatched items from both the source and target arrays

Enums

NeedlemanWunschError

Trace

Functions

bubble_sort_distance

damerau_lev

Finds the edit distance between source and target, taking into account additions, deletions, and swaps. This has a time complexity of O(n^2) and a space complexity of O(n^2).

generate_expanded_permutation

generating a permutation from the source vec to the target while maintaining the position of values by marking unmatched values in the target with None instead of just removing them

generate_permutation

Generate a permutation that when applied to the first argument’s elements produces the second argument. If there are elements in the first that are not in the second (and vice versa) then those elements will not be present in the final permutation, and thus the permutation will be shorter than both input slices. Information about which elements are unmatched in both the source and target vectors is provided in the result

iterable_bubble_sort

iterable_bubble_sort_from_perm

kendall_tau

Finds the distance between source and target by looking at only swaps.