算法项目集匹配模式

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添加到一个数组中。

在我的推理中是否错过了任何特殊情况（刚意识到如果不想错过[a,c]，则对于depth>2的节点必须放入多个id，例如存在[a,b,c]）？有没有更复杂的数据结构可以用来提高处理时间？

编辑：事实上，在深度n处，我需要使用我的方法2^(n-2)个id（考虑到我的树是密集的）。我不确定这是有效的方法...

编辑2：另一种方法是合并序列中每个单个元素的位图以建立每个模式（如SPADE算法中所用）。

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

通过一些数组操作，我应该能够将其与我的初始数组元素匹配。

- Alex

---

你可以构建一个DFA（“字典引擎”）来识别流中的所有六种模式。（这基本上就是fgrep所做的） - wildplasser

@wildplasser，我可能有很多元素和模式（唯一的约束是元素按模式排序），DFA是否仍然是有效的方法？你有任何实现参考吗？ - Alex

http://www.dcs.kcl.ac.uk/staff/mac/TSP/（第一章，第47页，如我所记）或可能是龙书。 - wildplasser

你实际的问题是什么？看起来你有一个问题，如果你能有效地解决这个问题，那么你就可以解决它。但是，对于序列中的每个长集合，你将会放入指数数量的ID，因此没有有效的解决方案。然而，你最初的问题可能更容易解决。 - btilly

看起来最好的方法是通过合并序列中每个单独元素位置的位图来构建不同的模式。 - Alex

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);
            }
        }
    }
}

- Khaled.K