Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * tsrank.c
4 : * rank tsvector by tsquery
5 : *
6 : * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
7 : *
8 : *
9 : * IDENTIFICATION
10 : * src/backend/utils/adt/tsrank.c
11 : *
12 : *-------------------------------------------------------------------------
13 : */
14 : #include "postgres.h"
15 :
16 : #include <limits.h>
17 : #include <math.h>
18 :
19 : #include "miscadmin.h"
20 : #include "tsearch/ts_utils.h"
21 : #include "utils/array.h"
22 : #include "utils/builtins.h"
23 :
24 : static const float weights[] = {0.1f, 0.2f, 0.4f, 1.0f};
25 :
26 : #define wpos(wep) ( w[ WEP_GETWEIGHT(wep) ] )
27 :
28 : #define RANK_NO_NORM 0x00
29 : #define RANK_NORM_LOGLENGTH 0x01
30 : #define RANK_NORM_LENGTH 0x02
31 : #define RANK_NORM_EXTDIST 0x04
32 : #define RANK_NORM_UNIQ 0x08
33 : #define RANK_NORM_LOGUNIQ 0x10
34 : #define RANK_NORM_RDIVRPLUS1 0x20
35 : #define DEF_NORM_METHOD RANK_NO_NORM
36 :
37 : static float calc_rank_or(const float *w, TSVector t, TSQuery q);
38 : static float calc_rank_and(const float *w, TSVector t, TSQuery q);
39 :
40 : /*
41 : * Returns a weight of a word collocation
42 : */
43 : static float4
44 18 : word_distance(int32 w)
45 : {
46 18 : if (w > 100)
47 0 : return 1e-30f;
48 :
49 18 : return 1.0 / (1.005 + 0.05 * exp(((float4) w) / 1.5 - 2));
50 : }
51 :
52 : static int
53 0 : cnt_length(TSVector t)
54 : {
55 0 : WordEntry *ptr = ARRPTR(t),
56 0 : *end = (WordEntry *) STRPTR(t);
57 0 : int len = 0;
58 :
59 0 : while (ptr < end)
60 : {
61 0 : int clen = POSDATALEN(t, ptr);
62 :
63 0 : if (clen == 0)
64 0 : len += 1;
65 : else
66 0 : len += clen;
67 :
68 0 : ptr++;
69 : }
70 :
71 0 : return len;
72 : }
73 :
74 :
75 : #define WordECompareQueryItem(e,q,p,i,m) \
76 : tsCompareString((q) + (i)->distance, (i)->length, \
77 : (e) + (p)->pos, (p)->len, (m))
78 :
79 :
80 : /*
81 : * Returns a pointer to a WordEntry's array corresponding to 'item' from
82 : * tsvector 't'. 'q' is the TSQuery containing 'item'.
83 : * Returns NULL if not found.
84 : */
85 : static WordEntry *
86 426 : find_wordentry(TSVector t, TSQuery q, QueryOperand *item, int32 *nitem)
87 : {
88 426 : WordEntry *StopLow = ARRPTR(t);
89 426 : WordEntry *StopHigh = (WordEntry *) STRPTR(t);
90 426 : WordEntry *StopMiddle = StopHigh;
91 : int difference;
92 :
93 426 : *nitem = 0;
94 :
95 : /* Loop invariant: StopLow <= item < StopHigh */
96 1146 : while (StopLow < StopHigh)
97 : {
98 1098 : StopMiddle = StopLow + (StopHigh - StopLow) / 2;
99 1098 : difference = WordECompareQueryItem(STRPTR(t), GETOPERAND(q), StopMiddle, item, false);
100 1098 : if (difference == 0)
101 : {
102 378 : StopHigh = StopMiddle;
103 378 : *nitem = 1;
104 378 : break;
105 : }
106 720 : else if (difference > 0)
107 252 : StopLow = StopMiddle + 1;
108 : else
109 468 : StopHigh = StopMiddle;
110 : }
111 :
112 426 : if (item->prefix)
113 : {
114 54 : if (StopLow >= StopHigh)
115 54 : StopMiddle = StopHigh;
116 :
117 54 : *nitem = 0;
118 :
119 222 : while (StopMiddle < (WordEntry *) STRPTR(t) &&
120 84 : WordECompareQueryItem(STRPTR(t), GETOPERAND(q), StopMiddle, item, true) == 0)
121 : {
122 84 : (*nitem)++;
123 84 : StopMiddle++;
124 : }
125 : }
126 :
127 426 : return (*nitem > 0) ? StopHigh : NULL;
128 : }
129 :
130 :
131 : /*
132 : * sort QueryOperands by (length, word)
133 : */
134 : static int
135 108 : compareQueryOperand(const void *a, const void *b, void *arg)
136 : {
137 108 : char *operand = (char *) arg;
138 108 : QueryOperand *qa = (*(QueryOperand *const *) a);
139 108 : QueryOperand *qb = (*(QueryOperand *const *) b);
140 :
141 216 : return tsCompareString(operand + qa->distance, qa->length,
142 108 : operand + qb->distance, qb->length,
143 : false);
144 : }
145 :
146 : /*
147 : * Returns a sorted, de-duplicated array of QueryOperands in a query.
148 : * The returned QueryOperands are pointers to the original QueryOperands
149 : * in the query.
150 : *
151 : * Length of the returned array is stored in *size
152 : */
153 : static QueryOperand **
154 54 : SortAndUniqItems(TSQuery q, int *size)
155 : {
156 54 : char *operand = GETOPERAND(q);
157 54 : QueryItem *item = GETQUERY(q);
158 : QueryOperand **res,
159 : **ptr,
160 : **prevptr;
161 :
162 54 : ptr = res = (QueryOperand **) palloc(sizeof(QueryOperand *) * *size);
163 :
164 : /* Collect all operands from the tree to res */
165 216 : while ((*size)--)
166 : {
167 162 : if (item->type == QI_VAL)
168 : {
169 108 : *ptr = (QueryOperand *) item;
170 108 : ptr++;
171 : }
172 162 : item++;
173 : }
174 :
175 54 : *size = ptr - res;
176 54 : if (*size < 2)
177 0 : return res;
178 :
179 54 : qsort_arg(res, *size, sizeof(QueryOperand *), compareQueryOperand, operand);
180 :
181 54 : ptr = res + 1;
182 54 : prevptr = res;
183 :
184 : /* remove duplicates */
185 108 : while (ptr - res < *size)
186 : {
187 54 : if (compareQueryOperand((void *) ptr, (void *) prevptr, (void *) operand) != 0)
188 : {
189 54 : prevptr++;
190 54 : *prevptr = *ptr;
191 : }
192 54 : ptr++;
193 : }
194 :
195 54 : *size = prevptr + 1 - res;
196 54 : return res;
197 : }
198 :
199 : static float
200 18 : calc_rank_and(const float *w, TSVector t, TSQuery q)
201 : {
202 : WordEntryPosVector **pos;
203 : WordEntryPosVector1 posnull;
204 : WordEntryPosVector *POSNULL;
205 : int i,
206 : k,
207 : l,
208 : p;
209 : WordEntry *entry,
210 : *firstentry;
211 : WordEntryPos *post,
212 : *ct;
213 : int32 dimt,
214 : lenct,
215 : dist,
216 : nitem;
217 18 : float res = -1.0;
218 : QueryOperand **item;
219 18 : int size = q->size;
220 :
221 18 : item = SortAndUniqItems(q, &size);
222 18 : if (size < 2)
223 : {
224 0 : pfree(item);
225 0 : return calc_rank_or(w, t, q);
226 : }
227 18 : pos = (WordEntryPosVector **) palloc0(sizeof(WordEntryPosVector *) * q->size);
228 :
229 : /* A dummy WordEntryPos array to use when haspos is false */
230 18 : posnull.npos = 1;
231 18 : posnull.pos[0] = 0;
232 18 : WEP_SETPOS(posnull.pos[0], MAXENTRYPOS - 1);
233 18 : POSNULL = (WordEntryPosVector *) &posnull;
234 :
235 54 : for (i = 0; i < size; i++)
236 : {
237 36 : firstentry = entry = find_wordentry(t, q, item[i], &nitem);
238 36 : if (!entry)
239 0 : continue;
240 :
241 72 : while (entry - firstentry < nitem)
242 : {
243 36 : if (entry->haspos)
244 36 : pos[i] = _POSVECPTR(t, entry);
245 : else
246 0 : pos[i] = POSNULL;
247 :
248 36 : dimt = pos[i]->npos;
249 36 : post = pos[i]->pos;
250 54 : for (k = 0; k < i; k++)
251 : {
252 18 : if (!pos[k])
253 0 : continue;
254 18 : lenct = pos[k]->npos;
255 18 : ct = pos[k]->pos;
256 36 : for (l = 0; l < dimt; l++)
257 : {
258 36 : for (p = 0; p < lenct; p++)
259 : {
260 18 : dist = abs((int) WEP_GETPOS(post[l]) - (int) WEP_GETPOS(ct[p]));
261 18 : if (dist || (dist == 0 && (pos[i] == POSNULL || pos[k] == POSNULL)))
262 : {
263 : float curw;
264 :
265 18 : if (!dist)
266 0 : dist = MAXENTRYPOS;
267 18 : curw = sqrt(wpos(post[l]) * wpos(ct[p]) * word_distance(dist));
268 18 : res = (res < 0) ? curw : 1.0 - (1.0 - res) * (1.0 - curw);
269 : }
270 : }
271 : }
272 : }
273 :
274 36 : entry++;
275 : }
276 : }
277 18 : pfree(pos);
278 18 : pfree(item);
279 18 : return res;
280 : }
281 :
282 : static float
283 36 : calc_rank_or(const float *w, TSVector t, TSQuery q)
284 : {
285 : WordEntry *entry,
286 : *firstentry;
287 : WordEntryPosVector1 posnull;
288 : WordEntryPos *post;
289 : int32 dimt,
290 : j,
291 : i,
292 : nitem;
293 36 : float res = 0.0;
294 : QueryOperand **item;
295 36 : int size = q->size;
296 :
297 : /* A dummy WordEntryPos array to use when haspos is false */
298 36 : posnull.npos = 1;
299 36 : posnull.pos[0] = 0;
300 :
301 36 : item = SortAndUniqItems(q, &size);
302 :
303 108 : for (i = 0; i < size; i++)
304 : {
305 : float resj,
306 : wjm;
307 : int32 jm;
308 :
309 72 : firstentry = entry = find_wordentry(t, q, item[i], &nitem);
310 72 : if (!entry)
311 6 : continue;
312 :
313 132 : while (entry - firstentry < nitem)
314 : {
315 66 : if (entry->haspos)
316 : {
317 66 : dimt = POSDATALEN(t, entry);
318 66 : post = POSDATAPTR(t, entry);
319 : }
320 : else
321 : {
322 0 : dimt = posnull.npos;
323 0 : post = posnull.pos;
324 : }
325 :
326 66 : resj = 0.0;
327 66 : wjm = -1.0;
328 66 : jm = 0;
329 132 : for (j = 0; j < dimt; j++)
330 : {
331 66 : resj = resj + wpos(post[j]) / ((j + 1) * (j + 1));
332 66 : if (wpos(post[j]) > wjm)
333 : {
334 66 : wjm = wpos(post[j]);
335 66 : jm = j;
336 : }
337 : }
338 : /*
339 : limit (sum(1/i^2),i=1,inf) = pi^2/6
340 : resj = sum(wi/i^2),i=1,noccurrence,
341 : wi - should be sorted desc,
342 : don't sort for now, just choose maximum weight. This should be corrected
343 : Oleg Bartunov
344 : */
345 66 : res = res + (wjm + resj - wjm / ((jm + 1) * (jm + 1))) / 1.64493406685;
346 :
347 66 : entry++;
348 : }
349 : }
350 36 : if (size > 0)
351 36 : res = res / size;
352 36 : pfree(item);
353 36 : return res;
354 : }
355 :
356 : static float
357 54 : calc_rank(const float *w, TSVector t, TSQuery q, int32 method)
358 : {
359 54 : QueryItem *item = GETQUERY(q);
360 54 : float res = 0.0;
361 : int len;
362 :
363 54 : if (!t->size || !q->size)
364 0 : return 0.0;
365 :
366 : /* XXX: What about NOT? */
367 54 : res = (item->type == QI_OPR && (item->qoperator.oper == OP_AND ||
368 36 : item->qoperator.oper == OP_PHRASE)) ?
369 72 : calc_rank_and(w, t, q) :
370 36 : calc_rank_or(w, t, q);
371 :
372 54 : if (res < 0)
373 0 : res = 1e-20f;
374 :
375 54 : if ((method & RANK_NORM_LOGLENGTH) && t->size > 0)
376 0 : res /= log((double) (cnt_length(t) + 1)) / log(2.0);
377 :
378 54 : if (method & RANK_NORM_LENGTH)
379 : {
380 0 : len = cnt_length(t);
381 0 : if (len > 0)
382 0 : res /= (float) len;
383 : }
384 :
385 : /* RANK_NORM_EXTDIST not applicable */
386 :
387 54 : if ((method & RANK_NORM_UNIQ) && t->size > 0)
388 0 : res /= (float) (t->size);
389 :
390 54 : if ((method & RANK_NORM_LOGUNIQ) && t->size > 0)
391 0 : res /= log((double) (t->size + 1)) / log(2.0);
392 :
393 54 : if (method & RANK_NORM_RDIVRPLUS1)
394 0 : res /= (res + 1);
395 :
396 54 : return res;
397 : }
398 :
399 : static const float *
400 210 : getWeights(ArrayType *win)
401 : {
402 : static float ws[lengthof(weights)];
403 : int i;
404 : float4 *arrdata;
405 :
406 210 : if (win == NULL)
407 210 : return weights;
408 :
409 0 : if (ARR_NDIM(win) != 1)
410 0 : ereport(ERROR,
411 : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
412 : errmsg("array of weight must be one-dimensional")));
413 :
414 0 : if (ArrayGetNItems(ARR_NDIM(win), ARR_DIMS(win)) < lengthof(weights))
415 0 : ereport(ERROR,
416 : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
417 : errmsg("array of weight is too short")));
418 :
419 0 : if (array_contains_nulls(win))
420 0 : ereport(ERROR,
421 : (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
422 : errmsg("array of weight must not contain nulls")));
423 :
424 0 : arrdata = (float4 *) ARR_DATA_PTR(win);
425 0 : for (i = 0; i < lengthof(weights); i++)
426 : {
427 0 : ws[i] = (arrdata[i] >= 0) ? arrdata[i] : weights[i];
428 0 : if (ws[i] > 1.0)
429 0 : ereport(ERROR,
430 : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
431 : errmsg("weight out of range")));
432 : }
433 :
434 0 : return ws;
435 : }
436 :
437 : Datum
438 0 : ts_rank_wttf(PG_FUNCTION_ARGS)
439 : {
440 0 : ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
441 0 : TSVector txt = PG_GETARG_TSVECTOR(1);
442 0 : TSQuery query = PG_GETARG_TSQUERY(2);
443 0 : int method = PG_GETARG_INT32(3);
444 : float res;
445 :
446 0 : res = calc_rank(getWeights(win), txt, query, method);
447 :
448 0 : PG_FREE_IF_COPY(win, 0);
449 0 : PG_FREE_IF_COPY(txt, 1);
450 0 : PG_FREE_IF_COPY(query, 2);
451 0 : PG_RETURN_FLOAT4(res);
452 : }
453 :
454 : Datum
455 0 : ts_rank_wtt(PG_FUNCTION_ARGS)
456 : {
457 0 : ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
458 0 : TSVector txt = PG_GETARG_TSVECTOR(1);
459 0 : TSQuery query = PG_GETARG_TSQUERY(2);
460 : float res;
461 :
462 0 : res = calc_rank(getWeights(win), txt, query, DEF_NORM_METHOD);
463 :
464 0 : PG_FREE_IF_COPY(win, 0);
465 0 : PG_FREE_IF_COPY(txt, 1);
466 0 : PG_FREE_IF_COPY(query, 2);
467 0 : PG_RETURN_FLOAT4(res);
468 : }
469 :
470 : Datum
471 0 : ts_rank_ttf(PG_FUNCTION_ARGS)
472 : {
473 0 : TSVector txt = PG_GETARG_TSVECTOR(0);
474 0 : TSQuery query = PG_GETARG_TSQUERY(1);
475 0 : int method = PG_GETARG_INT32(2);
476 : float res;
477 :
478 0 : res = calc_rank(getWeights(NULL), txt, query, method);
479 :
480 0 : PG_FREE_IF_COPY(txt, 0);
481 0 : PG_FREE_IF_COPY(query, 1);
482 0 : PG_RETURN_FLOAT4(res);
483 : }
484 :
485 : Datum
486 54 : ts_rank_tt(PG_FUNCTION_ARGS)
487 : {
488 54 : TSVector txt = PG_GETARG_TSVECTOR(0);
489 54 : TSQuery query = PG_GETARG_TSQUERY(1);
490 : float res;
491 :
492 54 : res = calc_rank(getWeights(NULL), txt, query, DEF_NORM_METHOD);
493 :
494 54 : PG_FREE_IF_COPY(txt, 0);
495 54 : PG_FREE_IF_COPY(query, 1);
496 54 : PG_RETURN_FLOAT4(res);
497 : }
498 :
499 : typedef struct
500 : {
501 : union
502 : {
503 : struct
504 : { /* compiled doc representation */
505 : QueryItem **items;
506 : int16 nitem;
507 : } query;
508 : struct
509 : { /* struct is used for preparing doc
510 : * representation */
511 : QueryItem *item;
512 : WordEntry *entry;
513 : } map;
514 : } data;
515 : WordEntryPos pos;
516 : } DocRepresentation;
517 :
518 : static int
519 348 : compareDocR(const void *va, const void *vb)
520 : {
521 348 : const DocRepresentation *a = (const DocRepresentation *) va;
522 348 : const DocRepresentation *b = (const DocRepresentation *) vb;
523 :
524 348 : if (WEP_GETPOS(a->pos) == WEP_GETPOS(b->pos))
525 : {
526 36 : if (WEP_GETWEIGHT(a->pos) == WEP_GETWEIGHT(b->pos))
527 : {
528 6 : if (a->data.map.entry == b->data.map.entry)
529 6 : return 0;
530 :
531 0 : return (a->data.map.entry > b->data.map.entry) ? 1 : -1;
532 : }
533 :
534 30 : return (WEP_GETWEIGHT(a->pos) > WEP_GETWEIGHT(b->pos)) ? 1 : -1;
535 : }
536 :
537 312 : return (WEP_GETPOS(a->pos) > WEP_GETPOS(b->pos)) ? 1 : -1;
538 : }
539 :
540 : #define MAXQROPOS MAXENTRYPOS
541 : typedef struct
542 : {
543 : bool operandexists;
544 : bool reverseinsert; /* indicates insert order, true means
545 : * descending order */
546 : uint32 npos;
547 : WordEntryPos pos[MAXQROPOS];
548 : } QueryRepresentationOperand;
549 :
550 : typedef struct
551 : {
552 : TSQuery query;
553 : QueryRepresentationOperand *operandData;
554 : } QueryRepresentation;
555 :
556 : #define QR_GET_OPERAND_DATA(q, v) \
557 : ( (q)->operandData + (((QueryItem*)(v)) - GETQUERY((q)->query)) )
558 :
559 : /*
560 : * TS_execute callback for matching a tsquery operand to QueryRepresentation
561 : */
562 : static TSTernaryValue
563 1158 : checkcondition_QueryOperand(void *checkval, QueryOperand *val,
564 : ExecPhraseData *data)
565 : {
566 1158 : QueryRepresentation *qr = (QueryRepresentation *) checkval;
567 1158 : QueryRepresentationOperand *opData = QR_GET_OPERAND_DATA(qr, val);
568 :
569 1158 : if (!opData->operandexists)
570 444 : return TS_NO;
571 :
572 714 : if (data)
573 : {
574 348 : data->npos = opData->npos;
575 348 : data->pos = opData->pos;
576 348 : if (opData->reverseinsert)
577 108 : data->pos += MAXQROPOS - opData->npos;
578 : }
579 :
580 714 : return TS_YES;
581 : }
582 :
583 : typedef struct
584 : {
585 : int pos;
586 : int p;
587 : int q;
588 : DocRepresentation *begin;
589 : DocRepresentation *end;
590 : } CoverExt;
591 :
592 : static void
593 498 : resetQueryRepresentation(QueryRepresentation *qr, bool reverseinsert)
594 : {
595 : int i;
596 :
597 2016 : for (i = 0; i < qr->query->size; i++)
598 : {
599 1518 : qr->operandData[i].operandexists = false;
600 1518 : qr->operandData[i].reverseinsert = reverseinsert;
601 1518 : qr->operandData[i].npos = 0;
602 : }
603 498 : }
604 :
605 : static void
606 720 : fillQueryRepresentationData(QueryRepresentation *qr, DocRepresentation *entry)
607 : {
608 : int i;
609 : int lastPos;
610 : QueryRepresentationOperand *opData;
611 :
612 1446 : for (i = 0; i < entry->data.query.nitem; i++)
613 : {
614 726 : if (entry->data.query.items[i]->type != QI_VAL)
615 0 : continue;
616 :
617 726 : opData = QR_GET_OPERAND_DATA(qr, entry->data.query.items[i]);
618 :
619 726 : opData->operandexists = true;
620 :
621 726 : if (opData->npos == 0)
622 : {
623 660 : lastPos = (opData->reverseinsert) ? (MAXQROPOS - 1) : 0;
624 660 : opData->pos[lastPos] = entry->pos;
625 660 : opData->npos++;
626 660 : continue;
627 : }
628 :
629 132 : lastPos = opData->reverseinsert ?
630 66 : (MAXQROPOS - opData->npos) :
631 66 : (opData->npos - 1);
632 :
633 66 : if (WEP_GETPOS(opData->pos[lastPos]) != WEP_GETPOS(entry->pos))
634 : {
635 84 : lastPos = opData->reverseinsert ?
636 42 : (MAXQROPOS - 1 - opData->npos) :
637 42 : (opData->npos);
638 :
639 42 : opData->pos[lastPos] = entry->pos;
640 42 : opData->npos++;
641 : }
642 : }
643 720 : }
644 :
645 : static bool
646 324 : Cover(DocRepresentation *doc, int len, QueryRepresentation *qr, CoverExt *ext)
647 : {
648 : DocRepresentation *ptr;
649 324 : int lastpos = ext->pos;
650 324 : bool found = false;
651 :
652 : /*
653 : * since this function recurses, it could be driven to stack overflow.
654 : * (though any decent compiler will optimize away the tail-recursion.
655 : */
656 324 : check_stack_depth();
657 :
658 324 : resetQueryRepresentation(qr, false);
659 :
660 324 : ext->p = INT_MAX;
661 324 : ext->q = 0;
662 324 : ptr = doc + ext->pos;
663 :
664 : /* find upper bound of cover from current position, move up */
665 606 : while (ptr - doc < len)
666 : {
667 456 : fillQueryRepresentationData(qr, ptr);
668 :
669 456 : if (TS_execute(GETQUERY(qr->query), (void *) qr,
670 : TS_EXEC_EMPTY, checkcondition_QueryOperand))
671 : {
672 174 : if (WEP_GETPOS(ptr->pos) > ext->q)
673 : {
674 174 : ext->q = WEP_GETPOS(ptr->pos);
675 174 : ext->end = ptr;
676 174 : lastpos = ptr - doc;
677 174 : found = true;
678 : }
679 174 : break;
680 : }
681 282 : ptr++;
682 : }
683 :
684 324 : if (!found)
685 150 : return false;
686 :
687 174 : resetQueryRepresentation(qr, true);
688 :
689 174 : ptr = doc + lastpos;
690 :
691 : /* find lower bound of cover from found upper bound, move down */
692 264 : while (ptr >= doc + ext->pos)
693 : {
694 : /*
695 : * we scan doc from right to left, so pos info in reverse order!
696 : */
697 264 : fillQueryRepresentationData(qr, ptr);
698 :
699 264 : if (TS_execute(GETQUERY(qr->query), (void *) qr,
700 : TS_EXEC_EMPTY, checkcondition_QueryOperand))
701 : {
702 174 : if (WEP_GETPOS(ptr->pos) < ext->p)
703 : {
704 174 : ext->begin = ptr;
705 174 : ext->p = WEP_GETPOS(ptr->pos);
706 : }
707 174 : break;
708 : }
709 90 : ptr--;
710 : }
711 :
712 174 : if (ext->p <= ext->q)
713 : {
714 : /*
715 : * set position for next try to next lexeme after beginning of found
716 : * cover
717 : */
718 174 : ext->pos = (ptr - doc) + 1;
719 174 : return true;
720 : }
721 :
722 0 : ext->pos++;
723 0 : return Cover(doc, len, qr, ext);
724 : }
725 :
726 : static DocRepresentation *
727 156 : get_docrep(TSVector txt, QueryRepresentation *qr, int *doclen)
728 : {
729 156 : QueryItem *item = GETQUERY(qr->query);
730 : WordEntry *entry,
731 : *firstentry;
732 : WordEntryPos *post;
733 : int32 dimt, /* number of 'post' items */
734 : j,
735 : i,
736 : nitem;
737 156 : int len = qr->query->size * 4,
738 156 : cur = 0;
739 : DocRepresentation *doc;
740 :
741 156 : doc = (DocRepresentation *) palloc(sizeof(DocRepresentation) * len);
742 :
743 : /*
744 : * Iterate through query to make DocRepresentation for words and it's
745 : * entries satisfied by query
746 : */
747 636 : for (i = 0; i < qr->query->size; i++)
748 : {
749 : QueryOperand *curoperand;
750 :
751 480 : if (item[i].type != QI_VAL)
752 162 : continue;
753 :
754 318 : curoperand = &item[i].qoperand;
755 :
756 318 : firstentry = entry = find_wordentry(txt, qr->query, curoperand, &nitem);
757 318 : if (!entry)
758 6 : continue;
759 :
760 : /* iterations over entries in tsvector */
761 654 : while (entry - firstentry < nitem)
762 : {
763 342 : if (entry->haspos)
764 : {
765 330 : dimt = POSDATALEN(txt, entry);
766 330 : post = POSDATAPTR(txt, entry);
767 : }
768 : else
769 : {
770 : /* ignore words without positions */
771 12 : entry++;
772 12 : continue;
773 : }
774 :
775 330 : while (cur + dimt >= len)
776 : {
777 0 : len *= 2;
778 0 : doc = (DocRepresentation *) repalloc(doc, sizeof(DocRepresentation) * len);
779 : }
780 :
781 : /* iterations over entry's positions */
782 714 : for (j = 0; j < dimt; j++)
783 : {
784 384 : if (curoperand->weight == 0 ||
785 30 : curoperand->weight & (1 << WEP_GETWEIGHT(post[j])))
786 : {
787 372 : doc[cur].pos = post[j];
788 372 : doc[cur].data.map.entry = entry;
789 372 : doc[cur].data.map.item = (QueryItem *) curoperand;
790 372 : cur++;
791 : }
792 : }
793 :
794 330 : entry++;
795 : }
796 : }
797 :
798 156 : if (cur > 0)
799 : {
800 150 : DocRepresentation *rptr = doc + 1,
801 150 : *wptr = doc,
802 : storage;
803 :
804 : /*
805 : * Sort representation in ascending order by pos and entry
806 : */
807 150 : qsort(doc, cur, sizeof(DocRepresentation), compareDocR);
808 :
809 : /*
810 : * Join QueryItem per WordEntry and it's position
811 : */
812 150 : storage.pos = doc->pos;
813 150 : storage.data.query.items = palloc(sizeof(QueryItem *) * qr->query->size);
814 150 : storage.data.query.items[0] = doc->data.map.item;
815 150 : storage.data.query.nitem = 1;
816 :
817 372 : while (rptr - doc < cur)
818 : {
819 222 : if (rptr->pos == (rptr - 1)->pos &&
820 6 : rptr->data.map.entry == (rptr - 1)->data.map.entry)
821 : {
822 6 : storage.data.query.items[storage.data.query.nitem] = rptr->data.map.item;
823 6 : storage.data.query.nitem++;
824 : }
825 : else
826 : {
827 216 : *wptr = storage;
828 216 : wptr++;
829 216 : storage.pos = rptr->pos;
830 216 : storage.data.query.items = palloc(sizeof(QueryItem *) * qr->query->size);
831 216 : storage.data.query.items[0] = rptr->data.map.item;
832 216 : storage.data.query.nitem = 1;
833 : }
834 :
835 222 : rptr++;
836 : }
837 :
838 150 : *wptr = storage;
839 150 : wptr++;
840 :
841 150 : *doclen = wptr - doc;
842 150 : return doc;
843 : }
844 :
845 6 : pfree(doc);
846 6 : return NULL;
847 : }
848 :
849 : static float4
850 156 : calc_rank_cd(const float4 *arrdata, TSVector txt, TSQuery query, int method)
851 : {
852 : DocRepresentation *doc;
853 : int len,
854 : i,
855 156 : doclen = 0;
856 : CoverExt ext;
857 156 : double Wdoc = 0.0;
858 : double invws[lengthof(weights)];
859 156 : double SumDist = 0.0,
860 156 : PrevExtPos = 0.0;
861 156 : int NExtent = 0;
862 : QueryRepresentation qr;
863 :
864 :
865 780 : for (i = 0; i < lengthof(weights); i++)
866 : {
867 624 : invws[i] = ((double) ((arrdata[i] >= 0) ? arrdata[i] : weights[i]));
868 624 : if (invws[i] > 1.0)
869 0 : ereport(ERROR,
870 : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
871 : errmsg("weight out of range")));
872 624 : invws[i] = 1.0 / invws[i];
873 : }
874 :
875 156 : qr.query = query;
876 156 : qr.operandData = (QueryRepresentationOperand *)
877 156 : palloc0(sizeof(QueryRepresentationOperand) * query->size);
878 :
879 156 : doc = get_docrep(txt, &qr, &doclen);
880 156 : if (!doc)
881 : {
882 6 : pfree(qr.operandData);
883 6 : return 0.0;
884 : }
885 :
886 750 : MemSet(&ext, 0, sizeof(CoverExt));
887 324 : while (Cover(doc, doclen, &qr, &ext))
888 : {
889 174 : double Cpos = 0.0;
890 174 : double InvSum = 0.0;
891 : double CurExtPos;
892 : int nNoise;
893 174 : DocRepresentation *ptr = ext.begin;
894 :
895 438 : while (ptr <= ext.end)
896 : {
897 264 : InvSum += invws[WEP_GETWEIGHT(ptr->pos)];
898 264 : ptr++;
899 : }
900 :
901 174 : Cpos = ((double) (ext.end - ext.begin + 1)) / InvSum;
902 :
903 : /*
904 : * if doc are big enough then ext.q may be equal to ext.p due to limit
905 : * of positional information. In this case we approximate number of
906 : * noise word as half cover's length
907 : */
908 174 : nNoise = (ext.q - ext.p) - (ext.end - ext.begin);
909 174 : if (nNoise < 0)
910 0 : nNoise = (ext.end - ext.begin) / 2;
911 174 : Wdoc += Cpos / ((double) (1 + nNoise));
912 :
913 174 : CurExtPos = ((double) (ext.q + ext.p)) / 2.0;
914 174 : if (NExtent > 0 && CurExtPos > PrevExtPos /* prevent division by
915 : * zero in a case of
916 : * multiple lexize */ )
917 42 : SumDist += 1.0 / (CurExtPos - PrevExtPos);
918 :
919 174 : PrevExtPos = CurExtPos;
920 174 : NExtent++;
921 : }
922 :
923 150 : if ((method & RANK_NORM_LOGLENGTH) && txt->size > 0)
924 0 : Wdoc /= log((double) (cnt_length(txt) + 1));
925 :
926 150 : if (method & RANK_NORM_LENGTH)
927 : {
928 0 : len = cnt_length(txt);
929 0 : if (len > 0)
930 0 : Wdoc /= (double) len;
931 : }
932 :
933 150 : if ((method & RANK_NORM_EXTDIST) && NExtent > 0 && SumDist > 0)
934 0 : Wdoc /= ((double) NExtent) / SumDist;
935 :
936 150 : if ((method & RANK_NORM_UNIQ) && txt->size > 0)
937 0 : Wdoc /= (double) (txt->size);
938 :
939 150 : if ((method & RANK_NORM_LOGUNIQ) && txt->size > 0)
940 0 : Wdoc /= log((double) (txt->size + 1)) / log(2.0);
941 :
942 150 : if (method & RANK_NORM_RDIVRPLUS1)
943 0 : Wdoc /= (Wdoc + 1);
944 :
945 150 : pfree(doc);
946 :
947 150 : pfree(qr.operandData);
948 :
949 150 : return (float4) Wdoc;
950 : }
951 :
952 : Datum
953 0 : ts_rankcd_wttf(PG_FUNCTION_ARGS)
954 : {
955 0 : ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
956 0 : TSVector txt = PG_GETARG_TSVECTOR(1);
957 0 : TSQuery query = PG_GETARG_TSQUERY(2);
958 0 : int method = PG_GETARG_INT32(3);
959 : float res;
960 :
961 0 : res = calc_rank_cd(getWeights(win), txt, query, method);
962 :
963 0 : PG_FREE_IF_COPY(win, 0);
964 0 : PG_FREE_IF_COPY(txt, 1);
965 0 : PG_FREE_IF_COPY(query, 2);
966 0 : PG_RETURN_FLOAT4(res);
967 : }
968 :
969 : Datum
970 0 : ts_rankcd_wtt(PG_FUNCTION_ARGS)
971 : {
972 0 : ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
973 0 : TSVector txt = PG_GETARG_TSVECTOR(1);
974 0 : TSQuery query = PG_GETARG_TSQUERY(2);
975 : float res;
976 :
977 0 : res = calc_rank_cd(getWeights(win), txt, query, DEF_NORM_METHOD);
978 :
979 0 : PG_FREE_IF_COPY(win, 0);
980 0 : PG_FREE_IF_COPY(txt, 1);
981 0 : PG_FREE_IF_COPY(query, 2);
982 0 : PG_RETURN_FLOAT4(res);
983 : }
984 :
985 : Datum
986 0 : ts_rankcd_ttf(PG_FUNCTION_ARGS)
987 : {
988 0 : TSVector txt = PG_GETARG_TSVECTOR(0);
989 0 : TSQuery query = PG_GETARG_TSQUERY(1);
990 0 : int method = PG_GETARG_INT32(2);
991 : float res;
992 :
993 0 : res = calc_rank_cd(getWeights(NULL), txt, query, method);
994 :
995 0 : PG_FREE_IF_COPY(txt, 0);
996 0 : PG_FREE_IF_COPY(query, 1);
997 0 : PG_RETURN_FLOAT4(res);
998 : }
999 :
1000 : Datum
1001 156 : ts_rankcd_tt(PG_FUNCTION_ARGS)
1002 : {
1003 156 : TSVector txt = PG_GETARG_TSVECTOR(0);
1004 156 : TSQuery query = PG_GETARG_TSQUERY(1);
1005 : float res;
1006 :
1007 156 : res = calc_rank_cd(getWeights(NULL), txt, query, DEF_NORM_METHOD);
1008 :
1009 156 : PG_FREE_IF_COPY(txt, 0);
1010 156 : PG_FREE_IF_COPY(query, 1);
1011 156 : PG_RETURN_FLOAT4(res);
1012 : }
|