पैटर्न के एक बड़े सेट के खिलाफ पेड़ से कैसे मिलान करें?

Question

मेरे पास प्रतीकों का एक संभावित अनंत सेट है: A, B, C, ... एक विशिष्ट विशेष प्लेसहोल्डर प्रतीक ? भी है (इसका अर्थ नीचे समझाया जाएगा)।

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

अंतिमता आवश्यकता का मतलब है कि पेड़ में नोड्स की कुल संख्या सकारात्मक परिमित पूर्णांक है। यह इस प्रकार है कि संलग्न उपनिवेशों की कुल संख्या, वृक्ष गहराई और प्रत्येक उप-पेड़ में नोड्स की कुल संख्या सभी सीमित हैं।

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

    A 
       /\ 
        ? B 
        /\ 
        A C 
        /|\ 
        A C Q 
         \ 
         ? 

A(?,B(A(A,C,Q(?)),C)) के रूप में प्रतिनिधित्व किया है।

मेरे पास पेड़ के पूर्व-गणना अपरिवर्तनीय सेट एस है जो मिलान के लिए पैटर्न के रूप में उपयोग किया जाएगा। सेट में आमतौर पर ~ 10 पेड़ होंगे, और इसके प्रत्येक तत्व में आमतौर पर ~ 10-30 नोड होंगे। मैं पहले से ही एस का कोई भी प्रतिनिधित्व बनाने के लिए बहुत समय का उपयोग कर सकता हूं जो नीचे बताई गई मेरी समस्या के अनुरूप सबसे अच्छा होगा।

मैं, कि प्रदान की एक समारोह है कि एक पेड़ टी (आमतौर पर के साथ ~ 10 नोड्स) और चेक जितनी जल्दी संभव स्वीकार करता है लिखने के लिए अगर टी एक सबट्री के रूप में एस के किसी भी तत्व शामिल हैं की जरूरत है प्लेसहोल्डर प्रतीक ? के साथ किसी भी नोड किसी भी गैर खाली सबट्री से मेल खाता है (दोनों यह टी में या का एक तत्व एस में प्रकट होते हैं)।

कृपया सेट एस और एक मैच की जांच करने के लिए एल्गोरिदम स्टोर करने के लिए डेटा संरचना का सुझाव दें। कोई भी प्रोग्रामिंग भाषा या छद्म कोड ठीक है।

Answer 1

This paperAho–Corasick algorithm का एक प्रकार का वर्णन करता है, जहां के बजाय एक परिमित राज्य मशीन (जो मानक Aho-Corasick एल्गोरिथ्म स्ट्रिंग मिलान के लिए उपयोग करता है) एल्गोरिथ्म के बजाय सबट्री मिलान के लिए एक पुशडाउन आटोमैटिक मशीन का उपयोग करता है का उपयोग करने का। अहो-कोरासिक स्ट्रिंग-मिलान एल्गोरिदम की तरह, उनके संस्करण को केवल एस के पूरे शब्दकोश के विरुद्ध मिलान करने के लिए इनपुट पेड़ के माध्यम से एक पास की आवश्यकता होती है।

पेपर काफी जटिल है - यह contact the author के लायक हो सकता है यह देखने के लिए कि उसके पास कोई स्रोत कोड उपलब्ध है या नहीं।

Answer 2

आपको जो चाहिए वह एक सीमित राज्य मशीन है जो संभावित मैचों के सेट को ट्रैक करती है।

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

आप term rewriting systems के तहत ऐसा करने के तरीकों के संदर्भ ढूंढ सकते हैं।