Fuse元组找到等价类

Question

假设我们有一个包含k个元素的有限域D = {d1,... dk}.

我们认为S是D ^ n的一个子集,即一组形式为<a1,..,an>的元组,其中ai为D.

我们希望使用S'(2 ^ D ^ n的子集)来表示它(紧凑地),即一组形式为<A1,...的元组>,其中Ai是D的子集.这意味着对于任何元组s在'S'中,Ai的叉积中的所有元素都存在于S.

例如,考虑D = {a,b,c}所以k = 3,n = 2并且元组S = <a,b> + <a,c> + <b,b> + <b,c>.

我们可以使用S'= <{a,b},{b,c}>来表示S.

这个单例解决方案也是最小的,S'= <{a},{b,c}> + <{b},{b,c}>也是一个解决方案,但它更大,因此不太理想.

在具体实例中,我们需要处理的一些大小:域D中的k~1000个元素,n <= 10相对较小(复杂性的主要来源),| S | 范围大于> 10 ^ 6.

一种天真的方法在于首先将S插入到S'2 ^ D ^ n的域中,然后使用以下测试,2',S'中的两个元组s1,s2可以融合以在S'iff中形成单个元组. .它们只有一个组成部分不同.

例如
<a,b> + <a,c> - > <{a},{b,c}>(第二部分不同)

<b,b> + <b,c> - > <{b},{b,c}>(第二个组成部分不同)

<{a},{b,c}> + <{b},{b,c}> - > <{a,b},{b,c}>(第一个组件不同)

现在可能有几个最小的S',我们有兴趣找到任何一个,并且某种最小化的近似值也可以,只要它们没有给出错误的结果(即使S'没有它可能的那么小) ,但我们得到非常快的结果).

朴素算法必须处理这样一个事实,即任何新引入的"融合"元组都可以与其他元组匹配,因此即使n保持低,它在大输入集上也会非常严重.你需要| S'| ^ 2比较以确保收敛,并且每当你融合两个元素时,我正在重新测试每一对(我怎么能改进它？).

很多效率都依赖于迭代顺序,因此以某种方式对集合进行排序可能是一个选项,或者可能是使用哈希进行索引,但我不知道该怎么做.

命令式伪代码是理想的,或指向重新设计问题的指针,我可以运行求解器的东西真的会有所帮助.

Answer 1

下面是一些伪代码（我尚未测试过的 C# 代码），它演示了S'=<{a},{b,c}>+<{b},{b,c}>方法。除了空间要求外，当对元素使用整数索引时，空间要求可以忽略不计；添加和测试元组的整体效率和速度应该非常快。如果您想要一个实用的解决方案，那么您已经有了一个，只需使用正确的 ADT。

ElementType[] domain = new ElementType[]; // a simple array of domain elements
  FillDomain(domain); // insert all domain elements
  SortArray(domain); // sort the domain elements  K log K time
SortedDictionary<int, HashSet<int>> subsets; // int's are index/ref into domain
subsets = new SortedDictionary<int, HashSet<int>>();
//
void AddTuple(SortedDictionary<int, HashSet<int>> tuples, ElementType[] domain, ElementType first, elementType second) {
    int a = BinarySearch(domain, first); // log K time (binary search)
    int b = BinarySearch(domain, second); // log K time (binary search)
    if(tuples.ContainsKey(a)) { // log N time (binary search on sorted keys)
        if(!tuples[a].Contains(b)) { // constant time (hash lookup)
            tuples[a].Add(b); // constant time (hash add)
        }         
    } else { // constant time (instance + hash add)
        tuples[a] = new HashSet<in>();
        tuples[a].Add(b);
    }
}
//
bool ContainsTuple(SortedDictionary<int, HashSet<int>> tuples, ElementType[] domain, ElementType first, ElementType second) {
    int a = BinarySearch(domain, first); // log K time (binary search)
    int b = BinarySearch(domain, second); // log K time (binary search)
    if(tuples.ContainsKey(a)) { // log N time (binary search on sorted keys)
        if(tuples[a].Contains(b)) { // constant time (hash test)
            return true;
        }
    }
    return false;
}

优化元组子集 S' 所节省的空间不会超过优化过程本身的减慢。对于大小优化（如果您知道 K 将小于 65536，您可以使用短整数而不是 SortedDictionary 和 HashSet 中的整数。但即使 5000 万个整数也只占用每个 32 位整数 4 个字节 * 5000 万 ~= 200 MB 。

编辑 这是另一种方法，通过将元组编码/映射到字符串，您可以利用二进制字符串比较以及 UTF-16 / UTF-8 编码非常高效的事实。同样，这仍然没有实现您想要的合并优化，但速度和效率会相当不错。

下面是一些 JavaScript 中的快速伪代码。

Array.prototype.binarySearch = function(elm) {
  var l = 0, h = this.length - 1, i; 
  while(l <= h) { 
    i = (l + h) >> 1; 
    if(this[i] < elm) l = ++i; 
    else if(this[i] > elm) h = --i; 
    else return i; 
  } 
  return -(++l); 
};
// map your ordered domain elements to characters 
// For example JavaScript's UTF-16 should be fine
// UTF-8 would work as well
var domain = {
  "a": String.fromCharCode(1),
  "b": String.fromCharCode(2),
  "c": String.fromCharCode(3),
  "d": String.fromCharCode(4)
}
var tupleStrings = [];
// map your tuple to the string encoding
function map(tuple) {
  var str = "";
  for(var i=0; i<tuple.length; i++) {
    str += domain[tuple[i]];
  }
  return str;
}
function add(tuple) {
  var str = map(tuple);
  // binary search
  var index = tupleStrings.binarySearch(str);
  if(index < 0) index = ~index;
  // insert depends on tupleString's type implementation
  tupleStrings.splice(index, 0, str);
}
function contains(tuple) {
  var str = map(tuple);
  // binary search 
  return tupleString.binarySearch(str) >= 0;
}

add(["a","b"]);
add(["a","c"]);
add(["b","b"]);
add(["b","c"]);
add(["c","c"]);
add(["d","a"]);
alert(contains(["a","a"]));
alert(contains(["d","a"]));
alert(JSON.stringify(tupleStrings, null, "\n"));