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

우아한형제 기술블로그를 보던 중, 이목을 끄는 제목을 발견하고 글을 읽게 되었습니다.

고르곤졸라는 되지만 고르곤 졸라는 안 돼! 배달의민족에서 금칙어를 관리하는 방법 | 우아한형

 

지난 글에서 아호 코라식 알고리즘과 트라이 구조에 대해 정리하였습니다.

https://kyko.tistory.com/59

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

아호 코라식 알고리즘은 다음과 같은 과정을 가지고 있습니다.

1. 패턴을 트라이에 저장
2. 실패 링크 생성
3. 탐색

이번에는 트라이를 BFS로 순회하며 각 노드마다 실패 링크를 생성하려고 합니다.

 

실패 링크 생성

---

실패 링크는 현재 노드(패턴의 문자)가 비교 중인 텍스트의 문자와 일치하지 않을 경우 이동할 노드 링크를 의미합니다.

빨간색 선이 실패 링크입니다.

 

'w'는 부모가 루트 노드이기 때문에 실패 링크는 루트 노드로 설정됩니다.

'j' 또한 부모가 루트 노드이므로 실패 링크는 루트 노드로 설정됩니다.

'ww'의 마지막 'w'에서 불일치가 발생하면, 'ww'의 가능한 접미사는 'w' 하나이므로 이전 링크로 이동합니다.

'wo'의 'o'에서 불일치가 발생하면, 'wo'의 가능한 접미사는 'o' 하나입니다. 그러나 부모인 'w'의 실패 링크가 루트 노드이고, 루트의 자식으로 'o'가 없기 때문에, 실패 링크는 부모인 'w'의 실패 링크인 루트 노드로 설정됩니다.

'ju'의 'u'에서 불일치가 발생하면, 'ju'의 가능한 접미사는 'u'하나입니다. 하지만 부모인 'j'의 실패 링크가 루트 노드이고, 루트의 자식으로 'u'가 없기 때문에, 실패 링크는 부모인 'j'의 실패 링크인 루트 노드로 설정됩니다.

'www'의 마지막 'w'에서 불일치가 발생하면, 'www'의 가능한 접미사는 'ww', 'w' 두 개입니다. 현재 노드와 가까운 실패 링크 일수록 길이가 길기 때문에, 길이가 긴 'ww'를 실패 링크로 할당합니다.

'woo'의 'o'에서 불일치가 발생하면, 'woo'의 가능한 접미사는 'oo', 'o' 두 개입니다. 그러나 이전 노드들 중 'oo'와 'o'가 없기 때문에, 실패 링크는 루트 노드로 할당됩니다.

'jun'에서도 마찬가지로 접미사가 'un'과 'n' 두 개가 존재하지만, 이전 노드들 중 'un'과 'n'이 없기 때문에 실패 링크는 루트 노드로 설정됩니다.

이를 코드로 구현하면 다음과 같습니다.

static void makeFailLink() {
        Queue<Node> q = new LinkedList<>();
        
        for (int i = 0; i<rootNode.childs.length; i++) {
            if(rootNode.childs[i] != null) {
                q.offer(rootNode.childs[i]);
                rootNode.childs[i].failLink = rootNode;
            } else {
                //serch에서 while문에서 결국 실패링크를 찾아내지못했을 때 루트노드부터 다시 시작할 수 있도록 해주는 역할도 함 반복문 탈출시켜줌 빈 자식 자리가 널이 아닌 루트
                rootNode.childs[i] = rootNode;
            }
        }
        
        while (!q.isEmpty()) {
            Node curNode = q.poll();

            for (int i = 0; i<26; i++) {
                if(curNode.childs[i]!= null) {
                    
                    //curNode.childs[i]에 i값이 바뀌며 새로운 자식을 찾을 때마다 failLink는 다시 curNode(i들의 부모노드)의 페일링크로 초기화되어야함. 왜? 특정 자식이 이 페일링크의 위치를 타고타고 트리 위에다가 가져다놨을 수도 있기 때
                    Node lastFailLink = curNode.failLink;
                    
                    while (lastFailLink.childs[i] == null) {
                        //부모노드의 페일 링크 노드의 자식 중 이어질 곳이 없다면(현재 내 노드의 알파벳을 가진 노드가 없다면) 부모노드의 페일링크의 페일링크로 이동 이걸 무한반복 
                        lastFailLink = lastFailLink.failLink;
                    }
                    //현재 노드의 부모 노드의 페일링크로 이동 -> 이 페일링크 노드의 자식 노드중 현재 노드의 알파벳 값을 가진 노드를 페일링크로 연결
                    curNode.childs[i].failLink = lastFailLink.childs[i];
                    //현재 노드외 연결된 페일링크 노드의 아웃풋 패턴이 있었다면 이 패턴을 현재 노드에서도 반환할 수 있도록 해줌  (ex. she he)
                    curNode.childs[i].outPuts.addAll(lastFailLink.childs[i].outPuts);
                    
                    q.offer(curNode.childs[i]);
                } 
            }
        }
    }

 

탐색

---

탐색 과정은 다음과 같습니다.

1. 문자가 일치하면 성공 링크(자식 노드, 검은색 화살표)를 따라 내려갑니다.

2. 문자가 일치하지 않으면 실패 링크(빨간 화살표)를 타고 올라가며 일치할 때까지 계속합니다.

• 텍스트 = "myungwoo"
• 패턴: { "www", "woo", "jun" }

텍스트: myungwoo

루트 노드의 자식 노드 중 'm'이 없으므로 이동하지 않습니다.

텍스트: myungwoo

루트 노드의 자식 노드 중 'y'가 없으므로 이동하지 않습니다.

텍스트: myungwoo

루트 노드의 자식 노드 중 'u'가 없으므로 이동하지 않습니다.

텍스트: myungwoo

루트 노드의 자식 노드 중 'n'이 없으므로 이동하지 않습니다.

텍스트: myungwoo

루트 노드의 자식 노드 중 'g'가 없으므로 이동하지 않습니다.

텍스트: myungwoo

루트 노드의 자식 노드 중 'w'가 있으므로, 성공 링크를 타고 이동합니다.

텍스트: myungwoo

'w' 노드의 자식 노드 중 'o'가 있으므로, 성공 링크를 타고 이동합니다.

텍스트: myungwoo

'o' 노드의 자식 노드 중 'o'가 있으므로, 성공 링크를 타고 이동합니다.

 

'w'는 마지막 노드이므로, 'woo' 패턴을 찾았습니다!

 

이를 코드로 구현하면 다음과 같습니다.

public class Main {
...
    static ArrayList<String> findPatterns = new ArrayList<>();
    static void search(String text) {
        Node parentNode = rootNode;
        for (char t : text.toCharArray()) {
            int c = t - 'a';
            while (parentNode.childs[c] == null) {
                parentNode = parentNode.failLink;
            }
            
            parentNode = parentNode.childs[c];
            findPatterns.addAll(parentNode.outPuts);
        }
    }   
...
}

 

전체 코드와 개선점

---

public class Main {
    static ArrayList<String> findPatterns = new ArrayList<>();
    static Node rootNode = new Node();
        
    static class Node {
        Node[] childs;
        ArrayList<String> outPuts;
        Node failLink;
        
        public Node() {
            childs = new Node[26];
            outPuts = new ArrayList<>();
            failLink = null;
        }
    }
    
    static void makeTrie (String pattern) {  
        Node node = rootNode;
        
        for (char c : pattern.toCharArray()) {
            int t = c - 'a';
            if(node.childs[t]==null) {
                node.childs[t] = new Node();
            }
            
            node = node.childs[t];
        }
        node.outPuts.add(pattern);
    }
    
    static void makeFailLink() {
        Queue<Node> q = new LinkedList<>();        
        for (int i = 0; i<rootNode.childs.length; i++) {
            if(rootNode.childs[i] != null) {
                q.offer(rootNode.childs[i]);
                rootNode.childs[i].failLink = rootNode;
            } else {
                rootNode.childs[i] = rootNode;
            }
        }
        
        while (!q.isEmpty()) {
            Node curNode = q.poll();

            for (int i = 0; i<26; i++) {
                if(curNode.childs[i]!= null) {
                    Node lastFailLink = curNode.failLink;                    
                    while (lastFailLink.childs[i] == null) {
                        lastFailLink = lastFailLink.failLink;
                    }
                    
                    curNode.childs[i].failLink = lastFailLink.childs[i];
                    curNode.childs[i].outPuts.addAll(lastFailLink.childs[i].outPuts);
                    
                    q.offer(curNode.childs[i]);
                } 
            }
        }
    }
    
    static void search(String text) {
        Node parentNode = rootNode;
        for (char t : text.toCharArray()) {
            int c = t - 'a';
            while (parentNode.childs[c] == null) {
                parentNode = parentNode.failLink;
            }
            
            parentNode = parentNode.childs[c];
            findPatterns.addAll(parentNode.outPuts);
        }
    }
    
   
    public static void main(String[] args) {    
        String[] patterns = new String[] {"www", "woo","jun"};
        for (int i = 0; i<patterns.length; i++) {
            makeTrie(patterns[i]);
        }
        
        makeFailLink();
        
        String text = "myungwoo";
        search(text);
        
        System.out.println(findPatterns);
    }
}

 

결과

 

위 코드는 각 노드에서 26 크기의 배열을 사용하고 있어 메모리 측면에서 비효율적입니다.

이를 개선하기 위해 해시맵을 사용하는 방법이 있습니다.

해시맵을 사용하면 패턴에 사용되는 문자에 대해서만 메모리를 할당하므로, 메모리 낭비를 줄일 수 있습니다.

 

참고자료

---

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

[BOJ] 백준 9250번 문자열 집합 판별 (Java)