← Back to branch summary

~vcs-imports/mammoth-replicator/trunk

« back to all changes in this revision

Viewing changes to contrib/tsearch/dict/porter_english.dct

  • Committer: alvherre
  • Date: 2005-12-16 21:24:52 UTC
  • Revision ID: svn-v4:db760fc0-0f08-0410-9d63-cc6633f64896:trunk:1
Initial import of the REL8_0_3 sources from the Pgsql CVS repository.

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/tsearch/dict/porter_english.dct
 
1
/*
 
2
 * ----START-LICENCE----
 
3
 * Copyright 1999,2000 BrightStation PLC
 
4
 *
 
5
 * This program is free software; you can redistribute it and/or
 
6
 * modify it under the terms of the GNU General Public License as
 
7
 * published by the Free Software Foundation; either version 2 of the
 
8
 * License, or (at your option) any later version.
 
9
 *
 
10
 * This program is distributed in the hope that it will be useful,
 
11
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
 * GNU General Public License for more details.
 
14
 *
 
15
 * You should have received a copy of the GNU General Public License
 
16
 * along with this program; if not, write to the Free Software
 
17
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 
18
 * USA
 
19
 * -----END-LICENCE-----
 
20
 */
 
21
/* Version 1: see http://open.muscat.com/ for further information */
 
22
 
 
23
 
 
24
#ifdef DICT_BODY
 
25
#include <ctype.h> /* tolower */
 
26
 
 
27
static void * setup_english_stemmer(void);
 
28
 
 
29
static const char * english_stem(void * z, const char * q, int i0, int i1);
 
30
 
 
31
static void closedown_english_stemmer(void * z);
 
32
 
 
33
 
 
34
/* To set up the english stemming process:
 
35
 
 
36
       void * z = setup_stemmer();
 
37
 
 
38
   to use it:
 
39
 
 
40
       char * p = stem(z, q, i0, i1);
 
41
 
 
42
   The word to be stemmed is in byte address q offsets i0 to i1
 
43
   inclusive (i.e. from q[i0] to q[i1]). The stemmed result is the
 
44
   C string at address p.
 
45
 
 
46
   To close down the stemming process:
 
47
 
 
48
   closedown_stemmer(z);
 
49
 
 
50
*/
 
51
 
 
52
/* The English stemming algorithm is essentially the Porter stemming
 
53
 * algorithm, and has been coded up by its author. It follows the algorithm
 
54
 * presented in
 
55
 *
 
56
 * Porter, 1980, An algorithm for suffix stripping, Program, Vol. 14,
 
57
 * no. 3, pp 130-137,
 
58
 *
 
59
 * only differing from it at the points marked -DEPARTURE- and -NEW-
 
60
 * below.
 
61
 *
 
62
 * For a more faithful version of the Porter algorithm, see
 
63
 *
 
64
 *     http://www.muscat.com/~martin/stem.html
 
65
 *
 
66
 */
 
67
 
 
68
/* Later additions:
 
69
 
 
70
   June 2000
 
71
 
 
72
   The 'l' of the 'logi' -> 'log' rule is put with the stem, so that
 
73
   short stems like 'geo' 'theo' etc work like 'archaeo' 'philo' etc.
 
74
 
 
75
   This follows a suggestion of Barry Wilkins, reasearch student at
 
76
   Birmingham.
 
77
 
 
78
 
 
79
   February 2000
 
80
 
 
81
   the cvc test for not dropping final -e now looks after vc at the
 
82
   beginning of a word, so are, eve, ice, ore, use keep final -e. In this
 
83
   test c is any consonant, including w, x and y. This extension was
 
84
   suggested by Chris Emerson.
 
85
 
 
86
   -fully    -> -ful   treated like  -fulness -> -ful, and
 
87
   -tionally -> -tion  treated like  -tional  -> -tion
 
88
 
 
89
   both in Step 2. These were suggested by Hiranmay Ghosh, of New Delhi.
 
90
 
 
91
   Invariants proceed, succeed, exceed. Also suggested by Hiranmay Ghosh.
 
92
 
 
93
*/
 
94
 
 
95
#include <stdio.h>
 
96
#include <stdlib.h>
 
97
#include <string.h>
 
98
 
 
99
struct pool {
 
100
 
 
101
    int size;
 
102
    struct pool_entry * entries;
 
103
 
 
104
};
 
105
 
 
106
/*  This is used as a library to resolve exceptions in the various
 
107
    stemming algorithms. Typical use is,
 
108
 
 
109
        struct pool * p = create_pool(t);
 
110
        char * s_translated = search_pool(p, strlen(s), s);
 
111
        ...
 
112
        free_pool(p);
 
113
 
 
114
    t is an array of strings, e.g.
 
115
 
 
116
        static char * t[] = {
 
117
 
 
118
            "sky",     "sky/skies/",
 
119
            "die",     "dying/",
 
120
            "lie",     "lying/",
 
121
            "tie",     "tying/",
 
122
            ....
 
123
            0, 0
 
124
 
 
125
        };
 
126
 
 
127
    if s is "sky", "skies", "dying" etc., translated_s is becomes "sky",
 
128
    "sky", "die" etc.
 
129
 
 
130
    The code includes a sort/merge capability which may be turned into
 
131
    (or replaced by) something more general later on.
 
132
 
 
133
*/
 
134
 
 
135
/*  merge(n, p, q, r, l, k, f) repeatedly merges n-byte sequences of items of
 
136
    size k from addresses p and q into r. f is the comparison routine and
 
137
    l is the limit point for q.
 
138
*/
 
139
 
 
140
static void merge(int n, char * p, char * q, char * r, char * l, int k,
 
141
                  int (*f)(char *, char *))
 
142
{  char * q0 = q;
 
143
   if (q0 > l) { memmove(r, p, l-p); return; }
 
144
   while (p < q0)
 
145
   {  char * pl = n+p;
 
146
      char * ql = n+q;
 
147
      if (ql > l) ql = l;
 
148
      while(true)
 
149
      {  if (p >= pl) { memmove(r, q, ql-q); r += ql-q; q = ql; break; }
 
150
         if (q >= ql) { memmove(r, p, pl-p); r += pl-p; p = pl; break; }
 
151
         if (f(p, q)) { memmove(r, p, k); p += k; }
 
152
                else { memmove(r, q, k); q += k; }
 
153
         r += k;
 
154
      }
 
155
   }
 
156
   memmove(r, q, l-q);
 
157
}
 
158
 
 
159
/*  In sort(p, c, k, f), p+c is a byte address at which begin a sequence of
 
160
    items of size k to be sorted. p+l is the address of the byte after the
 
161
    last of these items, so l - c is divisible by k. f is a comparison function
 
162
    for a pair of these items: f(p+i, q+j) is true if the item at p+i is before
 
163
    the item at q+j, false if it is equal to or after it.
 
164
*/
 
165
 
 
166
static void sort(char * p, int c, int l, int k,
 
167
                 int (*f)(char *, char *))
 
168
{
 
169
    char * q = malloc(l-c);  /* temporary work space */
 
170
    int j = k;
 
171
    int w = l-c;
 
172
    while (j < w)
 
173
    {   int cycle;
 
174
        for (cycle = 1; cycle <= 2; cycle++)
 
175
        {   int h = (w+j-1) / j / 2 * j;     /* half way */
 
176
            if (cycle == 1) merge(j, p+c, p+c+h, q, p+l, k, f);
 
177
                       else merge(j, q, q+h, p+c, q+w, k, f);
 
178
            j *= 2;
 
179
        }
 
180
    }
 
181
    free(q);
 
182
}
 
183
 
 
184
struct pool_entry {
 
185
 
 
186
    const char * translation;
 
187
    const char * pointer;
 
188
    int length;
 
189
 
 
190
};
 
191
 
 
192
static void print_entry(struct pool_entry * p)
 
193
    {
 
194
       { int j; for (j=0;j<p->length;j++) fprintf(stderr, "%c", (p->pointer)[j]); }
 
195
       fprintf(stderr, " --> %s\n", p->translation);
 
196
    }
 
197
 
 
198
/*  - debugging aid
 
199
    static void print_pool(struct pool * p)
 
200
    {   int i;
 
201
        int size = p->size;
 
202
        struct pool_entry * q = p->entries;
 
203
        fprintf(stderr, "\nPool:\n");
 
204
        for (i = 0; i < size; i++) print_entry(q+i);
 
205
    }
 
206
*/
 
207
 
 
208
/* compare(p, q) is our comparison function, used for f above
 
209
*/
 
210
 
 
211
static int compare(char * char_p, char * char_q)
 
212
{   struct pool_entry * p = (struct pool_entry *) char_p;
 
213
    struct pool_entry * q = (struct pool_entry *) char_q;
 
214
    if (p->length == q->length) return memcmp(p->pointer, q->pointer, p->length) < 0;
 
215
    return p->length < q->length;
 
216
}
 
217
 
 
218
static int count_slashes(const char * s[])
 
219
{   int slash_count = 0;
 
220
    int i;
 
221
    for (i = 1; s[i] != 0; i += 2)
 
222
    {   const char * p = s[i];
 
223
        int j = 0;
 
224
        while (p[j] != 0) if (p[j++] == '/') slash_count++;
 
225
    }
 
226
    return slash_count;
 
227
}
 
228
 
 
229
static struct pool * create_pool(const char * s[])
 
230
{   int size = count_slashes(s);
 
231
    struct pool_entry * z = (struct pool_entry *) malloc(size * sizeof(struct pool_entry));
 
232
    struct pool_entry * q = z;
 
233
    int i;
 
234
    for (i = 1; s[i] != 0; i += 2)
 
235
    {   const char * p = s[i];
 
236
        int j = 0;
 
237
        int j0 = 0;
 
238
        while(true)
 
239
        {   if (p[j] == 0)
 
240
            {  if (j0 != j) { fprintf(stderr, "%s lacks final '/'\n", p); exit(1); }
 
241
               break;
 
242
            }
 
243
            if (p[j] == '/')
 
244
            {
 
245
                q->translation = s[i-1];
 
246
                q->pointer = p+j0; q->length = j-j0;
 
247
                q++;
 
248
                j0 = j+1;
 
249
            }
 
250
            j++;
 
251
        }
 
252
    }
 
253
    sort((char *) z, 0, size * sizeof(struct pool_entry), sizeof(struct pool_entry), compare);
 
254
 
 
255
    /* now validate the contents */
 
256
 
 
257
    for (i = 1; i < size; i++)
 
258
    {   struct pool_entry * p = z+i;
 
259
        struct pool_entry * q = z+i-1;
 
260
        if (p->length == q->length && memcmp(p->pointer, q->pointer, p->length) == 0)
 
261
        {   fprintf(stderr, "warning: "); print_entry(p);
 
262
            fprintf(stderr, " and "); print_entry(q);
 
263
        }
 
264
    }
 
265
 
 
266
    {   struct pool * p = (struct pool *) malloc(sizeof(struct pool));
 
267
        p->entries = z;
 
268
        p->size = size;
 
269
        return p;
 
270
    }
 
271
}
 
272
 
 
273
static int compare_to_pool(int length, const char * s, int length_p, const char * s_p)
 
274
{   if (length != length_p) return length-length_p;
 
275
    return memcmp(s, s_p, length);
 
276
}
 
277
 
 
278
static const char * search_pool(struct pool * p, int length, char * s)
 
279
{   int i = 0;
 
280
    int j = p->size;
 
281
    struct pool_entry * q = p->entries;
 
282
    if (j == 0) return 0;  /* empty pool */
 
283
    if (compare_to_pool(length, s, q->length, q->pointer) < 0) return 0;
 
284
    while(true)
 
285
    {
 
286
        int h = (i+j)/2;
 
287
        int diff = compare_to_pool(length, s, (q+h)->length, (q+h)->pointer);
 
288
        if (diff == 0) return (q+h)->translation;
 
289
        if (j-i <= 1) return 0;
 
290
        if (diff < 0) j = h; else i = h;
 
291
    }
 
292
}
 
293
 
 
294
static void free_pool(struct pool * p)
 
295
{   free(p->entries);
 
296
    free(p);
 
297
}
 
298
 
 
299
struct english_stemmer
 
300
{
 
301
    char * p;
 
302
    int p_size;
 
303
    int k;
 
304
    int j;
 
305
    struct pool * irregulars;
 
306
};
 
307
 
 
308
/* The main part of the stemming algorithm starts here. z->p is a buffer
 
309
   holding a word to be stemmed. The letters are in z->p[0], z->p[1] ...
 
310
   ending at z->p[z->k]. z->k is readjusted downwards as the stemming
 
311
   progresses. Zero termination is not in fact used in the algorithm.
 
312
 
 
313
   Note that only lower case sequences are stemmed. Forcing to lower case
 
314
   should be done before english_stem(...) is called.
 
315
 
 
316
   We will write p, k etc in place of z->p, z->k in the comments.
 
317
*/
 
318
 
 
319
/* cons(z, i) is true <=> p[i] is a consonant.
 
320
*/
 
321
 
 
322
static int cons(struct english_stemmer * z, int i)
 
323
{   switch (z->p[i])
 
324
    {   case 'a': case 'e': case 'i': case 'o': case 'u':
 
325
            return false;
 
326
        case 'y':
 
327
            return (i==0) ? true : !cons(z, i - 1);
 
328
        default: return true;
 
329
    }
 
330
}
 
331
 
 
332
/* m(z) measures the number of consonant sequences between 0 and j. if c is
 
333
   a consonant sequence and v a vowel sequence, and <..> indicates arbitrary
 
334
   presence,
 
335
 
 
336
      <c><v>       gives 0
 
337
      <c>vc<v>     gives 1
 
338
      <c>vcvc<v>   gives 2
 
339
      <c>vcvcvc<v> gives 3
 
340
      ....
 
341
*/
 
342
 
 
343
static int m(struct english_stemmer * z)
 
344
{   int n = 0;
 
345
    int i = 0;
 
346
    while(true)
 
347
    {   if (i > z->j) return n;
 
348
        if (! cons(z, i)) break; i++;
 
349
    }
 
350
    i++;
 
351
    while(true)
 
352
    {   while(true)
 
353
        {   if (i > z->j) return n;
 
354
            if (cons(z, i)) break;
 
355
            i++;
 
356
        }
 
357
        i++;
 
358
        n++;
 
359
        while(true)
 
360
        {   if (i > z->j) return n;
 
361
            if (! cons(z, i)) break;
 
362
            i++;
 
363
        }
 
364
        i++;
 
365
    }
 
366
}
 
367
 
 
368
/* vowelinstem(z) is true p[0], ... p[j] contains a vowel
 
369
*/
 
370
 
 
371
static int vowelinstem(struct english_stemmer * z)
 
372
{   int i;
 
373
    for (i = 0; i <= z->j; i++) if (! cons(z, i)) return true;
 
374
    return false;
 
375
}
 
376
 
 
377
/* doublec(z, i) is true <=> p[i], p[i - 1] contain a double consonant.
 
378
*/
 
379
 
 
380
static int doublec(struct english_stemmer * z, int i)
 
381
{   if (i < 1) return false;
 
382
    if (z->p[i] != z->p[i - 1]) return false;
 
383
    return cons(z, i);
 
384
}
 
385
 
 
386
/* cvc(z, i) is true <=>
 
387
 
 
388
   a) ( -NEW- ) i == 1, and p[0] p[1] is vowel consonant, or
 
389
 
 
390
   b) p[i - 2], p[i - 1], p[i] has the form consonant -
 
391
      vowel - consonant and also if the second c is not w, x or y. this is used
 
392
      when trying to restore an e at the end of a short word. e.g.
 
393
 
 
394
         cav(e), lov(e), hop(e), crim(e), but
 
395
         snow, box, tray.
 
396
 
 
397
*/
 
398
 
 
399
static int cvc(struct english_stemmer * z, int i)
 
400
{
 
401
    if (i == 0) return false;   /* i == 0 never happens perhaps */
 
402
 
 
403
    if (i == 1) return !cons(z, 0) && cons(z, 1);
 
404
 
 
405
    if (!cons(z, i) || cons(z, i - 1) || !cons(z, i - 2)) return false;
 
406
    {   int ch = z->p[i];
 
407
        if (ch == 'w' || ch == 'x' || ch == 'y') return false;
 
408
    }
 
409
    return true;
 
410
}
 
411
 
 
412
/* ends(z, s, length) is true <=> p[0], ... p[k] ends with the string s.
 
413
*/
 
414
 
 
415
static int ends(struct english_stemmer * z, const char * s, int length)
 
416
{
 
417
    if (length > z->k + 1) return false;
 
418
    if (memcmp(z->p + z->k - length + 1, s, length) != 0) return false;
 
419
    z->j = z->k - length;
 
420
    return true;
 
421
}
 
422
 
 
423
/* setto(z, s, length) sets p[j + 1] ... to the characters in the string s,
 
424
   readjusting k.
 
425
*/
 
426
 
 
427
static void setto(struct english_stemmer * z, const char * s, int length)
 
428
{
 
429
    memmove(z->p + z->j + 1, s, length);
 
430
    z->k = z->j + length;
 
431
}
 
432
 
 
433
/* r(z, s, length) is used further down. */
 
434
 
 
435
static void r(struct english_stemmer * z, const char * s, int length)
 
436
{
 
437
    if (m(z) > 0) setto(z, s, length);
 
438
}
 
439
 
 
440
/* step_1ab(z) gets rid of plurals and -ed or -ing. e.g.
 
441
 
 
442
       caresses  ->  caress
 
443
       ponies    ->  poni
 
444
       sties     ->  sti
 
445
       tie       ->  tie       (-NEW-: see below)
 
446
       caress    ->  caress
 
447
       cats      ->  cat
 
448
 
 
449
       feed      ->  feed
 
450
       agreed    ->  agree
 
451
       disabled  ->  disable
 
452
 
 
453
       matting   ->  mat
 
454
       mating    ->  mate
 
455
       meeting   ->  meet
 
456
       milling   ->  mill
 
457
       messing   ->  mess
 
458
 
 
459
       meetings  ->  meet
 
460
 
 
461
*/
 
462
 
 
463
static void step_1ab(struct english_stemmer * z)
 
464
{   if (z->p[z->k] == 's')
 
465
    {   if (ends(z, "sses", 4)) z->k -= 2; else
 
466
        if (ends(z, "ies", 3))
 
467
            if (z->j == 0) z->k--; else z->k -= 2;
 
468
 
 
469
        /* this line extends the original algorithm, so that 'flies'->'fli' but
 
470
           'dies'->'die' etc */
 
471
 
 
472
        else
 
473
            if (z->p[z->k - 1] != 's') z->k--;
 
474
    }
 
475
 
 
476
    if (ends(z, "ied", 3)) { if (z->j == 0) z->k--; else z->k -= 2; } else
 
477
 
 
478
    /* this line extends the original algorithm, so that 'spied'->'spi' but
 
479
       'died'->'die' etc */
 
480
 
 
481
    if (ends(z, "eed", 3)) { if (m(z) > 0) z->k--; } else
 
482
    if ((ends(z, "ed", 2) || ends(z, "ing", 3)) && vowelinstem(z))
 
483
    {   z->k = z->j;
 
484
        if (ends(z, "at", 2)) setto(z, "ate", 3); else
 
485
        if (ends(z, "bl", 2)) setto(z, "ble", 3); else
 
486
        if (ends(z, "iz", 2)) setto(z, "ize", 3); else
 
487
        if (doublec(z, z->k))
 
488
        {   z->k--;
 
489
            {   int ch = z->p[z->k];
 
490
                if (ch == 'l' || ch == 's' || ch == 'z') z->k++;
 
491
            }
 
492
        }
 
493
        else if (m(z) == 1 && cvc(z, z->k)) setto(z, "e", 1);
 
494
    }
 
495
}
 
496
 
 
497
/* step_1c(z) turns terminal y to i when there is another vowel in the stem.
 
498
 
 
499
   -NEW-: This has been modified from the original Porter algorithm so that y->i
 
500
   is only done when y is preceded by a consonant, but not if the stem
 
501
   is only a single consonant, i.e.
 
502
 
 
503
       (*c and not c) Y -> I
 
504
 
 
505
   So 'happy' -> 'happi', but
 
506
      'enjoy' -> 'enjoy'  etc
 
507
 
 
508
   This is a much better rule. Formerly 'enjoy'->'enjoi' and 'enjoyment'->
 
509
   'enjoy'. Step 1c is perhaps done too soon; but with this modification that
 
510
   no longer really matters.
 
511
 
 
512
   Also, the removal of the vowelinstem(z) condition means that 'spy', 'fly',
 
513
   'try' ... stem to 'spi', 'fli', 'tri' and conflate with 'spied', 'tried',
 
514
   'flies' ...
 
515
 
 
516
*/
 
517
 
 
518
static void step_1c(struct english_stemmer * z)
 
519
{
 
520
    if (ends(z, "y", 1) && z->j > 0 && cons(z, z->k - 1)) z->p[z->k] = 'i';
 
521
}
 
522
 
 
523
 
 
524
/* step_2(z) maps double suffices to single ones. so -ization ( = -ize plus
 
525
   -ation) maps to -ize etc. Note that the string before the suffix must give
 
526
   m(z) > 0.
 
527
*/
 
528
 
 
529
static void step_2(struct english_stemmer * z)
 
530
{   switch (z->p[z->k - 1])
 
531
    {
 
532
        case 'a':
 
533
            if (ends(z, "ational", 7)) { r(z, "ate", 3); break; }
 
534
            if (ends(z, "tional", 6)) { r(z, "tion", 4); break; }
 
535
            break;
 
536
        case 'c':
 
537
            if (ends(z, "enci", 4)) { r(z, "ence", 4); break; }
 
538
            if (ends(z, "anci", 4)) { r(z, "ance", 4); break; }
 
539
            break;
 
540
        case 'e':
 
541
            if (ends(z, "izer", 4)) { r(z, "ize", 3); break; }
 
542
            break;
 
543
        case 'l':
 
544
            if (ends(z, "bli", 3)) { r(z, "ble", 3); break; } /*-DEPARTURE-*/
 
545
 
 
546
     /* To match the published algorithm, replace this line with
 
547
        case 'l':
 
548
            if (ends(z, "abli", 4)) { r(z, "able", 4); break; }
 
549
     */
 
550
            if (ends(z, "alli", 4))
 
551
            {
 
552
                if (m(z) > 0) { setto(z, "al", 2); step_2(z); } /*-NEW-*/
 
553
                break;
 
554
            }
 
555
 
 
556
            if (ends(z, "fulli", 5)) { r(z, "ful", 3); break; } /*-NEW-*/
 
557
            if (ends(z, "entli", 5)) { r(z, "ent", 3); break; }
 
558
            if (ends(z, "eli", 3)) { r(z, "e", 1); break; }
 
559
            if (ends(z, "ousli", 5)) { r(z, "ous", 3); break; }
 
560
            break;
 
561
        case 'o':
 
562
            if (ends(z, "ization", 7)) { r(z, "ize", 3); break; }
 
563
            if (ends(z, "ation", 5)) { r(z, "ate", 3); break; }
 
564
            if (ends(z, "ator", 4)) { r(z, "ate", 3); break; }
 
565
            break;
 
566
        case 's':
 
567
            if (ends(z, "alism", 5)) { r(z, "al", 2); break; }
 
568
            if (ends(z, "iveness", 7)) { r(z, "ive", 3); break; }
 
569
            if (ends(z, "fulness", 7)) { r(z, "ful", 3); break; }
 
570
            if (ends(z, "ousness", 7)) { r(z, "ous", 3); break; }
 
571
            break;
 
572
        case 't':
 
573
            if (ends(z, "aliti", 5)) { r(z, "al", 2); break; }
 
574
            if (ends(z, "iviti", 5)) { r(z, "ive", 3); break; }
 
575
            if (ends(z, "biliti", 6)) { r(z, "ble", 3); break; }
 
576
            break;
 
577
        case 'g':
 
578
            if (ends(z, "logi", 4))
 
579
            {   z->j++;                /*-NEW-*/ /*(Barry Wilkins)*/
 
580
                r(z, "og", 2); break;
 
581
            } /*-DEPARTURE-*/
 
582
 
 
583
     /* To match the published algorithm, delete this line */
 
584
 
 
585
    }
 
586
}
 
587
 
 
588
/* step_3(z) deals with -ic-, -full, -ness etc. Similar strategy to step_2.
 
589
*/
 
590
 
 
591
static void step_3(struct english_stemmer * z)
 
592
{   switch (z->p[z->k])
 
593
    {
 
594
        case 'e':
 
595
            if (ends(z, "icate", 5)) { r(z, "ic", 2); break; }
 
596
            if (ends(z, "ative", 5)) { r(z, "", 0); break; }
 
597
            if (ends(z, "alize", 5)) { r(z, "al", 2); break; }
 
598
            break;
 
599
        case 'i':
 
600
            if (ends(z, "iciti", 5)) { r(z, "ic", 2); break; }
 
601
            break;
 
602
        case 'l':
 
603
            if (ends(z, "ical", 4)) { r(z, "ic", 2); break; }
 
604
            if (ends(z, "ful", 3)) { r(z, "", 0); break; }
 
605
            break;
 
606
        case 's':
 
607
            if (ends(z, "ness", 4)) { r(z, "", 0); break; }
 
608
            break;
 
609
    }
 
610
}
 
611
 
 
612
/* step_4() takes off -ant, -ence etc., in context <c>vcvc<v>.
 
613
*/
 
614
 
 
615
static void step_4(struct english_stemmer * z)
 
616
{   switch (z->p[z->k - 1])
 
617
    {   case 'a':
 
618
            if (ends(z, "al", 2)) break; return;
 
619
        case 'c':
 
620
            if (ends(z, "ance", 4)) break;
 
621
            if (ends(z, "ence", 4)) break; return;
 
622
        case 'e':
 
623
            if (ends(z, "er", 2)) break; return;
 
624
        case 'i':
 
625
            if (ends(z, "ic", 2)) break; return;
 
626
        case 'l':
 
627
            if (ends(z, "able", 4)) break;
 
628
            if (ends(z, "ible", 4)) break; return;
 
629
        case 'n':
 
630
            if (ends(z, "ant", 3)) break;
 
631
            if (ends(z, "ement", 5)) break;
 
632
            if (ends(z, "ment", 4)) break;
 
633
            if (ends(z, "ent", 3)) break; return;
 
634
        case 'o':
 
635
            if (ends(z, "ion", 3) && (z->p[z->j] == 's' ||
 
636
                                    z->p[z->j] == 't')) break;
 
637
            if (ends(z, "ou", 2)) break; return;
 
638
            /* takes care of -ous */
 
639
        case 's':
 
640
            if (ends(z, "ism", 3)) break; return;
 
641
        case 't':
 
642
            if (ends(z, "ate", 3)) break;
 
643
            if (ends(z, "iti", 3)) break; return;
 
644
        case 'u':
 
645
            if (ends(z, "ous", 3)) break; return;
 
646
        case 'v':
 
647
            if (ends(z, "ive", 3)) break; return;
 
648
        case 'z':
 
649
            if (ends(z, "ize", 3)) break; return;
 
650
        default:
 
651
            return;
 
652
    }
 
653
    if (m(z) > 1) z->k = z->j;
 
654
}
 
655
 
 
656
/* step_5(z) removes a final -e if m(z) > 1, and changes -ll to -l if
 
657
   m(z) > 1.
 
658
*/
 
659
 
 
660
static void step_5(struct english_stemmer * z)
 
661
{   z->j = z->k;
 
662
    if (z->p[z->k] == 'e')
 
663
    {   int a = m(z);
 
664
        if (a > 1 || (a == 1 && !cvc(z, z->k - 1))) z->k--;
 
665
    }
 
666
    if (z->p[z->k] == 'l' && doublec(z, z->k) && m(z) > 1) z->k--;
 
667
}
 
668
 
 
669
static const char * english_stem(void * z_, const char * q, int i0, int i1)
 
670
{
 
671
    struct english_stemmer * z = (struct english_stemmer *) z_;
 
672
    int p_size = z->p_size;
 
673
 
 
674
    if (i1 - i0 + 50 > p_size)
 
675
    {   free(z->p);
 
676
        p_size = i1 - i0 + 75; /* ample */ z->p_size = p_size;
 
677
        z->p = (char *) malloc(p_size);
 
678
    }
 
679
 
 
680
    memmove(z->p, q + i0, i1 - i0 + 1);
 
681
 
 
682
    z->k = i1 - i0;
 
683
 
 
684
 
 
685
    {   const char * t = search_pool(z->irregulars, z->k + 1, z->p);
 
686
        if (t != 0)  {
 
687
                z->k = strlen(t) - 1;   
 
688
                return t;
 
689
        }
 
690
    }
 
691
 
 
692
    if (z->k > 1) /*-DEPARTURE-*/
 
693
 
 
694
   /* With this line, strings of length 1 or 2 don't go through the
 
695
      stemming process, although no mention is made of this in the
 
696
      published algorithm. Remove the line to match the published
 
697
      algorithm. */
 
698
 
 
699
    {   step_1ab(z); step_1c(z);
 
700
        step_2(z);
 
701
        step_3(z);
 
702
        step_4(z);
 
703
        step_5(z);
 
704
    }
 
705
 
 
706
    z->p[z->k + 1] = 0; /* C string form for now */
 
707
    return z->p;
 
708
}
 
709
 
 
710
/* -NEW-
 
711
   This is a table of irregular forms. It is quite short, but still
 
712
   reflects the errors actually drawn to Martin Porter's attention over
 
713
   a 20 year period!
 
714
 
 
715
   Extend it as necessary.
 
716
 
 
717
   The form of the table is:
 
718
 
 
719
     "p1" "s11/s12/s13/ ... /"
 
720
     "p2" "s21/s22/s23/ ... /"
 
721
     ...
 
722
     "pn" "sn1/sn2/sn3/ ... /"
 
723
     0, 0
 
724
 
 
725
   String sij is mapped to paradigm form pi, and the main stemming
 
726
   process is then bypassed.
 
727
*/
 
728
 
 
729
static const char * irregular_forms[] = {
 
730
 
 
731
    "sky",     "sky/skies/",
 
732
    "die",     "dying/",
 
733
    "lie",     "lying/",
 
734
    "tie",     "tying/",
 
735
    "news",    "news/",
 
736
    "inning",  "innings/inning/",
 
737
    "outing",  "outings/outing/",
 
738
    "canning", "cannings/canning/",
 
739
    "howe",    "howe/",
 
740
 
 
741
    /*-NEW-*/
 
742
    "proceed", "proceed/",
 
743
    "exceed",  "exceed/",
 
744
    "succeed", "succeed/",  /* Hiranmay Ghosh */
 
745
 
 
746
    0, 0  /* terminator */
 
747
 
 
748
};
 
749
 
 
750
 
 
751
/*
 
752
 * is_stopword part
 
753
 */
 
754
typedef struct {
 
755
        unsigned char   val;
 
756
        unsigned char   flag;
 
757
        unsigned char   right;
 
758
 
 
759
        unsigned char   child;
 
760
} ESWNODE;
 
761
 
 
762
/* is exists left tree ? */
 
763
#define L       0x01
 
764
/* finish word flag */
 
765
#define F       0x02
 
766
#define ISLEFT(x)       (((ESWNODE*)x)->flag & L)
 
767
#define ISFINISH(x)     (((ESWNODE*)x)->flag & F)
 
768
 
 
769
 
 
770
static ESWNODE engstoptree[] = {
 
771
        {'m',L,9,126},
 
772
        {'d',L,4,71},
 
773
        {'b',L,2,40},
 
774
        {'a',F,0,14},
 
775
        {'c',0,0,62},
 
776
        {'f',L,2,79},
 
777
        {'e',0,0,75},
 
778
        {'h',0,1,90},
 
779
        {'i',F,0,108},
 
780
        {'t',L,4,177},
 
781
        {'o',L,2,135},
 
782
        {'n',0,0,131},
 
783
        {'s',0,0,156},
 
784
        {'v',L,2,210},
 
785
        {'u',0,0,201},
 
786
        {'w',0,1,211},
 
787
        {'y',0,0,237},
 
788
 
 
789
        {'m',L|F,5,0},
 
790
        {'f',L,2,12},
 
791
        {'b',0,0,7},
 
792
        {'g',0,1,13},
 
793
        {'l',0,0,17},
 
794
        {'r',L,2,19},
 
795
        {'n',F,0,16},
 
796
        {'s',F,1,0},
 
797
        {'t',F,0,0},
 
798
 
 
799
        {'o',0,0,1},
 
800
 
 
801
        {'u',0,1,2},
 
802
        {'v',F,0,0},
 
803
 
 
804
        {'t',F,0,0},
 
805
 
 
806
        {'t',0,0,1},
 
807
 
 
808
        {'e',0,0,1},
 
809
 
 
810
        {'r',F,0,0},
 
811
 
 
812
        {'a',0,0,1},
 
813
 
 
814
        {'i',0,0,1},
 
815
 
 
816
        {'n',F,0,1},
 
817
 
 
818
        {'s',0,0,1},
 
819
 
 
820
        {'t',F,0,0},
 
821
 
 
822
        {'l',F,0,0},
 
823
 
 
824
        {'d',F,1,0},
 
825
        {'i',F,0,0},
 
826
 
 
827
        {'e',F,0,0},
 
828
 
 
829
        {'o',L,2,21},
 
830
        {'e',F,0,3},
 
831
        {'u',0,1,21},
 
832
        {'y',F,0,0},
 
833
 
 
834
        {'f',L,3,9},
 
835
        {'c',0,1,4},
 
836
        {'e',0,0,6},
 
837
        {'l',0,1,8},
 
838
        {'t',0,0,9},
 
839
 
 
840
        {'a',0,0,1},
 
841
 
 
842
        {'u',0,0,1},
 
843
 
 
844
        {'s',F,0,0},
 
845
 
 
846
        {'n',F,0,0},
 
847
 
 
848
        {'o',0,0,1},
 
849
 
 
850
        {'r',F,0,0},
 
851
 
 
852
        {'o',0,0,1},
 
853
 
 
854
        {'w',F,0,0},
 
855
 
 
856
        {'w',0,0,1},
 
857
 
 
858
        {'e',0,0,1},
 
859
 
 
860
        {'e',0,0,1},
 
861
 
 
862
        {'n',F,0,0},
 
863
 
 
864
        {'t',0,0,1},
 
865
 
 
866
        {'h',F,0,0},
 
867
 
 
868
        {'t',F,0,0},
 
869
 
 
870
        {'a',0,1,2},
 
871
        {'o',0,0,2},
 
872
 
 
873
        {'n',F,0,0},
 
874
 
 
875
        {'u',0,0,1},
 
876
 
 
877
        {'l',0,0,1},
 
878
 
 
879
        {'d',F,0,0},
 
880
 
 
881
        {'o',L|F,2,4},
 
882
        {'i',0,0,2},
 
883
        {'u',0,0,5},
 
884
 
 
885
        {'d',F,0,0},
 
886
 
 
887
        {'e',F,1,0},
 
888
        {'w',0,0,1},
 
889
 
 
890
        {'n',F,0,0},
 
891
 
 
892
        {'r',0,0,1},
 
893
 
 
894
        {'e',F,0,0},
 
895
 
 
896
        {'a',0,0,1},
 
897
 
 
898
        {'c',0,0,1},
 
899
 
 
900
        {'h',F,0,0},
 
901
 
 
902
        {'o',L,2,5},
 
903
        {'e',0,0,3},
 
904
        {'r',0,1,4},
 
905
        {'u',0,0,5},
 
906
 
 
907
        {'w',F,0,0},
 
908
 
 
909
        {'r',F,0,0},
 
910
 
 
911
        {'o',0,0,1},
 
912
 
 
913
        {'m',F,0,0},
 
914
 
 
915
        {'r',0,0,1},
 
916
 
 
917
        {'t',0,0,1},
 
918
 
 
919
        {'h',0,0,1},
 
920
 
 
921
        {'e',0,0,1},
 
922
 
 
923
        {'r',F,0,0},
 
924
 
 
925
        {'e',L|F,2,7},
 
926
        {'a',F,0,3},
 
927
        {'i',F,1,11},
 
928
        {'o',0,0,15},
 
929
 
 
930
        {'d',F,1,0},
 
931
        {'v',0,0,1},
 
932
 
 
933
        {'e',F,0,0},
 
934
 
 
935
        {'r',F,0,1},
 
936
 
 
937
        {'e',F,1,0},
 
938
        {'s',0,0,1},
 
939
 
 
940
        {'e',0,0,1},
 
941
 
 
942
        {'l',0,0,1},
 
943
 
 
944
        {'f',F,0,0},
 
945
 
 
946
        {'m',F,0,1},
 
947
 
 
948
        {'s',0,0,1},
 
949
 
 
950
        {'e',0,0,1},
 
951
 
 
952
        {'l',0,0,1},
 
953
 
 
954
        {'f',F,0,0},
 
955
 
 
956
        {'w',F,0,0},
 
957
 
 
958
        {'n',L|F,2,4},
 
959
        {'f',F,0,0},
 
960
        {'s',F,1,0},
 
961
        {'t',F,0,3},
 
962
 
 
963
        {'t',0,0,1},
 
964
 
 
965
        {'o',F,0,0},
 
966
 
 
967
        {'s',0,0,1},
 
968
 
 
969
        {'e',0,0,1},
 
970
 
 
971
        {'l',0,0,1},
 
972
 
 
973
        {'f',F,0,0},
 
974
 
 
975
        {'o',L,3,6},
 
976
        {'a',0,1,4},
 
977
        {'e',F,0,0},
 
978
        {'u',0,1,7},
 
979
        {'y',F,0,8},
 
980
 
 
981
        {'y',F,0,0},
 
982
 
 
983
        {'r',0,1,2},
 
984
        {'s',0,0,2},
 
985
 
 
986
        {'e',F,0,0},
 
987
 
 
988
        {'t',F,0,0},
 
989
 
 
990
        {'s',0,0,1},
 
991
 
 
992
        {'t',F,0,0},
 
993
 
 
994
        {'s',0,0,1},
 
995
 
 
996
        {'e',0,0,1},
 
997
 
 
998
        {'l',0,0,1},
 
999
 
 
1000
        {'f',F,0,0},
 
1001
 
 
1002
        {'o',F,0,1},
 
1003
 
 
1004
        {'r',F,1,0},
 
1005
        {'t',F,0,0},
 
1006
 
 
1007
        {'t',L,4,11},
 
1008
        {'n',L|F,2,7},
 
1009
        {'f',F,0,5},
 
1010
        {'r',F,0,0},
 
1011
        {'v',L,2,16},
 
1012
        {'u',0,0,9},
 
1013
        {'w',0,0,16},
 
1014
 
 
1015
        {'f',F,0,0},
 
1016
 
 
1017
        {'c',F,1,0},
 
1018
        {'l',0,0,1},
 
1019
 
 
1020
        {'i',F,0,0},
 
1021
 
 
1022
        {'h',0,0,1},
 
1023
 
 
1024
        {'e',0,0,1},
 
1025
 
 
1026
        {'r',F,0,0},
 
1027
 
 
1028
        {'r',F,1,2},
 
1029
        {'t',F,0,0},
 
1030
 
 
1031
        {'s',0,0,1},
 
1032
 
 
1033
        {'e',0,0,1},
 
1034
 
 
1035
        {'l',0,0,1},
 
1036
 
 
1037
        {'v',F,0,0},
 
1038
 
 
1039
        {'e',0,0,1},
 
1040
 
 
1041
        {'r',F,0,0},
 
1042
 
 
1043
        {'n',F,0,0},
 
1044
 
 
1045
        {'h',L,2,6},
 
1046
        {'a',0,0,3},
 
1047
        {'o',F,1,12},
 
1048
        {'u',0,0,13},
 
1049
 
 
1050
        {'m',0,0,1},
 
1051
 
 
1052
        {'e',F,0,0},
 
1053
 
 
1054
        {'e',L|F,2,0},
 
1055
        {'a',0,0,2},
 
1056
        {'o',0,0,3},
 
1057
 
 
1058
        {'l',0,0,1},
 
1059
 
 
1060
        {'l',F,0,0},
 
1061
 
 
1062
        {'u',0,0,1},
 
1063
 
 
1064
        {'l',0,0,1},
 
1065
 
 
1066
        {'d',F,0,0},
 
1067
 
 
1068
        {'m',0,0,1},
 
1069
 
 
1070
        {'e',F,0,0},
 
1071
 
 
1072
        {'c',0,0,1},
 
1073
 
 
1074
        {'h',F,0,0},
 
1075
 
 
1076
        {'h',0,1,2},
 
1077
        {'o',F,0,27},
 
1078
 
 
1079
        {'i',L|F,3,0},
 
1080
        {'a',0,1,4},
 
1081
        {'e',F,0,5},
 
1082
        {'o',0,1,17},
 
1083
        {'r',0,0,18},
 
1084
 
 
1085
        {'n',F,1,0},
 
1086
        {'t',F,0,0},
 
1087
 
 
1088
        {'n',L|F,3,0},
 
1089
        {'i',0,1,5},
 
1090
        {'m',F,0,5},
 
1091
        {'s',L,2,9},
 
1092
        {'r',0,0,7},
 
1093
        {'y',F,0,0},
 
1094
 
 
1095
        {'r',F,0,0},
 
1096
 
 
1097
        {'s',0,0,1},
 
1098
 
 
1099
        {'e',0,0,1},
 
1100
 
 
1101
        {'l',0,0,1},
 
1102
 
 
1103
        {'v',F,0,0},
 
1104
 
 
1105
        {'e',F,0,0},
 
1106
 
 
1107
        {'e',F,0,0},
 
1108
 
 
1109
        {'s',0,0,1},
 
1110
 
 
1111
        {'e',F,0,0},
 
1112
 
 
1113
        {'o',0,0,1},
 
1114
 
 
1115
        {'u',0,0,1},
 
1116
 
 
1117
        {'g',0,0,1},
 
1118
 
 
1119
        {'h',F,0,0},
 
1120
 
 
1121
        {'o',F,0,0},
 
1122
 
 
1123
        {'n',0,1,2},
 
1124
        {'p',F,0,0},
 
1125
 
 
1126
        {'d',0,1,2},
 
1127
        {'t',0,0,3},
 
1128
 
 
1129
        {'e',0,0,1},
 
1130
 
 
1131
        {'r',F,0,0},
 
1132
 
 
1133
        {'i',0,0,1},
 
1134
 
 
1135
        {'l',F,0,0},
 
1136
 
 
1137
        {'e',0,0,1},
 
1138
 
 
1139
        {'r',0,0,1},
 
1140
 
 
1141
        {'i',F,0,0},
 
1142
 
 
1143
        {'h',L,3,7},
 
1144
        {'a',F,1,0},
 
1145
        {'e',F,0,3},
 
1146
        {'i',0,1,17},
 
1147
        {'o',0,0,20},
 
1148
 
 
1149
        {'r',0,0,1},
 
1150
 
 
1151
        {'e',F,0,0},
 
1152
 
 
1153
        {'e',L,2,5},
 
1154
        {'a',0,0,3},
 
1155
        {'i',F,1,6},
 
1156
        {'o',F,0,9},
 
1157
 
 
1158
        {'t',F,0,0},
 
1159
 
 
1160
        {'n',F,1,0},
 
1161
        {'r',0,0,1},
 
1162
 
 
1163
        {'e',F,0,0},
 
1164
 
 
1165
        {'c',0,1,2},
 
1166
        {'l',0,0,2},
 
1167
 
 
1168
        {'h',F,0,0},
 
1169
 
 
1170
        {'e',F,0,0},
 
1171
 
 
1172
        {'m',F,0,0},
 
1173
 
 
1174
        {'l',0,1,2},
 
1175
        {'t',0,0,2},
 
1176
 
 
1177
        {'l',F,0,0},
 
1178
 
 
1179
        {'h',F,0,0},
 
1180
 
 
1181
        {'u',0,0,1},
 
1182
 
 
1183
        {'l',0,0,1},
 
1184
 
 
1185
        {'d',F,0,0},
 
1186
 
 
1187
        {'o',0,0,1},
 
1188
 
 
1189
        {'u',F,0,1},
 
1190
 
 
1191
        {'r',F,0,1},
 
1192
 
 
1193
        {'s',0,0,1},
 
1194
 
 
1195
        {'e',0,0,1},
 
1196
 
 
1197
        {'l',0,0,1},
 
1198
 
 
1199
        {'f',F,1,0},
 
1200
        {'v',F,0,0}
 
1201
};
 
1202
 
 
1203
static unsigned int
 
1204
find_english_stopword( unsigned char *buf, int len ) {
 
1205
        ESWNODE    *ptr = engstoptree;
 
1206
        int     result = 0;
 
1207
        unsigned char *cur = buf;
 
1208
 
 
1209
        while( cur - buf < len ) {
 
1210
                if ( ptr->val == *cur ) {
 
1211
                        cur++;
 
1212
                        if ( ISFINISH(ptr) ) result = cur - buf;
 
1213
                        if ( ! ptr->child ) break;
 
1214
                        ptr += ptr->child;
 
1215
                } else if ( ptr->val > *cur ) {
 
1216
                        if ( ISLEFT(ptr) )
 
1217
                                ptr++;
 
1218
                        else
 
1219
                                break;
 
1220
                } else {
 
1221
                        if ( ptr->right ) 
 
1222
                                ptr += ptr->right;
 
1223
                        else
 
1224
                                break;
 
1225
                }
 
1226
        }
 
1227
        return result;
 
1228
} 
 
1229
 
 
1230
#undef L
 
1231
#undef F
 
1232
#undef ISLEFT
 
1233
#undef ISFINISH
 
1234
 
 
1235
static int
 
1236
is_stopengword(void* obj,char* word,int len)
 
1237
{
 
1238
        return ( len == find_english_stopword((unsigned char*)word, len) ) ? 1 : 0;
 
1239
}
 
1240
 
 
1241
static void *
 
1242
setup_english_stemmer(void)
 
1243
{
 
1244
    struct english_stemmer * z = (struct english_stemmer *) malloc(sizeof(struct english_stemmer));
 
1245
    z->p = 0; z->p_size = 0;
 
1246
    z->irregulars = create_pool(irregular_forms);
 
1247
    return (void *) z;
 
1248
}
 
1249
 
 
1250
static void
 
1251
closedown_english_stemmer(void * z_)
 
1252
{
 
1253
    struct english_stemmer * z = (struct english_stemmer *) z_;
 
1254
    free_pool(z->irregulars);
 
1255
    free(z->p);
 
1256
    free(z);
 
1257
}
 
1258
 
 
1259
static char*
 
1260
engstemming(void* obj, char *word, int *len)
 
1261
{
 
1262
        struct english_stemmer * z = (struct english_stemmer *) obj;
 
1263
        const char* stemmed_word;
 
1264
        char *result = word;
 
1265
 
 
1266
        while(result-word < *len) {
 
1267
                *result = tolower((unsigned char) *result);
 
1268
                result++;
 
1269
        }
 
1270
        stemmed_word = english_stem(obj, word, 0, *len-1);
 
1271
        *len = z->k + 1;
 
1272
 
 
1273
        result = (char*)palloc( *len );
 
1274
        memcpy((void*)result, (void*)stemmed_word, *len);
 
1275
        return result;
 
1276
}
 
1277
#endif /* DICT_BODY */
 
1278
 
 
1279
#ifdef DICT_TABLE
 
1280
TABLE_DICT_START
 
1281
        "C",
 
1282
        setup_english_stemmer,
 
1283
        closedown_english_stemmer,
 
1284
        engstemming,
 
1285
        NULL,
 
1286
        is_stopengword
 
1287
TABLE_DICT_END
 
1288
#endif
 
1289