कुशल द्रव्यमान खोज समस्या

Question

समस्या: तारों की एक बड़ी स्थिर सूची प्रदान की जाती है। एक पैटर्न स्ट्रिंग जिसमें डेटा और वाइल्डकार्ड तत्व शामिल हैं (* और?)। विचार पैटर्न से मेल खाने वाले सभी तारों को वापस करना है - काफी सरल।

वर्तमान समाधान: मैं वर्तमान में बड़ी सूची स्कैन करने और पैटर्न के खिलाफ प्रत्येक प्रविष्टि को ग्लोबिंग करने के रैखिक दृष्टिकोण का उपयोग कर रहा हूं।

मेरा प्रश्न: क्या कोई उपयुक्त डेटा संरचनाएं हैं जो मैं बड़ी सूची को स्टोर कर सकता हूं ताकि खोज की जटिलता ओ (एन) से कम हो?

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

Answer 1

आप स्मृति के बारे में परवाह नहीं करते हैं और आप के लिए, पूर्व प्रक्रिया सूची में खर्च कर सकते हैं, हर प्रत्यय के एक क्रमबद्ध सारिणी निर्मित मूल शब्द की ओर इशारा करते, जैसे, [ 'हैलो', 'दुनिया'], इस स्टोर:

[('d' , 'world'), 
('ello' , 'hello'), 
('hello', 'hello'), 
('ld' , 'world'), 
('llo' , 'hello'), 
('lo' , 'hello'), 
('o' , 'hello'), 
('orld' , 'world'), 
('rld' , 'world'), 
('world', 'world')] 

इस सरणी का उपयोग पैटर्न के टुकड़े का उपयोग कर मैच उम्मीदवार के सेट बनाने के लिए।

उदाहरण के लिए, अगर पैटर्न *or* है, उम्मीदवार मैच ('orld' , 'world') सबस्ट्रिंग or पर एक द्विआधारी काट का उपयोग कर पाते हैं, तो एक सामान्य ग्लोबिंग दृष्टिकोण का उपयोग कर मैच की पुष्टि करें।

और अधिक जटिल है, जैसे, h*o, उम्मीदवारों के सेट h और o के लिए बनाया गया है और अंतिम रैखिक ग्लोब से पहले उनके चौराहे मिल जाए वाइल्डकार्ड है।

Answer 2

आप नियमित ट्राई बना सकते हैं और वाइल्डकार्ड किनारों को जोड़ सकते हैं। तो आपकी जटिलता ओ (एन) होगी जहां एन पैटर्न की लंबाई है। आपको पहले पैटर्न में के * के साथ रनों को प्रतिस्थापित करना होगा (एक ओ (एन) ऑपरेशन भी)।

तो शब्दों की सूची थे मैं एक बैल तो trie इस तरह एक सा लगेगा हूँ:

 
    (I ($ [I]) 
    a (m ($ [am]) 
     n ($ [an]) 
     ? ($ [am an]) 
     * ($ [am an])) 
    o (x ($ [ox]) 
     ? ($ [ox]) 
     * ($ [ox])) 
    ? ($ [I] 
     m ($ [am]) 
     n ($ [an]) 
     x ($ [ox]) 
     ? ($ [am an ox]) 
     * ($ [I am an ox] 
     m ($ [am]) ...) 
    * ($ [I am an ox] 
     I ... 
    ... 

और यहाँ एक नमूना अजगर कार्यक्रम है:

 
import sys 

def addWord(root, word): 
    add(root, word, word, '') 

def add(root, word, tail, prev): 
    if tail == '': 
     addLeaf(root, word) 
    else: 
     head = tail[0] 
     tail2 = tail[1:] 
     add(addEdge(root, head), word, tail2, head) 
     add(addEdge(root, '?'), word, tail2, head) 
    if prev != '*': 
     for l in range(len(tail)+1): 
      add(addEdge(root, '*'), word, tail[l:], '*') 

def addEdge(root, char): 
    if not root.has_key(char): 
     root[char] = {} 
    return root[char] 

def addLeaf(root, word): 
    if not root.has_key('$'): 
     root['$'] = [] 
    leaf = root['$'] 
    if word not in leaf: 
     leaf.append(word) 

def findWord(root, pattern): 
    prev = '' 
    for p in pattern: 
     if p == '*' and prev == '*': 
      continue 
     prev = p 
     if not root.has_key(p): 
      return [] 
     root = root[p] 
    if not root.has_key('$'): 
     return [] 
    return root['$'] 

def run(): 
    print("Enter words, one per line terminate with a . on a line") 
    root = {} 
    while 1: 
     line = sys.stdin.readline()[:-1] 
     if line == '.': break 
     addWord(root, line) 
    print(repr(root)) 
    print("Now enter search patterns. Do not use multiple sequential '*'s") 
    while 1: 
     line = sys.stdin.readline()[:-1] 
     if line == '.': break 
     print(findWord(root, line)) 

run() 

Answer 3

मैं सहमत हूं कि एक प्रत्यय trie कोशिश करने का एक अच्छा विचार है, सिवाय इसके कि आपके डेटासेट के आकार का आकार इसे निर्माण का उपयोग कर सकता है जितना समय इसके उपयोग को बचाएगा। अगर आपको निर्माण लागत को कम करने के लिए उन्हें कई बार पूछताछ की जाती है तो वे सबसे अच्छे होते हैं। शायद कुछ सौ प्रश्न।

यह भी ध्यान दें कि समानांतरता के लिए यह एक अच्छा बहाना है। सूची में दो कटौती करें और इसे दो अलग प्रोसेसर को दें और अपनी नौकरी तेजी से दो बार करें।

Answer 4

आप कहते हैं कि आप वर्तमान में रैखिक खोज कर रहे हैं। क्या यह आपको अक्सर बार-बार किए गए क्वेरी पैटर्न पर कोई डेटा देता है? जैसे blah*bl?h से अधिक आम है (जो मुझे लगता है कि यह था) आपके वर्तमान उपयोगकर्ताओं के बीच?

इस तरह के पूर्व ज्ञान के साथ आप सामान्य रूप से उपयोग किए गए मामलों पर अपने अनुक्रमण प्रयासों पर ध्यान केंद्रित कर सकते हैं और उन्हें अधिक कठिन, और अभी तक कम कम करने की कोशिश करने की बजाय, कम (कम) की समस्या को हल करने की बजाय प्रत्येक संभव क्वेरी समान रूप से तेज़ी से।

Answer 5

आप अपने तारों में वर्णों की संख्या को रखकर एक सरल गति प्राप्त कर सकते हैं। कोई स्ट्रिंग नहीं b एस या एक b क्वेरी abba* से मेल नहीं खा सकता है, इसलिए इसका परीक्षण करने में कोई बात नहीं है। यह पूरे शब्दों पर बहुत बेहतर काम करता है, यदि आपके तार उन लोगों से बने हैं, क्योंकि पात्रों की तुलना में कई और शब्द हैं; इसके अलावा, बहुत सारे पुस्तकालय हैं जो आपके लिए इंडेक्स बना सकते हैं। दूसरी ओर, यह आपके द्वारा उल्लिखित एन-ग्राम दृष्टिकोण के समान ही है।

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

सामान्यतः, सभी स्पीडअप उन चीजों को त्यागने के विचार पर आधारित होंगे जो संभवतः मेल नहीं खा सकते हैं। सूचकांक के लिए और कितना आपके डेटा पर निर्भर करता है। उदाहरण के लिए, यदि सामान्य पैटर्न लंबाई स्ट्रिंग लम्बाई के करीब है, तो आप यह देखने के लिए जांच सकते हैं कि स्ट्रिंग पैटर्न को पकड़ने के लिए पर्याप्त है या नहीं।

Answer 6

बहु-स्ट्रिंग खोज के लिए बहुत अच्छे एल्गोरिदम हैं। Google "नेवरो स्ट्रिंग सर्च" और आप बहु-स्ट्रिंग विकल्पों का एक अच्छा विश्लेषण देखेंगे। कई एल्गोरिदम "सामान्य" मामलों के लिए बेहद अच्छे हैं (खोज तार जो काफी लंबे होते हैं: वू-मैनबर; उन पात्रों के साथ खोज तार जो पाठ में मामूली दुर्लभ हैं: समांतर हॉर्सपूल)। अहो-कोरासिक एक एल्गोरिदम है जो प्रति इनपुट चरित्र के काम (एक छोटे) बाध्य राशि की गारंटी देता है, इससे कोई फर्क नहीं पड़ता कि खोज में सबसे खराब व्यवहार करने के लिए इनपुट टेक्स्ट कैसे ट्यून किया गया है। Snort जैसे कार्यक्रमों के लिए, यह वास्तव में महत्वपूर्ण है, इनकार सेवा के हमलों के सामने। यदि आप रुचि रखते हैं कि वास्तव में कितनी कुशल अहो-कोरासिक खोज लागू की जा सकती है, तो ACISM - an Aho-Corasick Interleaved State Matrix पर एक नज़र डालें।