स्ट्रिंग खोजों को करने के लिए एक तेज़ तरीका ढूंढ रहे हैं

Question

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

चेक करने के लिए उप-तारों की सूची लगभग 10k ऐसे उप-स्ट्रिंग्स है। मैंने जो किया वह बस उप-स्ट्रिंग फ़ाइल में लाइन से लाइन पर गया था और मैच की तलाश में था और यदि पाया गया कि यूआरएल श्रेणी ए से संबंधित है तो मुझे परीक्षणों में पाया गया कि यह समय लेने वाला था।

मैं कंप्यूटर विज्ञान छात्र नहीं हूं इसलिए एल्गोरिदम अनुकूलित करने के बारे में ज्यादा जानकारी नहीं है। लेकिन क्या यह तेजी से बनाने का कोई तरीका है? बस साधारण विचार। प्रोग्रामिंग भाषा एक बड़ा मुद्दा नहीं है लेकिन जावा या पर्ल बेहतर होगा।

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

Answer 1

हाँ, मैं Aho-Corasick algorithm एल्गोरिथ्म जावा में समस्या आप सुझाव दे रहे हैं के लिए लागू किया है और यह एक सुसंगत अनुभवहीन कार्यान्वयन पर के बारे में x180 के सुधार (तुम क्या कर रहे) से पता चला। ऑनलाइन कई कार्यान्वयन उपलब्ध हैं, हालांकि मैं उन्हें बेहतर प्रदर्शन के लिए ट्विक कर दूंगा। ध्यान दें कि समाधान जटिलता शब्द की लंबाई (आपके मामले में यूआरएल) से जुड़ी है और उप-तारों की संख्या नहीं है। इसके अलावा इसे केवल मिलान के लिए औसत पर एक पास की आवश्यकता होती है।

पी.एस - हम काम साक्षात्कार में लोगों से यह सवाल देने के लिए किया है, इसलिए इसे हल करने के कई तरीके हैं। मैं जो पेशकश करता हूं वह वह है जिसे हम उत्पादन कोड में उपयोग करते हैं, जो (अभी के लिए) अन्य सभी समाधानों को धड़कता है।

संपादित करें: गलत एल्गोरिथ्म नाम पहले से तय हो गई ...

Answer 2

आप उसी उपसर्ग को साझा करने वाले वर्गों में सबस्ट्रिंग को संपीड़ित कर सकते हैं। यह एक महत्वपूर्ण मार्जिन द्वारा समय काटना चाहिए।

आप प्रत्येक यात्रा 1 से स्ट्रिंग स्थानांतरण मैचों के लिए देख रहे हैं, तो आप अपनी गति काफ़ी (नियमित अभिव्यक्ति के साथ के रूप में) एक बेहतर एल्गोरिथ्म का उपयोग कर सुधार कर सकते हैं।

Answer 3

मैं सम्मानित Grep का उपयोग कर के बजाय इस कार्य के लिए एक प्रोग्रामिंग भाषा के उपयोग का सुझाव चाहते हैं। यह तेजी से Boyer-Moore string searching algorithm का उपयोग करता है, जो कुछ मिलियन लाइनों के लिए पर्याप्त होना चाहिए।

Answer 4

इसे अनुकूलित करने के लिए विभिन्न दृष्टिकोण निश्चित रूप से संभव हैं। आपकी पृष्ठभूमि के बारे में, मैं आपको एक सरल स्केच करूंगा। जो मानते हैं कि उप-तारों की सूची अक्सर बदलती नहीं है।

1. सभी उप-तारों से एक विशाल नियमित अभिव्यक्ति उत्पन्न करें।
2. उस regexp संकलित करें, देखें। उदाहरण के लिए जावा में कक्षा पैटर्न। उस संकलित नियमित अभिव्यक्ति को प्रतिबिंबित करें।
3. प्रत्येक यूआरएल से मेल खाने के लिए एक ही संकलित नियमित अभिव्यक्ति का उपयोग करें।

Answer 5

पर्ल (एक नियमित अभिव्यक्ति में वैकल्पिक तार की लंबी सूची के अनुकूलन के लिए एक निश्चित समग्र संकलित regex लंबाई, जहां यह में बदल जाती अप करने के लिए पर बहुत अच्छा है लिखा था एक कम कुशल तंत्र)। आप की तरह एक निश्चित श्रेणी मैच के लिए एक regex के निर्माण के लिए सक्षम होना चाहिए:

$catAre = join('|', map quotemeta, @catAstrings); 
$catAre = qr/$catAre/; 

Answer 6

जावा लाइब्रेरीज कि लागू आम स्ट्रिंग खोज एल्गोरिदम https://stackoverflow.com/questions/5564610/fast-alernative-for-stringindexofstring-str के जवाब देखें। समांतरता के साथ मिलकर आप लाखों यूआरएल को काफी जल्दी पार्स करने में सक्षम होना चाहिए। ऐसा करने में काफी आसान है; आपको शायद इसे आज़माएं और देखें कि अनुकूलन में बहुत अधिक देखने से पहले समय स्वीकार्य है या नहीं।

Answer 7

मैं इसे टिप्पणी के रूप में पहली लिखा था, लेकिन उसके बाद मैंने महसूस किया, मुझे लगता है कि यह एक जवाब
आप (जावा में तरह Apache Lucene) कुछ सूचना पुनर्प्राप्ति प्रणाली का उपयोग करें और अनुक्रमणिका से दस्तावेजों के रूप में उपयोग कर सकते हैं यूआरएल के रूप में अधिक उपयुक्त है।
फिर, अनुक्रमण के बाद - आप प्रश्नों पर पुन: प्रयास कर सकते हैं, और उनमें से प्रत्येक के लिए खोज कर सकते हैं, परिणाम मेल खाने वाले यूआरएल होंगे।
PROS:
* खोज को प्रत्येक क्वेरी के लिए सभी यूआरएल पर पुनरावृत्ति की आवश्यकता नहीं होगी। -
* यदि आप बाद में चौराहे या सबस्ट्रिंग/प्रश्नों के मिलन की आवश्यकता होगी, तो पुस्तकालय आप इस कार्यक्षमता
कान्स देता है:
* अनुक्रमण कुछ समय लग जाएगा ...
* यदि आप रैम पर कुछ अतिरिक्त जगह की आवश्यकता हो सकती/सूचकांक के लिए डिस्क।

मुझे लगता है कि यह खोज करने के लायक है, शायद समय के साथ खोज के लाभ के अनुक्रमण के दौरान उपभोग किया गया समय।

Answer 8

मैंने पर्ल में पहले इस तरह की चीज की है, ट्विटर से डेटा की आने वाली स्ट्रीम के खिलाफ ~ 13k कीवर्ड की एक सूची की तुलना करने के लिए उन सभी कीवर्ड से मिलान करने वाली सभी ट्वीट्स (और प्रत्येक कीवर्ड कौन से कीवर्ड) से मेल खाता है। किसी न किसी मामले में, कोड लगता है:

use Regexp::Assemble; 
my $ra = Regexp::Assemble->new; 
$ra->add(@keywords); 
my $regex = $ra->re; 

for my $tweet (@tweets) { 
    my @matches = $tweet =~ /$regex/g; 
    # do whatever with @matches... 
} 

ध्यान दें कि यह Regexp::Assemble का उपयोग करता है, regex, जो कोर पर्ल वितरण का हिस्सा नहीं है निर्माण करने के लिए तो आप स्थापित करने के लिए करता है, तो CPAN से यदि आप चाहते हैं की आवश्यकता होगी इस कोड को अनुकूलित करें।

यदि आप perl 5.10 या बाद में उपयोग कर रहे हैं, तो "स्मार्ट मैच" ऑपरेटर (~~) भी है जो बिना किसी अतिरिक्त मॉड्यूल की आवश्यकता के कुछ ऐसा कर सकता है।

Answer 9

मैं वर्तमान में इस समस्या पर काम कर रहा हूं। मैं इस निष्कर्ष पर आया:

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

अधिक तकनीकी भाषा के बारे में क्षमा करें। लेकिन मुझे लगता है कि यदि आप यूआरएल की सूची से एक विशिष्ट यूआरएल खोज रहे हैं तो एचएटी ट्राई बेहतर विकल्प है। (मैंने एक एचएटी ट्राई बनाई है जो यूआरएल के 6 लाख स्टोर करने के लिए 12 एमबी का उपभोग करेगी।)