아호 코 라식 | Advanced Data Structures: Aho-Corasick Automaton 모든 답변

당신은 주제를 찾고 있습니까 “아호 코 라식 – Advanced Data Structures: Aho-Corasick Automaton“? 다음 카테고리의 웹사이트 https://kk.taphoamini.com 에서 귀하의 모든 질문에 답변해 드립니다: https://kk.taphoamini.com/wiki/. 바로 아래에서 답을 찾을 수 있습니다. 작성자 Niema Moshiri 이(가) 작성한 기사에는 조회수 36,866회 및 좋아요 618개 개의 좋아요가 있습니다.

아호 코 라식 주제에 대한 동영상 보기

여기에서 이 주제에 대한 비디오를 시청하십시오. 주의 깊게 살펴보고 읽고 있는 내용에 대한 피드백을 제공하세요!

d여기에서 Advanced Data Structures: Aho-Corasick Automaton – 아호 코 라식 주제에 대한 세부정보를 참조하세요

아호 코 라식 주제에 대한 자세한 내용은 여기를 참조하세요.

아호코라식(Aho-Corasick) – 네이버 블로그

아호코라식(Aho-Corasick)은 현재 광범위하게 알려진 거의 유일한 일대다 패턴매칭 알고리즘이고, 그 존재 자체만으로 거의 KMP급의, 개선의 여지가 …

+ 여기에 보기

Source: m.blog.naver.com

Date Published: 7/6/2022

View: 8229

[알고리즘] 아호 코라식(Aho-Corasick) 알고리즘 – 팡트루야

2. 아호 코라식(Aho-Corasick) 알고리즘이란? · 일대다 문자열 패턴 매칭에 사용되는 알고리즘입니다. 패턴 문자열의 갯수와 상관없이 · 원본 문자열을 한 …

+ 여기에 자세히 보기

Source: pangtrue.tistory.com

Date Published: 11/7/2022

View: 4249

아호 코라식 알고리즘 – 위키백과, 우리 모두의 백과사전

아호 코라식 알고리즘(Aho–Corasick string matching algorithm)은 Alfred V. Aho와 Margaret J. Corasick이 고안한 문자열 검색 알고리즘(매칭 알고리즘)이다.

+ 여기에 자세히 보기

Source: ko.wikipedia.org

Date Published: 12/4/2022

View: 7217

(C++) 문자열 검색 알고리즘 : 아호-코라식(Aho-Corasick …

아호 코라식 알고리즘을 이해하기 위해선 트라이 자료구조와 KMP 알고리즘 개념이 선행되어야 한다.(추가로 BFS 도 알고 있어야 한다.) …

+ 여기에 표시

Source: ansohxxn.github.io

Date Published: 8/23/2021

View: 7531

[알고리즘] 다중 문자열 검색 아호 코라식(Aho-Corasick …

아호 코라식 알고리즘(Aho–Corasick string matching algorithm)은 Alfred V. Aho와 Margaret J. Corasick이 고안한 문자열 검색 알고리즘(매칭 …

+ 더 읽기

Source: loosie.tistory.com

Date Published: 4/1/2022

View: 5558

Aho-Corasick Multiple Pattern Matching Algorithm – 구사과

Aho-Corasick Multiple Pattern Matching Algorithm … 문자열 S와 여러 개의 문자열 T가 주어졌을 때, T에 있는 문자열 중 하나와 S가 매칭이 되는 지를 …

+ 여기에 자세히 보기

Source: koosaga.com

Date Published: 4/5/2021

View: 3416

아호코라식 다중 패턴 매칭(Aho-Corasick)

여러 문자열 패턴이 있고, 특정 문자열에 어떤 패턴이 어디에 존재하는지 확인하고 싶을 때 쓰는 알고리즘입니다. 기술적으로는 prefix와 suffix를 가지고 …

+ 여기에 자세히 보기

Source: coloredrabbit.tistory.com

Date Published: 7/13/2022

View: 2951

문자열 매칭 알고리즘[3](트라이 & 아호 코라식)[String …

문자열 매칭 알고리즘[3](트라이 & 아호 코라식)[String Searching Algorithm, Trie & Aho-Corasick]. jjudrgn 2022. 1. 15. 18:50. KMP : 문자열 S가 있을 때, …

+ 여기에 자세히 보기

Source: jjudrgn.tistory.com

Date Published: 8/14/2022

View: 5298

아호 코 라식 | Advanced Data Structures: Aho-Corasick …

아호 코라식 알고리즘(Aho–Corasick string matching algorithm)은 Alfred V. Aho와 Margaret J. Corasick이 고안한 문자열 검색 알고리즘(매칭 알고리즘) …

+ 자세한 내용은 여기를 클릭하십시오

Source: you.1111.com.vn

Date Published: 3/24/2021

View: 904

KMP 알고리즘과 Aho-Corasick 알고리즘

본 글에서는 대표적인 문자열 검색 알고리즘인 KMP 알고리즘과 Aho-Corasick 알고리즘에 대해 다루려 한다. 두 알고리즘이 알고리즘계에서 잘 알려진 …

+ 여기를 클릭

Source: www.secmem.org

Date Published: 10/20/2022

View: 6914

주제와 관련된 이미지 아호 코 라식

주제와 관련된 더 많은 사진을 참조하십시오 Advanced Data Structures: Aho-Corasick Automaton. 댓글에서 더 많은 관련 이미지를 보거나 필요한 경우 더 많은 관련 기사를 볼 수 있습니다.

---

주제에 대한 기사 평가 아호 코 라식

• Author: Niema Moshiri
• Views: 조회수 36,866회
• Likes: 좋아요 618개
• Date Published: 2020. 4. 26.
• Video Url link: https://www.youtube.com/watch?v=O7_w001f58c

아호코라식(Aho-Corasick)

안녕하세요. 진짜 강좌를 이제 두 달만에… 메이플 개꿀잼이네요.

문자열 파트 글이 두 개 남았는데, 모두가 아실 아호코라식과 서픽스어레이입니다만…

오늘 드디어 제가 각 잡고 아호코라식 강좌글을 쓰려고 합니다.

아호코라식(Aho-Corasick)은 현재 광범위하게 알려진 거의 유일한 일대다 패턴매칭 알고리즘이고, 그 존재 자체만으로 거의 KMP급의, 개선의 여지가 보이지 않는 사기적 성능을 자랑합니다.

일대다 패턴매칭은 지금까지의 KMP나 라빈카프 등과 달리, 문자열 하나 안에 여러 각각의 문자열이 존재하는지를 다 판별하는 것을 말합니다.

문자열 S에서, 찾을 단어 집합 W의 각 단어 w1, w2, … , wk를 찾는다고 해봅시다. 그리고 S의 길이를 N, 각 단어의 길이를 m1, m2, … mk라 하면…

그냥 naive하게 완전탐색으로 찾는다면 O(N(m1+m2+…+mk))입니다.

그러나, 아호 코라식은 또 S를 한 번만 훑어서 결과를 내기 때문에 O(N+m1+m2+…+mk)입니다. (뭐???)

사실 저거보다는 좀 크긴 합니다. 전처리과정 및 기타등등 때문에… 하지만 여전히 대단한 건 사실.

KMP의 확장이 아호코라식이라고 볼 수 있습니다. 반대로 아호코라식의 축소가 KMP고요.

KMP와 유사하게, 오토마타적 개념이 들어갑니다. 한 번 예시를 봅시다.

대략 이렇게 생겼는데 시작 state는 제일 왼쪽의 것입니다.

네, 이거… 바로 이전 글을 보셨다면 아시겠지만 일종의 트라이입니다.

여기서 S의 문자를 하나씩 인풋으로 읽어가면서 다음 state로 이동해야 하는데요. 다음 state를 go 함수로 정의합니다.

빨간 것들이 output 노드고, output 노드에 도달했다면 거기 적혀 있는 문자열들이 S에 등장한다는 것이 확정되는 겁니다.

output 노드들에는 이 노드를 지날 때 내뱉는 단어의 목록이 있는데 이를 output 함수라 합니다.

한 번 시뮬레이션을 해봅시다. S = “cdhisxy”일 때, 어떤 문자열들이 S에 들어있는지…!

현재 state가 빨간색입니다. 만약 중간에 매칭이 끊기면 시작 state로 돌아간다고 해보죠. 일단은…

일단 첫 번째 글자 c를 인풋으로 받아서 다른 데로 갈 수가 없네요. 그대로 있습니다.

다음 글자 d도 마찬가지입니다.

그러나 h를 보니까 이번엔 갈 수가 있네요. 이동합니다.

다음 글자인 i 역시 다음 길이 있으므로 이동.

s를 봐서 output 노드 중 하나에 도달합니다. 여기 도착했다면 “his”는 S에 속한다는 걸 알 수 있습니다.

직관적으로 맞고, 실제로도 맞죠. h, i, s를 순서대로 거쳐온 곳이 여기니까요.

그 다음 글자 x에 대한 이동경로가 없으므로 처음으로 돌아가고… 이하 생략.

일단 W의 원소를 찾는 걸 대략 살펴보았지만 아직은 뭔가 빠진 점이 있습니다.

일단 S를 앞에서부터 한 글자씩 훑어가다가 결과가 나와야 하고, 절대 뒤로 돌아가지 않는다는 원칙을 지켜야 하는데…

만약 S = “shis”라면 s, h를 지나고 i를 봤을 때 어디로 가야 할까요?

일단 S에 “his”가 있는 건 확실한데, i를 보고 시작지점으로 돌아가면 절대 저걸 찾을 수가 없습니다.

어디로 돌아가야 할까요?

일단 결과를 보고 끼워맞추기식으로 추측하자면, 시작지점에서 h를 받고 이동한 state로 보내야 “his”를 찾을 수 있습니다. 빨간색 점선으로 표시했습니다.

저기로 즉각 이동해서, 거기서 go(i)가 존재하는지 보고 존재한다면 이동하면 됩니다.

이렇게 아호코라식 알고리즘을 진행하면서 갈 곳이 없어지면 단순히 시작지점이 아니라 다른 어떤 곳으로 보내는 다른 함수가 필요합니다. 그것을 fail 함수라 칭합니다.

KMP에서도 사용했던 용어인데, 거의 비슷합니다. 여기선 저 오토마타가 일직선이 아닐 뿐이죠.

이렇게 아호코라식에는 go, output, fail 3개의 중요한 함수가 존재합니다.

그럼 이제 fail 함수 값을 도대체 어떻게 빠르게 알아내느냐가 문제입니다.

아무렇게나 알아내서 너무 느려지면 아호코라식의 저 빠른 탐색시간이 의미가 없어지니까요.

아니 일단 도대체 어디로 가야 할까요? 그것부터 알아봅시다.

위 예제에서, 왜 fail 함수 중 하나인 저 빨간 점선이 저렇게 이어져 있는 걸까요?

그것은 바로 그 state까지 거쳐온 인풋과 관련이 있습니다.

설명을 쉽게 하기 위해 몇몇 노드들에 이름을 붙이겠습니다.

여기서 go(u, h) = v, go(v, e) = w, go(u, s) = x이고

output(v) = {}, output(w) = {“he”},

fail(v) = u, fail(y) = v입니다. 이런 식으로 각 함수를 표기하겠습니다.

자 이제 fail(y) = v인 이유를 알아내야 하죠.

정점 y로 가려면 시작점으로부터 “sh”를 거쳐와야 하고, 좀 더 일반화하면 바로 최근에 훑은 문자가 s, h여야 합니다.

정점 v로 가려면 최근에 훑은 문자가 h기만 하면 될 겁니다.

한번 생각해 봅시다. W 집합 안에 h(…), sh(…) 2개의 단어가 있는데 (…) 부분이 동일하다고 해보죠.

그렇다면 만약 S에서 sh(…)를 찾았다면 자동으로 h(…)도 있어야만 합니다. 역은 성립하지 않죠.

따라서 sh(…)를 찾으러 가던 경로에서 어긋나도 h(…)로 가는 경로로 보내도 손해볼 게 없고, 오히려 다른 h로 시작하는 단어들, 여기서는 “his”를 문제없이 찾을 수 있을 겁니다.

또한, 그림에는 없지만 마찬가지 이유로 fail(z) = w이기도 합니다.

그러면 트라이상에 h가 엄청 많으면 어디로 보낼지 어떻게 아느냐? 여기서 규칙이 하나 더 있습니다. fail 함수는 반드시 자신보다 깊이가 작은 노드를 가리킵니다. 루트만 제외하고요.

어려운 예제를 한 번 봅시다. KMP에서 fail로 가고 또 거기서 fail로 가는 등, 한 번만 fail로 이동하고서 끝나지 않는 경우가 있는데, 아호코라식에서도 마찬가지입니다.

여기서도 그냥 루트로 가는 fail 간선들은 생략합니다. 그렇지 않은 것들에 대해 생각해보죠.

“ada” 노드에서의 fail은 쉽죠. “a”로 가면 될 겁니다.

만약 S = “adac”면 c를 보고 fail 함수를 통해 “a”로 돌아가 “ac”를 찾아갑니다.

노드 “adab”의 fail도 마찬가지로 노드 “ab”를 찾아가게 하면 됩니다. “adad”도 마찬가지로 “ad”로 보내면 됩니다.

지금까지 fail 함수를 관찰하면서 알 수 있는 점은, fail(x) = y면 x의 (x가 아닌) 접미사 중 하나가 반드시 y입니다. 그렇게 놀라운 사실이 아니죠? 그리고 이 말이 아까의 fail 함수 결과는 깊이가 줄어든다는 말을 뒷받침합니다.

여기서 더 나아가서, y는 가능한 한 가장 긴 접미사입니다. 다음을 봅시다.

몇몇 간선은 복잡해서 지웠고, “adada”의 fail이 “ada”가 되는데요.

자 이제 S = “adadac”면 마지막에 c를 보고 fail로 돌아가야 하는데요, 아직은 “ac”에 도달할 수 없죠.

여기서 한 번 더 fail을 타고 가보니 이제 go(…, c)가 존재합니다! “ac”를 찾을 수 있죠.

자, 이제 fail 함수가 주어졌을 때 메커니즘을 정리해 드리겠습니다.

① 현재 state x, 인풋 c에 대해 go(x, c)가 있으면 거기로 이동한다.

② 만약 없다면, fail(x)로 이동한 후 ①로 돌아간다. 단, 이미 루트면 아무것도 하지 않는다.

KMP를 어느 정도 이해하신 분이라면, 정말로 아호코라식이 KMP의 확장이 맞게 느껴지실 겁니다. 상당 부분이 비슷하게 작동하고 있죠.

이제 마지막으로 fail 함수를 정하는 것만 빠르게 하면 되겠는데요. 아까 말씀드렸듯이 fail(x)는 트라이상에 존재하는 x의 가장 긴 접미사 노드입니다. 물론 x 자신은 아닙니다.

이걸 찾아야겠는데… BFS를 통해 깊이가 작은 노드부터 방문해가면 fail 함수를 DP를 적용하듯이 결정할 수 있습니다.

아까 첫 번째 예제에서 “he”와 “she”를 보면, fail 함수 간선들이 평행선을 그리는데 이것 또한 그리 놀라운 일이 아닙니다.

만약 어떤 트라이상의 문자열 x, yx가 있고(x, y는 문자열) fail(yx) = x라 해봅시다. 그럼 여기에 각각 똑같은 문자열 z를 더 이어붙여 xz, yxz도 W에 포함시키면?

fail(yxz)는 무엇인가요? xz겠죠. 실제로 오토마타상에서 z 구간의 노드들의 fail을 다 간선으로 나타내면 쭈우우욱 평행선들을 그리게 될 겁니다.

이런 구조 덕분에, 문자열 p가 있을 때, 문자 x를 이어붙이면 fail(px) = go(fail(p), x)이 됩니다. 이제 바텀업 DP처럼 보이죠?

또한, 마지막으로 여기서 output 함수도 다듬어주어야 합니다. 사실 처음에 트라이를 만들 때 “she” 끝에 “he”도 속하는지 어떻게 알겠어요?

fail(x) = y일 때, output(y) ⊂ output(x)인 관계가 성립합니다! 이것도 접미사 관계에서 나타나는 관계죠.

이제부터 자세한 건 코드를 봅시다.

https://www.acmicpc.net/problem/9250

아호코라식 제일 기초 문제입니다. 노테이션에 주의해야 하는데 이 문제에서는 찾아야 할 단어의 집합이 S입니다.

Q번의 질문이 들어오는데 각 단어가 S의 원소를 적어도 하나 포함하는지를 대답하는 문제입니다.

아호코라식을 사용한다면 시간복잡도가 어떻게 되냐면, 오토마타를 만드는 데 O(S의 단어 길이 합), 각 단어 판정에 O(단어 길이)만큼이 들어갑니다. 후자 Q가 곱해졌을 시에 더 크고, 값이 대략 천만쯤 되므로 돌아갑니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 #include < cstdio > #include < queue > #include < algorithm > using namespace std ; // 트라이 구조체 struct Trie{ // 현재 노드에서 해당 문자를 받으면 가는 노드 Trie * go[ 26 ]; // 현재 노드에서 해당 문자의 go 목적지가 없을 때 가는 노드 Trie * fail; // 현재 노드에 도달하면 찾는 문자열 집합: 이 문제에서는 존재성만 따지면 됨 bool output; Trie(){ fill(go, go + 26 , nullptr); output = false ; } ~Trie(){ for ( int i = 0 ; i < 26 ; i + + ) if (go[i]) delete go[i]; } void insert( const char * key){ if ( * key = = '\0' ){ output = true ; return ; } int next = * key - 'a' ; if ( ! go[next]){ go[next] = new Trie; } go[next] - > insert(key + 1 ); } }; int main(){ int N, M; char str[ 10001 ]; // 트라이에 S의 원소들을 모두 집어넣는다. Trie * root = new Trie; scanf ( “%d” , & N); for ( int i = 0 ; i < N; i + + ){ scanf ( "%s" , str); root - > insert(str); } // BFS를 통해 트라이 노드를 방문하며 fail 함수를 만든다. queue < Trie * > Q; root – > fail = root; Q.push(root); while ( ! Q.empty()){ Trie * current = Q. front (); Q. pop (); // 26개의 input 각각에 대해 처리한다. for ( int i = 0 ; i < 26 ; i + + ){ Trie * next = current - > go[i]; if ( ! next) continue ; // 루트의 fail은 루트다. if (current = = root) next – > fail = root; else { Trie * dest = current – > fail; // fail을 참조할 가장 가까운 조상을 찾아간다. while (dest ! = root & & ! dest – > go[i]) dest = dest – > fail; // fail(px) = go(fail(p), x) if (dest – > go[i]) dest = dest – > go[i]; next – > fail = dest; } // fail(x) = y일 때, output(y) ⊂ output(x) if (next – > fail – > output) next – > output = true ; // 큐에 다음 노드 push Q.push(next); } } // 각 문자열을 받아 문제를 푼다. scanf ( “%d” , & M); for ( int i = 0 ; i < M; i + + ){ scanf ( "%s" , str); // 루트부터 시작 Trie * current = root; bool result = false ; for ( int c = 0 ; str[c]; c + + ){ int next = str[c] - 'a' ; // 현재 노드에서 갈 수 없으면 fail을 계속 따라감 while (current ! = root & & ! current - > go[next]) current = current – > fail; // go 함수가 존재하면 이동. 루트면 이게 false일 수도 있다 if (current – > go[next]) current = current – > go[next]; // 현재 노드에 output이 있으면 찾은 것이다. if (current – > output){ result = true ; break ; } } // 결과 출력 puts(result ? “YES” : “NO” ); } // 내 힙은 소중하기에 꼭 동적할당을 해제한다. delete root; } Colored by Color Scripter cs

코드가 크게 트라이 구조체 정의, 트라이에 S의 원소들 삽입, fail 및 output 함수 완성, Q개의 문자열 각각 판정하기 이렇게 4구간으로 나뉘어 있습니다.

매우 기니까 부분부분 쪼개서 보시는 걸 추천드립니다.

사실 위 코드에서는 항상 fail(x)가 x의 가장 긴 접미사가 아닐 수도 있는데요, 그건 굳이 그렇지 않아도 결과에 아무 영향이 가지 않아서입니다.

추천 문제

9250번: 문자열 집합 판별

위에서 설명한 문제입니다.

10256번: 돌연변이 (★)

BOJ에서 아호코라식 응용 문제 중 제일 유명합니다. 마커의 길이가 최대 100이니까, 그냥 가능한 모든 돌연변이 마커를 찾아 트라이를 구성하면 됩니다. 돌연변이 마커의 개수는 O(m^2)개죠. 그리고 주어진 DNA에서 몇 개의 단어가 등장하는지 세면 됩니다. 개수를 세려면 단순히 output이 bool 변수면 안 되겠죠?

트라이의 성격상 메모리를 굉장히 많이 쓰는데 한 입력에 테스트 케이스도 여러 개기 때문에, 자신이 만약 트라이나 무언가를 동적할당한다면 꼭 해제를 해주셔야 합니다. 또한 문자가 4개밖에 등장하지 않으므로 어떻게든 대응을 시켜 go 배열도 4칸으로 최소화하는 게 좋습니다. 메모리 초과가 많이 나는 문제입니다.

5735번: Emoticons (★)

아주 조금만 응용을 해야 합니다. 일단 이젠 영소문자만 등장하지가 않으므로 go 함수 메모리가 더 커질 겁니다. 각 문장마다 이모티콘을 한 번 찾을 때마다, 그 찾은 이모티콘의 제일 끝 자리에 대응하는 글자만 지우면 최소 개수의 글자를 지울 수 있습니다.

6300번: Word Puzzles

방법을 굳이 설명하지 않겠습니다… 여러분이 생각하시는 그게 맞을 겁니다… 정말 자신이 코딩변태다 싶은 분이 아니면, 그냥 이런 문제가 대회에 나온 적이 있구나 하는 정도만 알아가시는 게…

[알고리즘] 아호 코라식(Aho-Corasick) 알고리즘

1. 개요

다음과 같은 두 개의 문자열이 있습니다.

S = “abababdddd” (String의 약자를 따서 S라 표현)

W = “bab” (Word의 약자를 따서 W라 표현)

아시는거처럼 S에서 W가 존재하는지를 찾아내는, 이른바 일대일 문자열 패턴 매칭 알고리즘으로는 KMP 알고리즘이 있습니다.

그런데 매칭에 사용될 패턴이 다음과 같이 여러 개라면 어떨까요? 🤔

S = “abababdddd”

W = {“bab”, “bd”, “ab”}

즉, 하나의 문자열 안에서 여러 개의 부분 문자열이 존재하는지 찾아내는 일대다 문자열 패턴 매칭이라면 어떻게 할 수 있을까요?

물론 W 집합 안의 문자열에 대해 하나씩 KMP 알고리즘을 돌려보는 방법도 가능합니다.

KMP 알고리즘의 시간 복잡도는 $O(n+m)$ 니깐,

P 집합 안의 문자열의 갯수가 k개라고 할때 KMP 알고리즘으로 일대다 문자열 패턴 매칭을 했을 경우의 시간 복잡도는..

$O(kn+m_{1}+m_{2}+…+m_{k})$ 입니다.

2. 아호 코라식(Aho-Corasick) 알고리즘이란?

예상하신대로 아호 코라식은 일대다 문자열 패턴 매칭에 사용되는 알고리즘입니다. 패턴 문자열의 갯수와 상관없이 원본 문자열을 한 번만 훑어서 찾아내기 때문에 시간 복잡도는 $O(n+m_{1}+m_{2}+…+m_{k})$ 입니다. ( KMP보다 놀라울정도로 빠른건 아닌거같은데… 🧐 )

어쨋든, 아호 코라식 알고리즘은 KMP 알고리즘의 확장이라고 볼 수 있습니다. (메커니즘이 비슷합니다).

KMP 알고리즘이 문자열과 문자열 간의 매칭이라면, 아호 코라식은 문자열과 트라이 간의 매칭입니다.

(아호 코라식을 배우시기 전에 KMP 알고리즘과 트라이 자료구조가 선행이 되어있어야 합니다..!)

다음과 같은 트라이가 있습니다. (S는 원본 문자열, W는 패턴 문자열 집합)

[그림 1] 트라이 모습

S 문자열과 트라이 간의 패턴 매칭 과정을 살펴보겠습니다.

[그림 2] 트라이에서의 매칭 과정

이어서 그 다음 문자인 b도 있기 때문에 똑같이 “abab” 라는 문자열을 찾을 수 있습니다. 문제는 그 다음인데요,

b 문자 다음은 a 문자인데 해당 문자는 없기 때문에 현재 노드를 가리키는 포인터가 롤백을 해야합니다.

[그림 3] 트라이에서 매칭 중 실패한 상황

트라이에서 매칭을 하다가 매칭이 실패했을 경우 현재 가리키고 있는 지점을 다른 곳으로 이동시키는 함수를 fail 함수라고 부릅니다.

그럼 포인터를 어디로 이동시켜야할까? 매칭에 실패한 문자 전까지의 일치한 문자열에 대해 접두사와 접미사가 같은 지점입니다.

[그림 4] 매칭에 실패했을 땐 그 전까지 일치한 문자열의 접두사-접미사가 같은 지점으로 이동

다음부터는 지금까지의 과정을 반복하면 되니 생략하겠습니다. 😉

매칭의 과정과 실패했을 때 어디로 이동해야하는지는 알겠는데.. 어떻게 저 지점으로 이동할 수 있을까요?

이 부분부터 조금 어려울 수 있는데 하나씩 살펴보겠습니다.

트라이는 Trie 안에 각 노드를 가리킬 TrieNode 타입 변수를 두는 식으로 만들었습니다. (어떤 식으로 구현하는가는 자유입니다.)

class Trie { TrieNode root = new TrieNode(true); // 메서드는 생략.. } class TrieNode { TrieNode[] child; TrieNode fail; // 실패했을 때, 이동해야할 지점을 가리킬 변수 boolean isEnd; // 완성된 문자열인지 표시 (일반적인 트라이에 나오는 개념입니다.) boolean isRoot; TrieNode(boolean isRoot) { child = new TrieNode[26]; // 알파벳 소문자만 있다고 가정하고 사이즈는 26 this.isRoot = isRoot; } // 메서드는 생략… }

다음으로, 실패 함수 코드를 살펴보겠습니다. 해당 함수의 역할은 위 TrieNode의 fail 변수의 값을 채워주는 것입니다.

그러기 위해선 트라이를 탐색해야하기 때문에 BFS 탐색이 사용됩니다.

// 실패 함수 (KMP로 비교를 하다가 실패했을 때의 이동해야할 지점을 정의한다.) // 일반적인 KMP 구현에서 getPi() 메서드에 해당한다. void failure() { Queue q = new LinkedList<>(); trie.root.fail = trie.root; // root 회귀 q.add(trie.root); // 트리에 담긴 문자열에 대해 접두사-접미사가 동일한 것을 뽑아내야 한다. (BFS 이용) while (!q.isEmpty()) { TrieNode currentNode = q.poll(); // 알파벳 소문자만 있다고 가정하고 크기는 26 for (int i = 0; i < 26; i++) { TrieNode nextNode = currentNode.child[i]; if (nextNode == null) continue; if (currentNode.isRoot) { // root 자식 노드의 fail은 그들의 부모인 root 노드가 된다. nextNode.fail = trie.root; } else { TrieNode failure = currentNode.fail; while (!failure.isRoot && failure.child[i] == null) { failure = failure.fail; } if (failure.child[i] != null) { failure = failure.child[i]; } nextNode.fail = failure; } if (nextNode.fail.isEnd) { nextNode.isEnd = true; } q.add(nextNode); } } } 세팅이 끝났으면 마지막으로 문자열과 트라이 간의 KMP 알고리즘을 사용하는 코드는 다음과 같습니다. boolean kmp(String origin, TrieNode root) { TrieNode currentNode = root; boolean isFind = false; for (int i = 0; i < origin.length(); i++) { int idx = origin.charAt(i) - 'a'; while (!currentNode.isRoot && currentNode.child[idx] == null) { currentNode = currentNode.fail; } if (currentNode.child[idx] != null) { currentNode = currentNode.child[idx]; } if (currentNode.isEnd) { // 원본 문자열에서 패턴 문자열 하나를 찾았다면 isFind = true; } } return isFind; } 3. 참고자료 [1] m.blog.naver.com/PostView.nhn [2] www.slideshare.net/ssuser81b91b/ahocorasick-algorithm [3] koosaga.com/157

아호 코라식 알고리즘

아호 코라식 알고리즘(Aho–Corasick string matching algorithm)은 Alfred V. Aho와 Margaret J. Corasick이 고안한 문자열 검색 알고리즘(매칭 알고리즘)이다.

패턴 1개를 탐색하는 매칭 알고리즘은 선형 시간에 구현됨을 KMP 등 여러 알고리즘을 통하여 증명되었다. 하지만 패턴 집합에 대하여 이러한 알고리즘을 수행하게 되면 패턴 개수에 비례하여 그 속도가 느려지게 된다. 즉, O ( m + z n ) {\displaystyle O(m+zn)} 의 시간 복잡도를 가지게 된다.( m {\displaystyle m} : 모든 패턴들의 길이 합, z {\displaystyle z} : 패턴 수, n {\displaystyle n} : text 크기) 하지만 Aho-Corasick 알고리즘을 이용하면 O ( m + n + k ) {\displaystyle O(m+n+k)} 의 시간 복잡도로 패턴 집합에 대하여 패턴 길이와 텍스트의 선형 시간에 탐색을 처리할 수 있게 된다.(k: 텍스트 내에 패턴의 발생 수) 이러한 Aho-Corasick 알고리즘을 구현하기 위하여 Keyword Tree, Failure link, Output link 자료구조를 사용하여야 한다.

키워드 트리 [ 편집 ]

키워드 트리(Keyword Tree)는 패턴의 글자 하나를 하나의 간선으로 한다. 그리고 서로 패턴들의 접두사가 최대한 같을 때까지는 같은 정점으로 간선을 따라가고 글자가 달라지면 다른 간선으로 가도록 만들게 된다. 전 처리 과정에서 Keyword Tree를 만들면서 모든 패턴들의 길이의 합의 시간 복잡도 안에 만들 수 있게 된다.

실패 링크 [ 편집 ]

모든 패턴을 차례로 Keyword Tree에 넣은 이 후에는 이 Tree에 실패 링크(Failure link)를 추가해주게 된다. 루트에서 거리가 1인 정점들의 Failure link는 루트로 초기화한다. 그리고 거리가 2 이상인 정점들에 대해서 거리를 키워가면서 바로 앞 정점의 Failure link를 따라 가서 앞 정점과 해당 정점 사이의 간선에 해당하는 글자와 Failure link를 따라 간 정점의 글자가 같으면 그 정점으로 Failure link를 저장하게 되고 아니면 계속 Failure link를 따라가면서 처리하고 만약 루트가 나오면 해당 글자와 같은 거리가 1인 정점이 존재하면 거기로 Failure link를 저장하고 아니면 루트로 저장하게 된다. 위와 같은 방법으로 하게 되면 모든 패턴들의 길이의 합의 시간 복잡도 안에 모든 Failure link를 만들 수 있게 된다.

출력 링크 [ 편집 ]

여기에 패턴들 중에 다른 패턴의 substring이 존재하게 되면 패턴들을 탐색하지 못 할 때가 발생할 수 있다. 이를 막기 위하여 출력 링크(Output link)라는 자료 구조를 추가하게 된다. 각각의 패턴들이 끝이 나는 정점은 그 정점을 Output link로 가지게 된다. 그리고 다른 정점에서 Failure link를 따라 가서 패턴이 끝이 나게 되면 여러 단계의 Failure link를 무시하고 바로 그 정점으로 Output link를 연결해 주게 된다. 이를 하기 위하여 Failure link를 추가할 때, 같이 Failure link를 따라간 정점이 패턴의 끝이면 그 정점으로 Output link로 하고 그렇지 않으면 그 정점의 Output link를 가져옴으로 모든 패턴들의 길이의 합의 시간 복잡도 안에 처리가 가능하게 된다.

자료구조를 이용한 탐색 [ 편집 ]

텍스트의 글자와 Keyword Tree의 간선의 글자와 비교하면서 정점으로 내려가게 된다. 비교하면서 내려가면서 Output link가 존재하는지 확인을 계속 하고 Output link가 존재하면 패턴이 발생했음을 알려주게 된다. 또한 비교하다가 틀리게 되면 Failure link를 따라 가서 계속 글자를 비교해 주면서 탐색을 하게 된다. 이와 같이 탐색을 하게 됨으로 텍스트에 대하여 한번 확인하였으면 다시 확인하지 않게 되고 따라서 O ( m + n + k ) {\displaystyle O(m+n+k)} 의 시간 복잡도로 처리가 가능하게 된다.

참조 [ 편집 ]

(C++) 문자열 검색 알고리즘 : 아호-코라식(Aho-Corasick) 알고리즘

🚀 서론

아호 코라식 알고리즘을 이해하기 위해선 트라이 자료구조와 KMP 알고리즘 개념이 선행되어야 한다.(추가로 BFS 도 알고 있어야 한다.) 아호 코라식은 트라이 자료구조를 사용하며 KMP 알고리즘의 확장판이라고 볼 수 있기 때문이다. 자세한 설명은 아래 링크 참고 🙂

🔥 쓰임새

여러 문자열 들을 동시에 찾아야 하는 검색 엔진 에서 유용하게 사용되는 알고리즘

KMP 👉 텍스트에서 검색어 하나를 찾아낼 때 사용 (1:1)

아호 코라식 👉 텍스트에서 검색어 여러개를 동시에 찾아낼 때 사용 (1:N)

ex) “cacachefcachy” 텍스트에 { “cache”, “he”, “chef”, “archy” } 中 하나라도 부분 문자열로 포함되어 있는지 찾기.

아호코라식 알고리즘을 통해 수 많은 페이지에서 여러 검색어들이 부분적으로 포함된 각각의 위치들을 빠르게 찾아낼 수 있다.

🔥 용어

텍스트, text : 검색을 실행할 문자열. 이 문자열 내에 원하는 검색어가 있는지 탐색해보고자 함. \(N\) : 텍스트의 길이

검색어, search, pattern : 검색할 문자열. 검색이 된다면 텍스트 의 부분 문자열. 문자열 패턴 매칭을 하는 것과도 같기에 패턴이라고도 칭할 것. \(M\) : 검색어의 길이 \(k\) : 검색어의 총 개수 👉 아호 코라식은 검색어가 여러개일 때 사용

🔥 다른 방법들과의 비교 (+ 아호-코라식의 시간 복잡도)

브루트 포스 일일이 검색어들마다 텍스트와 브루트 포스로 비교한다면 👉 \(O(nm_{1} + nm_{2} + nm_{3} + .. + nm_{k})\)

KMP 알고리즘을 N 번 실행 일일이 검색어들마다 텍스트와 KMP 알고리즘으로 비교 👉 \(O(n + m_{1} + n + m_{2} + n + m_{3} + .. + n + m_{k}) = O(kn + m_{1} + m_{2} + m_{3} + .. + m_{k})\) 동일한 텍스트를 \(k\) 번 검사해야 하고 (\(kn\)) 검색어들 별로 실패 함수들 \(m_{1} + m_{2} + m_{3} + .. + m_{k}\) 을 따로 다 만들어야 한다.

아호 코라식 을 사용했을 때 일일이 검색어들마다 비교하지 않고, 검색어들을 트라이 트리에 모아두고 한번에 순회한다. 👉 \(O(n + m_{1} + m_{2} + .. + m_{k})\) 텍스트의 순회는 단 한번만 하면 된다. \(n\) 검색어 별로 실패 “링크” 를 만들 때 \(m_{1} + m_{2} + m_{3} + .. + m_{k}\) 아호 코라식은 실패 함수 “배열”을 만들지 않고 트라이에서 불일치시 돌아갈 실패 “링크” 를 만든다. 이 실패 링크 또한 KMP 처럼 접두사 = 접미사의 최대 길이인 곳으로 돌아간다. A 검색어를 검사하는데서 불일치가 발생했다면 A 검색어의 접미사와 일치하는 다른 B 검색어의 접두사 노드로 간다!

을 사용했을 때

🚀 구현 코드 및 과정 설명

아호 코라식 알고리즘은 트라이 + KMP 짬뽕

🔥 아호-코라식 개념 설명 (두서없음 주의..)

1️⃣ 검색어들은 트라이에 저장한다.

트라이는 여러개의 문자열을 트리 형태로 저장하는 형태의 자료 구조이다. 또한 이 문자열들의 공통된 접두사는 하나의 노드로 묶여 탐색 공간이 줄어들기 때문에 이 트라이에 저장된 문자열들에서 내가 찾아보고자 하는 길이만큼의 시간만 들여서 빠르게 찾아낼 수 있다.

검색어가 여러개일 때, 텍스트 문자열에 이 검색어들이 각각 탐색되는지를 “빠르게” 알고 싶다면 이 검색어들을 트라이에 저장하여 여기서 탐색한다는 것이 아호 코라식의 아이디어다.

2️⃣ KMP 처럼 접두사 = 접미사 실패함수를 미리 전처리 과정에서 구해놓는다. 아호 코라식에선 “실패 링크”라고 불린다. 노드 별로 실패 링크를 만든다.

KMP 와 달리 검색어가 여러개이기 때문에 걸칠 수 있는 그 대상은 검색어 하나가 아닌 여러개가 후보가 될 수 있다. 예를 들어 “블라블라AB” 까지 일치했었다면 이제 “AB” 를 접두사로 가진 ‘다른 검색어’로 이동할 수 있다는 것이다. “AB” 는 이미 일치했다고 걸쳐진 상태로 “AB” 로 시작하는 이 검색어를 텍스트와 비교하는 식이다. 즉, 걸칠 수 있는 다른 검색어로 비교 대상을 바꾸는 것이다.

노드별로 실패링크를 만든다는 것은 A 검색어의 원소와 텍스트를 비교해나가다가 불일치가 발생하면 A 검색어에서 이전까지 일치한 부분 문자열의 접미사를 접두사로 가지는 다른 B 검색어 ‘노드’로 이동하도록 하는 트라이 트리의 “링크”를 만들어주는 것이다.

여기서 한번 짚고 넘어가고 싶은 부분은 트라이 트리에 있어 “조상 및 부모 노드”는 이전 문자이며, “자식 노드”는 다음 문자라는 것에 주의하자. 직계 부모, 직계 조상이면 자신이 속한 그 문자열을 비롯하여 같은 접두사를 공유하는 문자열들 내에서의 “이전 문자”일테고 직계는 아니지만 그냥 나보다 깊이가 얕은 위의 노드들이면 다른 검색어에 속하지만 나보다 인덱스 상으로 더 앞의 문자가 될 것이다. 자식은 그 반대!

3️⃣ KMP 처럼 탐색 시 접두사 = 접미사 최대 길이를 활용하고 걸치는 작업을 한다.

실패 링크로 이동하는 것 자체가 걸치는 작업 이다.

현재 A 노드(=글자)를 방문 중이라고 예를 들자면 KMP 와 비교 이전까지 일치한 문자열 👉 트라이 트리 안에서 A 글자까지 내려오면서 지나온 문자들 이전까지 일치한 문자열의 접미사와 다른 문자열의 접두사 👉 다른 검색어로 비교 하기 위해 옮겨가, 해당 접두사를 걸쳐놓는 위치로 이동한다. 이미 전처리 과정에서 실패 링크를 다 만들어 놨기 때문에 다른 검색어의 걸칠 수 있는 그 위치로 이동하면 된다.

📌 정리

성공 링크 현재 노드(문자)가 비교 중인 텍스트 원소와 일치한다면 이동할 노드 링크 자식 노드(비교중인 검색어의 다음 문자)로 이동하는 링크이다. 트라이를 만드는 과정인 Inser 삽입 함수 과정에서 자연스럽게 정해진다.

실패 링크 현재 노드(문자)가 비교 중인 텍스트 원소와 일치하지 않는다면 이동할 노드 링크 다른 검색어에 걸칠 수 있는게 있다면, 즉!! 이전 노드까지의 접미사 중 다른 검색어의 접두사와 일치하는게 있다면, 즉!! 현재 방문 중인 노드의 부모 노드의 실패링크! 부모의 실패 링크를 타고 가면 나오는 노드에서도 현재 문자가 자식 노드(=다음 문자)로 연결 되는게 있다면 현재 노드의 실패 링크는 부모 노드의 실패 링크의 자식 노드로 가게끔 연결해준다. 즉, 현재 문자에서 불일치되면 현재문자는 이전 문자(부모 노드)까지의 접미사와 동일한 타 검색어의 접두사의 끝 문자가 되도록 이동을 할 수 있도록 하는 것이다. 예시 “블라블라AC” 는 불일치 발생시 “AC블라블라” 로 이동 하도록 실패 링크를 놓을 수 있다. “블라블라ACZ” 는 불일치 발생시 “ACZ블라블라” 로 이동 하도록 실패 링크를 놓을 수 있다. “블라블라AC” 의 자식인 “블라블라ACZ” 는 “블라블라AC” 의 실패 링크인 “AC블라블라” 의 자식인 “ACZ블라블라”를 실패 링크로 가질 수 있는 것이다. 단! “블라블라AC” 의 “C” 의 다음 글자가 “Z” 인게 트라이에 존재한다는 전제하에! 부모의 실패 링크를 타고 가면 나오는 노드에서도 현재 문자가 자식 노드(=다음 문자)로 연결 되는게 없다면 루트로 돌아갈 떄까지, 혹은 현재 문자가 접두사의 끝이 될 수 있을 때까지 부모의 실패링크를 타고 올라가고 그 노드의 실패 링크를 또 타고 올라가고를 반복하여 올라간다. 전체적으로 이렇게 가장 가까운 조상인 직계 부모의 실패링크부터 검사를 하고, 연결되는게 없다면 타고타고 올라가고 하기 때문에 접두사 = 접미사의 “최대 길이”라는 것이 자연스럽게 보장이 된다. 조상 노드들부터 이렇게 실패 링크를 결정 지어 왔기 때문에 DP 방식으로 생각하면 된다.

밑에서 더 자세히 설명하겠지만 BFS 방식으로 루트부터 깊이대로 차례 차례 노드 들을 방문해 내려오면서 각각 실패 링크를 만들어 준다. 그래서 현재 노드의 실패 링크를 결정하고자 하는 시점엔 이미 그의 조상 노드들의 실패 링크는 모두 정해진 상태이다. 만약 재귀 호출 방식으로 DFS 를 사용한다면 직계 부모의 실패 링크는 알 수 있지만 실패 링크를 따라간 노드의 실패 링크는 알 수가 없을 수도 있기 때문이다.(아직 실패링크 안 만든 상태일 수도) 따라서 BFS 를 통해 깊이대로 차례 차례 실패 링크를 만든다.

전체적으로 말로 풀어서 설명하기가 너무 어렵다. 😅 그러니 밑에 도식화 한 과정을 보며 이해해보자.

🔥 전체 코드

#include using namespace std ; struct Trie { // 노드 객체 클래스 public: bool isEnd ; // 이 노드가 한 검색어의 끝인지 아닌지를 알려줌 string p ; // 이 노드까지의 접두사 (아호 코라식의 필요한 부분은 아니다.) map < char , Trie *> child ; // 자식 노드 링크 Trie * fail ; // 실패 링크 ⭐ Trie () : isEnd ( false ), fail ( nullptr ) {} void Insert ( string pattern ) { Trie * now = this ; int m = pattern . length (); for ( int i = 0 ; i < m ; ++ i ) { if ( now -> child . find ( pattern [ i ]) == now -> child . end ()) now -> child [ pattern [ i ]] = new Trie ; now = now -> child [ pattern [ i ]]; if ( i == m – 1 ) { now -> p = pattern ; now -> isEnd = true ; } } } void Fail () { // BFS + KMP Trie * root = this ; queue < Trie *> q ; q . push ( root ); while ( ! q . empty ()) { Trie * now = q . front (); q . pop (); for ( auto & ch : now -> child ) { Trie * next = ch . second ; if ( now == root ) next -> fail = root ; else { Trie * prev = now -> fail ; while ( prev != root && prev -> child . find ( ch . first ) == prev -> child . end ()) prev = prev -> fail ; if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ; } if ( next -> fail -> isEnd ) next -> isEnd = true ; q . push ( next ); } } } }; vector < pair < string , int >> KMP ( string text , Trie * root ) { Trie * now = root ; int n = text . length (); vector < pair < string , int >> answer ; for ( int i = 0 ; i < n ; ++ i ) { while ( now != root && now -> child . find ( text [ i ]) == now -> child . end ()) now = now -> fail ; if ( now -> child . find ( text [ i ]) != now -> child . end ()) now = now -> child [ text [ i ]]; if ( now -> isEnd ) { answer . push_back ({ now -> p , i }); } } return answer ; } int main () { freopen ( “input.txt” , “r” , stdin ); int N ; cin >> N ; vector < string > patterns ( N ); for ( int i = 0 ; i < N ; ++ i ) cin >> patterns [ i ]; Trie * root = new Trie ; for ( int i = 0 ; i < N ; ++ i ) root -> Insert ( patterns [ i ]); root -> Fail (); string text ; cin >> text ; vector < pair < string , int >> answer = KMP ( text , root ); cout << text << "에서 검색하기" << ' ' ; for ( int i = 0 ; i < answer . size (); ++ i ) cout << "확인된 검색어 : " << answer [ i ]. first << ", 위치 : " << answer [ i ]. second << ' ' ; } 💎입력💎 검색어 👉 cache, he, chef, achy 텍스트 👉 cacachefcachy 💎출력💎 cacachefcachy에서 검색하기 확인된 검색어 : cache, 위치 : 6 확인된 검색어 : chef, 위치 : 7 확인된 검색어 : achy, 위치 : 12 1️⃣ 삽입 함수 (트라이 만들기) // Trie 트라이의 멤버 함수 // 📌 노드들의 성공 링크 결정 void Insert ( string pattern ) { Trie * now = this ; int m = pattern . length (); for ( int i = 0 ; i < m ; ++ i ) { if ( now -> child . find ( pattern [ i ]) == now -> child . end ()) now -> child [ pattern [ i ]] = new Trie ; now = now -> child [ pattern [ i ]]; if ( i == m – 1 ) { now -> p = pattern ; now -> isEnd = true ; } } }

가장 첫 번째로 해주어야할 작업은 검색어들을 트라이 트리에 삽입하는 것이다. 검색어의 마지막 글자엔 해당 검색어를 문자열 p 에 할당해주고 isEnd 를 True 로 바꾸었다. 진한 노란색은 isEnd 가 True인 단어의 끝을 의미한다.

원래 실제 메모리상으론 첫 번째 그림처럼 되는게 맞다. 그러나 아호 코라식 과정을 이해하는데 도움이 되기 위하여 두 번째 그림과 같이 해당 글자까지의 접두사로 노드를 표현하겠다.

2️⃣ 실패 함수 (트라이를 BFS 순회하며 노드마다 실패 링크 만들어주기)

// Trie 트라이의 멤버 함수 // 📌 노드들의 실패 링크 결정 void Fail () { // BFS + KMP Trie * root = this ; queue < Trie *> q ; q . push ( root ); while ( ! q . empty ()) { Trie * now = q . front (); // 방문 중인 노드 q . pop (); /* 자식 노드들 큐에 삽입 및 실패 링크 만들어주기 */ for ( auto & ch : now -> child ) { Trie * next = ch . second ; // 자식 노드 (now 의 자식 next) // 부모(now)가 루트 노드라면 실패 링크는 루트로 한다. // 첫 문자부터 불일치였다면 걸칠 수 있는게 없기 때문이다. if ( now == root ) next -> fail = root ; // 부모(now)가 루트 노드가 아니라면 else { Trie * prev = now -> fail ; // 부모 노드(= 이전 문자)의 실패 링크! 현재 노드(next) 까지 도달 했다는 것은 부모 노드(= 이전 문자)까진 일치했었다는 뜻이다. // 부모의 실패 링크에 현재 문자(next)가 자식 노드로 연결되지 않았다면, 즉 자식으로 없다면! 혹시 그 실패 링크가 루트 노드가 되거나 현재 문자를 자식으로 둔 노드를 찾을 떄까지 실패 링크를 타고 타고 올라간다. // 접미사 = 접두사인 타 검색어의 접두사를 찾을 때까지 올라감 // 타고 타고 올라갈 수록 접미사 = 접두사의 길이는 짧아질 수 밖에 없다. while ( prev != root && prev -> child . find ( ch . first ) == prev -> child . end ()) prev = prev -> fail ; // 현재 노드(next)의 실패링크를 결정한 실패링크의 자식 노드로 연결 if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ; } // che 의 실패링크가 he 라면, 근데 he 가 완전한 단어의 모습이라면! chef 의 che 또한 isEnd 가 true 가 될 수 있다. che 에서 불일치가 발생하더라도 그건 완전한 검색어 he 로도 걸칠 수 있기 때문이다. if ( next -> fail -> isEnd ) next -> isEnd = true ; q . push ( next ); } } }

BFS 순회

회색 별표 : 현재 방문 중인 노드 now (= 현재 노드인 next 의 부모)

(= 현재 노드인 의 부모) 노란 화살표 : 성공 링크

주황 화살표 : 실패 링크 볼드체는 현재 예약 중인 노드 next 에게 방금 만들어준 실패 링크

if ( now == root ) next -> fail = root ;

“a” 에서 불일치가 발생한다면?

부모가 루트이기 때문에 실패 링크는 루트로 한다. 이전 문자가 하나도 없기 때문에 이전 문자에서 접두사 = 접미사를 찾을 수 없어 처음부터 찾도록 실패시 트라이의 루트로 돌아가도록 한다.

if ( now == root ) next -> fail = root ;

“c” 에서 불일치가 발생한다면?

부모가 루트이기 때문에 실패 링크는 루트로 한다. 이전 문자가 하나도 없기 때문에 이전 문자에서 접두사 = 접미사를 찾을 수 없어 처음부터 찾도록 실패시 트라이의 루트로 돌아가도록 한다.

if ( now == root ) next -> fail = root ;

“h” 에서 불일치가 발생한다면?

부모가 루트이기 때문에 실패 링크는 루트로 한다. 이전 문자가 하나도 없기 때문에 이전 문자에서 접두사 = 접미사를 찾을 수 없어 처음부터 찾도록 실패시 트라이의 루트로 돌아가도록 한다.

“ac” 의 “c” 에서 불일치가 발생한다면 ?

“ac”의 가능한 접미사는 “c” 뿐이다.

if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “a” 의 실패 링크가 루트인데 루트의 자식으로 “c” 가 있다. 즉, “c” 로 시작하는 접두사가 있다는 의미이다. 실패시 이 “c” 로 이동하도록 한다.

“ca” 의 “a” 에서 불일치가 발생한다면 ?

“ca”의 가능한 접미사는 “a” 뿐이다.

if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “c” 의 실패 링크가 루트인데 루트의 자식으로 “a” 가 있다. 즉, “a” 로 시작하는 접두사가 있다는 의미이다. 실패시 이 “a” 로 이동하도록 한다.

“ch” 의 “h” 에서 불일치가 발생한다면 ?

“ch”의 가능한 접미사는 “h” 뿐이다.

if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “c” 의 실패 링크가 루트인데 루트의 자식으로 “h” 가 있다. 즉, “h” 로 시작하는 접두사가 있다는 의미이다. 실패시 이 “h” 로 이동하도록 한다.

“he” 의 “e” 에서 불일치가 발생한다면 ?

“he”의 가능한 접미사는 “e” 뿐이다.

next -> fail = prev ;

부모인 “h” 의 실패 링크가 루트인데 루트의 자식으로 “e” 가 없다. 즉, “e” 로 시작하는 접두사가 없다는 의미이다. 부모 실패 링크가 루트이니 while 에도 걸리지 않고, 부모 실패링크의 자식으로 “e” 가 없으니 if 문에도 걸리지 않는다.

부모의 실패 링크인 루트가 그대로 할당 된다. “he” 의 “e” 에서 불일치가 발생한다면 “he” 보다 짧은 것 중 “e” 로 시작할 수 있는게 없기 때문에 루트로 향한다.

“ach” 의 “h” 에서 불일치가 발생한다면 ?

“ach” 의 가능한 접미사는 “h”, “ch” 가 있다. (길이가 긴게 선택될 수록 좋다. 현재 노드와 가까운 실패링크일 수록 길이가 길다.)

if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “ac” 의 실패 링크인 “c”의 자식으로 “h” 가 있다. 즉, “ch” 로 시작하는 접두사가 있다는 의미이다. 실패시 이 “ch” 로 이동하도록 한다.

“cac” 의 “c” 에서 불일치가 발생한다면 ?

“cac” 의 가능한 접미사는 “c”, “ac” 가 있다. (길이가 긴게 선택될 수록 좋다. 현재 노드와 가까운 실패링크일 수록 길이가 길다.)

if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “ca” 의 실패 링크인 “a”의 자식으로 “c” 가 있다. 즉, “ac” 로 시작하는 접두사가 있다는 의미이다. 실패시 이 “ac” 로 이동하도록 한다.

“che” 의 “e” 에서 불일치가 발생한다면 ?

“che” 의 가능한 접미사는 “e”, “he” 가 있다. (길이가 긴게 선택될 수록 좋다. 현재 노드와 가까운 실패링크일 수록 길이가 길다.)

if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “ch” 의 실패 링크인 “h”의 자식으로 “he” 가 있다. 즉, “he” 로 시작하는 접두사가 있다는 의미이다. 실패시 이 “he” 로 이동하도록 한다.

if ( next -> fail -> isEnd ) next -> isEnd = true ;

“che” 의 실패링크인 “he” 는 단어의 끝이다. 즉, “che” 에 “he” 검색어가 포함되어 있다는 것이다. 따라서 “che” 의 isEnd 도 True 로 체크를 해준다. (진한 노란색으로 색 바꿔줌)

“he” 의 자식은 아무것도 없기 때문에 for문 예약 작업 하지 않고 넘어간다.

“achy” 의 “y” 에서 불일치가 발생한다면 ?

“achy” 의 가능한 접미사는 “y”, “hy”, “chy” 가 있다. (길이가 긴게 선택될 수록 좋다. 현재 노드와 가까운 실패링크일 수록 길이가 길다.)

while ( prev != root && prev -> child . find ( ch . first ) == prev -> child . end ()) prev = prev -> fail ; // if 는 false next -> fail = prev ;

부모인 “ach” 의 실패 링크인 “ch”의 자식으로 “y” 가 없다. 👉 “chy” 로 걸칠 수 있는 접두사 없음 부모의 실패링크가 루트도 아니기 때문에 while 문을 돌며 “hy”, “y” 로 걸칠 수 있을지 각각 검사하러 간다. “ch” 의 실패 링크인 “h”의 자식으로 “y” 가 없다. “h” 의 실패 링크인 루트의 자식으로 “y” 가 없다. 결국 “hy”, “y” 접두사도 존재하지 않기에 “ach” 의 실패 링크는 루트가 된다.

“cach” 의 “h” 에서 불일치가 발생한다면 ?

“cach” 의 가능한 접미사는 “h”, “ch”, “ach” 가 있다. (길이가 긴게 선택될 수록 좋다. 현재 노드와 가까운 실패링크일 수록 길이가 길다.)

if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “cac” 의 실패 링크인 “ac”의 자식으로 “ach” 가 있다. 즉, “ach” 로 시작하는 접두사가 있다는 의미이다. 실패시 이 “ach” 로 이동하도록 한다.

“chef” 의 “f” 에서 불일치가 발생한다면 ?

“chef” 의 가능한 접미사는 “f”, “ef”, “hef” 가 있다. (길이가 긴게 선택될 수록 좋다. 현재 노드와 가까운 실패링크일 수록 길이가 길다.)

while ( prev != root && prev -> child . find ( ch . first ) == prev -> child . end ()) prev = prev -> fail ; // if 문은 false next -> fail = prev ;

부모인 “che” 의 실패 링크인 “he”의 자식으로 “y” 가 없다. 👉 “hef” 로 걸칠 수 있는 접두사 없음 부모의 실패링크가 루트도 아니기 때문에 while 문을 돌며 “ef”, “f” 로 걸칠 수 있을지 각각 검사하러 간다. “he” 의 실패 링크인 루트의 자식으로 “f” 가 없다. 결국 “ef”, “f” 접두사도 존재하지 않기에 “chef” 의 실패 링크는 루트가 된다.

“achy” 의 자식은 아무것도 없기 때문에 for문 예약 작업 하지 않고 넘어간다.

“cache” 의 “e” 에서 불일치가 발생한다면 ?

“cache” 의 가능한 접미사는 “e”, “he”, “che”, “ache” 가 있다. (길이가 긴게 선택될 수록 좋다. 현재 노드와 가까운 실패링크일 수록 길이가 길다.)

while ( prev != root && prev -> child . find ( ch . first ) == prev -> child . end ()) prev = prev -> fail ; if ( prev -> child . find ( ch . first ) != prev -> child . end ()) // if 도 True 가 됨! prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “cach” 의 실패 링크인 “ach”의 자식으로 “e” 가 없다. 👉 “ache” 로 걸칠 수 있는 접두사 없음 부모의 실패링크가 루트도 아니기 때문에 while 문을 돌며 “che”, “he”, “e” 로 걸칠 수 있을지 각각 검사하러 간다. “ach” 의 실패 링크인 “ch”의 자식으로 “e” 가 있다. (while문 종료) 따라서 “cache” 의 실패 링크는 “che” 가 된다.

“chef” 의 자식은 아무것도 없기 때문에 for문 예약 작업 하지 않고 넘어간다.

“cache” 의 자식은 아무것도 없기 때문에 for문 예약 작업 하지 않고 넘어간다.

3️⃣ 검색 함수 (KMP 알고리즘 방식으로 트라이에서 검색)

// 전역 함수 vector < pair < string , int >> KMP ( string text , Trie * root ) { Trie * now = root ; int n = text . length (); vector < pair < string , int >> answer ; for ( int i = 0 ; i < n ; ++ i ) { // 텍스트 글자가 현재 방문 중인 노드(검색어 글자)와 일치하지 않는다면 👉 일치하는게 하나도 없는 상태(now == root)가 되거나 일치할 때까지 실패 링크 타기 while ( now != root && now -> child . find ( text [ i ]) == now -> child . end ()) now = now -> fail ; // 일치한다면 성공링크 타고 내려가기 if ( now -> child . find ( text [ i ]) != now -> child . end ()) now = now -> child [ text [ i ]]; // 검색어를 찾았다면 if ( now -> isEnd ) { answer . push_back ({ now -> p , i }); // 그 문자열과 위치를 answer 에 담도록 하였다. } } return answer ; }

일치할 경우 “성공 링크”를 타고 내려간다. (노란 화살표)

일치하지 않을 경우, 일치할 때까지 (혹은 루트가 될 때까지) “실패 링크”를 타고 올라간다. (주황 화살표)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : 루트

루트의 성공 링크 (첫 번째 if) 루트의 자식인 c 로 이동

아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : c

c 의 성공 링크 (첫 번째 if) c 의 자식인 ca 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : ca

ca 의 성공 링크 (첫 번째 if) ca 의 자식인 cac 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : cac

실패 링크 (while) cac 의 자식엔 caca 가 없다. 👉 cac 의 실패 링크인 ac 로 이동 ac 의 자식엔 aca 가 없다. 👉 ac 의 실패 링크인 c 로 이동 c 의 자식엔 ca 가 있다.

c 의 성공 링크 (첫 번째 if) c 의 자식인 ca 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : ca

ca 의 성공 링크 (첫 번째 if) ca 의 자식인 cac 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : cac

cac 의 성공 링크 (첫 번째 if) cac 의 자식인 cach 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : cach

cach 의 성공 링크 (첫 번째 if) cach 의 자식인 cache 로 이동

의 성공 링크 (첫 번째 if) 검색어 찾음 ! ! ! (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : cache

실패 링크 (while) cache 의 자식엔 cachef 가 없다. 👉 cache 의 실패 링크인 che 로 이동 che 의 자식엔 chef 가 있다.

che 의 성공 링크 (첫 번째 if) che 의 자식인 chef 로 이동

의 성공 링크 (첫 번째 if) 검색어 찾음 ! ! ! (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : chef

실패 링크 (while) chef 의 자식엔 chefc 가 없다. 👉 chef 의 실패 링크인 루트로 이동

루트의 성공 링크 (첫 번째 if) 루트의 자식인 c 로 이동

아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : c

c 의 성공 링크 (첫 번째 if) c 의 자식인 ca 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : ca

ca 의 성공 링크 (첫 번째 if) ca 의 자식인 cac 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : cac

cac 의 성공 링크 (첫 번째 if) cac 의 자식인 cach 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : cach

실패 링크 (while) cach 의 자식엔 cachy 가 없다. 👉 cach 의 실패 링크인 ach 로 이동 ach 의 자식엔 achy 가 있다.

ach 의 성공 링크 (첫 번째 if) ach 의 자식인 achy 로 이동

의 성공 링크 (첫 번째 if) 검색어 찾음 ! ! ! (두 번째 if)

이렇게 하여 텍스트를 모두 순회하였고 탐색을 종료 🙂

📌 Reference

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

[알고리즘] 다중 문자열 검색 아호 코라식(Aho-Corasick) 알고리즘 정리 (Java)

아호 코라식(Aho-Corasick) 알고리즘

아호 코라식 알고리즘(Aho–Corasick string matching algorithm)은 Alfred V. Aho와 Margaret J. Corasick이 고안한 문자열 검색 알고리즘(매칭 알고리즘)이다. (위키 참고)

패턴 1개를 탐색하는 매칭 알고리즘은 선형 시간에 구현됨을 KMP 등 여러 알고리즘을 통하여 증명되었다. 하지만 패턴 집합에 대하여 이러한 알고리즘을 수행하게 되면 패턴 개수에 비례하여 그 속도가 느려지게 된다.

m = 모든 패턴들의 길이 합, p = 패턴수, n = text 크기

즉 , O(m + p*n)의 시간 복잡도를 가지게 된다.

하지만 아호 코라식 알고리즘을 이용하면 O (m + p + n)의 시간복잡도로 패턴 집하에 대하여 패턴 길이와 텍스트의 선형 시간 탐색에 처리할 수 있게 된다. 이에 대한 분석은 모든 구현을 마친뒤 마지막에 한 번 더 다룰 것이다.

다중 문자열 검색

여러 패턴 집합을 구하는 문제를 다중 문자열 검색 문제라고 한다.

KMP는 1개 패턴 문자열을 매칭 시키는 문제를 해결했다면

다중 문자열 검색은 짚더미(parent): “CACACHEFCACHY” , 바늘 문자열(pattern[]): { “CACHE”, “HE”, “CHEF”, “ACHY” } 이 있다고 하면 각 바늘 문자열들의 출현 위치를 모두 찾아 해결해야 한다.

있다고 하면 각 바늘 문자열들의 출현 위치를 모두 찾아 해결해야 한다. KMP 알고리즘을 사용하면 위에서 말했던 바와 같이 패턴 수(바늘 문자열 갯수)만큼 순회해야 한다.

1. KMP 알고리즘으로 접근하기

KMP 알고리즘의 동작원리를 돌이켜 보자. KMP 알고리즘은 전처리 과정에서 부분 매칭 테이블을 계산하는데, 이것은 바늘 문자열(pattern)의 각 접두사마다 이 접두사의 접두사도 되고 접미사도 되는 문자열의 최대 길이를 계산해 둔 것이다.

예를 들어 “CACHE”를 찾는데 첫 세 글자인 “CAC가 대응되고 실패했다고 하자. 이때 대응된 부분의 접두사도 되고 접미사도 되는 최대 문자열은 “C”이다.

따라서 KMP 알고리즘은 세 글자 대신 한 글자가 대응되었다고 생각하고 다음 글자가 A인지를 확인한다. 이와 같은 과정이 있기 때문에 “CACACHE” 같은 문자열에서 “CACHE”를 찾을 때에도 parent의 각 문자를 한 번만 보고 모든 출현 위치를 찾아낼 수 있다.

대응에 실패했을 때 어디로 가서 검색을 계속해야 할지 알려준다는 의미에서 이와 같은 정보를 **실패 함수(failure function)**라고도 부른다.

바늘 문자열(pattern)의 실패 함수 정보를 그림으로 표현해보자. “CACHE”, “HE”, “CHEF”, “ACHY”에 대해 KMP 알고리즘이 생성하는 실패 함수 정보를 나타낸다.

오른쪽으로 가는 실선 화살표는 해당 상태에서 대응이 성공했을 경우 움직일 상태를 의미하고,

왼쪽으로 가는 점선 화살표는 실패 함수를 나타낸다.

예를 들어 “CAC”상태에 있는 다음 글자가 H라면 “CACH” 상태로 갈 수 있지만, 해당 글자가 H가 아니라면 “C”로 돌아가 다음 글자가 A인지 비교해야 한다.

[KMP 알고리즘의 전처리 결과 시뮬레이션]

KMP 시뮬레이션

2. 트라이(Trie) 자료구조 적용하기

트라이는 집합에 포함된 문자열을 찾는 탐색 자료 구조이다. 트라이에 포함된 문자열들이 접두사를 공유할 경우, 이 접두사들은 같은 노드에 대응된다는 점을 이용해 탐색 공간을 줄이는 알고리즘을 설계할 수 있다.

위 그림의 문제점은 중복된 데이터가 너무 많다는 것이다. 이 모든 접두사들을 트라이로 그려보면 다음 그림과 같은 자료구조를 얻을 수 있다. 겹치던 상태들이 깨끗하게 정리되었다.

[문제에서 찾는 패턴을 모두 포함하는 트라이]

트라이 자료 패턴

실패 함수를 다음과 같이 다시 정의하자.

failure(s) = s 의 접미사이면서 트라이에 포함된 가장 긴 문자열까지 가는 화살표

이와 같은 정의를 이용해 위의 트라이 자료구조 그림에서 각 노드의 실패 함수를 계산하면 다음 그림과 같은 상태로 나아간다. 이와 같은 실패 함수를 전처리 과정에서 만든 뒤, 짚더미 문자열(parent)의 글자를 순회하면서 트라이의 상태들을 서로 오가면 모든 바늘 문자열들에 대해 동시에 KMP 알고리즘을 수행하는 것과 같은 효과를 얻을 수 있다.

[트라이 상에서 계산한 실패 함수]

트라이 실패함수

이 알고리즘을 바로 아호-코라식(Aho-Corasick) 문자열 검색 알고리즘이라고 부른다. 아호-코라식 알고리즘은 긴 문서에서 많은 문자열을 동시에 찾아야 하는 검색 엔진 등에서 특히 유용하게 사용된다. 이제 아호-코라식 알고리즘이 실패 함수를 계산하는 방법과 실제 문자열을 탐색하는 과정을 구현해보자.

따라서, 아호-코라식 알고리즘은 (1) 패턴 1개를 탐색하는 문자열 매칭 알고리즘 에 (2) 집합에 포함된 문자열을 탐색하는 자료구조 를 합성한 것이라고 보면 된다.

아호-코라식(Aho-Corasick) 문자열 검색 알고리즘 구현하기

1. 실패 함수의 계산

아호-코라식 알고리즘을 사용하기 위해서는 트라이 자료구조에서 다음과 같은 정보를 추가적으로 가지고 있어야 한다.

실패 링크(failure link) 는 이 노드에서의 실패 함수 값으로, 이 노드에서 다음 글자가 대응하는 데 실패했을 때 다음으로 가서 시도해야 할 노드의 포인터 이다. 위 그림에서 점선 화살표들이 실패 링크를 나타낸다.

는 이 노드에서의 실패 함수 값으로, 이다. 위 그림에서 점선 화살표들이 실패 링크를 나타낸다. 출력 문자열 목록 은 각 노드에 도달했을 때 어떤 바늘 문자열(pattern)들을 발견하게 되는지를 저장 한다. 한 바늘 문자열(pattern)이 다른 바늘 문자열의 부분 문자열인 경우, 해당 바늘 문자열이 종료되는 노드 외의 장소에서도 문자열을 발견할 수 있기 때문에 별도의 목록이 필요하다. 예를 들어 세 개의 바늘 문자열 ABC, B, BC가 있다면 상태 AB에 도달했을 때는 바늘 문자열 B를, 상태 ABC에 도달했을 때는 바늘 문자열 ABC와 BC를 발견할 수 있다.

은 각 노드에 도달했을 때 한다.

2. 실패 링크 만들기

출력 문자열 목록은 실패 링크가 있을 경우 쉽게 계산할 수 있으므로, 우선은 각 노드의 실패 링크를 형성하는데 집중하자.

주어진 트라이 노드의 실패 링크를 계산하는 가장 간단한 방법은 해당 노드에 대응된 문자열의 모든 접미사들을 하나하나 시도하면서 이 중 트라이에 포함되어 있는 첫 번째 문자열을 찾는 것이다.

이 방식은 아주 비효율적이지만 트라이 크기가 그리 크지 않다면 써먹을 수는 있다.

모든 접미사들을 시도하는 방법보다 더 효율적인 방식이 있으니 이를 공부해보자.

2-1. 부모 노드의 실패 링크를 이용해 자식 노드의 실패 링크를 쉽게 알아내기

보다 빠르게 실패 링크를 계산하는 중요한 단서는 부모 노드의 실패 링크를 이용해 자식 노드의 실패 링크를 쉽게 알아낼 수 있다는 것이다. “CAC”와 “CACH”를 예로 들어보자. 두 노드의 실패 링크인 “AC”와 “ACH”또한 서로 부모의 자손 사이임을 알 수있다. 왜?

어떤 문자열 A와 그 뒤에 글자 x를 붙인 문자열 Ax가 트라이 상에서 부모 자식 관계라 하자.

Ax의 실패 링크가 루트로 가지 않는 경우, 실패 링크를 따라가 만나는 문자열의 마지막 문자는 항상 x이다. 따라서 실패 링크를 따라가 만나는 문자열의 마지막 문자는 항상 x이다. 따라서 실패 링크를 따라가 만나는 문자열의 마지막 문자는 항상 x이다.

따라서 실패 링크를 따라가 만난 문자열을 Bx라고 쓸 수 있다. 여기서 x를 떼어낸 B를 생각해 보면 그림에서 볼 수 있듯이 B는 항상 A의 접미사가 되어야 한다.

따라서 부모 노드인 A의 실패 연결에 B에 x를 붙인 자손 Bx가 있는지를 확인해 Bx가 Ax의 실패 링크가 됨을 쉽게 알 수 있다.

부모 노드의 실패 링크를 이용해 자식 노드의 실패 링크를 쉽게 알아내기

2-2. 부모 노드의 실패 링크로 찾을 수 없을 경우 부모의 부모의 실패링크를 계속해서 탐색하기

물론 1번 규칙만으로 모든 실패 링크를 찾을 수 없다. “CACH”와 “CACHE”의 관계를 살펴보자.

“CACH”의 실패 링크인 “ACH”에는 E로 표시된 간선이 없기 때문에 이 규칙으로는 “CACHE”의 실패 연결을 찾을 수 없다.

이때 우리가 할 일은 “ACH”의 실패 링크를 한 번 더 따라가는 것이다. 이렇게 실패 링크를 따라가면 “CACH”의 접미사들을 긴 것부터 순회하게 된다.

이 과정에서 처음으로 E로 표시된 간선이 있는 노드는 “CH”이므로, 이 간선을 따라가서 “CHE”를 얻으면 된다. 만약 실패 연결을 따라 루트로 돌아갈 때까지 다음 글자로 표시된 간선을 찾을 수 없다면 이 노드의 실패 링크는 트라이의 루트가 된다.

부모의 부모의 실패링크를 계속해서 탐색하기

이제 마지막으로 실패 링크를 계산할 순서를 설계하면 된다. 한 노드의 실패 링크를 계산하기 위해서는 그 부모 노드에서 실패 링크를 따라가 만날 수 있는 모든 노드들에 대해 실패 링크를 먼저 계산해야 하기 때문이다.

단순하게 재귀호출을 이용한 DFS로 트라이의 노드들을 순회하면서, 방문 순서대로 실패 연결을 계산해서는 이 조건을 만족시킬 수 없다.

이때 부모의 실패 연결은 알 수 있지만 부모에서 실패 링크를 따라간 노드의 실패 링크를 모를 수 있기 때문이다.

2-3. BFS 탐색 으로 구현하기

이 문제를 해결하는 방법은 실패 링크를 따라갔을 때 만나는 문자열은 원래 노드의 문자열보다 항상 짧다는 데 주목하는 것이다.

루트에서부터 시작해서 깊이가 낮은 노드들부터 순서대로 실패 링크를 계산하면, 항상 현재 노드보다 짧은 문자열을 갖는 모든 노드들에 대해 실패 링크를 계산한 뒤이기 때문에 우리에게 필요한 노드들의 실패 링크를 모두 가지고 있을 것이다.

따라서 실패 링크를 만드는 computeFailFunc()는 너비 우선 탐색인 BFS를 이용하여 구현한다.

public void computeFailFunc() { Queue q = new LinkedList<>(); this.fail = this; // this : root q.add(this); while(!q.isEmpty()) { TrieNode cur = q.poll(); for(int i=0; i<26; i++) { // 알파벳만 포함되어있는 문자열 탐색이므로 26으로 설정 char c = (char)(i+97); TrieNode nxt = cur.childNode.get(c); if(nxt ==null) continue; // 1레벨 노드의 실패 연결은 항상 루트 if(cur == this) { nxt.fail = this; }else { //아닌 경우 부모의 실패 연결을 따라가면서 실패 연결을 찾는다. TrieNode t = cur.fail; // t: 부모 실패노드 // 2. 부모 실패노드의 자식노드가 c가 아닌 경우 실패노드 거슬러 탐색하기 while(t!=this && t.childNode.get(c) == null) { t = t.fail; } // 1. 부모 실패노드의 자식노드가 c인 경우 실패링크 연결 if(t.childNode.get(c) != null) { t = t.childNode.get(c); } nxt.fail = t; } // 이 위치에서 끝나는 바늘 문자열이 있으면 추가한다. (출력 링크) if(nxt.fail.output) { nxt.output =true; } q.add(nxt); } } } 2-4. 출력 문자열 목록을 계산하는 부분 (output) 실패 링크를 계산하고 나면 해당 위치에서 출력 문자열 목록을 복사해 온 뒤, 현재 위치에서 끝나는 문자열을 추가한다. 이와 같은 방법으로 출력 문자열 목록을 계산할 수 있는 이유는, 현재 노드에 대응되는 문자열의 접미사가 트라이에 포함된 어떤 문자열과 같다면, 이 노드에서 실패 링크를 따라가다 보면 이 문자열을 반드시 찾을 수 있기 때문이다. "CACHE"에서 실패 링크를 따라가다 보면 "HE"를 찾을 수 있는 것처럼 말이다. 위 예제에서 주어진 그래프에는 "CHE"가 새롭게 출력 문자열 목록에 추가된다. 출력 문자열 목록 추가 3. 실제 탐색 과정의 구현 이와 같이 실패 링크를 계산해 두고 나면 실제 탐색 과정은 KMP 알고리즘과 거의 다를 것이 없다. 몇 글자나 대응되었는지를 나타내는 matched 변수 → 현재 상태를 나타내는 trieNode로 바뀌고, 부분 일치 테이블 참조 대신 → 실패 링크를 참조한다. public boolean ahoCorasick(String word) { TrieNode trieNode = this; // 짚더미 문자열 탐색 (0~word.length()-1) for(int i=0; i

Aho-Corasick Multiple Pattern Matching Algorithm

https://www.slideshare.net/ssuser81b91b/ahocorasick-algorithm

문자열 S와 여러 개의 문자열 T가 주어졌을 때, T에 있는 문자열 중 하나와 S가 매칭이 되는 지를 계산 할 수 있는 알고리즘이다. 선형 시간에 작동한다.

Aho Corasick Algorithm을 알기 위해서는 KMP 알고리즘과 트라이에 대한 이해가 필요하다. KMP 알고리즘에 대한 koosaga.com의 설명

아호 코라식 알고리즘을 한 문장으로 설명하면, KMP에서 사용하는 Failure function을 트라이에 확장시키는 것. 딱 이것으로 끝난다. 스텝도 비슷하다.

* 1. 트라이가 주어졌을 때 트라이에서 Failure function (Failure link나 Suffix link라고도 부른다) 을 계산하는 것

* 2. Failure function이 계산된 트라이에서 문자열을 찾는 것

1번이 전처리 과정이므로 당연히 1번이 2번보다 선행되는 과정이다. 하지만 설명의 편의를 위해 2번을 먼저 설명한다.

2. Failure function이 계산된 트라이에서 문자열을 찾는 것

먼저, 트라이에다가 T에 있는 모든 문자열을 저장하는 과정이 필요할 것이다. 문자열을 저장하면서, 마지막 문자가 가리키는 노드에 체크를 해놓자. (output check라고 부르겠다. 보통 output link라고 부르는 것 같은데, 혼란을 주는 이름인 것 같아서 이 설명에서는 새로운 단어를 사용한다.) 이는 “이 노드에 도달했다면 한 문자열과 매칭이 됐다”는 것을 표시해 준다. 당연히 문자열을 찾으면서 알아야 할 정보이기도 하다.

트라이 각 노드의 Failure function은 다음과 같이 정의된다.

“루트가 아닌 각 노드 v에 대해서, 루트 -> w로 가는 경로가, 루트 -> v로 가는 경로의 suffix이며, w != v이고, 그러한 것이 여러 개 있다면 그 중 가장 긴 것”

이를 사용하면 KMP와 동일한 방법으로 트라이를 따라갈 수 있다. 끝점을 늘려가면서, 만약에 해당 문자열을 포함하는 트라이 상 경로가 있다면 그 곳으로 움직이고, 그렇지 않다면 Failure function을 통해서 skip을 반복하는 방식이다. 이를 반복하면 트라이 상 깊이를 최대로 유지하면서 계속 탐색을 진행할 것이다.

그렇다면, 현재 트라이 상 어떠한 노드 v에 있을 때, 루트 -> v로 가는 경로의 substring 중 T에 속한 문자열이 있는 지를 알 수 있을까? 단순하게 생각하면 v의 output check 여부에 따라서 판정할 수 있을 것 같지만, 트라이 상 깊이를 최대로 유지했기 때문에, 루트 -> v로 가는 경로의 suffix 중에서 T에 속한 문자열이 있다면 이를 찾지 못하게 된다.

이를 Naive하게 해결하는 방법은, 각각의 노드에 도달했을 때마다 Failure function을 타고 올라가면서, 그 중 output check가 있는 노드의 존재를 확인하는 것이다. 이 방법은 전처리를 통해서 시간 복잡도를 줄일 수 있는데, failure function 역시 트리의 형태를 띄므로 (각각의 노드가 깊이가 작은 노드 정확히 한개를 부모로 가지고 있으며, 모든 노드에서 루트로 도달 가능하다.) failure function tree에서 자식으로 dfs나 bfs로 output check를 뿌려주면, 굳이 부모를 타고 가지 않아도 이미 부모에서 뿌려준 값이 있기 때문에 상수 시간에 판정이 가능하다.

1. Failure function을 계산하는 것

Failure function을 계산하는 것은 너비 우선 탐색을 통해서 할 수 있다. KMP랑 비슷한 방법인데, 루트에서의 깊이가 1인 노드들은 failure function이 자명하다 (루트). BFS를 하면 깊이 순으로 트리를 탐색할 수 있다. 루트에서의 깊이가 2인 노드들, 3인 노드들을 순서대로 탐색한다면, 해당 노드보다 깊이가 낮은 노드들은 이미 다 계산이 완료되어 있기 때문에 failure function을 계산할 수 있다. 고로, 부모의 failure function을 안다면 이를 토대로 새로운 failure function을 계산할 수 있다.

이 과정에서 BFS를 사용하기 때문에, 여기서 한 줄의 코드를 추가하는 것만으로도 output check 데이터를 뿌려줄 수 있다. 고로 위에서 output check를 따로 코딩해야 하는 번거로움이 사라진다.

코드 : https://gist.github.com/koosaga/96e5de4ccb99616f9bc3a760ec964cbe

연습 문제가 여러개 있다.

https://www.acmicpc.net/problem/9250

https://www.acmicpc.net/problem/10256

https://www.acmicpc.net/problem/5905

풀이 힌트

접기 KMP에서 얘기했듯이 아호 코라식 역시 일종의 유한 상태 오토마타를 만든다. DP 상태에 트라이 노드를 넣으면 된다

접기

http://codeforces.com/contest/163/problem/E

풀이 힌트

접기 output check가 동적으로 바뀌는 문제이다. 이 경우에는 전처리가 힘드니 루트를 일일히 뒤져보는 것을 생각해보면, 결국 트리에서 쿼리를 하는 문제가 되는데 * 쿼리 1 : 노드를 마킹하거나 마킹 해제 * 쿼리 2 : 해당 노드의 조상들 중 마킹된 노드가 있는지 판별

자료 구조를 사용해서 해결하면 된다. 접기

도움이 될 수 있는 다른 글도 소개한다 : http://blog.myungwoo.kr/101

아호코라식 다중 패턴 매칭(Aho-Corasick)

아호 코라식(Aho-chorasick)

여러 문자열 패턴이 있고, 특정 문자열에 어떤 패턴이 어디에 존재하는지 확인하고 싶을 때 쓰는 알고리즘입니다.

기술적으로는 prefix와 suffix를 가지고 노는 문자열 탐색 알고리즘이라고 말하고 싶네요. KMP도 마찬가지지만 이 알고리즘 역시 매칭 실패했을 때 지금까지 사용한 데이터를 그대로 활용해서 효율적으로 탐색하고 싶어합니다. 아시다시피 그 동작을 실패 함수(Failure function)라고 합니다.

[사전 지식]

* 트라이(trie) – prefix 문자열을 저장하는 자료구조. 만약 검색 대상 문자열이 패턴과 정확히 일치해야만 한다면 적절한 자료구조입니다.

* BFS – 아호코라식 자료구조를 동적으로 건설해나가는데, 여기서 실패함수 구조에 의해 BFS를 통해 완성하는 것이 적절합니다.

[Aho-chorasick 노드 데이터]

아호코라식은 트라이 자료구조를 사용합니다. 트라이를 구성할 때 몇 가지 기본적인 데이터를 가집니다.

struct _trie { _trie *fail; // 실패했을 때 찾아가는 노드 포인터(주소, 인덱스 등) _trie *child[TRIE_CHILD_SIZE]; // 트라이 자식 노드 vector words; // 현재 노드를 끝으로 하는 패턴의 집합 };

[실패 함수(다이나믹 프로그래밍)]

실패 함수는 특정 위치에서 매칭 실패 했을 때, 가장 효율적인 위치를 뜻합니다. 여기서는 그 위치는 노드가 됩니다.

[효율적?] 아호코라식은 패턴 A의 부분문자열 suffix가 패턴 B의 prefix임을 이용합니다. 트라이 특정 노드 X에서 실패 함수는 루트부터 X까지 사용된 문자를 나열하면 X에 해당하는 문자열 Xs가 나옵니다. Xs의 suffix 중 패턴들의 prefix와 매칭되는 것들 중 가장 긴 것을 가져옵니다. 이 때 이 가장 긴 prefix에 해당하는 노드가 실패 함수가 가리키는 노드가 됩니다.

※ 패턴의 prefix는 트라이 루트부터 탐색을 의미한다.

간단하게 길이 1짜리를 생각해봅시다. 여기에 해당하는 노드들의 실패함수는 루트가 됩니다. 그 중 한 노드를 A라고 하면, A까지는 매칭이 됐으나, A 이후에 매칭이 없다면 어디로 돌아가야할까요? 한글자에선 suffix나 prefix 모두 같기 때문에 의미가 없습니다.

길이 2를 생각해봅시다. 현재 노드 C까지 x, y 두 문자를 타고 왔다고 보는 겁니다. 여기서 루트의 y에 해당하는 자식 노드 D가 존재해야 실패 함수를 D로 지정할 수 있습니다. 만약에 존재하지 않는다면 노드 C의 실패 함수는 루트와 연결되어 다시 처음부터 탐색하도록 유도됩니다.

일반화를 위해 길이 k를 생각해봅시다. 앞에서 말한 것처럼 우린 현재 노드 X까지 왔을 때, 가장 긴 prefix에 해당하는 노드를 가져오고 싶습니다. 가장 긴 prefix라고 함은 이미 앞에서 계산되지 않았을까요? 가령 X까지 abcdef 문자열이 구성될 때 X의 부모노드 Y까지의 문자열은 abcde임이 틀림없습니다. 만약 Y의 실패함수가 루트가 아닌 cde에 해당하는 노드 T를 가리킬 때, T의 자식 중 ‘f’ 문자에 해당하는 노드가 있다면 그 노드가 곧 X의 실패함수임을 알 수 있습니다. 따라서 길이 k에 해당하는 노드의 실패함수는 바로 위 부모 노드의 실패함수를 활용합니다.

이렇게 진행하면 굳이 루트부터 재탐색하지 않고도 바로 구할 수 있습니다. 저장된 데이터를 재활용하여 사용하기 때문에 다이나믹이라고 말할 수 있겠습니다.

[아호코라식 건설]

현재 노드까지의 문자열 suffix와 루트부터의 prefix를 봐야하기 때문에 현재 노드의 depth가 prefix의 depth보다 짧을 이유가 없습니다. 따라서 depth를 같게끔 내려가는 구조인 BFS를 쓰면됩니다.

일반 트라이에서는 문자열 마지막에 해당하는 노드만 문자열 끝을 뜻합니다. 하지만 아호코라식에서는 문자열 중간에 있는 노드가 문자열 끝을 나타낼 수 있습니다. 이유는 (몇 번 말하는지 모르겠지만ㅠ) 노드까지의 해당하는 문자열의 suffix를 prefix로 재활용하는 구조를 생각해야합니다. 탐색 중 방문 노드가 X이고, X의 실패함수에 해당하는 노드 K가 패턴 그 자체라고 해봅시다. 즉, K까지의 문자열이 X까지의 문자열의 suffix인 경우를 말합니다. 따라서 X 노드를 방문할 때 패턴이 매칭했음을 나타내기 위해 실패함수 노드에서 패턴 정보를 가져옵니다.

void ahocorasick() { queue<_trie*> q; q.push(root); while (!q.empty()) { _trie* u = q.front(); q.pop(); for (int i = 0; i < TRIE_CHILD_SIZE; i++) if (u->child[i]) { _trie* nxt = u->child[i]; if (u == root) nxt->fail = u; else { _trie* k = u->fail; while (k != root && !k->child[i]) k = k->fail; if (k->child[i]) k = k->child[i]; nxt->fail = k; } // 실패함수에 해당하는 노드로부터 패턴 정보를 가져온다. nxt->words.insert(nxt->words.end(), nxt->fail->words.begin(), nxt->fail->words.end()); q.push(nxt); } } }

[탐색]

설명을 용이하게 하기 위해 아래처럼 용어 정리를 하겠습니다.

s: 탐색할 문자열

n: s의 길이

m: 패턴들의 길이 합

z: s에서 탐색된 패턴들의 수

s[i]: i번째 인덱스에 해당하는 문자

시간 복잡도: O(n + m + z)

[탐색 – prefix 매칭]

현재 노드에서 s[i]에 해당하는 문자와 같은 자식 노드가 있다면 문자가 존재한다고 볼 수 있습니다.

[탐색 – 미스 매칭]

현재 노드에서 s[i]에 해당하는 문자와 같은 자식 노드가 없다면 실패함수로 넘어가야합니다.

실패함수 구조상 s[i]에 해당하는 자식을 찾을 때까지 여러 차례 depth를 낮추며 접근해야할 필요가 있습니다. 전부 없다면 종착지는 루트가 됩니다.

예시 1)

p = “xyxyxy” 패턴이 있을 때, 이를 trie에 넣는 걸 생각해봅시다.

각 인덱스에 대해 실패함수를 적자면 아래 표와 같습니다.

i 0 1 2 3 4 5 fail (R) (R) A B ? ?

부모 노드로부터 실패 함수를 가져오기 때문에 결과 표는 아래와 같습니다. (A나 B가 아님을 확인)

i 0 1 2 3 4 5 fail (R) (R) A B C D

4 인덱스에 해당하는 노드 E의 실패함수는 노드 C와 연결됩니다. 이유는 더 범용성이 넓기 때문인데 곧바로 노드 A로 가버리면 노드 C 이후의 노드들을 이용해 탐색할 기회를 잃어버립니다. 반대로 C 이후의 노드들로 탐색했을 때 매칭이 되지 않더라도 실패함수를 이용해서 상위 노드로 올라갈 수 있습니다.

예시 2)

s = “xyxyxyb”

패턴 = [“xyxyxy”, “xyb”]

위 구조에서 탐색할 때, 노드 F에 문자 ‘b’에 해당하는 자식 노드가 없기 때문에 실패함수가 동작하는데, D노드로 이동합니다. D 노드에도 ‘b’에 해당하는 자식 노드가 없기 때문에 B노드로 이동합니다. 여기엔 ‘b’에 해당하는 노드 G가 존재하니 G로 이동합니다. 여기서 한 번만 실패 함수를 타고 올라가는 게 아니라 여러 번 타고 올라가야 함을 알 수 있습니다.

[탐색 – 패턴 매칭]

s에 포함된 패턴을 찾기 위해서는 트라이와 s를 동시에 순회하면서 패턴의 끝을 해당하는 데이터가 현재 노드에 존재하는지 확인하면 됩니다.

상황에 따라 패턴의 존재함을 저장할 수도 있고, 단어 인덱스 리스트를 저장할 수도 있고, 길이만 저장할 수도 있습니다. 문제를 잘 읽고 최적화합시다.

_trie* cur = root; for (i = 0; s[i]; i++) { int idx = getIndex(s[i]); while (cur != root && !cur->child[idx]) cur = cur->fail; if (cur->child[idx]) cur = cur->child[idx]; if(!cur->words.empty()) ;// do something }

문자열 매칭 알고리즘[3](트라이 & 아호 코라식)[String Searching Algorithm, Trie & Aho-Corasick]

KMP : 문자열 S가 있을 때, 패턴 P를 찾는 알고리즘

Trie : 문자열 N개가 있을 때, 문자열 S를 찾는 알고리즘

ex) 출석부에서 내 이름(full name) 찾기

Aho-corasick : 문자열 N개가 있을 때, 패턴 P를 찾는 알고리즘

ex)출석부에서 나랑 성이 같은 사람, 이름이 같은 사람을 찾기

코딩테스트 비중은 KMP보다 Trie가 더 높으며 Trie는 해시로 대처 할 수 있다고 함.

아호 코라식은 자주 나오는 문제는 아니다.

Trie

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85)

숫자 비교는 O(1)이지만

문자열 비교는 최대 O(길이)가 걸린다.

문자열 N개를 담고있는 BST에서 검색하는데 걸리는 시간은 O(lgN)이 아니고 O(길이*lgN)이다.

N개 문자열을 오름차순 정렬(길이의 최댓값 M) : NMlgN

트라이의 한 노드는 어떤 문자열의 접두사를 나타낸다.

따라서, Trie는 prefix Tree라고도 한다.

트라이의 초기 상태 : 루트(“”)만 있다.

트라이는 우리가 추가 하지 않은 문자열도 트리에 추가 되어 있다.

고로 우리가 추가한 문자열만 valid 변수를 통해서 구별한다.

모든 노드의 level, 높이는 문자열의 길이와 같다.

//트라이 대신 해시로 풀 수 있는 문제가 많다 하하

구현

#include #include using namespace std; struct Trie { struct Node { int children[26]; // 알파벳 소문자 26개 bool valid; // true : 추가한 문자열 Node() { for (int i = 0; i < 26; ++i) { children[i] = -1; } valid = false; } }; vector trie; int root; int init() { Node x; trie.push_back(x); return (int)trie.size() – 1; } Trie() { root = init(); } void add(int node, string &s, int index) { //node : 탐색하고 있는 노드의 인덱스, s : 추가하고 있는 문자열, if (index == s.size()) { trie[node].valid = true; return; } int c = s[index] – ‘a’; // 자식의 인덱스 if (trie[node].children[c] == -1) { // 없다면 int next = init(); trie[node].children[c] = next; } int child = trie[node].children[c]; add(child, s, index + 1); } void add(string &s) { add(root, s, 0); } bool search(int node, string &s, int index) { if (node == -1) return false; if (index == s.length()) return true; //return trie[node].valid; int c = s[index] – ‘a’; int child = trie[node].children[c]; return search(child, s, index + 1); } bool search(string &s) { return search(root, s, 0); } };

vaild로 추가한 문자열과 중간 과정때문에 생긴 노드와 구별.

Aho-corasick

Aho-corasick : 문자열 N개가 있을 때, 패턴 P를 찾는 알고리즘

ex)출석부에서 나랑 성이 같은 사람, 이름이 같은 사람을 찾기

kmp에서의 fail을 trie에서도 구현하는 것

fail[i] s의 i까지 부분 문자열(접두사)에서 prefix == suffix 중에서 가장 긴 문자열의 길이

->

fail[node] = node가 나타내는 문자열s의 suffix이면서 trie에 포함된 가장 긴 문자열

https://ko.wikipedia.org/wiki/%EC%95%84%ED%98%B8_%EC%BD%94%EB%9D%BC%EC%8B%9D_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

//Aho-Corasick #include #include #include #include #include #include using namespace std; struct nd { int child[26]; int pi; bool valid; nd() { for (int i = 0; i<26; i++) { child[i] = -1; } valid = false; pi = -1; } }; vector tr; int init() { nd x; tr.push_back(x); return (int)tr.size() – 1; } void add(int nd, string &s, int index) { if (index == s.size()) { tr[nd].valid = true; return; } int c = s[index] – ‘a’; if (tr[nd].child[c] == -1) { int next = init(); tr[nd].child[c] = next; } add(tr[nd].child[c], s, index + 1); } int main() { int root = init(); int n; cin >> n; vector a(n); for (int i = 0; i> a[i]; add(root, a[i], 0); } // ↑ trie 코드, queue q; // fail 값 찾기. tr[root].pi = root; q.push(root); while (!q.empty()) { //bfs로 fail 값 찾기, prefix ==suffix, 길이 < 문자열 int cur = q.front(); q.pop(); for (int i = 0; i<26; i++) { int next = tr[cur].child[i]; if (next == -1) continue; if (cur == root) { tr[next].pi = root; // 길이가 1인 prefix } else { // kmp와 같은 과정 ~ int x = tr[cur].pi; while (x != root && tr[x].child[i] == -1) { x = tr[x].pi; } if (tr[x].child[i] != -1) { x = tr[x].child[i]; } tr[next].pi = x; } // ~ kmp와 같은 과정 int pi = tr[next].pi; tr[next].valid |= tr[pi].valid; //문자열이 or 연산으로 위도 찾았다고 할때 q.push(next); } } // ~fail 값 계산 완료. int m; cin >> m; while (m–) { string s; cin >> s; int nd = root; bool ans = false; for (int i = 0; i

아호 코 라식 | Advanced Data Structures: Aho-Corasick Automaton 상위 195개 베스트 답변

당신은 주제를 찾고 있습니까 “아호 코 라식 – Advanced Data Structures: Aho-Corasick Automaton“? 다음 카테고리의 웹사이트 you.1111.com.vn 에서 귀하의 모든 질문에 답변해 드립니다: https://you.1111.com.vn/blog. 바로 아래에서 답을 찾을 수 있습니다. 작성자 Niema Moshiri 이(가) 작성한 기사에는 조회수 35,832회 및 좋아요 606개 개의 좋아요가 있습니다.

여기에서 이 주제에 대한 비디오를 시청하십시오. 주의 깊게 살펴보고 읽고 있는 내용에 대한 피드백을 제공하세요!

아호코라식(Aho-Corasick)은 현재 광범위하게 알려진 거의 유일한 일대다 패턴매칭 알고리즘이고, 그 존재 자체만으로 거의 KMP급의, 개선의 여지가 …

+ 여기에 표시

Source: m.blog.naver.com

Date Published: 1/8/2021

View: 4127

아호 코라식 알고리즘(Aho–Corasick string matching algorithm)은 Alfred V. Aho와 Margaret J. Corasick이 고안한 문자열 검색 알고리즘(매칭 알고리즘)이다.

+ 여기를 클릭

Source: ko.wikipedia.org

Date Published: 11/27/2021

View: 4274

2. 아호 코라식(Aho-Corasick) 알고리즘이란? · 일대다 문자열 패턴 매칭에 사용되는 알고리즘입니다. 패턴 문자열의 갯수와 상관없이 · 원본 문자열을 한 …

+ 여기에 표시

Source: pangtrue.tistory.com

Date Published: 2/26/2021

View: 475

아호 코라식 알고리즘을 이해하기 위해선 트라이 자료구조와 KMP 알고리즘 개념이 선행되어야 한다.(추가로 BFS 도 알고 있어야 한다.) …

+ 여기를 클릭

Source: ansohxxn.github.io

Date Published: 6/16/2021

View: 7436

아호 코라식 알고리즘(Aho–Corasick string matching algorithm)은 Alfred V. Aho와 Margaret J. Corasick이 고안한 문자열 검색 알고리즘(매칭 …

+ 여기에 자세히 보기

Source: loosie.tistory.com

Date Published: 11/17/2022

View: 1213

Aho-Corasick Multiple Pattern Matching Algorithm … 문자열 S와 여러 개의 문자열 T가 주어졌을 때, T에 있는 문자열 중 하나와 S가 매칭이 되는 지를 …

+ 여기를 클릭

Source: koosaga.com

Date Published: 1/24/2021

View: 7663

여러 문자열 패턴이 있고, 특정 문자열에 어떤 패턴이 어디에 존재하는지 확인하고 싶을 때 쓰는 알고리즘입니다. 기술적으로는 prefix와 suffix를 가지고 …

+ 자세한 내용은 여기를 클릭하십시오

Source: coloredrabbit.tistory.com

Date Published: 10/7/2021

View: 5857

본 글에서는 대표적인 문자열 검색 알고리즘인 KMP 알고리즘과 Aho-Corasick 알고리즘에 대해 다루려 한다. 두 알고리즘이 알고리즘계에서 잘 알려진 …

+ 여기를 클릭

Source: www.secmem.org

Date Published: 6/23/2021

View: 8628

그래서 이 부분을 다중 패턴 매칭 알고리즘인 아호코라식을 사용하여서 구현하였다. 아호코라식 알고리즘은 찾아야 하는 패턴이 많을 때 단순 2중 for문에 …

+ 여기에 표시

Source: tempdev.tistory.com

Date Published: 7/1/2021

View: 1403

Aho-Corasick 알고리즘. 2015년 9월 29일; h0ngjun7; 댓글 (2개); aho-corasick, pattern-matching. Aho-Corasick Algorithm(아호 코라식 알고리즘) from Hongjun Jang …

+ 여기에 더 보기

Source: www.acmicpc.net

Date Published: 5/15/2021

View: 7210

주제와 관련된 더 많은 사진을 참조하십시오 Advanced Data Structures: Aho-Corasick Automaton. 댓글에서 더 많은 관련 이미지를 보거나 필요한 경우 더 많은 관련 기사를 볼 수 있습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 #include < cstdio > #include < queue > #include < algorithm > using namespace std ; // 트라이 구조체 struct Trie{ // 현재 노드에서 해당 문자를 받으면 가는 노드 Trie * go[ 26 ]; // 현재 노드에서 해당 문자의 go 목적지가 없을 때 가는 노드 Trie * fail; // 현재 노드에 도달하면 찾는 문자열 집합: 이 문제에서는 존재성만 따지면 됨 bool output; Trie(){ fill(go, go + 26 , nullptr); output = false ; } ~Trie(){ for ( int i = 0 ; i < 26 ; i + + ) if (go[i]) delete go[i]; } void insert( const char * key){ if ( * key = = '\0' ){ output = true ; return ; } int next = * key - 'a' ; if ( ! go[next]){ go[next] = new Trie; } go[next] - > insert(key + 1 ); } }; int main(){ int N, M; char str[ 10001 ]; // 트라이에 S의 원소들을 모두 집어넣는다. Trie * root = new Trie; scanf ( “%d” , & N); for ( int i = 0 ; i < N; i + + ){ scanf ( "%s" , str); root - > insert(str); } // BFS를 통해 트라이 노드를 방문하며 fail 함수를 만든다. queue < Trie * > Q; root – > fail = root; Q.push(root); while ( ! Q.empty()){ Trie * current = Q. front (); Q. pop (); // 26개의 input 각각에 대해 처리한다. for ( int i = 0 ; i < 26 ; i + + ){ Trie * next = current - > go[i]; if ( ! next) continue ; // 루트의 fail은 루트다. if (current = = root) next – > fail = root; else { Trie * dest = current – > fail; // fail을 참조할 가장 가까운 조상을 찾아간다. while (dest ! = root & & ! dest – > go[i]) dest = dest – > fail; // fail(px) = go(fail(p), x) if (dest – > go[i]) dest = dest – > go[i]; next – > fail = dest; } // fail(x) = y일 때, output(y) ⊂ output(x) if (next – > fail – > output) next – > output = true ; // 큐에 다음 노드 push Q.push(next); } } // 각 문자열을 받아 문제를 푼다. scanf ( “%d” , & M); for ( int i = 0 ; i < M; i + + ){ scanf ( "%s" , str); // 루트부터 시작 Trie * current = root; bool result = false ; for ( int c = 0 ; str[c]; c + + ){ int next = str[c] - 'a' ; // 현재 노드에서 갈 수 없으면 fail을 계속 따라감 while (current ! = root & & ! current - > go[next]) current = current – > fail; // go 함수가 존재하면 이동. 루트면 이게 false일 수도 있다 if (current – > go[next]) current = current – > go[next]; // 현재 노드에 output이 있으면 찾은 것이다. if (current – > output){ result = true ; break ; } } // 결과 출력 puts(result ? “YES” : “NO” ); } // 내 힙은 소중하기에 꼭 동적할당을 해제한다. delete root; } Colored by Color Scripter cs

// 실패 함수 (KMP로 비교를 하다가 실패했을 때의 이동해야할 지점을 정의한다.) // 일반적인 KMP 구현에서 getPi() 메서드에 해당한다. void failure() { Queue q = new LinkedList<>(); trie.root.fail = trie.root; // root 회귀 q.add(trie.root); // 트리에 담긴 문자열에 대해 접두사-접미사가 동일한 것을 뽑아내야 한다. (BFS 이용) while (!q.isEmpty()) { TrieNode currentNode = q.poll(); // 알파벳 소문자만 있다고 가정하고 크기는 26 for (int i = 0; i < 26; i++) { TrieNode nextNode = currentNode.child[i]; if (nextNode == null) continue; if (currentNode.isRoot) { // root 자식 노드의 fail은 그들의 부모인 root 노드가 된다. nextNode.fail = trie.root; } else { TrieNode failure = currentNode.fail; while (!failure.isRoot && failure.child[i] == null) { failure = failure.fail; } if (failure.child[i] != null) { failure = failure.child[i]; } nextNode.fail = failure; } if (nextNode.fail.isEnd) { nextNode.isEnd = true; } q.add(nextNode); } } } 세팅이 끝났으면 마지막으로 문자열과 트라이 간의 KMP 알고리즘을 사용하는 코드는 다음과 같습니다. boolean kmp(String origin, TrieNode root) { TrieNode currentNode = root; boolean isFind = false; for (int i = 0; i < origin.length(); i++) { int idx = origin.charAt(i) - 'a'; while (!currentNode.isRoot && currentNode.child[idx] == null) { currentNode = currentNode.fail; } if (currentNode.child[idx] != null) { currentNode = currentNode.child[idx]; } if (currentNode.isEnd) { // 원본 문자열에서 패턴 문자열 하나를 찾았다면 isFind = true; } } return isFind; } 3. 참고자료 [1] m.blog.naver.com/PostView.nhn [2] www.slideshare.net/ssuser81b91b/ahocorasick-algorithm [3] koosaga.com/157 🚀 서론 아호 코라식 알고리즘을 이해하기 위해선 트라이 자료구조와 KMP 알고리즘 개념이 선행되어야 한다.(추가로 BFS 도 알고 있어야 한다.) 아호 코라식은 트라이 자료구조를 사용하며 KMP 알고리즘의 확장판이라고 볼 수 있기 때문이다. 자세한 설명은 아래 링크 참고 🙂 🔥 쓰임새 여러 문자열 들을 동시에 찾아야 하는 검색 엔진 에서 유용하게 사용되는 알고리즘 KMP 👉 텍스트에서 검색어 하나를 찾아낼 때 사용 (1:1) 아호 코라식 👉 텍스트에서 검색어 여러개를 동시에 찾아낼 때 사용 (1:N) ex) “cacachefcachy” 텍스트에 { “cache”, “he”, “chef”, “archy” } 中 하나라도 부분 문자열로 포함되어 있는지 찾기. 아호코라식 알고리즘을 통해 수 많은 페이지에서 여러 검색어들이 부분적으로 포함된 각각의 위치들을 빠르게 찾아낼 수 있다. 🔥 용어 텍스트, text : 검색을 실행할 문자열. 이 문자열 내에 원하는 검색어가 있는지 탐색해보고자 함. \(N\) : 텍스트의 길이 검색어, search, pattern : 검색할 문자열. 검색이 된다면 텍스트 의 부분 문자열. 문자열 패턴 매칭을 하는 것과도 같기에 패턴이라고도 칭할 것. \(M\) : 검색어의 길이 \(k\) : 검색어의 총 개수 👉 아호 코라식은 검색어가 여러개일 때 사용 🔥 다른 방법들과의 비교 (+ 아호-코라식의 시간 복잡도) 브루트 포스 일일이 검색어들마다 텍스트와 브루트 포스로 비교한다면 👉 \(O(nm_{1} + nm_{2} + nm_{3} + .. + nm_{k})\) KMP 알고리즘을 N 번 실행 일일이 검색어들마다 텍스트와 KMP 알고리즘으로 비교 👉 \(O(n + m_{1} + n + m_{2} + n + m_{3} + .. + n + m_{k}) = O(kn + m_{1} + m_{2} + m_{3} + .. + m_{k})\) 동일한 텍스트를 \(k\) 번 검사해야 하고 (\(kn\)) 검색어들 별로 실패 함수들 \(m_{1} + m_{2} + m_{3} + .. + m_{k}\) 을 따로 다 만들어야 한다. 아호 코라식 을 사용했을 때 일일이 검색어들마다 비교하지 않고, 검색어들을 트라이 트리에 모아두고 한번에 순회한다. 👉 \(O(n + m_{1} + m_{2} + .. + m_{k})\) 텍스트의 순회는 단 한번만 하면 된다. \(n\) 검색어 별로 실패 “링크” 를 만들 때 \(m_{1} + m_{2} + m_{3} + .. + m_{k}\) 아호 코라식은 실패 함수 “배열”을 만들지 않고 트라이에서 불일치시 돌아갈 실패 “링크” 를 만든다. 이 실패 링크 또한 KMP 처럼 접두사 = 접미사의 최대 길이인 곳으로 돌아간다. A 검색어를 검사하는데서 불일치가 발생했다면 A 검색어의 접미사와 일치하는 다른 B 검색어의 접두사 노드로 간다! 을 사용했을 때 🚀 구현 코드 및 과정 설명 아호 코라식 알고리즘은 트라이 + KMP 짬뽕 🔥 아호-코라식 개념 설명 (두서없음 주의..) 1️⃣ 검색어들은 트라이에 저장한다. 트라이는 여러개의 문자열을 트리 형태로 저장하는 형태의 자료 구조이다. 또한 이 문자열들의 공통된 접두사는 하나의 노드로 묶여 탐색 공간이 줄어들기 때문에 이 트라이에 저장된 문자열들에서 내가 찾아보고자 하는 길이만큼의 시간만 들여서 빠르게 찾아낼 수 있다. 검색어가 여러개일 때, 텍스트 문자열에 이 검색어들이 각각 탐색되는지를 “빠르게” 알고 싶다면 이 검색어들을 트라이에 저장하여 여기서 탐색한다는 것이 아호 코라식의 아이디어다. 2️⃣ KMP 처럼 접두사 = 접미사 실패함수를 미리 전처리 과정에서 구해놓는다. 아호 코라식에선 “실패 링크”라고 불린다. 노드 별로 실패 링크를 만든다. KMP 와 달리 검색어가 여러개이기 때문에 걸칠 수 있는 그 대상은 검색어 하나가 아닌 여러개가 후보가 될 수 있다. 예를 들어 “블라블라AB” 까지 일치했었다면 이제 “AB” 를 접두사로 가진 ‘다른 검색어’로 이동할 수 있다는 것이다. “AB” 는 이미 일치했다고 걸쳐진 상태로 “AB” 로 시작하는 이 검색어를 텍스트와 비교하는 식이다. 즉, 걸칠 수 있는 다른 검색어로 비교 대상을 바꾸는 것이다. 노드별로 실패링크를 만든다는 것은 A 검색어의 원소와 텍스트를 비교해나가다가 불일치가 발생하면 A 검색어에서 이전까지 일치한 부분 문자열의 접미사를 접두사로 가지는 다른 B 검색어 ‘노드’로 이동하도록 하는 트라이 트리의 “링크”를 만들어주는 것이다. 여기서 한번 짚고 넘어가고 싶은 부분은 트라이 트리에 있어 “조상 및 부모 노드”는 이전 문자이며, “자식 노드”는 다음 문자라는 것에 주의하자. 직계 부모, 직계 조상이면 자신이 속한 그 문자열을 비롯하여 같은 접두사를 공유하는 문자열들 내에서의 “이전 문자”일테고 직계는 아니지만 그냥 나보다 깊이가 얕은 위의 노드들이면 다른 검색어에 속하지만 나보다 인덱스 상으로 더 앞의 문자가 될 것이다. 자식은 그 반대! 3️⃣ KMP 처럼 탐색 시 접두사 = 접미사 최대 길이를 활용하고 걸치는 작업을 한다. 실패 링크로 이동하는 것 자체가 걸치는 작업 이다. 현재 A 노드(=글자)를 방문 중이라고 예를 들자면 KMP 와 비교 이전까지 일치한 문자열 👉 트라이 트리 안에서 A 글자까지 내려오면서 지나온 문자들 이전까지 일치한 문자열의 접미사와 다른 문자열의 접두사 👉 다른 검색어로 비교 하기 위해 옮겨가, 해당 접두사를 걸쳐놓는 위치로 이동한다. 이미 전처리 과정에서 실패 링크를 다 만들어 놨기 때문에 다른 검색어의 걸칠 수 있는 그 위치로 이동하면 된다. 📌 정리 성공 링크 현재 노드(문자)가 비교 중인 텍스트 원소와 일치한다면 이동할 노드 링크 자식 노드(비교중인 검색어의 다음 문자)로 이동하는 링크이다. 트라이를 만드는 과정인 Inser 삽입 함수 과정에서 자연스럽게 정해진다. 실패 링크 현재 노드(문자)가 비교 중인 텍스트 원소와 일치하지 않는다면 이동할 노드 링크 다른 검색어에 걸칠 수 있는게 있다면, 즉!! 이전 노드까지의 접미사 중 다른 검색어의 접두사와 일치하는게 있다면, 즉!! 현재 방문 중인 노드의 부모 노드의 실패링크! 부모의 실패 링크를 타고 가면 나오는 노드에서도 현재 문자가 자식 노드(=다음 문자)로 연결 되는게 있다면 현재 노드의 실패 링크는 부모 노드의 실패 링크의 자식 노드로 가게끔 연결해준다. 즉, 현재 문자에서 불일치되면 현재문자는 이전 문자(부모 노드)까지의 접미사와 동일한 타 검색어의 접두사의 끝 문자가 되도록 이동을 할 수 있도록 하는 것이다. 예시 “블라블라AC” 는 불일치 발생시 “AC블라블라” 로 이동 하도록 실패 링크를 놓을 수 있다. “블라블라ACZ” 는 불일치 발생시 “ACZ블라블라” 로 이동 하도록 실패 링크를 놓을 수 있다. “블라블라AC” 의 자식인 “블라블라ACZ” 는 “블라블라AC” 의 실패 링크인 “AC블라블라” 의 자식인 “ACZ블라블라”를 실패 링크로 가질 수 있는 것이다. 단! “블라블라AC” 의 “C” 의 다음 글자가 “Z” 인게 트라이에 존재한다는 전제하에! 부모의 실패 링크를 타고 가면 나오는 노드에서도 현재 문자가 자식 노드(=다음 문자)로 연결 되는게 없다면 루트로 돌아갈 떄까지, 혹은 현재 문자가 접두사의 끝이 될 수 있을 때까지 부모의 실패링크를 타고 올라가고 그 노드의 실패 링크를 또 타고 올라가고를 반복하여 올라간다. 전체적으로 이렇게 가장 가까운 조상인 직계 부모의 실패링크부터 검사를 하고, 연결되는게 없다면 타고타고 올라가고 하기 때문에 접두사 = 접미사의 “최대 길이”라는 것이 자연스럽게 보장이 된다. 조상 노드들부터 이렇게 실패 링크를 결정 지어 왔기 때문에 DP 방식으로 생각하면 된다. 밑에서 더 자세히 설명하겠지만 BFS 방식으로 루트부터 깊이대로 차례 차례 노드 들을 방문해 내려오면서 각각 실패 링크를 만들어 준다. 그래서 현재 노드의 실패 링크를 결정하고자 하는 시점엔 이미 그의 조상 노드들의 실패 링크는 모두 정해진 상태이다. 만약 재귀 호출 방식으로 DFS 를 사용한다면 직계 부모의 실패 링크는 알 수 있지만 실패 링크를 따라간 노드의 실패 링크는 알 수가 없을 수도 있기 때문이다.(아직 실패링크 안 만든 상태일 수도) 따라서 BFS 를 통해 깊이대로 차례 차례 실패 링크를 만든다. 전체적으로 말로 풀어서 설명하기가 너무 어렵다. 😅 그러니 밑에 도식화 한 과정을 보며 이해해보자. 🔥 전체 코드 #include using namespace std ; struct Trie { // 노드 객체 클래스 public: bool isEnd ; // 이 노드가 한 검색어의 끝인지 아닌지를 알려줌 string p ; // 이 노드까지의 접두사 (아호 코라식의 필요한 부분은 아니다.) map < char , Trie *> child ; // 자식 노드 링크 Trie * fail ; // 실패 링크 ⭐ Trie () : isEnd ( false ), fail ( nullptr ) {} void Insert ( string pattern ) { Trie * now = this ; int m = pattern . length (); for ( int i = 0 ; i < m ; ++ i ) { if ( now -> child . find ( pattern [ i ]) == now -> child . end ()) now -> child [ pattern [ i ]] = new Trie ; now = now -> child [ pattern [ i ]]; if ( i == m – 1 ) { now -> p = pattern ; now -> isEnd = true ; } } } void Fail () { // BFS + KMP Trie * root = this ; queue < Trie *> q ; q . push ( root ); while ( ! q . empty ()) { Trie * now = q . front (); q . pop (); for ( auto & ch : now -> child ) { Trie * next = ch . second ; if ( now == root ) next -> fail = root ; else { Trie * prev = now -> fail ; while ( prev != root && prev -> child . find ( ch . first ) == prev -> child . end ()) prev = prev -> fail ; if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ; } if ( next -> fail -> isEnd ) next -> isEnd = true ; q . push ( next ); } } } }; vector < pair < string , int >> KMP ( string text , Trie * root ) { Trie * now = root ; int n = text . length (); vector < pair < string , int >> answer ; for ( int i = 0 ; i < n ; ++ i ) { while ( now != root && now -> child . find ( text [ i ]) == now -> child . end ()) now = now -> fail ; if ( now -> child . find ( text [ i ]) != now -> child . end ()) now = now -> child [ text [ i ]]; if ( now -> isEnd ) { answer . push_back ({ now -> p , i }); } } return answer ; } int main () { freopen ( “input.txt” , “r” , stdin ); int N ; cin >> N ; vector < string > patterns ( N ); for ( int i = 0 ; i < N ; ++ i ) cin >> patterns [ i ]; Trie * root = new Trie ; for ( int i = 0 ; i < N ; ++ i ) root -> Insert ( patterns [ i ]); root -> Fail (); string text ; cin >> text ; vector < pair < string , int >> answer = KMP ( text , root ); cout << text << "에서 검색하기" << ' ' ; for ( int i = 0 ; i < answer . size (); ++ i ) cout << "확인된 검색어 : " << answer [ i ]. first << ", 위치 : " << answer [ i ]. second << ' ' ; } 💎입력💎 검색어 👉 cache, he, chef, achy 텍스트 👉 cacachefcachy 💎출력💎 cacachefcachy에서 검색하기 확인된 검색어 : cache, 위치 : 6 확인된 검색어 : chef, 위치 : 7 확인된 검색어 : achy, 위치 : 12 1️⃣ 삽입 함수 (트라이 만들기) // Trie 트라이의 멤버 함수 // 📌 노드들의 성공 링크 결정 void Insert ( string pattern ) { Trie * now = this ; int m = pattern . length (); for ( int i = 0 ; i < m ; ++ i ) { if ( now -> child . find ( pattern [ i ]) == now -> child . end ()) now -> child [ pattern [ i ]] = new Trie ; now = now -> child [ pattern [ i ]]; if ( i == m – 1 ) { now -> p = pattern ; now -> isEnd = true ; } } }

가장 첫 번째로 해주어야할 작업은 검색어들을 트라이 트리에 삽입하는 것이다. 검색어의 마지막 글자엔 해당 검색어를 문자열 p 에 할당해주고 isEnd 를 True 로 바꾸었다. 진한 노란색은 isEnd 가 True인 단어의 끝을 의미한다.

원래 실제 메모리상으론 첫 번째 그림처럼 되는게 맞다. 그러나 아호 코라식 과정을 이해하는데 도움이 되기 위하여 두 번째 그림과 같이 해당 글자까지의 접두사로 노드를 표현하겠다.

2️⃣ 실패 함수 (트라이를 BFS 순회하며 노드마다 실패 링크 만들어주기)

// Trie 트라이의 멤버 함수 // 📌 노드들의 실패 링크 결정 void Fail () { // BFS + KMP Trie * root = this ; queue < Trie *> q ; q . push ( root ); while ( ! q . empty ()) { Trie * now = q . front (); // 방문 중인 노드 q . pop (); /* 자식 노드들 큐에 삽입 및 실패 링크 만들어주기 */ for ( auto & ch : now -> child ) { Trie * next = ch . second ; // 자식 노드 (now 의 자식 next) // 부모(now)가 루트 노드라면 실패 링크는 루트로 한다. // 첫 문자부터 불일치였다면 걸칠 수 있는게 없기 때문이다. if ( now == root ) next -> fail = root ; // 부모(now)가 루트 노드가 아니라면 else { Trie * prev = now -> fail ; // 부모 노드(= 이전 문자)의 실패 링크! 현재 노드(next) 까지 도달 했다는 것은 부모 노드(= 이전 문자)까진 일치했었다는 뜻이다. // 부모의 실패 링크에 현재 문자(next)가 자식 노드로 연결되지 않았다면, 즉 자식으로 없다면! 혹시 그 실패 링크가 루트 노드가 되거나 현재 문자를 자식으로 둔 노드를 찾을 떄까지 실패 링크를 타고 타고 올라간다. // 접미사 = 접두사인 타 검색어의 접두사를 찾을 때까지 올라감 // 타고 타고 올라갈 수록 접미사 = 접두사의 길이는 짧아질 수 밖에 없다. while ( prev != root && prev -> child . find ( ch . first ) == prev -> child . end ()) prev = prev -> fail ; // 현재 노드(next)의 실패링크를 결정한 실패링크의 자식 노드로 연결 if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ; } // che 의 실패링크가 he 라면, 근데 he 가 완전한 단어의 모습이라면! chef 의 che 또한 isEnd 가 true 가 될 수 있다. che 에서 불일치가 발생하더라도 그건 완전한 검색어 he 로도 걸칠 수 있기 때문이다. if ( next -> fail -> isEnd ) next -> isEnd = true ; q . push ( next ); } } }

BFS 순회

회색 별표 : 현재 방문 중인 노드 now (= 현재 노드인 next 의 부모)

(= 현재 노드인 의 부모) 노란 화살표 : 성공 링크

주황 화살표 : 실패 링크 볼드체는 현재 예약 중인 노드 next 에게 방금 만들어준 실패 링크

if ( now == root ) next -> fail = root ;

“a” 에서 불일치가 발생한다면?

부모가 루트이기 때문에 실패 링크는 루트로 한다. 이전 문자가 하나도 없기 때문에 이전 문자에서 접두사 = 접미사를 찾을 수 없어 처음부터 찾도록 실패시 트라이의 루트로 돌아가도록 한다.

if ( now == root ) next -> fail = root ;

“c” 에서 불일치가 발생한다면?

부모가 루트이기 때문에 실패 링크는 루트로 한다. 이전 문자가 하나도 없기 때문에 이전 문자에서 접두사 = 접미사를 찾을 수 없어 처음부터 찾도록 실패시 트라이의 루트로 돌아가도록 한다.

if ( now == root ) next -> fail = root ;

“h” 에서 불일치가 발생한다면?

부모가 루트이기 때문에 실패 링크는 루트로 한다. 이전 문자가 하나도 없기 때문에 이전 문자에서 접두사 = 접미사를 찾을 수 없어 처음부터 찾도록 실패시 트라이의 루트로 돌아가도록 한다.

“ac” 의 “c” 에서 불일치가 발생한다면 ?

“ac”의 가능한 접미사는 “c” 뿐이다.

if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “a” 의 실패 링크가 루트인데 루트의 자식으로 “c” 가 있다. 즉, “c” 로 시작하는 접두사가 있다는 의미이다. 실패시 이 “c” 로 이동하도록 한다.

“ca” 의 “a” 에서 불일치가 발생한다면 ?

“ca”의 가능한 접미사는 “a” 뿐이다.

if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “c” 의 실패 링크가 루트인데 루트의 자식으로 “a” 가 있다. 즉, “a” 로 시작하는 접두사가 있다는 의미이다. 실패시 이 “a” 로 이동하도록 한다.

“ch” 의 “h” 에서 불일치가 발생한다면 ?

“ch”의 가능한 접미사는 “h” 뿐이다.

if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “c” 의 실패 링크가 루트인데 루트의 자식으로 “h” 가 있다. 즉, “h” 로 시작하는 접두사가 있다는 의미이다. 실패시 이 “h” 로 이동하도록 한다.

“he” 의 “e” 에서 불일치가 발생한다면 ?

“he”의 가능한 접미사는 “e” 뿐이다.

next -> fail = prev ;

부모인 “h” 의 실패 링크가 루트인데 루트의 자식으로 “e” 가 없다. 즉, “e” 로 시작하는 접두사가 없다는 의미이다. 부모 실패 링크가 루트이니 while 에도 걸리지 않고, 부모 실패링크의 자식으로 “e” 가 없으니 if 문에도 걸리지 않는다.

부모의 실패 링크인 루트가 그대로 할당 된다. “he” 의 “e” 에서 불일치가 발생한다면 “he” 보다 짧은 것 중 “e” 로 시작할 수 있는게 없기 때문에 루트로 향한다.

“ach” 의 “h” 에서 불일치가 발생한다면 ?

“ach” 의 가능한 접미사는 “h”, “ch” 가 있다. (길이가 긴게 선택될 수록 좋다. 현재 노드와 가까운 실패링크일 수록 길이가 길다.)

if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “ac” 의 실패 링크인 “c”의 자식으로 “h” 가 있다. 즉, “ch” 로 시작하는 접두사가 있다는 의미이다. 실패시 이 “ch” 로 이동하도록 한다.

“cac” 의 “c” 에서 불일치가 발생한다면 ?

“cac” 의 가능한 접미사는 “c”, “ac” 가 있다. (길이가 긴게 선택될 수록 좋다. 현재 노드와 가까운 실패링크일 수록 길이가 길다.)

if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “ca” 의 실패 링크인 “a”의 자식으로 “c” 가 있다. 즉, “ac” 로 시작하는 접두사가 있다는 의미이다. 실패시 이 “ac” 로 이동하도록 한다.

“che” 의 “e” 에서 불일치가 발생한다면 ?

“che” 의 가능한 접미사는 “e”, “he” 가 있다. (길이가 긴게 선택될 수록 좋다. 현재 노드와 가까운 실패링크일 수록 길이가 길다.)

if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “ch” 의 실패 링크인 “h”의 자식으로 “he” 가 있다. 즉, “he” 로 시작하는 접두사가 있다는 의미이다. 실패시 이 “he” 로 이동하도록 한다.

if ( next -> fail -> isEnd ) next -> isEnd = true ;

“che” 의 실패링크인 “he” 는 단어의 끝이다. 즉, “che” 에 “he” 검색어가 포함되어 있다는 것이다. 따라서 “che” 의 isEnd 도 True 로 체크를 해준다. (진한 노란색으로 색 바꿔줌)

“he” 의 자식은 아무것도 없기 때문에 for문 예약 작업 하지 않고 넘어간다.

“achy” 의 “y” 에서 불일치가 발생한다면 ?

“achy” 의 가능한 접미사는 “y”, “hy”, “chy” 가 있다. (길이가 긴게 선택될 수록 좋다. 현재 노드와 가까운 실패링크일 수록 길이가 길다.)

while ( prev != root && prev -> child . find ( ch . first ) == prev -> child . end ()) prev = prev -> fail ; // if 는 false next -> fail = prev ;

부모인 “ach” 의 실패 링크인 “ch”의 자식으로 “y” 가 없다. 👉 “chy” 로 걸칠 수 있는 접두사 없음 부모의 실패링크가 루트도 아니기 때문에 while 문을 돌며 “hy”, “y” 로 걸칠 수 있을지 각각 검사하러 간다. “ch” 의 실패 링크인 “h”의 자식으로 “y” 가 없다. “h” 의 실패 링크인 루트의 자식으로 “y” 가 없다. 결국 “hy”, “y” 접두사도 존재하지 않기에 “ach” 의 실패 링크는 루트가 된다.

“cach” 의 “h” 에서 불일치가 발생한다면 ?

“cach” 의 가능한 접미사는 “h”, “ch”, “ach” 가 있다. (길이가 긴게 선택될 수록 좋다. 현재 노드와 가까운 실패링크일 수록 길이가 길다.)

if ( prev -> child . find ( ch . first ) != prev -> child . end ()) prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “cac” 의 실패 링크인 “ac”의 자식으로 “ach” 가 있다. 즉, “ach” 로 시작하는 접두사가 있다는 의미이다. 실패시 이 “ach” 로 이동하도록 한다.

“chef” 의 “f” 에서 불일치가 발생한다면 ?

“chef” 의 가능한 접미사는 “f”, “ef”, “hef” 가 있다. (길이가 긴게 선택될 수록 좋다. 현재 노드와 가까운 실패링크일 수록 길이가 길다.)

while ( prev != root && prev -> child . find ( ch . first ) == prev -> child . end ()) prev = prev -> fail ; // if 문은 false next -> fail = prev ;

부모인 “che” 의 실패 링크인 “he”의 자식으로 “y” 가 없다. 👉 “hef” 로 걸칠 수 있는 접두사 없음 부모의 실패링크가 루트도 아니기 때문에 while 문을 돌며 “ef”, “f” 로 걸칠 수 있을지 각각 검사하러 간다. “he” 의 실패 링크인 루트의 자식으로 “f” 가 없다. 결국 “ef”, “f” 접두사도 존재하지 않기에 “chef” 의 실패 링크는 루트가 된다.

“achy” 의 자식은 아무것도 없기 때문에 for문 예약 작업 하지 않고 넘어간다.

“cache” 의 “e” 에서 불일치가 발생한다면 ?

“cache” 의 가능한 접미사는 “e”, “he”, “che”, “ache” 가 있다. (길이가 긴게 선택될 수록 좋다. 현재 노드와 가까운 실패링크일 수록 길이가 길다.)

while ( prev != root && prev -> child . find ( ch . first ) == prev -> child . end ()) prev = prev -> fail ; if ( prev -> child . find ( ch . first ) != prev -> child . end ()) // if 도 True 가 됨! prev = prev -> child [ ch . first ]; next -> fail = prev ;

부모인 “cach” 의 실패 링크인 “ach”의 자식으로 “e” 가 없다. 👉 “ache” 로 걸칠 수 있는 접두사 없음 부모의 실패링크가 루트도 아니기 때문에 while 문을 돌며 “che”, “he”, “e” 로 걸칠 수 있을지 각각 검사하러 간다. “ach” 의 실패 링크인 “ch”의 자식으로 “e” 가 있다. (while문 종료) 따라서 “cache” 의 실패 링크는 “che” 가 된다.

“chef” 의 자식은 아무것도 없기 때문에 for문 예약 작업 하지 않고 넘어간다.

“cache” 의 자식은 아무것도 없기 때문에 for문 예약 작업 하지 않고 넘어간다.

3️⃣ 검색 함수 (KMP 알고리즘 방식으로 트라이에서 검색)

// 전역 함수 vector < pair < string , int >> KMP ( string text , Trie * root ) { Trie * now = root ; int n = text . length (); vector < pair < string , int >> answer ; for ( int i = 0 ; i < n ; ++ i ) { // 텍스트 글자가 현재 방문 중인 노드(검색어 글자)와 일치하지 않는다면 👉 일치하는게 하나도 없는 상태(now == root)가 되거나 일치할 때까지 실패 링크 타기 while ( now != root && now -> child . find ( text [ i ]) == now -> child . end ()) now = now -> fail ; // 일치한다면 성공링크 타고 내려가기 if ( now -> child . find ( text [ i ]) != now -> child . end ()) now = now -> child [ text [ i ]]; // 검색어를 찾았다면 if ( now -> isEnd ) { answer . push_back ({ now -> p , i }); // 그 문자열과 위치를 answer 에 담도록 하였다. } } return answer ; }

일치할 경우 “성공 링크”를 타고 내려간다. (노란 화살표)

일치하지 않을 경우, 일치할 때까지 (혹은 루트가 될 때까지) “실패 링크”를 타고 올라간다. (주황 화살표)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : 루트

루트의 성공 링크 (첫 번째 if) 루트의 자식인 c 로 이동

아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : c

c 의 성공 링크 (첫 번째 if) c 의 자식인 ca 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : ca

ca 의 성공 링크 (첫 번째 if) ca 의 자식인 cac 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : cac

실패 링크 (while) cac 의 자식엔 caca 가 없다. 👉 cac 의 실패 링크인 ac 로 이동 ac 의 자식엔 aca 가 없다. 👉 ac 의 실패 링크인 c 로 이동 c 의 자식엔 ca 가 있다.

c 의 성공 링크 (첫 번째 if) c 의 자식인 ca 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : ca

ca 의 성공 링크 (첫 번째 if) ca 의 자식인 cac 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : cac

cac 의 성공 링크 (첫 번째 if) cac 의 자식인 cach 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : cach

cach 의 성공 링크 (첫 번째 if) cach 의 자식인 cache 로 이동

의 성공 링크 (첫 번째 if) 검색어 찾음 ! ! ! (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : cache

실패 링크 (while) cache 의 자식엔 cachef 가 없다. 👉 cache 의 실패 링크인 che 로 이동 che 의 자식엔 chef 가 있다.

che 의 성공 링크 (첫 번째 if) che 의 자식인 chef 로 이동

의 성공 링크 (첫 번째 if) 검색어 찾음 ! ! ! (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : chef

실패 링크 (while) chef 의 자식엔 chefc 가 없다. 👉 chef 의 실패 링크인 루트로 이동

루트의 성공 링크 (첫 번째 if) 루트의 자식인 c 로 이동

아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : c

c 의 성공 링크 (첫 번째 if) c 의 자식인 ca 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : ca

ca 의 성공 링크 (첫 번째 if) ca 의 자식인 cac 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : cac

cac 의 성공 링크 (첫 번째 if) cac 의 자식인 cach 로 이동

의 성공 링크 (첫 번째 if) 아직 검색어 찾지 못함 (두 번째 if)

텍스트 : c a c a c h e f c a c h y

현재 방문 노드 : cach

실패 링크 (while) cach 의 자식엔 cachy 가 없다. 👉 cach 의 실패 링크인 ach 로 이동 ach 의 자식엔 achy 가 있다.

ach 의 성공 링크 (첫 번째 if) ach 의 자식인 achy 로 이동

의 성공 링크 (첫 번째 if) 검색어 찾음 ! ! ! (두 번째 if)

이렇게 하여 텍스트를 모두 순회하였고 탐색을 종료 🙂

📌 Reference

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

키워드에 대한 정보 아호 코 라식

다음은 Bing에서 아호 코 라식 주제에 대한 검색 결과입니다. 필요한 경우 더 읽을 수 있습니다.

이 기사는 인터넷의 다양한 출처에서 편집되었습니다. 이 기사가 유용했기를 바랍니다. 이 기사가 유용하다고 생각되면 공유하십시오. 매우 감사합니다!

사람들이 주제에 대해 자주 검색하는 키워드 Advanced Data Structures: Aho-Corasick Automaton

• advanced
• data
• structures
• aho
• corasick
• aho-corasick
• automaton
• automatons
• algorithm
• algorithms
• multiway
• trie
• MWT
• tries
• MWTs
• failure
• links
• link
• pattern
• patterns
• matching
• database
• databases
• short
• sequence
• sequences
• dna
• long
• query
• string
• strings
• bioinformatics

Advanced #Data #Structures: #Aho-Corasick #Automaton

---

YouTube에서 아호 코 라식 주제의 다른 동영상 보기

주제에 대한 기사를 시청해 주셔서 감사합니다 Advanced Data Structures: Aho-Corasick Automaton | 아호 코 라식, 이 기사가 유용하다고 생각되면 공유하십시오, 매우 감사합니다.