구문 분석 기 Tokenizer
단어 분리기 의 역할 은 문자열 을'단어'목록 으로 바 꾸 는 것 입 니 다.다음은'대학 생활'이라는 입력 을 예 로 들 어 설명 하 겠 습 니 다.
'대학 생활'이라는 말 에 단 어 를 나 누 면 보통 하나의 단어 기 는 세 단계 로 나 누 어 이 루어 진다.
(1)'대학 생활'이라는 말의 모든 단 어 를 찾 아서 하나의 집합 으로 한다.즉,[대,대학,대학생,학,학생,학생,생활,생활]
(2)첫 번 째 단계 에서 얻 은 집합 에서'대학 생활'이라는 말 을 조합 할 수 있 는 모든 부분 을 찾 습 니 다.즉,:
[대,학,생,활]
[대,학,생활]
[대,학생,일]
[대학,학생,생활]
[대학,생활]
[대학생,일]
(3)두 번 째 단계 에서 발생 하 는 모든 부분 에서 가장 가능 한 것 을 최종 분사 결과 로 선택한다.
첫 번 째 단계 에 필요 한 집합 을 얻 기 위해 서 는 보통 사전 이 필요 하 다.대부분의 단어 기 는 사전 을 바탕 으로 단 어 를 나 누 는 것 이다.그러면 지금 우리 에 게 작은 사전 이 있다 고 가정 하 자.[대학,대학생,학습,학습 기,학생,화,생활,생활].먼저'대학 생활'이라는 말 에서 이 사전 안의 모든 단어 와 일치 해 야 한다.어떤 학생 들 의 머 릿 속 에 이런 과정 이 나타 날 수 있다.
public class Demo1{
//
static Set<String> dic = new HashSet(){{
add(" ");
add(" ");
add(" ");
add(" ");
add(" ");
add(" ");
add(" ");
add(" ");
}};
//
static List<String> getAllWordsMatched(String sentence){
List<String> wordList = new ArrayList<>();
for(int index = 0;index < sentence.length();index++){
for(int offset = index+1; offset <= sentence.length();offset++){
String sub = sentence.substring(index,offset);
if(dic.contains(sub)){
wordList.add(sub);
}
}
}
return wordList;
}
public static void main(String[] args){
String sentence = " ";
getAllWordsMatched(sentence).forEach(System.out::println);
}
}대학.
대학생.
학생.
살다
여기까지 우 리 는 사전에 서 단 어 를 찾 는 임 무 를 완벽 하 게 완수 한 것 같다.그러나 실제 분사 기의 사전 은 수 십 만 내지 수백 만 개의 어 휘 량 이 있 는데 위의 이런 알고리즘 을 사용 하면 성능 이 너무 낮다.이러한 일치 하 는 알고리즘 을 효과적으로 실현 하 는 방법 은 매우 많 습 니 다.다음은 간단하게 소개 하 겠 습 니 다.
2.AC 자동 동기(Aho-Corasick automation)
AC 자동 동 기 는 자주 사용 하 는 다 중 모드 매 칭 알고리즘 으로 사전 트 리(trie 트 리)의 데이터 구조 와 KMP 알고리즘 의 실패 지침 사상 을 바탕 으로 실현 되 며 좋 은 성능 을 가지 고 실현 하기 가 매우 간단 합 니 다.
2.1 사전 트 리(trie 트 리)
바 이 두 백과 가 트 리 나무 에 대한 설명 을 참조 하 세 요.트 리 나 무 는 나무 구조 이 고 해시 나무의 변종 입 니 다.전형 적 인 응용 프로그램 은 대량의 문자열 을 통계,정렬,저장 하 는 데 사용 되 기 때문에 검색엔진 시스템 에서 텍스트 주파수 통계 에 자주 사용 된다.문자열 의 공공 접 두 사 를 이용 하여 조회 시간 을 줄 이 고 불필요 한 문자열 비 교 를 최대한 줄 이 며 해시 트 리 보다 조회 효율 이 높다 는 것 이 장점 이다.
다음은[대학,대학생,학습,학습 기,학생,생기,생활,생활]이라는 사전 이 저 장 된 trie 나무 입 니 다.
이것 은 각 단어의 n 번 째 글자 로 n 번 째 부터 n 번 째+1 층 노드 사이 의 경로 인 해시 값 을 만 드 는 해시 트 리 로 볼 수 있 으 며,각 노드 는 실제 저장 할 단어 입 니 다.
지금 은 이 나무 로 대학 생활 의 매 칭 을 한다.여전히'대'자로 부터 일치 합 니 다.다음 그림 에서 보 듯 이 뿌리 노드 부터 가장 왼쪽 경 로 를 따라 큰 글자 에 일치 합 니 다.'대'노드 를 따라'대학'에 일치 할 수 있 고 계속 일치 하면'대학생'에 일치 할 수 있 습 니 다.그 후에 사전 에'대'자로 시작 하 는 단어 가 없어 서[대학,대학생]1 차 일치 가 끝 났 습 니 다.
"학"자의 시작 단어 와 계속 일치 합 니 다.방법 은 이전 단계 와 같 습 니 다.[학생]과 일치 할 수 있 습 니 다.
'생'과'살 아 있 는'글자 의 시작 단어 가 계속 일치 하면'대학 생활'이 사전에 서 의 단어 가 모두 밝 혀 진다.
이 를 통 해 알 수 있 듯 이'대'자로 시작 하 는 단 어 를 예 로 들 면 첫 번 째 매 칭 방식 은 사전에'대','대학','대학','대학 생활'을 포함 하 는 지 4 차례 조회 해 야 하 는데 트 리 를 사용 해 조회 할 때'대학생'이라는 단 어 를 찾 으 면 해당 라운드 매 칭 을 중단 하고 매 칭 횟수 를 줄 이 며 매 칭 할 문장 이 길 어 질 수록이런 성능 우 위 는 더욱 뚜렷 해진 다.
2.2 실패 지침
위의 일치 과정 을 살 펴 보면'대학생'이라는 단어 와 일치 한 후에 사전 에'대'자로 시작 하 는 다른 단어 가 존재 하지 않 기 때문에 이번 라운드 가 끝나 면'학'자로 시작 하 는 단어 와 계속 일치 할 것 이다.이때 다시 뿌리 노드 로 돌아 가 계속 일치 해 야 한다.만약 에 이때'대학생'노드 에 지침 이 있 으 면'학생'노드 를 가리 킬 수 있다.한 번 의 조 회 를 줄 일 수 있다.유사 하 게'학생'과 일치 한 후에'학생'노드 에 지침 이 있 으 면'생활'노드 를 가리 킬 수 있 고 한 번 의 조 회 를 줄 일 수 있다.현재 단계 노드 와 일치 하지 않 습 니 다.점프 해 야 할 지침 은 실패 지침 입 니 다.실패 지침 을 만 든 나 무 는 다음 과 같 습 니 다.
그림 의 빨간색 선 은 실패 지침 입 니 다.아래쪽 노드 가 일치 하지 않 을 때 어느 노드 로 넘 어가 서 계속 일치 해 야 하 는 지 를 가리 키 고 있 습 니 다.
실패 포인터 생 성 과정 은 보통:
1.트 리 트 리 만 들 기.
2.BFS 각 노드(DFS 를 사용 할 수 없습니다.각 노드 의 실패 포인터 가 생 성 될 때 이전 노드 의 실패 포인터 가 모두 생 성 되 었 는 지 확인 해 야 하기 때 문 입 니 다).
3.뿌리 노드 의 하위 노드 의 실패 지침 은 뿌리 노드 를 가리킨다.
4.다른 노드 는 부모 노드 의 실패 포인터 가 가리 키 는 노드 의 하위 노드 가 이 노드 글자 와 같은 노드 가 있 는 지,있 으 면 실패 포인터 가 이 노드 를 가리 키 고 없 으 면 글자 가 같은 노드 나 루트 노드 를 찾 을 때 까지 아까 의 과정 을 반복 합 니 다.
조회 과정 은 다음 과 같 습 니 다.
이 코드 를 실행 하면 출력 합 니 다:
대학.
대학생.
학생.
살다
사전 에 있 는 모든 문장 에 나타 난 단어 와 일치 한 후에 두 번 째 단 계 를 계속 합 니 다.얻 은 집합 에서'대학 생활'이라는 문장 으로 조합 할 수 있 는 모든 부분 을 찾 습 니 다.그러나 이곳 에서 작은 문제 에 부 딪 혔 다.위 에서 찾 아 낸 네 단어 중'대학'과'생활'이라는 두 단어 만 이'대학 생활'이라는 문장 을 구성 할 수 있 고'대학생'과'생활'은 일치 하 는 단어 에서 연결 할 수 있 는 단 어 를 찾 을 수 없다.현실 에 서 는 사전 이 모든 어 휘 를 포괄 하기 어려워 이런 경우 가 종종 발생 한다.여기에 일치 하 는 단어의 집합 에 한 글 자 를 추가 로 넣 을 수 있 습 니 다.이것 은 새로운 집합 을 얻 었 습 니 다.
[대학,대학생,학생,생활]U[대학,학,학생,생활]=[대학,대학생,학생,생활,대학,학,학생,생활]
그림 으로 이 집합 을 나타 내 는 단어 조합 을 사용 할 수 있 습 니 다.시작 노드 부터 끝 노드 까지 의 모든 경 로 는 모든 단어 방식 입 니 다.
최종 분사 결과
그렇다면 이런 가능 한 분사 조합 중 어떤 것 을 최종 분사 결과 로 선택해 야 할 까?대부분의 분사 기의 주요 차이 도 여기에 나타난다.일부 분사 기 는 사용자 가 선택 할 수 있 도록 다양한 분사 전략 을 제공 할 수 있다.예 를 들 어 최소 단어 전략 은 그림 에서 종료 노드 에 도달 할 수 있 는 모든 경로 중 가장 짧 은(최소 노드 를 거 친)하 나 를 선택 하 는 것 이다.위의 이 방향 도 에 대해 가장 짧 은 경 로 는 두 가지 가 있 는데 그것 이 바로'대학,생활'과'대학생,생활'의 최종 분사 가 끝나 면 이 두 가지 경로 중에서 하 나 를 선택한다.이런 선택 방법 은 가장 간단 하고 성능 도 높 지만 정확성 이 비교적 떨어진다.사실 곰 곰 이 생각해 보면 어떤 분사 전략 을 쓰 든 가장 정확 할 수 있 는 것,즉 확률 이 가장 높 은 것 을 고 르 려 는 목적 이 있다 는 것 을 알 수 있 습 니 다."대학 생활 은'대,학,활'으로 나 눌 확률 이 P(대)P(학|대)P(생|대,학)P(생|대,학)로 나 뉘 는데 그 확률 을 계산 하려 면'대'의 출현 확률 을 알 아야 한다.'대'가 나타 날 때'학'이 나타 날 확률,'대','학'이 동시에 나타 날 때'생'의 확률,'대','학'이 나타 날 확률 을 알 아야 한다.'생'이 동시에 나타 날 때'살 아 있 는'확률 이 나타난다.이러한 출현 확률 은 대량의 문장 으로 구 성 된 텍스트 라 이브 러 리 에서 통계 할 수 있 지만 문 제 는 사전 이 임의의 N 개의 단어 가 나 올 때 단어 W 가 나 올 확률 을 기록 하려 면 M 개의 어 휘 를 저장 하 는 사전 은 M^N 급 의 관계 데 이 터 를 저장 해 야 하기 때문에 이 사전 은 너무 커서 보통 N 의 크기 를 제한 합 니 다.일반적으로 N 은 2 또는 3 입 니 다.조건 확률 을 계산 할 때 앞의 2~3 단어 만 고려 하 는 것 은 마 르 코 프 체인 을 바탕 으로 한 간소화 이다.N 이 2 일 때 는 이원 모델,N 이 3 일 때 는 3 원 모델 이 라 고 한다.50 만 단어 가 있 는 사전 의 이원 모델 은 50 만*50 만 개의 관 계 를 필요 로 한다.이것 도 상당히 큰 급 이다.이 를 압축 하거나 다른 유사 형식 으로 전환 할 수 있다.이 부분 은 상대 적 으로 복잡 하 다.여기 서 설명 을 하지 않 고 더 간단 한 형식 을 사용한다.모든 단어의 등장 이 독립 적 인 사건 이 라 고 가정 하면 P(대,학,생,활)=P(대)P(학)P(생)P(생)P(활)를 사용한다.이 확률 을 계산 하려 면 각 단어의 출현 확률,한 단어의 출현 확률=단어 가 나타 나 는 횟수/텍스트 라 이브 러 리 에서 단어의 총량 만 알 아야 한다.그러면 이전에 사 용 했 던 사전 을[대학 5,대학생 4,학습 6,학습 기 3,학생 5,화 8,생활 7,생활 2]로 업데이트 한 다음 의 숫자 는 이 단어 들 이 텍스트 라 이브 러 리 에 나타 난 횟수 이 고 텍스트 라 이브 러 리 에서 단어의 문 제 는 바로 이 단어 들 이 나타 난 횟수 의 합 이다=5+4+6+3+5+8+7+2=40
그러면 P(대학,생활)=P(대학)P(생활)=5/40*7/40
P(대학생,일)=P(대학생)P(일)=4/40*0/40 이곳 에 문제 가 생 겼 다.사전 에 존재 하지 않 는 단어 에 대한 확률 은 0 이다.이 로 인해 전체 곱 하기 가 0 이다.이것 은 불합리 하 다.이런 상황 에 대해 부 드 럽 게 처리 할 수 있다.쉽게 말 하면 사전 에 존재 하지 않 는 단어의 출현 횟수 를 1 로 설정 할 수 있다.그래서 P(대학생,살다=P(대학생)P(살다)=4/40*1/40
최종 적 으로 가장 가능 한 단어 조합 을 고 를 수 있다.이로써 세 번 째 단 계 는 끝났다.
이상 은 바로 단어 기 Tokenizer 의 상세 한 내용 입 니 다.단어 기 Tokenizer 에 관 한 자 료 는 저희 의 다른 관련 글 을 주목 하 세 요!
좋은 웹페이지 즐겨찾기
