خوارزمية / خطوات لإيجاد أطول البادئة البحث في باتريشيا Trie

Question

أقوم بتنفيذ PATRICIA يحاول بحث بادئة IP، يمكنني الحصول على التعليمات البرمجية التي تعمل في المباراة الرئيسية كاملة، ولكن تواجه مشاكل في البحث البادئة، عندما تكون هناك مفاتيح هي بادئات مفاتيح أخرى، مثل:

1.2.3.0
1.2.0.0

هل يمكن لأي شخص أن يساعدني في خوارزمية بحث البادئة في الحالة المذكورة أعلاه يجب أن أفكر في هذه المفاتيح ذات الطول المنفصل (أي / 24 و 16)؟

Answer 1

ألق نظرة على Net-Patricia. هذا هو تنفيذ Trie Patricia للبحث عن عناوين IP. الواجهة هي بيرل، ولكن الكود الأساسي في C. هنا رابط، ولكن يجب أن يكون لدى العديد من أرشيفات CPAN:

http://cpansearch.perl.org/src/philipp/net-patricia-1.15_07/libpatricia/patricia.c.

Answer 2

إذا كنت تستخدم هذه Trie لتخزين أرقام IP كعناصر ذات طول ثابت، فهي بالتأكيد ليست بالطريقة الصحيحة. النقطة هنا هي أن PT مفيدة بشكل خاص لتخزين بيانات الطول المتغير.

إذا قمت بتخزين أجزاء من أرقام IP، لأن البادئات ذات الطول المتغير ثم PT هو اختيار جيد.
في هذه الحالة، يجب أن تكون مفاتيحك ذات طول مختلف.
دعنا نقول أنك تقوم بتخزين البادئة "192.168" في Binary 0xC0 0xA8، يمكنك إضافة هذا ككل مفتاح.
بعد ذلك، عند البحث عن IP مثل 192.168.1.1 يمكنك الحصول على معلومات تحتوي على Trie على 192.168 وهي بادئة لما تبحث عنه.

كل ما عليك فعله هو تخزين "الجزء الشائع" أثناء عبور المريين.
هذه هي إضافة بسيطة إلى هذه تطبيق. فقط تأكد من أنه أثناء النزول إلى Trie يمكنك تخزين الجزء المشترك في مكان ما في معلمات الوظيفة المتكررة.
لفهم جيد ل patricia trie أود أن أقترح القراءة كتاب خوارزميات روبرت سبيعي وهو مصدر عظيم للمعرفة.

تعديل: هناك مشكلة واحدة عند تخزين سلاسل C في PT. تم تصميم هذه Trie لتخزين البيانات الثنائية، لكنك مهتم فقط في الحصول على بايت كاملة. تأكد من أنك تخزن جزءا مشتركا من البادئة فقط إذا كان حجمها في BITS مضاعف 8. للحصول على مثال خاطئ: لديك مفتاح في شجرةك: 0xc0 0xa5 وأنت تبحث Fro 0xC0 0xa6. سوف تتوقف اجتيازك عندما يكون الجزء المشترك "0xc0xa"، لكنك مهتما بأخذ "0xc0" فقط. لذلك تأكد من تخزين البايتات المشتركة، وليس بت.

Answer 3

هناك تطبيق ج قابل للقراءة إلى حد ما في رمز الاختبار ل LLVM: https://llvm.org/svn/llvm-project/test-suite/trunk/multisource/benchmarks/mibench/network-patricia/