计算机工程 ›› 2007, Vol. 33 ›› Issue (21): 12-14.doi: 10.3969/j.issn.1000-3428.2007.21.005

• 博士论文 • 上一篇    下一篇

利用格结构特性生成概念格的算法

时百胜1,2,刘宗田1,余 泓2   

  1. (1. 上海大学计算机工程与科学学院,上海 200072;2. 苏州科技学院应用数学系,苏州 215009)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-11-05 发布日期:2007-11-05

Algorithm of Building Concept Lattice Based on Its Structure

SHI Bai-sheng1,2, LIU Zong-tian1, YU Hong2   

  1. (1. School of Computer Engineering and Science, Shanghai University, Shanghai 200072; 2. Department of Applied Mathematics, University of Science and Technology of Suzhou, Suzhou 215009)
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-11-05 Published:2007-11-05

摘要: 给出了概念格中关于后代和后继的一些性质,利用这些性质,提出了一种生成所有概念及其序关系的算法。对于任一形式概念,该算法能产生它的全部后代,并确认哪些后代为后继。为提高算法效率,采用了集合的精确匹配代替高代价的子集关系的检验。与现有算法相比,该算法的计算效率有显著的提高。

关键词: 概念格, 形式概念, 后代, 后继, 算法

Abstract: This paper gives some basic properties of children and successors in the concept lattice. By making use of these properties, it presents an algorithm to generate all concepts and its lattice order. Given a formal concept, this algorithm can produce all the children and identify all successors from them. During its implementation, the set exact matching takes place of against subset testing operations which is at a high price and the better computation efficiency is achieved.

Key words: concept lattice, formal concept, child, successor, algorithm

中图分类号: