edit_distance: calculate edit distance between strings
authorKevin Locke <kevin@kevinlocke.name>
Sat, 19 Nov 2016 04:19:25 +0000 (21:19 -0700)
committerDavid Gibson <david@gibson.dropbear.id.au>
Wed, 23 Nov 2016 11:49:25 +0000 (22:49 +1100)
commite0663bef2ec73ed33b22e5a029284296495aab87
tree502f30ac7999825298f8076deaaa612e5706961c
parent214086cfafb1f5bf7785a29f4497f3adf196ed8b
edit_distance: calculate edit distance between strings

This commit creates the edit_distance module for calculating various
edit distance measures.  The edit distance quantifies the similarity
between two strings based on the number of modifications necessary to
turn one string into the other.  There are several edit distance
measures which differ in the operations which are permitted and the
cost (aka weight) of the operations.  This module provides functions
for calculating the Longest Common Subsequence (LCS), Levenshtein, and
Damerau-Levenshtein (restricted and unrestricted) distances.  Weighted
versions of these functions can be created by defining cost functions
as preprocessor macros when compiling this module.  Distances over
other array types (e.g. wide strings, integers, structs) can be
accomplished by defining the element type and equality test macros.

Signed-off-by: Kevin Locke <kevin@kevinlocke.name>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
16 files changed:
ccan/edit_distance/LICENSE [new symlink]
ccan/edit_distance/_info [new file with mode: 0644]
ccan/edit_distance/edit_distance-params.h [new file with mode: 0644]
ccan/edit_distance/edit_distance-private.h [new file with mode: 0644]
ccan/edit_distance/edit_distance.bib [new file with mode: 0644]
ccan/edit_distance/edit_distance.c [new file with mode: 0644]
ccan/edit_distance/edit_distance.h [new file with mode: 0644]
ccan/edit_distance/edit_distance_dl.c [new file with mode: 0644]
ccan/edit_distance/edit_distance_lcs.c [new file with mode: 0644]
ccan/edit_distance/edit_distance_lev.c [new file with mode: 0644]
ccan/edit_distance/edit_distance_rdl.c [new file with mode: 0644]
ccan/edit_distance/test/api.c [new file with mode: 0644]
ccan/edit_distance/test/run-types-short.c [new file with mode: 0644]
ccan/edit_distance/test/run-types-struct.c [new file with mode: 0644]
ccan/edit_distance/test/run-types-wchar.c [new file with mode: 0644]
ccan/edit_distance/test/run-weights.c [new file with mode: 0644]