1 /*-------------------------------------------------------------------------
4 * rank tsvector by tsquery
6 * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
10 * src/backend/utils/adt/tsrank.c
12 *-------------------------------------------------------------------------
18 #include "tsearch/ts_type.h"
19 #include "tsearch/ts_utils.h"
20 #include "utils/array.h"
21 #include "miscadmin.h"
24 static float weights[] = {0.1f, 0.2f, 0.4f, 1.0f};
26 #define wpos(wep) ( w[ WEP_GETWEIGHT(wep) ] )
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
37 static float calc_rank_or(float *w, TSVector t, TSQuery q);
38 static float calc_rank_and(float *w, TSVector t, TSQuery q);
41 * Returns a weight of a word collocation
49 return 1.0 / (1.005 + 0.05 * exp(((float4) w) / 1.5 - 2));
53 cnt_length(TSVector t)
55 WordEntry *ptr = ARRPTR(t),
56 *end = (WordEntry *) STRPTR(t);
61 int clen = POSDATALEN(t, ptr);
75 #define WordECompareQueryItem(e,q,p,i,m) \
76 tsCompareString((q) + (i)->distance, (i)->length, \
77 (e) + (p)->pos, (p)->len, (m))
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.
86 find_wordentry(TSVector t, TSQuery q, QueryOperand *item, int32 *nitem)
88 WordEntry *StopLow = ARRPTR(t);
89 WordEntry *StopHigh = (WordEntry *) STRPTR(t);
90 WordEntry *StopMiddle = StopHigh;
95 /* Loop invariant: StopLow <= item < StopHigh */
96 while (StopLow < StopHigh)
98 StopMiddle = StopLow + (StopHigh - StopLow) / 2;
99 difference = WordECompareQueryItem(STRPTR(t), GETOPERAND(q), StopMiddle, item, false);
102 StopHigh = StopMiddle;
106 else if (difference > 0)
107 StopLow = StopMiddle + 1;
109 StopHigh = StopMiddle;
114 if (StopLow >= StopHigh)
115 StopMiddle = StopHigh;
119 while (StopMiddle < (WordEntry *) STRPTR(t) &&
120 WordECompareQueryItem(STRPTR(t), GETOPERAND(q), StopMiddle, item, true) == 0)
127 return (*nitem > 0) ? StopHigh : NULL;
132 * sort QueryOperands by (length, word)
135 compareQueryOperand(const void *a, const void *b, void *arg)
137 char *operand = (char *) arg;
138 QueryOperand *qa = (*(QueryOperand **) a);
139 QueryOperand *qb = (*(QueryOperand **) b);
141 return tsCompareString(operand + qa->distance, qa->length,
142 operand + qb->distance, qb->length,
147 * Returns a sorted, de-duplicated array of QueryOperands in a query.
148 * The returned QueryOperands are pointers to the original QueryOperands
151 * Length of the returned array is stored in *size
153 static QueryOperand **
154 SortAndUniqItems(TSQuery q, int *size)
156 char *operand = GETOPERAND(q);
157 QueryItem *item = GETQUERY(q);
162 ptr = res = (QueryOperand **) palloc(sizeof(QueryOperand *) * *size);
164 /* Collect all operands from the tree to res */
167 if (item->type == QI_VAL)
169 *ptr = (QueryOperand *) item;
179 qsort_arg(res, *size, sizeof(QueryOperand **), compareQueryOperand, (void *) operand);
184 /* remove duplicates */
185 while (ptr - res < *size)
187 if (compareQueryOperand((void *) ptr, (void *) prevptr, (void *) operand) != 0)
195 *size = prevptr + 1 - res;
199 /* A dummy WordEntryPos array to use when haspos is false */
200 static WordEntryPosVector POSNULL = {
201 1, /* Number of elements that follow */
206 calc_rank_and(float *w, TSVector t, TSQuery q)
208 WordEntryPosVector **pos;
225 item = SortAndUniqItems(q, &size);
229 return calc_rank_or(w, t, q);
231 pos = (WordEntryPosVector **) palloc0(sizeof(WordEntryPosVector *) * q->size);
232 WEP_SETPOS(POSNULL.pos[0], MAXENTRYPOS - 1);
234 for (i = 0; i < size; i++)
236 firstentry = entry = find_wordentry(t, q, item[i], &nitem);
240 while (entry - firstentry < nitem)
243 pos[i] = _POSVECPTR(t, entry);
249 for (k = 0; k < i; k++)
253 lenct = pos[k]->npos;
255 for (l = 0; l < dimt; l++)
257 for (p = 0; p < lenct; p++)
259 dist = Abs((int) WEP_GETPOS(post[l]) - (int) WEP_GETPOS(ct[p]));
260 if (dist || (dist == 0 && (pos[i] == &POSNULL || pos[k] == &POSNULL)))
266 curw = sqrt(wpos(post[l]) * wpos(ct[p]) * word_distance(dist));
267 res = (res < 0) ? curw : 1.0 - (1.0 - res) * (1.0 - curw);
282 calc_rank_or(float *w, TSVector t, TSQuery q)
295 item = SortAndUniqItems(q, &size);
297 for (i = 0; i < size; i++)
303 firstentry = entry = find_wordentry(t, q, item[i], &nitem);
307 while (entry - firstentry < nitem)
311 dimt = POSDATALEN(t, entry);
312 post = POSDATAPTR(t, entry);
323 for (j = 0; j < dimt; j++)
325 resj = resj + wpos(post[j]) / ((j + 1) * (j + 1));
326 if (wpos(post[j]) > wjm)
333 limit (sum(i/i^2),i->inf) = pi^2/6
334 resj = sum(wi/i^2),i=1,noccurence,
335 wi - should be sorted desc,
336 don't sort for now, just choose maximum weight. This should be corrected
339 res = res + (wjm + resj - wjm / ((jm + 1) * (jm + 1))) / 1.64493406685;
351 calc_rank(float *w, TSVector t, TSQuery q, int4 method)
353 QueryItem *item = GETQUERY(q);
357 if (!t->size || !q->size)
360 /* XXX: What about NOT? */
361 res = (item->type == QI_OPR && item->qoperator.oper == OP_AND) ?
362 calc_rank_and(w, t, q) : calc_rank_or(w, t, q);
367 if ((method & RANK_NORM_LOGLENGTH) && t->size > 0)
368 res /= log((double) (cnt_length(t) + 1)) / log(2.0);
370 if (method & RANK_NORM_LENGTH)
377 /* RANK_NORM_EXTDIST not applicable */
379 if ((method & RANK_NORM_UNIQ) && t->size > 0)
380 res /= (float) (t->size);
382 if ((method & RANK_NORM_LOGUNIQ) && t->size > 0)
383 res /= log((double) (t->size + 1)) / log(2.0);
385 if (method & RANK_NORM_RDIVRPLUS1)
392 getWeights(ArrayType *win)
394 static float ws[lengthof(weights)];
401 if (ARR_NDIM(win) != 1)
403 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
404 errmsg("array of weight must be one-dimensional")));
406 if (ArrayGetNItems(ARR_NDIM(win), ARR_DIMS(win)) < lengthof(weights))
408 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
409 errmsg("array of weight is too short")));
411 if (ARR_HASNULL(win))
413 (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
414 errmsg("array of weight must not contain nulls")));
416 arrdata = (float4 *) ARR_DATA_PTR(win);
417 for (i = 0; i < lengthof(weights); i++)
419 ws[i] = (arrdata[i] >= 0) ? arrdata[i] : weights[i];
422 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
423 errmsg("weight out of range")));
430 ts_rank_wttf(PG_FUNCTION_ARGS)
432 ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
433 TSVector txt = PG_GETARG_TSVECTOR(1);
434 TSQuery query = PG_GETARG_TSQUERY(2);
435 int method = PG_GETARG_INT32(3);
438 res = calc_rank(getWeights(win), txt, query, method);
440 PG_FREE_IF_COPY(win, 0);
441 PG_FREE_IF_COPY(txt, 1);
442 PG_FREE_IF_COPY(query, 2);
443 PG_RETURN_FLOAT4(res);
447 ts_rank_wtt(PG_FUNCTION_ARGS)
449 ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
450 TSVector txt = PG_GETARG_TSVECTOR(1);
451 TSQuery query = PG_GETARG_TSQUERY(2);
454 res = calc_rank(getWeights(win), txt, query, DEF_NORM_METHOD);
456 PG_FREE_IF_COPY(win, 0);
457 PG_FREE_IF_COPY(txt, 1);
458 PG_FREE_IF_COPY(query, 2);
459 PG_RETURN_FLOAT4(res);
463 ts_rank_ttf(PG_FUNCTION_ARGS)
465 TSVector txt = PG_GETARG_TSVECTOR(0);
466 TSQuery query = PG_GETARG_TSQUERY(1);
467 int method = PG_GETARG_INT32(2);
470 res = calc_rank(getWeights(NULL), txt, query, method);
472 PG_FREE_IF_COPY(txt, 0);
473 PG_FREE_IF_COPY(query, 1);
474 PG_RETURN_FLOAT4(res);
478 ts_rank_tt(PG_FUNCTION_ARGS)
480 TSVector txt = PG_GETARG_TSVECTOR(0);
481 TSQuery query = PG_GETARG_TSQUERY(1);
484 res = calc_rank(getWeights(NULL), txt, query, DEF_NORM_METHOD);
486 PG_FREE_IF_COPY(txt, 0);
487 PG_FREE_IF_COPY(query, 1);
488 PG_RETURN_FLOAT4(res);
500 compareDocR(const void *va, const void *vb)
502 DocRepresentation *a = (DocRepresentation *) va;
503 DocRepresentation *b = (DocRepresentation *) vb;
505 if (a->pos == b->pos)
507 return (a->pos > b->pos) ? 1 : -1;
514 } QueryRepresentation;
516 #define QR_GET_OPERAND_EXISTS(q, v) ( (q)->operandexist[ ((QueryItem*)(v)) - GETQUERY((q)->query) ] )
517 #define QR_SET_OPERAND_EXISTS(q, v) QR_GET_OPERAND_EXISTS(q,v) = true
520 checkcondition_QueryOperand(void *checkval, QueryOperand *val)
522 QueryRepresentation *qr = (QueryRepresentation *) checkval;
524 return QR_GET_OPERAND_EXISTS(qr, val);
532 DocRepresentation *begin;
533 DocRepresentation *end;
538 Cover(DocRepresentation *doc, int len, QueryRepresentation *qr, Extention *ext)
540 DocRepresentation *ptr;
541 int lastpos = ext->pos;
546 * since this function recurses, it could be driven to stack overflow.
547 * (though any decent compiler will optimize away the tail-recursion.
551 memset(qr->operandexist, 0, sizeof(bool) * qr->query->size);
555 ptr = doc + ext->pos;
557 /* find upper bound of cover from current position, move up */
558 while (ptr - doc < len)
560 for (i = 0; i < ptr->nitem; i++)
562 if (ptr->item[i]->type == QI_VAL)
563 QR_SET_OPERAND_EXISTS(qr, ptr->item[i]);
565 if (TS_execute(GETQUERY(qr->query), (void *) qr, false, checkcondition_QueryOperand))
567 if (ptr->pos > ext->q)
582 memset(qr->operandexist, 0, sizeof(bool) * qr->query->size);
586 /* find lower bound of cover from found upper bound, move down */
587 while (ptr >= doc + ext->pos)
589 for (i = 0; i < ptr->nitem; i++)
590 if (ptr->item[i]->type == QI_VAL)
591 QR_SET_OPERAND_EXISTS(qr, ptr->item[i]);
592 if (TS_execute(GETQUERY(qr->query), (void *) qr, true, checkcondition_QueryOperand))
594 if (ptr->pos < ext->p)
604 if (ext->p <= ext->q)
607 * set position for next try to next lexeme after begining of founded
610 ext->pos = (ptr - doc) + 1;
615 return Cover(doc, len, qr, ext);
618 static DocRepresentation *
619 get_docrep(TSVector txt, QueryRepresentation *qr, int *doclen)
621 QueryItem *item = GETQUERY(qr->query);
629 int len = qr->query->size * 4,
631 DocRepresentation *doc;
634 doc = (DocRepresentation *) palloc(sizeof(DocRepresentation) * len);
635 operand = GETOPERAND(qr->query);
637 for (i = 0; i < qr->query->size; i++)
639 QueryOperand *curoperand;
641 if (item[i].type != QI_VAL)
644 curoperand = &item[i].qoperand;
646 if (QR_GET_OPERAND_EXISTS(qr, &item[i]))
649 firstentry = entry = find_wordentry(txt, qr->query, curoperand, &nitem);
653 while (entry - firstentry < nitem)
657 dimt = POSDATALEN(txt, entry);
658 post = POSDATAPTR(txt, entry);
666 while (cur + dimt >= len)
669 doc = (DocRepresentation *) repalloc(doc, sizeof(DocRepresentation) * len);
672 for (j = 0; j < dimt; j++)
679 doc[cur].item = (QueryItem **) palloc(sizeof(QueryItem *) * qr->query->size);
681 for (k = 0; k < qr->query->size; k++)
683 QueryOperand *kptr = &item[k].qoperand;
684 QueryOperand *iptr = &item[i].qoperand;
687 (item[k].type == QI_VAL &&
688 compareQueryOperand(&kptr, &iptr, operand) == 0))
691 * if k == i, we've already checked above that
694 doc[cur].item[doc[cur].nitem] = item + k;
696 QR_SET_OPERAND_EXISTS(qr, item + k);
702 doc[cur].nitem = doc[cur - 1].nitem;
703 doc[cur].item = doc[cur - 1].item;
705 doc[cur].pos = WEP_GETPOS(post[j]);
706 doc[cur].wclass = WEP_GETWEIGHT(post[j]);
718 qsort((void *) doc, cur, sizeof(DocRepresentation), compareDocR);
727 calc_rank_cd(float4 *arrdata, TSVector txt, TSQuery query, int method)
729 DocRepresentation *doc;
735 double invws[lengthof(weights)];
736 double SumDist = 0.0,
740 QueryRepresentation qr;
743 for (i = 0; i < lengthof(weights); i++)
745 invws[i] = ((double) ((arrdata[i] >= 0) ? arrdata[i] : weights[i]));
748 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
749 errmsg("weight out of range")));
750 invws[i] = 1.0 / invws[i];
754 qr.operandexist = (bool *) palloc0(sizeof(bool) * query->size);
756 doc = get_docrep(txt, &qr, &doclen);
759 pfree(qr.operandexist);
763 MemSet(&ext, 0, sizeof(Extention));
764 while (Cover(doc, doclen, &qr, &ext))
769 DocRepresentation *ptr = ext.begin;
771 while (ptr <= ext.end)
773 InvSum += invws[ptr->wclass];
777 Cpos = ((double) (ext.end - ext.begin + 1)) / InvSum;
780 * if doc are big enough then ext.q may be equal to ext.p due to limit
781 * of posional information. In this case we approximate number of
782 * noise word as half cover's length
784 nNoise = (ext.q - ext.p) - (ext.end - ext.begin);
786 nNoise = (ext.end - ext.begin) / 2;
787 Wdoc += Cpos / ((double) (1 + nNoise));
789 CurExtPos = ((double) (ext.q + ext.p)) / 2.0;
790 if (NExtent > 0 && CurExtPos > PrevExtPos /* prevent devision by
793 SumDist += 1.0 / (CurExtPos - PrevExtPos);
795 PrevExtPos = CurExtPos;
799 if ((method & RANK_NORM_LOGLENGTH) && txt->size > 0)
800 Wdoc /= log((double) (cnt_length(txt) + 1));
802 if (method & RANK_NORM_LENGTH)
804 len = cnt_length(txt);
806 Wdoc /= (double) len;
809 if ((method & RANK_NORM_EXTDIST) && NExtent > 0 && SumDist > 0)
810 Wdoc /= ((double) NExtent) / SumDist;
812 if ((method & RANK_NORM_UNIQ) && txt->size > 0)
813 Wdoc /= (double) (txt->size);
815 if ((method & RANK_NORM_LOGUNIQ) && txt->size > 0)
816 Wdoc /= log((double) (txt->size + 1)) / log(2.0);
818 if (method & RANK_NORM_RDIVRPLUS1)
823 pfree(qr.operandexist);
825 return (float4) Wdoc;
829 ts_rankcd_wttf(PG_FUNCTION_ARGS)
831 ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
832 TSVector txt = PG_GETARG_TSVECTOR(1);
833 TSQuery query = PG_GETARG_TSQUERY(2);
834 int method = PG_GETARG_INT32(3);
837 res = calc_rank_cd(getWeights(win), txt, query, method);
839 PG_FREE_IF_COPY(win, 0);
840 PG_FREE_IF_COPY(txt, 1);
841 PG_FREE_IF_COPY(query, 2);
842 PG_RETURN_FLOAT4(res);
846 ts_rankcd_wtt(PG_FUNCTION_ARGS)
848 ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
849 TSVector txt = PG_GETARG_TSVECTOR(1);
850 TSQuery query = PG_GETARG_TSQUERY(2);
853 res = calc_rank_cd(getWeights(win), txt, query, DEF_NORM_METHOD);
855 PG_FREE_IF_COPY(win, 0);
856 PG_FREE_IF_COPY(txt, 1);
857 PG_FREE_IF_COPY(query, 2);
858 PG_RETURN_FLOAT4(res);
862 ts_rankcd_ttf(PG_FUNCTION_ARGS)
864 TSVector txt = PG_GETARG_TSVECTOR(0);
865 TSQuery query = PG_GETARG_TSQUERY(1);
866 int method = PG_GETARG_INT32(2);
869 res = calc_rank_cd(getWeights(NULL), txt, query, method);
871 PG_FREE_IF_COPY(txt, 0);
872 PG_FREE_IF_COPY(query, 1);
873 PG_RETURN_FLOAT4(res);
877 ts_rankcd_tt(PG_FUNCTION_ARGS)
879 TSVector txt = PG_GETARG_TSVECTOR(0);
880 TSQuery query = PG_GETARG_TSQUERY(1);
883 res = calc_rank_cd(getWeights(NULL), txt, query, DEF_NORM_METHOD);
885 PG_FREE_IF_COPY(txt, 0);
886 PG_FREE_IF_COPY(query, 1);
887 PG_RETURN_FLOAT4(res);