xapian-core
1.4.27
|
Edit distance calculation algorithm. More...
#include <config.h>
#include "editdistance.h"
#include "omassert.h"
#include <algorithm>
#include <cstdlib>
Go to the source code of this file.
Classes | |
struct | edist_seq< CHR > |
class | edist_state< CHR > |
Macros | |
#define | INF 1000000 |
Functions | |
template<class CHR > | |
static int | seqcmp_editdist (const CHR *ptr1, int len1, const CHR *ptr2, int len2, int max_distance) |
int | edit_distance_unsigned (const unsigned *ptr1, int len1, const unsigned *ptr2, int len2, int max_distance) |
Calculate the edit distance between two sequences. More... | |
Edit distance calculation algorithm.
Based on that described in:
"An extension of Ukkonen's enhanced dynamic programming ASM algorithm" by Hal Berghel, University of Arkansas and David Roach, Acxiom Corporation
http://berghel.net/publications/asm/asm.php
Definition in file editdistance.cc.
#define INF 1000000 |
Definition at line 137 of file editdistance.cc.
Referenced by edist_state< CHR >::edist_state().
int edit_distance_unsigned | ( | const unsigned * | ptr1, |
int | len1, | ||
const unsigned * | ptr2, | ||
int | len2, | ||
int | max_distance | ||
) |
Calculate the edit distance between two sequences.
Edit distance is defined as the minimum number of edit operations required to move from one sequence to another. The edit operations considered are:
ptr1 | A pointer to the start of the first sequence. |
len1 | The length of the first sequence. |
ptr2 | A pointer to the start of the second sequence. |
len2 | The length of the first sequence. |
max_distance | The greatest edit distance that's interesting to us. If the true edit distance is > max_distance, any value > max_distance may be returned instead (which allows the edit distance algorithm to avoid work for poor matches). |
Definition at line 206 of file editdistance.cc.
Referenced by Xapian::Database::get_spelling_suggestion().
|
static |
Definition at line 169 of file editdistance.cc.
References edist_state< CHR >::edist_calc_f_kp(), and edist_state< CHR >::get_f_kp().