AC 자동 동기 python 구현

얼마 전에 사형 과 기계 학습 경 기 를 할 때 사형 께 서 저 에 게 1.5w 라벨 이 20w 데이터 에 나타 난 횟수 와 일치 하 라 고 하 셨 습 니 다. 처음에 저 는 정규 표현 식 으로 1.5w 라벨 과 20w 데 이 터 를 이중 순환 으로 옮 겨 다 녔 습 니 다. 대충 계산 해 보 니 모든 라벨 이 달 리 는 데 6 일 정도 걸 렸 습 니 다. (이것 은 저 를 절망 하 게 합 니 다)나중에 사형 께 서 저 에 게 AC 자동 기 를 사용 하 라 고 말씀 하 셨 습 니 다. 저 는 오후 내 내 AC 자동 기 를 실현 하지 못 하 는 것 을 보 았 습 니 다. 어 쩔 수 없 이 사형 은 시간 을 내 서 제 임 무 를 완성 할 수 밖 에 없 었 습 니 다.
며칠 간 의 모색 끝 에 나 는 AC 자동 동 기 를 대충 실현 했다.
먼저 AC 자동 동기 가 무엇 인지 소개 합 니 다. Aho - Corasick automation 은 1975 년 에 베 어 실험실 에서 생 겨 난 유명한 다 중 모드 매 칭 알고리즘 입 니 다.다 중 모드 매 칭 알고리즘, 내 작업 (다 중 태그 매 칭 문제) 에 완벽 하 게 부합 합 니 다. 간단하게 말 하면 AC 자동 동 기 는 사전 트 리 + kmp 알고리즘 + 어 울 리 지 않 는 지침 입 니 다.
python 사전 트 리 만 들 기 (실제로는 트 리 만 들 기) python 에 구조 체 가 없 기 때문에 트 리 의 노드 는 하나의 클래스 로 표시 합 니 다.

class node(object):

    def __init__(self):
        self.next = {}       #     ，           
        self.fail = None     #    ，   AC      
        self.isWord = False  #  ，              
        self.word = ""       #      

다음은 AC 자동 동 기 를 정의 하 는 클래스 입 니 다.

class ac_automation(object):

    def __init__(self):
        self.root = node()  #     

사전 트 리 만 들 기:

def add(self, word):
        temp_root = self.root
        for char in word:                           #        
            if char not in temp_root.next:          #          ，         
                temp_root.next[char] = node()       
            temp_root = temp_root.next[char]        #        
        temp_root.isWord = True                     #    ，                 
        temp_root.word = word                       #      

fail 포인터 만 들 기:

def make_fail(self):
        temp_que = []                                    #  BFS        
        temp_que.append(self.root)
        while len(temp_que) != 0:
            temp = temp_que.pop(0)
            p = None
            for key,value in temp.next.item():
                if temp == self.root:                     #        fail    
                    temp.next[key].fail = self.root
                else:
                    p = temp.fail
                    while p is not None:                  #  fial          
                        if key in p.next:                 #      fail       ，   
                            temp.next[key].fail = p.fail
                            break
                        p = p.fail
                    if p is None:                         #     fail     ，    
                        temp.next[key].fail = self.root
                temp_que.append(temp.next[key])

다 중 모드 일치:

def search(self, content):
        p = self.root
        result = []
        currentposition = 0       #           

        while currentposition < len(content):
            word = content[currentposition]
            while word in p.next == False and p != self.root:    #     ，    
                p = p.fail

            if word in p.next:
                p = p.next[word]
            else:
                p = self.root

            if p.isWord:                 #         ，       
                result.append(p.word)

            currentposition += 1

위의 세 가 지 를 결합 하면 AC 자동 동기 의 유형 이다.

class ac_automation(object):

    def __init__(self):
        self.root = node()

    def add(self, word):
        temp_root = self.root
        for char in word:
            if char not in temp_root.next:
                temp_root.next[char] = node()
            temp_root = temp_root.next[char]
        temp_root.isWord = True
        temp_root.word = word

    def make_fail(self):
        temp_que = []
        temp_que.append(self.root)
        while len(temp_que) != 0:
            temp = temp_que.pop(0)
            p = None
            for key,value in temp.next.item():
                if temp == self.root:
                    temp.next[key].fail = self.root
                else:
                    p = temp.fail
                    while p is not None:
                        if key in p.next:
                            temp.next[key].fail = p.fail
                            break
                        p = p.fail
                    if p is None:
                        temp.next[key].fail = self.root
                temp_que.append(temp.next[key])

    def search(self, content):
        p = self.root
        result = []
        currentposition = 0

        while currentposition < len(content):
            word = content[currentposition]
            while word in p.next == False and p != self.root:
                p = p.fail

            if word in p.next:
                p = p.next[word]
            else:
                p = self.root

            if p.isWord:
                result.append(p.word)

            currentposition += 1
        return result

테스트:

ac = ac_automation()
ac.add('   ')
ac.add('   ')
ac.add('666')
ac.add('    ')


ac.search('              ，              ')

['   ', '   ']

AC 자동 동 기 는 정말 좋 은 물건 입 니 다!
참고:https://github.com/metadata1984/pyAhocorasick