Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Fix the fts5 bm25() function so that it matches the documentation. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | fts5 |
Files: | files | file ages | folders |
SHA1: |
1ac7a8d0af9a71ddf6a1421033dcb9fa |
User & Date: | dan 2014-12-23 19:18:34.426 |
Context
2014-12-29
| ||
11:24 | Fixes to built-in tokenizers. (check-in: b33fe0dd89 user: dan tags: fts5) | |
2014-12-23
| ||
19:18 | Fix the fts5 bm25() function so that it matches the documentation. (check-in: 1ac7a8d0af user: dan tags: fts5) | |
2014-12-22
| ||
21:01 | Fixes and simplifications for the snippet() and highlight() functions. (check-in: ca5d44042a user: dan tags: fts5) | |
Changes
Changes to ext/fts5/fts5.c.
︙ | ︙ | |||
1258 1259 1260 1261 1262 1263 1264 | Fts5Table *pTab = (Fts5Table*)(pCsr->base.pVtab); int rc = SQLITE_OK; if( CsrFlagTest(pCsr, FTS5CSR_REQUIRE_DOCSIZE) ){ i64 iRowid = fts5CursorRowid(pCsr); rc = sqlite3Fts5StorageDocsize(pTab->pStorage, iRowid, pCsr->aColumnSize); } | > > > > > > | > | 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 | Fts5Table *pTab = (Fts5Table*)(pCsr->base.pVtab); int rc = SQLITE_OK; if( CsrFlagTest(pCsr, FTS5CSR_REQUIRE_DOCSIZE) ){ i64 iRowid = fts5CursorRowid(pCsr); rc = sqlite3Fts5StorageDocsize(pTab->pStorage, iRowid, pCsr->aColumnSize); } if( iCol<0 ){ int i; *pnToken = 0; for(i=0; i<pTab->pConfig->nCol; i++){ *pnToken += pCsr->aColumnSize[i]; } }else if( iCol<pTab->pConfig->nCol ){ *pnToken = pCsr->aColumnSize[iCol]; }else{ *pnToken = 0; rc = SQLITE_RANGE; } return rc; } static int fts5ApiPoslist( Fts5Context *pCtx, int iPhrase, |
︙ | ︙ |
Changes to ext/fts5/fts5.h.
︙ | ︙ | |||
44 45 46 47 48 49 50 | /* ** EXTENSION API FUNCTIONS ** ** xUserData(pFts): ** Return a copy of the context pointer the extension function was ** registered with. ** | < > > > | | > > > > | 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | /* ** EXTENSION API FUNCTIONS ** ** xUserData(pFts): ** Return a copy of the context pointer the extension function was ** registered with. ** ** xColumnTotalSize(pFts, iCol, pnToken): ** If parameter iCol is less than zero, set output variable *pnToken ** to the total number of tokens in the FTS5 table. Or, if iCol is ** non-negative but less than the number of columns in the table, return ** the total number of tokens in column iCol, considering all rows in ** the FTS5 table. ** ** If parameter iCol is greater than or equal to the number of columns ** in the table, SQLITE_RANGE is returned. Or, if an error occurs (e.g. ** an OOM condition or IO error), an appropriate SQLite error code is ** returned. ** ** xColumnCount: ** Returns the number of columns in the FTS5 table. ** ** xColumnSize: ** Reports the size in tokens of a column value from the current row. ** |
︙ | ︙ |
Changes to ext/fts5/fts5_aux.c.
︙ | ︙ | |||
113 114 115 116 117 118 119 | /************************************************************************* ** Start of highlight() implementation. */ typedef struct HighlightContext HighlightContext; struct HighlightContext { CInstIter iter; /* Coalesced Instance Iterator */ | | | | 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 | /************************************************************************* ** Start of highlight() implementation. */ typedef struct HighlightContext HighlightContext; struct HighlightContext { CInstIter iter; /* Coalesced Instance Iterator */ int iRangeStart; /* First token to include */ int iRangeEnd; /* If non-zero, last token to include */ const char *zOpen; /* Opening highlight */ const char *zClose; /* Closing highlight */ const char *zIn; /* Input text */ int nIn; /* Size of input text in bytes */ int iOff; /* Current offset within zIn[] */ char *zOut; /* Output value */ }; |
︙ | ︙ | |||
160 161 162 163 164 165 166 | int iPos /* Position offset of token */ ){ HighlightContext *p = (HighlightContext*)pContext; int rc = SQLITE_OK; if( p->iRangeEnd>0 ){ if( iPos<p->iRangeStart || iPos>p->iRangeEnd ) return SQLITE_OK; | | | 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 | int iPos /* Position offset of token */ ){ HighlightContext *p = (HighlightContext*)pContext; int rc = SQLITE_OK; if( p->iRangeEnd>0 ){ if( iPos<p->iRangeStart || iPos>p->iRangeEnd ) return SQLITE_OK; if( p->iRangeStart && iPos==p->iRangeStart ) p->iOff = iStartOff; } if( iPos==p->iter.iStart ){ fts5HighlightAppend(&rc, p, &p->zIn[p->iOff], iStartOff - p->iOff); fts5HighlightAppend(&rc, p, p->zOpen, -1); p->iOff = iStartOff; } |
︙ | ︙ | |||
235 236 237 238 239 240 241 242 243 | sqlite3_result_text(pCtx, (const char*)ctx.zOut, -1, SQLITE_TRANSIENT); }else{ sqlite3_result_error_code(pCtx, rc); } sqlite3_free(ctx.zOut); } /* **************************************************************************/ | > | > > | < < > > | 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 | sqlite3_result_text(pCtx, (const char*)ctx.zOut, -1, SQLITE_TRANSIENT); }else{ sqlite3_result_error_code(pCtx, rc); } sqlite3_free(ctx.zOut); } /* ** End of highlight() implementation. **************************************************************************/ /* ** Implementation of snippet() function. */ static void fts5SnippetFunction( const Fts5ExtensionApi *pApi, /* API offered by current FTS version */ Fts5Context *pFts, /* First arg to pass to pApi functions */ sqlite3_context *pCtx, /* Context for returning result/error */ int nVal, /* Number of values in apVal[] array */ sqlite3_value **apVal /* Array of trailing arguments */ ){ HighlightContext ctx; int rc = SQLITE_OK; /* Return code */ int iCol; /* 1st argument to snippet() */ const char *zEllips; /* 4th argument to snippet() */ int nToken; /* 5th argument to snippet() */ int nInst; /* Number of instance matches this row */ int i; /* Used to iterate through instances */ int nPhrase; /* Number of phrases in query */ unsigned char *aSeen; /* Array of "seen instance" flags */ int iBestCol; /* Column containing best snippet */ int iBestStart = 0; /* First token of best snippet */ int iBestLast; /* Last token of best snippet */ int nBestScore = 0; /* Score of best snippet */ int nColSize; /* Total size of iBestCol in tokens */ if( nVal!=5 ){ const char *zErr = "wrong number of arguments to function snippet()"; sqlite3_result_error(pCtx, zErr, -1); return; } memset(&ctx, 0, sizeof(HighlightContext)); iCol = sqlite3_value_int(apVal[0]); rc = pApi->xColumnText(pFts, iCol, &ctx.zIn, &ctx.nIn); ctx.zOpen = (const char*)sqlite3_value_text(apVal[1]); ctx.zClose = (const char*)sqlite3_value_text(apVal[2]); zEllips = (const char*)sqlite3_value_text(apVal[3]); nToken = sqlite3_value_int(apVal[4]); iBestLast = nToken-1; iBestCol = (iCol>=0 ? iCol : 0); nPhrase = pApi->xPhraseCount(pFts); aSeen = sqlite3_malloc(nPhrase); if( aSeen==0 ){ rc = SQLITE_NOMEM; } |
︙ | ︙ | |||
359 360 361 362 363 364 365 | } sqlite3_free(ctx.zOut); sqlite3_free(aSeen); } /************************************************************************/ | < > | < > | | | | > | > | | < < < < | < < < < < < < | | | < | < < < < < < < < < < | | | < < < < < < < < < | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | > < | > > | > | > | < | < < < | | | < | > | | | < | | | | < < < | | < < < < | | < < < | < | | > | < > | < < | < < | < < < < < < < | < < < < < < < < < < < < < < < < | < < < < < < < < | < < < < < < < < < | | | > | > > > > > > | < < < < | | > | > | < | | < < > > | < < < < < < < < | > | | < < | | < < | > > | > | < | < < | | | > | < < < | | < < < < < < < | 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 | } sqlite3_free(ctx.zOut); sqlite3_free(aSeen); } /************************************************************************/ /* ** The first time the bm25() function is called for a query, an instance ** of the following structure is allocated and populated. */ typedef struct Fts5Bm25Data Fts5Bm25Data; struct Fts5Bm25Data { int nPhrase; /* Number of phrases in query */ double avgdl; /* Average number of tokens in each row */ double *aIDF; /* IDF for each phrase */ double *aFreq; /* Array used to calculate phrase freq. */ }; /* ** Callback used by fts5Bm25GetData() to count the number of rows in the ** table matched by each individual phrase within the query. */ static int fts5CountCb( const Fts5ExtensionApi *pApi, Fts5Context *pFts, void *pUserData /* Pointer to sqlite3_int64 variable */ ){ sqlite3_int64 *pn = (sqlite3_int64*)pUserData; (*pn)++; return SQLITE_OK; } /* ** Set *ppData to point to the Fts5Bm25Data object for the current query. ** If the object has not already been allocated, allocate and populate it ** now. */ static int fts5Bm25GetData( const Fts5ExtensionApi *pApi, Fts5Context *pFts, Fts5Bm25Data **ppData /* OUT: bm25-data object for this query */ ){ int rc = SQLITE_OK; /* Return code */ Fts5Bm25Data *p; /* Object to return */ p = pApi->xGetAuxdata(pFts, 0); if( p==0 ){ int nPhrase; /* Number of phrases in query */ sqlite3_int64 nRow; /* Number of rows in table */ sqlite3_int64 nToken; /* Number of tokens in table */ int nByte; /* Bytes of space to allocate */ int i; /* Allocate the Fts5Bm25Data object */ nPhrase = pApi->xPhraseCount(pFts); nByte = sizeof(Fts5Bm25Data) + nPhrase*2*sizeof(double); p = (Fts5Bm25Data*)sqlite3_malloc(nByte); if( p==0 ){ rc = SQLITE_NOMEM; }else{ memset(p, 0, nByte); p->nPhrase = nPhrase; p->aIDF = (double*)&p[1]; p->aFreq = &p->aIDF[nPhrase]; } /* Calculate the average document length for this FTS5 table */ if( rc==SQLITE_OK ) rc = pApi->xRowCount(pFts, &nRow); if( rc==SQLITE_OK ) rc = pApi->xColumnTotalSize(pFts, -1, &nToken); if( rc==SQLITE_OK ) p->avgdl = (double)nToken / (double)nRow; /* Calculate an IDF for each phrase in the query */ for(i=0; rc==SQLITE_OK && i<nPhrase; i++){ sqlite3_int64 nHit = 0; rc = pApi->xQueryPhrase(pFts, i, (void*)&nHit, fts5CountCb); if( rc==SQLITE_OK ){ /* Calculate the IDF (Inverse Document Frequency) for phrase i. ** This is done using the standard BM25 formula as found on wikipedia: ** ** IDF = log( (N - nHit + 0.5) / (nHit + 0.5) ) ** ** where "N" is the total number of documents in the set and nHit ** is the number that contain at least one instance of the phrase ** under consideration. ** ** The problem with this is that if (N < 2*nHit), the IDF is ** negative. Which is undesirable. So the mimimum allowable IDF is ** (1e-6) - roughly the same as a term that appears in just over ** half of set of 5,000,000 documents. */ double idf = log( (nRow - nHit + 0.5) / (nHit + 0.5) ); if( idf<=0.0 ) idf = 1e-6; p->aIDF[i] = idf; } } if( rc!=SQLITE_OK ){ sqlite3_free(p); }else{ rc = pApi->xSetAuxdata(pFts, p, sqlite3_free); } if( rc!=SQLITE_OK ) p = 0; } *ppData = p; return rc; } /* ** Implementation of bm25() function. */ static void fts5Bm25Function( const Fts5ExtensionApi *pApi, /* API offered by current FTS version */ Fts5Context *pFts, /* First arg to pass to pApi functions */ sqlite3_context *pCtx, /* Context for returning result/error */ int nVal, /* Number of values in apVal[] array */ sqlite3_value **apVal /* Array of trailing arguments */ ){ const double k1 = 1.2; /* Constant "k1" from BM25 formula */ const double b = 0.75; /* Constant "b" from BM25 formula */ int rc = SQLITE_OK; /* Error code */ double score = 0.0; /* SQL function return value */ Fts5Bm25Data *pData; /* Values allocated/calculated once only */ int i; /* Iterator variable */ int nInst; /* Value returned by xInstCount() */ double D; /* Total number of tokens in row */ double *aFreq; /* Array of phrase freq. for current row */ /* Calculate the phrase frequency (symbol "f(qi,D)" in the documentation) ** for each phrase in the query for the current row. */ rc = fts5Bm25GetData(pApi, pFts, &pData); if( rc==SQLITE_OK ){ aFreq = pData->aFreq; memset(aFreq, 0, sizeof(double) * pData->nPhrase); rc = pApi->xInstCount(pFts, &nInst); } for(i=0; rc==SQLITE_OK && i<nInst; i++){ int ip; int ic; int io; rc = pApi->xInst(pFts, i, &ip, &ic, &io); if( rc==SQLITE_OK ){ double w = (nVal > ic) ? sqlite3_value_double(apVal[ic]) : 1.0; aFreq[ip] += w; } } /* Figure out the total size of the current row in tokens. */ if( rc==SQLITE_OK ){ int nTok; rc = pApi->xColumnSize(pFts, -1, &nTok); D = (double)nTok; } /* Determine the BM25 score for the current row. */ for(i=0; rc==SQLITE_OK && i<pData->nPhrase; i++){ score += pData->aIDF[i] * ( ( aFreq[i] * (k1 + 1.0) ) / ( aFreq[i] + k1 * (1 - b + b * D / pData->avgdl) ) ); } /* If no error has occurred, return the calculated score. Otherwise, ** throw an SQL exception. */ if( rc==SQLITE_OK ){ sqlite3_result_double(pCtx, score); }else{ sqlite3_result_error_code(pCtx, rc); } } int sqlite3Fts5AuxInit(fts5_api *pApi){ struct Builtin { const char *zFunc; /* Function name (nul-terminated) */ void *pUserData; /* User-data pointer */ fts5_extension_function xFunc;/* Callback function */ void (*xDestroy)(void*); /* Destructor function */ } aBuiltin [] = { { "snippet", 0, fts5SnippetFunction, 0 }, { "highlight", 0, fts5HighlightFunction, 0 }, { "bm25", 0, fts5Bm25Function, 0 }, }; int rc = SQLITE_OK; /* Return code */ int i; /* To iterate through builtin functions */ for(i=0; rc==SQLITE_OK && i<sizeof(aBuiltin)/sizeof(aBuiltin[0]); i++){ rc = pApi->xCreateFunction(pApi, aBuiltin[i].zFunc, aBuiltin[i].pUserData, |
︙ | ︙ |
Changes to ext/fts5/fts5_storage.c.
︙ | ︙ | |||
725 726 727 728 729 730 731 | } return rc; } int sqlite3Fts5StorageSize(Fts5Storage *p, int iCol, i64 *pnToken){ int rc = fts5StorageLoadTotals(p, 0); if( rc==SQLITE_OK ){ | > > > > > > > | > > > | 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 | } return rc; } int sqlite3Fts5StorageSize(Fts5Storage *p, int iCol, i64 *pnToken){ int rc = fts5StorageLoadTotals(p, 0); if( rc==SQLITE_OK ){ *pnToken = 0; if( iCol<0 ){ int i; for(i=0; i<p->pConfig->nCol; i++){ *pnToken += p->aTotalSize[i]; } }else if( iCol<p->pConfig->nCol ){ *pnToken = p->aTotalSize[iCol]; }else{ rc = SQLITE_RANGE; } } return rc; } int sqlite3Fts5StorageRowCount(Fts5Storage *p, i64 *pnRow){ int rc = fts5StorageLoadTotals(p, 0); if( rc==SQLITE_OK ){ |
︙ | ︙ |