我有一组具有顺序关系的元素(可能很大):
[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.tail,set.tail.tail ...),每次到达节点时,我都会将相应的id添加到数组中。
我是否会在推理中错过任何特殊情况(如果意识到如果集合中不存在[a,b,c],如果我不想错过[a,c],我必须为
depth>2
的节点放置多个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]
通过一些数组操作,我应该能够将其与初始数组的元素相匹配。
最佳答案
如果要构建前缀树(又名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);
}
}
}
}
关于算法项目集匹配模式,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/32480800/