How to remove duplicate words from free‑text in C

1 Answer

0 votes
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

/*
    removeDuplicateWordsFreeText (C version)

    Removes duplicate words from free text:
    - Case‑insensitive comparison
    - Preserves original casing of first occurrence
    - Splits on ANY non‑letter sequence
    - Preserves original order
    - Efficient O(n) using a simple hash set

    Strategy:
    1. Trim outer whitespace.
    2. Split on ANY non‑letter sequence using manual scanning.
    3. Lowercase each word for comparison.
    4. Keep only first occurrence.
    5. Reassemble into a space‑separated string.
*/

/* ---------------------------------------------------------------
   Trim whitespace from both ends
--------------------------------------------------------------- */
char *trim(char *s) {
    while (isspace((unsigned char)*s)) s++;
    if (*s == 0) return s;

    char *end = s + strlen(s) - 1;
    while (end > s && isspace((unsigned char)*end)) end--;
    end[1] = '\0';
    
    return s;
}

/* ---------------------------------------------------------------
   Convert string to lowercase (copy)
--------------------------------------------------------------- */
char *toLowerCopy(const char *s) {
    size_t len = strlen(s);
    char *out = malloc(len + 1);
    for (size_t i = 0; i < len; i++)
        out[i] = tolower((unsigned char)s[i]);
    out[len] = '\0';
    
    return out;
}

/* ---------------------------------------------------------------
   Simple hash set for strings (open addressing)
--------------------------------------------------------------- */
typedef struct {
    char **keys;
    size_t size;
} HashSet;

size_t hashString(const char *s, size_t size) {
    size_t h = 146527;
    while (*s) h = h * 33 ^ (unsigned char)*s++;
    
    return h % size;
}

HashSet *hashSetCreate(size_t size) {
    HashSet *set = malloc(sizeof(HashSet));
    set->size = size;
    set->keys = calloc(size, sizeof(char *));
    
    return set;
}

int hashSetInsert(HashSet *set, const char *key) {
    size_t idx = hashString(key, set->size);

    for (size_t i = 0; i < set->size; i++) {
        size_t pos = (idx + i) % set->size;

        if (set->keys[pos] == NULL) {
            set->keys[pos] = strdup(key);
            return 1;  // inserted
        }
        if (strcmp(set->keys[pos], key) == 0)
            return 0;  // duplicate
    }
    
    return 0;
}

void hashSetFree(HashSet *set) {
    for (size_t i = 0; i < set->size; i++)
        free(set->keys[i]);
    free(set->keys);
    free(set);
}

/* ---------------------------------------------------------------
   Split free text into words using ANY non‑letter sequence
--------------------------------------------------------------- */
char **splitWords(const char *text, int *count) {
    char *copy = strdup(text);
    char *p = copy;

    char **words = malloc(sizeof(char *) * 1024);
    int wcount = 0;

    while (*p) {
        while (*p && !isalpha((unsigned char)*p)) p++;
        if (!*p) break;

        char *start = p;
        while (*p && isalpha((unsigned char)*p)) p++;

        size_t len = p - start;
        char *word = malloc(len + 1);
        memcpy(word, start, len);
        word[len] = '\0';

        words[wcount++] = word;
    }

    free(copy);
    *count = wcount;
    
    return words;
}

/* ---------------------------------------------------------------
   Remove duplicates (case‑insensitive)
--------------------------------------------------------------- */
char *removeDuplicateWordsFreeText(const char *text) {
    char *clean = trim(strdup(text));

    int count = 0;
    char **words = splitWords(clean, &count);

    HashSet *seen = hashSetCreate(2048);

    char **unique = malloc(sizeof(char *) * count);
    int ucount = 0;

    for (int i = 0; i < count; i++) {
        char *lower = toLowerCopy(words[i]);

        if (hashSetInsert(seen, lower)) {
            unique[ucount++] = words[i];  // preserve original casing
        } else {
            free(words[i]);
        }
        free(lower);
    }

    // Build output string
    size_t total = 0;
    for (int i = 0; i < ucount; i++)
        total += strlen(unique[i]) + 1;

    char *result = malloc(total + 1);
    result[0] = '\0';

    for (int i = 0; i < ucount; i++) {
        strcat(result, unique[i]);
        if (i + 1 < ucount) strcat(result, " ");
        free(unique[i]);
    }

    free(unique);
    free(words);
    free(clean);
    hashSetFree(seen);

    return result;
}

/* ---------------------------------------------------------------
   Main
--------------------------------------------------------------- */
int main() {
    const char *input =
        "Hello, hello! This is a test. A TEST, hello universe...   "
        "UNIVERSE! Hello; ***  Is Anybody There?";

    char *output = removeDuplicateWordsFreeText(input);

    printf("%s\n", output);

    free(output);

    return 0;
}


/*
run:

Hello This is a test universe Anybody There

*/

 



answered Aug 2 by avibootz
...