C 語言實現簡易倒排索引：從數據結構到完整代碼

什麼是倒排索引？

倒排索引是搜索引擎、文檔檢索系統的核心數據結構。它建立「詞項 → 文檔列表」的映射，能快速定位包含特定關鍵詞的所有文檔。本文演示一個簡單的 C 語言實現，包含創建、插入、查詢、遍歷與釋放操作。

數據結構設計

在 inver.h 中定義三個核心結構體：

typedef struct _invertfile_ {
    unsigned int tablelen;   // 哈希表大小
    void **table;            // 指向 word_t 的指針數組
    unsigned int nodecount;  // 總詞頻節點數
} if_t;

typedef struct _word_ {
    unsigned int id;         // 詞項 ID
    unsigned int refered;    // 包含該詞的文檔數
    void *link;              // 指向 wf_t 鏈表頭
} word_t;

typedef struct _word_frequency_ {
    unsigned int d_id;       // 文檔 ID
    unsigned int refered;    // 該詞在文檔中的出現次數
    void *next;              // 下一個詞頻節點
} wf_t;

if_t 為主結構，內含指針數組 table，每個槽位指向一個 word_t；word_t 通過 link 掛載 wf_t 單向鏈表，記錄該詞出現的文檔 ID 及頻次。

核心函數實現

1. 創建倒排表 invertfile_create

if_t* invertfile_create(int length) {
    if_t *h = calloc(1, sizeof(if_t));
    if (!h) return NULL;

    h->table = calloc(length, sizeof(void *));
    h->tablelen = length;
    h->nodecount = 0;

    for (int i = 0; i < length; i++) {
        h->table[i] = malloc(sizeof(word_t));
        word_t *w = (word_t *)h->table[i];
        w->id = i;
        w->refered = 0;
        w->link = NULL;
    }
    return h;
}

分配主結構與指針數組，並預先為每個槽位分配 word_t，初始化 ID 為索引值。

2. 插入詞項 invertfile_insert

void invertfile_insert(if_t *h, int w_id, int d_id) {
    word_t *w = (word_t *)h->table[w_id];
    wf_t *wf = invertfile_search(h, w_id, d_id);

    if (wf) {
        wf->refered++;  // 已存在，累加詞頻
    } else {
        wf = malloc(sizeof(wf_t));
        wf->next = w->link;
        w->link = wf;
        w->refered++;
        wf->refered = 1;
        wf->d_id = d_id;
        h->nodecount++;
    }
}

先查詢是否已存在該文檔，存在則遞增詞頻；否則頭插法創建新節點。

3. 查詢詞頻 invertfile_search

wf_t* invertfile_search(if_t *h, int w_id, int d_id) {
    word_t *w = (word_t *)h->table[w_id];
    if (w->refered > 0) {
        wf_t *wf = (wf_t *)w->link;
        while (wf) {
            if (wf->d_id == d_id) return wf;
            wf = (wf_t *)wf->next;
        }
    }
    return NULL;
}

4. 遍歷輸出 invertfile_traverse 與 釋放內存 invertfile_free

void invertfile_traverse(if_t *h) {
    for (int i = 0; i < h->tablelen; i++) {
        word_t *w = (word_t *)h->table[i];
        wf_t *wf = (wf_t *)w->link;
        printf("word_id:%d;", w->id);
        while (wf) {
            printf("d_id:%d,freq:%d;", wf->d_id, wf->refered);
            wf = (wf_t *)wf->next;
        }
        printf("\n");
    }
}

void invertfile_free(if_t *h) {
    for (int i = 0; i < h->tablelen; i++) {
        word_t *w = (word_t *)h->table[i];
        wf_t *wf = (wf_t *)w->link, *cur;
        while (wf) {
            cur = wf;
            wf = (wf_t *)wf->next;
            free(cur);
        }
        free(w);
    }
    free(h->table);
    free(h);
}

測試驗證

main.cpp 插入測試數據：

if_t *f = invertfile_create(10);
invertfile_insert(f, 1, 1);
invertfile_insert(f, 1, 1);  // 詞頻 +1
invertfile_insert(f, 1, 3);
invertfile_insert(f, 2, 5);
invertfile_traverse(f);
invertfile_free(f);

輸出結果：

word_id:0;
word_id:1;d_id:3,freq:1;d_id:1,freq:2;
word_id:2;d_id:5,freq:1;
word_id:3;
...
word_id:9;

詞項 1 出現在文檔 1（詞頻 2）和文檔 3（詞頻 1）；詞項 2 出現在文檔 5（詞頻 1）。

優化方向

• 使用動態擴容的哈希表替代固定大小數組
• 引入雙向鏈表或跳表加速刪除操作
• 採用內存池減少頻繁 malloc/free 開銷
• 支持持久化存儲（如 mmap 或 LevelDB）