git.ozlabs.org Git - ccan/blob - ccan/strgrp/strgrp.c

   1 /*
   2     Group similar strings
   3     Copyright (C) 2014  Andrew Jeffery <andrew@aj.id.au>
   4
   5     This program is free software: you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation, either version 3 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU Lesser General Public License for more details.
  14
  15     You should have received a copy of the GNU Lesser General Public License
  16     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18 #include <assert.h>
  19 #include <stdbool.h>
  20 #include <stdint.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include "ccan/darray/darray.h"
  24 #include "ccan/stringmap/stringmap.h"
  25 #include "ccan/tal/tal.h"
  26 #include "ccan/tal/str/str.h"
  27 #include "strgrp.h"
  28 #include "config.h"
  29
  30 typedef darray(struct strgrp_grp *) darray_grp;
  31 typedef darray(struct strgrp_item *) darray_item;
  32
  33 typedef stringmap(struct strgrp_grp *) stringmap_grp;
  34
  35 struct grp_score {
  36     struct strgrp_grp *grp;
  37     double score;
  38 };
  39
  40 typedef darray(struct grp_score *) darray_score;
  41
  42 struct strgrp {
  43     double threshold;
  44     stringmap_grp known;
  45     unsigned int n_grps;
  46     darray_grp grps;
  47     struct grp_score *scores;
  48 };
  49
  50 struct strgrp_iter {
  51     const struct strgrp *ctx;
  52     int i;
  53 };
  54
  55 struct strgrp_grp {
  56     const char *key;
  57     size_t key_len;
  58     darray_item items;
  59     int32_t n_items;
  60 };
  61
  62 struct strgrp_grp_iter {
  63     const struct strgrp_grp *grp;
  64     int i;
  65 };
  66
  67 struct strgrp_item {
  68     const char *key;
  69     void *value;
  70 };
  71
  72 #define ROWS 2
  73
  74 static inline int cmi(int i, int j) {
  75     return ROWS * j + i;
  76 }
  77
  78 static inline int16_t
  79 lcs(const char *const a, const char *const b) {
  80     const int lb = strlen(b);
  81     const int lbp1 = lb + 1;
  82     int16_t *const lookup = calloc(ROWS * lbp1, sizeof(int16_t));
  83     if (!lookup) {
  84         return -1;
  85     }
  86     int ia, ib;
  87     for (ia = (strlen(a) - 1); ia >= 0; ia--) {
  88         const char iav = a[ia];
  89         for (ib = lb - 1; ib >= 0; ib--) {
  90             const char ibv = b[ib];
  91             const int ial = (ia + 1) & 1; // ia last
  92             const int iac = ia & 1; // ia current
  93             const int ibl = ib + 1; // ib last
  94             // don't need separate "ib current" as it's just ib
  95             if (iav == ibv) {
  96                 lookup[cmi(iac, ib)] = 1 + lookup[cmi(ial, ibl)];
  97             } else {
  98                 const int16_t valb = lookup[cmi(ial, ib)];
  99                 const int16_t vabl = lookup[cmi(iac, ibl)];
 100                 lookup[cmi(iac, ib)] = (valb > vabl) ? valb : vabl;
 101             }
 102         }
 103     }
 104     int16_t result = lookup[0];
 105     free(lookup);
 106     return result;
 107 }
 108
 109 #undef ROWS
 110
 111 static inline double
 112 nlcs(const char *const a, const char *const b) {
 113     const double lcss = lcs(a, b);
 114     return 2 * lcss / (strlen(a) + strlen(b));
 115 }
 116
 117 static bool
 118 should_grp_score(const struct strgrp *const ctx,
 119         const struct strgrp_grp *const grp, const char *const str) {
 120     const size_t strl = strlen(str);
 121     const size_t keyl = grp->key_len;
 122     double sr =  strl / keyl;
 123     if (1 < sr) {
 124         sr = 1 / sr;
 125     }
 126     return ctx->threshold <= sr;
 127 }
 128
 129 static inline double
 130 grp_score(const struct strgrp_grp *const grp, const char *const str) {
 131     return nlcs(grp->key, str);
 132 }
 133
 134 static struct strgrp_item *
 135 new_item(tal_t *const tctx, const char *const str, void *const data) {
 136     struct strgrp_item *i = talz(tctx, struct strgrp_item);
 137     if (!i) {
 138         return NULL;
 139     }
 140     i->key = tal_strdup(i, str);
 141     i->value = data;
 142     return i;
 143 }
 144
 145 static bool
 146 add_item(struct strgrp_grp *const ctx, const char *const str,
 147         void *const data) {
 148     struct strgrp_item *i = new_item(ctx, str, data);
 149     if (!i) {
 150         return false;
 151     }
 152     darray_push(ctx->items, i);
 153     ctx->n_items++;
 154     return true;
 155 }
 156
 157 static void
 158 free_grp(struct strgrp_grp *grp) {
 159     darray_free(grp->items);
 160 }
 161
 162 static struct strgrp_grp *
 163 new_grp(tal_t *const tctx, const char *const str, void *const data) {
 164     struct strgrp_grp *b = talz(tctx, struct strgrp_grp);
 165     if (!b) {
 166         return NULL;
 167     }
 168     b->key = tal_strdup(b, str);
 169     b->key_len = strlen(str);
 170     b->n_items = 0;
 171     darray_init(b->items);
 172     tal_add_destructor(b, free_grp);
 173     if (!add_item(b, str, data)) {
 174         return tal_free(b);
 175     }
 176     return b;
 177 }
 178
 179 static struct strgrp_grp *
 180 add_grp(struct strgrp *const ctx, const char *const str,
 181         void *const data) {
 182     struct strgrp_grp *b = new_grp(ctx, str, data);
 183     if (!b) {
 184         return NULL;
 185     }
 186     darray_push(ctx->grps, b);
 187     ctx->n_grps++;
 188     if (ctx->scores) {
 189         if (!tal_resize(&ctx->scores, ctx->n_grps)) {
 190             return NULL;
 191         }
 192     } else {
 193         ctx->scores = tal_arr(ctx, struct grp_score, ctx->n_grps);
 194         if (!ctx->scores) {
 195             return NULL;
 196         }
 197     }
 198     return b;
 199 }
 200
 201 struct strgrp *
 202 strgrp_new(const double threshold) {
 203     struct strgrp *ctx = talz(NULL, struct strgrp);
 204     ctx->threshold = threshold;
 205     stringmap_init(ctx->known, NULL);
 206     darray_init(ctx->grps);
 207     return ctx;
 208 }
 209
 210 static inline void
 211 cache(struct strgrp *const ctx, struct strgrp_grp *const grp,
 212         const char *const str) {
 213     *(stringmap_enter(ctx->known, str)) = grp;
 214 }
 215
 216 static struct strgrp_grp *
 217 grp_for(struct strgrp *const ctx, const char *const str) {
 218     if (!ctx->n_grps) {
 219         return NULL;
 220     }
 221     {
 222         struct strgrp_grp **const grp = stringmap_lookup(ctx->known, str);
 223         if (grp) {
 224             return *grp;
 225         }
 226     }
 227     int i;
 228 // Keep ccanlint happy in reduced feature mode
 229 #if HAVE_OPENMP
 230     #pragma omp parallel for schedule(dynamic)
 231 #endif
 232     for (i = 0; i < ctx->n_grps; i++) {
 233         ctx->scores[i].grp = darray_item(ctx->grps, i);
 234         const bool ss = should_grp_score(ctx, ctx->scores[i].grp, str);
 235         ctx->scores[i].score = ss ? grp_score(ctx->scores[i].grp, str) : 0;
 236     }
 237     struct grp_score *max = NULL;
 238     for (i = 0; i < ctx->n_grps; i++) {
 239         if (!max || ctx->scores[i].score > max->score) {
 240             max = &(ctx->scores[i]);
 241         }
 242     }
 243     return (max && max->score >= ctx->threshold) ? max->grp : NULL;
 244 }
 245
 246 const struct strgrp_grp *
 247 strgrp_grp_for(struct strgrp *const ctx, const char *const str) {
 248     return grp_for(ctx, str);
 249 }
 250
 251 const struct strgrp_grp *
 252 strgrp_add(struct strgrp *const ctx, const char *const str,
 253         void *const data) {
 254     bool inserted = false;
 255     struct strgrp_grp *pick = grp_for(ctx, str);
 256     if (pick) {
 257         inserted = add_item(pick, str, data);
 258     } else {
 259         pick = add_grp(ctx, str, data);
 260         inserted = (NULL != pick);
 261     }
 262     if (inserted) {
 263         assert(NULL != pick);
 264         cache(ctx, pick, str);
 265     }
 266     return pick;
 267 }
 268
 269 struct strgrp_iter *
 270 strgrp_iter_new(struct strgrp *const ctx) {
 271     struct strgrp_iter *iter = talz(ctx, struct strgrp_iter);
 272     if (!iter) {
 273         return NULL;
 274     }
 275     iter->ctx = ctx;
 276     iter->i = 0;
 277     return iter;
 278 }
 279
 280 const struct strgrp_grp *
 281 strgrp_iter_next(struct strgrp_iter *const iter) {
 282     return (iter->ctx->n_grps == iter->i) ?
 283         NULL : darray_item(iter->ctx->grps, iter->i++);
 284 }
 285
 286 void
 287 strgrp_iter_free(struct strgrp_iter *const iter) {
 288     tal_free(iter);
 289 }
 290
 291 struct strgrp_grp_iter *
 292 strgrp_grp_iter_new(const struct strgrp_grp *const grp) {
 293     struct strgrp_grp_iter *iter = talz(grp, struct strgrp_grp_iter);
 294     if (!iter) {
 295         return NULL;
 296     }
 297     iter->grp = grp;
 298     iter->i = 0;
 299     return iter;
 300 }
 301
 302 const struct strgrp_item *
 303 strgrp_grp_iter_next(struct strgrp_grp_iter *const iter) {
 304     return (iter->grp->n_items == iter->i) ?
 305         NULL : darray_item(iter->grp->items, iter->i++);
 306 }
 307
 308 void
 309 strgrp_grp_iter_free(struct strgrp_grp_iter *iter) {
 310     tal_free(iter);
 311 }
 312
 313 const char *
 314 strgrp_grp_key(const struct strgrp_grp *const grp) {
 315     return grp->key;
 316 }
 317
 318 const char *
 319 strgrp_item_key(const struct strgrp_item *const item) {
 320     return item->key;
 321 }
 322
 323 void *
 324 strgrp_item_value(const struct strgrp_item *const item) {
 325     return item->value;
 326 }
 327
 328 void
 329 strgrp_free(struct strgrp *const ctx) {
 330     darray_free(ctx->grps);
 331     stringmap_free(ctx->known);
 332     tal_free(ctx);
 333 }
 334
 335 void
 336 strgrp_free_cb(struct strgrp *const ctx, void (*cb)(void *data)) {
 337     struct strgrp_grp **grp;
 338     struct strgrp_item **item;
 339     darray_foreach(grp, ctx->grps) {
 340         darray_foreach(item, (*grp)->items) {
 341             cb((*item)->value);
 342         }
 343     }
 344     strgrp_free(ctx);
 345 }
 346
 347 #include <stdio.h>
 348
 349 static void
 350 print_item(const struct strgrp_item *item) {
 351     printf("\t%s\n", item->key);
 352 }
 353
 354 static void
 355 print_grp(const struct strgrp_grp *const grp) {
 356     struct strgrp_item **item;
 357     printf("%s:\n", grp->key);
 358     darray_foreach(item, grp->items) {
 359         print_item(*item);
 360     }
 361     printf("\n");
 362 }
 363
 364 void
 365 strgrp_print(const struct strgrp *const ctx) {
 366     struct strgrp_grp **grp;
 367     darray_foreach(grp, ctx->grps) {
 368         print_grp(*grp);
 369     }
 370 }