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)
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]