/src/aspell/modules/speller/default/leditdist.cpp

Source

#include "leditdist.hpp"

// The basic algorithm is as follows:
//
// Let A[n] represent the nth character of string n
//     A[n..] represent the substring of A starting at n
//            if n > length of A then it is considered an empty string
//
// edit_distance(A,B,limit) = ed(A,B,0)
//   where ed(A,B,d) = d                              if A & B is empty.
//                   = infinity                       if d > limit
//                   = ed(A[2..],B[2..], d)           if A[1] == B[1] 
//                   = min ( ed(A[2..],B[2..], d+1),  
//                           ed(A,     B[2..], d+1),
//                           ed(A[2..],B,      d+1) ) otherwise
//
// However, the code below:
// 1) Also allows for swaps
// 2) Allow weights to be attached to each edit
// 3) Is not recursive, it uses a loop when it is tail recursion
//    and a small stack otherwise.  The stack will NEVER be larger
//    then 2 * limit.
// 4) Is extremely optimized


#define check_rest(a,b,s)   \
  a0 = a; b0 = b;           \
  while (*a0 == *b0) {      \
    if (*a0 == '\0') {      \
      if (s < min) min = s; \
      break;                \
    }                       \
    ++a0; ++b0;             \
  }

namespace aspeller {

  int limit_edit_distance(const char * a, const char * b, 
        int limit, const EditDistanceWeights & w)
  {
    limit = limit*w.max;
    static const int size = 10;
    struct Edit {
      const char * a;
      const char * b;
      int score;
    };
    Edit begin[size];
    Edit * i = begin;
    const char * a0;
    const char * b0;
    int score = 0;
    int min = LARGE_NUM;
    
    while (true) {
      
      while (*a == *b) {
  if (*a == '\0') { 
    if (score < min) min = score;
    goto FINISH;
  } 
  ++a; ++b;
      }

      if (*a == '\0') {

  do {
    score += w.del2;
    if (score >= min) goto FINISH;
    ++b;
  } while (*b != '\0');
  min = score;
  
      } else if (*b == '\0') {
  
  do {
    score += w.del1;
    if (score >= min) goto FINISH;
    ++a;
  } while (*a != '\0');
  min = score;
  
      } else {

  if (score + w.max <= limit) {
    if (limit*w.min <= w.max*(w.min+score)) {
      // if floor(score/max)=limit/max-1 then this edit is only good
      // if it makes the rest of the string match.  So check if
      // the rest of the string matches to avoid the overhead of
      // pushing it on then off the stack
      
      // delete a character from a
      check_rest(a+1,b,score + w.del1);
      
      // delete a character from b
      check_rest(a,b+1,score + w.del2);
      
      if (*a == *(b+1) && *b == *(a+1)) {

        // swap two characters
        check_rest(a+2,b+2, score + w.swap);

      } else {

        // substitute one character for another which is the same
        // thing as deleting a character from both a & b
        check_rest(a+1,b+1, score + w.sub);
      
      }
    
    } else {
    
      // delete a character from a
      i->a = a + 1;
      i->b = b;
      i->score = score + w.del1;
      ++i;
    
      // delete a character from b
      i->a = a;
      i->b = b + 1;
      i->score = score + w.del2;
      ++i;
      
      // If two characters can be swapped and make a match 
      // then the substitution is pointless.
      // Also, there is no need to push this on the stack as
      // it is going to be imminently removed.
      if (*a == *(b+1) && *b == *(a+1)) {
        
        // swap two characters
        a = a + 2;
        b = b + 2;
        score += w.swap;
        continue;
        
      } else {
        
        // substitute one character for another which is the same
        // thing as deleting a character from both a & b
        a = a + 1;
        b = b + 1;
        score += w.sub;
        continue;
      
      }
    }
  }
      }
    FINISH:
      if (i == begin) return min;
      --i;
      a = i->a;
      b = i->b;
      score = i->score;
    }
  }

#undef check_rest
#define check_rest(a,b,w)               \
          a0 = a; b0 = b;               \
          while(*a0 == *b0) {           \
      if (*a0 == '\0') {          \
        if (w < min) min = w;     \
        break;                    \
      }                           \
      ++a0;                       \
      ++b0;                       \
          }                             \
          if (amax < a0) amax = a0;

#define check2(a,b,w)                                             \
  aa = a; bb = b;                                                 \
  while(*aa == *bb) {                                             \
    if (*aa == '\0')  {                                           \
      if (amax < aa) amax = aa;                                   \
      if (w < min) min = w;                                       \
      break;                                                      \
    }                                                             \
    ++aa; ++bb;                                                   \
  }                                                               \
  if (*aa == '\0') {                                              \
    if (amax < aa) amax = aa;                                     \
    if (*bb == '\0') {}                                           \
    else if (*(bb+1) == '\0' && w+ws.del2 < min) min = w+ws.del2; \
  } else if (*bb == '\0') {                                       \
    ++aa;                                                         \
    if (amax < aa) amax = aa;                                     \
    if (*aa == '\0' && w+ws.del1 < min) min = w+ws.del1;          \
  } else {                                                        \
    check_rest(aa+1,bb,w+ws.del1);                                \
    check_rest(aa,bb+1,w+ws.del2);                                \
    if (*aa == *(bb+1) && *bb == *(aa+1)) {                       \
      check_rest(aa+2,bb+2,w+ws.swap);                            \
    } else {                                                      \
      check_rest(aa+1,bb+1,w+ws.sub);                             \
    }                                                             \
  }

  EditDist limit0_edit_distance(const char * a, const char * b,
        const EditDistanceWeights & ws)
  {
    while(*a == *b) {
      if (*a == '\0')
  return EditDist(0, a);
      ++a; ++b;
    }

    return EditDist(LARGE_NUM, a);
  }

  EditDist limit1_edit_distance(const char * a, const char * b,
        const EditDistanceWeights & ws)
  {
    int min = LARGE_NUM;
    const char * a0;
    const char * b0;
    const char * amax = a;
    
    while(*a == *b) { 
      if (*a == '\0') 
  return EditDist(0, a);
      ++a; ++b;
    }

    if (*a == '\0') {
      
      ++b;
      if (*b == '\0') return EditDist(ws.del2, a);
      return EditDist(LARGE_NUM, a);
      
    } else if (*b == '\0') {

      ++a;
      if (*a == '\0') return EditDist(ws.del1, a);
      return EditDist(LARGE_NUM, a);
      
    } else {
      
      // delete a character from a
      check_rest(a+1,b,ws.del1);
      
      // delete a character from b
      check_rest(a,b+1,ws.del2);

      if (*a == *(b+1) && *b == *(a+1)) {
  
  // swap two characters
  check_rest(a+2,b+2,ws.swap);

      } else {
  
  // substitute one character for another which is the same
  // thing as deleting a character from both a & b
  check_rest(a+1,b+1,ws.sub);
  
      }
    }
    return EditDist(min, amax);
  }

  EditDist limit2_edit_distance(const char * a, const char * b,
        const EditDistanceWeights & ws)
  {
    int min = LARGE_NUM;
    const char * a0;
    const char * b0;
    const char * aa;
    const char * bb;
    const char * amax = a;
    
    while(*a == *b) { 
      if (*a == '\0') 
  return EditDist(0, a);
      ++a; ++b;
    }

    if (*a == '\0') {
      
      ++b;
      if (*b == '\0') return EditDist(ws.del2, a);
      ++b;
      if (*b == '\0') return EditDist(2*ws.del2, a);
      return EditDist(LARGE_NUM, a);
      
    } else if (*b == '\0') {

      ++a;
      if (*a == '\0') return EditDist(ws.del1, a);
      ++a;
      if (*a == '\0') return EditDist(2*ws.del1, a);
      return EditDist(LARGE_NUM, a);
      
    } else {
      
      // delete a character from a
      check2(a+1,b,ws.del1);
      
      // delete a character from b
      check2(a,b+1,ws.del2);

      if (*a == *(b+1) && *b == *(a+1)) {
  
  // swap two characters
  check2(a+2,b+2,ws.swap);

      } else {
  
  // substitute one character for another which is the same
  // thing as deleting a character from both a & b
  check2(a+1,b+1,ws.sub);
  
      }
    }
    return EditDist(min, amax);
  }
}



Coverage Report

Created: 2026-10-17 06:41

Line	Count	Source
1
2		#include "leditdist.hpp"
3
4		// The basic algorithm is as follows:
5		//
6		// Let A[n] represent the nth character of string n
7		// A[n..] represent the substring of A starting at n
8		// if n > length of A then it is considered an empty string
9		//
10		// edit_distance(A,B,limit) = ed(A,B,0)
11		// where ed(A,B,d) = d if A & B is empty.
12		// = infinity if d > limit
13		// = ed(A[2..],B[2..], d) if A[1] == B[1]
14		// = min ( ed(A[2..],B[2..], d+1),
15		// ed(A, B[2..], d+1),
16		// ed(A[2..],B, d+1) ) otherwise
17		//
18		// However, the code below:
19		// 1) Also allows for swaps
20		// 2) Allow weights to be attached to each edit
21		// 3) Is not recursive, it uses a loop when it is tail recursion
22		// and a small stack otherwise. The stack will NEVER be larger
23		// then 2 * limit.
24		// 4) Is extremely optimized
25
26
27		#define check_rest(a,b,s) \
28	178M	a0 = a; b0 = b; \
29	190M	while (a0 == b0) { \
30	12.9M	if (*a0 == '\0') { \
31	950k	if (s < min) min = s; \
32	950k	break; \
33	950k	} \
34	12.9M	++a0; ++b0; \
35	12.0M	}
36
37		namespace aspeller {
38
39		int limit_edit_distance(const char * a, const char * b,
40		int limit, const EditDistanceWeights & w)
41	5.97M	{
42	5.97M	limit = limit*w.max;
43	5.97M	static const int size = 10;
44	5.97M	struct Edit {
45	5.97M	const char * a;
46	5.97M	const char * b;
47	5.97M	int score;
48	5.97M	};
49	5.97M	Edit begin[size];
50	5.97M	Edit * i = begin;
51	5.97M	const char * a0;
52	5.97M	const char * b0;
53	5.97M	int score = 0;
54	5.97M	int min = LARGE_NUM;
55
56	96.2M	while (true) {
57
58	103M	while (a == b) {
59	7.57M	if (*a == '\0') {
60	104k	if (score < min) min = score;
61	104k	goto FINISH;
62	104k	}
63	7.46M	++a; ++b;
64	7.46M	}
65
66	96.1M	if (*a == '\0') {
67
68	16.8M	do {
69	16.8M	score += w.del2;
70	16.8M	if (score >= min) goto FINISH;
71	15.0M	++b;
72	15.0M	} while (*b != '\0');
73	1.97M	min = score;
74
75	92.3M	} else if (*b == '\0') {
76
77	38.7M	do {
78	38.7M	score += w.del1;
79	38.7M	if (score >= min) goto FINISH;
80	36.5M	++a;
81	36.5M	} while (*a != '\0');
82	679k	min = score;
83
84	89.4M	} else {
85
86	89.4M	if (score + w.max <= limit) {
87	89.4M	if (limitw.min <= w.max(w.min+score)) {
88		// if floor(score/max)=limit/max-1 then this edit is only good
89		// if it makes the rest of the string match. So check if
90		// the rest of the string matches to avoid the overhead of
91		// pushing it on then off the stack
92
93		// delete a character from a
94	59.3M	check_rest(a+1,b,score + w.del1);
95
96		// delete a character from b
97	59.3M	check_rest(a,b+1,score + w.del2);
98
99	59.3M	if (a == (b+1) && b == (a+1)) {
100
101		// swap two characters
102	287k	check_rest(a+2,b+2, score + w.swap);
103
104	59.0M	} else {
105
106		// substitute one character for another which is the same
107		// thing as deleting a character from both a & b
108	59.0M	check_rest(a+1,b+1, score + w.sub);
109
110	59.0M	}
111
112	59.3M	} else {
113
114		// delete a character from a
115	30.0M	i->a = a + 1;
116	30.0M	i->b = b;
117	30.0M	i->score = score + w.del1;
118	30.0M	++i;
119
120		// delete a character from b
121	30.0M	i->a = a;
122	30.0M	i->b = b + 1;
123	30.0M	i->score = score + w.del2;
124	30.0M	++i;
125
126		// If two characters can be swapped and make a match
127		// then the substitution is pointless.
128		// Also, there is no need to push this on the stack as
129		// it is going to be imminently removed.
130	30.0M	if (a == (b+1) && b == (a+1)) {
131
132		// swap two characters
133	148k	a = a + 2;
134	148k	b = b + 2;
135	148k	score += w.swap;
136	148k	continue;
137
138	29.9M	} else {
139
140		// substitute one character for another which is the same
141		// thing as deleting a character from both a & b
142	29.9M	a = a + 1;
143	29.9M	b = b + 1;
144	29.9M	score += w.sub;
145	29.9M	continue;
146
147	29.9M	}
148	30.0M	}
149	89.4M	}
150	89.4M	}
151	66.1M	FINISH:
152	66.1M	if (i == begin) return min;
153	60.1M	--i;
154	60.1M	a = i->a;
155	60.1M	b = i->b;
156	60.1M	score = i->score;
157	60.1M	}
158	5.97M	}
159
160		#undef check_rest
161		#define check_rest(a,b,w) \
162	240M	a0 = a; b0 = b; \
163	283M	while(a0 == b0) { \
164	44.3M	if (*a0 == '\0') { \
165	2.20M	if (w < min) min = w; \
166	2.20M	break; \
167	2.20M	} \
168	44.3M	++a0; \
169	42.1M	++b0; \
170	42.1M	} \
171	240M	if (amax < a0) amax = a0;
172
173		#define check2(a,b,w) \
174	74.6M	aa = a; bb = b; \
175	85.8M	while(aa == bb) { \
176	11.3M	if (*aa == '\0') { \
177	106k	if (amax < aa) amax = aa; \
178	106k	if (w < min) min = w; \
179	106k	break; \
180	106k	} \
181	11.3M	++aa; ++bb; \
182	11.2M	} \
183	74.6M	if (*aa == '\0') { \
184	2.76M	if (amax < aa) amax = aa; \
185	2.76M	if (*bb == '\0') {} \
186	2.76M	else if (*(bb+1) == '\0' && w+ws.del2 < min) min = w+ws.del2; \
187	71.8M	} else if (*bb == '\0') { \
188	487k	++aa; \
189	487k	if (amax < aa) amax = aa; \
190	487k	if (*aa == '\0' && w+ws.del1 < min) min = w+ws.del1; \
191	71.3M	} else { \
192	71.3M	check_rest(aa+1,bb,w+ws.del1); \
193	71.3M	check_rest(aa,bb+1,w+ws.del2); \
194	71.3M	if (aa == (bb+1) && bb == (aa+1)) { \
195	695k	check_rest(aa+2,bb+2,w+ws.swap); \
196	70.6M	} else { \
197	70.6M	check_rest(aa+1,bb+1,w+ws.sub); \
198	70.6M	} \
199	71.3M	}
200
201		EditDist limit0_edit_distance(const char * a, const char * b,
202		const EditDistanceWeights & ws)
203	624k	{
204	742k	while(a == b) {
205	153k	if (*a == '\0')
206	35.2k	return EditDist(0, a);
207	117k	++a; ++b;
208	117k	}
209
210	589k	return EditDist(LARGE_NUM, a);
211	624k	}
212
213		EditDist limit1_edit_distance(const char * a, const char * b,
214		const EditDistanceWeights & ws)
215	11.2M	{
216	11.2M	int min = LARGE_NUM;
217	11.2M	const char * a0;
218	11.2M	const char * b0;
219	11.2M	const char * amax = a;
220
221	16.3M	while(a == b) {
222	5.09M	if (*a == '\0')
223	22.8k	return EditDist(0, a);
224	5.07M	++a; ++b;
225	5.07M	}
226
227	11.2M	if (*a == '\0') {
228
229	36.2k	++b;
230	36.2k	if (*b == '\0') return EditDist(ws.del2, a);
231	16.3k	return EditDist(LARGE_NUM, a);
232
233	11.1M	} else if (*b == '\0') {
234
235	2.24M	++a;
236	2.24M	if (*a == '\0') return EditDist(ws.del1, a);
237	1.58M	return EditDist(LARGE_NUM, a);
238
239	8.93M	} else {
240
241		// delete a character from a
242	8.93M	check_rest(a+1,b,ws.del1);
243
244		// delete a character from b
245	8.93M	check_rest(a,b+1,ws.del2);
246
247	8.93M	if (a == (b+1) && b == (a+1)) {
248
249		// swap two characters
250	129k	check_rest(a+2,b+2,ws.swap);
251
252	8.80M	} else {
253
254		// substitute one character for another which is the same
255		// thing as deleting a character from both a & b
256	8.80M	check_rest(a+1,b+1,ws.sub);
257
258	8.80M	}
259	8.93M	}
260	8.93M	return EditDist(min, amax);
261	11.2M	}
262
263		EditDist limit2_edit_distance(const char * a, const char * b,
264		const EditDistanceWeights & ws)
265	26.6M	{
266	26.6M	int min = LARGE_NUM;
267	26.6M	const char * a0;
268	26.6M	const char * b0;
269	26.6M	const char * aa;
270	26.6M	const char * bb;
271	26.6M	const char * amax = a;
272
273	33.6M	while(a == b) {
274	7.03M	if (*a == '\0')
275	81	return EditDist(0, a);
276	7.03M	++a; ++b;
277	7.03M	}
278
279	26.6M	if (*a == '\0') {
280
281	1.63M	++b;
282	1.63M	if (*b == '\0') return EditDist(ws.del2, a);
283	1.51M	++b;
284	1.51M	if (b == '\0') return EditDist(2ws.del2, a);
285	1.08M	return EditDist(LARGE_NUM, a);
286
287	25.0M	} else if (*b == '\0') {
288
289	122k	++a;
290	122k	if (*a == '\0') return EditDist(ws.del1, a);
291	118k	++a;
292	118k	if (a == '\0') return EditDist(2ws.del1, a);
293	82.9k	return EditDist(LARGE_NUM, a);
294
295	24.8M	} else {
296
297		// delete a character from a
298	24.8M	check2(a+1,b,ws.del1);
299
300		// delete a character from b
301	24.8M	check2(a,b+1,ws.del2);
302
303	24.8M	if (a == (b+1) && b == (a+1)) {
304
305		// swap two characters
306	168k	check2(a+2,b+2,ws.swap);
307
308	24.7M	} else {
309
310		// substitute one character for another which is the same
311		// thing as deleting a character from both a & b
312	24.7M	check2(a+1,b+1,ws.sub);
313
314	24.7M	}
315	24.8M	}
316	24.8M	return EditDist(min, amax);
317	26.6M	}
318		}
319
320