基数比较法—高效的信息表求核方法

Comparing radix method—efficient approach to compute core of information table

目前的求核方法大多基于决策表,基于信息表的报道不多。为此,先寻找理论依据,说明了U/C与U(/C-{a})的内在关系,证明了U(/C-{a})≠U/C与真细分的等价性,证明了可以通过比较等价类和它子类的基数来判断是否真细分。然后基于最高位优先基数排序思想,应用正整数有序分拆特性定义了一个用于记录和比较等价类基数的数组,接着设计了一个信息表求核算法,时间复杂度为O(|C|2|U)|,空间复杂度为O(|U)|。算法的主要贡献是将求核问题转化为等价类生成过程中的集合基数比较问题。通过实例验证了算法的正确性。

At present,approaches to compute the core based on decision table are in the overwhelming majority,and based on information table are in the tiny minority.For this reason,beginning with seeking theoretical basis,the inherent correlation between U/C and U/（C-{a}） is explained,and the equivalence relation between UI（C-{a}）#U/C and real subdivision is discovered,and so is that real subdivision can be judged whether it is true or not by comparing an equivalence class radix with its subclass＇s.Then basing on principle of most significant ditital radix sorting,and applying property of positive integer ordered partition,an array used for recording and comparing the radix of equivalence classes is defined,and then an algorithm for computing the core of information table is designed.Its time complexity is O（｜C｜^2｜U｜）,and the space complexity is O（｜U｜）.The important contribution that it made is the way to get the core is transformed into comparing set radix during the course of generating equivalence classes.Its correctness is verified by the example.