अहो-कोरासिक एल्गोरिदम

यह एल्गोरिदम दिए गए कीवर्ड्स के सेट की सभी घटनाओं को ढूंढने में सहायक है। यह एक प्रकार का डिक्शनरी-मैचिंग एल्गोरिदम है। यह सभी कीवर्ड्स का उपयोग करके एक ट्री स्ट्रक्चर बनाता है। ट्री बनाने के बाद, यह खोज को रैखिक समय में बनाने के लिए ट्री को ऑटोमेटन में बदलने का प्रयास करता है। अहो-कोरासिक एल्गोरिदम के तीन अलग-अलग चरण हैं।

ये हैं Go-to, Failure, और Output। गो-टू चरण में, यह सभी कीवर्ड्स का उपयोग करके ट्री बनाता है। अगले चरण या फेल्योर चरण में, यह कुछ कीवर्ड्स के उचित सफिक्स को प्राप्त करने के लिए बैकवर्ड ट्रांजिशन ढूंढने का प्रयास करता है। आउटपुट चरण में, ऑटोमेटन के हर स्टेट 's' के लिए, यह उन सभी शब्दों को ढूंढता है जो स्टेट 's' पर समाप्त हो रहे हैं।

इस एल्गोरिदम की टाइम कॉम्प्लेक्सिटी है: O(N + L + Z), जहां N टेक्स्ट की लंबाई है, L कीवर्ड्स की लंबाई है और Z मैच की संख्या है।

इनपुट और आउटपुट

इनपुट: पैटर्न्स का एक सेट: {their, there, answer, any, bye}
मेन स्ट्रिंग: "isthereanyanswerokgoodbye"
आउटपुट: Word there location: 2
Word any location: 7
Word answer location: 10
Word bye location: 22

एल्गोरिदम

buildTree(patternList, size)

इनपुट: सभी पैटर्न्स की लिस्ट, और लिस्ट का साइज

आउटपुट: पैटर्न्स ढूंढने के लिए ट्रांजिशन मैप उत्पन्न करें

Begin
    output ऐरे के सभी एलिमेंट्स को 0 पर सेट करें
    fail ऐरे के सभी एलिमेंट्स को -1 पर सेट करें
    goto मैट्रिक्स के सभी एलिमेंट्स को -1 पर सेट करें
    state := 1 // प्रारंभ में केवल एक स्टेट है।
    for all patterns 'i' in the patternList, do
        word := patternList[i]
        present := 0
        for all character 'ch' of word, do
            if goto[present, ch] = -1 then
                goto[present, ch] := state
                state := state + 1
            present := goto[present, ch]
        done
        output[present] := output[present] OR (i बार 1 को लेफ्ट शिफ्ट करें)
    done
    for all type of characters ch, do
        if goto[0, ch] ≠ 0 then
            fail[goto[0,ch]] := 0
            goto[0, ch] को एक क्यू q में इन्सर्ट करें।
        done
    while q is not empty, do
        newState := q का पहला एलिमेंट
        q से डिलीट करें।
        for all possible character ch, do
            if goto[newState, ch] ≠ -1 then
                failure := fail[newState]
                while goto[failure, ch] = -1, do
                    failure := goto[failure, ch]
                done
                fail[goto[newState, ch]] = failure
                output[goto[newState, ch]] := output[goto[newState,ch]] OR output[failure]
                goto[newState, ch] को q में इन्सर्ट करें।
            done
        done
    done
    return state
End

getNextState(presentState, nextChar)

इनपुट: वर्तमान स्टेट और अगला कैरेक्टर अगला स्टेट निर्धारित करने के लिए

आउटपुट: अगला स्टेट

Begin
    answer := presentState
    ch := nextChar
    while goto[answer, ch] = -1, do
        answer := fail[answer]
    done
    return goto[answer, ch]
End

patternSearch(patternList, size, text)

इनपुट: पैटर्न्स की लिस्ट, लिस्ट का साइज और मेन टेक्स्ट

आउटपुट: टेक्स्ट के वे इंडेक्स जहां पैटर्न्स मिले

Begin
    call buildTree(patternList, size)
    presentState := 0
    for all indexes of the text, do
        if output[presentState] = 0
            अगले भाग को इग्नोर करें और अगले इटरेशन के लिए जाएं
        for all patterns in the patternList, do
            if आउटपुट ऐरे का उपयोग करके पैटर्न मिला, then
                वह लोकेशन प्रिंट करें जहां पैटर्न मौजूद है
            done
        done
    done
End

उदाहरण

#include <iostream>
#include <queue>
#define MAXS 500 // सभी पैटर्न्स की लंबाई का योग
#define MAXC 26 // वर्णमाला में 26 अक्षर
using namespace std;

int output[MAXS];
int fail[MAXS];
int gotoMat[MAXS][MAXC];

int buildTree(string array[], int size) {
    for(int i = 0; i < MAXS; i++)
        output[i] = 0; // आउटपुट के सभी एलिमेंट 0 हैं
    for(int i = 0; i < MAXS; i++)
        fail[i] = -1; // फेल्योर ऐरे के सभी एलिमेंट -1 हैं
    for(int i = 0; i < MAXS; i++)
        for(int j = 0; j < MAXC; j++)
            gotoMat[i][j] = -1; // goto मैट्रिक्स के सभी एलिमेंट -1 हैं
    int state = 1; // केवल एक स्टेट है
    for (int i = 0; i < size; i++) {
        // array में सभी पैटर्न के लिए ट्राई स्ट्रक्चर बनाएं
        string word = array[i];
        int presentState = 0;
        for (int j = 0; j < word.size(); ++j) { // सभी पैटर्न जोड़े जाते हैं
            int ch = word[j] - 'a'; // 'a' का ASCII घटाएं
            if (gotoMat[presentState][ch] == -1) // यदि ch मौजूद नहीं है तो नया नोड बनाएं
                gotoMat[presentState][ch] = state++; // स्टेट बढ़ाएं
            presentState = gotoMat[presentState][ch];
        }
        output[presentState] |= (1 << i); // वर्तमान शब्द आउटपुट में जोड़ा गया
    }
    for (int ch = 0; ch < MAXC; ++ch) // यदि ch सीधे रूट से जुड़ा नहीं है
        if (gotoMat[0][ch] == -1)
            gotoMat[0][ch] = 0;
    queue<int> q;
    for (int ch = 0; ch < MAXC; ++ch) {
        // नोड फेल होने पर पिछले स्टेट पर जाता है
        if (gotoMat[0][ch] != 0) {
            fail[gotoMat[0][ch]] = 0;
            q.push(gotoMat[0][ch]);
        }
    }
    while (q.size()) {
        int state = q.front(); // फ्रंट नोड हटाएं
        q.pop();
        for (int ch = 0; ch <= MAXC; ++ch) {
            if (gotoMat[state][ch] != -1) { // यदि goto स्टेट मौजूद है
                int failure = fail[state];
                while (gotoMat[failure][ch] == -1) // उचित सफिक्स के साथ सबसे गहरा नोड ढूंढें
                    failure = fail[failure];
                failure = gotoMat[failure][ch];
                fail[gotoMat[state][ch]] = failure;
                output[gotoMat[state][ch]] |= output[failure]; // आउटपुट वैल्यू मर्ज करें
                q.push(gotoMat[state][ch]); // अगले लेवल नोड को क्यू में जोड़ें
            }
        }
    }
    return state;
}

int getNextState(int presentState, char nextChar) {
    int answer = presentState;
    int ch = nextChar - 'a'; // 'a' का ASCII घटाएं
    while (gotoMat[answer][ch] == -1) // यदि goto नहीं मिला, तो फेल फंक्शन का उपयोग करें
        answer = fail[answer];
    return gotoMat[answer][ch];
}

void patternSearch(string arr[], int size, string text) {
    buildTree(arr, size); // ट्राई स्ट्रक्चर बनाएं
    int presentState = 0; // वर्तमान स्टेट को 0 बनाएं
    for (int i = 0; i < text.size(); i++) { // पैटर्न की सभी घटनाएं ढूंढें
        presentState = getNextState(presentState, text[i]);
        if (output[presentState] == 0) // यदि कोई मैच नहीं तो कंटिन्यू;
            continue;
        for (int j = 0; j < size; ++j) { // मैच मिला और शब्द प्रिंट करें
            if (output[presentState] & (1 << j)) {
                cout << "Word " << arr[j] << " location: " << i - arr[j].size() + 1 << endl;
            }
        }
    }
}

int main() {
    string arr[] = {"their", "there", "answer", "any", "bye"};
    string text = "isthereanyanswerokgoodbye";
    int k = sizeof(arr) / sizeof(arr[0]);
    patternSearch(arr, k, text);
    return 0;
}

आउटपुट

Word there location: 2
Word any location: 7
Word answer location: 10
Word bye location: 22