计算机工程 ›› 2013, Vol. 39 ›› Issue (1): 45-48.doi: 10.3969/j.issn.1000-3428.2013.01.009

• 软件技术与数据库 • 上一篇    下一篇

基于多线程技术的分辨函数析取范式生成算法

蒙祖强,周石泉,黄柏雄   

  1. (广西大学计算机与电子信息学院,南宁 530004)
  • 收稿日期:2011-09-19 修回日期:2012-02-19 出版日期:2013-01-15 发布日期:2013-01-13
  • 作者简介:蒙祖强(1974-),男,教授、博士后,主研方向:粒度计算,知识发现;周石泉,硕士研究生;黄柏雄,讲师、 硕士研究生
  • 基金项目:
    国家自然科学基金资助项目(61063032);广西自然科学基金资助项目(2012GXNSFAA053225)

Disjunction Normal Form Generation Algorithm of Discernibility Function Based on Multi-thread Technology

MENG Zu-qiang, ZHOU Shi-quan, HUANG Bo-xiong   

  1. (College of Computer, Electronics and Information, Guangxi University, Nanning 530004, China)
  • Received:2011-09-19 Revised:2012-02-19 Online:2013-01-15 Published:2013-01-13

摘要: 基于分辨矩阵计算信息系统的所有约简,都需要将合取范式转化为析取范式,但是该转化过程存在组合爆炸问题。为解决该问题,根据合取范式、合取运算和析取运算的特点,构建析取范式转化的并行模型,提出基于多线程技术的分辨函数析取范式生成算法,利用Windows的自动线程调度功能提高范式转换的效率。实验结果表明,该算法的析取范式转化效率会随着合取范式长度的增加而提高,适合在多核CPU计算机上运行。

关键词: 属性约简, 分辨函数, 多线程技术, 并行模型, 析取范式

Abstract: It is required to translate conjunction normal form into disjunction normal form when using discernibility matrix to compute all reducts of an information system. But there exists the combination explosion problem in this transformation process. Following the properties of conjunction normal form, And operator and OR operator, this paper constructs a parallel model for the transformation process, and then proposes a multi-thread technology-based algorithm for generating disjunction normal forms. The proposed algorithm improves the efficiency of transformation by using the functions of automatic thread scheduling of Windows. Experimental results show that the algorithm seems more efficient in the cases where conjunction normal forms have relatively large length, making good use of multi-core CPU resources of computers.

Key words: attribute reduction, discernibility function, multi-thread technology, parallel model, disjunction normal form

中图分类号: