如何查找给定集合中多重集的所有子集？

Question

说我有多重集的一组D：

D = { 
    {d, g, o}, 
    {a, e, t, t}, 
    {a, m, t}, 
} 

给出一个多重M，像

M = {a, a, m, t} 

我想一个算法f给我的D是子集的所有元素（或更多精确地说，“子地图”）M：

f = {{a, m, t}} 

如果我们只执行一个这样的查询，则对D（在O(#D)时间内）的所有元素进行扫描显然是最佳的。但是如果我们想要回答许多相同的D和M这样的查询，我们可以通过将D预处理成更智能的数据结构来加快查询速度。

我们可以将D的全部内容转换为散列表，然后迭代所有可能的子集M，查看散列表中的每个子集，但这是O(2^#M)。对于小型M很好，对于中型到大型M不太好。

是否可以在#M的多项式时间内做到这一点？或者，也许是为了减少一个已知的NP完全问题，以证明这是不可能的快速？

编辑：我刚才意识到在最坏的情况下，我们需要输出所有D，所以#D仍然会出现在时间复杂度上。所以让我们假设输出的大小是由一些常数限定的。

Answer 1

这是TernarySearchTree（TST）的快速实现，它可以帮助解决您的问题。几年前，我受到DrDobbs的一篇文章的启发。您可以通过http://www.drdobbs.com/database/ternary-search-trees/184410528了解更多信息。它提供了一些关于TST和性能分析的背景知识。

在您的问题描述示例中，D将是包含“dgo”，“aett”和“amt”键的字典。这些值与密钥相同。

M是你的搜索字符串，它基本上是这样说的：“给我所有的字典中包含一个子集或所有这些字母的键的值”。字符的顺序并不重要。人物 '。'在搜索中用作通配符。

对于任何给定的M，此算法和数据结构不要求您查看D的所有元素。因此，在这方面它会很快。我还对访问节点数量和大部分时间做了一些测试，访问的节点数量只是字典中总节点的一小部分，即使对于找不到的密钥也是如此。

此算法还可以选择性地允许您输入限制字典返回的键的最小和最大长度。

对不起，冗长的代码，但它是完整的，你可以测试。

import java.util.ArrayList; 
import java.io.*; 

public class TSTTree<T> 
{ 
    private TSTNode<T> root; 
    private int size = 0; 
    private int totalNodes = 0; 

    public int getSize() { return size; } 

    public int getTotalNodes() { return totalNodes; } 

    public TSTTree() 
    { 
    } 

    public TSTNode<T> getRoot() { return root; } 

    public void insert(String key, T value) 
    { 
     if(key==null || key.length()==0) return; 

     char[] keyArray = key.toCharArray(); 

     if(root==null) root = new TSTNode<T>(keyArray[0]); 
     TSTNode<T> currentNode = root; 
     TSTNode<T> parentNode = null; 

     int d = 0; 
     int i = 0; 

     while(currentNode!=null) 
     { 
      parentNode = currentNode; 
      d = keyArray[i] - currentNode.getSplitChar(); 
      if(d==0) 
      { 
       if((++i) == keyArray.length) // Found the key 
       { 
        if(currentNode.getValue()!=null) 
         System.out.println(currentNode.getValue() + " replaced with " + value); 
        else 
         size++; 
        currentNode.setValue(value);  // Replace value at Node 
        return; 
       } 
       else 
        currentNode = currentNode.getEqChild(); 
      } 
      else if(d<0) 
       currentNode = currentNode.getLoChild(); 
      else 
       currentNode = currentNode.getHiChild(); 
     } 

     currentNode = new TSTNode<T>(keyArray[i++]); 
     totalNodes++; 
     if(d==0) 
      parentNode.setEqChild(currentNode); 
     else if(d<0) 
      parentNode.setLoChild(currentNode); 
     else 
      parentNode.setHiChild(currentNode); 

     for(;i<keyArray.length;i++) 
     { 
      TSTNode<T> tempNode = new TSTNode<T>(keyArray[i]); 
      totalNodes++; 
      currentNode.setEqChild(tempNode); 
      currentNode = tempNode; 
     } 

     currentNode.setValue(value);  // Insert value at Node 
     size++; 
    } 

    public ArrayList<T> find(String charsToSearch) { 
     return find(charsToSearch,1,charsToSearch.length()); 
    } 

    // Return all values with keys between minLen and maxLen containing "charsToSearch". 
    public ArrayList<T> find(String charsToSearch, int minLen, int maxLen) { 
     ArrayList<T> list = new ArrayList<T>(); 
     char[] charArray = charsToSearch.toCharArray(); 
     int[] charFreq = new int[256]; 
     for(int i=0;i<charArray.length;i++) charFreq[charArray[i]]++; 
     maxLen = charArray.length>maxLen ? maxLen : charArray.length; 
     pmsearch(root,charFreq,minLen,maxLen,1, list); 
     return list; 
    } 

    public void pmsearch(TSTNode<T> node, int[] charFreq, int minLen, int maxLen, int depth, ArrayList<T> list) { 
     if(node==null) return; 

     char c = node.getSplitChar(); 
     if(isSmaller(charFreq,c)) 
      pmsearch(node.getLoChild(),charFreq,minLen,maxLen,depth,list); 
     if(charFreq[c]>0) { 
      if(depth>=minLen && node.getValue()!=null) list.add(node.getValue()); 
      if(depth<maxLen) { 
       charFreq[c]--; 
       pmsearch(node.getEqChild(),charFreq,minLen,maxLen,depth+1,list); 
       charFreq[c]++; 
      } 
     } 
     else if(charFreq['.']>0) { // Wildcard 
      if(depth>=minLen && node.getValue()!=null) list.add(node.getValue()); 
      if(depth<maxLen) { 
       charFreq['.']--; 
       pmsearch(node.getEqChild(),charFreq,minLen,maxLen,depth+1,list); 
       charFreq['.']++; 
      } 
     }    
     if(isGreater(charFreq,c)) 
      pmsearch(node.getHiChild(),charFreq,minLen,maxLen,depth,list); 
    } 

    private boolean isGreater(int[] charFreq, char c) { 
     if(charFreq['.']>0) return true; 

     boolean retval = false; 
     for(int i=c+1;i<charFreq.length;i++) { 
      if(charFreq[i]>0) { 
       retval = true; 
       break; 
      } 
     } 
     return retval; 
    } 

    private boolean isSmaller(int[] charFreq, char c) { 
     if(charFreq['.']>0) return true; 

     boolean retval = false; 
     for(int i=c-1;i>-1;i--) { 
      if(charFreq[i]>0) { 
       retval = true; 
       break; 
      } 
     } 
     return retval; 
    } 
} 

下面是一个小测试程序。测试程序只需按照确切的顺序在您的示例中插入4个键/值对。如果你有一个有很多元素的D，那么最好先将它排序并以锦标赛的方式构建字典（即插入中间元素，然后递归填充左半部分和右半部分）。这将确保树是平衡的。

import org.junit.*; 
import org.junit.runner.*; 
import java.io.*; 
import java.util.*; 
import org.junit.runner.notification.Failure; 

public class MyTest 
{ 
    static TSTTree<String> dictionary = new TSTTree<String>(); 

    @BeforeClass 
    public static void initialize() { 
     dictionary.insert("dgo","dgo"); 
     dictionary.insert("aett","aett"); 
     dictionary.insert("amt","amt"); 
    } 

    @Test 
    public void testMethod() { 
     System.out.println("testMethod"); 
     ArrayList<String> result = dictionary.find("aamt"); 
     System.out.println("Results: "); 
     for(Iterator it=result.iterator();it.hasNext();) { 
      System.out.println(it.next()); 
     } 
    } 

    @Test 
    // Test with a wildcard which finds "dgo" value 
    public void testMethod1() { 
     System.out.println("testMethod1"); 
     ArrayList<String> result = dictionary.find("aamtdo."); 
     System.out.println("Results: "); 
     for(Iterator it=result.iterator();it.hasNext();) { 
      System.out.println(it.next()); 
     } 
    } 

    public static void main(String[] args) { 
     Result result = JUnitCore.runClasses(MyTest.class); 
     for (Failure failure : result.getFailures()) { 
     System.out.println(failure.toString()); 
     } 
    } 
}