C语言的Aho-Corasick算法

问题描述 投票：0回答：1

我编写了一个带有转换表的 Aho-Corasick 算法，该转换表在文本中搜索一组单词并使用 

malloc()
显示出现次数，但我遇到了此错误：

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

对于在字母大小为 20 的文本中搜索集合，它工作得很好，但对于字母大小为 70 的文本，它不起作用，并且我收到此分段错误错误。

c segmentation-fault malloc string-matching aho-corasick
1个回答
0
投票

至少存在以下问题：

  • 您将字符转换为可以大于

    ALPHABET_SIZE
    的索引值，在索引到转换表时调用未定义的行为。

    • 如果字典很大，
  • maxNode

    的初始值

    500000
    可能会太小。您不检查 
    trie->nextNode
    是否留在 
    ajoutmot
    中的数组边界内（即：
    trie->nextNode < trie->maxNode
    ），从而在使用 
    trie->transition[courant][index]
    写入 
    trie->finale[courant]
    或 
    courant >= trie->maxNode
    时导致未定义的行为。
    

    

    • 这是使用归一化索引值的 
ajoutmot
 和 
AhoCorrasick
 的修改版本：
int charindex(char c) {
#if ALPHABET_SIZE >= 64
    if (c >= 'a' && c <= 'z') {
        return c - 'a';
    } else
    if (c >= 'A' && c <= 'Z') {
        return c - 'A' + 26;
    } else
    if (c >= '0' && c <= '9') {
        return c - '0' + 52;
    } else
    if (c == ' ') {
        return 62;
    } else {
        // Caractère spécial, traitez-les comme une lettre supplémentaire
        return 63;
    }
#else
#error ALPHABET_SIZE too small
#endif
}

void ajoutmot(Trie *trie, char mot[MAX_WORD_LENGTH]) {
    int courant = 0;
    for (size_t i = 0; i < strlen(mot); ++i) {
        char c = mot[i];
        int index = charindex(c);

        if (trie->transition[courant][index] == 0) {
            if (trie->nextNode >= trie->maxNode) {
                fprintf(stderr, "Erreur: tableau de transitions plein pour le mot %s\n", mot);
                exit(EXIT_FAILURE);
            }
            trie->transition[courant][index] = trie->nextNode;
            trie->nextNode++;
        }
        courant = trie->transition[courant][index];
    }
    trie->finale[courant] = 1;
}

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 = charindex(c);

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



这可能无法解决所有问题，但应该防止分段错误。请注意，分段错误是一个很容易修复的错误，因为调试器将立即指向有问题的代码。

    



      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.