👇🏾 🌊 👦🏿 त्वरित फ़ाइल खोज 🤼 🌨️ 📐

एक अनुवादक से: मैं आपके ध्यान में 15 जनवरी, 1983 को प्रकाशित एक बहुत पुराने लेख का अनुवाद लाता हूं। इतनी प्रभावशाली उम्र के बावजूद, लेख मुझे दिलचस्प लगा, और यह संभव है कि यह आज किसी के लिए उपयोगी होगा। यह लेख, वैसे, आदमी को संदर्भित किया गया है (1) opennet.ru पर सहायता अनुभाग देखें: https://www.opennet.ru/man.shtml?topic=locate ।

सारांश

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

फ़ाइल पथ डेटाबेस एक गुप्त रूप से एन्कोडेड है, लेक्सिकोग्राफ़िक रूप से सॉर्ट की गई सूची (जिसे कभी-कभी "फ्रंट कंप्रेस" फ़ाइल कहा जाता है), जो प्रभावी संपीड़न प्राप्त करने के लिए नियमित रूप से बिग्रामिक एन्कोडिंग के अधीन भी होती है। सामान्य ASCII प्रतिनिधित्व की तुलना में संपीड़न अनुपात 5 से 6 है। सूची को संशोधित रैखिक खोज का उपयोग करके स्कैन किया गया है, विशेष रूप से वृद्धिशील कोडिंग के लिए अनुकूलित है, जबकि एल्गोरिथ्म द्वारा बिताया गया विशिष्ट समय एक नियमित खोज से 40-50% कम है।

परिचय

कंप्यूटर सिस्टम, या कंप्यूटर नेटवर्क में फाइलें ढूंढना एक जटिल प्रक्रिया है। UNIX उपयोगकर्ता इसे विभिन्न प्रकार से कार्यान्वित कर सकते हैं, cd, ls और grep कमांडों में हेरफेर करने से लेकर विशेष कमांड तक, जैसे कि बर्कले व्हाईस और फ्लीस द्वारा विकसित किए गए, और अधिक आम यूनिक्स कमांड पाते हैं।

दुर्भाग्य से, पलायन (बर्कले से) घर निर्देशिका तक सीमित है, और जहां केवल मानक स्थानों में स्थित सिस्टम कोड और प्रलेखन की खोज कर सकते हैं।

खोज:

find / -name "*<filename>*" -print

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

प्रारंभिक गणना

सिस्टम में सभी फाइलों की स्थैतिक सूची क्यों न बनाएं और उस पर grep की तलाश करें? 20,000 फ़ाइलों वाली एक विशिष्ट प्रणाली में फ़ाइल नामों के 1,000 ब्लॉक शामिल होंगे, भले ही आप / यूआर को छोटा / यू करें। हमारे अनलोड किए गए पीडीपी -11 / 70 सिस्टम पर जीआरपी प्रति सेकंड 30-40 ब्लॉक की प्रक्रिया करता है, और स्कैन करने के लिए आधा मिनट की आवश्यकता होगी। यह आमतौर पर इस्तेमाल की जाने वाली कमांड के लिए स्वीकार्य नहीं है।

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

दबाव

अनुप्रयोगों के लिए उपयोग में तेजी लाने के लिए, आप बाइनरी सर्च या हैश टेबल का उपयोग करने का सुझाव दे सकते हैं, लेकिन ऐसी योजनाएं आंशिक तुलना के लिए अच्छी तरह से काम नहीं करती हैं, अगर हम केवल नाम के एक हिस्से में रुचि रखते हैं। क्रमबद्ध डेटा कंप्रेशन तकनीक, जिसे वृद्धिशील कोडिंग के रूप में जाना जाता है, जो एक समान शब्दकोश संपीड़न कार्य के लिए उपयोग किया जाता था, आसानी से लागू किया जाता है [मॉरिस / थॉम्पसन, 1974]। इस मामले में, पिछले नाम के सबसे लंबे उपसर्ग की गणना की जाती है। उदाहरण के लिए:

/usr/src
/usr/src/cmd/aardvark.c
/usr/src/cmd/armadillo.c
/usr/tmp/zoo

इसमें बदला गया

0/usr/src
8/cmd/aardvark.c
14armadillo.c
5tmp/zoo

डिकोडिंग सरल होगी (चर घोषणाएं छोड़ दी गई हैं)

fp = fopen(COMPRESSED_FILELIST, "r");
while((count = (getc(fp) & 0177)) != EOF) {
    for(p = path + count; (*p++ = getc(fp)) < 0200; )
        ; /*overlay old path with new*/
    ungetc(*--p, fp);
    *p-- = NULL;
    if(math(path, name) == YES)
        puts(path);
}

जहां गणित एक फ़ंक्शन है जो यह निर्धारित करता है कि क्या नाम स्ट्रिंग का नाम पथ स्ट्रिंग में निहित है ।

वास्तव में, चूंकि एन्कोडेड सूची अनकोडेड की तुलना में लगभग पांच गुना कम है, और डिकोडिंग बहुत सरल है, प्रोग्राम पाठ फ़ाइल पर grep की तुलना में तीन से चार गुना तेजी से चलता है ।

और भी तेज

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

find name

ध्यान दें कि ऊपर दिया गया कोड अभी भी अनपैक की गई सूची को खोजता है, यद्यपि स्मृति में, डिस्क पर नहीं। विपरीत दिशा में एक विकल्प के साथ एक स्ट्रिंग की तुलना करके इसे टाला जा सकता है। स्ट्रिंग नाम के अंतिम वर्ण को नाम दें और गणित को इसके साथ बदलें :

for(s = p, cutoff = path + count; s > cutoff; s--) {
    if(*s == namend) { /*quick first char check*/
        for(p = namend - 1, q = s - 1; *p != NULL; p--, q--)
            if(*q != *p)
                break;
        if(*p == NULL) {
            puts(path);
            break;
        }
    }
}

यह तीन मामलों को देखकर समझना आसान है। यदि प्रतिस्थापन पूरी तरह से कटऑफ के दाईं ओर है , तो तुलना सफलतापूर्वक समाप्त हो जाएगी। यदि वे ओवरलैप करते हैं, तो कटऑफ "नरम" हो जाता है और तुलना जारी रहती है। यदि सबस्ट्रिंग कटऑफ़ के बाईं ओर पूरी तरह से झूठ है , तो पिछली पंक्तियों के लिए एक मैच सामने आएगा, जिसका अर्थ है कि हम इस खोज को नहीं कर सकते हैं! तकनीकी रूप से, कटऑफ को तुलना करने के तुरंत बाद पथ पर ले जाया जा सकता है। इस शर्त को ऊपर छोड़ दिया गया है।

दो-स्तरीय उपकरण

आप खोज पैटर्न वर्णों के प्रसंस्करण के कारण खोज को धीमा करने से बच सकते हैं । ऐसा करने में, हम ऐसा नाम है जो अक्षरों से परे शामिल नहीं है और धीमी पुनरावर्ती क्रिया का उपयोग के भाग पर कार्रवाई amath अंदर खोज । अर्थात,

puts(path)

हो जाता है

if(globchars == NO | amatch(path, name))
    puts(path);

जहां globchars है निर्धारित करते हैं नाम अक्षरों से परे होता है। एक साधारण आदमी कमांड के लिए खोज पैटर्न का उपयोग करने का एक उदाहरण :

vtroff -man 'find '*man*'"$1"'.[1-9]

और सुधार

खोज उपयोगिता का उत्पादन कोड गैर-मुद्रण योग्य ASCII कोड के साथ सबसे आम दो-वर्ण संयोजनों को बदलकर संपीड़न अनुपात को 20-25% बढ़ा देता है। ".c" और ".P" विशेष रूप से आम हैं।

अन्य एल्गोरिदम जो समय और डेटा के आकार के बीच अन्य ट्रेड-ऑफ्स को लागू करते हैं, जैसे कि हफमैन एल्गोरिथ्म [रेगबती, 1981], आशाजनक नहीं दिखते हैं: वे सिर्फ प्रदर्शन सीमा के साथ I / O प्रदर्शन सीमा को बदलते हैं।

बॉयर-मूर उप-रेखीय खोज विधियों [बॉयर, 1977] या मैक्रो-मॉडल विधियों [स्टॉपर / सिजमेंस्की, 1982] का उपयोग किया जा सकता है।

निष्कर्ष में, यह ध्यान दिया जाना चाहिए कि हमने 180 सेकंड और दो पृष्ठों पर फिट होने वाले C कोड का उपयोग करके कुछ सेकंड में 19,000 फ़ाइल नामों को स्कैन किया।

संदर्भ

बोयर, आरएस ए फास्ट स्ट्रिंग सर्चिंग एलगोरिदम, कम्युनिटी। एसीएम, वॉल्यूम। 20, नंबर 10, अक्टूबर 1977.
मॉरिस, आर। और थॉम्पसन, के। वेबर का दूसरा एक पिन के प्रमुख पर, अप्रकाशित तकनीकी मेमो, बेल प्रयोगशालाओं, मरे हिल, एनवाई, 1974।
रेग्बाती, एचके एक डेटा संपीड़न Techinques का अवलोकन, कंप्यूटर, वॉल्यूम। 14, नहीं। 4, अप्रैल 1981.
Storer, JA और Szymanski, टीजी डेटा संपीड़न के माध्यम से Textual प्रतिस्थापन, जे ACM, वॉल्यूम। 29, नहीं। 4, अक्टूबर 1982।

त्वरित फ़ाइल खोज