home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

อัลกอริทึม Aho-Corasick

อัลกอริธึมนี้มีประโยชน์ในการค้นหาการเกิดขึ้นทั้งหมดของชุดคีย์เวิร์ดที่ระบุทั้งหมด เป็นอัลกอริธึมการจับคู่พจนานุกรมชนิดหนึ่ง ใช้โครงสร้างแบบต้นไม้โดยใช้คำสำคัญทั้งหมด หลังจากสร้างต้นไม้แล้ว มันพยายามแปลงต้นไม้ให้เป็นหุ่นยนต์เพื่อทำการค้นหาในเวลาเชิงเส้น Aho-Corasick Algorithm มีสามขั้นตอนที่แตกต่างกัน

สิ่งเหล่านี้คือ ไปสู่ ​​ความล้มเหลว และ ผลผลิต . ในด่านไปสู่ ​​มันทำให้ทรีใช้คีย์เวิร์ดทั้งหมด ในระยะต่อไปหรือในระยะความล้มเหลว จะพยายามค้นหาการเปลี่ยนแปลงย้อนหลังเพื่อให้ได้คำต่อท้ายที่เหมาะสมของคำหลักบางคำ ในขั้นตอนการส่งออก สำหรับทุกรัฐของหุ่นยนต์ จะค้นหาคำทั้งหมดที่ลงท้ายด้วย 's'

ความซับซ้อนของเวลาของอัลกอริทึมนี้คือ:O(N + L + Z) โดยที่ N คือความยาวของข้อความ L คือความยาวของคำหลัก และ Z คือจำนวนที่ตรงกัน

อินพุตและเอาต์พุต

Input:
A set of patterns: {their, there, answer, any, bye}
The main string: “isthereanyanswerokgoodbye”
Output:
Word there location: 2
Word any location: 7
Word answer location: 10
Word bye location: 22

อัลกอริทึม

buildTree(patternList, size)

ป้อนข้อมูล - รายการรูปแบบทั้งหมดและขนาดของรายการ

ผลลัพธ์ − สร้างแผนที่การเปลี่ยนแปลงเพื่อค้นหารูปแบบ

Begin
   set all elements of output array to 0
   set all elements of fail array to -1
   set all elements of goto matrix to -1
   state := 1       //at first there is only one state.

   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 (shift left 1 for i times)
   done

   for all type of characters ch, do
      if goto[0, ch] ≠ 0 then
         fail[goto[0,ch]] := 0
         insert goto[0, ch] into a Queue q.
   done

   while q is not empty, do
      newState := first element of q
      delete from 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]
            insert goto[newState, ch] into q.
      done
   done
   return state
End

getNextState(presentState, nextChar)

อินพุต - สถานะปัจจุบันและอักขระถัดไปเพื่อกำหนดสถานะถัดไป

ผลผลิต : สถานะต่อไป

Begin
   answer := presentState
   ch := nextChar

   while goto[answer, ch] = -41, do
      answer := fail[answer]
   done
   return goto[answer, ch]
End

ค้นหารูปแบบ(รายการรูปแบบ ขนาด ข้อความ)

อินพุต - รายการรูปแบบ ขนาดของรายการ และข้อความหลัก

ผลลัพธ์ − ดัชนีของข้อความที่พบรูปแบบ

Begin
   call buildTree(patternList, size)
   presentState := 0

   for all indexes of the text, do
      if output[presentState] = 0
         ignore next part and go for next iteration
      for all patterns in the patternList, do
         if the pattern found using output array, then
            print the location where pattern is present
      done
   done
End

ตัวอย่าง

#include <iostream>
#include <queue>
#define MAXS 500    //sum of the length of all patterns
#define MAXC 26     //as 26 letters in alphabet
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;    //all element of output is 0

   for(int i = 0; i<MAXS; i++)
      fail[i] = -1;    //all element of failure array is -1

   for(int i = 0; i<MAXS; i++)
      for(int j = 0; j<MAXC; j++)
         gotoMat[i][j] = -1;    //all element of goto matrix is -1

   int state = 1;    //there is only one state

   for (int i = 0; i < size; i++) {    //make trie structure for all pattern in array
      //const string &word = array[i];
      string word = array[i];
      int presentState = 0;

      for (int j = 0; j < word.size(); ++j) {    //all pattern is added
         int ch = word[j] - 'a';
         if (gotoMat[presentState][ch] == -1)    //ic ch is not present make new node
            gotoMat[presentState][ch] = state++;    //increase state
            presentState = gotoMat[presentState][ch];
      }
      output[presentState] |= (1 << i); //current word added in the output
   }

   for (int ch = 0; ch < MAXC; ++ch)   //if ch is not directly connected to root
      if (gotoMat[0][ch] == -1)
         gotoMat[0][ch] = 0;

         queue<int> q;

   for (int ch = 0; ch < MAXC; ++ch) {    //node goes to previous state when fails
      if (gotoMat[0][ch] != 0) {
         fail[gotoMat[0][ch]] = 0;
         q.push(gotoMat[0][ch]);
      }
   }

   while (q.size()) {
      int state = q.front();    //remove front node
      q.pop();

      for (int ch = 0; ch <= MAXC; ++ch) {
         if (gotoMat[state][ch] != -1) {    //if goto state is present
            int failure = fail[state];
            while (gotoMat[failure][ch] == -1)    //find deepest node with proper suffix
               failure = fail[failure];
            failure = gotoMat[failure][ch];
            fail[gotoMat[state][ch]] = failure;
            output[gotoMat[state][ch]] |= output[failure];   // Merge output values
            q.push(gotoMat[state][ch]);    //add next level node to the queue
         }
      }
   }
   return state;
}

int getNextState(int presentState, char nextChar) {
   int answer = presentState;
   int ch = nextChar - 'a'; //subtract ascii of 'a'

   while (gotoMat[answer][ch] == -1) //if go to is not found, use fail function
      answer = fail[answer];
   return gotoMat[answer][ch];
}

void patternSearch(string arr[], int size, string text) {
   buildTree(arr, size);    //make the trie structure
   int presentState = 0;    //make current state as 0

   for (int i = 0; i < text.size(); i++) {    //find all occurances of pattern
      presentState = getNextState(presentState, text[i]);
      if (output[presentState] == 0)    //if no match continue;
      for (int j = 0; j < size; ++j) {   //matching found and print words
         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