util/snippet.c

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