基于线性表或二叉排序树的低频词过滤系统
时间: 2023-03-19 15:29:10 浏览: 125
基于线性表或二叉排序树的低频词过滤系统是一种用于过滤文本中低频词的系统。它可以通过建立一个线性表或二叉排序树来存储所有单词,并记录每个单词出现的次数。然后,根据设定的阈值,将出现次数低于阈值的单词过滤掉,从而提高文本的质量和可读性。这种系统可以应用于各种文本处理场景,如搜索引擎、文本分类、信息提取等。
相关问题
一篇英文文章存储在一个文本文件中,然后分别基于线性表、二叉排序树和哈希表不同的存储结构,完成单词词频的统计和单词的检索功能。同时计算不同检索策略下的平均查找长度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;
}
```
一篇英文文章存储在一个文本文件中,分别基于线性表、二叉排序树和散列表的不同存储结构,实现单词词频的的统计和单词的检索功能。同时计算不同检索策略下的ASL,通过比较ASL的大小,对不同检索策略的时间性能做出相应的比较分析
根据线性表、二叉排序树和散列表的不同存储结构,可以实现对英文文章中单词词频的统计和单词的检索功能。为了比较不同检索策略的时间性能,可以计算出每种检索策略下的平均搜索长度(ASL),通过对比ASL的大小,来对不同检索策略的时间性能进行比较分析。