算法项集匹配模式

Question

我有一组具有订单关系的元素(可能很大):

[a,b,c,d,e,f] 

和一组带有id的频繁模式(可能很大):

[a]:1,[b]:2,[c]:3,[a,b]:4,[b,c]:5,[a,b,c]:6

我有一系列有序集:

[a,b], [e], [c], [e,f], [a,b,c]

我想将序列中的每个集合与相应模式的ID匹配:

[a,b]:{1,2,4}, [e]:{}, [c]:{3}, [a,b,c]:{1,2,3,4,5,6}

我的目标是限制序列上的传递次数,因此我想构建一个我可以在扫描期间使用的数据结构.我在想一个前缀树:

??null
   ???a : 1
   |  |
   |  ???b : 4
   |     |
   |     ???c : { 5, 6 }
   |
   ???b : 2
   |  |
   |  ???c : 5
   |
   ???c : 3

我扫描序列中的一个集合,并通过递归多次传递它(set,set.tail,set.tail.tail ...),每当我到达一个节点时,我将相应的id添加到数组中.

我是否会错过我的推理中的任何特殊情况(只是意识到depth>2如果我不想错过[a,c]如果[a,b,c]存在于集合中,我必须为节点添加多个id )？我可以使用更复杂的数据结构来改善处理时间吗？

编辑:事实上在深度n,我需要2^(n-2)用我的方法的id(考虑到我的树是密集的).我不确定这是一个有效的方法......

Edit2:另一种合并序列中每个元素的位图以构建每个模式的方法(如SPADE算法中所使用的).

a  : [1,0,0,0,1]
b  : [0,1,0,0,1]
ab : [0,0,0,0,1]

通过一些数组操作,我应该能够将它与我的初始数组的元素相匹配.

Answer 1

如果您正在构建前缀树（又名 trie），则所有节点都是唯一的，因此集合的前缀树按{a,b,c} 字母顺序排列且具有连续性前缀树如下所示：

\n\n

\xe2\x94\x80\xe2\x94\x80null\n   \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80a : 1\n   |  |\n   |  \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80b : 4\n   |     |\n   |     \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80c : 6\n   |\n   \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80b : 2\n   |  |\n   |  \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80c : 5\n   |\n   \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80c : 3\n

\n\n

它映射到前缀集{ a, b, c, ab, bc, abc }。

\n\n

树的空间复杂度为SUM k for k = 1..N ~ O(N^2)。

\n\n

节点.java

\n\n

class Node\n{\n    public String str;\n    public ArrayList<String> child;\n\n    public Node (String str)\n    {\n        this.str = str;\n        this.child = new ArrayList<String>();\n    }\n}\n

\n\n

MyTree.java

\n\n

class MyTree\n{\n    Node head;\n\n    ..\n\n    public void build_tree(String [] symbol)\n    {\n        this.head = new Node("");\n        build(symbol,head,0,symbol.length-1);\n    }\n\n    // build the prefix tree through DFS\n    private void build(String [] symbol, Node parent, int start, int end)\n    {\n        Node ch = null;\n        for (int i=start; i<=end; i++)\n        {\n            ch = new Node(symbol[i]);\n            parent.child.add(ch);\n\n            if (end - start > 0)\n            {\n                build(symbol,ch,i,end);\n            }\n        }\n    }\n}\n

\n