एक प्रत्यय पेड़ और उपयोग के लघु, जावा कार्यान्वयन?

Question

मैं जावा में एक छोटी, सरल प्रत्यय वृक्ष भवन/उपयोग एल्गोरिदम की तलाश में हूं। सबसे अच्छा जो मैंने पाया है वह अब तक सेमेन्टिक डिस्कवरी टूलकिट के साथ है, लेकिन कार्यान्वयन कई हज़ार लाइन लंबी है और कई वर्गों को फैलाता है। आदर्श रूप से, कार्यान्वयन जितना संभव हो उतना छोटा होगा और कुछ सौ लाइनों से अधिक नहीं होगा।

क्या किसी के पास ऐसा कोई कार्यान्वयन है?

Answer 1

कार्ककेन और सैंडर्स द्वारा "सरल रैखिक कार्य प्रत्यय ऐरे निर्माण" लेख, सी ++ की 50 पंक्तियों के साथ समाप्त होता है। आप शायद एलसीपी सरणी का उत्पादन करने के लिए कुछ भी चाहते हैं। एस और प्रत्यय सरणी पीओएस दिए गए, "रैखिक समय में एलसीपी सरणी की गणना" के लिए गुगलिंग। आपको वह मिलना चाहिए

Answer 2

आप mine भी ले सकते हैं लेकिन यह Ukkonen के एल्गोरिदम नहीं है - अन्य सभी सरल दृष्टिकोणों के रूप में, यह वर्गबद्ध समय में चलता है। मैं मानता हूं कि एक बेवकूफ एल्गोरिदम (जो छोटे अनुक्रमों के लिए ठीक काम कर सकता है) आधे दिन में लिखना आसान है।

Answer 3

मैंने बस एक प्रत्यय पेड़ के जावा कार्यान्वयन को समाप्त किया। मेरे blog entry में आप प्रत्यय पेड़ों के बारे में अधिक जानकारी प्राप्त कर सकते हैं, मेरी लाइब्रेरी का उपयोग कैसे करें, साथ ही सबवर्सन और मेवेन का उपयोग करके लाइब्रेरी डाउनलोड और निर्माण करें। हां, यह एक वर्ग फ़ाइल में केवल कुछ पंक्तियों से अधिक है, लेकिन यह अत्यधिक दस्तावेज है और वास्तविक दुनिया में व्यावहारिक उद्देश्यों के लिए उपयोग के लिए बनाया गया है। इसके अलावा, यह रैखिक समय निर्माण के लिए Ukkonen दृष्टिकोण का उपयोग करता है। (यहां नोट किए गए अधिकांश कार्यान्वयन में कम से कम ओ (एन^2) चलने का समय है।)