没有合适的资源?快使用搜索试试~ 我知道了~
首页ac-bm算法研究源程序
ac-bm算法研究源程序
5星 · 超过95%的资源 需积分: 12 19 下载量 37 浏览量
更新于2023-03-16
评论 2
收藏 83KB DOC 举报
AC-BM算法研究源代码 AC-BM算法将待匹配的字符串集合转换为一个类似于Aho-Corasick算法的树状有限状态自动机,但构建时不是基于字符串的后缀而是前缀
资源详情
资源评论
资源推荐
#ifndef _AC_BM_H
#dene _AC_BM_H
#dene PATTERN_LEN 1024
#dene MAX_ITEMS 20
/// 模式树节点结构
typedef struct _pattern_tree_node
{
int label ; // 标识, -2 根节点, -1 中间节点, n 第 n 个字串尾节点
int depth ; // 节点深度
unsigned char ch ; // 节点对应的字符
int GSshift ; // 好字串位移
int BCshift ;
unsigned char one_child ; // 其中的一个子索引字符
struct _pattern_tree_node *childs[256] ; // 256 个字符的对应节点指针
int nchild ; // 子节点个数
struct _pattern_tree_node *parent ; // 父节点
} pattern_tree_node ;
// 关键字数据结构
typedef struct _pattern_data
{
unsigned char data[PATTERN_LEN] ; // 关键字字串
int len ; // 关键字字串长
} pattern_data ;
// 模式树结构
typedef struct _pattern_tree
{
pattern_tree_node *root ; // 树根节点
int max_depth ; // 最大字串深度
int min_pattern_size ; // 最短的字串长度
int BCshift[256] ; // 256 个字符中坏字符的 shift
pattern_data *pattern_list ; // 指向节点数组第一个字串的指针
int pattern_count ; // 包含的字串个数
} pattern_tree ;
// 匹配信息结构体
typedef struct _matched_info
{
int pattern_i ; // 关键字在关键字数组中的 index
unsigned long o8set ; // 在待匹配文本 text 中的偏移值
} matched_info_t ;
// 创建 模式树
int ACtree_build (pattern_tree *ptree,
pattern_data *patterns,
int npattern) ;
// 打印 当前节点及其所有后缀节点
void _print_tree (pattern_tree_node *root) ;
// 打印 整个模式树
void ACtree_print_tree (pattern_tree *ptree);
// 打印 搜索结果
int match_resualt_printf_ex (unsigned char *text,
pattern_data *patterns,
int npattern,
matched_info_t matched_items[],
int nmatched);
// 释放 模式树空间
void _clean_tree(pattern_tree_node *root) ;
// 设置 模式树的 BCshift
int ACtree_compute_BCshifts (pattern_tree *ptree) ;
// 创建 ac_bm 模式树
pattern_tree *acbm_init (pattern_data *patterns, int npattern) ;
// 释放 ac_bm 模式树空间
void acbm_clean (pattern_tree *ptree) ;
// ac_bm 搜索算法改进版
int acbm_search (pattern_tree *ptree,
unsigned char *text,
int text_len,
matched_info_t matched_items[],
int nmax_index);
// 计算并调整 ACTree 模式树的 BCshift 和 GSshift
int ACtree_compute_shifts(pattern_tree *ptree) ;
// 计算并调整 ACTree 模式树的 GSshift
int ACtree_compute_GSshifts(pattern_tree *ptree) ;
// 初始化 ACTree 的 GSshift
int ACtree_init_GSshifts(pattern_tree *ptree) ;
// 初始化当前节点的 GSshift
int _init_GSshifts(pattern_tree_node *root, int shift) ;
// 调整 ACTree 中关键字 pat1 的 GSshift
int set_GSshift (pattern_tree *ptree,
unsigned char *pat,
int depth,
int shift) ;
// 调整 ACTree 中关键字 pat1 因 pat2 而发生变化的 GSshift
int compute_GSshift(pattern_tree *ptree,
unsigned char *pat1,
int pat1_len,
unsigned char *pat2,
int pat2_len) ;
#endif
AC-BM.c 文件如下:
// 头文件
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "ac_bm.h"
// 宏定义
//#dene CASE_SENSITIVE
//#dene DEBUG_SEARCH
unsigned char mychar[100];
/*--------------------------------------------------------------------------
* 函数名:
* ACTree_bulid
*
* 函数功能:
* 创建 ACtree 模式树,包括各个节点,字符索引,及其他的信息,ptree 指向根节点
*
* 参数说明:
* pattern_tree *ptree : 指向 ACTree 的指针
* pattern_data *patterns : 关键字字串数组
* int npattern : 关键字字串个数
*
* 返回值类型: int
* 0 : 创建成功
* -1 : 出错
----------------------------------------------------------------------------*/
int ACtree_build (pattern_tree *ptree,
pattern_data *patterns,
int npattern)
{
int i ;
pattern_tree_node *root = NULL, *parent = NULL ;
unsigned char ch ;
int max_pattern_len = 0, min_pattern_len = PATTERN_LEN ;
if (NULL == ptree || NULL == patterns || npattern < 0)
{
goto err ;
}
root = (pattern_tree_node *) malloc (sizeof (pattern_tree_node)) ;
if (NULL == root)
{
goto err ;
}
memset (root, 0, sizeof (pattern_tree_node)) ;
root->label = -2 ; // 树根标志
root->depth = 0 ; // 树根深度
// 对输入的字串循环处理添加进 ACTree
for (i = 0 ; i < npattern ; i++)
{
int pat_len ;
int ch_i ;
pat_len = (patterns+i)->len ;
if (pat_len == 0)
{
continue ;
}
else
{
if (pat_len > PATTERN_LEN)
{
pat_len = PATTERN_LEN ;
}
if (pat_len > max_pattern_len)
{
max_pattern_len = pat_len ;
}
if (pat_len < min_pattern_len)
{
min_pattern_len = pat_len ;
}
parent = root ;
for (ch_i = 0 ; ch_i < pat_len ; ch_i++)
{
ch = ((patterns+i)->data)[ch_i] ;
#ifndef CASE_SENSITIVE
ch = tolower(ch) ;
#endif
// 对应的字符索引为 NULL
if (NULL == parent->childs[ch])
{
break ;
}
parent = parent->childs[ch] ;
}
if (ch_i < pat_len)
{
// 在父节点下添加新节点
for (; ch_i < pat_len ; ch_i++)
{
pattern_tree_node *node = NULL ;
ch = ((patterns+i)->data)[ch_i] ;
#ifndef CASE_SENSITIVE
ch = tolower(ch) ;
#endif
node = (pattern_tree_node *) malloc (sizeof (pattern_tree_node)) ;
if (node == NULL)
{
goto err ;
}
memset (node, 0, sizeof(pattern_tree_node)) ;
node->depth = ch_i + 1 ;
node->ch = ch ;
node->label = -1 ;
// 将新节点添加到父节点的对应字符索引指针
parent->childs[ch] = node ;
// 不考虑大小写的分别
#ifndef CASE_SENSITIVE
if ((ch >= 'a') && (ch <= 'z'))
{
parent->childs[ch-32] = node ;
}
#endif
parent->nchild++ ;
parent->one_child = ch ;
node->parent = parent ;
parent = node ;
}
}
}
// lable 记录字串来自于第几个输入字串
parent->label = i ;
}
ptree->pattern_list = patterns ;
ptree->pattern_count = npattern ;
剩余21页未读,继续阅读
u010295870
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 27页智慧街道信息化建设综合解决方案.pptx
- 计算机二级Ms-Office选择题汇总.doc
- 单链表的插入和删除实验报告 (2).docx
- 单链表的插入和删除实验报告.pdf
- 物联网智能终端项目设备管理方案.pdf
- 如何打造品牌的模式.doc
- 样式控制与页面布局.pdf
- 武汉理工Java实验报告(二).docx
- 2021线上新品消费趋势报告.pdf
- 第3章 Matlab中的矩阵及其运算.docx
- 基于Web的人力资源管理系统的必要性和可行性.doc
- 基于一阶倒立摆的matlab仿真实验.doc
- 速运公司物流管理模式研究教材
- 大数据与管理.pptx
- 单片机课程设计之步进电机.doc
- 大数据与数据挖掘.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论2