util/snippet.c

   1 /* $Id: snippet.c,v 1.13 2007-08-21 11:06:47 adam Exp $
   2    Copyright (C) 1995-2007
   3    Index Data ApS
   4
   5 This file is part of the Zebra server.
   6
   7 Zebra is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with this program; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20
  21 */
  22
  23 #include <stddef.h>
  24 #include <string.h>
  25 #include <yaz/nmem.h>
  26 #include <yaz/log.h>
  27 #include <idzebra/snippet.h>
  28
  29 struct zebra_snippets {
  30     NMEM nmem;
  31     zebra_snippet_word *front;
  32     zebra_snippet_word *tail;
  33 };
  34
  35 zebra_snippets *zebra_snippets_create(void)
  36 {
  37     NMEM nmem = nmem_create();
  38     zebra_snippets *l = nmem_malloc(nmem, sizeof(*l));
  39     l->nmem = nmem;
  40     l->front = l->tail = 0;
  41     return l;
  42 }
  43
  44 void zebra_snippets_destroy(zebra_snippets *l)
  45 {
  46     if (l)
  47         nmem_destroy(l->nmem);
  48 }
  49
  50 void zebra_snippets_append(zebra_snippets *l,
  51                            zint seqno, int ws, int ord, const char *term)
  52 {
  53     zebra_snippets_append_match(l, seqno, ws, ord, term, strlen(term), 0);
  54 }
  55
  56 void zebra_snippets_appendn(zebra_snippets *l,
  57                             zint seqno, int ws, int ord, const char *term,
  58                             size_t term_len)
  59 {
  60     zebra_snippets_append_match(l, seqno, ws, ord, term, term_len, 0);
  61 }
  62
  63
  64 void zebra_snippets_append_match(zebra_snippets *l,
  65                                  zint seqno, int ws, int ord,
  66                                  const char *term, size_t term_len,
  67                                  int match)
  68 {
  69     struct zebra_snippet_word *w = nmem_malloc(l->nmem, sizeof(*w));
  70
  71     w->next = 0;
  72     w->prev = l->tail;
  73     if (l->tail)
  74     {
  75         l->tail->next = w;
  76     }
  77     else
  78     {
  79         l->front = w;
  80     }
  81     l->tail = w;
  82
  83     w->seqno = seqno;
  84     w->ws = ws;
  85     w->ord = ord;
  86     w->term = nmem_malloc(l->nmem, term_len+1);
  87     memcpy(w->term, term, term_len);
  88     w->term[term_len] = '\0';
  89     w->match = match;
  90     w->mark = 0;
  91 }
  92
  93 zebra_snippet_word *zebra_snippets_list(zebra_snippets *l)
  94 {
  95     return l->front;
  96 }
  97
  98 const zebra_snippet_word *zebra_snippets_constlist(const zebra_snippets *l)
  99 {
 100     return l->front;
 101 }
 102
 103 void zebra_snippets_log(const zebra_snippets *l, int log_level, int all)
 104 {
 105     zebra_snippet_word *w;
 106     for (w = l->front; w; w = w->next)
 107     {
 108         if (all || w->mark)
 109             yaz_log(log_level, "term='%s'%s mark=%d seqno=" ZINT_FORMAT " ord=%d",
 110                     w->term, (w->match && !w->ws ? "*" : ""), w->mark,
 111                     w->seqno, w->ord);
 112     }
 113 }
 114
 115 zebra_snippets *zebra_snippets_window(const zebra_snippets *doc,
 116                                       const zebra_snippets *hit,
 117                                       int window_size)
 118 {
 119     int ord = -1;
 120     zebra_snippets *result = zebra_snippets_create();
 121     if (window_size == 0)
 122         window_size = 1000000;
 123
 124     while(1)
 125     {
 126         zint window_start;
 127         zint first_seq_no_best_window = 0;
 128         zint last_seq_no_best_window = 0;
 129         int number_best_window = 0;
 130         const zebra_snippet_word *hit_w, *doc_w;
 131         int min_ord = 0; /* not set yet */
 132
 133         for (hit_w = zebra_snippets_constlist(hit); hit_w; hit_w = hit_w->next)
 134             if (hit_w->ord > ord &&
 135                 (min_ord == 0 || hit_w->ord < min_ord))
 136             {
 137                 min_ord = hit_w->ord;
 138             }
 139         if (min_ord == 0)
 140             break;
 141         ord = min_ord;
 142
 143         for (hit_w = zebra_snippets_constlist(hit); hit_w; hit_w = hit_w->next)
 144         {
 145             if (hit_w->ord == ord)
 146             {
 147                 const zebra_snippet_word *look_w = hit_w;
 148                 int number_this = 0;
 149                 zint seq_no_last = 0;
 150                 while (look_w && look_w->seqno < hit_w->seqno + window_size)
 151                 {
 152                     if (look_w->ord == ord)
 153                     {
 154                         seq_no_last = look_w->seqno;
 155                         number_this++;
 156                     }
 157                     look_w = look_w->next;
 158                 }
 159                 if (number_this > number_best_window)
 160                 {
 161                     number_best_window = number_this;
 162                     first_seq_no_best_window = hit_w->seqno;
 163                     last_seq_no_best_window = seq_no_last;
 164                 }
 165             }
 166         }
 167         yaz_log(YLOG_DEBUG, "ord=%d", ord);
 168         yaz_log(YLOG_DEBUG, "first_seq_no_best_window=" ZINT_FORMAT,
 169                 first_seq_no_best_window);
 170         yaz_log(YLOG_DEBUG, "last_seq_no_best_window=" ZINT_FORMAT,
 171                 last_seq_no_best_window);
 172         yaz_log(YLOG_DEBUG, "number_best_window=%d", number_best_window);
 173
 174         window_start = (first_seq_no_best_window + last_seq_no_best_window -
 175                         window_size) / 2;
 176         for (doc_w = zebra_snippets_constlist(doc); doc_w; doc_w = doc_w->next)
 177             if (doc_w->ord == ord
 178                 && doc_w->seqno >= window_start
 179                 && doc_w->seqno < window_start + window_size)
 180             {
 181                 int match = 0;
 182                 for (hit_w = zebra_snippets_constlist(hit); hit_w;
 183                      hit_w = hit_w->next)
 184                 {
 185                     if (hit_w->ord == ord && hit_w->seqno == doc_w->seqno)
 186
 187                     {
 188                         match = 1;
 189                         break;
 190                     }
 191                 }
 192                 zebra_snippets_append_match(result, doc_w->seqno,
 193                                             doc_w->ws,
 194                                             ord, doc_w->term,
 195                                             strlen(doc_w->term), match);
 196             }
 197     }
 198     return result;
 199 }
 200
 201 static void zebra_snippets_clear(zebra_snippets *sn)
 202 {
 203     zebra_snippet_word *w;
 204
 205     for (w = zebra_snippets_list(sn); w; w = w->next)
 206     {
 207         w->mark = 0;
 208         w->match = 0;
 209     }
 210 }
 211
 212 void zebra_snippets_ring(zebra_snippets *doc, const zebra_snippets *hit,
 213                          int before, int after)
 214 {
 215     int ord = -1;
 216
 217     zebra_snippets_clear(doc);
 218     while (1)
 219     {
 220         const zebra_snippet_word *hit_w;
 221         zebra_snippet_word *doc_w;
 222         int min_ord = 0; /* not set yet */
 223
 224         for (hit_w = zebra_snippets_constlist(hit); hit_w; hit_w = hit_w->next)
 225             if (hit_w->ord > ord &&
 226                 (min_ord == 0 || hit_w->ord < min_ord))
 227             {
 228                 min_ord = hit_w->ord;
 229             }
 230         if (min_ord == 0)
 231             break;
 232         ord = min_ord;
 233
 234         for (hit_w = zebra_snippets_constlist(hit); hit_w; hit_w = hit_w->next)
 235         {
 236             if (hit_w->ord == ord)
 237             {
 238                 for (doc_w = zebra_snippets_list(doc); doc_w; doc_w = doc_w->next)
 239                 {
 240                     if (doc_w->ord == ord && doc_w->seqno == hit_w->seqno
 241                         && !doc_w->ws)
 242                     {
 243                         doc_w->match = 1;
 244                         doc_w->mark = 1;
 245                         break;
 246                     }
 247
 248                 }
 249                 /* mark following terms */
 250                 if (doc_w)
 251                 {
 252                     zebra_snippet_word *w = doc_w->next;
 253                     while (w)
 254                         if (w->ord == ord
 255                             && hit_w->seqno - before < w->seqno
 256                             && hit_w->seqno + after > w->seqno)
 257                         {
 258                             w->mark = 1;
 259                             w = w->next;
 260                         }
 261                         else
 262                             break;
 263                 }
 264                 /* mark preceding terms */
 265                 if (doc_w)
 266                 {
 267                     zebra_snippet_word *w = doc_w->prev;
 268                     while (w)
 269                         if (w->ord == ord
 270                             && hit_w->seqno - before < w->seqno
 271                             && hit_w->seqno + after > w->seqno)
 272                         {
 273                             w->mark = 1;
 274                             w = w->prev;
 275                         }
 276                         else
 277                             break;
 278                 }
 279             }
 280         }
 281     }
 282 }
 283
 284
 285 /*
 286  * Local variables:
 287  * c-basic-offset: 4
 288  * indent-tabs-mode: nil
 289  * End:
 290  * vim: shiftwidth=4 tabstop=8 expandtab
 291  */
 292