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