43 edist_seq(
const CHR * ptr_,
int len_) : ptr(ptr_), len(len_) { }
72 return (k + maxdist) * fkp_cols + p + 1;
77 edist_state(
const CHR * ptr1,
int len1,
const CHR * ptr2,
int len2);
82 return fkp[calc_index(k, p)];
86 fkp[calc_index(k, p)] = val;
90 if (pos1 <= 0 || pos2 <= 0 || pos1 >= seq1.
len || pos2 >= seq2.
len)
return false;
91 return (seq1.
ptr[pos1 - 1] == seq2.
ptr[pos2] &&
92 seq1.
ptr[pos1] == seq2.
ptr[pos2 - 1]);
95 void edist_calc_f_kp(
int k,
int p);
101 int maxlen = get_f_kp(k, p - 1) + 1;
102 int maxlen2 = get_f_kp(k - 1, p - 1);
103 int maxlen3 = get_f_kp(k + 1, p - 1) + 1;
105 if (is_transposed(maxlen, maxlen + k)) {
110 if (maxlen >= maxlen2) {
111 if (maxlen >= maxlen3) {
118 if (maxlen2 >= maxlen3) {
129 while (maxlen < seq1.len &&
130 maxlen + k < seq2.len &&
131 seq1.ptr[maxlen] == seq2.ptr[maxlen + k]) {
134 set_f_kp(k, p, maxlen);
140 const CHR * ptr2,
int len2)
141 : seq1(ptr1, len1), seq2(ptr2, len2), maxdist(len2)
145 int fkp_rows =
maxdist * 2 + 1;
152 for (
int k = 1; k <=
maxdist; ++k) {
153 for (
int p = -1; p < k - 1; ++p) {
172 int lendiff = len2 - len1;
181 if (len1 == 0)
return len2;
186 while (p <= max_distance) {
187 for (
int temp_p = 0; temp_p != p; ++temp_p) {
188 int inc = p - temp_p;
189 if (abs(lendiff - inc) <= temp_p) {
192 if (abs(lendiff + inc) <= temp_p) {
198 if (state.
get_f_kp(lendiff, p) == len1)
break;
207 const unsigned * ptr2,
int len2,
210 return seqcmp_editdist<unsigned>(ptr1, len1, ptr2, len2, max_distance);
int calc_index(int k, int p) const
bool is_transposed(int pos1, int pos2) const
Edit distance calculation algorithm.
static int seqcmp_editdist(const CHR *ptr1, int len1, const CHR *ptr2, int len2, int max_distance)
int get_f_kp(int k, int p) const
void edist_calc_f_kp(int k, int p)
void set_f_kp(int k, int p, int val)
edist_state(const edist_state &)
Don't allow copying.
edist_seq(const CHR *ptr_, int len_)
Various assertion macros.
int edit_distance_unsigned(const unsigned *ptr1, int len1, const unsigned *ptr2, int len2, int max_distance)
Calculate the edit distance between two sequences.