python 자연 언어 처리 사전 트 리 지식 총화

사전 나무
자연 언어 처리 에서 문자열 집합 은 자주 사전 트 리 로 저장 되 는데 이것 은 문자열 의 트 리 데이터 구조 입 니 다.사전 트 리 의 모든 변 은 하나의 글자 에 대응 하고 뿌리 노드 에서 아래로 내 려 오 는 경로 로 하나의 문자열 을 구성 합 니 다.
사전 트 리 는 노드 에 문자열 을 직접 저장 하지 않 고 단 어 를 루트 노드 에서 특정한 노드 사이 의 경로 로 보고 종점 노드 에 표 시 를 한다(이 노드 가 끝 났 음 을 나타 낸다).
단 어 를 조회 하려 면 이 경 로 를 따라 뿌리 노드 에서 내 려 가 야 한 다 는 것 을 말한다.표 시 된 노드 에 갈 수 있다 면 이 문자열 이 집합 에 있 음 을 설명 합 니 다.그렇지 않 으 면 설명 이 없습니다.다음 그림 은 사전 트 리 구조의 예시 입 니 다.

위의 그림 에서 보 듯 이 모든 경 로 는 하나의 어휘 이 고 하위 노드 가 없 으 면 이 경로 의 끝 을 판단 할 수 있다.구체 적 으로 다음 표 시 를 비 출 수 있 습 니 다.
단어
경로
환영 하 다.
0-1-2
북경대학
0-3-8
북경
0-3-4-5
북경대학
0-3-4-6-7
사전 나무의 실현 에 대해 서 는 데이터 구 조 를 열심히 배 운 독자 들 이 모두 손 쉽게 잡 을 수 있 을 것 이 라 고 믿 습 니 다.여 기 는 군말 이 아 닙 니 다.한 LP 라 이브 러 리 는 이미 다양한 사전 트 리 를 제 공 했 기 때문이다.
2.DoubleArrayTrieSegment
DoubleArray Trie Segment 류 를 알 기 전에 우 리 는 두 배열 의 사전 책의 개념 을 알 아야 한다.
우 리 는 모두 알 고 있 습 니 다.나무 에서 찾 을 때 우 리 는 보통 2 분 으로 찾 습 니 다.만약 에 특정한 나무의 노드 에 N 개의 노드 가 있다 면 그 복잡 도 는 O(logN)입 니 다.이렇게 한 나무의 옮 겨 다 니 는 것 이 매우 느 릴 것 입 니 다.그래서 두 개의 사전 나무의 개념 이 탄생 했 습 니 다.
두 배열 사전 트 리(DAT)는 상태 전이 복잡 도 를 상수 로 하 는 데이터 구조 다.그럼 컨디션 이 뭐 예요?제 한 된 상태 자동 동기(DFA)를 확인 하 는 측면 에서 볼 때 모든 노드 는 하나의 상태 이 고 상 태 는 현재 조회 한 접 두 사 를 나타 낸다.
부모 노드 에서 하위 노드 로 이동 하 는 과정 은 상태 이동 으로 볼 수 있다.특정한 문자 에 따라 상태 이동 을 하기 전에 우 리 는 부모 노드 에 이 문자 와 하위 노드 의 맵 관 계 를 물 을 것 이다(즉,하나의 경로 의 한 변).만약 에 부모 노드 가 조건 을 만족 시 키 는 변 이 있 으 면 상 태 는 하위 노드 로 이전 합 니 다.그렇지 않 으 면 즉시 실패 하여 조회 할 수 없습니다.모든 전 이 를 성공 적 으로 마 쳤 을 때 우 리 는 마지막 상 태 를 받 아 이 상태 가 최종 상태 인지 물 었 다.그렇다면 이 단 어 를 찾 아 보 세 요.그렇지 않 으 면 사전 에 존재 하지 않 습 니 다.
예 를 들 어 우리 가 첫 번 째 그림 의'베 이 징 대학'을 조회 할 때 상 태 는 0 이 고 북 으로 조회 할 때 상 태 는 3 이 며 베 이 징 으로 조회 할 때 상 태 는 4 이 고 대시 상 태 는 6 이 며 학 창시 상 태 는 7 이 며 마지막 으로 7 에 하위 노드 가 있 는 지 판단 한다.만약 에 이 단어 가 일치 하지 않 으 면 사전 에 없다.예 를 들 어'베 이 징 대'를 조회 하면 어휘 에 없다.
한편,두 배열 사전 은 base 와 check 두 배열 로 구성 되 는데 그 중에서 base 배열 은 노드 이자 상태 이 고 남 은 상태 와 점용 상태 로 나 뉘 며 check 배열 은 모든 요소 로 특정한 상태의 전구 상 태 를 나타 낸다.구체 적 인 공식 은 다음 과 같다.

base[s] + c = t
check[t] =  s

base 트 리 그룹의 s 는 현재 상태의 아래 표 시 를 대표 하고 t 는 전이 상태의 아래 표 시 를 대표 하 며 c 는 입력 문자 의 수 치 를 대표 합 니 다.

base[s] + c = t //        

이전 후 상태 에서 t 로 표시 되 고 부자 관계 가 유일한 것 이기 때문에 현재 요소 의 전구 상 태 를 검사 하여 이전 성공 여 부 를 확인 할 수 있 습 니 다.

check[t] = s //          

이러한 알고리즘 은 전통 적 인 트 리 2 분 에 비해 찾 는 장점 은 하나의 덧셈 만 있 으 면 한 번 의 상태 이전 을 완성 할 수 있 고 상수 시간 만 걸 렸 다 는 것 이다.다음은 두 배열 트 리 의 원리 도(상태 이전 과정 을 주의 깊 게 관찰)를 제시 했다.

두 배열 사전 트 리 의 원 리 를 알 게 되면 DoubleArray Trie Segment 를 배 울 수 있 습 니 다.DoubleArray Trie Segment 는 DAT(두 배열 사전 트 리)에 가장 길 게 일치 하 는 패키지 입 니 다.기본적으로 hanlp.propertes 에서 CoreDictionary Path 가 지정 한 사전 을 불 러 옵 니 다.
대응 하 는 python 코드 는 다음 과 같 습 니 다:

if __name__ == "__main__":
    HanLP.Config.ShowTermNature=False#         
    segment=DoubleArrayTrieSegment()
    print(segment.seg("         ，    Happy"))

실행 후 다음 그림 과 같은 결 과 를 얻 을 수 있 습 니 다.

물론 이것 은 HanLP 가 제공 하 는 기본 사전 입 니 다.자신의 사전 을 불 러 오 거나 앞에서 언급 한 다른 오픈 소스 사전 라 이브 러 리 를 불 러 오 려 면 코드 를 다음 과 같이 바 꿀 수 있 습 니 다.

DoubleArrayTrieSegment(["  1"，"  2"])

그러나 독자 들 이 주 의 를 기 울 였 는 지 모 르 겠 습 니 다.위의 영어 happy 는 우리 에 게 하나의 자모 로 뜯 어 주 었 습 니 다.그러나 사실은 이것 은 전체 입 니 다.만약 에 여기 서 숫자 로 바 꾸 는 것 도 하나의 숫자 라면 어떻게 뜯 지 못 하 게 합 니까?
코드 를 보 겠 습 니 다.

if __name__ == "__main__":
    HanLP.Config.ShowTermNature=True
    segment=DoubleArrayTrieSegment()
    segment.enablePartOfSpeechTagging(True)
    print(segment.seg("         ，    Happy"))

enablePartOfSpeechTagging 함 수 는 숫자 와 영문 인식 을 활성화 하 는 동시에 쇼 TermNature 를 True 로 바 꾸 어 출력 결 과 를 관찰 하 는 것 을 의미 합 니 다.

여 기 는 우리 가 앞에서 쓴 알고리즘 출력 과 똑 같 고 분 리 된 어휘 와 어휘의 표기 속성 이 있 습 니 다.
3.AhoCorasickDoubleArray TrieSegment
비록 두 배열 의 사전 나 무 는 대량의 데 이 터 를 옮 겨 다 닐 수 있 지만 데이터 가 비교적 길 고 이런 긴 어휘 가 비교적 많다 면 예 를 들 어'하늘 에 명령 을 받 고 장수 영창'이 하나의 어 휘 를 계산 하면 처리 하 는 시간 이 복잡 하고 시간 이 많이 걸린다.그래서 우 리 는 ACDAT 를 이용 해 옮 겨 다 녀 야 한다.
여기 서 블 로 거들 은 그 원 리 를 설명 하지 않 는 다.너무 긴 지면 에 한계 가 있 기 때문에 관심 이 있 는 사람 은 나무 구조의 처 리 를 전문 적 으로 배 울 수 있다.독 자 는 그 원 리 를 알 고 언제 더 블 배열 로 옮 겨 다 니 고 언제 ACDAT 로 옮 겨 다 니 면 된다.한편,한 LP 가 봉 인 된 ACDAT 의 실현 류 는 AhoCorasick DoubleArray Trie Segment 이다.
다음은 AhoCorasick DoubleArray TrieSegment 를 실현 합 니 다.코드 는 다음 과 같 습 니 다.

if __name__ == "__main__":
    HanLP.Config.ShowTermNature = False
    segment = JClass("com.hankcs.hanlp.seg.Other.AhoCorasickDoubleArrayTrieSegment")()
    print(segment.seg("         ，        "))

실행 후 효 과 는 다음 과 같 습 니 다.

주의해 야 할 것 은 python 의 HanLP 가 AhoCorasick DoubleArray Trie Segment 류 를 제 공 했 지만 독자 들 이 시도 해 볼 수 있 습 니 다.교체 후 실행 이 잘못 되 고 콘 솔 에 서 는 seg 함수 가 없 음 을 알려 줍 니 다.한편,HanLP 라 이브 러 리 는 자바 기반 으로 개발 되 었 기 때문에 실제 프로젝트 에 서 는 JClass 를 사용 하여 자바 류 를 불 러 와 실전 을 진행 합 니 다.python 의 HanLP 라 이브 러 리 는 자바 보다 운행 속도 가 두 배 느 리 지만 python 의 장점 은 상대 적 으로 간단 하고 다른 프로그램의 클래스 를 호출 할 수 있 기 때문에 속 도 는 python 이 자바 류 를 인용 하여 호출 하면 속도 가 같 습 니 다.
python 자연 언어 처리 사전 트 리 지식 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 python 사전 트 리 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!