एल्गोरिथ्म/चरणों पेट्रीसिया Trie में सबसे लंबे समय तक उपसर्ग खोज खोजने के लिए

Question

कार्यान्वयन के लिए मैं कर रहा हूँ पेट्रीसिया आईपी उपसर्ग देखने के लिए कोशिश करता है, मैं कोड पूरा कुंजी मैच के लिए काम, लेकिन उपसर्ग खोज, के साथ समस्याओं का सामना करना पड़ मिल सकता है जब वहाँ चाबियाँ हैं जो कर रहे हैं अन्य चाबियों का उपसर्ग, जैसे:

1.2.3.0 
1.2.0.0 

किसी को भी उपरोक्त मामले में उपसर्ग खोजों के लिए एल्गोरिथ्म के साथ मेरी मदद कर सकते मैं अलग लंबाई की कुंजी के रूप में इन पर विचार करना चाहिए (यानी,/24 और 16)?

Answer 1

नेट-पेट्रीसिया पर एक नज़र डालें। यह आईपी पते देखने के लिए पेट्रीसिया ट्राई का कार्यान्वयन है। इंटरफ़ेस पर्ल है, लेकिन अंतर्निहित कोड सी में है यहाँ एक कड़ी है, लेकिन कई CPAN अभिलेखागार यह होना चाहिए:

http://cpansearch.perl.org/src/PHILIPP/Net-Patricia-1.15_07/libpatricia/patricia.c

Answer 2

यदि आप आईपी संख्याओं को निश्चित लंबाई के तत्वों के रूप में संग्रहीत करने के लिए इस त्रिभुज का उपयोग करते हैं तो यह निश्चित रूप से सही तरीका नहीं है। यहां बिंदु यह है कि पीटी चरम लंबाई डेटा भंडारण के लिए विशेष रूप से उपयोगी है।

यदि आप चर संख्या के उपसर्ग के रूप में आईपी संख्याओं के हिस्सों को संग्रहीत करते हैं तो पीटी एक अच्छी पसंद है।
इस मामले में हाँ आपकी चाबियाँ अलग-अलग लंबाई का होना चाहिए।
मान लें कि आप बाइनरी 0xC0 0xA8 में उपसर्ग "192.168" संग्रहीत कर रहे हैं, आप इसे पहली कुंजी के रूप में जोड़ते हैं।
फिर, जब आप आईपी की खोज 1 9 2.168.1.1 की तरह करते हैं तो आप जानकारी प्राप्त कर सकते हैं कि आपके त्रिभुज में 1 9 2.168 है जो आप ढूंढ रहे हैं इसका एक उपसर्ग है।

आपको केवल त्रिभुज के दौरान "सामान्य भाग" को स्टोर करना है।
यह this कार्यान्वयन के लिए मामूली अतिरिक्त है। बस सुनिश्चित करें कि त्रिभुज नीचे जाने के दौरान आप रिकर्सिव फ़ंक्शन के पैरामीटर में कहीं भी सामान्य भाग को स्टोर करते हैं।
पेट्रीसिया ट्राई की अच्छी समझ के लिए मैं Robert Sedgewick's Algorithms book पढ़ने का सुझाव दूंगा जो ज्ञान का एक बड़ा स्रोत है।

संपादित करें: पीटी में सी स्ट्रिंग को संग्रहीत करते समय एक समस्या है। यह trie बाइनरी डेटा स्टोर करने के लिए डिज़ाइन किया गया है, लेकिन आप केवल पूरे बाइट प्राप्त करने में रुचि रखते हैं। सुनिश्चित करें कि आप केवल उपसर्ग के सामान्य भाग को संग्रहीत कर रहे हैं यदि बिट्स में इसका आकार 8 से अधिक है। गलत उदाहरण के लिए: आपके पास अपने पेड़ में कुंजी है: 0xC0 0xA5 और आप 0xC0 0xA6 से देख रहे हैं। आपका ट्रैवर्सल सामान्य भाग "0xC0 0xA" पर रुक जाएगा, लेकिन आप केवल "0xC0" लेने में रुचि रखते हैं। तो बिट बाइट्स, सामान्य बाइट्स को स्टोर करना सुनिश्चित करें।

Answer 3

LLVM के लिए परीक्षण कोड में एक काफी पठनीय सी कार्यान्वयन नहीं है: https://llvm.org/svn/llvm-project/test-suite/trunk/MultiSource/Benchmarks/MiBench/network-patricia/