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