git.ozlabs.org Git - ccan/blob - ccan/edit_distance/edit_distance.h

   1 /** @file
   2  * Main header file for edit_distance which defines the module API.
   3  *
   4  * @copyright 2016 Kevin Locke <kevin@kevinlocke.name>
   5  *            MIT license - see LICENSE file for details
   6  */
   7 #ifndef CCAN_EDIT_DISTANCE_H
   8 #define CCAN_EDIT_DISTANCE_H
   9
  10 #include <stddef.h>             /* size_t */
  11
  12 #ifndef ed_dist
  13 /**
  14  * ed_dist - Type in which the edit distance is expressed.
  15  *
  16  * The name @c ed_dist can be defined to another algebraic type (or this
  17  * typedef can be edited) when compiling this module.
  18  */
  19 typedef unsigned int ed_dist;
  20 #endif
  21
  22 #ifndef ed_elem
  23 /**
  24  * ed_elem - Element type of arrays for which the edit distance is calculated.
  25  *
  26  * Changing this type often requires changing #ED_HAS_ELEM, #ED_HASH_ELEM, and
  27  * #ED_HASH_MAX.  It requires changing #ED_ELEM_EQUAL for non-primitive types.
  28  * These can be changed in edit_distance-params.h or defined externally.
  29  */
  30 typedef char ed_elem;
  31 #endif
  32
  33 #ifndef ed_size
  34 /**
  35  * ed_size - Type in which the array size is expressed.
  36  *
  37  * The name @c ed_size can be defined to another algebraic type (or this
  38  * typedef can be edited) when compiling this module.  If @c ed_size is a
  39  * signed type, the caller must ensure passed values are non-negative.
  40  * @c ed_size must be large enough to hold @c max(slen,tlen)+2, it does not
  41  * need to be large enough to hold @c slen*tlen.
  42  *
  43  * Note: @c ed_size is only likely to have a noticeable impact in
  44  * edit_distance_dl() which maintains an array of @c #ED_HASH_MAX+1 ::ed_size
  45  * values.
  46  */
  47 typedef unsigned int ed_size;
  48 #endif
  49
  50 /**
  51  * ed_measure - Supported edit distance measures.
  52  */
  53 enum ed_measure {
  54         /**
  55          * Longest Common Subsequence (LCS) distance.
  56          *
  57          * The LCS distance is an edit distance measured by the number of
  58          * insert and delete operations necessary to turn @p src into @p tgt.
  59          *
  60          * This implementation uses an iterative version of the Wagner-Fischer
  61          * algorithm @cite Wagner74 which requires <code>O(slen * tlen)</code>
  62          * time and <code>min(slen, tlen) + 1</code> space.
  63          */
  64         EDIT_DISTANCE_LCS = 1,
  65         /**
  66          * Levenshtein distance.
  67          *
  68          * The Levenshtein distance is an edit distance measured by the number
  69          * of insert, delete, and substitute operations necessary to turn
  70          * @p src into @p tgt as described by Vladimir Levenshtein.
  71          * @cite Levenshtein66
  72          *
  73          * This implementation uses a modified version of the Wagner-Fischer
  74          * algorithm @cite Wagner74 which requires <code>O(slen * tlen)</code>
  75          * time and only <code>min(slen, tlen) + 1</code> space.
  76          */
  77         EDIT_DISTANCE_LEV,
  78         /**
  79          * Restricted Damerau-Levenshtein distance (aka Optimal String
  80          * Alignment distance).
  81          *
  82          * The Restricted Damerau-Levenshtein distance is an edit distance
  83          * measured by the number of insert, delete, substitute, and transpose
  84          * operations necessary to turn @p src into @p tgt with the restriction
  85          * that no substring is edited more than once (equivalently, that no
  86          * edits overlap). @cite Boytsov11
  87          *
  88          * This implementation uses a modified version of the Wagner-Fischer
  89          * algorithm @cite Wagner74 which requires <code>O(slen * tlen)</code>
  90          * time and only <code>2 * min(slen, tlen) + 2</code> space.
  91          */
  92         EDIT_DISTANCE_RDL,
  93         /**
  94          * Damerau-Levenshtein distance.
  95          *
  96          * The Damerau-Levenshtein distance is an edit distance measured by the
  97          * number of insert, delete, substitute, and transpose operations
  98          * necessary to turn @p src into @p tgt . @cite Damerau64
  99          *
 100          * This implementation uses the Lowrance-Wagner algorithm @cite Wagner75
 101          * which takes <code>O(slen * tlen)</code> time and
 102          * <code>O(slen * tlen)</code> space.
 103          */
 104         EDIT_DISTANCE_DL,
 105 };
 106
 107 /**
 108  * edit_distance - Calculates the edit distance between two arrays.
 109  *
 110  * @param src Source array to calculate distance from.
 111  * @param slen Number of elements in @p src to consider.
 112  * @param tgt Target array to calculate distance to.
 113  * @param tlen Number of elements in @p tgt to consider.
 114  * @param measure Edit distance measure to calculate.
 115  * @return Edit distance from @p src[0..slen-1] to @p tgt[0..tlen-1].  (i.e.
 116  * The minimal sum of the weights of the operations necessary to convert
 117  * @p src[0..slen-1] into @p tgt[0..tlen-1].)
 118  *
 119  * @code
 120  * Example:
 121  * const char *source = "kitten";
 122  * const char *target = "sitting";
 123  * assert(edit_distance(source, strlen(source),
 124  *                      target, strlen(target),
 125  *                      EDIT_DISTANCE_DL) == 3);
 126  * Example_End: @endcode
 127  */
 128 ed_dist edit_distance(const ed_elem *src, ed_size slen,
 129                       const ed_elem *tgt, ed_size tlen,
 130                       enum ed_measure measure);
 131 #endif