C 語言實現簡易倒排索引 (Inverted Index) 完整代碼

資料結構設計

[c]
// invert.h
#ifndef INVERT_FILE_H
#define INVERT_FILE_H

#include 
#include 

typedef struct _invertfile_ {
    unsigned int tablelen;   // 雜湊表大小 (詞ID空間)
    void **table;            // 指向 word_t 陣列
    unsigned int nodecount;  // 總倒排鏈節點數
} if_t;

typedef struct _word_ {
    unsigned int id;         // 詞 ID
    unsigned int refered;    // 文檔頻次 (DF)
    void *link;              // 指向 wf_t 鏈表頭
} word_t;

typedef struct _word_frequency_ {
    unsigned int d_id;       // 文檔 ID
    unsigned int refered;    // 該文檔內詞頻 (TF)
    void *next;              // 下一個文檔節點
} wf_t;

if_t* invertfile_create(int length);
void invertfile_insert(if_t *h, int w_id, int d_id);
wf_t* invertfile_search(if_t *h, int w_id, int d_id);
void invertfile_traverse(if_t *h);
void invertfile_free(if_t *h);

#endif

核心邏輯實現

[c]
// invert.c
#include "invert.h"

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++) {
        word_t *w = calloc(1, sizeof(word_t));
        w->id = i;
        w->refered = 0;
        w->link = NULL;
        h->table[i] = w;
    }
    return h;
}

// 查找詞 w_id 在文檔 d_id 的倒排節點
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;
}

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++; // TF++
    } else {
        wf = malloc(sizeof(wf_t));
        wf->d_id = d_id;
        wf->refered = 1;
        wf->next = w->link; // 頭插法
        w->link = wf;
        w->refered++; // DF++
        h->nodecount++;
    }
}

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;
        while (wf) {
            wf_t *cur = wf;
            wf = (wf_t*)wf->next;
            free(cur);
        }
        free(w);
    }
    free(h->table);
    free(h);
}

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");
    }
}

測試驗證

[c]
// main.c
#include "invert.h"
int main() {
    if_t *f = invertfile_create(10);
    invertfile_insert(f, 1, 1); // 詞1 在 文檔1 出現
    invertfile_insert(f, 1, 1); // 詞1 在 文檔1 再次出現 (TF=2)
    invertfile_insert(f, 1, 3); // 詞1 在 文檔3 出現
    invertfile_insert(f, 2, 5); // 詞2 在 文檔5 出現
    invertfile_traverse(f);
    invertfile_free(f);
    return 0;
}

輸出結果

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. 動態詞表：目前 tablelen 固定，需雙雜湊或 B+ 樹支援動態增長。
2. 壓縮存儲：d_id 差分編碼 (Delta Encoding) + Varint/Gamma 碼壓縮。
3. 持久化：序列化至磁碟 (mmap/LevelDB/RocksDB)，支援增量更新與合併。
4. 檢索介面：布林查詢 (AND/OR/NOT)、TF-IDF/BM25 評分、分頁排序。
5. 併發控制：RWLock 或無鎖結構支援多執行緒寫入/讀取。