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
  29 typedef darray(struct strgrp_grp *) darray_grp;
  30 typedef darray(struct strgrp_item *) darray_item;
  31
  32 typedef stringmap(struct strgrp_grp *) stringmap_grp;
  33
  34 struct grp_score {
  35     struct strgrp_grp *grp;
  36     double score;
  37 };
  38
  39 typedef darray(struct grp_score *) darray_score;
  40
  41 struct strgrp {
  42     double threshold;
  43     stringmap_grp known;
  44     unsigned int n_grps;
  45     darray_grp grps;
  46     struct grp_score *scores;
  47 };
  48
  49 struct strgrp_iter {
  50     const struct strgrp *ctx;
  51     int i;
  52 };
  53
  54 struct strgrp_grp {
  55     const char *key;
  56     size_t key_len;
  57     darray_item items;
  58     int32_t n_items;
  59 };
  60
  61 struct strgrp_grp_iter {
  62     const struct strgrp_grp *grp;
  63     int i;
  64 };
  65
  66 struct strgrp_item {
  67     const char *key;
  68     void *value;
  69 };
  70
  71 #define ROWS 2
  72
  73 static inline int cmi(int i, int j) {
  74     return ROWS * j + i;
  75 }
  76
  77 static inline int16_t
  78 lcs(const char *const a, const char *const b) {
  79     const int lb = strlen(b);
  80     const int lbp1 = lb + 1;
  81     int16_t *const lookup = calloc(ROWS * lbp1, sizeof(int16_t));
  82     if (!lookup) {
  83         return -1;
  84     }
  85     int ia, ib;
  86     for (ia = (strlen(a) - 1); ia >= 0; ia--) {
  87         const char iav = a[ia];
  88         for (ib = lb - 1; ib >= 0; ib--) {
  89             const char ibv = b[ib];
  90             const int ial = (ia + 1) & 1; // ia last
  91             const int iac = ia & 1; // ia current
  92             const int ibl = ib + 1; // ib last
  93             // don't need separate "ib current" as it's just ib
  94             if (iav == ibv) {
  95                 lookup[cmi(iac, ib)] = 1 + lookup[cmi(ial, ibl)];
  96             } else {
  97                 const int16_t valb = lookup[cmi(ial, ib)];
  98                 const int16_t vabl = lookup[cmi(iac, ibl)];
  99                 lookup[cmi(iac, ib)] = (valb > vabl) ? valb : vabl;
 100             }
 101         }
 102     }
 103     int16_t result = lookup[0];
 104     free(lookup);
 105     return result;
 106 }
 107
 108 #undef ROWS
 109
 110 static inline double
 111 nlcs(const char *const a, const char *const b) {
 112     const double lcss = lcs(a, b);
 113     return 2 * lcss / (strlen(a) + strlen(b));
 114 }
 115
 116 static bool
 117 should_grp_score(const struct strgrp *const ctx,
 118         const struct strgrp_grp *const grp, const char *const str) {
 119     const size_t strl = strlen(str);
 120     const size_t keyl = grp->key_len;
 121     double sr =  strl / keyl;
 122     if (1 < sr) {
 123         sr = 1 / sr;
 124     }
 125     return ctx->threshold <= sr;
 126 }
 127
 128 static inline double
 129 grp_score(const struct strgrp_grp *const grp, const char *const str) {
 130     return nlcs(grp->key, str);
 131 }
 132
 133 static struct strgrp_item *
 134 new_item(tal_t *const tctx, const char *const str, void *const data) {
 135     struct strgrp_item *i = talz(tctx, struct strgrp_item);
 136     if (!i) {
 137         return NULL;
 138     }
 139     i->key = tal_strdup(i, str);
 140     i->value = data;
 141     return i;
 142 }
 143
 144 static bool
 145 add_item(struct strgrp_grp *const ctx, const char *const str,
 146         void *const data) {
 147     struct strgrp_item *i = new_item(ctx, str, data);
 148     if (!i) {
 149         return false;
 150     }
 151     darray_push(ctx->items, i);
 152     ctx->n_items++;
 153     return true;
 154 }
 155
 156 static void
 157 free_grp(struct strgrp_grp *grp) {
 158     darray_free(grp->items);
 159 }
 160
 161 static struct strgrp_grp *
 162 new_grp(tal_t *const tctx, const char *const str, void *const data) {
 163     struct strgrp_grp *b = talz(tctx, struct strgrp_grp);
 164     if (!b) {
 165         return NULL;
 166     }
 167     b->key = tal_strdup(b, str);
 168     b->key_len = strlen(str);
 169     b->n_items = 0;
 170     darray_init(b->items);
 171     tal_add_destructor(b, free_grp);
 172     if (!add_item(b, str, data)) {
 173         return tal_free(b);
 174     }
 175     return b;
 176 }
 177
 178 static struct strgrp_grp *
 179 add_grp(struct strgrp *const ctx, const char *const str,
 180         void *const data) {
 181     struct strgrp_grp *b = new_grp(ctx, str, data);
 182     if (!b) {
 183         return NULL;
 184     }
 185     darray_push(ctx->grps, b);
 186     ctx->n_grps++;
 187     if (ctx->scores) {
 188         if (!tal_resize(&ctx->scores, ctx->n_grps)) {
 189             return NULL;
 190         }
 191     } else {
 192         ctx->scores = tal_arr(ctx, struct grp_score, ctx->n_grps);
 193         if (!ctx->scores) {
 194             return NULL;
 195         }
 196     }
 197     return b;
 198 }
 199
 200 struct strgrp *
 201 strgrp_new(const double threshold) {
 202     struct strgrp *ctx = talz(NULL, struct strgrp);
 203     ctx->threshold = threshold;
 204     stringmap_init(ctx->known, NULL);
 205     darray_init(ctx->grps);
 206     return ctx;
 207 }
 208
 209 static inline void
 210 cache(struct strgrp *const ctx, struct strgrp_grp *const grp,
 211         const char *const str) {
 212     *(stringmap_enter(ctx->known, str)) = grp;
 213 }
 214
 215 static struct strgrp_grp *
 216 grp_for(struct strgrp *const ctx, const char *const str) {
 217     if (!ctx->n_grps) {
 218         return NULL;
 219     }
 220     {
 221         struct strgrp_grp **const grp = stringmap_lookup(ctx->known, str);
 222         if (grp) {
 223             return *grp;
 224         }
 225     }
 226     int i;
 227     #pragma omp parallel for schedule(dynamic)
 228     for (i = 0; i < ctx->n_grps; i++) {
 229         ctx->scores[i].grp = darray_item(ctx->grps, i);
 230         const bool ss = should_grp_score(ctx, ctx->scores[i].grp, str);
 231         ctx->scores[i].score = ss ? grp_score(ctx->scores[i].grp, str) : 0;
 232     }
 233     struct grp_score *max = NULL;
 234     for (i = 0; i < ctx->n_grps; i++) {
 235         if (!max || ctx->scores[i].score > max->score) {
 236             max = &(ctx->scores[i]);
 237         }
 238     }
 239     return (max && max->score >= ctx->threshold) ? max->grp : NULL;
 240 }
 241
 242 const struct strgrp_grp *
 243 strgrp_grp_for(struct strgrp *const ctx, const char *const str) {
 244     return grp_for(ctx, str);
 245 }
 246
 247 const struct strgrp_grp *
 248 strgrp_add(struct strgrp *const ctx, const char *const str,
 249         void *const data) {
 250     bool inserted = false;
 251     struct strgrp_grp *pick = grp_for(ctx, str);
 252     if (pick) {
 253         inserted = add_item(pick, str, data);
 254     } else {
 255         pick = add_grp(ctx, str, data);
 256         inserted = (NULL != pick);
 257     }
 258     if (inserted) {
 259         assert(NULL != pick);
 260         cache(ctx, pick, str);
 261     }
 262     return pick;
 263 }
 264
 265 struct strgrp_iter *
 266 strgrp_iter_new(struct strgrp *const ctx) {
 267     struct strgrp_iter *iter = talz(ctx, struct strgrp_iter);
 268     if (!iter) {
 269         return NULL;
 270     }
 271     iter->ctx = ctx;
 272     iter->i = 0;
 273     return iter;
 274 }
 275
 276 const struct strgrp_grp *
 277 strgrp_iter_next(struct strgrp_iter *const iter) {
 278     return (iter->ctx->n_grps == iter->i) ?
 279         NULL : darray_item(iter->ctx->grps, iter->i++);
 280 }
 281
 282 void
 283 strgrp_iter_free(struct strgrp_iter *const iter) {
 284     tal_free(iter);
 285 }
 286
 287 struct strgrp_grp_iter *
 288 strgrp_grp_iter_new(const struct strgrp_grp *const grp) {
 289     struct strgrp_grp_iter *iter = talz(grp, struct strgrp_grp_iter);
 290     if (!iter) {
 291         return NULL;
 292     }
 293     iter->grp = grp;
 294     iter->i = 0;
 295     return iter;
 296 }
 297
 298 const struct strgrp_item *
 299 strgrp_grp_iter_next(struct strgrp_grp_iter *const iter) {
 300     return (iter->grp->n_items == iter->i) ?
 301         NULL : darray_item(iter->grp->items, iter->i++);
 302 }
 303
 304 void
 305 strgrp_grp_iter_free(struct strgrp_grp_iter *iter) {
 306     tal_free(iter);
 307 }
 308
 309 const char *
 310 strgrp_grp_key(const struct strgrp_grp *const grp) {
 311     return grp->key;
 312 }
 313
 314 const char *
 315 strgrp_item_key(const struct strgrp_item *const item) {
 316     return item->key;
 317 }
 318
 319 void *
 320 strgrp_item_value(const struct strgrp_item *const item) {
 321     return item->value;
 322 }
 323
 324 void
 325 strgrp_free(struct strgrp *const ctx) {
 326     darray_free(ctx->grps);
 327     stringmap_free(ctx->known);
 328     tal_free(ctx);
 329 }
 330
 331 void
 332 strgrp_free_cb(struct strgrp *const ctx, void (*cb)(void *data)) {
 333     struct strgrp_grp **grp;
 334     struct strgrp_item **item;
 335     darray_foreach(grp, ctx->grps) {
 336         darray_foreach(item, (*grp)->items) {
 337             cb((*item)->value);
 338         }
 339     }
 340     strgrp_free(ctx);
 341 }
 342
 343 #include <stdio.h>
 344
 345 static void
 346 print_item(const struct strgrp_item *item) {
 347     printf("\t%s\n", item->key);
 348 }
 349
 350 static void
 351 print_grp(const struct strgrp_grp *const grp) {
 352     struct strgrp_item **item;
 353     printf("%s:\n", grp->key);
 354     darray_foreach(item, grp->items) {
 355         print_item(*item);
 356     }
 357     printf("\n");
 358 }
 359
 360 void
 361 strgrp_print(const struct strgrp *const ctx) {
 362     struct strgrp_grp **grp;
 363     darray_foreach(grp, ctx->grps) {
 364         print_grp(*grp);
 365     }
 366 }