基于线性表和二叉排序树的低频词过滤系统

基于线性表和二叉排序树的低频词过滤系统，是一种文本过滤系统，可以用于过滤掉出现频率较低的词语。该系统首先将文本中的所有词语存储在一个线性表中，然后对该线性表进行排序。接着，该系统会将排序后的词语依次插入到一个二叉排序树中，构建起一个具有快速查找和删除功能的数据结构。在进行文本过滤时，该系统会快速地在二叉排序树中查找每个词语的出现频率，如果某个词语的出现频率低于设定的阈值，该词语将被视为低频词语并被过滤掉。

相关问题

基于线性表或二叉排序树的低频词过滤系统

基于线性表或二叉排序树的低频词过滤系统是一种用于过滤文本中低频词的系统。它可以通过建立一个线性表或二叉排序树来存储所有单词，并记录每个单词出现的次数。然后，根据设定的阈值，将出现次数低于阈值的单词过滤掉，从而提高文本的质量和可读性。这种系统可以应用于各种文本处理场景，如搜索引擎、文本分类、信息提取等。

一篇英文文章存储在一个文本文件中，然后分别基于线性表、二叉排序树和哈希表不同的存储结构，完成单词词频的统计和单词的检索功能。同时计算不同检索策略下的平均查找长度ASLC语言代码

以下是基于线性表、二叉排序树和哈希表不同存储结构实现单词词频统计和单词检索功能的ASLC代码：

## 线性表存储结构

定义一个单词节点结构体，包含单词和出现次数两个变量。定义一个线性表结构体，包含单词节点数组和当前单词节点数两个变量。实现单词词频统计和单词检索功能。

struct word_node {
    char word[20];
    int count;
};

struct word_list {
    struct word_node nodes[1000];
    int count;
};

struct word_list wordList;

void word_count(char* filename) {
    FILE* fp = fopen(filename, "r");
    char word[20];
    while (fscanf(fp, "%s", word) != EOF) {
        int exist = 0;
        for (int i = 0; i < wordList.count; i++) {
            if (strcmp(wordList.nodes[i].word, word) == 0) {
                wordList.nodes[i].count++;
                exist = 1;
                break;
            }
        }
        if (!exist) {
            strcpy(wordList.nodes[wordList.count].word, word);
            wordList.nodes[wordList.count].count = 1;
            wordList.count++;
        }
    }
    fclose(fp);
}

int word_search(char* word) {
    for (int i = 0; i < wordList.count; i++) {
        if (strcmp(wordList.nodes[i].word, word) == 0) {
            return wordList.nodes[i].count;
        }
    }
    return 0;
}

## 二叉排序树存储结构

定义一个单词节点结构体，包含单词、出现次数、左右子树节点指针三个变量。定义一个二叉排序树结构体，包含根节点指针一个变量。实现单词词频统计和单词检索功能。

struct word_node {
    char word[20];
    int count;
    struct word_node* left;
    struct word_node* right;
};

struct bst {
    struct word_node* root;
};

void bst_insert(struct bst* tree, char* word) {
    if (!tree->root) {
        tree->root = (struct word_node*) malloc(sizeof(struct word_node));
        strcpy(tree->root->word, word);
        tree->root->count = 1;
        tree->root->left = NULL;
        tree->root->right = NULL;
        return;
    }
    struct word_node* node = tree->root;
    while (1) {
        if (strcmp(node->word, word) == 0) {
            node->count++;
            return;
        } else if (strcmp(node->word, word) > 0) {
            if (node->left) {
                node = node->left;
            } else {
                node->left = (struct word_node*) malloc(sizeof(struct word_node));
                strcpy(node->left->word, word);
                node->left->count = 1;
                node->left->left = NULL;
                node->left->right = NULL;
                return;
            }
        } else {
            if (node->right) {
                node = node->right;
            } else {
                node->right = (struct word_node*) malloc(sizeof(struct word_node));
                strcpy(node->right->word, word);
                node->right->count = 1;
                node->right->left = NULL;
                node->right->right = NULL;
                return;
            }
        }
    }
}

void bst_traverse(struct word_node* node) {
    if (!node) {
        return;
    }
    bst_traverse(node->left);
    printf("%s: %d\n", node->word, node->count);
    bst_traverse(node->right);
}

int bst_search(struct word_node* node, char* word) {
    if (!node) {
        return 0;
    }
    if (strcmp(node->word, word) == 0) {
        return node->count;
    } else if (strcmp(node->word, word) > 0) {
        return bst_search(node->left, word);
    } else {
        return bst_search(node->right, word);
    }
}

## 哈希表存储结构

定义一个单词节点结构体，包含单词和出现次数两个变量。定义一个哈希表结构体，包含单词节点指针数组和当前单词节点数两个变量。实现单词词频统计和单词检索功能。

struct word_node {
    char word[20];
    int count;
};

struct hash_table {
    struct word_node* nodes[1000];
    int count;
};

struct hash_table hashTable;

unsigned int hash(char* str) {
    unsigned int hash = 0;
    for (int i = 0; str[i] != '\0'; i++) {
        hash = hash * 31 + str[i];
    }
    return hash % 1000;
}

void hash_insert(char* word) {
    int index = hash(word);
    struct word_node* node = hashTable.nodes[index];
    while (node) {
        if (strcmp(node->word, word) == 0) {
            node->count++;
            return;
        }
        node = node->next;
    }
    struct word_node* newNode = (struct word_node*) malloc(sizeof(struct word_node));
    strcpy(newNode->word, word);
    newNode->count = 1;
    newNode->next = hashTable.nodes[index];
    hashTable.nodes[index] = newNode;
    hashTable.count++;
}

void hash_traverse() {
    for (int i = 0; i < 1000; i++) {
        struct word_node* node = hashTable.nodes[i];
        while (node) {
            printf("%s: %d\n", node->word, node->count);
            node = node->next;
        }
    }
}

int hash_search(char* word) {
    int index = hash(word);
    struct word_node* node = hashTable.nodes[index];
    while (node) {
        if (strcmp(node->word, word) == 0) {
            return node->count;
        }
        node = node->next;
    }
    return 0;
}

计算不同检索策略下的平均查找长度ASLC代码如下：

int linear_search(char* word) {
    for (int i = 0; i < wordList.count; i++) {
        if (strcmp(wordList.nodes[i].word, word) == 0) {
            return i + 1;
        }
    }
    return 0;
}

int bst_average_search_length(struct word_node* node, int depth) {
    if (!node) {
        return 0;
    }
    int leftDepth = bst_average_search_length(node->left, depth + 1);
    int rightDepth = bst_average_search_length(node->right, depth + 1);
    return depth + leftDepth + rightDepth;
}

int hash_average_search_length(char* word) {
    int index = hash(word);
    struct word_node* node = hashTable.nodes[index];
    int count = 0;
    while (node) {
        count++;
        if (strcmp(node->word, word) == 0) {
            return count;
        }
        node = node->next;
    }
    return 0;
}