算法项集匹配模式

Question

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

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

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

[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 的节点放置多个 id，如果我不想错过 [a,c] if [a ,b,c] 存在于集合中) ?是否可以使用更复杂的数据结构来缩短处理时间？

编辑:事实上在深度 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} 的前缀树按字母顺序连续 看起来像这样:

──null
   ├──a : 1
   |  |
   |  └──b : 4
   |     |
   |     └──c : 6
   |
   ├──b : 2
   |  |
   |  └──c : 5
   |
   └──c : 3

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

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

Node.java

class Node
{
    public String str;
    public ArrayList<String> child;

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

MyTree.java

class MyTree
{
    Node head;

    ..

    public void build_tree(String [] symbol)
    {
        this.head = new Node("");
        build(symbol,head,0,symbol.length-1);
    }

    // build the prefix tree through DFS
    private void build(String [] symbol, Node parent, int start, int end)
    {
        Node ch = null;
        for (int i=start; i<=end; i++)
        {
            ch = new Node(symbol[i]);
            parent.child.add(ch);

            if (end - start > 0)
            {
                build(symbol,ch,i,end);
            }
        }
    }
}