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 <limits.h>
  20 #include <math.h>
  21 #include <stdbool.h>
  22 #include <stdint.h>
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include "ccan/darray/darray.h"
  27 #include "ccan/stringmap/stringmap.h"
  28 #include "ccan/tal/tal.h"
  29 #include "ccan/tal/str/str.h"
  30 #include "strgrp.h"
  31 #include "config.h"
  32
  33 #if HAVE_OPENMP
  34 #include <omp.h>
  35 #else
  36 #define omp_get_max_threads() 1
  37 #define omp_get_thread_num() 0
  38 #endif
  39
  40 #define CHAR_N_VALUES (1 << CHAR_BIT)
  41
  42 typedef darray(struct strgrp_grp *) darray_grp;
  43 typedef darray(struct strgrp_item *) darray_item;
  44
  45 typedef stringmap(struct strgrp_grp *) stringmap_grp;
  46
  47 struct grp_score {
  48     struct strgrp_grp *grp;
  49     double score;
  50 };
  51
  52 struct cosvec {
  53     const char *str;
  54     int16_t pop[CHAR_N_VALUES];
  55 };
  56
  57 typedef darray(struct grp_score *) darray_score;
  58
  59 struct strgrp {
  60     double threshold;
  61     stringmap_grp known;
  62     unsigned int n_grps;
  63     darray_grp grps;
  64     struct grp_score *scores;
  65     int32_t n_cosvecs;
  66     struct cosvec *cosvecs;
  67 };
  68
  69 struct strgrp_iter {
  70     const struct strgrp *ctx;
  71     int i;
  72 };
  73
  74 struct strgrp_grp {
  75     const char *key;
  76     size_t key_len;
  77     darray_item items;
  78     int32_t n_items;
  79 };
  80
  81 struct strgrp_grp_iter {
  82     const struct strgrp_grp *grp;
  83     int i;
  84 };
  85
  86 struct strgrp_item {
  87     const char *key;
  88     void *value;
  89 };
  90
  91
  92 /* String vector cosine similarity[1]
  93  *
  94  * [1] http://blog.nishtahir.com/2015/09/19/fuzzy-string-matching-using-cosine-similarity/
  95  */
  96
  97 static inline void
  98 strpopcnt(struct cosvec *ctx) {
  99     const char *c;
 100     memset(ctx->pop, 0, CHAR_N_VALUES * sizeof(int16_t));
 101     for(c = ctx->str; *c; c++) {
 102         assert(*c >= 0);
 103         ctx->pop[(unsigned char)*c]++;
 104     }
 105 }
 106
 107 static inline double
 108 strcossim(struct cosvec *avec, struct cosvec *bvec) {
 109     strpopcnt(avec);
 110     strpopcnt(bvec);
 111     int32_t saibi = 0;
 112     int32_t sai2 = 0;
 113     int32_t sbi2 = 0;
 114     size_t i;
 115     for (i = 0; i < CHAR_N_VALUES; i++) {
 116         saibi += avec->pop[i] * bvec->pop[i];
 117         sai2 += avec->pop[i] * avec->pop[i];
 118         sbi2 += bvec->pop[i] * bvec->pop[i];
 119     }
 120     return saibi / (sqrt(sai2) * sqrt(sbi2));
 121 }
 122
 123 /* Low-cost filter functions */
 124
 125 static inline bool
 126 should_grp_score_cos(const struct strgrp *const ctx, struct cosvec *const avec,
 127         struct cosvec *const bvec) {
 128     return ctx->threshold <= strcossim(avec, bvec);
 129 }
 130
 131 static inline bool
 132 should_grp_score_len(const struct strgrp *const ctx,
 133         const struct strgrp_grp *const grp, const char *const str) {
 134     const size_t strl = strlen(str);
 135     const size_t keyl = grp->key_len;
 136     double sr =  strl / keyl;
 137     if (1 < sr) {
 138         sr = 1 / sr;
 139     }
 140     return ctx->threshold <= sr;
 141 }
 142
 143 /* Scoring - Longest Common Subsequence[2]
 144  *
 145  * [2] https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
 146  */
 147 #define ROWS 2
 148
 149 static inline int cmi(int i, int j) {
 150     return ROWS * j + i;
 151 }
 152
 153 static inline int16_t
 154 lcs(const char *const a, const char *const b) {
 155     const int lb = strlen(b);
 156     const int lbp1 = lb + 1;
 157     int16_t *const lookup = calloc(ROWS * lbp1, sizeof(int16_t));
 158     if (!lookup) {
 159         return -1;
 160     }
 161     int ia, ib;
 162     for (ia = (strlen(a) - 1); ia >= 0; ia--) {
 163         const char iav = a[ia];
 164         for (ib = lb - 1; ib >= 0; ib--) {
 165             const char ibv = b[ib];
 166             const int ial = (ia + 1) & 1; // ia last
 167             const int iac = ia & 1; // ia current
 168             const int ibl = ib + 1; // ib last
 169             // don't need separate "ib current" as it's just ib
 170             if (iav == ibv) {
 171                 lookup[cmi(iac, ib)] = 1 + lookup[cmi(ial, ibl)];
 172             } else {
 173                 const int16_t valb = lookup[cmi(ial, ib)];
 174                 const int16_t vabl = lookup[cmi(iac, ibl)];
 175                 lookup[cmi(iac, ib)] = (valb > vabl) ? valb : vabl;
 176             }
 177         }
 178     }
 179     int16_t result = lookup[0];
 180     free(lookup);
 181     return result;
 182 }
 183
 184 #undef ROWS
 185
 186 static inline double
 187 nlcs(const char *const a, const char *const b) {
 188     const double lcss = lcs(a, b);
 189     return 2 * lcss / (strlen(a) + strlen(b));
 190 }
 191
 192 static inline double
 193 grp_score(const struct strgrp_grp *const grp, const char *const str) {
 194     return nlcs(grp->key, str);
 195 }
 196
 197 /* Structure management */
 198
 199 static struct strgrp_item *
 200 new_item(tal_t *const tctx, const char *const str, void *const data) {
 201     struct strgrp_item *i = talz(tctx, struct strgrp_item);
 202     if (!i) {
 203         return NULL;
 204     }
 205     i->key = tal_strdup(i, str);
 206     i->value = data;
 207     return i;
 208 }
 209
 210 static bool
 211 add_item(struct strgrp_grp *const ctx, const char *const str,
 212         void *const data) {
 213     struct strgrp_item *i = new_item(ctx, str, data);
 214     if (!i) {
 215         return false;
 216     }
 217     darray_push(ctx->items, i);
 218     ctx->n_items++;
 219     return true;
 220 }
 221
 222 static void
 223 free_grp(struct strgrp_grp *grp) {
 224     darray_free(grp->items);
 225 }
 226
 227 static struct strgrp_grp *
 228 new_grp(tal_t *const tctx, const char *const str, void *const data) {
 229     struct strgrp_grp *b = talz(tctx, struct strgrp_grp);
 230     if (!b) {
 231         return NULL;
 232     }
 233     b->key = tal_strdup(b, str);
 234     b->key_len = strlen(str);
 235     b->n_items = 0;
 236     darray_init(b->items);
 237     tal_add_destructor(b, free_grp);
 238     if (!add_item(b, str, data)) {
 239         return tal_free(b);
 240     }
 241     return b;
 242 }
 243
 244 static struct strgrp_grp *
 245 add_grp(struct strgrp *const ctx, const char *const str,
 246         void *const data) {
 247     struct strgrp_grp *b = new_grp(ctx, str, data);
 248     if (!b) {
 249         return NULL;
 250     }
 251     darray_push(ctx->grps, b);
 252     ctx->n_grps++;
 253     if (ctx->scores) {
 254         if (!tal_resize(&ctx->scores, ctx->n_grps)) {
 255             return NULL;
 256         }
 257     } else {
 258         ctx->scores = tal_arr(ctx, struct grp_score, ctx->n_grps);
 259         if (!ctx->scores) {
 260             return NULL;
 261         }
 262     }
 263     return b;
 264 }
 265
 266 struct strgrp *
 267 strgrp_new(const double threshold) {
 268     struct strgrp *ctx = talz(NULL, struct strgrp);
 269     ctx->threshold = threshold;
 270     stringmap_init(ctx->known, NULL);
 271     // n threads compare strings
 272     ctx->n_cosvecs = 2 * omp_get_max_threads();
 273     ctx->cosvecs = tal_arrz(ctx, struct cosvec, ctx->n_cosvecs);
 274     darray_init(ctx->grps);
 275     return ctx;
 276 }
 277
 278 static inline void
 279 cache(struct strgrp *const ctx, struct strgrp_grp *const grp,
 280         const char *const str) {
 281     *(stringmap_enter(ctx->known, str)) = grp;
 282 }
 283
 284 static inline struct cosvec *
 285 tl_avec(struct strgrp *ctx) {
 286     return &ctx->cosvecs[omp_get_thread_num()];
 287 }
 288
 289 static inline struct cosvec *
 290 tl_bvec(struct strgrp *ctx) {
 291     return &ctx->cosvecs[omp_get_thread_num() + 1];
 292 }
 293
 294 static struct strgrp_grp *
 295 grp_for(struct strgrp *const ctx, const char *const str) {
 296     if (!ctx->n_grps) {
 297         return NULL;
 298     }
 299     {
 300         struct strgrp_grp **const grp = stringmap_lookup(ctx->known, str);
 301         if (grp) {
 302             return *grp;
 303         }
 304     }
 305     int i;
 306 // Keep ccanlint happy in reduced feature mode
 307 #if HAVE_OPENMP
 308     #pragma omp parallel for schedule(dynamic)
 309 #endif
 310     for (i = 0; i < ctx->n_grps; i++) {
 311         ctx->scores[i].grp = darray_item(ctx->grps, i);
 312         if (should_grp_score_len(ctx, ctx->scores[i].grp, str)) {
 313             tl_avec(ctx)->str = ctx->scores[i].grp->key;
 314             tl_bvec(ctx)->str = str;
 315             if (should_grp_score_cos(ctx, tl_avec(ctx), tl_bvec(ctx))) {
 316                 ctx->scores[i].score = grp_score(ctx->scores[i].grp, str);
 317             } else {
 318                 ctx->scores[i].score = 0;
 319             }
 320         } else {
 321             ctx->scores[i].score = 0;
 322         }
 323     }
 324     struct grp_score *max = NULL;
 325     for (i = 0; i < ctx->n_grps; i++) {
 326         if (!max || ctx->scores[i].score > max->score) {
 327             max = &(ctx->scores[i]);
 328         }
 329     }
 330     return (max && max->score >= ctx->threshold) ? max->grp : NULL;
 331 }
 332
 333 const struct strgrp_grp *
 334 strgrp_grp_for(struct strgrp *const ctx, const char *const str) {
 335     return grp_for(ctx, str);
 336 }
 337
 338 const struct strgrp_grp *
 339 strgrp_add(struct strgrp *const ctx, const char *const str,
 340         void *const data) {
 341     bool inserted = false;
 342     struct strgrp_grp *pick = grp_for(ctx, str);
 343     if (pick) {
 344         inserted = add_item(pick, str, data);
 345     } else {
 346         pick = add_grp(ctx, str, data);
 347         inserted = (NULL != pick);
 348     }
 349     if (inserted) {
 350         assert(NULL != pick);
 351         cache(ctx, pick, str);
 352     }
 353     return pick;
 354 }
 355
 356 struct strgrp_iter *
 357 strgrp_iter_new(struct strgrp *const ctx) {
 358     struct strgrp_iter *iter = talz(ctx, struct strgrp_iter);
 359     if (!iter) {
 360         return NULL;
 361     }
 362     iter->ctx = ctx;
 363     iter->i = 0;
 364     return iter;
 365 }
 366
 367 const struct strgrp_grp *
 368 strgrp_iter_next(struct strgrp_iter *const iter) {
 369     return (iter->ctx->n_grps == iter->i) ?
 370         NULL : darray_item(iter->ctx->grps, iter->i++);
 371 }
 372
 373 void
 374 strgrp_iter_free(struct strgrp_iter *const iter) {
 375     tal_free(iter);
 376 }
 377
 378 struct strgrp_grp_iter *
 379 strgrp_grp_iter_new(const struct strgrp_grp *const grp) {
 380     struct strgrp_grp_iter *iter = talz(grp, struct strgrp_grp_iter);
 381     if (!iter) {
 382         return NULL;
 383     }
 384     iter->grp = grp;
 385     iter->i = 0;
 386     return iter;
 387 }
 388
 389 const struct strgrp_item *
 390 strgrp_grp_iter_next(struct strgrp_grp_iter *const iter) {
 391     return (iter->grp->n_items == iter->i) ?
 392         NULL : darray_item(iter->grp->items, iter->i++);
 393 }
 394
 395 void
 396 strgrp_grp_iter_free(struct strgrp_grp_iter *iter) {
 397     tal_free(iter);
 398 }
 399
 400 const char *
 401 strgrp_grp_key(const struct strgrp_grp *const grp) {
 402     return grp->key;
 403 }
 404
 405 const char *
 406 strgrp_item_key(const struct strgrp_item *const item) {
 407     return item->key;
 408 }
 409
 410 void *
 411 strgrp_item_value(const struct strgrp_item *const item) {
 412     return item->value;
 413 }
 414
 415 void
 416 strgrp_free(struct strgrp *const ctx) {
 417     darray_free(ctx->grps);
 418     stringmap_free(ctx->known);
 419     tal_free(ctx);
 420 }
 421
 422 void
 423 strgrp_free_cb(struct strgrp *const ctx, void (*cb)(void *data)) {
 424     struct strgrp_grp **grp;
 425     struct strgrp_item **item;
 426     darray_foreach(grp, ctx->grps) {
 427         darray_foreach(item, (*grp)->items) {
 428             cb((*item)->value);
 429         }
 430     }
 431     strgrp_free(ctx);
 432 }
 433
 434 static void
 435 print_item(const struct strgrp_item *item) {
 436     printf("\t%s\n", item->key);
 437 }
 438
 439 static void
 440 print_grp(const struct strgrp_grp *const grp) {
 441     struct strgrp_item **item;
 442     printf("%s:\n", grp->key);
 443     darray_foreach(item, grp->items) {
 444         print_item(*item);
 445     }
 446     printf("\n");
 447 }
 448
 449 void
 450 strgrp_print(const struct strgrp *const ctx) {
 451     struct strgrp_grp **grp;
 452     darray_foreach(grp, ctx->grps) {
 453         print_grp(*grp);
 454     }
 455 }