« back to all changes in this revision
Viewing changes to src/hunspell/suggestmgr.cxx
- browse files at revision 4
- compare with another revision
- download diff
- download tarball
- view history from revision 4
- Committer: Bazaar Package Importer
- Author(s): Craig Small
- Date: 2011-05-14 20:12:49 UTC
- mfrom: (1.1.2 upstream)
- Revision ID: james.westby@ubuntu.com-20110514201249-184gqx5jjqam02lg
Tags: 2.0-rc5-1
New upstream release
- files removed:
- .pc/about_ui_version
- .pc/about_ui_version/src
- .pc/about_ui_version/src/ui
- .pc/hunspell_dict
- .pc/hunspell_dict/src
- src/hunspell
- src/hunspell/.deps
- src/hunspell/.libs
- src/hunspell/.libs/libhunspell-1.2.la
- src/hunspell/.libs/libhunspell-1.2.so
- src/hunspell/.libs/libhunspell-1.2.so.0
- files modified:
- .pc/applied-patches
added
removed
src/hunspell/suggestmgr.cxx
1
#include "license.hunspell"
2
#include "license.myspell"
3
4
#include <stdlib.h>
5
#include <string.h>
6
#include <stdio.h>
7
#include <ctype.h>
8
9
#include "suggestmgr.hxx"
10
#include "htypes.hxx"
11
#include "csutil.hxx"
12
13
const w_char W_VLINE = { '\0', '|' };
14
15
SuggestMgr::SuggestMgr(const char * tryme, int maxn,
16
AffixMgr * aptr)
17
{
18
19
// register affix manager and check in string of chars to
20
// try when building candidate suggestions
21
pAMgr = aptr;
22
23
csconv = NULL;
24
25
ckeyl = 0;
26
ckey = NULL;
27
ckey_utf = NULL;
28
29
ctryl = 0;
30
ctry = NULL;
31
ctry_utf = NULL;
32
33
utf8 = 0;
34
langnum = 0;
35
complexprefixes = 0;
36
37
maxSug = maxn;
38
nosplitsugs = 0;
39
maxngramsugs = MAXNGRAMSUGS;
40
41
if (pAMgr) {
42
char * enc = pAMgr->get_encoding();
43
csconv = get_current_cs(enc);
44
free(enc);
45
langnum = pAMgr->get_langnum();
46
ckey = pAMgr->get_key_string();
47
nosplitsugs = pAMgr->get_nosplitsugs();
48
if (pAMgr->get_maxngramsugs() >= 0) maxngramsugs = pAMgr->get_maxngramsugs();
49
utf8 = pAMgr->get_utf8();
50
complexprefixes = pAMgr->get_complexprefixes();
51
}
52
53
if (ckey) {
54
if (utf8) {
55
w_char t[MAXSWL];
56
ckeyl = u8_u16(t, MAXSWL, ckey);
57
ckey_utf = (w_char *) malloc(ckeyl * sizeof(w_char));
58
if (ckey_utf) memcpy(ckey_utf, t, ckeyl * sizeof(w_char));
59
else ckeyl = 0;
60
} else {
61
ckeyl = strlen(ckey);
62
}
63
}
64
65
if (tryme) {
66
ctry = mystrdup(tryme);
67
if (ctry) ctryl = strlen(ctry);
68
if (ctry && utf8) {
69
w_char t[MAXSWL];
70
ctryl = u8_u16(t, MAXSWL, tryme);
71
ctry_utf = (w_char *) malloc(ctryl * sizeof(w_char));
72
if (ctry_utf) memcpy(ctry_utf, t, ctryl * sizeof(w_char));
73
else ctryl = 0;
74
}
75
}
76
}
77
78
79
SuggestMgr::~SuggestMgr()
80
{
81
pAMgr = NULL;
82
if (ckey) free(ckey);
83
ckey = NULL;
84
if (ckey_utf) free(ckey_utf);
85
ckey_utf = NULL;
86
ckeyl = 0;
87
if (ctry) free(ctry);
88
ctry = NULL;
89
if (ctry_utf) free(ctry_utf);
90
ctry_utf = NULL;
91
ctryl = 0;
92
maxSug = 0;
93
#ifdef MOZILLA_CLIENT
94
delete [] csconv;
95
#endif
96
}
97
98
int SuggestMgr::testsug(char** wlst, const char * candidate, int wl, int ns, int cpdsuggest,
99
int * timer, clock_t * timelimit) {
100
int cwrd = 1;
101
if (ns == maxSug) return maxSug;
102
for (int k=0; k < ns; k++) {
103
if (strcmp(candidate,wlst[k]) == 0) cwrd = 0;
104
}
105
if ((cwrd) && checkword(candidate, wl, cpdsuggest, timer, timelimit)) {
106
wlst[ns] = mystrdup(candidate);
107
if (wlst[ns] == NULL) {
108
for (int j=0; j<ns; j++) free(wlst[j]);
109
return -1;
110
}
111
ns++;
112
}
113
return ns;
114
}
115
116
// generate suggestions for a misspelled word
117
// pass in address of array of char * pointers
118
// onlycompoundsug: probably bad suggestions (need for ngram sugs, too)
119
120
int SuggestMgr::suggest(char*** slst, const char * w, int nsug,
121
int * onlycompoundsug)
122
{
123
int nocompoundtwowords = 0;
124
char ** wlst;
125
w_char word_utf[MAXSWL];
126
int wl = 0;
127
128
char w2[MAXWORDUTF8LEN];
129
const char * word = w;
130
131
// word reversing wrapper for complex prefixes
132
if (complexprefixes) {
133
strcpy(w2, w);
134
if (utf8) reverseword_utf(w2); else reverseword(w2);
135
word = w2;
136
}
137
138
if (*slst) {
139
wlst = *slst;
140
} else {
141
wlst = (char **) malloc(maxSug * sizeof(char *));
142
if (wlst == NULL) return -1;
143
for (int i = 0; i < maxSug; i++) {
144
wlst[i] = NULL;
145
}
146
}
147
148
if (utf8) {
149
wl = u8_u16(word_utf, MAXSWL, word);
150
}
151
152
for (int cpdsuggest=0; (cpdsuggest<2) && (nocompoundtwowords==0); cpdsuggest++) {
153
154
// suggestions for an uppercase word (html -> HTML)
155
if ((nsug < maxSug) && (nsug > -1)) {
156
nsug = (utf8) ? capchars_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
157
capchars(wlst, word, nsug, cpdsuggest);
158
}
159
160
// perhaps we made a typical fault of spelling
161
if ((nsug < maxSug) && (nsug > -1))
162
nsug = replchars(wlst, word, nsug, cpdsuggest);
163
164
// perhaps we made chose the wrong char from a related set
165
if ((nsug < maxSug) && (nsug > -1)) {
166
nsug = mapchars(wlst, word, nsug, cpdsuggest);
167
}
168
169
// did we swap the order of chars by mistake
170
if ((nsug < maxSug) && (nsug > -1)) {
171
nsug = (utf8) ? swapchar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
172
swapchar(wlst, word, nsug, cpdsuggest);
173
}
174
175
// did we swap the order of non adjacent chars by mistake
176
if ((nsug < maxSug) && (nsug > -1)) {
177
nsug = (utf8) ? longswapchar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
178
longswapchar(wlst, word, nsug, cpdsuggest);
179
}
180
181
// did we just hit the wrong key in place of a good char (case and keyboard)
182
if ((nsug < maxSug) && (nsug > -1)) {
183
nsug = (utf8) ? badcharkey_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
184
badcharkey(wlst, word, nsug, cpdsuggest);
185
}
186
187
// only suggest compound words when no other suggestion
188
if ((cpdsuggest == 0) && (nsug > 0)) nocompoundtwowords=1;
189
190
// did we add a char that should not be there
191
if ((nsug < maxSug) && (nsug > -1)) {
192
nsug = (utf8) ? extrachar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
193
extrachar(wlst, word, nsug, cpdsuggest);
194
}
195
196
197
// did we forgot a char
198
if ((nsug < maxSug) && (nsug > -1)) {
199
nsug = (utf8) ? forgotchar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
200
forgotchar(wlst, word, nsug, cpdsuggest);
201
}
202
203
// did we move a char
204
if ((nsug < maxSug) && (nsug > -1)) {
205
nsug = (utf8) ? movechar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
206
movechar(wlst, word, nsug, cpdsuggest);
207
}
208
209
// did we just hit the wrong key in place of a good char
210
if ((nsug < maxSug) && (nsug > -1)) {
211
nsug = (utf8) ? badchar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
212
badchar(wlst, word, nsug, cpdsuggest);
213
}
214
215
// did we double two characters
216
if ((nsug < maxSug) && (nsug > -1)) {
217
nsug = (utf8) ? doubletwochars_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
218
doubletwochars(wlst, word, nsug, cpdsuggest);
219
}
220
221
// perhaps we forgot to hit space and two words ran together
222
if ((!nosplitsugs) && (nsug < maxSug) && (nsug > -1)) {
223
nsug = twowords(wlst, word, nsug, cpdsuggest);
224
}
225
226
} // repeating ``for'' statement compounding support
227
228
if (nsug < 0) {
229
// we ran out of memory - we should free up as much as possible
230
for (int i = 0; i < maxSug; i++)
231
if (wlst[i] != NULL) free(wlst[i]);
232
free(wlst);
233
wlst = NULL;
234
}
235
236
if (!nocompoundtwowords && (nsug > 0) && onlycompoundsug) *onlycompoundsug = 1;
237
238
*slst = wlst;
239
return nsug;
240
}
241
242
// generate suggestions for a word with typical mistake
243
// pass in address of array of char * pointers
244
#ifdef HUNSPELL_EXPERIMENTAL
245
int SuggestMgr::suggest_auto(char*** slst, const char * w, int nsug)
246
{
247
int nocompoundtwowords = 0;
248
char ** wlst;
249
250
char w2[MAXWORDUTF8LEN];
251
const char * word = w;
252
253
// word reversing wrapper for complex prefixes
254
if (complexprefixes) {
255
strcpy(w2, w);
256
if (utf8) reverseword_utf(w2); else reverseword(w2);
257
word = w2;
258
}
259
260
if (*slst) {
261
wlst = *slst;
262
} else {
263
wlst = (char **) malloc(maxSug * sizeof(char *));
264
if (wlst == NULL) return -1;
265
}
266
267
for (int cpdsuggest=0; (cpdsuggest<2) && (nocompoundtwowords==0); cpdsuggest++) {
268
269
// perhaps we made a typical fault of spelling
270
if ((nsug < maxSug) && (nsug > -1))
271
nsug = replchars(wlst, word, nsug, cpdsuggest);
272
273
// perhaps we made chose the wrong char from a related set
274
if ((nsug < maxSug) && (nsug > -1))
275
nsug = mapchars(wlst, word, nsug, cpdsuggest);
276
277
if ((cpdsuggest==0) && (nsug>0)) nocompoundtwowords=1;
278
279
// perhaps we forgot to hit space and two words ran together
280
281
if ((nsug < maxSug) && (nsug > -1) && check_forbidden(word, strlen(word))) {
282
nsug = twowords(wlst, word, nsug, cpdsuggest);
283
}
284
285
} // repeating ``for'' statement compounding support
286
287
if (nsug < 0) {
288
for (int i=0;i<maxSug; i++)
289
if (wlst[i] != NULL) free(wlst[i]);
290
free(wlst);
291
return -1;
292
}
293
294
*slst = wlst;
295
return nsug;
296
}
297
#endif // END OF HUNSPELL_EXPERIMENTAL CODE
298
299
// suggestions for an uppercase word (html -> HTML)
300
int SuggestMgr::capchars_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
301
{
302
char candidate[MAXSWUTF8L];
303
w_char candidate_utf[MAXSWL];
304
memcpy(candidate_utf, word, wl * sizeof(w_char));
305
mkallcap_utf(candidate_utf, wl, langnum);
306
u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
307
return testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
308
}
309
310
// suggestions for an uppercase word (html -> HTML)
311
int SuggestMgr::capchars(char** wlst, const char * word, int ns, int cpdsuggest)
312
{
313
char candidate[MAXSWUTF8L];
314
strcpy(candidate, word);
315
mkallcap(candidate, csconv);
316
return testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
317
}
318
319
// suggestions for when chose the wrong char out of a related set
320
int SuggestMgr::mapchars(char** wlst, const char * word, int ns, int cpdsuggest)
321
{
322
char candidate[MAXSWUTF8L];
323
clock_t timelimit;
324
int timer;
325
candidate[0] = '\0';
326
327
int wl = strlen(word);
328
if (wl < 2 || ! pAMgr) return ns;
329
330
int nummap = pAMgr->get_nummap();
331
struct mapentry* maptable = pAMgr->get_maptable();
332
if (maptable==NULL) return ns;
333
334
timelimit = clock();
335
timer = MINTIMER;
336
return map_related(word, (char *) &candidate, 0, 0, wlst, cpdsuggest, ns, maptable, nummap, &timer, &timelimit);
337
}
338
339
int SuggestMgr::map_related(const char * word, char * candidate, int wn, int cn,
340
char** wlst, int cpdsuggest, int ns,
341
const mapentry* maptable, int nummap, int * timer, clock_t * timelimit)
342
{
343
if (*(word + wn) == '\0') {
344
int cwrd = 1;
345
*(candidate + cn) = '\0';
346
int wl = strlen(candidate);
347
for (int m=0; m < ns; m++)
348
if (strcmp(candidate, wlst[m]) == 0) cwrd = 0;
349
if ((cwrd) && checkword(candidate, wl, cpdsuggest, timer, timelimit)) {
350
if (ns < maxSug) {
351
wlst[ns] = mystrdup(candidate);
352
if (wlst[ns] == NULL) return -1;
353
ns++;
354
}
355
}
356
return ns;
357
}
358
int in_map = 0;
359
for (int j = 0; j < nummap; j++) {
360
for (int k = 0; k < maptable[j].len; k++) {
361
int len = strlen(maptable[j].set[k]);
362
if (strncmp(maptable[j].set[k], word + wn, len) == 0) {
363
in_map = 1;
364
for (int l = 0; l < maptable[j].len; l++) {
365
strcpy(candidate + cn, maptable[j].set[l]);
366
ns = map_related(word, candidate, wn + len, strlen(candidate), wlst,
367
cpdsuggest, ns, maptable, nummap, timer, timelimit);
368
if (!(*timer)) return ns;
369
}
370
}
371
}
372
}
373
if (!in_map) {
374
*(candidate + cn) = *(word + wn);
375
ns = map_related(word, candidate, wn + 1, cn + 1, wlst, cpdsuggest,
376
ns, maptable, nummap, timer, timelimit);
377
}
378
return ns;
379
}
380
381
// suggestions for a typical fault of spelling, that
382
// differs with more, than 1 letter from the right form.
383
int SuggestMgr::replchars(char** wlst, const char * word, int ns, int cpdsuggest)
384
{
385
char candidate[MAXSWUTF8L];
386
const char * r;
387
int lenr, lenp;
388
int wl = strlen(word);
389
if (wl < 2 || ! pAMgr) return ns;
390
int numrep = pAMgr->get_numrep();
391
struct replentry* reptable = pAMgr->get_reptable();
392
if (reptable==NULL) return ns;
393
for (int i=0; i < numrep; i++ ) {
394
r = word;
395
lenr = strlen(reptable[i].pattern2);
396
lenp = strlen(reptable[i].pattern);
397
// search every occurence of the pattern in the word
398
while ((r=strstr(r, reptable[i].pattern)) != NULL) {
399
strcpy(candidate, word);
400
if (r-word + lenr + strlen(r+lenp) >= MAXSWUTF8L) break;
401
strcpy(candidate+(r-word),reptable[i].pattern2);
402
strcpy(candidate+(r-word)+lenr, r+lenp);
403
ns = testsug(wlst, candidate, wl-lenp+lenr, ns, cpdsuggest, NULL, NULL);
404
if (ns == -1) return -1;
405
// check REP suggestions with space
406
char * sp = strchr(candidate, ' ');
407
if (sp) {
408
*sp = '\0';
409
if (checkword(candidate, strlen(candidate), 0, NULL, NULL)) {
410
int oldns = ns;
411
*sp = ' ';
412
ns = testsug(wlst, sp + 1, strlen(sp + 1), ns, cpdsuggest, NULL, NULL);
413
if (ns == -1) return -1;
414
if (oldns < ns) {
415
free(wlst[ns - 1]);
416
wlst[ns - 1] = mystrdup(candidate);
417
if (!wlst[ns - 1]) return -1;
418
}
419
}
420
*sp = ' ';
421
}
422
r++; // search for the next letter
423
}
424
}
425
return ns;
426
}
427
428
// perhaps we doubled two characters (pattern aba -> ababa, for example vacation -> vacacation)
429
int SuggestMgr::doubletwochars(char** wlst, const char * word, int ns, int cpdsuggest)
430
{
431
char candidate[MAXSWUTF8L];
432
int state=0;
433
int wl = strlen(word);
434
if (wl < 5 || ! pAMgr) return ns;
435
for (int i=2; i < wl; i++ ) {
436
if (word[i]==word[i-2]) {
437
state++;
438
if (state==3) {
439
strcpy(candidate,word);
440
strcpy(candidate+i-1,word+i+1);
441
ns = testsug(wlst, candidate, wl-2, ns, cpdsuggest, NULL, NULL);
442
if (ns == -1) return -1;
443
state=0;
444
}
445
} else {
446
state=0;
447
}
448
}
449
return ns;
450
}
451
452
// perhaps we doubled two characters (pattern aba -> ababa, for example vacation -> vacacation)
453
int SuggestMgr::doubletwochars_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
454
{
455
w_char candidate_utf[MAXSWL];
456
char candidate[MAXSWUTF8L];
457
int state=0;
458
if (wl < 5 || ! pAMgr) return ns;
459
for (int i=2; i < wl; i++) {
460
if (w_char_eq(word[i], word[i-2])) {
461
state++;
462
if (state==3) {
463
memcpy(candidate_utf, word, (i - 1) * sizeof(w_char));
464
memcpy(candidate_utf+i-1, word+i+1, (wl-i-1) * sizeof(w_char));
465
u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl-2);
466
ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
467
if (ns == -1) return -1;
468
state=0;
469
}
470
} else {
471
state=0;
472
}
473
}
474
return ns;
475
}
476
477
// error is wrong char in place of correct one (case and keyboard related version)
478
int SuggestMgr::badcharkey(char ** wlst, const char * word, int ns, int cpdsuggest)
479
{
480
char tmpc;
481
char candidate[MAXSWUTF8L];
482
int wl = strlen(word);
483
strcpy(candidate, word);
484
// swap out each char one by one and try uppercase and neighbor
485
// keyboard chars in its place to see if that makes a good word
486
487
for (int i=0; i < wl; i++) {
488
tmpc = candidate[i];
489
// check with uppercase letters
490
candidate[i] = csconv[((unsigned char)tmpc)].cupper;
491
if (tmpc != candidate[i]) {
492
ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
493
if (ns == -1) return -1;
494
candidate[i] = tmpc;
495
}
496
// check neighbor characters in keyboard string
497
if (!ckey) continue;
498
char * loc = strchr(ckey, tmpc);
499
while (loc) {
500
if ((loc > ckey) && (*(loc - 1) != '|')) {
501
candidate[i] = *(loc - 1);
502
ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
503
if (ns == -1) return -1;
504
}
505
if ((*(loc + 1) != '|') && (*(loc + 1) != '\0')) {
506
candidate[i] = *(loc + 1);
507
ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
508
if (ns == -1) return -1;
509
}
510
loc = strchr(loc + 1, tmpc);
511
}
512
candidate[i] = tmpc;
513
}
514
return ns;
515
}
516
517
// error is wrong char in place of correct one (case and keyboard related version)
518
int SuggestMgr::badcharkey_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
519
{
520
w_char tmpc;
521
w_char candidate_utf[MAXSWL];
522
char candidate[MAXSWUTF8L];
523
memcpy(candidate_utf, word, wl * sizeof(w_char));
524
// swap out each char one by one and try all the tryme
525
// chars in its place to see if that makes a good word
526
for (int i=0; i < wl; i++) {
527
tmpc = candidate_utf[i];
528
// check with uppercase letters
529
mkallcap_utf(candidate_utf + i, 1, langnum);
530
if (!w_char_eq(tmpc, candidate_utf[i])) {
531
u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
532
ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
533
if (ns == -1) return -1;
534
candidate_utf[i] = tmpc;
535
}
536
// check neighbor characters in keyboard string
537
if (!ckey) continue;
538
w_char * loc = ckey_utf;
539
while ((loc < (ckey_utf + ckeyl)) && !w_char_eq(*loc, tmpc)) loc++;
540
while (loc < (ckey_utf + ckeyl)) {
541
if ((loc > ckey_utf) && !w_char_eq(*(loc - 1), W_VLINE)) {
542
candidate_utf[i] = *(loc - 1);
543
u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
544
ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
545
if (ns == -1) return -1;
546
}
547
if (((loc + 1) < (ckey_utf + ckeyl)) && !w_char_eq(*(loc + 1), W_VLINE)) {
548
candidate_utf[i] = *(loc + 1);
549
u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
550
ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
551
if (ns == -1) return -1;
552
}
553
do { loc++; } while ((loc < (ckey_utf + ckeyl)) && !w_char_eq(*loc, tmpc));
554
}
555
candidate_utf[i] = tmpc;
556
}
557
return ns;
558
}
559
560
// error is wrong char in place of correct one
561
int SuggestMgr::badchar(char ** wlst, const char * word, int ns, int cpdsuggest)
562
{
563
char tmpc;
564
char candidate[MAXSWUTF8L];
565
clock_t timelimit = clock();
566
int timer = MINTIMER;
567
int wl = strlen(word);
568
strcpy(candidate, word);
569
// swap out each char one by one and try all the tryme
570
// chars in its place to see if that makes a good word
571
for (int j=0; j < ctryl; j++) {
572
for (int i=wl-1; i >= 0; i--) {
573
tmpc = candidate[i];
574
if (ctry[j] == tmpc) continue;
575
candidate[i] = ctry[j];
576
ns = testsug(wlst, candidate, wl, ns, cpdsuggest, &timer, &timelimit);
577
if (ns == -1) return -1;
578
if (!timer) return ns;
579
candidate[i] = tmpc;
580
}
581
}
582
return ns;
583
}
584
585
// error is wrong char in place of correct one
586
int SuggestMgr::badchar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
587
{
588
w_char tmpc;
589
w_char candidate_utf[MAXSWL];
590
char candidate[MAXSWUTF8L];
591
clock_t timelimit = clock();
592
int timer = MINTIMER;
593
memcpy(candidate_utf, word, wl * sizeof(w_char));
594
// swap out each char one by one and try all the tryme
595
// chars in its place to see if that makes a good word
596
for (int j=0; j < ctryl; j++) {
597
for (int i=wl-1; i >= 0; i--) {
598
tmpc = candidate_utf[i];
599
if (w_char_eq(tmpc, ctry_utf[j])) continue;
600
candidate_utf[i] = ctry_utf[j];
601
u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
602
ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, &timer, &timelimit);
603
if (ns == -1) return -1;
604
if (!timer) return ns;
605
candidate_utf[i] = tmpc;
606
}
607
}
608
return ns;
609
}
610
611
// error is word has an extra letter it does not need
612
int SuggestMgr::extrachar_utf(char** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
613
{
614
char candidate[MAXSWUTF8L];
615
w_char candidate_utf[MAXSWL];
616
w_char * p;
617
w_char tmpc = W_VLINE; // not used value, only for VCC warning message
618
if (wl < 2) return ns;
619
// try omitting one char of word at a time
620
memcpy(candidate_utf, word, wl * sizeof(w_char));
621
for (p = candidate_utf + wl - 1; p >= candidate_utf; p--) {
622
w_char tmpc2 = *p;
623
if (p < candidate_utf + wl - 1) *p = tmpc;
624
u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl - 1);
625
ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
626
if (ns == -1) return -1;
627
tmpc = tmpc2;
628
}
629
return ns;
630
}
631
632
// error is word has an extra letter it does not need
633
int SuggestMgr::extrachar(char** wlst, const char * word, int ns, int cpdsuggest)
634
{
635
char tmpc = '\0';
636
char candidate[MAXSWUTF8L];
637
char * p;
638
int wl = strlen(word);
639
if (wl < 2) return ns;
640
// try omitting one char of word at a time
641
strcpy (candidate, word);
642
for (p = candidate + wl - 1; p >=candidate; p--) {
643
char tmpc2 = *p;
644
*p = tmpc;
645
ns = testsug(wlst, candidate, wl-1, ns, cpdsuggest, NULL, NULL);
646
if (ns == -1) return -1;
647
tmpc = tmpc2;
648
}
649
return ns;
650
}
651
652
// error is missing a letter it needs
653
int SuggestMgr::forgotchar(char ** wlst, const char * word, int ns, int cpdsuggest)
654
{
655
char candidate[MAXSWUTF8L];
656
char * p;
657
clock_t timelimit = clock();
658
int timer = MINTIMER;
659
int wl = strlen(word);
660
// try inserting a tryme character before every letter (and the null terminator)
661
for (int i = 0; i < ctryl; i++) {
662
strcpy(candidate, word);
663
for (p = candidate + wl; p >= candidate; p--) {
664
*(p+1) = *p;
665
*p = ctry[i];
666
ns = testsug(wlst, candidate, wl+1, ns, cpdsuggest, &timer, &timelimit);
667
if (ns == -1) return -1;
668
if (!timer) return ns;
669
}
670
}
671
return ns;
672
}
673
674
// error is missing a letter it needs
675
int SuggestMgr::forgotchar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
676
{
677
w_char candidate_utf[MAXSWL];
678
char candidate[MAXSWUTF8L];
679
w_char * p;
680
clock_t timelimit = clock();
681
int timer = MINTIMER;
682
// try inserting a tryme character at the end of the word and before every letter
683
for (int i = 0; i < ctryl; i++) {
684
memcpy (candidate_utf, word, wl * sizeof(w_char));
685
for (p = candidate_utf + wl; p >= candidate_utf; p--) {
686
*(p + 1) = *p;
687
*p = ctry_utf[i];
688
u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl + 1);
689
ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, &timer, &timelimit);
690
if (ns == -1) return -1;
691
if (!timer) return ns;
692
}
693
}
694
return ns;
695
}
696
697
698
/* error is should have been two words */
699
int SuggestMgr::twowords(char ** wlst, const char * word, int ns, int cpdsuggest)
700
{
701
char candidate[MAXSWUTF8L];
702
char * p;
703
int c1, c2;
704
int forbidden = 0;
705
int cwrd;
706
707
int wl=strlen(word);
708
if (wl < 3) return ns;
709
710
if (langnum == LANG_hu) forbidden = check_forbidden(word, wl);
711
712
strcpy(candidate + 1, word);
713
// split the string into two pieces after every char
714
// if both pieces are good words make them a suggestion
715
for (p = candidate + 1; p[1] != '\0'; p++) {
716
p[-1] = *p;
717
// go to end of the UTF-8 character
718
while (utf8 && ((p[1] & 0xc0) == 0x80)) {
719
*p = p[1];
720
p++;
721
}
722
if (utf8 && p[1] == '\0') break; // last UTF-8 character
723
*p = '\0';
724
c1 = checkword(candidate,strlen(candidate), cpdsuggest, NULL, NULL);
725
if (c1) {
726
c2 = checkword((p+1),strlen(p+1), cpdsuggest, NULL, NULL);
727
if (c2) {
728
*p = ' ';
729
730
// spec. Hungarian code (need a better compound word support)
731
if ((langnum == LANG_hu) && !forbidden &&
732
// if 3 repeating letter, use - instead of space
733
(((p[-1] == p[1]) && (((p>candidate+1) && (p[-1] == p[-2])) || (p[-1] == p[2]))) ||
734
// or multiple compounding, with more, than 6 syllables
735
((c1 == 3) && (c2 >= 2)))) *p = '-';
736
737
cwrd = 1;
738
for (int k=0; k < ns; k++)
739
if (strcmp(candidate,wlst[k]) == 0) cwrd = 0;
740
if (ns < maxSug) {
741
if (cwrd) {
742
wlst[ns] = mystrdup(candidate);
743
if (wlst[ns] == NULL) return -1;
744
ns++;
745
}
746
} else return ns;
747
// add two word suggestion with dash, if TRY string contains
748
// "a" or "-"
749
// NOTE: cwrd doesn't modified for REP twoword sugg.
750
if (ctry && (strchr(ctry, 'a') || strchr(ctry, '-')) &&
751
mystrlen(p + 1) > 1 &&
752
mystrlen(candidate) - mystrlen(p) > 1) {
753
*p = '-';
754
for (int k=0; k < ns; k++)
755
if (strcmp(candidate,wlst[k]) == 0) cwrd = 0;
756
if (ns < maxSug) {
757
if (cwrd) {
758
wlst[ns] = mystrdup(candidate);
759
if (wlst[ns] == NULL) return -1;
760
ns++;
761
}
762
} else return ns;
763
}
764
}
765
}
766
}
767
return ns;
768
}
769
770
771
// error is adjacent letter were swapped
772
int SuggestMgr::swapchar(char ** wlst, const char * word, int ns, int cpdsuggest)
773
{
774
char candidate[MAXSWUTF8L];
775
char * p;
776
char tmpc;
777
int wl=strlen(word);
778
// try swapping adjacent chars one by one
779
strcpy(candidate, word);
780
for (p = candidate; p[1] != 0; p++) {
781
tmpc = *p;
782
*p = p[1];
783
p[1] = tmpc;
784
ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
785
if (ns == -1) return -1;
786
p[1] = *p;
787
*p = tmpc;
788
}
789
// try double swaps for short words
790
// ahev -> have, owudl -> would
791
if (wl == 4 || wl == 5) {
792
candidate[0] = word[1];
793
candidate[1] = word[0];
794
candidate[2] = word[2];
795
candidate[wl - 2] = word[wl - 1];
796
candidate[wl - 1] = word[wl - 2];
797
ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
798
if (ns == -1) return -1;
799
if (wl == 5) {
800
candidate[0] = word[0];
801
candidate[1] = word[2];
802
candidate[2] = word[1];
803
ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
804
if (ns == -1) return -1;
805
}
806
}
807
return ns;
808
}
809
810
// error is adjacent letter were swapped
811
int SuggestMgr::swapchar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
812
{
813
w_char candidate_utf[MAXSWL];
814
char candidate[MAXSWUTF8L];
815
w_char * p;
816
w_char tmpc;
817
int len = 0;
818
// try swapping adjacent chars one by one
819
memcpy (candidate_utf, word, wl * sizeof(w_char));
820
for (p = candidate_utf; p < (candidate_utf + wl - 1); p++) {
821
tmpc = *p;
822
*p = p[1];
823
p[1] = tmpc;
824
u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
825
if (len == 0) len = strlen(candidate);
826
ns = testsug(wlst, candidate, len, ns, cpdsuggest, NULL, NULL);
827
if (ns == -1) return -1;
828
p[1] = *p;
829
*p = tmpc;
830
}
831
// try double swaps for short words
832
// ahev -> have, owudl -> would, suodn -> sound
833
if (wl == 4 || wl == 5) {
834
candidate_utf[0] = word[1];
835
candidate_utf[1] = word[0];
836
candidate_utf[2] = word[2];
837
candidate_utf[wl - 2] = word[wl - 1];
838
candidate_utf[wl - 1] = word[wl - 2];
839
u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
840
ns = testsug(wlst, candidate, len, ns, cpdsuggest, NULL, NULL);
841
if (ns == -1) return -1;
842
if (wl == 5) {
843
candidate_utf[0] = word[0];
844
candidate_utf[1] = word[2];
845
candidate_utf[2] = word[1];
846
u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
847
ns = testsug(wlst, candidate, len, ns, cpdsuggest, NULL, NULL);
848
if (ns == -1) return -1;
849
}
850
}
851
return ns;
852
}
853
854
// error is not adjacent letter were swapped
855
int SuggestMgr::longswapchar(char ** wlst, const char * word, int ns, int cpdsuggest)
856
{
857
char candidate[MAXSWUTF8L];
858
char * p;
859
char * q;
860
char tmpc;
861
int wl=strlen(word);
862
// try swapping not adjacent chars one by one
863
strcpy(candidate, word);
864
for (p = candidate; *p != 0; p++) {
865
for (q = candidate; *q != 0; q++) {
866
if (abs((int)(p-q)) > 1) {
867
tmpc = *p;
868
*p = *q;
869
*q = tmpc;
870
ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
871
if (ns == -1) return -1;
872
*q = *p;
873
*p = tmpc;
874
}
875
}
876
}
877
return ns;
878
}
879
880
881
// error is adjacent letter were swapped
882
int SuggestMgr::longswapchar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
883
{
884
w_char candidate_utf[MAXSWL];
885
char candidate[MAXSWUTF8L];
886
w_char * p;
887
w_char * q;
888
w_char tmpc;
889
// try swapping not adjacent chars
890
memcpy (candidate_utf, word, wl * sizeof(w_char));
891
for (p = candidate_utf; p < (candidate_utf + wl); p++) {
892
for (q = candidate_utf; q < (candidate_utf + wl); q++) {
893
if (abs((int)(p-q)) > 1) {
894
tmpc = *p;
895
*p = *q;
896
*q = tmpc;
897
u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
898
ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
899
if (ns == -1) return -1;
900
*q = *p;
901
*p = tmpc;
902
}
903
}
904
}
905
return ns;
906
}
907
908
// error is a letter was moved
909
int SuggestMgr::movechar(char ** wlst, const char * word, int ns, int cpdsuggest)
910
{
911
char candidate[MAXSWUTF8L];
912
char * p;
913
char * q;
914
char tmpc;
915
916
int wl=strlen(word);
917
// try moving a char
918
strcpy(candidate, word);
919
for (p = candidate; *p != 0; p++) {
920
for (q = p + 1; (*q != 0) && ((q - p) < 10); q++) {
921
tmpc = *(q-1);
922
*(q-1) = *q;
923
*q = tmpc;
924
if ((q-p) < 2) continue; // omit swap char
925
ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
926
if (ns == -1) return -1;
927
}
928
strcpy(candidate, word);
929
}
930
for (p = candidate + wl - 1; p > candidate; p--) {
931
for (q = p - 1; (q >= candidate) && ((p - q) < 10); q--) {
932
tmpc = *(q+1);
933
*(q+1) = *q;
934
*q = tmpc;
935
if ((p-q) < 2) continue; // omit swap char
936
ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
937
if (ns == -1) return -1;
938
}
939
strcpy(candidate, word);
940
}
941
return ns;
942
}
943
944
// error is a letter was moved
945
int SuggestMgr::movechar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
946
{
947
w_char candidate_utf[MAXSWL];
948
char candidate[MAXSWUTF8L];
949
w_char * p;
950
w_char * q;
951
w_char tmpc;
952
// try moving a char
953
memcpy (candidate_utf, word, wl * sizeof(w_char));
954
for (p = candidate_utf; p < (candidate_utf + wl); p++) {
955
for (q = p + 1; (q < (candidate_utf + wl)) && ((q - p) < 10); q++) {
956
tmpc = *(q-1);
957
*(q-1) = *q;
958
*q = tmpc;
959
if ((q-p) < 2) continue; // omit swap char
960
u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
961
ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
962
if (ns == -1) return -1;
963
}
964
memcpy (candidate_utf, word, wl * sizeof(w_char));
965
}
966
for (p = candidate_utf + wl - 1; p > candidate_utf; p--) {
967
for (q = p - 1; (q >= candidate_utf) && ((p - q) < 10); q--) {
968
tmpc = *(q+1);
969
*(q+1) = *q;
970
*q = tmpc;
971
if ((p-q) < 2) continue; // omit swap char
972
u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
973
ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
974
if (ns == -1) return -1;
975
}
976
memcpy (candidate_utf, word, wl * sizeof(w_char));
977
}
978
return ns;
979
}
980
981
// generate a set of suggestions for very poorly spelled words
982
int SuggestMgr::ngsuggest(char** wlst, char * w, int ns, HashMgr** pHMgr, int md)
983
{
984
985
int i, j;
986
int lval;
987
int sc, scphon;
988
int lp, lpphon;
989
int nonbmp = 0;
990
991
// exhaustively search through all root words
992
// keeping track of the MAX_ROOTS most similar root words
993
struct hentry * roots[MAX_ROOTS];
994
char * rootsphon[MAX_ROOTS];
995
int scores[MAX_ROOTS];
996
int scoresphon[MAX_ROOTS];
997
for (i = 0; i < MAX_ROOTS; i++) {
998
roots[i] = NULL;
999
scores[i] = -100 * i;
1000
rootsphon[i] = NULL;
1001
scoresphon[i] = -100 * i;
1002
}
1003
lp = MAX_ROOTS - 1;
1004
lpphon = MAX_ROOTS - 1;
1005
scphon = scoresphon[MAX_ROOTS-1];
1006
1007
char w2[MAXWORDUTF8LEN];
1008
char f[MAXSWUTF8L];
1009
char * word = w;
1010
1011
// word reversing wrapper for complex prefixes
1012
if (complexprefixes) {
1013
strcpy(w2, w);
1014
if (utf8) reverseword_utf(w2); else reverseword(w2);
1015
word = w2;
1016
}
1017
1018
char mw[MAXSWUTF8L];
1019
w_char u8[MAXSWL];
1020
int nc = strlen(word);
1021
int n = (utf8) ? u8_u16(u8, MAXSWL, word) : nc;
1022
1023
// set character based ngram suggestion for words with non-BMP Unicode characters
1024
if (n == -1) {
1025
utf8 = 0;
1026
n = nc;
1027
nonbmp = 1;
1028
}
1029
1030
struct hentry* hp = NULL;
1031
int col = -1;
1032
phonetable * ph = (pAMgr) ? pAMgr->get_phonetable() : NULL;
1033
char target[MAXSWUTF8L];
1034
char candidate[MAXSWUTF8L];
1035
if (ph) {
1036
strcpy(candidate, word);
1037
mkallcap(candidate, csconv);
1038
phonet(candidate, target, n, *ph);
1039
}
1040
1041
for (i = 0; i < md; i++) {
1042
while (0 != (hp = (pHMgr[i])->walk_hashtable(col, hp))) {
1043
if ((hp->astr) && (pAMgr) &&
1044
(TESTAFF(hp->astr, pAMgr->get_forbiddenword(), hp->alen) ||
1045
TESTAFF(hp->astr, ONLYUPCASEFLAG, hp->alen) ||
1046
TESTAFF(hp->astr, pAMgr->get_nosuggest(), hp->alen) ||
1047
TESTAFF(hp->astr, pAMgr->get_onlyincompound(), hp->alen))) continue;
1048
1049
sc = ngram(3, word, HENTRY_WORD(hp), NGRAM_LONGER_WORSE + NGRAM_LOWERING) +
1050
leftcommonsubstring(word, HENTRY_WORD(hp));
1051
1052
// check special pronounciation
1053
if ((hp->var & H_OPT_PHON) && copy_field(f, HENTRY_DATA(hp), MORPH_PHON)) {
1054
int sc2 = ngram(3, word, f, NGRAM_LONGER_WORSE + NGRAM_LOWERING) +
1055
leftcommonsubstring(word, f);
1056
if (sc2 > sc) sc = sc2;
1057
}
1058
1059
if (ph && (sc > 2) && (abs(n - (int) hp->clen) <= 3)) {
1060
char target2[MAXSWUTF8L];
1061
strcpy(candidate, HENTRY_WORD(hp));
1062
mkallcap(candidate, csconv);
1063
phonet(candidate, target2, -1, *ph);
1064
scphon = 2 * ngram(3, target, target2, NGRAM_LONGER_WORSE);
1065
}
1066
1067
if (sc > scores[lp]) {
1068
scores[lp] = sc;
1069
roots[lp] = hp;
1070
lval = sc;
1071
for (j=0; j < MAX_ROOTS; j++)
1072
if (scores[j] < lval) {
1073
lp = j;
1074
lval = scores[j];
1075
}
1076
}
1077
1078
if (scphon > scoresphon[lpphon]) {
1079
scoresphon[lpphon] = scphon;
1080
rootsphon[lpphon] = HENTRY_WORD(hp);
1081
lval = scphon;
1082
for (j=0; j < MAX_ROOTS; j++)
1083
if (scoresphon[j] < lval) {
1084
lpphon = j;
1085
lval = scoresphon[j];
1086
}
1087
}
1088
}}
1089
1090
// find minimum threshold for a passable suggestion
1091
// mangle original word three differnt ways
1092
// and score them to generate a minimum acceptable score
1093
int thresh = 0;
1094
for (int sp = 1; sp < 4; sp++) {
1095
if (utf8) {
1096
for (int k=sp; k < n; k+=4) *((unsigned short *) u8 + k) = '*';
1097
u16_u8(mw, MAXSWUTF8L, u8, n);
1098
thresh = thresh + ngram(n, word, mw, NGRAM_ANY_MISMATCH + NGRAM_LOWERING);
1099
} else {
1100
strcpy(mw, word);
1101
for (int k=sp; k < n; k+=4) *(mw + k) = '*';
1102
thresh = thresh + ngram(n, word, mw, NGRAM_ANY_MISMATCH + NGRAM_LOWERING);
1103
}
1104
}
1105
thresh = thresh / 3;
1106
thresh--;
1107
1108
// now expand affixes on each of these root words and
1109
// and use length adjusted ngram scores to select
1110
// possible suggestions
1111
char * guess[MAX_GUESS];
1112
char * guessorig[MAX_GUESS];
1113
int gscore[MAX_GUESS];
1114
for(i=0;i<MAX_GUESS;i++) {
1115
guess[i] = NULL;
1116
guessorig[i] = NULL;
1117
gscore[i] = -100 * i;
1118
}
1119
1120
lp = MAX_GUESS - 1;
1121
1122
struct guessword * glst;
1123
glst = (struct guessword *) calloc(MAX_WORDS,sizeof(struct guessword));
1124
if (! glst) {
1125
if (nonbmp) utf8 = 1;
1126
return ns;
1127
}
1128
1129
for (i = 0; i < MAX_ROOTS; i++) {
1130
if (roots[i]) {
1131
struct hentry * rp = roots[i];
1132
int nw = pAMgr->expand_rootword(glst, MAX_WORDS, HENTRY_WORD(rp), rp->blen,
1133
rp->astr, rp->alen, word, nc,
1134
((rp->var & H_OPT_PHON) ? copy_field(f, HENTRY_DATA(rp), MORPH_PHON) : NULL));
1135
1136
for (int k = 0; k < nw ; k++) {
1137
sc = ngram(n, word, glst[k].word, NGRAM_ANY_MISMATCH + NGRAM_LOWERING) +
1138
leftcommonsubstring(word, glst[k].word);
1139
1140
if ((sc > thresh)) {
1141
if (sc > gscore[lp]) {
1142
if (guess[lp]) {
1143
free (guess[lp]);
1144
if (guessorig[lp]) {
1145
free(guessorig[lp]);
1146
guessorig[lp] = NULL;
1147
}
1148
}
1149
gscore[lp] = sc;
1150
guess[lp] = glst[k].word;
1151
guessorig[lp] = glst[k].orig;
1152
lval = sc;
1153
for (j=0; j < MAX_GUESS; j++)
1154
if (gscore[j] < lval) {
1155
lp = j;
1156
lval = gscore[j];
1157
}
1158
} else {
1159
free(glst[k].word);
1160
if (glst[k].orig) free(glst[k].orig);
1161
}
1162
} else {
1163
free(glst[k].word);
1164
if (glst[k].orig) free(glst[k].orig);
1165
}
1166
}
1167
}
1168
}
1169
free(glst);
1170
1171
// now we are done generating guesses
1172
// sort in order of decreasing score
1173
1174
1175
bubblesort(&guess[0], &guessorig[0], &gscore[0], MAX_GUESS);
1176
if (ph) bubblesort(&rootsphon[0], NULL, &scoresphon[0], MAX_ROOTS);
1177
1178
// weight suggestions with a similarity index, based on
1179
// the longest common subsequent algorithm and resort
1180
1181
int is_swap;
1182
for (i=0; i < MAX_GUESS; i++) {
1183
if (guess[i]) {
1184
// lowering guess[i]
1185
char gl[MAXSWUTF8L];
1186
int len;
1187
if (utf8) {
1188
w_char _w[MAXSWL];
1189
len = u8_u16(_w, MAXSWL, guess[i]);
1190
mkallsmall_utf(_w, len, langnum);
1191
u16_u8(gl, MAXSWUTF8L, _w, len);
1192
} else {
1193
strcpy(gl, guess[i]);
1194
mkallsmall(gl, csconv);
1195
len = strlen(guess[i]);
1196
}
1197
1198
int _lcs = lcslen(word, gl);
1199
1200
// same characters with different casing
1201
if ((n == len) && (n == _lcs)) {
1202
gscore[i] += 2000;
1203
break;
1204
}
1205
1206
// heuristic weigthing of ngram scores
1207
gscore[i] +=
1208
// length of longest common subsequent minus length difference
1209
2 * _lcs - abs((int) (n - len)) +
1210
// weight length of the left common substring
1211
leftcommonsubstring(word, gl) +
1212
// weight equal character positions
1213
((_lcs == commoncharacterpositions(word, gl, &is_swap)) ? 1: 0) +
1214
// swap character (not neighboring)
1215
((is_swap) ? 1000 : 0);
1216
}
1217
}
1218
1219
bubblesort(&guess[0], &guessorig[0], &gscore[0], MAX_GUESS);
1220
1221
// phonetic version
1222
if (ph) for (i=0; i < MAX_ROOTS; i++) {
1223
if (rootsphon[i]) {
1224
// lowering rootphon[i]
1225
char gl[MAXSWUTF8L];
1226
int len;
1227
if (utf8) {
1228
w_char _w[MAXSWL];
1229
len = u8_u16(_w, MAXSWL, rootsphon[i]);
1230
mkallsmall_utf(_w, len, langnum);
1231
u16_u8(gl, MAXSWUTF8L, _w, len);
1232
} else {
1233
strcpy(gl, rootsphon[i]);
1234
mkallsmall(gl, csconv);
1235
len = strlen(rootsphon[i]);
1236
}
1237
1238
// heuristic weigthing of ngram scores
1239
scoresphon[i] += 2 * lcslen(word, gl) - abs((int) (n - len)) +
1240
// weight length of the left common substring
1241
leftcommonsubstring(word, gl);
1242
}
1243
}
1244
1245
if (ph) bubblesort(&rootsphon[0], NULL, &scoresphon[0], MAX_ROOTS);
1246
1247
// copy over
1248
int oldns = ns;
1249
1250
int same = 0;
1251
for (i=0; i < MAX_GUESS; i++) {
1252
if (guess[i]) {
1253
if ((ns < oldns + maxngramsugs) && (ns < maxSug) && (!same || (gscore[i] > 1000))) {
1254
int unique = 1;
1255
// leave only excellent suggestions, if exists
1256
if (gscore[i] > 1000) same = 1;
1257
for (j = 0; j < ns; j++) {
1258
// don't suggest previous suggestions or a previous suggestion with prefixes or affixes
1259
if ((!guessorig[i] && strstr(guess[i], wlst[j])) ||
1260
(guessorig[i] && strstr(guessorig[i], wlst[j])) ||
1261
// check forbidden words
1262
!checkword(guess[i], strlen(guess[i]), 0, NULL, NULL)) unique = 0;
1263
}
1264
if (unique) {
1265
wlst[ns++] = guess[i];
1266
if (guessorig[i]) {
1267
free(guess[i]);
1268
wlst[ns-1] = guessorig[i];
1269
}
1270
} else {
1271
free(guess[i]);
1272
if (guessorig[i]) free(guessorig[i]);
1273
}
1274
} else {
1275
free(guess[i]);
1276
if (guessorig[i]) free(guessorig[i]);
1277
}
1278
}
1279
}
1280
1281
oldns = ns;
1282
if (ph) for (i=0; i < MAX_ROOTS; i++) {
1283
if (rootsphon[i]) {
1284
if ((ns < oldns + MAXPHONSUGS) && (ns < maxSug)) {
1285
int unique = 1;
1286
for (j = 0; j < ns; j++) {
1287
// don't suggest previous suggestions or a previous suggestion with prefixes or affixes
1288
if (strstr(rootsphon[i], wlst[j]) ||
1289
// check forbidden words
1290
!checkword(rootsphon[i], strlen(rootsphon[i]), 0, NULL, NULL)) unique = 0;
1291
}
1292
if (unique) {
1293
wlst[ns++] = mystrdup(rootsphon[i]);
1294
if (!wlst[ns - 1]) return ns - 1;
1295
}
1296
}
1297
}
1298
}
1299
1300
if (nonbmp) utf8 = 1;
1301
return ns;
1302
}
1303
1304
1305
// see if a candidate suggestion is spelled correctly
1306
// needs to check both root words and words with affixes
1307
1308
// obsolote MySpell-HU modifications:
1309
// return value 2 and 3 marks compounding with hyphen (-)
1310
// `3' marks roots without suffix
1311
int SuggestMgr::checkword(const char * word, int len, int cpdsuggest, int * timer, clock_t * timelimit)
1312
{
1313
struct hentry * rv=NULL;
1314
int nosuffix = 0;
1315
1316
// check time limit
1317
if (timer) {
1318
(*timer)--;
1319
if (!(*timer) && timelimit) {
1320
if ((clock() - *timelimit) > TIMELIMIT) return 0;
1321
*timer = MAXPLUSTIMER;
1322
}
1323
}
1324
1325
if (pAMgr) {
1326
if (cpdsuggest==1) {
1327
if (pAMgr->get_compound()) {
1328
rv = pAMgr->compound_check(word, len, 0, 0, 100, 0, NULL, 0, 1); //EXT
1329
if (rv) return 3; // XXX obsolote categorisation
1330
}
1331
return 0;
1332
}
1333
1334
rv = pAMgr->lookup(word);
1335
1336
if (rv) {
1337
if ((rv->astr) && (TESTAFF(rv->astr,pAMgr->get_forbiddenword(),rv->alen)
1338
|| TESTAFF(rv->astr,pAMgr->get_nosuggest(),rv->alen))) return 0;
1339
while (rv) {
1340
if (rv->astr && (TESTAFF(rv->astr,pAMgr->get_needaffix(),rv->alen) ||
1341
TESTAFF(rv->astr, ONLYUPCASEFLAG, rv->alen) ||
1342
TESTAFF(rv->astr,pAMgr->get_onlyincompound(),rv->alen))) {
1343
rv = rv->next_homonym;
1344
} else break;
1345
}
1346
} else rv = pAMgr->prefix_check(word, len, 0); // only prefix, and prefix + suffix XXX
1347
1348
if (rv) {
1349
nosuffix=1;
1350
} else {
1351
rv = pAMgr->suffix_check(word, len, 0, NULL, NULL, 0, NULL); // only suffix
1352
}
1353
1354
if (!rv && pAMgr->have_contclass()) {
1355
rv = pAMgr->suffix_check_twosfx(word, len, 0, NULL, FLAG_NULL);
1356
if (!rv) rv = pAMgr->prefix_check_twosfx(word, len, 1, FLAG_NULL);
1357
}
1358
1359
// check forbidden words
1360
if ((rv) && (rv->astr) && (TESTAFF(rv->astr,pAMgr->get_forbiddenword(),rv->alen) ||
1361
TESTAFF(rv->astr, ONLYUPCASEFLAG, rv->alen) ||
1362
TESTAFF(rv->astr,pAMgr->get_nosuggest(),rv->alen) ||
1363
TESTAFF(rv->astr,pAMgr->get_onlyincompound(),rv->alen))) return 0;
1364
1365
if (rv) { // XXX obsolote
1366
if ((pAMgr->get_compoundflag()) &&
1367
TESTAFF(rv->astr, pAMgr->get_compoundflag(), rv->alen)) return 2 + nosuffix;
1368
return 1;
1369
}
1370
}
1371
return 0;
1372
}
1373
1374
int SuggestMgr::check_forbidden(const char * word, int len)
1375
{
1376
struct hentry * rv = NULL;
1377
1378
if (pAMgr) {
1379
rv = pAMgr->lookup(word);
1380
if (rv && rv->astr && (TESTAFF(rv->astr,pAMgr->get_needaffix(),rv->alen) ||
1381
TESTAFF(rv->astr,pAMgr->get_onlyincompound(),rv->alen))) rv = NULL;
1382
if (!(pAMgr->prefix_check(word,len,1)))
1383
rv = pAMgr->suffix_check(word,len, 0, NULL, NULL, 0, NULL); // prefix+suffix, suffix
1384
// check forbidden words
1385
if ((rv) && (rv->astr) && TESTAFF(rv->astr,pAMgr->get_forbiddenword(),rv->alen)) return 1;
1386
}
1387
return 0;
1388
}
1389
1390
#ifdef HUNSPELL_EXPERIMENTAL
1391
// suggest possible stems
1392
int SuggestMgr::suggest_pos_stems(char*** slst, const char * w, int nsug)
1393
{
1394
char ** wlst;
1395
1396
struct hentry * rv = NULL;
1397
1398
char w2[MAXSWUTF8L];
1399
const char * word = w;
1400
1401
// word reversing wrapper for complex prefixes
1402
if (complexprefixes) {
1403
strcpy(w2, w);
1404
if (utf8) reverseword_utf(w2); else reverseword(w2);
1405
word = w2;
1406
}
1407
1408
int wl = strlen(word);
1409
1410
1411
if (*slst) {
1412
wlst = *slst;
1413
} else {
1414
wlst = (char **) calloc(maxSug, sizeof(char *));
1415
if (wlst == NULL) return -1;
1416
}
1417
1418
rv = pAMgr->suffix_check(word, wl, 0, NULL, wlst, maxSug, &nsug);
1419
1420
// delete dash from end of word
1421
if (nsug > 0) {
1422
for (int j=0; j < nsug; j++) {
1423
if (wlst[j][strlen(wlst[j]) - 1] == '-') wlst[j][strlen(wlst[j]) - 1] = '\0';
1424
}
1425
}
1426
1427
*slst = wlst;
1428
return nsug;
1429
}
1430
#endif // END OF HUNSPELL_EXPERIMENTAL CODE
1431
1432
1433
char * SuggestMgr::suggest_morph(const char * w)
1434
{
1435
char result[MAXLNLEN];
1436
char * r = (char *) result;
1437
char * st;
1438
1439
struct hentry * rv = NULL;
1440
1441
*result = '\0';
1442
1443
if (! pAMgr) return NULL;
1444
1445
char w2[MAXSWUTF8L];
1446
const char * word = w;
1447
1448
// word reversing wrapper for complex prefixes
1449
if (complexprefixes) {
1450
strcpy(w2, w);
1451
if (utf8) reverseword_utf(w2); else reverseword(w2);
1452
word = w2;
1453
}
1454
1455
rv = pAMgr->lookup(word);
1456
1457
while (rv) {
1458
if ((!rv->astr) || !(TESTAFF(rv->astr, pAMgr->get_forbiddenword(), rv->alen) ||
1459
TESTAFF(rv->astr, pAMgr->get_needaffix(), rv->alen) ||
1460
TESTAFF(rv->astr,pAMgr->get_onlyincompound(),rv->alen))) {
1461
if (!HENTRY_FIND(rv, MORPH_STEM)) {
1462
mystrcat(result, " ", MAXLNLEN);
1463
mystrcat(result, MORPH_STEM, MAXLNLEN);
1464
mystrcat(result, word, MAXLNLEN);
1465
}
1466
if (HENTRY_DATA(rv)) {
1467
mystrcat(result, " ", MAXLNLEN);
1468
mystrcat(result, HENTRY_DATA2(rv), MAXLNLEN);
1469
}
1470
mystrcat(result, "\n", MAXLNLEN);
1471
}
1472
rv = rv->next_homonym;
1473
}
1474
1475
st = pAMgr->affix_check_morph(word,strlen(word));
1476
if (st) {
1477
mystrcat(result, st, MAXLNLEN);
1478
free(st);
1479
}
1480
1481
if (pAMgr->get_compound() && (*result == '\0'))
1482
pAMgr->compound_check_morph(word, strlen(word),
1483
0, 0, 100, 0,NULL, 0, &r, NULL);
1484
1485
return (*result) ? mystrdup(line_uniq(result, MSEP_REC)) : NULL;
1486
}
1487
1488
#ifdef HUNSPELL_EXPERIMENTAL
1489
char * SuggestMgr::suggest_morph_for_spelling_error(const char * word)
1490
{
1491
char * p = NULL;
1492
char ** wlst = (char **) calloc(maxSug, sizeof(char *));
1493
if (!**wlst) return NULL;
1494
// we will use only the first suggestion
1495
for (int i = 0; i < maxSug - 1; i++) wlst[i] = "";
1496
int ns = suggest(&wlst, word, maxSug - 1, NULL);
1497
if (ns == maxSug) {
1498
p = suggest_morph(wlst[maxSug - 1]);
1499
free(wlst[maxSug - 1]);
1500
}
1501
if (wlst) free(wlst);
1502
return p;
1503
}
1504
#endif // END OF HUNSPELL_EXPERIMENTAL CODE
1505
1506
/* affixation */
1507
char * SuggestMgr::suggest_hentry_gen(hentry * rv, char * pattern)
1508
{
1509
char result[MAXLNLEN];
1510
*result = '\0';
1511
int sfxcount = get_sfxcount(pattern);
1512
1513
if (get_sfxcount(HENTRY_DATA(rv)) > sfxcount) return NULL;
1514
1515
if (HENTRY_DATA(rv)) {
1516
char * aff = pAMgr->morphgen(HENTRY_WORD(rv), rv->blen, rv->astr, rv->alen,
1517
HENTRY_DATA(rv), pattern, 0);
1518
if (aff) {
1519
mystrcat(result, aff, MAXLNLEN);
1520
mystrcat(result, "\n", MAXLNLEN);
1521
free(aff);
1522
}
1523
}
1524
1525
// check all allomorphs
1526
char allomorph[MAXLNLEN];
1527
char * p = NULL;
1528
if (HENTRY_DATA(rv)) p = (char *) strstr(HENTRY_DATA2(rv), MORPH_ALLOMORPH);
1529
while (p) {
1530
struct hentry * rv2 = NULL;
1531
p += MORPH_TAG_LEN;
1532
int plen = fieldlen(p);
1533
strncpy(allomorph, p, plen);
1534
allomorph[plen] = '\0';
1535
rv2 = pAMgr->lookup(allomorph);
1536
while (rv2) {
1537
// if (HENTRY_DATA(rv2) && get_sfxcount(HENTRY_DATA(rv2)) <= sfxcount) {
1538
if (HENTRY_DATA(rv2)) {
1539
char * st = (char *) strstr(HENTRY_DATA2(rv2), MORPH_STEM);
1540
if (st && (strncmp(st + MORPH_TAG_LEN,
1541
HENTRY_WORD(rv), fieldlen(st + MORPH_TAG_LEN)) == 0)) {
1542
char * aff = pAMgr->morphgen(HENTRY_WORD(rv2), rv2->blen, rv2->astr, rv2->alen,
1543
HENTRY_DATA(rv2), pattern, 0);
1544
if (aff) {
1545
mystrcat(result, aff, MAXLNLEN);
1546
mystrcat(result, "\n", MAXLNLEN);
1547
free(aff);
1548
}
1549
}
1550
}
1551
rv2 = rv2->next_homonym;
1552
}
1553
p = strstr(p + plen, MORPH_ALLOMORPH);
1554
}
1555
1556
return (*result) ? mystrdup(result) : NULL;
1557
}
1558
1559
char * SuggestMgr::suggest_gen(char ** desc, int n, char * pattern) {
1560
char result[MAXLNLEN];
1561
char result2[MAXLNLEN];
1562
char newpattern[MAXLNLEN];
1563
*newpattern = '\0';
1564
if (n == 0) return 0;
1565
*result2 = '\0';
1566
struct hentry * rv = NULL;
1567
if (!pAMgr) return NULL;
1568
1569
// search affixed forms with and without derivational suffixes
1570
while(1) {
1571
1572
for (int k = 0; k < n; k++) {
1573
*result = '\0';
1574
// add compound word parts (except the last one)
1575
char * s = (char *) desc[k];
1576
char * part = strstr(s, MORPH_PART);
1577
if (part) {
1578
char * nextpart = strstr(part + 1, MORPH_PART);
1579
while (nextpart) {
1580
copy_field(result + strlen(result), part, MORPH_PART);
1581
part = nextpart;
1582
nextpart = strstr(part + 1, MORPH_PART);
1583
}
1584
s = part;
1585
}
1586
1587
char **pl;
1588
char tok[MAXLNLEN];
1589
strcpy(tok, s);
1590
char * alt = strstr(tok, " | ");
1591
while (alt) {
1592
alt[1] = MSEP_ALT;
1593
alt = strstr(alt, " | ");
1594
}
1595
int pln = line_tok(tok, &pl, MSEP_ALT);
1596
for (int i = 0; i < pln; i++) {
1597
// remove inflectional and terminal suffixes
1598
char * is = strstr(pl[i], MORPH_INFL_SFX);
1599
if (is) *is = '\0';
1600
char * ts = strstr(pl[i], MORPH_TERM_SFX);
1601
while (ts) {
1602
*ts = '_';
1603
ts = strstr(pl[i], MORPH_TERM_SFX);
1604
}
1605
char * st = strstr(s, MORPH_STEM);
1606
if (st) {
1607
copy_field(tok, st, MORPH_STEM);
1608
rv = pAMgr->lookup(tok);
1609
while (rv) {
1610
char newpat[MAXLNLEN];
1611
strcpy(newpat, pl[i]);
1612
strcat(newpat, pattern);
1613
char * sg = suggest_hentry_gen(rv, newpat);
1614
if (!sg) sg = suggest_hentry_gen(rv, pattern);
1615
if (sg) {
1616
char ** gen;
1617
int genl = line_tok(sg, &gen, MSEP_REC);
1618
free(sg);
1619
sg = NULL;
1620
for (int j = 0; j < genl; j++) {
1621
if (strstr(pl[i], MORPH_SURF_PFX)) {
1622
int r2l = strlen(result2);
1623
result2[r2l] = MSEP_REC;
1624
strcpy(result2 + r2l + 1, result);
1625
copy_field(result2 + strlen(result2), pl[i], MORPH_SURF_PFX);
1626
mystrcat(result2, gen[j], MAXLNLEN);
1627
} else {
1628
sprintf(result2 + strlen(result2), "%c%s%s",
1629
MSEP_REC, result, gen[j]);
1630
}
1631
}
1632
freelist(&gen, genl);
1633
}
1634
rv = rv->next_homonym;
1635
}
1636
}
1637
}
1638
freelist(&pl, pln);
1639
}
1640
1641
if (*result2 || !strstr(pattern, MORPH_DERI_SFX)) break;
1642
strcpy(newpattern, pattern);
1643
pattern = newpattern;
1644
char * ds = strstr(pattern, MORPH_DERI_SFX);
1645
while (ds) {
1646
strncpy(ds, MORPH_TERM_SFX, MORPH_TAG_LEN);
1647
ds = strstr(pattern, MORPH_DERI_SFX);
1648
}
1649
}
1650
return (*result2 ? mystrdup(result2) : NULL);
1651
}
1652
1653
1654
// generate an n-gram score comparing s1 and s2
1655
int SuggestMgr::ngram(int n, char * s1, const char * s2, int opt)
1656
{
1657
int nscore = 0;
1658
int ns;
1659
int l1;
1660
int l2;
1661
1662
if (utf8) {
1663
w_char su1[MAXSWL];
1664
w_char su2[MAXSWL];
1665
l1 = u8_u16(su1, MAXSWL, s1);
1666
l2 = u8_u16(su2, MAXSWL, s2);
1667
if ((l2 <= 0) || (l1 == -1)) return 0;
1668
// lowering dictionary word
1669
if (opt & NGRAM_LOWERING) mkallsmall_utf(su2, l2, langnum);
1670
for (int j = 1; j <= n; j++) {
1671
ns = 0;
1672
for (int i = 0; i <= (l1-j); i++) {
1673
for (int l = 0; l <= (l2-j); l++) {
1674
int k;
1675
for (k = 0; (k < j); k++) {
1676
w_char * c1 = su1 + i + k;
1677
w_char * c2 = su2 + l + k;
1678
if ((c1->l != c2->l) || (c1->h != c2->h)) break;
1679
}
1680
if (k == j) {
1681
ns++;
1682
break;
1683
}
1684
}
1685
}
1686
nscore = nscore + ns;
1687
if (ns < 2) break;
1688
}
1689
} else {
1690
l2 = strlen(s2);
1691
if (l2 == 0) return 0;
1692
l1 = strlen(s1);
1693
char *t = mystrdup(s2);
1694
if (opt & NGRAM_LOWERING) mkallsmall(t, csconv);
1695
for (int j = 1; j <= n; j++) {
1696
ns = 0;
1697
for (int i = 0; i <= (l1-j); i++) {
1698
char c = *(s1 + i + j);
1699
*(s1 + i + j) = '\0';
1700
if (strstr(t,(s1+i))) ns++;
1701
*(s1 + i + j ) = c;
1702
}
1703
nscore = nscore + ns;
1704
if (ns < 2) break;
1705
}
1706
free(t);
1707
}
1708
1709
ns = 0;
1710
if (opt & NGRAM_LONGER_WORSE) ns = (l2-l1)-2;
1711
if (opt & NGRAM_ANY_MISMATCH) ns = abs(l2-l1)-2;
1712
ns = (nscore - ((ns > 0) ? ns : 0));
1713
return ns;
1714
}
1715
1716
// length of the left common substring of s1 and (decapitalised) s2
1717
int SuggestMgr::leftcommonsubstring(char * s1, const char * s2) {
1718
if (utf8) {
1719
w_char su1[MAXSWL];
1720
w_char su2[MAXSWL];
1721
// decapitalize dictionary word
1722
if (complexprefixes) {
1723
int l1 = u8_u16(su1, MAXSWL, s1);
1724
int l2 = u8_u16(su2, MAXSWL, s2);
1725
if (*((short *)su1+l1-1) == *((short *)su2+l2-1)) return 1;
1726
} else {
1727
int i;
1728
u8_u16(su1, 1, s1);
1729
u8_u16(su2, 1, s2);
1730
unsigned short idx = (su2->h << 8) + su2->l;
1731
unsigned short otheridx = (su1->h << 8) + su1->l;
1732
if (otheridx != idx &&
1733
(otheridx != unicodetolower(idx, langnum))) return 0;
1734
int l1 = u8_u16(su1, MAXSWL, s1);
1735
int l2 = u8_u16(su2, MAXSWL, s2);
1736
for(i = 1; (i < l1) && (i < l2) &&
1737
(su1[i].l == su2[i].l) && (su1[i].h == su2[i].h); i++);
1738
return i;
1739
}
1740
} else {
1741
if (complexprefixes) {
1742
int l1 = strlen(s1);
1743
int l2 = strlen(s2);
1744
if (*(s2+l1-1) == *(s2+l2-1)) return 1;
1745
} else {
1746
char * olds = s1;
1747
// decapitalise dictionary word
1748
if ((*s1 != *s2) && (*s1 != csconv[((unsigned char)*s2)].clower)) return 0;
1749
do {
1750
s1++; s2++;
1751
} while ((*s1 == *s2) && (*s1 != '\0'));
1752
return (int)(s1 - olds);
1753
}
1754
}
1755
return 0;
1756
}
1757
1758
int SuggestMgr::commoncharacterpositions(char * s1, const char * s2, int * is_swap) {
1759
int num = 0;
1760
int diff = 0;
1761
int diffpos[2];
1762
*is_swap = 0;
1763
if (utf8) {
1764
w_char su1[MAXSWL];
1765
w_char su2[MAXSWL];
1766
int l1 = u8_u16(su1, MAXSWL, s1);
1767
int l2 = u8_u16(su2, MAXSWL, s2);
1768
// decapitalize dictionary word
1769
if (complexprefixes) {
1770
mkallsmall_utf(su2+l2-1, 1, langnum);
1771
} else {
1772
mkallsmall_utf(su2, 1, langnum);
1773
}
1774
for (int i = 0; (i < l1) && (i < l2); i++) {
1775
if (((short *) su1)[i] == ((short *) su2)[i]) {
1776
num++;
1777
} else {
1778
if (diff < 2) diffpos[diff] = i;
1779
diff++;
1780
}
1781
}
1782
if ((diff == 2) && (l1 == l2) &&
1783
(((short *) su1)[diffpos[0]] == ((short *) su2)[diffpos[1]]) &&
1784
(((short *) su1)[diffpos[1]] == ((short *) su2)[diffpos[0]])) *is_swap = 1;
1785
} else {
1786
int i;
1787
char t[MAXSWUTF8L];
1788
strcpy(t, s2);
1789
// decapitalize dictionary word
1790
if (complexprefixes) {
1791
int l2 = strlen(t);
1792
*(t+l2-1) = csconv[((unsigned char)*(t+l2-1))].clower;
1793
} else {
1794
mkallsmall(t, csconv);
1795
}
1796
for (i = 0; (*(s1+i) != 0) && (*(t+i) != 0); i++) {
1797
if (*(s1+i) == *(t+i)) {
1798
num++;
1799
} else {
1800
if (diff < 2) diffpos[diff] = i;
1801
diff++;
1802
}
1803
}
1804
if ((diff == 2) && (*(s1+i) == 0) && (*(t+i) == 0) &&
1805
(*(s1+diffpos[0]) == *(t+diffpos[1])) &&
1806
(*(s1+diffpos[1]) == *(t+diffpos[0]))) *is_swap = 1;
1807
}
1808
return num;
1809
}
1810
1811
int SuggestMgr::mystrlen(const char * word) {
1812
if (utf8) {
1813
w_char w[MAXSWL];
1814
return u8_u16(w, MAXSWL, word);
1815
} else return strlen(word);
1816
}
1817
1818
// sort in decreasing order of score
1819
void SuggestMgr::bubblesort(char** rword, char** rword2, int* rsc, int n )
1820
{
1821
int m = 1;
1822
while (m < n) {
1823
int j = m;
1824
while (j > 0) {
1825
if (rsc[j-1] < rsc[j]) {
1826
int sctmp = rsc[j-1];
1827
char * wdtmp = rword[j-1];
1828
rsc[j-1] = rsc[j];
1829
rword[j-1] = rword[j];
1830
rsc[j] = sctmp;
1831
rword[j] = wdtmp;
1832
if (rword2) {
1833
wdtmp = rword2[j-1];
1834
rword2[j-1] = rword2[j];
1835
rword2[j] = wdtmp;
1836
}
1837
j--;
1838
} else break;
1839
}
1840
m++;
1841
}
1842
return;
1843
}
1844
1845
// longest common subsequence
1846
void SuggestMgr::lcs(const char * s, const char * s2, int * l1, int * l2, char ** result) {
1847
int n, m;
1848
w_char su[MAXSWL];
1849
w_char su2[MAXSWL];
1850
char * b;
1851
char * c;
1852
int i;
1853
int j;
1854
if (utf8) {
1855
m = u8_u16(su, MAXSWL, s);
1856
n = u8_u16(su2, MAXSWL, s2);
1857
} else {
1858
m = strlen(s);
1859
n = strlen(s2);
1860
}
1861
c = (char *) malloc((m + 1) * (n + 1));
1862
b = (char *) malloc((m + 1) * (n + 1));
1863
if (!c || !b) {
1864
if (c) free(c);
1865
if (b) free(b);
1866
*result = NULL;
1867
return;
1868
}
1869
for (i = 1; i <= m; i++) c[i*(n+1)] = 0;
1870
for (j = 0; j <= n; j++) c[j] = 0;
1871
for (i = 1; i <= m; i++) {
1872
for (j = 1; j <= n; j++) {
1873
if ( ((utf8) && (*((short *) su+i-1) == *((short *)su2+j-1)))
1874
|| ((!utf8) && ((*(s+i-1)) == (*(s2+j-1))))) {
1875
c[i*(n+1) + j] = c[(i-1)*(n+1) + j-1]+1;
1876
b[i*(n+1) + j] = LCS_UPLEFT;
1877
} else if (c[(i-1)*(n+1) + j] >= c[i*(n+1) + j-1]) {
1878
c[i*(n+1) + j] = c[(i-1)*(n+1) + j];
1879
b[i*(n+1) + j] = LCS_UP;
1880
} else {
1881
c[i*(n+1) + j] = c[i*(n+1) + j-1];
1882
b[i*(n+1) + j] = LCS_LEFT;
1883
}
1884
}
1885
}
1886
*result = b;
1887
free(c);
1888
*l1 = m;
1889
*l2 = n;
1890
}
1891
1892
int SuggestMgr::lcslen(const char * s, const char* s2) {
1893
int m;
1894
int n;
1895
int i;
1896
int j;
1897
char * result;
1898
int len = 0;
1899
lcs(s, s2, &m, &n, &result);
1900
if (!result) return 0;
1901
i = m;
1902
j = n;
1903
while ((i != 0) && (j != 0)) {
1904
if (result[i*(n+1) + j] == LCS_UPLEFT) {
1905
len++;
1906
i--;
1907
j--;
1908
} else if (result[i*(n+1) + j] == LCS_UP) {
1909
i--;
1910
} else j--;
1911
}
1912
free(result);
1913
return len;
1914
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1