Institute of Computing Technology, Chinese Academy IR
| 正则表达式分组的1／（1-1／k）-近似算法 | |
柳厅文 ; 孙永; 卜东波; 郭莉; 方滨兴
| |
| 2012 | |
| 发表期刊 | 软件学报
 |
| ISSN | 1000-9825 |
| 卷号 | 23.0期号:009页码:2261 |
| 摘要 | 对正则表达式集合进行分组是解决DFA状态膨胀问题的一种重要方法．已有的分组算法大都是启发式的或蛮力的，分组效果很差．分析了DFA状态膨胀的原因，总结了某些正则表达式间的冲突状况．证明了当冲突非负和冲突独立时，正则表达式集合的最优k分组问题可归结为最大k割问题，从而说明该问题是NP-Hard的基于局部搜索的思想，提出了一种分组算法GRELS来解决分组问题，并证明对最大k割问题，该算法的近似比是1／（1—1／k）．与已有的分组算法相比，当分组数目相同时，GRELS算法分组结果的状态总数最少，并且集合发生变化时所需的更新时间最短． |
| 关键词 | 正则表达式 深度包检测 分组算法 局部搜索 1／（1—1哟近似 |
| 语种 | 英语 |
| 文献类型 | 期刊论文 |
| 条目标识符 | http://119.78.100.204/handle/2XEOYT63/35788 |
| 专题 | 中国科学院计算技术研究所期刊论文_中文 |
| 作者单位 | 中国科学院计算技术研究所 |
| 第一作者单位 | 中国科学院计算技术研究所 |
| 推荐引用方式 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. |
| 条目包含的文件 | 条目无相关文件。 | |||||
| 个性服务 |
| 推荐该条目 |
| 保存到收藏夹 |
| 查看访问统计 |
| 导出为Endnote文件 |
| 谷歌学术 |
| 谷歌学术中相似的文章 |
| [柳厅文]的文章 |
| [孙永]的文章 |
| [卜东波]的文章 |
| 百度学术 |
| 百度学术中相似的文章 |
| [柳厅文]的文章 |
| [孙永]的文章 |
| [卜东波]的文章 |
| 必应学术 |
| 必应学术中相似的文章 |
| [柳厅文]的文章 |
| [孙永]的文章 |
| [卜东波]的文章 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论