संपीड़ित पाठ फ़ाइलों में तेज खोज

Question

मुझे ज़िप्ड की बड़ी संख्या में फ़ाइलों (.txt) में टेक्स्ट खोजने में सक्षम होना चाहिए। संपीड़न किसी और चीज में बदला जा सकता है या यहां तक ​​कि स्वामित्व बन गया है। मैं सभी फ़ाइलों को अनपॅक करने और खोज स्ट्रिंग को संपीड़ित (एन्कोड) से बचाना चाहता हूं और संपीड़ित फ़ाइलों में खोज करना चाहता हूं। यह सभी फ़ाइलों के लिए एक ही कोडबुक के साथ हफमैन संपीड़न का उपयोग करना संभव होना चाहिए। मैं पहिया का पुन: आविष्कार नहीं करना चाहता, इसलिए .. कोई भी ऐसी लाइब्रेरी जानता है जो ऐसा कुछ करता है या हफमैन एल्गोरिदम जिसे लागू और परीक्षण किया जाता है, या शायद एक बेहतर विचार है?

धन्यवाद अग्रिम

Answer 1

अधिकांश टेक्स्ट फ़ाइलों को LZ-family एल्गोरिदम के साथ संपीड़ित किया जाता है, जो Dictionary Coder को Entropy Coder जैसे हफमैन के साथ जोड़ती है।

क्योंकि शब्दकोश कोडर निरंतर अद्यतन "शब्दकोश" पर निर्भर करता है, इसका कोडिंग परिणाम इतिहास पर निर्भर करता है (शब्दकोष में सभी कोड जो वर्तमान डेटा तक इनपुट डेटा से प्राप्त होते हैं), इसलिए यह नहीं है किसी पिछले स्थान पर कूदने और पहले के सभी डेटा को डीकोड किए बिना, डीकोडिंग शुरू करना संभव है।

मेरी राय में, आप केवल एक zlib स्ट्रीम डिकोडर का उपयोग कर सकते हैं जो डिकंप्रेस्ड डेटा लौटाता है क्योंकि यह पूरी फ़ाइल को डिकंप्रेसर करने के इंतजार के बिना चला जाता है। यह निष्पादन समय को सहेज नहीं पाएगा लेकिन स्मृति को बचाएगा।

एक दूसरा सुझाव अंग्रेजी शब्दों पर हफमैन कोडिंग करना है, और शब्दकोश कोडर भाग के बारे में भूलना है। प्रत्येक अंग्रेजी शब्द को एक अद्वितीय उपसर्ग-मुक्त कोड में मैप किया जाता है।

अंत में, @SHODAN ने सबसे समझदार सुझाव दिया, जो फ़ाइलों को अनुक्रमणित करना, सूचकांक को संपीड़ित करना और संकुचित पाठ फ़ाइलों के साथ बंडल देना है। एक खोज करने के लिए, केवल इंडेक्स फ़ाइल को डिकंप्रेस करें और शब्दों को देखें। यह वास्तव में शब्दों पर हफमैन कोडिंग करने में सुधार है - एक बार आपको शब्दों की आवृत्ति (एक बार उपसर्ग कोड असाइन करने के लिए) मिलती है, तो आप पहले ही इंडेक्स बना चुके हैं, ताकि आप इंडेक्स को खोज के लिए रख सकें।

Answer 2

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

Answer 3

यह संभावना नहीं है कि आप एक संपीड़ित फ़ाइल में असंपीड़ित तारों को खोज सकेंगे। मुझे लगता है कि आपके सर्वोत्तम विकल्पों के लिए एक फाइल को किसी भी तरह से अनुक्रमणित करना है। शायद लुसीन का उपयोग करना?

Answer 4

संपीड़ित फ़ाइलों में पाठ की खोज असम्पीडित टेक्स्ट फ़ाइलों में एक ही चीज़ की खोज करने से तेज़ी से हो सकती है।

एक संपीड़न तकनीक मैंने देखा है इसी क्रम में कुछ जगह बलिदान तेजी से खोज करने के लिए:

• पाठ में प्रत्येक शब्द का 2^16 प्रविष्टियों के साथ एक शब्दकोश बनाए रखें। शाब्दिक बाइट्स के लिए पहली 256 प्रविष्टियों को आरक्षित करें, यदि आप किसी ऐसे शब्द पर आते हैं जो शब्दकोश में नहीं है - भले ही कई बड़े ग्रंथों में 32,000 से अधिक अद्वितीय शब्द हैं, इसलिए उन्हें कभी भी उन शाब्दिक बाइट्स का उपयोग करने की आवश्यकता नहीं है।
• प्रत्येक शब्द के लिए 16-बिट शब्दकोश सूचकांक को प्रतिस्थापित करके मूल पाठ को संपीड़ित करें।
• (वैकल्पिक) सामान्य मामले दो शब्दों एक भी अंतरिक्ष चरित्र से अलग कर दिया जाता है, कि अंतरिक्ष चरित्र त्यागें; अन्यथा शब्दों में शब्दों के बीच स्ट्रिंग में सभी बाइट्स को विशेष "शब्द" (उदाहरण के लिए, "।" और "," और "\ n") के रूप में "कोई डिफ़ॉल्ट रिक्त स्थान" विशेषता के साथ टैग किया गया है, और फिर "संपीड़ित करें" "उन स्ट्रिंग्स को संबंधित शब्दकोश इंडेक्स के साथ बदलकर। उसी तरह से वाक्यांश संपीड़ित करने, और ठीक उसी तरह आप मूल पाठ में मूल स्ट्रिंग के लिए खोज करेंगे में संकुचित पाठ में बाइट्स की संकुचित स्ट्रिंग को खोजते हुए शब्द या वाक्यांश के लिए
• खोजें।

विशेष रूप से, एक शब्द आमतौर पर संकुचित पाठ है, जो मूल पाठ में उस शब्द के लिए खोज की तुलना में तेजी है में 16-बिट सूचकांक की तुलना करने के लिए कम कर देता है के लिए खोज है, क्योंकि

• प्रत्येक तुलना कम बाइट की तुलना की आवश्यकता है - 2, बजाय हालांकि कई बाइट्स है कि शब्द में थे, और
• हमारे पास कम से तुलना कर रहे हैं, क्योंकि संपीड़ित फ़ाइल कम है।

कुछ प्रकार के नियमित अभिव्यक्तियों का अनुवाद एक और नियमित अभिव्यक्ति में किया जा सकता है जो सीधे संपीड़ित फ़ाइल में आइटम पाता है (और शायद कुछ झूठी सकारात्मक भी पाता है)। इस तरह की एक खोज भी, मूल पाठ फ़ाइल पर मूल रेगुलर एक्सप्रेशन के उपयोग की तुलना में कम तुलना करता है क्योंकि संपीड़ित फ़ाइल कम है, लेकिन आम तौर पर प्रत्येक नियमित अभिव्यक्ति तुलना में अधिक काम की आवश्यकता है, तो यह या मूल regex ऑपरेटिंग तुलना में तेजी से नहीं हो सकता मूल पाठ पर।

(सिद्धांत रूप में आप चर लंबाई Huffman उपसर्ग कोड के साथ फिक्स्ड लंबाई 16-बिट कोड की जगह सकता है, का उल्लेख किया rwong के रूप में - परिणामी संपीड़ित फ़ाइल छोटा हो जाएगा, लेकिन सॉफ्टवेयर निपटने के लिए उन फ़ाइलों के साथ एक होगा थोड़ा धीमा और अधिक जटिल)।

और अधिक परिष्कृत तकनीक के लिए, आप

• MG4J पर दिख सकता है: इयान एच Witten, एलिस्टेयर Moffat, और टिमोथी सी बेल

Answer 5

यह संभव है द्वारा Managing Gigabytes for Java

"Managing Gigabytes: Compressing and Indexing Documents and Images", और काफी कुशलता से किया जा सकता है। इस विषय पर बहुत से रोमांचक शोध हैं, अधिक औपचारिक रूप से एक संक्षिप्त डेटा संरचना के रूप में जाना जाता है। कुछ विषयों में मैं अनुशंसा करता हूं: वेवलेट पेड़, एफएम-इंडेक्स/आरआरआर, संक्षिप्त प्रत्यय सरणी। आप कई प्रकार के प्रकाशनों के प्रदर्शन के रूप में कुशलता से हफमैन एन्कोडेड तारों को भी खोज सकते हैं।