Re-estabslished rank-1. Gets same order of results, but slightly different
[idzebra-moved-to-github.git] / index / livcode.c
1 /*
2   
3 The University of Liverpool
4
5 Modifications to Zebra 1.1 / YAZ 1.7 to enable ranking
6 by attribute weight.
7
8 Copyright (c) 2001-2002 The University of Liverpool.  All
9 rights reserved.
10
11 Licensed under the Academic Free License version 1.1.
12 http://opensource.org/licenses/academic.php
13
14 $Id: livcode.c,v 1.4 2004-10-26 15:32:11 heikki Exp $
15
16 */
17
18 #ifdef SKIPTHIS  /* Need to fix the interface - FIXME */
19
20 #include <stdlib.h>
21 #include <stdio.h>
22 #ifdef WIN32
23 #include <process.h>
24 #else
25 #include <unistd.h>
26 #endif
27 #include <assert.h>
28
29 #include "index.h"
30 #include "zserver.h"
31
32 /*
33 ** These functions/routines 
34 ** 1. reads in and builds a linked list of rank attr/rank score pairs
35 ** 2. expand a simple query into a paired list of complex/simple nodes.
36 */
37
38 typedef struct rstype
39 {
40     struct rstype *next_rsnode ;
41     int rank ;
42     int score ;
43     char *rankstr ;
44 } rsnode, *refrsnode ;
45
46 refrsnode start_rsnode = NULL ;
47
48 /*
49 ** Function/Routine prototypes
50 */
51 static int        search_for_score( char *rankstr ) ;
52 static char      *search_for_rankstr( int rank ) ;
53 static int        search_for_rank( int rank ) ;
54 static refrsnode  set_rsnode( int rank, int score ) ;
55 static int        read_zrank_file(ZebraHandle zh) ;
56
57 static void       convert_simple2complex(ZebraHandle zh, Z_RPNStructure *rpnstruct ) ;
58 static void       walk_complex_query(ZebraHandle zh, Z_RPNStructure *rpnstruct ) ;
59 static Z_Complex *expand_query(ZebraHandle zh, Z_Operand *thisop ) ;
60 static Z_Complex *set_1complex_1operand( Z_Complex *comp,Z_Operand *simp ) ;
61 static Z_Complex *set_2operands( Z_Operand *sim1,Z_Operand *sim2 ) ;
62 static Z_Operand *set_operand( Z_Operand *thisop, int newattr ) ;
63 static int        check_operand_attrs( Z_Operand *thisop ) ;
64
65 /*
66 ** search_for_score()
67 ** given a rank-string traverse down the linked list ;
68 ** return its score if found otherwise return -1.
69 */
70 int search_for_score( char *rankstr )
71 {
72     refrsnode node = start_rsnode ;
73     int rank ;
74   
75     if ( sscanf( rankstr,"%d",&rank ) )
76     {
77         while ( node )
78         {
79             if ( node->rank == rank ) return node->score ;
80             node = node->next_rsnode ;
81         }
82     }
83     return -1 ;
84 }
85
86 /*
87 ** search_for_rankstr()
88 ** given a rank traverse down the linked list ; 
89 ** return its string if found otherwise return NULL.
90 */
91 char *search_for_rankstr( int rank )
92 {
93     refrsnode node = start_rsnode ;
94   
95     while ( node )
96     {
97         if ( node->rank == rank ) return node->rankstr ;
98         node = node->next_rsnode ;
99     }
100     return "rank" ;
101 }
102
103 /*
104 ** search_for_rank()
105 ** given a rank traverse down the linked list ;
106 ** return 1 if found otherwise return 0.
107 */
108 int search_for_rank( int rank )
109 {
110     refrsnode node = start_rsnode ;
111
112     while ( node )
113     {
114         if ( node->rank == rank ) return 1 ;
115         node = node->next_rsnode ;
116     }
117     return 0 ;
118 }
119
120 /*
121 ** set_rsnode()
122 ** given a rank and a score, build the rest of the rsnode structure.
123 */
124 refrsnode set_rsnode( int rank, int score )
125 {
126 #define BUFFMAX 128
127     refrsnode node = (refrsnode)malloc( sizeof(rsnode) ) ;
128     char buff[BUFFMAX] ;
129
130     node->next_rsnode = NULL  ;
131     node->rank        = rank  ;
132     node->score       = score ;
133
134     sprintf( buff,"%d",rank ) ;
135     node->rankstr     = (char *)malloc( strlen(buff)+1 ) ;
136     strcpy( node->rankstr, buff ) ;
137
138     return node ;
139 }
140
141 /*
142 ** read_zrank_file(zh)
143 ** read in the rankfile and build the rank/score linked list ; 
144 ** return 0 : can't open the zebra config. file
145 ** return 0 : can't find the rankfile entry in the zebra config. file
146 ** return 0 : can't open the rankfile itself
147 ** return the number of distinct ranks read in.
148 */
149 int read_zrank_file(ZebraHandle zh)
150 {
151 #define LINEMAX 256
152     char line[ LINEMAX ] ;
153     char rname[ LINEMAX ] ;
154     char *lineptr ;
155     FILE *ifd ;
156     int rank = 0 ;
157     int score = 0 ;
158     int numranks = 0 ;
159  
160     /*
161     ** open the zebra configuration file and look for the "rankfile:"
162     ** entry which contains the path/name of the rankfile
163     */
164     
165     const char *rankfile = res_get_def(zh->res, "rankfile", 0);
166     const char *profilePath = res_get_def(zh->res, "profilePath",
167                                           DEFAULT_PROFILE_PATH);
168
169     if (!rankfile)
170     {
171         yaz_log(LOG_LOG, "rankfile entry not found in config file" ) ;
172         return 0 ;
173     }
174     ifd = yaz_path_fopen(profilePath, rankfile, "r" ) ;
175     if ( ifd )
176     {
177         while ( (lineptr = fgets( line,LINEMAX,ifd )) )
178         {
179             if ( sscanf( lineptr,"rankfile: %s", rname ) == 1 )
180                 rankfile  = rname ;
181         }
182
183         /*
184         ** open the rankfile and read the rank/score pairs
185         ** ignore 1016 
186         ** ignore duplicate ranks 
187         ** ignore ranks without +ve scores
188         */
189         if ( rankfile )
190         { 
191             if ( !(ifd = fopen( rankfile, "r" )) )
192             {
193                 logf( LOG_LOG, "unable to open rankfile %s",rankfile ) ;
194                 return 0;
195             }
196      
197             while ( (lineptr = fgets( line,LINEMAX,ifd )) )
198             {
199                 sscanf( lineptr,"%d : %d", &rank,&score ) ;
200                 if ( ( score > 0 ) && ( rank != 1016 ) )
201                 {
202                     refrsnode new_rsnode ;
203     
204                     if ( search_for_rank( rank ) == 0 )
205                     {
206                         new_rsnode              = set_rsnode( rank,score ) ;
207                         new_rsnode->next_rsnode = start_rsnode ;
208                         start_rsnode            = new_rsnode ;
209                         numranks++ ;
210                     }
211                 }
212             }
213         }
214         else 
215         {
216             yaz_log(LOG_WARN|LOG_ERRNO, "unable to open config file (%s)",
217                     rankfile);
218         }
219     }
220     return numranks ;
221 }
222
223 /*
224 ** set_operand() 
225 ** build an operand "node" - hav to make a complete copy of thisop and 
226 ** then insert newattr in the appropriate place
227 ** 
228 */
229 Z_Operand *set_operand( Z_Operand *thisop, int newattr )
230 {
231     Z_Operand            *operand ;
232     Z_AttributesPlusTerm *attributesplusterm ;
233     Z_AttributeList      *attributelist ;
234     Z_AttributeElement   *attributeelement ;
235     Z_AttributeElement   *attrptr ;
236     Z_AttributeElement   **attrptrptr ;
237     Z_Term               *term ;
238     Odr_oct              *general ;
239     int i ;
240
241     operand            = (Z_Operand *) 
242                          malloc( sizeof( Z_Operand ) ) ;
243     attributesplusterm = (Z_AttributesPlusTerm *)
244                          malloc( sizeof( Z_AttributesPlusTerm ) ) ;
245     attributelist      = (Z_AttributeList *)
246                          malloc( sizeof( Z_AttributeList ) ) ;
247     attributeelement   = (Z_AttributeElement *)
248                          malloc( sizeof( Z_AttributeElement ) ) ;
249     term               = (Z_Term *)
250                          malloc( sizeof( Z_Term ) ) ;
251     general            = (Odr_oct *)
252                          malloc( sizeof( Odr_oct ) ) ;
253
254     operand->which                 = Z_Operand_APT ;
255     operand->u.attributesPlusTerm  = attributesplusterm ;
256
257     attributesplusterm->attributes = attributelist ;
258     attributesplusterm->term       = term ;
259
260     attributelist->num_attributes  = thisop->u.attributesPlusTerm->
261                                      attributes->num_attributes ;
262
263     attrptr = (Z_AttributeElement *) malloc( sizeof(Z_AttributeElement) *
264                                              attributelist->num_attributes ) ;
265     attrptrptr = (Z_AttributeElement **) malloc( sizeof(Z_AttributeElement) *
266                                            attributelist->num_attributes ) ; 
267
268     attributelist->attributes = attrptrptr ;
269
270     for ( i = 0 ; i < attributelist->num_attributes ; i++ )
271     {
272         *attrptr = *thisop->u.attributesPlusTerm->attributes->attributes[i] ;
273
274          attrptr->attributeType  = (int *)malloc( sizeof(int *) ) ;
275         *attrptr->attributeType  = *thisop->u.attributesPlusTerm->attributes->
276                                     attributes[i]->attributeType;
277
278          attrptr->value.numeric  = (int *)malloc( sizeof(int *) ) ;
279         *attrptr->value.numeric  = *thisop->u.attributesPlusTerm->attributes->
280                                     attributes[i]->value.numeric;
281
282         if ( (*attrptr->attributeType == 1) && 
283              (*attrptr->value.numeric == 1016) )
284         {
285             *attrptr->value.numeric = newattr ;
286         }
287         *attrptrptr++ = attrptr++ ;
288     }
289
290     term->which     = Z_Term_general ;
291     term->u.general = general ;
292
293     general->len  = thisop->u.attributesPlusTerm->term->u.general->len ;
294     general->size = thisop->u.attributesPlusTerm->term->u.general->size ;
295     general->buf  = malloc( general->size ) ;
296     strcpy( general->buf,
297             thisop->u.attributesPlusTerm->term->u.general->buf ) ;
298
299     return operand ;
300 }
301
302 /*
303 ** set_2operands()
304 ** build a complex "node" with two (simple) operand "nodes" as branches
305 */
306 Z_Complex *set_2operands( Z_Operand *sim1,Z_Operand *sim2 )
307 {
308     Z_Complex *top        ;
309     Z_RPNStructure *s1    ;
310     Z_RPNStructure *s2    ;
311     Z_Operator *roperator ;
312
313     top       = (Z_Complex *)     malloc( sizeof( Z_Complex      ) ) ;
314     s1        = (Z_RPNStructure *)malloc( sizeof( Z_RPNStructure ) ) ;
315     s2        = (Z_RPNStructure *)malloc( sizeof( Z_RPNStructure ) ) ;
316     roperator = (Z_Operator *)    malloc( sizeof( Z_Operator     ) ) ;
317
318     top->roperator          = roperator     ;
319     top->roperator->which   = Z_Operator_or ;
320     top->roperator->u.op_or = odr_nullval() ;
321
322     top->s1                 = s1                    ;
323     top->s1->which          = Z_RPNStructure_simple ;
324     top->s1->u.simple       = sim1                  ;
325
326     top->s2                 = s2                    ;
327     top->s2->which          = Z_RPNStructure_simple ;
328     top->s2->u.simple       = sim2                  ;
329
330     return top ;
331 }
332
333 /*
334 ** set_1complex_1operand()
335 ** build a complex "node" with a complex "node" branch and an 
336 ** operand "node" branch
337 */
338 Z_Complex *set_1complex_1operand( Z_Complex *comp,Z_Operand *simp )
339 {
340     Z_Complex *top        ;
341     Z_RPNStructure *s1    ;
342     Z_RPNStructure *s2    ;
343     Z_Operator *roperator ;
344
345     top       = (Z_Complex *)     malloc( sizeof( Z_Complex      ) ) ;
346     s1        = (Z_RPNStructure *)malloc( sizeof( Z_RPNStructure ) ) ;
347     s2        = (Z_RPNStructure *)malloc( sizeof( Z_RPNStructure ) ) ;
348     roperator = (Z_Operator *)    malloc( sizeof( Z_Operator     ) ) ;
349
350     top->roperator          = roperator     ;
351     top->roperator->which   = Z_Operator_or ;
352     top->roperator->u.op_or = odr_nullval() ;
353
354     top->s1                 = s1                     ;
355     top->s1->which          = Z_RPNStructure_complex ;
356     top->s1->u.complex      = comp                   ;
357
358     top->s2                 = s2                     ;
359     top->s2->which          = Z_RPNStructure_simple  ;
360     top->s2->u.simple       = simp                   ;
361
362     return top ;
363 }
364
365 /*
366 ** expand_query()
367 ** expand a simple query into a number of complex queries
368 */
369 Z_Complex *expand_query(ZebraHandle zh, Z_Operand *thisop )
370 {
371     Z_Complex *top ;
372     int numattrs = 0 ;
373
374     /*
375     ** start_rsnode will be set if we have already read the rankfile 
376     ** so don't bother again but we need to know the number of attributes
377     ** in the linked list so traverse it again to find out how many.
378     */
379     if ( start_rsnode )
380     {
381         refrsnode node = start_rsnode ;
382         while ( node )
383         {
384             numattrs++ ;
385             node = node->next_rsnode ;
386         }
387     } 
388
389     /*
390     ** only expand the query if there are 2 or more attributes 
391     */
392     if ( numattrs >= 2 )
393     {
394         refrsnode node = start_rsnode ;
395         int attr1 ;
396         int attr2 ;
397
398         attr1 = node->rank ; node = node->next_rsnode ;
399         attr2 = node->rank ; node = node->next_rsnode ;
400
401         /*
402         ** this is the special case and has to be done first because the 
403         ** last complex node in the linear list has two simple nodes whereas 
404         ** all the others have a complex and a simple.
405         */
406         top = set_2operands( set_operand( thisop,attr1 ),
407                              set_operand( thisop,attr2 ) ) ;
408
409         /*
410         ** do the rest as complex/simple pairs
411         */
412         while ( node )
413         {
414             attr1 = node->rank ; node = node->next_rsnode ;
415             top = set_1complex_1operand( top,set_operand( thisop,attr1 ) ) ;
416         }
417         /*
418         ** finally add the 1016 rank attribute at the top of the tree
419         */
420         top = set_1complex_1operand( top,set_operand( thisop,1016 ) ) ;
421
422         return top ;
423     }
424     else return NULL ;
425 }
426
427 /*
428 ** check_operand_attrs()
429 ** loop through the attributes of a particular operand 
430 ** return 1 if (type==1 && value==1016) && (type==2 && value==102) 
431 ** otherwise return 0
432 */
433 int check_operand_attrs( Z_Operand *thisop ) 
434 {
435     Z_AttributeElement *attrptr ;
436     int cond1 = 0 ;
437     int cond2 = 0 ;
438     int numattrs ;
439     int i ;
440
441     numattrs = thisop->u.attributesPlusTerm->attributes->num_attributes ;
442
443     for ( i = 0 ; i < numattrs ; i++ )
444     {
445         attrptr = thisop->u.attributesPlusTerm->attributes->attributes[i] ;
446
447         if ( (*attrptr->attributeType == 1) && 
448              (*attrptr->value.numeric == 1016) )
449             cond1 = 1 ;
450
451         if ( (*attrptr->attributeType == 2) && 
452              (*attrptr->value.numeric == 102) )
453             cond2 = 1 ;
454     }
455
456     return (cond1 & cond2) ;
457 }
458
459 /*
460 ** convert_simple2complex()
461 ** 
462 */
463 void convert_simple2complex(ZebraHandle zh, Z_RPNStructure *rpnstruct )
464 {
465     Z_Complex *complex = NULL ;                                         
466     Z_Operand *operand = rpnstruct->u.simple ;                          
467
468     if ( check_operand_attrs( operand ) )
469     {
470         complex = expand_query(zh, operand ) ;
471
472         if ( complex )
473         {
474             /*
475             ** Everything is complete so replace the original
476             ** operand with the newly built complex structure
477             ** This is it ... no going back!!
478             */
479             rpnstruct->which     = Z_RPNStructure_complex ;
480             rpnstruct->u.complex = complex ;
481         }
482     }                                                                       
483 }
484
485 /*
486 ** walk_complex_query()
487 ** recursively traverse the tree expanding any simple queries we find
488 */
489 void walk_complex_query(ZebraHandle zh, Z_RPNStructure *rpnstruct )
490 {
491     if ( rpnstruct->which == Z_RPNStructure_simple )
492     {
493         convert_simple2complex(zh, rpnstruct ) ;
494     }
495     else
496     {
497         walk_complex_query(zh, rpnstruct->u.complex->s1 ) ;
498         walk_complex_query(zh, rpnstruct->u.complex->s2 ) ;
499     }
500 }
501
502 void zebra_livcode_transform(ZebraHandle zh, Z_RPNQuery *query)
503 {
504     /*
505     ** Got a search request,
506     ** 1. if it is a simple query, see if it suitable for expansion
507     **    i.e. the attributes are of the form ...
508     **    (type==1 && value==1016) && (type==2 && value==102)
509     ** or
510     ** 2. if it is complex, traverse the complex query tree and expand
511     **    any simples simples as above
512     */
513 #if LIV_CODE
514     Z_RPNStructure *rpnstruct = query->RPNStructure ;
515     
516     if ( rpnstruct->which == Z_RPNStructure_simple )
517     {
518         convert_simple2complex(zh, rpnstruct ) ;
519     }
520     else if ( rpnstruct->which == Z_RPNStructure_complex )
521     {
522         walk_complex_query(zh, rpnstruct ) ;
523     }
524 #endif
525 }
526
527
528 struct rank_class_info {
529     int dummy;
530 };
531
532 struct rank_term_info {
533     int local_occur;
534     int global_occur;
535     int global_inv;
536     int rank_flag;
537 };
538
539 struct rank_set_info {
540     int last_pos;
541     int no_entries;
542     int no_rank_entries;
543     NMEM nmem;
544     struct rank_term_info *entries;
545 };
546
547 static int log2_int (unsigned g)
548 {
549     int n = 0;
550     while ((g = g>>1))
551         n++;
552     return n;
553 }
554
555 /*
556  * create: Creates/Initialises this rank handler. This routine is 
557  *  called exactly once. The routine returns the class_handle.
558  */
559 static void *create (ZebraHandle zh)
560 {
561     struct rank_class_info *ci = (struct rank_class_info *)
562         xmalloc (sizeof(*ci));
563
564     logf (LOG_DEBUG, "livrank create");
565
566     read_zrank_file(zh) ;
567
568     return ci;
569 }
570
571 /*
572  * destroy: Destroys this rank handler. This routine is called
573  *  when the handler is no longer needed - i.e. when the server
574  *  dies. The class_handle was previously returned by create.
575  */
576 static void destroy (struct zebra_register *reg, void *class_handle)
577 {
578     struct rank_class_info *ci = (struct rank_class_info *) class_handle;
579
580     logf (LOG_DEBUG, "livrank destroy");
581     xfree (ci);
582 }
583
584
585 /*
586  * begin: Prepares beginning of "real" ranking. Called once for
587  *  each result set. The returned handle is a "set handle" and
588  *  will be used in each of the handlers below.
589  */
590 static void *begin (struct zebra_register *reg, void *class_handle, 
591                     RSET rset, NMEM nmem)
592 {
593     struct rank_set_info *si = (struct rank_set_info *) xmalloc (sizeof(*si));
594     int i;
595
596     logf (LOG_DEBUG, "livrank begin");
597     /* FIXME - Now that we don't have term counts in rsets, what do we */
598     /* do about this ??? */
599     si->no_entries = 0; /* rset->no_rset_terms; */ /* FIXME ??? */
600     si->no_rank_entries = 0;
601     si->nmem=nmem;
602     si->entries = (struct rank_term_info *)
603         xmalloc (sizeof(*si->entries)*si->no_entries);
604     for (i = 0; i < si->no_entries; i++)
605     {
606         const char *flags = ""; /* rset->rset_terms[i]->flags; *//* FIXME ???*/
607         int g = 0; /* rset->rset_terms[i]->nn; */ /* FIXME ??? */
608         const char *cp = strstr(flags, ",u=");
609
610         si->entries[i].rank_flag = 1;
611         if (cp)
612         {
613             char *t = search_for_rankstr(atoi(cp+3));
614             if (t)
615                 si->entries[i].rank_flag = search_for_score(t) ;
616         }
617         if ( si->entries[i].rank_flag )
618             (si->no_rank_entries)++;
619
620         si->entries[i].local_occur = 0;
621         si->entries[i].global_occur = g;
622         si->entries[i].global_inv = 32 - log2_int (g);
623         logf (LOG_DEBUG, "-------- %d ------", 32 - log2_int (g));
624     }
625     return si;
626 }
627
628 /*
629  * end: Terminates ranking process. Called after a result set
630  *  has been ranked.
631  */
632 static void end (struct zebra_register *reg, void *set_handle)
633 {
634     struct rank_set_info *si = (struct rank_set_info *) set_handle;
635     logf (LOG_DEBUG, "livrank end");
636     xfree (si->entries);
637     xfree (si);
638 }
639
640 /*
641  * add: Called for each word occurence in a result set. This routine
642  *  should be as fast as possible. This routine should "incrementally"
643  *  update the score.
644  */
645 static void add (void *set_handle, int seqno, int term_index)
646 {
647     struct rank_set_info *si = (struct rank_set_info *) set_handle;
648     logf (LOG_DEBUG, "rank-1 add seqno=%d term_index=%d", seqno, term_index);
649     si->last_pos = seqno;
650     si->entries[term_index].local_occur++;
651 }
652
653 /*
654  * calc: Called for each document in a result. This handler should 
655  *  produce a score based on previous call(s) to the add handler. The
656  *  score should be between 0 and 1000. If score cannot be obtained
657  *  -1 should be returned.
658  */
659 static int calc (void *set_handle, zint sysno)
660 {
661     int i, lo, divisor, score = 0;
662     struct rank_set_info *si = (struct rank_set_info *) set_handle;
663
664     logf (LOG_DEBUG, "livrank calc sysno=" ZINT_FORMAT, sysno);
665
666     if (!si->no_rank_entries)
667         return -1;
668     for (i = 0; i < si->no_entries; i++)
669     {
670         score += si->entries[i].local_occur * si->entries[i].rank_flag ;
671     }
672     for (i = 0; i < si->no_entries; i++)
673         if (si->entries[i].rank_flag && (lo = si->entries[i].local_occur))
674             score += (8+log2_int (lo)) * si->entries[i].global_inv;
675     score *= 34;
676     divisor = si->no_rank_entries * (8+log2_int (si->last_pos/si->no_entries));
677     score = score / divisor;
678     if (score > 1000)
679         score = 1000;
680     for (i = 0; i < si->no_entries; i++)
681         si->entries[i].local_occur = 0;
682     return score;
683 }
684
685 /*
686  * Pseudo-meta code with sequence of calls as they occur in a
687  * server. Handlers are prefixed by --:
688  *
689  *     server init
690  *     -- create
691  *     foreach search
692  *        rank result set
693  *        -- begin
694  *        foreach record
695  *           foreach word
696  *              -- add
697  *           -- calc
698  *        -- end
699  *     -- destroy
700  *     server close
701  */
702
703 static struct rank_control rank_control = {
704     "livrank",
705     create,
706     destroy,
707     begin,
708     end,
709     calc,
710     add,
711 };
712  
713 struct rank_control *rankliv_class = &rank_control;
714 #endif
715