कौन सी संरचना सर्वोत्तम प्रदर्शन परिणाम प्रदान करती है; trie (उपसर्ग पेड़), प्रत्यय पेड़ या प्रत्यय सरणी? क्या अन्य समान संरचनाएं हैं? इन संरचनाओं के अच्छे जावा कार्यान्वयन क्या हैं?ट्री बनाम प्रत्यय पेड़ बनाम प्रत्यय सरणी
संपादित करें: इस मामले में मैं ग्रंथों पर शब्दकोश के नामों की पहचान करने के लिए नामों के एक बड़े शब्दकोश और प्राकृतिक भाषा ग्रंथों के एक बड़े समूह के बीच स्ट्रिंग मिलान करना चाहता हूं।
ट्राई इस तरह की खोज की पहली डेटा संरचना थी।
प्रत्यय पेड़ त्रिभुज में सुधार है (इसमें प्रत्यय लिंक हैं जो रैखिक त्रुटि खोज की अनुमति देते हैं, प्रत्यय पेड़ त्रिभुज की अनावश्यक शाखाओं को ट्रिम करता है इसलिए इसे अधिक जगह की आवश्यकता नहीं होती है)।
प्रत्यय सरणी प्रत्यय पेड़ (कोई प्रत्यय लिंक (धीमी त्रुटि मिलान) के आधार पर एक अलग डेटा संरचना है, फिर भी पैटर्न मिलान बहुत तेज है)।
त्रिभुज वास्तविक दुनिया के उपयोग के लिए नहीं है क्योंकि यह बहुत अधिक जगह का उपभोग करता है।
प्रत्यय पेड़ त्रिभुज से तेज और तेज़ है और इसका उपयोग डीएनए को इंडेक्स करने या कुछ बड़े वेब सर्च इंजनों को अनुकूलित करने के लिए किया जाता है।
प्रत्यय सरणी प्रत्यय पेड़ की तुलना में कुछ पैटर्न खोजों में धीमी है लेकिन कम जगह का उपयोग करती है, और अधिक व्यापक रूप से प्रत्यय के पेड़ की तुलना में उपयोग की जाती है।
डेटा संरचनाओं की एक ही परिवार में:
अन्य कार्यान्वयन कर रहे हैं, सीएसटी एक प्रत्यय सरणी और कुछ अतिरिक्त डेटा संरचनाओं का उपयोग कर प्रत्यय पेड़ खोज क्षमताओं में से कुछ पाने के लिए प्रत्यय के पेड़ के एक कार्यान्वयन है।
एफसीएसटी इसे आगे ले जाता है, यह एक प्रत्यय सरणी के साथ एक नमूना प्रत्यय पेड़ लागू करता है।
डीएफसीएसटी एफसीएसटी का गतिशील संस्करण है।
विस्तार करना:
दो महत्वपूर्ण कारकों अंतरिक्ष उपयोग और संचालन निष्पादन समय कर रहे हैं। आपको लगता है कि आधुनिक दिन मशीनों के साथ यह प्रासंगिक नहीं है लेकिन एक इंसान के डीएनए को इंडेक्स करने के लिए 40 गीगाबाइट मेमोरी की आवश्यकता होगी (एक असम्पीडित और अपरिवर्तित प्रत्यय पेड़ का उपयोग करके)। और इस सूचकांक में से एक को इस डेटा में बनाने के लिए दिन लग सकते हैं। Google की कल्पना करें, इसमें बहुत सारे खोज योग्य डेटा हैं, उन्हें सभी वेब डेटा पर एक बड़ी अनुक्रमणिका की आवश्यकता है और जब भी कोई कोई वेब पेज बनाता है तो वे इसे नहीं बदलते हैं। उनके पास कैशिंग का कुछ रूप है। हालांकि मुख्य सूचकांक शायद स्थिर है। और हर हफ्ते या तो वे सभी नई वेब साइट्स और डेटा इकट्ठा करते हैं और एक नया इंडेक्स बनाते हैं, जब नया समाप्त हो जाता है तो पुराने को बदल दिया जाता है। मुझे नहीं पता कि वे कौन से एल्गोरिदम का उपयोग इंडेक्स में करते हैं, लेकिन शायद यह एक विभाजन डेटाबेस पर प्रत्यय वृक्ष गुणों के साथ एक प्रत्यय सरणी है।
सीएसटी 8 गीगाबाइट का उपयोग करता है, हालांकि प्रत्यय पेड़ संचालन की गति बहुत कम हो जाती है।
प्रत्यय सरणी कुछ 700 मेगास में 2 गीगा में भी ऐसा ही कर सकती है। हालांकि आपको डीएनए में एक प्रत्यय सरणी के साथ अनुवांशिक त्रुटियां नहीं मिलेंगी (अर्थात्: वाइल्डकार्ड के साथ पैटर्न की खोज करना बहुत धीमा है)।
एफसीएसटी (पूरी तरह संपीड़ित प्रत्यय पेड़) 800 से 1.5 गीगा में एक प्रत्यय पेड़ बना सकता है। सीएसटी की ओर एक छोटी सी गति में गिरावट के साथ।
डीएफसीएसटी एफसीएसटी की तुलना में 20% अधिक स्थान का उपयोग करता है, और एफसीएसटी के स्थिर कार्यान्वयन की गति को खो देता है (हालांकि गतिशील सूचकांक बहुत महत्वपूर्ण है)।
प्रत्यय पेड़ के कई व्यवहार्य (स्पेस वार) कार्यान्वयन नहीं हैं क्योंकि ऑपरेशन की गति को डेटा संरचनाओं को रैम स्पेस लागत की क्षतिपूर्ति करना बहुत मुश्किल है।
यह कहा गया है कि प्रत्यय पेड़ त्रुटियों के साथ मिलान पैटर्न के लिए बहुत ही रोचक खोज परिणाम है। अहो कोरसिक तेज़ नहीं है (हालांकि लगभग कुछ परिचालनों के लिए तेज़, त्रुटि मिलान नहीं) और बॉयर मूर धूल में छोड़ा गया है।
"रैखिक क्या है त्रुटि खोज "? –
रैखिक त्रुटि खोज एक त्रुटि खोज है जो रैखिक समय में सभी संभावित त्रुटि मिलान लौटाती है। उदाहरण के लिए, एक पाठ में "हाउस", "होसा", "हॉटसे" शब्द कहीं भी हैं। एक निरंतर त्रुटि मैच एक ऑपरेशन में सभी त्रुटियों को वापस कर देगा। रैखिक त्रुटि मैच COUNT (मैचों) में सभी त्रुटियों (मैचों) देता है। इस मामले में 2. कुछ इसे पाठ के आकार (त्रुटि के लिए पाठ स्कैन) पर एक रैखिक खोज के रूप में व्याख्या कर सकते हैं, और इसलिए लागत टेक्स्ट के आकार के बराबर होगी। लगभग सभी त्रुटि खोज एल्गोरिदम का मामला कौन सा है, हालांकि यह प्रत्यय पेड़ के मामले में नहीं है। –
प्रत्यय सरणी का लाभ प्रत्यय पेड़ की तुलना में कम जगह का उपयोग करता है। लेकिन हम उसे कैसे जान सकते हैं? क्या कोई गणितीय सबूत है या हम व्यावहारिक प्रयोगों पर आधारित हैं? –
प्रत्यय पेड़ का उपयोग करके आप कुछ लिख सकते हैं जो ओ (एन + एम + के) समय में आपके पाठ से आपके शब्दकोश से मेल खाता है, जहां आपके शब्दकोश में अक्ष है, एम आपके पाठ में अक्षर है, और के की संख्या है मैचों। इस के लिए प्रयास बहुत धीमे हैं। मुझे यकीन नहीं है कि एक प्रत्यय ऐरे क्या है, इसलिए मैं उस पर टिप्पणी नहीं कर सकता।
उसने कहा, यह कोड के लिए तुच्छ नहीं है और मुझे आवश्यक कार्यों को प्रदान करने वाले किसी भी जावा पुस्तकालयों के बारे में पता नहीं है।
प्रत्यय Arrays के बारे में: http://en.wikipedia.org/wiki/Suffix_array –
हाँ, मैं प्रत्यय Arrays पर पढ़ रहा हूँ। बाहर निकलें उनके पास सफ़िक्स पेड़ के समान असीमित गति है लेकिन अधिक जगह कुशल हैं। वे निश्चित रूप से एक विकल्प हैं। – swestrup
संपादित करें: इस मामले में मैं नाम का एक बड़ा शब्दकोश और प्राकृतिक भाषा के ग्रंथों के एक बड़े सेट के बीच स्ट्रिंग मिलान करने के लिए, क्रम में ग्रंथों पर शब्दकोश के नामों की पहचान करने के लिए चाहते हैं।
यह Aho-Corasick algorithm के लिए एक आवेदन की तरह लगता है: रैखिक में शब्दकोश से एक automaton (रेखीय समय में) है, जो तब से अधिक पाठों में शब्दकोश से कोई भी शब्द की सभी घटनाओं को खोजने के लिए इस्तेमाल किया जा सकता का निर्माण (भी पहर)।
क्या संचालन कर रही पर योजना है (these lecture notes में वर्णन है, विकिपीडिया पृष्ठ के "बाहरी लिंक" अनुभाग से जुड़ा हुआ है, एक बहुत पेज पर ही वर्णन से पढ़ने के लिए। आसान है)? libdivsufsort एक समय में सी
प्रत्यय सरणी निर्माण के लिए उस दक्षता को प्राप्त करने की तकनीक क्या है? – curious
समय पर सवाल। एम्पलैब ने गहराई से व्याख्या के साथ एक समांतर संस्करण जारी किया है, https://amplab.cs.berkeley.edu/publication/parallel-lightweight-wavelet-tree-suffix-array-and-fm-index-construction/ –
This प्रेरित सॉर्टिंग एल्गोरिदम (सैइस कहा जाता है) के कार्यान्वयन के लिए एक वास्तविक प्रत्यय सरणी कार्यान्वयन था, जिसमें प्रत्यय सरणी बनाने के लिए जावा संस्करण है।
Trie बनाम प्रत्यय पेड़
दोनों डेटा संरचना सुनिश्चित एक बहुत तेजी से ऊपर देखो, खोज के समय क्वेरी शब्द, जटिलता समय हे (एम) की लंबाई जहां मीटर क्वेरी की लंबाई है के लिए आनुपातिक है शब्द।
इसका मतलब यह है कि यदि हमारे पास 10 वर्ण हैं तो क्वेरी शब्द है, इसलिए हमें इसे खोजने के लिए अधिकतम 10 चरणों की आवश्यकता है।
Trie: तारों को संग्रहित करने के लिए एक पेड़ जिसमें प्रत्येक सामान्य उपसर्ग के लिए एक नोड होता है। तारों को अतिरिक्त पत्ते नोड्स में संग्रहित किया जाता है।
: किसी दिए गए स्ट्रिंग के प्रत्यय से संबंधित एक त्रिभुज का एक कॉम्पैक्ट प्रतिनिधित्व जहां एक बच्चे के साथ सभी नोड्स उनके माता-पिता के साथ विलय हो जाते हैं। एल्गोरिदम और डेटा संरचनाओं की शब्दकोश
आम तौर पर Trie, सूचकांक शब्दकोश शब्द (शब्दकोश) या तार उदाहरण डी = {ABCD, abcdd, bxcdf के किसी भी सेट करने के लिए इस्तेमाल .....:
डीईएफ़ से हैं, ZZZZ}
एक प्रत्यय टी = {abcdabcg, abcdabc, abcdab, abcda, एबीसीडी का टी = abcdabcg सभी प्रत्यय हमारे पाठ के सभी प्रत्यय पर एक ही डेटा संरचना "Trie" का उपयोग करके सूचकांक पाठ के लिए इस्तेमाल किया पेड़, एबीसी, एबी, ए}
अब यह तारों के समूहों की तरह दिखता है। हम तारों के इस समूह (टी के सभी प्रत्यय) पर एक ट्री का निर्माण करते हैं।
दोनों डेटा संरचना का निर्माण रैखिक है, यह समय और स्थान में ओ (एन) लेता है।
डिकोनरी (तारों का एक सेट) के मामले में: n = सभी शब्दों के वर्णों का योग। पाठ में : एन = पाठ की लंबाई।
प्रत्यय सरणी: संपीड़ित सैप में एक प्रत्यय पेड़ का प्रतिनिधित्व करने के लिए एक तकनीकी है, यह एक स्ट्रिंग के प्रत्यय की सभी शुरुआती स्थितियों की एक सरणी है।
यह खोज समय में प्रत्यय पेड़ से धीमा है।
अधिक जानकारी के लिए विकिपीडिया पर जाएं, इस विषय पर बात करने वाला एक अच्छा लेख है।
संचालन के लिए सर्वश्रेष्ठ प्रदर्शन? –