| 主权项 |
1. A computer implemented method for verifying membership in one or more sets that are subsets of a global set, the method comprising:
representing members of the global set by mapping each member to a distinct Boolean variable of length d, wherein 2d is not less than the number of members in the global set; representing a subset of the global set by a Boolean expression which evaluates to a first value for any of the assignments to the Boolean variables which represent members of the subset, and which evaluates to a second value for any of the assignments to the Boolean variables which represent members of the global set that are not members of the subset, wherein the Boolean expression is constructed from one or more subsets so as to be evaluated efficiently for any assignment to the Boolean variables which represent members of the global set; and determining membership of a target member of the global set in a target subset of the global set by evaluating the Boolean expression that represents the target subset based on the mapping of the target member; wherein the Boolean expressions representing the subsets C of the global set are in disjunctive normal form (DNF) or conjunctive normal form (CNF)wherein the Boolean expression is represented by pairs of words y1z1, y1z2, . . . , ykzk, wherein yi and zi represent a first word and a second word of length d-bits or greater and are used to represent the ith clause in the Boolean expression; the jth bit in yi is 1 when the jth Boolean variable is present in the clause and 0 when it is not present; when it is present, then:
when the Boolean expression is in DNF: the jth bit in zi is 1 if the ith Boolean variable is true and 0 otherwise; and when the Boolean expression is in CNF: the jth bit in zi is 0 if the ith Boolean variable is true and 1 otherwise; wherein said representing members of the global set by mapping, said representing a subset of the global set by a Boolean expression, and said determining membership configured by a computing unit programmed to carry out perform the steps of the method using a processor; and wherein a member of the global set, g, represented by a mapping xg, is tested for membership in C, where: DNF: g is a member of C if for any i between 1 and k:
((xg XOR zi) AND yi)=0; CNF: g is not a member of C if for any i between 1 and k:
((xg XOR zi) AND yi)=0. |
