FP-ट्री का प्रतिनिधित्व क्या है?

एक FP-ट्री इनपुट डेटा का एक ठोस विवरण है। इसे डेटा सेट को एक समय में एक लेनदेन पढ़कर और प्रत्येक लेनदेन को FP-ट्री में एक मार्ग पर मैप करके इकट्ठा किया जाता है। कई लेनदेन कई आइटम साझा कर सकते हैं, उनके मार्ग ओवरलैप हो सकते हैं।

मार्ग एक-दूसरे के साथ जितना अधिक ओवरलैप करते हैं, FP-ट्री वास्तुकला का उपयोग करके उतना अधिक संपीड़न लागू किया जा सकता है। यदि FP-ट्री का आकार मुख्य मेमोरी में फिट होने के लिए पर्याप्त है, तो यह हमें डिस्क पर सहेजे गए डेटा पर बार-बार पास बनाने के बजाय मेमोरी में वास्तुकला से सीधे लगातार आइटमसेट निकालने में सक्षम करेगा।

ट्री में प्रत्येक नोड एक आइटम का लेबल शामिल करता है साथ ही एक काउंटर जो दिए गए मार्ग पर मैप किए गए लेनदेन की संख्या प्रदर्शित करता है। मूल रूप से, FP-ट्री में केवल नल प्रतीक द्वारा परिभाषित रूट नोड शामिल होता है।

FP-ट्री को निम्नलिखित तरीकों से जारी रखा जाता है -

डेटा सेट को एक बार खोजा जाता है ताकि प्रत्येक आइटम की सपोर्ट काउंट तय की जा सके। कम बारंबारता वाले आइटम हटा दिए जाते हैं, जबकि लगातार आइटम घटती सपोर्ट काउंट में स्थिर होते हैं।

एल्गोरिदम FP ट्री बनाने के लिए डेटा पर दूसरा पास बनाता है। पहली लेनदेन {a, b} की समीक्षा के बाद, a और b के रूप में लेबल किए गए नोड्स उत्पन्न होते हैं। नल → a → b से एक मार्ग लेनदेन को एन्कोड करने के लिए बनाया जाता है। मार्ग के साथ प्रत्येक नोड की आवृत्ति गिनती 1 होती है।

दूसरे लेनदेन {b, c, d} की समीक्षा के बाद, आइटम b, c, और d के लिए नोड्स का एक नया सेट उत्पन्न होता है। नल → b → c → d नोड्स को जोड़कर लेनदेन को परिभाषित करने के लिए एक मार्ग बनाया जाता है।

इस मार्ग के साथ प्रत्येक नोड की आवृत्ति गिनती भी एक के समान होती है। हालांकि पहले दो लेनदेन में एक आइटम सामान्य है, जो b है, उनके मार्ग असंयुक्त हैं क्योंकि लेनदेन एक सामान्य उपसर्ग साझा नहीं करते हैं।

तीसरा लेनदेन {a, c, d, e}, पहले लेनदेन के साथ एक सामान्य उपसर्ग आइटम (जो a है) साझा करता है। तदनुसार, तीसरे लेनदेन का मार्ग, नल → a → c → d → e, पहले लेनदेन के मार्ग, नल → a → b के साथ ओवरलैप करता है। उनके ओवरलैपिंग मार्ग के कारण, नोड a के लिए आवृत्ति गिनती दो तक बढ़ जाती है, जबकि हाल ही में बनाए गए नोड्स c, d, और e के लिए आवृत्ति गिनती एक के समान होती है।

यह चरण तब तक जारी रहता है जब तक प्रत्येक लेनदेन को FP-ट्री में दिए गए मार्गों में से एक पर मैप नहीं किया जाता। FP-ट्री का आकार असंपीड़ित डेटा के आकार से छोटा होता है क्योंकि मार्केट बास्केट जानकारी में कई लेनदेन अधिक आइटम साझा करते हैं।