正则表达式分组的1／（1-1／k）-近似算法
文献类型：期刊论文
| 作者 | 柳厅文 ; 孙永; 卜东波; 郭莉; 方滨兴
|
| 刊名 | 软件学报
 |
| 出版日期 | 2012 |
| 卷号 | 23.0期号:009页码:2261 |
| 关键词 | 正则表达式 深度包检测 分组算法 局部搜索 1／（1—1哟近似 |
| ISSN号 | 1000-9825 |
| 英文摘要 | 对正则表达式集合进行分组是解决DFA状态膨胀问题的一种重要方法．已有的分组算法大都是启发式的或蛮力的，分组效果很差．分析了DFA状态膨胀的原因，总结了某些正则表达式间的冲突状况．证明了当冲突非负和冲突独立时，正则表达式集合的最优k分组问题可归结为最大k割问题，从而说明该问题是NP-Hard的基于局部搜索的思想，提出了一种分组算法GRELS来解决分组问题，并证明对最大k割问题，该算法的近似比是1／（1—1／k）．与已有的分组算法相比，当分组数目相同时，GRELS算法分组结果的状态总数最少，并且集合发生变化时所需的更新时间最短． |
| 语种 | 英语 |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/35787]  |
| 专题 | 中国科学院计算技术研究所期刊论文_中文 |
| 作者单位 | 中国科学院计算技术研究所 |
| 推荐引用方式 GB/T 7714 | 柳厅文,孙永,卜东波,等. 正则表达式分组的1／（1-1／k）-近似算法[J]. 软件学报,2012,23.0(009):2261. |
| APA | 柳厅文,孙永,卜东波,郭莉,&方滨兴.(2012).正则表达式分组的1／（1-1／k）-近似算法.软件学报,23.0(009),2261. |
| MLA | 柳厅文,et al."正则表达式分组的1／（1-1／k）-近似算法".软件学报 23.0.009(2012):2261. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。