Quick string search to find an element of a string array that matches a givven pattern

For each sheet that you process, you can build a suffix array as described in this article . Before starting your search, read the sheet, find the starting lines (as integer indices in the sheet buffer), create a suffix array and sort it as described in the article.

Now if you are looking for lines where a pattern occurs, such as "table", you can search for the next entry after "table" and the next entry after "tablf", match where you moved the right letter, odometer style.

If both indices are the same, there is no match. If they are different, you will get a list of pointers in the sheet:

"tab. And now ..."
----------------------------------------------------------------
"table and ..."                0x0100ab30
"table water for ..."          0x0100132b
"tablet computer ..."          0x01000208
----------------------------------------------------------------
"tabloid reporter ..."

      

        
        
        
      

    

This will give you a list of pointers from which, by subtracting the base pointer of the sheet buffer, you can get the offsets of the integers. Comparison with the starting lines will give you the line numbers corresponding to those pointers. (The line numbers are sorted, so you can do a binary search here.)

The memory overhead is an array of pointers that are the same size as the leaf buffer, so for 30,000 lines of 200 characters, this would be about 48MB on a 64-bit machine. (The overhead of row indexes is negligible.)

Sorting the array will take a long time, but only done once for each sheet.

Edit . The idea seems to work well. I have executed it and can scan a dictionary of about 130,000 words in a text file of almost 600k in one second:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define die(...) exit((fprintf(stderr, "Fatal: " __VA_ARGS__), \
    putc(10, stderr), 1))



typedef struct Sheet Sheet;    

struct Sheet {
    size_t size;    /* Number of chars */
    char *buf;      /* Null-terminated char buffer */
    char **ptr;     /* Pointers into char buffer */
    size_t nline;   /* number of lines */
    int *line;      /* array of offset of line beginnings */
    size_t naux;    /* size of scratch array */
    char **aux;     /* scratch array */
};


/*
 *      Count occurrence of c in zero-terminated string p.
 */
size_t strcount(const char *p, int c)
{
    size_t n = 0;

    for (;;) {
        p = strchr(p, c);
        if (p == NULL) return n;
        p++;
        n++;        
    }

    return 0;
}

/*
 *      String comparison via pointers to strings.
 */
int pstrcmp(const void *a, const void *b)
{
    const char *const *aa = a;
    const char *const *bb = b;

    return strcmp(*aa, *bb);
}

/*
 *      Pointer comparison.
 */
int ptrcmp(const void *a, const void *b)
{
    const char *const *aa = a;
    const char *const *bb = b;

    if (*aa == *bb) return 0;   
    return (*aa < *bb) ? -1 : 1;
}

/*
 *      Create and prepare a sheet, i.e. a text file to search.
 */
Sheet *sheet_new(const char *fn)
{
    Sheet *sheet;
    FILE *f = fopen(fn, "r");
    size_t n;
    int last;
    char *p;
    char **pp;

    if (f == NULL) die("Couldn't open %s", fn);

    sheet = malloc(sizeof(*sheet));
    if (sheet == NULL) die("Allocation failed");

    fseek(f, 0, SEEK_END);
    sheet->size = ftell(f);
    fseek(f, 0, SEEK_SET);

    sheet->buf = malloc(sheet->size + 1);
    sheet->ptr = malloc(sheet->size * sizeof(*sheet->ptr));

    if (sheet->buf == NULL) die("Allocation failed");
    if (sheet->ptr == NULL) die("Allocation failed");

    fread(sheet->buf, 1, sheet->size, f);
    sheet->buf[sheet->size] = '\0';
    fclose(f);

    sheet->nline = strcount(sheet->buf, '\n');
    sheet->line = malloc(sheet->nline * sizeof(*sheet->line));

    sheet->aux = NULL;
    sheet->naux = 0;

    n = 0;
    last = 0;
    p = sheet->buf;
    pp = sheet->ptr;
    while (*p) {
        *pp++ = p;
        if (*p == '\n') {
            sheet->line[n++] = last;
            last = p - sheet->buf + 1;
        }
        p++;
    }

    qsort(sheet->ptr, sheet->size, sizeof(*sheet->ptr), pstrcmp);

    return sheet;
}

/*
 *      Clean up sheet.
 */
void sheet_delete(Sheet *sheet)
{
    free(sheet->buf);
    free(sheet->ptr);
    free(sheet->line);
    free(sheet->aux);
    free(sheet);
}

/*
 *      Binary range search for string pointers.
 */
static char **pstr_bsearch(const char *key,
    char **arr, size_t high)
{
    size_t low = 0;

    while (low < high) {
        size_t mid = (low + high) / 2;
        int diff = strcmp(key, arr[mid]);

        if (diff < 0) high = mid;
        else low = mid + 1;
    }

    return arr + low;
}

/*
 *      Binary range search for line offsets.
 */
static const int *int_bsearch(int key, const int *arr, size_t high)
{
    size_t low = 0;

    while (low < high) {
        size_t mid = (low + high) / 2;
        int diff = key - arr[mid];

        if (diff < 0) high = mid;
        else low = mid + 1;
    }

    if (low < 1) return NULL;
    return arr + low - 1;
}

/*
 *      Find occurrences of the string key in the sheet. Returns the
 *      number of lines in which the key occurs and assigns up to
 *      max lines to the line array. (If max is 0, line may be NULL.)
 */
int sheet_find(Sheet *sheet, char *key,
    int line[], int max)
{
    char **begin, **end;
    int n = 0;
    size_t i, m;
    size_t last;

    begin = pstr_bsearch(key, sheet->ptr, sheet->size);
    if (begin == NULL) return 0;

    key[strlen(key) - 1]++;
    end = pstr_bsearch(key, sheet->ptr, sheet->size);
    key[strlen(key) - 1]--;
    if (end == NULL) return 0;
    if (end == begin) return 0;

    m = end - begin;
    if (m > sheet->naux) {
        if (sheet->naux == 0) sheet->naux = 0x100;
        while (sheet->naux < m) sheet->naux *= 2;
        sheet->aux = realloc(sheet->aux, sheet->naux * sizeof(*sheet->aux));
        if (sheet->aux == NULL) die("Re-allocation failed");        
    }

    memcpy(sheet->aux, begin, m * sizeof(*begin));
    qsort(sheet->aux, m, sizeof(*begin), ptrcmp);

    last = 0;
    for (i = 0; i < m; i++) {
        int offset = sheet->aux[i] - sheet->buf;
        const int *p;

        p = int_bsearch(offset, sheet->line + last, sheet->nline - last);

        if (p) {
            if (n < max) line[n] = p - sheet->line;
            last = p - sheet->line + 1;
            n++;
        }
    }

    return n;
}

/*
 *      Example client code
 */
int main(int argc, char **argv)
{
    Sheet *sheet;
    FILE *f;

    if (argc != 3) die("Usage: %s patterns corpus", *argv);

    sheet = sheet_new(argv[2]);

    f = fopen(argv[1], "r");
    if (f == NULL) die("Can't open %s.", argv[1]);
    for (;;) {
        char str[80];
        int line[50];
        int i, n;

        if (fgets(str, sizeof(str), f) == NULL) break;
        strtok(str, "\n");
        n = sheet_find(sheet, str, line, 50);
        printf("%8d %s\n", n, str);

        if (n > 50) n = 50;
        for (i = 0; i < n; i++) printf("    [%d] %d\n", i, line[i] + 1);
    }
    fclose(f);

    sheet_delete(sheet);

    return 0;
}

      

        
        
        
      

    

The implementation has its rough edges, but it works. I don't particularly like the scratch array and additional sorting by the found range of pointers, but it turns out that even sorting a large array of suffixes doesn't take too long.

You can expand this solution to more sheets if you like.