40
41
42
43
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
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
|
40
41
42
43
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
-
+
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
-
+
-
-
+
+
-
-
+
-
-
-
-
-
+
-
-
+
-
-
-
-
+
-
-
-
-
-
-
+
-
-
-
+
+
-
-
-
-
-
-
-
-
+
-
-
-
-
+
+
+
+
+
-
-
+
+
+
-
-
-
-
-
+
-
-
-
-
+
-
-
-
-
-
-
+
+
+
+
-
-
-
-
-
-
-
-
-
+
-
-
-
+
-
-
+
-
-
+
+
-
+
+
+
+
-
-
+
+
-
-
-
-
-
-
-
+
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
-
-
-
+
+
+
+
+
-
|
static int fts5SimpleDestroy(sqlite4_tokenizer *p){
return SQLITE4_OK;
}
typedef struct Fts5RankCtx Fts5RankCtx;
struct Fts5RankCtx {
sqlite4 *db;
double *aAvgdl; /* Average document size of each field */
double avgdl; /* Average document size in tokens */
int nPhrase; /* Number of phrases in query */
double *aIdf; /* IDF weights for each phrase in query */
};
static void fts5RankFreeCtx(void *pCtx){
if( pCtx ){
Fts5RankCtx *p = (Fts5RankCtx *)pCtx;
sqlite4DbFree(p->db, p);
}
}
#define BM25_EXPLAIN 0x01
#define BM25_FCOLUMNS 0x02
#define BM25_FSTREAMS 0x04
static int fts5GetSizeFreqScale(
sqlite4_context *pCtx,
int nArg, sqlite4_value **apArg,/* Function arguments */
int bm25mask, /* bm25 configuration mask */
int iPhrase, /* Phrase number */
int iField, /* Field number */
int *pnSize, /* OUT: Size of field in tokens */
int *pnFreq, /* OUT: Occurences of phrase in field */
double *pdScale /* OUT: Scale to use with this field */
){
int rc;
double scale = 1.0;
int nSize = 0;
int nFreq = 0;
if( bm25mask & BM25_FCOLUMNS ){
rc = sqlite4_mi_match_count(pCtx, iField, -1, iPhrase, &nFreq);
if( rc==SQLITE4_OK ) rc = sqlite4_mi_size(pCtx, iField, -1, &nSize);
if( nArg>iField ) scale = sqlite4_value_double(apArg[iField]);
}else if( bm25mask & BM25_FSTREAMS ){
rc = sqlite4_mi_match_count(pCtx, -1, iField, iPhrase, &nFreq);
if( rc==SQLITE4_OK ) rc = sqlite4_mi_size(pCtx, -1, iField, &nSize);
if( nArg>iField ) scale = sqlite4_value_double(apArg[iField]);
}else{
rc = sqlite4_mi_match_count(pCtx, -1, -1, iPhrase, &nFreq);
if( rc==SQLITE4_OK ) rc = sqlite4_mi_size(pCtx, -1, -1, &nSize);
}
*pnSize = nSize;
*pnFreq = nFreq;
*pdScale = scale;
return rc;
}
** A BM25(F) based ranking function for fts5.
** A BM25 based ranking function for fts5.
**
** This is based on the information in the Robertson/Zaragoza paper
** referenced above. As there is no way to provide relevance feedback
** IDF weights (equation 3.3 in R/Z) are used instead of RSJ for each phrase.
** The rest of the implementation is as presented in equations 3.19-21.
** The rest of the implementation is as presented in equation 3.15.
**
** R and Z observe that the experimental evidence suggests that reasonable
** values for free parameters "b" and "k1" are often in the ranges
** (0.5 < b < 0.8) and (1.2 < k1 < 2), although the optimal values depend
** on the nature of both the documents and queries. The implementation
** below sets each parameter to the midpoint of the suggested range.
*/
static void fts5Rank(sqlite4_context *pCtx, int nArg, sqlite4_value **apArg){
const double b = 0.65;
const double k1 = 1.6;
sqlite4 *db = sqlite4_context_db_handle(pCtx);
int rc = SQLITE4_OK; /* Error code */
Fts5RankCtx *p; /* Structure to store reusable values */
int i; /* Used to iterate through phrases */
double rank = 0.0; /* UDF return value */
int bExplain; /* True to run in explain mode */
char *zExplain = 0; /* String to return in explain mode */
int bExplain = 0;
char *zExplain = 0;
int nField = 1; /* Number of fields in collection */
int bm25mask = SQLITE4_PTR_TO_INT(sqlite4_user_data(pCtx));
if( sqlite4_user_data(pCtx) ) bExplain = 1;
bExplain = (bm25mask & BM25_EXPLAIN);
if( bm25mask & BM25_FCOLUMNS ) sqlite4_mi_column_count(pCtx, &nField);
if( bm25mask & BM25_FSTREAMS ) sqlite4_mi_stream_count(pCtx, &nField);
nByte = sizeof(Fts5RankCtx) + (nPhrase+nField) * sizeof(double);
nByte = sizeof(Fts5RankCtx) + nPhrase * sizeof(double);
p = (Fts5RankCtx *)sqlite4DbMallocZero(db, nByte);
sqlite4_set_auxdata(pCtx, 0, (void *)p, fts5RankFreeCtx);
p = sqlite4_get_auxdata(pCtx, 0);
if( !p ){
rc = SQLITE4_NOMEM;
}else{
int N; /* Total number of docs in collection */
int ni; /* Number of docs with phrase i */
p->db = db;
p->nPhrase = nPhrase;
p->aIdf = (double *)&p[1];
p->aAvgdl = &p->aIdf[nPhrase];
/* Determine the average document length. For bm25f, determine the
/* Determine the average document length */
** average length of each field. */
int iField;
for(iField=0; iField<nField; iField++){
int nTotal;
if( bm25mask & BM25_FCOLUMNS ){
rc = sqlite4_mi_total_size(pCtx, iField, -1, &nTotal);
}else if( bm25mask & BM25_FSTREAMS ){
rc = sqlite4_mi_total_size(pCtx, -1, iField, &nTotal);
}else{
rc = sqlite4_mi_total_size(pCtx, -1, -1, &nTotal);
}
if( rc==SQLITE4_OK ){
p->aAvgdl[iField] = (double)nTotal / (double)N;
}
if( bExplain ){
int iField;
zExplain = sqlite4MAppendf(
db, zExplain, "%s<table><tr><th>Stream<th>Scale<th>avgsl<th>sl",
zExplain
);
for(i=0; i<p->nPhrase; i++){
zExplain = sqlite4MAppendf(
db, zExplain, "%s<th>tf</span><sub>%d</sub>", zExplain, i
);
}
for(iField=0; rc==SQLITE4_OK && iField<nField; iField++){
int dl, tf;
double scale;
rc = fts5GetSizeFreqScale(
pCtx, nArg, apArg, bm25mask, 0, iField, &dl, &tf, &scale
);
zExplain = sqlite4MAppendf(
db, zExplain, "%s<tr><td>%d<td>%.2f<td>%.2f<td>%d",
zExplain, iField, scale, p->aAvgdl[iField], dl
);
for(i=0; rc==SQLITE4_OK && i<p->nPhrase; i++){
rc = fts5GetSizeFreqScale(
pCtx, nArg, apArg, bm25mask, i, iField, &dl, &tf, &scale
);
zExplain = sqlite4MAppendf(db, zExplain, "%s<td>%d", zExplain, tf);
}
}
zExplain = sqlite4MAppendf(
db, zExplain, "%s</table><table><tr><th>Phrase<th>IDF", zExplain
);
for(i=0; i<nField; i++){
zExplain = sqlite4MAppendf(
db, zExplain, "%s<th><span style=text-decoration:overline>"
"tf</span><sub>s%d</sub>", zExplain, i
);
}
zExplain = sqlite4MAppendf(db, zExplain, "%s<th>rank", zExplain);
}
for(i=0; rc==SQLITE4_OK && i<p->nPhrase; i++){
int iField;
double tfns = 0.0; /* Sum of tfn for all fields */
double prank; /* Contribution to rank of this phrase */
db, zExplain, "%s<tr><td>%d<td>%.2f", zExplain, i, p->aIdf[i]
db, zExplain, "%s(idf=%.2f L=%.2f tf=%d) rank=%.2f", zExplain,
p->aIdf[i], L, tf, prank
);
if( (i+1)<p->nPhrase ){
zExplain = sqlite4MAppendf(db, zExplain, "%s<br>", zExplain);
}
}
}
for(iField = 0; iField<nField; iField++){
double scale = 1.0;
int tf; /* Count of phrase i in row (term freq.) */
double tfn; /* Normalized term frequency */
int dl; /* Tokens in this row (document length) */
double B; /* B from formula 3.20 */
/* Set variable tf to the total number of occurrences of phrase iPhrase
** in this row/field. And dl to the number of tokens in the current
** row/field. */
rc = fts5GetSizeFreqScale(
pCtx, nArg, apArg, bm25mask, i, iField, &dl, &tf, &scale
);
B = (1.0 - b) + b * (double)dl / p->aAvgdl[iField]; /* 3.20 */
tfn = scale * (double)tf / B;
tfns += tfn; /* 3.19 */
if( bExplain ){
zExplain = sqlite4MAppendf(db, zExplain, "%s<td>%.2f", zExplain, tfn);
}
}
prank = p->aIdf[i] * tfns / (k1 + tfns); /* 3.21 */
if( bExplain ){
zExplain = sqlite4MAppendf(db, zExplain, "%s<td>%.2f", zExplain, prank);
}
/* Add it to the overall rank */
rank += prank;
}
zExplain = sqlite4MAppendf(
db, zExplain, "%s</table><b>overall rank=%.2f</b>", zExplain, rank
);
zExplain = sqlite4MAppendf(
db, zExplain, "%s<br>total=%.2f", zExplain, rank
);
}
sqlite4_result_text(pCtx, zExplain, -1, SQLITE4_TRANSIENT);
sqlite4DbFree(db, zExplain);
}else{
sqlite4_result_double(pCtx, rank);
}
}else{
sqlite4_result_error_code(pCtx, rc);
}
sqlite4DbFree(db, zExplain);
|
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
|
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
|
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
-
-
-
-
-
+
+
+
-
-
-
-
-
+
+
+
+
+
+
+
+
|
sqlite4_free(pEnv, aBuf);
return SQLITE4_OK;
}
int sqlite4InitFts5Func(sqlite4 *db){
int rc;
int i;
struct RankFunction {
const char *zName;
int mask;
} aRank[] = {
{ "rank", 0 },
{ "erank", BM25_EXPLAIN },
{ "rankc", BM25_FCOLUMNS },
{ "erankc", BM25_FCOLUMNS|BM25_EXPLAIN },
{ "ranks", BM25_FSTREAMS },
{ "eranks", BM25_FSTREAMS|BM25_EXPLAIN }
};
if( rc==SQLITE4_OK ){
if( rc!=SQLITE4_OK ) return rc;
rc = sqlite4_create_mi_function(
db, "snippet", -1, SQLITE4_UTF8, 0, fts5Snippet, 0);
}
for(i=0; rc==SQLITE4_OK && i<ArraySize(aRank); i++){
void *p = SQLITE4_INT_TO_PTR(aRank[i].mask);
const char *z = aRank[i].zName;
rc = sqlite4_create_mi_function(db, z, -1, SQLITE4_UTF8, p, fts5Rank, 0);
}
|