एल्गोरिथ्म पैटर्न

Question

मिलान मैं तत्वों (संभावित बड़ा) एक आदेश संबंध के साथ का एक सेट है itemset मेरे पास आदेशित सेट का अनुक्रम है:

[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 के नोड्स के लिए एकाधिक आईडी डालना है यदि मैं [ए, सी] याद नहीं करना चाहता हूं यदि [ए, बी, सी] मौजूद है सेट) ? क्या कोई और परिष्कृत डेटा संरचना है जिसका उपयोग मैं प्रसंस्करण समय में सुधार के लिए कर सकता हूं?

संपादित करें: वास्तव में गहराई से, मुझे अपनी विधि के साथ 2^(n-2) आईडी की आवश्यकता है (मेरे पेड़ को घने पर विचार करना)। मुझे यकीन है कि यह यह करने के लिए एक वैध तरीका है नहीं कर रहा हूँ ...

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