third_party/sqlite/src/ext/fts2/fts2_porter.c

   1 /*
   2 ** 2006 September 30
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 ** Implementation of the full-text-search tokenizer that implements
  13 ** a Porter stemmer.
  14 */
  15
  16 /*
  17 ** The code in this file is only compiled if:
  18 **
  19 **     * The FTS2 module is being built as an extension
  20 **       (in which case SQLITE_CORE is not defined), or
  21 **
  22 **     * The FTS2 module is being built into the core of
  23 **       SQLite (in which case SQLITE_ENABLE_FTS2 is defined).
  24 */
  25 #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS2)
  26
  27
  28 #include <assert.h>
  29 #include <stdlib.h>
  30 #include <stdio.h>
  31 #include <string.h>
  32
  33 #include "fts2_tokenizer.h"
  34
  35 /*
  36 ** Class derived from sqlite3_tokenizer
  37 */
  38 typedef struct porter_tokenizer {
  39   sqlite3_tokenizer base;      /* Base class */
  40 } porter_tokenizer;
  41
  42 /*
  43 ** Class derived from sqlit3_tokenizer_cursor
  44 */
  45 typedef struct porter_tokenizer_cursor {
  46   sqlite3_tokenizer_cursor base;
  47   const char *zInput;          /* input we are tokenizing */
  48   int nInput;                  /* size of the input */
  49   int iOffset;                 /* current position in zInput */
  50   int iToken;                  /* index of next token to be returned */
  51   char *zToken;                /* storage for current token */
  52   int nAllocated;              /* space allocated to zToken buffer */
  53 } porter_tokenizer_cursor;
  54
  55
  56 /* Forward declaration */
  57 static const sqlite3_tokenizer_module porterTokenizerModule;
  58
  59
  60 /*
  61 ** Create a new tokenizer instance.
  62 */
  63 static int porterCreate(
  64   int argc, const char * const *argv,
  65   sqlite3_tokenizer **ppTokenizer
  66 ){
  67   porter_tokenizer *t;
  68   t = (porter_tokenizer *) sqlite3_malloc(sizeof(*t));
  69   if( t==NULL ) return SQLITE_NOMEM;
  70   memset(t, 0, sizeof(*t));
  71   *ppTokenizer = &t->base;
  72   return SQLITE_OK;
  73 }
  74
  75 /*
  76 ** Destroy a tokenizer
  77 */
  78 static int porterDestroy(sqlite3_tokenizer *pTokenizer){
  79   sqlite3_free(pTokenizer);
  80   return SQLITE_OK;
  81 }
  82
  83 /*
  84 ** Prepare to begin tokenizing a particular string.  The input
  85 ** string to be tokenized is zInput[0..nInput-1].  A cursor
  86 ** used to incrementally tokenize this string is returned in
  87 ** *ppCursor.
  88 */
  89 static int porterOpen(
  90   sqlite3_tokenizer *pTokenizer,         /* The tokenizer */
  91   const char *zInput, int nInput,        /* String to be tokenized */
  92   sqlite3_tokenizer_cursor **ppCursor    /* OUT: Tokenization cursor */
  93 ){
  94   porter_tokenizer_cursor *c;
  95
  96   c = (porter_tokenizer_cursor *) sqlite3_malloc(sizeof(*c));
  97   if( c==NULL ) return SQLITE_NOMEM;
  98
  99   c->zInput = zInput;
 100   if( zInput==0 ){
 101     c->nInput = 0;
 102   }else if( nInput<0 ){
 103     c->nInput = (int)strlen(zInput);
 104   }else{
 105     c->nInput = nInput;
 106   }
 107   c->iOffset = 0;                 /* start tokenizing at the beginning */
 108   c->iToken = 0;
 109   c->zToken = NULL;               /* no space allocated, yet. */
 110   c->nAllocated = 0;
 111
 112   *ppCursor = &c->base;
 113   return SQLITE_OK;
 114 }
 115
 116 /*
 117 ** Close a tokenization cursor previously opened by a call to
 118 ** porterOpen() above.
 119 */
 120 static int porterClose(sqlite3_tokenizer_cursor *pCursor){
 121   porter_tokenizer_cursor *c = (porter_tokenizer_cursor *) pCursor;
 122   sqlite3_free(c->zToken);
 123   sqlite3_free(c);
 124   return SQLITE_OK;
 125 }
 126 /*
 127 ** Vowel or consonant
 128 */
 129 static const char cType[] = {
 130    0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0,
 131    1, 1, 1, 2, 1
 132 };
 133
 134 /*
 135 ** isConsonant() and isVowel() determine if their first character in
 136 ** the string they point to is a consonant or a vowel, according
 137 ** to Porter ruls.
 138 **
 139 ** A consonate is any letter other than 'a', 'e', 'i', 'o', or 'u'.
 140 ** 'Y' is a consonant unless it follows another consonant,
 141 ** in which case it is a vowel.
 142 **
 143 ** In these routine, the letters are in reverse order.  So the 'y' rule
 144 ** is that 'y' is a consonant unless it is followed by another
 145 ** consonent.
 146 */
 147 static int isVowel(const char*);
 148 static int isConsonant(const char *z){
 149   int j;
 150   char x = *z;
 151   if( x==0 ) return 0;
 152   assert( x>='a' && x<='z' );
 153   j = cType[x-'a'];
 154   if( j<2 ) return j;
 155   return z[1]==0 || isVowel(z + 1);
 156 }
 157 static int isVowel(const char *z){
 158   int j;
 159   char x = *z;
 160   if( x==0 ) return 0;
 161   assert( x>='a' && x<='z' );
 162   j = cType[x-'a'];
 163   if( j<2 ) return 1-j;
 164   return isConsonant(z + 1);
 165 }
 166
 167 /*
 168 ** Let any sequence of one or more vowels be represented by V and let
 169 ** C be sequence of one or more consonants.  Then every word can be
 170 ** represented as:
 171 **
 172 **           [C] (VC){m} [V]
 173 **
 174 ** In prose:  A word is an optional consonant followed by zero or
 175 ** vowel-consonant pairs followed by an optional vowel.  "m" is the
 176 ** number of vowel consonant pairs.  This routine computes the value
 177 ** of m for the first i bytes of a word.
 178 **
 179 ** Return true if the m-value for z is 1 or more.  In other words,
 180 ** return true if z contains at least one vowel that is followed
 181 ** by a consonant.
 182 **
 183 ** In this routine z[] is in reverse order.  So we are really looking
 184 ** for an instance of of a consonant followed by a vowel.
 185 */
 186 static int m_gt_0(const char *z){
 187   while( isVowel(z) ){ z++; }
 188   if( *z==0 ) return 0;
 189   while( isConsonant(z) ){ z++; }
 190   return *z!=0;
 191 }
 192
 193 /* Like mgt0 above except we are looking for a value of m which is
 194 ** exactly 1
 195 */
 196 static int m_eq_1(const char *z){
 197   while( isVowel(z) ){ z++; }
 198   if( *z==0 ) return 0;
 199   while( isConsonant(z) ){ z++; }
 200   if( *z==0 ) return 0;
 201   while( isVowel(z) ){ z++; }
 202   if( *z==0 ) return 1;
 203   while( isConsonant(z) ){ z++; }
 204   return *z==0;
 205 }
 206
 207 /* Like mgt0 above except we are looking for a value of m>1 instead
 208 ** or m>0
 209 */
 210 static int m_gt_1(const char *z){
 211   while( isVowel(z) ){ z++; }
 212   if( *z==0 ) return 0;
 213   while( isConsonant(z) ){ z++; }
 214   if( *z==0 ) return 0;
 215   while( isVowel(z) ){ z++; }
 216   if( *z==0 ) return 0;
 217   while( isConsonant(z) ){ z++; }
 218   return *z!=0;
 219 }
 220
 221 /*
 222 ** Return TRUE if there is a vowel anywhere within z[0..n-1]
 223 */
 224 static int hasVowel(const char *z){
 225   while( isConsonant(z) ){ z++; }
 226   return *z!=0;
 227 }
 228
 229 /*
 230 ** Return TRUE if the word ends in a double consonant.
 231 **
 232 ** The text is reversed here. So we are really looking at
 233 ** the first two characters of z[].
 234 */
 235 static int doubleConsonant(const char *z){
 236   return isConsonant(z) && z[0]==z[1] && isConsonant(z+1);
 237 }
 238
 239 /*
 240 ** Return TRUE if the word ends with three letters which
 241 ** are consonant-vowel-consonent and where the final consonant
 242 ** is not 'w', 'x', or 'y'.
 243 **
 244 ** The word is reversed here.  So we are really checking the
 245 ** first three letters and the first one cannot be in [wxy].
 246 */
 247 static int star_oh(const char *z){
 248   return
 249     z[0]!=0 && isConsonant(z) &&
 250     z[0]!='w' && z[0]!='x' && z[0]!='y' &&
 251     z[1]!=0 && isVowel(z+1) &&
 252     z[2]!=0 && isConsonant(z+2);
 253 }
 254
 255 /*
 256 ** If the word ends with zFrom and xCond() is true for the stem
 257 ** of the word that preceeds the zFrom ending, then change the
 258 ** ending to zTo.
 259 **
 260 ** The input word *pz and zFrom are both in reverse order.  zTo
 261 ** is in normal order.
 262 **
 263 ** Return TRUE if zFrom matches.  Return FALSE if zFrom does not
 264 ** match.  Not that TRUE is returned even if xCond() fails and
 265 ** no substitution occurs.
 266 */
 267 static int stem(
 268   char **pz,             /* The word being stemmed (Reversed) */
 269   const char *zFrom,     /* If the ending matches this... (Reversed) */
 270   const char *zTo,       /* ... change the ending to this (not reversed) */
 271   int (*xCond)(const char*)   /* Condition that must be true */
 272 ){
 273   char *z = *pz;
 274   while( *zFrom && *zFrom==*z ){ z++; zFrom++; }
 275   if( *zFrom!=0 ) return 0;
 276   if( xCond && !xCond(z) ) return 1;
 277   while( *zTo ){
 278     *(--z) = *(zTo++);
 279   }
 280   *pz = z;
 281   return 1;
 282 }
 283
 284 /*
 285 ** This is the fallback stemmer used when the porter stemmer is
 286 ** inappropriate.  The input word is copied into the output with
 287 ** US-ASCII case folding.  If the input word is too long (more
 288 ** than 20 bytes if it contains no digits or more than 6 bytes if
 289 ** it contains digits) then word is truncated to 20 or 6 bytes
 290 ** by taking 10 or 3 bytes from the beginning and end.
 291 */
 292 static void copy_stemmer(const char *zIn, int nIn, char *zOut, int *pnOut){
 293   int i, mx, j;
 294   int hasDigit = 0;
 295   for(i=0; i<nIn; i++){
 296     int c = zIn[i];
 297     if( c>='A' && c<='Z' ){
 298       zOut[i] = c - 'A' + 'a';
 299     }else{
 300       if( c>='0' && c<='9' ) hasDigit = 1;
 301       zOut[i] = c;
 302     }
 303   }
 304   mx = hasDigit ? 3 : 10;
 305   if( nIn>mx*2 ){
 306     for(j=mx, i=nIn-mx; i<nIn; i++, j++){
 307       zOut[j] = zOut[i];
 308     }
 309     i = j;
 310   }
 311   zOut[i] = 0;
 312   *pnOut = i;
 313 }
 314
 315
 316 /*
 317 ** Stem the input word zIn[0..nIn-1].  Store the output in zOut.
 318 ** zOut is at least big enough to hold nIn bytes.  Write the actual
 319 ** size of the output word (exclusive of the '\0' terminator) into *pnOut.
 320 **
 321 ** Any upper-case characters in the US-ASCII character set ([A-Z])
 322 ** are converted to lower case.  Upper-case UTF characters are
 323 ** unchanged.
 324 **
 325 ** Words that are longer than about 20 bytes are stemmed by retaining
 326 ** a few bytes from the beginning and the end of the word.  If the
 327 ** word contains digits, 3 bytes are taken from the beginning and
 328 ** 3 bytes from the end.  For long words without digits, 10 bytes
 329 ** are taken from each end.  US-ASCII case folding still applies.
 330 **
 331 ** If the input word contains not digits but does characters not
 332 ** in [a-zA-Z] then no stemming is attempted and this routine just
 333 ** copies the input into the input into the output with US-ASCII
 334 ** case folding.
 335 **
 336 ** Stemming never increases the length of the word.  So there is
 337 ** no chance of overflowing the zOut buffer.
 338 */
 339 static void porter_stemmer(const char *zIn, int nIn, char *zOut, int *pnOut){
 340   int i, j, c;
 341   char zReverse[28];
 342   char *z, *z2;
 343   if( nIn<3 || nIn>=sizeof(zReverse)-7 ){
 344     /* The word is too big or too small for the porter stemmer.
 345     ** Fallback to the copy stemmer */
 346     copy_stemmer(zIn, nIn, zOut, pnOut);
 347     return;
 348   }
 349   for(i=0, j=sizeof(zReverse)-6; i<nIn; i++, j--){
 350     c = zIn[i];
 351     if( c>='A' && c<='Z' ){
 352       zReverse[j] = c + 'a' - 'A';
 353     }else if( c>='a' && c<='z' ){
 354       zReverse[j] = c;
 355     }else{
 356       /* The use of a character not in [a-zA-Z] means that we fallback
 357       ** to the copy stemmer */
 358       copy_stemmer(zIn, nIn, zOut, pnOut);
 359       return;
 360     }
 361   }
 362   memset(&zReverse[sizeof(zReverse)-5], 0, 5);
 363   z = &zReverse[j+1];
 364
 365
 366   /* Step 1a */
 367   if( z[0]=='s' ){
 368     if(
 369      !stem(&z, "sess", "ss", 0) &&
 370      !stem(&z, "sei", "i", 0)  &&
 371      !stem(&z, "ss", "ss", 0)
 372     ){
 373       z++;
 374     }
 375   }
 376
 377   /* Step 1b */
 378   z2 = z;
 379   if( stem(&z, "dee", "ee", m_gt_0) ){
 380     /* Do nothing.  The work was all in the test */
 381   }else if(
 382      (stem(&z, "gni", "", hasVowel) || stem(&z, "de", "", hasVowel))
 383       && z!=z2
 384   ){
 385      if( stem(&z, "ta", "ate", 0) ||
 386          stem(&z, "lb", "ble", 0) ||
 387          stem(&z, "zi", "ize", 0) ){
 388        /* Do nothing.  The work was all in the test */
 389      }else if( doubleConsonant(z) && (*z!='l' && *z!='s' && *z!='z') ){
 390        z++;
 391      }else if( m_eq_1(z) && star_oh(z) ){
 392        *(--z) = 'e';
 393      }
 394   }
 395
 396   /* Step 1c */
 397   if( z[0]=='y' && hasVowel(z+1) ){
 398     z[0] = 'i';
 399   }
 400
 401   /* Step 2 */
 402   switch( z[1] ){
 403    case 'a':
 404      stem(&z, "lanoita", "ate", m_gt_0) ||
 405      stem(&z, "lanoit", "tion", m_gt_0);
 406      break;
 407    case 'c':
 408      stem(&z, "icne", "ence", m_gt_0) ||
 409      stem(&z, "icna", "ance", m_gt_0);
 410      break;
 411    case 'e':
 412      stem(&z, "rezi", "ize", m_gt_0);
 413      break;
 414    case 'g':
 415      stem(&z, "igol", "log", m_gt_0);
 416      break;
 417    case 'l':
 418      stem(&z, "ilb", "ble", m_gt_0) ||
 419      stem(&z, "illa", "al", m_gt_0) ||
 420      stem(&z, "iltne", "ent", m_gt_0) ||
 421      stem(&z, "ile", "e", m_gt_0) ||
 422      stem(&z, "ilsuo", "ous", m_gt_0);
 423      break;
 424    case 'o':
 425      stem(&z, "noitazi", "ize", m_gt_0) ||
 426      stem(&z, "noita", "ate", m_gt_0) ||
 427      stem(&z, "rota", "ate", m_gt_0);
 428      break;
 429    case 's':
 430      stem(&z, "msila", "al", m_gt_0) ||
 431      stem(&z, "ssenevi", "ive", m_gt_0) ||
 432      stem(&z, "ssenluf", "ful", m_gt_0) ||
 433      stem(&z, "ssensuo", "ous", m_gt_0);
 434      break;
 435    case 't':
 436      stem(&z, "itila", "al", m_gt_0) ||
 437      stem(&z, "itivi", "ive", m_gt_0) ||
 438      stem(&z, "itilib", "ble", m_gt_0);
 439      break;
 440   }
 441
 442   /* Step 3 */
 443   switch( z[0] ){
 444    case 'e':
 445      stem(&z, "etaci", "ic", m_gt_0) ||
 446      stem(&z, "evita", "", m_gt_0)   ||
 447      stem(&z, "ezila", "al", m_gt_0);
 448      break;
 449    case 'i':
 450      stem(&z, "itici", "ic", m_gt_0);
 451      break;
 452    case 'l':
 453      stem(&z, "laci", "ic", m_gt_0) ||
 454      stem(&z, "luf", "", m_gt_0);
 455      break;
 456    case 's':
 457      stem(&z, "ssen", "", m_gt_0);
 458      break;
 459   }
 460
 461   /* Step 4 */
 462   switch( z[1] ){
 463    case 'a':
 464      if( z[0]=='l' && m_gt_1(z+2) ){
 465        z += 2;
 466      }
 467      break;
 468    case 'c':
 469      if( z[0]=='e' && z[2]=='n' && (z[3]=='a' || z[3]=='e')  && m_gt_1(z+4)  ){
 470        z += 4;
 471      }
 472      break;
 473    case 'e':
 474      if( z[0]=='r' && m_gt_1(z+2) ){
 475        z += 2;
 476      }
 477      break;
 478    case 'i':
 479      if( z[0]=='c' && m_gt_1(z+2) ){
 480        z += 2;
 481      }
 482      break;
 483    case 'l':
 484      if( z[0]=='e' && z[2]=='b' && (z[3]=='a' || z[3]=='i') && m_gt_1(z+4) ){
 485        z += 4;
 486      }
 487      break;
 488    case 'n':
 489      if( z[0]=='t' ){
 490        if( z[2]=='a' ){
 491          if( m_gt_1(z+3) ){
 492            z += 3;
 493          }
 494        }else if( z[2]=='e' ){
 495          stem(&z, "tneme", "", m_gt_1) ||
 496          stem(&z, "tnem", "", m_gt_1) ||
 497          stem(&z, "tne", "", m_gt_1);
 498        }
 499      }
 500      break;
 501    case 'o':
 502      if( z[0]=='u' ){
 503        if( m_gt_1(z+2) ){
 504          z += 2;
 505        }
 506      }else if( z[3]=='s' || z[3]=='t' ){
 507        stem(&z, "noi", "", m_gt_1);
 508      }
 509      break;
 510    case 's':
 511      if( z[0]=='m' && z[2]=='i' && m_gt_1(z+3) ){
 512        z += 3;
 513      }
 514      break;
 515    case 't':
 516      stem(&z, "eta", "", m_gt_1) ||
 517      stem(&z, "iti", "", m_gt_1);
 518      break;
 519    case 'u':
 520      if( z[0]=='s' && z[2]=='o' && m_gt_1(z+3) ){
 521        z += 3;
 522      }
 523      break;
 524    case 'v':
 525    case 'z':
 526      if( z[0]=='e' && z[2]=='i' && m_gt_1(z+3) ){
 527        z += 3;
 528      }
 529      break;
 530   }
 531
 532   /* Step 5a */
 533   if( z[0]=='e' ){
 534     if( m_gt_1(z+1) ){
 535       z++;
 536     }else if( m_eq_1(z+1) && !star_oh(z+1) ){
 537       z++;
 538     }
 539   }
 540
 541   /* Step 5b */
 542   if( m_gt_1(z) && z[0]=='l' && z[1]=='l' ){
 543     z++;
 544   }
 545
 546   /* z[] is now the stemmed word in reverse order.  Flip it back
 547   ** around into forward order and return.
 548   */
 549   *pnOut = i = strlen(z);
 550   zOut[i] = 0;
 551   while( *z ){
 552     zOut[--i] = *(z++);
 553   }
 554 }
 555
 556 /*
 557 ** Characters that can be part of a token.  We assume any character
 558 ** whose value is greater than 0x80 (any UTF character) can be
 559 ** part of a token.  In other words, delimiters all must have
 560 ** values of 0x7f or lower.
 561 */
 562 static const char porterIdChar[] = {
 563 /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */
 564     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,  /* 3x */
 565     0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 4x */
 566     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1,  /* 5x */
 567     0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 6x */
 568     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,  /* 7x */
 569 };
 570 #define isDelim(C) (((ch=C)&0x80)==0 && (ch<0x30 || !porterIdChar[ch-0x30]))
 571
 572 /*
 573 ** Extract the next token from a tokenization cursor.  The cursor must
 574 ** have been opened by a prior call to porterOpen().
 575 */
 576 static int porterNext(
 577   sqlite3_tokenizer_cursor *pCursor,  /* Cursor returned by porterOpen */
 578   const char **pzToken,               /* OUT: *pzToken is the token text */
 579   int *pnBytes,                       /* OUT: Number of bytes in token */
 580   int *piStartOffset,                 /* OUT: Starting offset of token */
 581   int *piEndOffset,                   /* OUT: Ending offset of token */
 582   int *piPosition                     /* OUT: Position integer of token */
 583 ){
 584   porter_tokenizer_cursor *c = (porter_tokenizer_cursor *) pCursor;
 585   const char *z = c->zInput;
 586
 587   while( c->iOffset<c->nInput ){
 588     int iStartOffset, ch;
 589
 590     /* Scan past delimiter characters */
 591     while( c->iOffset<c->nInput && isDelim(z[c->iOffset]) ){
 592       c->iOffset++;
 593     }
 594
 595     /* Count non-delimiter characters. */
 596     iStartOffset = c->iOffset;
 597     while( c->iOffset<c->nInput && !isDelim(z[c->iOffset]) ){
 598       c->iOffset++;
 599     }
 600
 601     if( c->iOffset>iStartOffset ){
 602       int n = c->iOffset-iStartOffset;
 603       if( n>c->nAllocated ){
 604         c->nAllocated = n+20;
 605         c->zToken = sqlite3_realloc(c->zToken, c->nAllocated);
 606         if( c->zToken==NULL ) return SQLITE_NOMEM;
 607       }
 608       porter_stemmer(&z[iStartOffset], n, c->zToken, pnBytes);
 609       *pzToken = c->zToken;
 610       *piStartOffset = iStartOffset;
 611       *piEndOffset = c->iOffset;
 612       *piPosition = c->iToken++;
 613       return SQLITE_OK;
 614     }
 615   }
 616   return SQLITE_DONE;
 617 }
 618
 619 /*
 620 ** The set of routines that implement the porter-stemmer tokenizer
 621 */
 622 static const sqlite3_tokenizer_module porterTokenizerModule = {
 623   0,
 624   porterCreate,
 625   porterDestroy,
 626   porterOpen,
 627   porterClose,
 628   porterNext,
 629 };
 630
 631 /*
 632 ** Allocate a new porter tokenizer.  Return a pointer to the new
 633 ** tokenizer in *ppModule
 634 */
 635 void sqlite3Fts2PorterTokenizerModule(
 636   sqlite3_tokenizer_module const**ppModule
 637 ){
 638   *ppModule = &porterTokenizerModule;
 639 }
 640
 641 #endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS2) */