基于C语言的Aho-Corasick算法大字母集下段错误问题求助

实现了带转移表的Aho-Corasick算法，用于文本中指定词集的搜索与次数统计，使用malloc()分配内存。当ALPHABET_SIZE设为20时程序运行正常，但设为70时触发以下错误：

Segmentation fault (core dumped)

附实现代码：

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

#define ALPHABET_SIZE 70
#define MAX_WORD_LENGTH 100000

typedef struct Element Element;
struct Element {
    int nombre;
    Element *suivant;
};

typedef struct File File;

struct File {
    Element *premier;
    Element *dernier;
};

File *creerfile() {
    File *file = (File *)malloc(sizeof(File));
    if (file == NULL) {
        perror("Erreur d'allocation pour la file");
        exit(EXIT_FAILURE);
    }

    file->premier = NULL;
    file->dernier = NULL;

    return file;
}

int estVide(File *file) {
    return file->premier == NULL;
}

void enfiler(File *file, int element) {
    Element *nouveau = malloc(sizeof(*nouveau));
    if (nouveau == NULL) {
        perror("Erreur d'allocation pour un élément de la file");
        exit(EXIT_FAILURE);
    }

    nouveau->nombre = element;
    nouveau->suivant = NULL;

    if (file->premier != NULL) {
        file->dernier->suivant = nouveau;
    } else {
        file->premier = nouveau;
    }

    file->dernier = nouveau;
}

int defiler(File *file) {
    if (file == NULL || file->premier == NULL) {
        perror("Erreur de défiler : file vide");
        exit(EXIT_FAILURE);
    }

    int nombreDefile = file->premier->nombre;
    Element *elementDefile = file->premier;

    file->premier = elementDefile->suivant;
    free(elementDefile);

    if (file->premier == NULL) {
        file->dernier = NULL;
    }

    return nombreDefile;
}

struct _trie {
    int maxNode;
    int nextNode;
    int **transition;
    char *finale;
    int *supp;
};

typedef struct _trie Trie;

void initialisationTrie(Trie *trie, int maxNode) {
    trie->maxNode = maxNode;
    trie->nextNode = 1;
    trie->transition = (int **)malloc(maxNode * sizeof(int *));
    if (trie->transition == NULL) {
        perror("Erreur d'allocation pour le tableau de transitions");
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < maxNode; ++i) {
        trie->transition[i] = (int *)malloc(ALPHABET_SIZE * sizeof(int));
        if (trie->transition[i] == NULL) {
            perror("Erreur d'allocation pour une ligne du tableau de transitions");
            exit(EXIT_FAILURE);
        }
        for (int j = 0; j < ALPHABET_SIZE; ++j) {
            trie->transition[i][j] = 0;
        }
    }

    trie->finale = (char *)malloc(maxNode * sizeof(char));
    if (trie->finale == NULL) {
        perror("Erreur d'allocation pour le tableau finale");
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < maxNode; ++i) {
        trie->finale[i] = 0;
    }

    trie->supp = (int *)malloc(maxNode * sizeof(int));
    if (trie->supp == NULL) {
        perror("Erreur d'allocation pour le tableau supp");
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < maxNode; ++i) {
        trie->supp[i] = 0;
    }
}

void ajoutmot(Trie *trie, char mot[MAX_WORD_LENGTH]) {
    int courant = 0;
    for (int i = 0; i < strlen(mot); ++i) {
        char c = mot[i];
        int index;
        if (c >= 'a' && c <= 'z') {
            index = c - 'a';
        } else {
            // Caractère spécial, traitez-le comme une lettre
            index = c - 'A' + 26;  // Ajoutez 26 pour l'ajustement
        }

        if (trie->transition[courant][index] == 0) {
            trie->transition[courant][index] = trie->nextNode;
            trie->nextNode++;
        }

        courant = trie->transition[courant][index];
    }
    trie->finale[courant] = 1;
}

void constructionsuppleants(Trie *trie) {
    File *file = creerfile();
    for (int i = 0; i < ALPHABET_SIZE; ++i) {
        if (trie->transition[0][i] != 0) {
            enfiler(file, trie->transition[0][i]);
            trie->supp[trie->transition[0][i]] = 0;
        }
    }

    while (!estVide(file)) {
        int r = defiler(file);
        for (int i = 0; i < ALPHABET_SIZE; ++i) {
            int s = trie->transition[r][i];
            if (s != 0) {
                enfiler(file, s);
                int etat = trie->supp[r];
                while (trie->transition[etat][i] == 0 && etat != 0) {
                    etat = trie->supp[etat];
                }
                trie->supp[s] = trie->transition[etat][i] != 0 ? trie->transition[etat][i] : 0;
            }
        }
    }

    free(file);
}

int AhoCorrasick(Trie *trie, char *text) {
    int cmpt = 0;
    int etat = 0;
    for (int i = 0; text[i] != '\0'; ++i) {
        char c = text[i];
        int index;
        if (c >= 'a' && c <= 'z') {
            index = c - 'a';
        } else {
            // Traitez le caractère spécial comme une lettre
            index = c - 'a' + 26;
        }

        while (trie->transition[etat][index] == 0 && etat != 0) {
            etat = trie->supp[etat];
        }

        etat = trie->transition[etat][index] != 0 ? trie->transition[etat][index] : 0;

        int etatTemporaire = etat;
        while (etatTemporaire != 0) {
            if (trie->finale[etatTemporaire] == 1) {
                cmpt++;
            }
            etatTemporaire = trie->supp[etatTemporaire];
        }
    }

    return cmpt;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "aho_corrasick_matrice.c"
#include "aho_corrasick_matrice.h"

#define ALPHABET_SIZE 70
#define BUFFER_SIZE 4096
#define MAX_WORD_LENGTH 100000

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "Usage: %s mots.txt texte.txt\n", argv[0]);
        exit(EXIT_FAILURE);
    }

    Trie trie;
    long int maxNode = 500000;
    initialisationTrie(&trie, maxNode);

    FILE *motsFile = fopen(argv[1], "r");
    if (motsFile == NULL) {
        fprintf(stderr, "Erreur lors de l'ouverture du fichier %s\n", argv[1]);
        exit(EXIT_FAILURE);
    }

    char mot[MAX_WORD_LENGTH];
    while (fscanf(motsFile, "%s", mot) == 1) {
        ajoutmot(&trie, mot);
    }

    fclose(motsFile);

    constructionsuppleants(&trie);

    FILE *texteFile = fopen(argv[2], "r");
    if (texteFile == NULL) {
        fprintf(stderr, "Erreur lors de l'ouverture du fichier %s\n", argv[2]);
        exit(EXIT_FAILURE);
    }

    char buffer[BUFFER_SIZE];
    int occurrences = 0;

    while (fgets(buffer, sizeof(buffer), texteFile) != NULL) {
        occurrences += AhoCorrasick(&trie, buffer);
    }

    printf("Nombre d'occurrences est : %d\n", occurrences);

    fclose(texteFile);

    free(trie.finale);
    for (int i = 0; i < maxNode; ++i) {
        free(trie.transition[i]);
    }
    free(trie.transition);
    free(trie.supp);

    return 0;
}

1. 字符索引计算错误导致数组越界 #

这是触发段错误的主要原因：

• AhoCorrasick函数的else分支错误使用c - 'a' +26，对于大写字母（如'A'），'A'-'a'结果为负数，加26后仍为负，直接导致访问transition数组时越界。
• 未对字符范围做有效校验，遇到非大小写字母的字符（如数字、符号）时，计算出的索引可能超过ALPHABET_SIZE-1，触发非法内存访问。

2. 内存分配规模过大（潜在诱因） #

当ALPHABET_SIZE=70时，transition数组总内存为500000 * 70 * sizeof(int)=140MB，加上finale和supp数组，总内存占用接近160MB。若运行环境内存紧张，可能加剧内存访问错误。

3. 代码结构问题 #

• 重复定义ALPHABET_SIZE、MAX_WORD_LENGTH等宏，容易引发逻辑混淆。
• main函数直接包含.c文件，违反模块化规范，可能导致符号重复定义。

1. 修正字符索引映射逻辑 #

确保所有字符的索引落在0~ALPHABET_SIZE-1范围内，示例代码如下：

方案一：分类型映射（精确控制） #

替换ajoutmot和AhoCorrasick中的索引计算部分：

int index;
if (c >= 'a' && c <= 'z') {
    index = c - 'a'; // 小写字母：0-25
} else if (c >= 'A' && c <= 'Z') {
    index = c - 'A' + 26; // 大写字母：26-51
} else if (c >= '0' && c <= '9') {
    index = c - '0' + 52; // 数字：52-61
} else {
    // 处理常见符号，映射到62-69（可根据需求扩展）
    switch(c) {
        case '!': index=62; break;
        case '@': index=63; break;
        case '#': index=64; break;
        case '$': index=65; break;
        case '%': index=66; break;
        case '^': index=67; break;
        case '&': index=68; break;
        case '*': index=69; break;
        default: 
            // 跳过未定义字符，避免越界
            continue;
    }
}

方案二：通用哈希映射（简单粗暴） #

若无需精确区分字符类型，可直接对字符做模运算确保索引合法：

index = (unsigned char)c % ALPHABET_SIZE;

注：此方式可能导致不同字符冲突，需根据业务场景选择。

2. 优化内存分配 #

• 降低maxNode初始值，比如从500000调整为100000，测试通过后再根据词集大小动态调整，或改为动态扩容的Trie结构。
• 改用稀疏数组存储转移表，仅保存存在的转移关系，减少内存占用。

3. 修复代码结构 #

• 删除重复的宏定义和头文件包含，确保ALPHABET_SIZE等宏仅定义一次。
• 将算法代码拆分到.h和.c文件中，main函数仅包含头文件，禁止直接包含.c文件。

4. 添加边界校验 #

在访问数组前添加索引合法性校验，提前拦截错误：

// 在计算index后添加
if (index < 0 || index >= ALPHABET_SIZE) {
    fprintf(stderr, "无效字符索引：%d，字符：%c\n", index, c);
    continue;
}

若修复后仍有问题，可使用gdb定位崩溃点：

gdb ./your_program
run mots.txt texte.txt
bt # 查看调用栈，定位具体崩溃位置

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