Алгоритм сопоставления НИКАКИХ гарантий шаблон

Question

У меня есть набор элементов (потенциально большой) с отношением порядка:

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

и набор частых паттернов (потенциально большой) с идентификаторами:

[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] 

Я хочу сопоставить каждый набор в последовательности с идентификаторами соответствующего модели:

[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 ...), каждый раз, когда я достигаю узла, я добавляю соответствующие идентификаторы в массив.

Я пропустил какой-либо особый случай в своих рассуждениях (только что понял, что я должен поместить несколько идентификаторов для узлов depth>2, если я не хочу пропустить [a, c], если [a, b, c] существуют в задавать) ? Есть ли более сложная структура данных, которую я могу использовать для улучшения времени обработки?

Редактировать: Фактически на глубине n мне нужно 2^(n-2) ids с моим методом (учитывая, что мое дерево плотно). Я не уверен, что это правильный способ сделать это ...

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