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

   1 #include "config.h"
   2 #include <stdio.h>
   3 #include <string.h>
   4
   5 /**
   6  * strgrp - group/cluster similar strings.
   7  *
   8  * strgrp uses the Longest Common Subsequence (LCS) algorithm[1] to cluster
   9  * similar strings. It is governed by a threshold which is compared against
  10  * the computed normalised LCS length for all known groups.
  11  *
  12  * As a coarse and not entirely accurate summary, strgrp takes the following
  13  * steps:
  14  *
  15  * 1. For all known strings, calculate the normalised LCS value against the
  16  * input string
  17  *
  18  * 2. Find the maximum normalised LCS value and associated group
  19  *
  20  * 3. If the calculated maximum normalised LCS value exceeds the configured
  21  * threshold add the input string to the group, otherwise create a new group
  22  *
  23  * The clustering operation is expensive; LCS on its own is computationally
  24  * O(mn) on its two input strings and optimally requires O(min(m,n)) memory. In
  25  * general each input string should be compared against all known strings,
  26  * giving O(n^2) behaviour of the clustering algorithm on top of the O(mn) LCS
  27  * similarity measurement.
  28  *
  29  * strgrp tries to battle this complexity on several fronts:
  30  *
  31  * 1. Coarse reduction of the required comparisons. Each group has a 'key',
  32  * which is the string that triggered the creation of the group. Input strings
  33  * are only compared against group keys rather than all known strings, reducing
  34  * the complexity to the current number of groups rather than all known
  35  * strings. Note due the pathological case where the number of groups is equal
  36  * to the number of known strings the algorithm still  has O(n^2) computational
  37  * complexity
  38  *
  39  * 2. Elimination of LCS computations that will never breach the configured
  40  * threshold. This property can be measured from the length of the input
  41  * strings, and a negative result avoids invoking the O(mn) behaviour of LCS
  42  *
  43  * 3. Caching of input strings and their associated group. By incurring the
  44  * cost of a map's string hash function we may eliminate all calls to the LCS
  45  * function for exact matches, potentially reducing the insertion to a
  46  * constant-time operation.
  47  *
  48  * 4. Whilst the data dependencies of LCS prevent internally parallel
  49  * implementations, LCS as a function can be applied in parallel. The code
  50  * uses OpenMP to automatically distribute scoring of the input string
  51  * against group keys across a number of threads.
  52  *
  53  * [1] https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
  54  *
  55  * License: LGPL
  56  * Author: Andrew Jeffery <andrew@aj.id.au>
  57  *
  58  * Example:
  59  *     FILE *f;
  60  *     char *buf;
  61  *     struct strgrp *ctx;
  62  *     struct strgrp_iter *iter;
  63  *     const struct strgrp_grp *grp;
  64  *     struct strgrp_grp_iter *grp_iter;
  65  *     const struct strgrp_item *item;
  66  *
  67  *     f = fdopen(0, "r");
  68  *     #define BUF_SIZE 512
  69  *     buf = malloc(BUF_SIZE);
  70  *     ctx = strgrp_new(0.85);
  71  *     while(fgets(buf, BUF_SIZE, f)) {
  72  *         buf[strcspn(buf, "\r\n")] = '\0';
  73  *         if (!strgrp_add(ctx, buf, NULL)) {
  74  *             printf("Failed to classify %s\n", buf);
  75  *         }
  76  *     }
  77  *
  78  *     // Re-implement something similar to strgrp_print() via API as an
  79  *     // example
  80  *     iter = strgrp_iter_new(ctx);
  81  *     while(NULL != (grp = strgrp_iter_next(iter))) {
  82  *         printf("%s\n", strgrp_grp_key(grp));
  83  *         grp_iter = strgrp_grp_iter_new(grp);
  84  *         while(NULL != (item = strgrp_grp_iter_next(grp_iter))) {
  85  *              printf("\t%s\n", strgrp_item_key(item));
  86  *         }
  87  *         strgrp_grp_iter_free(grp_iter);
  88  *     }
  89  *
  90  *     strgrp_iter_free(iter);
  91  *     strgrp_free(ctx);
  92  *     free(buf);
  93  *     fclose(f);
  94  */
  95 int main(int argc, char *argv[]) {
  96     if (argc != 2) {
  97         return 1;
  98     }
  99
 100     if (strcmp(argv[1], "depends") == 0) {
 101         printf("ccan/darray\n");
 102         printf("ccan/stringmap\n");
 103         printf("ccan/tal\n");
 104         printf("ccan/tal/str\n");
 105         return 0;
 106     }
 107
 108     if (strcmp(argv[1], "testdepends") == 0) {
 109         printf("ccan/str\n");
 110         return 0;
 111     }
 112
 113 #if HAVE_OPENMP
 114     if (strcmp(argv[1], "cflags") == 0) {
 115         printf("-fopenmp\n");
 116         return 0;
 117     }
 118 #endif
 119
 120     return 1;
 121 }