सेट की संपीड़न के लिए एल्गोरिदम

Question

मेरे पास सेट का संग्रह है जिसे मैं trie में रखना चाहता हूं।

सामान्य प्रयास तत्वों के तारों से बने होते हैं - अर्थात, तत्वों का क्रम महत्वपूर्ण है। सेट में परिभाषित आदेश की कमी है, इसलिए अधिक संपीड़न की संभावना है।

उदाहरण के लिए, तार "abc", "bc" दिया, और "c", मैं trie बनाएंगे:

(*,3) -> ('a',1) -> ('b',1) -> ('c',1) 
     -> ('b',1) -> ('c',1) 
     -> ('c',1) 

लेकिन सेट { 'a', 'b', 'c' }, { 'b', 'c' }, { 'c' } को देखते हुए, मैं ऊपर trie बना सकते हैं, या किसी इन ग्यारह में:

(*,3) -> ('a',1) -> ('b',1) -> ('c',1) 
     -> ('c',2) -> ('a',1) 

(*,3) -> ('a',1) -> ('c',1) -> ('b',1) 
     -> ('b',1) -> ('c',1) 
     -> ('c',1) 

(*,3) -> ('a',1) -> ('c',1) -> ('b',1) 
     -> ('c',2) -> ('a',1) 

(*,3) -> ('b',2) -> ('a',1) -> ('c',1) 
       -> ('c',1) 
     -> ('c',1) 

(*,3) -> ('b',1) -> ('a',1) -> ('c',1) 
     -> ('c',2) -> ('b',1) 

(*,3) -> ('b',2) -> ('c',2) -> ('a',1) 
     -> ('c',1) 

(*,3) -> ('b',1) -> ('c',1) -> ('a',1) 
     -> ('c',2) -> ('b',1) 

(*,3) -> ('c',2) -> ('a',1) -> ('b',1) 
     -> ('b',1) -> ('c',1) 

(*,3) -> ('c',2) -> ('a',1) -> ('b',1) 
       -> ('b',1) 

(*,3) -> ('c',2) -> ('b',1) -> ('a',1) 
     -> ('b',1) -> ('c',1) 

(*,3) -> ('c',3) -> ('b',2) -> ('a',1) 

तो स्पष्ट रूप से संपीड़न के लिए कमरा (7 नोड्स 4) है।

I संदिग्ध अपने बच्चों की सापेक्ष आवृत्ति पर निर्भर प्रत्येक नोड पर स्थानीय आदेश को परिभाषित करने से यह होगा, लेकिन मुझे यकीन नहीं है, और यह अत्यधिक महंगा हो सकता है।

तो इससे पहले कि मैंने व्हाइटबोर्ड मारा, और अपने स्वयं के संपीड़न एल्गोरिदम पर क्रैकिंग शुरू कर दिया, क्या कोई मौजूदा है? यह कितना महंगा है? क्या यह एक थोक प्रक्रिया है, या इसे प्रति-सम्मिलित/हटाया जा सकता है?

Answer 1

असल में आपको निर्भरता ग्राफ बनाना चाहिए। यदि तत्व वाई केवल तभी होता है जब एक्स होता है, तो x से y के किनारे खींचें (समानता के मामले में, बस क्रमिक रूप से क्रमबद्ध करें)। परिणामी ग्राफ एक डीएजी है। अब, मोड़ के साथ तत्वों का क्रम प्राप्त करने के लिए इस ग्राफ का एक स्थलीय सॉर्टिंग करें। जब भी आप दो (या अधिक तत्वों) में से एक चुन सकते हैं, तो अधिकतर घटनाओं वाले व्यक्ति को चुनें।

Answer 2

मुझे लगता है कि आपको आइटम आवृत्ति के अनुसार एक सेट सॉर्ट करना चाहिए और आपको संदेह है कि यह एक अच्छा हेरिस्टिक है। FP-growth (लगातार पैटर्न खनन) में कॉम्पैक्ट तरीके से प्रतिनिधित्व करने के लिए उपयोग करने के लिए एक ही दृष्टिकोण।

Answer 3

मेरा संदेह यह है कि अधिकतम संपीड़न शीर्ष पर सबसे आम तत्व रखेगा (जैसा कि आपके अंतिम उदाहरण में है)।

संपीड़न एल्गोरिथ्म सेट के पूरे संग्रह और शीर्ष नोड के साथ शुरू होता है, और रिकर्सिवली शामिल करने वाले प्रत्येक सबसेट के लिए नोड्स सबसे आम तत्वों

Compress(collection, node): 
    while NOT collection.isEmpty? 
     e = collection.find_most_common_element 
     c2 = collection.find_all_containing(e) 
     collection = collection - c2 
     if e==NIL //empty sets only 
     node[END_OF_SET]=node 
     else 
     c2.each{set.remove(e)} 
     node[e]=new Node 
     Compress(c2,node[e]) 
     end 
    end 

बनाने जिसके परिणामस्वरूप पेड़ होता है एक विशेष अंत के- यह इंगित करने के लिए मार्कर सेट करें कि एक पूर्ण सेट उस नोड पर समाप्त होता है। आपके उदाहरण के लिए यह

*->(C,3)->(B,2)->(A,1)->EOS 
       ->EOS 
      ->EOS 

होगा हटाया जा रहा है एक सेट में आसान है, बस इसे EOS मार्कर (और किसी भी माता-पिता नोड्स है कि खाली हो जाते हैं) है हटा दें। आप उड़ सकते हैं प्रत्येक नोड पर फ्लाई पर डालें, जब तक कोई मिलान न हो, तब तक अधिकांश बच्चों के साथ मेल खाने वाले तत्व में उतरें, फिर उपरोक्त एल्गोरिदम का उपयोग करें - लेकिन इसे अधिकतम संपीड़ित रखना मुश्किल होगा। जब तत्व बी ने तत्व ए की तुलना में अधिक बच्चों को प्राप्त किया, तो आपको बी 0 नोड में ए & बी वाले सभी सेटों को स्थानांतरित करना होगा, जिसमें सभी ए के बच्चों की पूर्ण खोज शामिल होगी। लेकिन अगर आप इसे संपीड़ित नहीं रखते हैं, तो समावेशन खोज अब सेट आकार के साथ रैखिक नहीं हैं।