xapian-core/api/editdistance.h

   1 /** @file editdistance.h
   2  * @brief Edit distance calculation algorithm.
   3  */
   4 /* Copyright (C) 2003 Richard Boulton
   5  * Copyright (C) 2007,2008 Olly Betts
   6  *
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  20  */
  21
  22 #ifndef XAPIAN_INCLUDED_EDITDISTANCE_H
  23 #define XAPIAN_INCLUDED_EDITDISTANCE_H
  24
  25 /** Calculate the edit distance between two sequences.
  26  *
  27  *  Edit distance is defined as the minimum number of edit operations
  28  *  required to move from one sequence to another.  The edit operations
  29  *  considered are:
  30  *   - Insertion of a character at an arbitrary position.
  31  *   - Deletion of a character at an arbitrary position.
  32  *   - Substitution of a character at an arbitrary position.
  33  *   - Transposition of two neighbouring characters at an arbitrary position
  34  *     in the string.
  35  *
  36  *  @param ptr1 A pointer to the start of the first sequence.
  37  *  @param len1 The length of the first sequence.
  38  *  @param ptr2 A pointer to the start of the second sequence.
  39  *  @param len2 The length of the first sequence.
  40  *  @param max_distance The greatest edit distance that's interesting to us.
  41  *                      If the true edit distance is > max_distance, any
  42  *                      value > max_distance may be returned instead (which
  43  *                      allows the edit distance algorithm to avoid work for
  44  *                      poor matces).
  45  *
  46  *  @return The edit distance from one item to the other.
  47  */
  48 int edit_distance_unsigned(const unsigned* ptr1, int len1,
  49                            const unsigned* ptr2, int len2,
  50                            int max_distance);
  51
  52 #endif // XAPIAN_INCLUDED_EDITDISTANCE_H