如何实现14万词字典的单词去重并写入uniq数组？

Hey there! Let's tackle this problem of deduplicating your 140k-word dictionary and capturing duplicates. I'll walk you through two practical approaches in C—one that's straightforward to implement, and another optimized for speed with large datasets.

Approach 1: Sort & Deduplicate (Simple, Easy to Implement) #

This method leverages sorting to group duplicate words together, then we can iterate through the sorted list to extract unique entries and flag duplicates. It's great if you don't want to mess with custom data structures like hash tables.

Step-by-Step Implementation #

1. First, read all your words into a dynamic array (all_words). Make sure you track the total number of words (word_count).
2. Use qsort to sort the array—this will cluster identical words next to each other.
3. Traverse the sorted array, skipping duplicates while adding unique words to your uniq array, and print duplicates as you find them.

Code Example #

First, add the missing headers you'll need:

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

Then the comparison function for sorting:

// Comparison function for qsort (compares two strings)
int compare_words(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

Now the deduplication logic:

// Assume all_words is your array of 140k words, word_count is the total number of words
char **uniq = malloc(word_count * sizeof(char *));
if (!uniq) {
    perror("Failed to allocate memory for uniq array");
    exit(EXIT_FAILURE);
}

int uniq_count = 0;
for (int i = 0; i < word_count; ) {
    char *current_word = all_words[i];
    // Add the unique word to our uniq array
    uniq[uniq_count++] = strdup(current_word); // Use strdup to copy, or re-use the pointer if safe

    // Skip and log all duplicates of current_word
    int j = i + 1;
    while (j < word_count && strcmp(all_words[j], current_word) == 0) {
        printf("Duplicate found: %s %s\n", current_word, all_words[j]);
        j++;
    }
    i = j; // Jump to the next unique word
}

// Optional: Shrink the uniq array to its actual size to save memory
uniq = realloc(uniq, uniq_count * sizeof(char *));
if (!uniq && uniq_count > 0) {
    perror("Failed to reallocate uniq array");
    exit(EXIT_FAILURE);
}

Notes #

• Time complexity: O(n log n) from the sort, which is totally acceptable for 140k entries.
• Don't forget to free all dynamically allocated memory later (both all_words and uniq).

Approach 2: Hash Table (Faster for Large Datasets) #

If you want faster average-time performance (O(n) instead of O(n log n)), a hash table is the way to go. We'll use a chained hash table to handle collisions, which is simple to implement in C.

Step-by-Step Implementation #

1. Define a hash table structure to track words we've already seen.
2. Create a hash function to map words to table indices.
3. Iterate through your word list: check if each word exists in the hash table. If it does, log the duplicate; if not, add it to both the hash table and your uniq array.

Code Example #

First, define the hash table node and helper functions:

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

// Hash table node structure
typedef struct HashNode {
    char *word;
    struct HashNode *next;
} HashNode;

// Use a large prime number as the hash table size to minimize collisions
#define HASH_TABLE_SIZE 100003

// Simple hash function for strings (djb2 algorithm)
unsigned int hash_string(const char *str) {
    unsigned int hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; // Equivalent to hash * 33 + c
    }
    return hash % HASH_TABLE_SIZE;
}

// Check if a word exists in the hash table
int hash_contains(HashNode **table, const char *word) {
    unsigned int idx = hash_string(word);
    HashNode *current = table[idx];
    while (current != NULL) {
        if (strcmp(current->word, word) == 0) {
            return 1; // Word found
        }
        current = current->next;
    }
    return 0; // Word not found
}

// Insert a word into the hash table
void hash_insert(HashNode **table, const char *word) {
    unsigned int idx = hash_string(word);
    HashNode *new_node = malloc(sizeof(HashNode));
    if (!new_node) {
        perror("Failed to allocate hash node");
        exit(EXIT_FAILURE);
    }
    new_node->word = strdup(word);
    new_node->next = table[idx];
    table[idx] = new_node;
}

Now the main deduplication logic:

// Initialize hash table (all pointers start as NULL)
HashNode **hash_table = calloc(HASH_TABLE_SIZE, sizeof(HashNode *));
if (!hash_table) {
    perror("Failed to allocate hash table");
    exit(EXIT_FAILURE);
}

// Allocate space for the uniq array (worst case: all words are unique)
char **uniq = malloc(word_count * sizeof(char *));
if (!uniq) {
    perror("Failed to allocate uniq array");
    exit(EXIT_FAILURE);
}

int uniq_count = 0;
for (int i = 0; i < word_count; i++) {
    char *current_word = all_words[i];
    if (hash_contains(hash_table, current_word)) {
        // Log the duplicate
        printf("Duplicate found: %s\n", current_word);
    } else {
        // Add to uniq array and hash table
        uniq[uniq_count++] = strdup(current_word);
        hash_insert(hash_table, current_word);
    }
}

// Shrink uniq array to actual size
uniq = realloc(uniq, uniq_count * sizeof(char *));
if (!uniq && uniq_count > 0) {
    perror("Failed to reallocate uniq array");
    exit(EXIT_FAILURE);
}

// Don't forget to clean up the hash table to avoid memory leaks
for (int i = 0; i < HASH_TABLE_SIZE; i++) {
    HashNode *current = hash_table[i];
    while (current != NULL) {
        HashNode *temp = current;
        current = current->next;
        free(temp->word);
        free(temp);
    }
}
free(hash_table);

Notes #

• This method is faster for large datasets since lookups are average O(1).
• The hash function choice matters—we used the djb2 algorithm which works well for strings.
• Always clean up the hash table memory to avoid leaks!

内容的提问来源于stack exchange，提问作者Darek Missa