다 중 정규 표현 식 일치 (다 중 정규 표현 식 일치)

현재 febird 의 자동 라 이브 러 리 는 정규 표현 식 을 지원 하고 있 으 며, 다 중 정규 표현 식 매 칭 을 지원 합 니 다:
M 의 정규 표현 식 을 지정 합 니 다. 정규 표현 식 마다 [0, M) 의 유일한 ID 가 있 습 니 다. 이 알고리즘 은 정규 표현 식 에 DFA 를 생 성 합 니 다.
입력 텍스트 Text 를 하나 더 지정 합 니 다. 길 이 는 T 입 니 다. 최 장 일치 만 가정 하면 이 Text 는 M 개의 정규 표현 식 의 K 개 와 일치 할 수 있 습 니 다.
이 DFA 에서 내 일치 알고리즘 을 실행 하면 O (T + K) 의 시간 복잡 도 에서 K 의 정규 표현 식 을 찾 을 수 있 습 니 다. 이 시간 복잡 도 는 M 과 전혀 관계 가 없습니다. 정보 론의 측면 에서 볼 때 이 알고리즘 이 가장 좋 습 니 다.
Text 에 있 는 모든 N 개의 일치 점 (N < = T) 을 얻 으 려 면 O (T + K1 +... Kn) 가 필요 합 니 다. 그 중에서 키 는 i 번 째 일치 점 이 일치 하 는 정규 표현 식 수 를 표시 합 니 다.
이것 은 아마도 현존 하 는 가장 효율 적 인 이 문 제 를 해결 하 는 알고리즘 일 것 이다. 이전에 나 는 이 문 제 를 해결 하기 어렵다 고 생각 했다. 어 려 운 문자열 문제 가 지금 은 해결 되 었 고 세 계 는 평온 해 졌 다!
처음에 내 가 이 문 제 를 제 기 했 을 때, 만약 내 가 그때 부터 그것 을 해결 하려 고 시도 했다 면, 아마도 영원히 해결 할 수 없 었 을 것 이다!
이 문제 의 최종 해결 은 다른 몇 가지 문제 의 해결 에서 비롯 된 것 이다. 내 가 DAWG 를 완벽 하고 효율적으로 실현 한 후에 나 는 동태 적 인 DAWG 기반 맵 을 어떻게 실현 할 것 인 가 를 생각 하고 있다. ？... 에 있다 자동 동기 의 일부 알고리즘 과 응용 에서 나 는 해결 방안 (붉 은 검 은 나무 색인 번호 와 유사) 을 상 상 했 지만 나중에 곰 곰 이 생각해 보 니 그 방안 은 전혀 통 하지 않 았 다!
그 후에 저 는 구문 주음 문 제 를 생각 하기 시 작 했 습 니 다. 구문 주음 문제 의 난점 은 구문 중의 다 음 자 에 있 습 니 다. 만약 에 한 단어 에 여러 개의 다 음 자가 있다 면 이 문장의 모든 가능 한 주음 수량 은 지수 입 니 다. 만약 에 우리 가 한자 구문 에서 그의 모든 주음 을 얻 으 려 면 이것 은 문제 가 되 지 않 습 니 다. 구문 주음 문 제 는:
한자 구문 집합 과 한자 마다 의 모든 발음 을 지정 합 니 다 (여러 개 일 수 있 습 니 다. 모호 음 을 포함 하면 더 많 습 니 다)
요구: 이 구문 집합 과 한자 주음 에서 데이터 구 조 를 만 들 고 이 데이터 구 조 는 다음 과 같은 기능 을 실현 할 수 있 습 니 다.
      병 음 을 지정 하여 가장 빠 른 속도 로 병 음 에 대응 하 는 단 어 를 찾 습 니 다.
이 문 제 는 처음 만 났 을 때 어렵 고 신경 을 많이 쓰 지 않 았 다. 맵 문제 이기 때문에 그 때 는 내 머 릿 속 에 DAWG 만 DFA 기반 맵 을 실현 할 수 있 었 고 DAWG 는 이런 지수 문 제 를 해결 할 수 없다 는 것 을 알 고 있 었 다.
그 후에 우연히 기회 가 왔 습 니 다. 저도 구체 적 인 동기 가 무엇 인지 기억 이 나 지 않 습 니 다. 저 는 DFA 에 인 터 페 이 스 를 추 가 했 습 니 다. 

int match_key(char delim, string text, function<void(int keylen, string value)> on_match);

delim 은 보통 \ t 입 니 다. 이 인터페이스 에 사용 할 DFA 를 만 들 때 한 줄 (key, value) 텍스트 를 입력 하 십시오: key \ t value
match key 가 \ t 에 부 딪 혔 을 때 일치 하 는 문자열 의 길 이 를 keylen 으로 하고 \ t 뒤의 부분 을 value 로 하고 on match 를 통 해 호출 자 에 게 되 돌려 줍 니 다. 모든 것 을 되 돌려 주 는 것 은 ADFA 에서 같은 key 가 여러 value 에 대응 하 는 것 이 자 연 스 러 운 일이 기 때 문 입 니 다. 한 마디 로 하면 사용자 로 서 는 매우 간단 합 니 다.효과 적 인 인터페이스 입 니 다. 또한, 자동 동기 생 성 은 분 리 된 일반적인 프로그램 (adfa build) 입 니 다. 이것 은 가장 간단 한 생태 를 형성 합 니 다. adfa build 는 텍스트 파일 에서 DFA 바 이 너 리 파일 을 생 성하 고, 온라인 서버 프로그램 에서 DFA 바 이 너 리 파일 을 불 러 오고 match key 를 호출 합 니 다. 각각 다른 서버 프로그램 에 addfa build 를 따로 쓸 필요 가 없습니다!
그리고 나 서 나 는 이것 이 주음 문 제 를 해결 할 수 있다 는 것 을 곧 깨 달 았 다. 관건 은 그 DFA 를 생 성 하 는 것 이다. 가장 간단 한 방법 은 구문 집합 에서 하나의 (pinyin, 한자) pair 를 생 성 하 는 것 이다. 여기 서 key 는 병 음 이 고 한 자 는 value 이다. 한 단어 에 다 음 자가 있 으 면 여러 개 (key, value) 를 생 성 하 는 것 이다.pair, 같은 value 에 대응 하 는 key 수 를 상관 하지 않 습 니 다. 다 음 자가 아 닌 지수 개 일 수 있 습 니 다. 바보 같이 이것 만 (key, value)pair 는 adfa build 프로그램 에 출력 되 었 습 니 다. 최종 적 으로 그 DFA 를 생 성 할 수 있 을 것 입 니 다. 또한 최소 화 된 DFA 입 니 다. 이 DFA 생 성 과정 은 Onfly Minimize 이기 때문에 메모리 사용량 이 폭발 하지 않 습 니 다. 하지만 메모리 가 폭발 하지 않 고 시간 은 지수 급 입 니 다!
이 문 제 는 저 를 오랫동안 괴 롭 혔 습 니 다. 그 동안 저 는 밤낮으로 생각 했 습 니 다. 지수 문 제 를 해결 할 수 없 었 습 니 다. 그 러 던 어느 날, 목욕 을 할 때 저 는 갑자기 NFA 를 매개체 로 한 다 는 것 을 깨 달 았 습 니 다. 왜냐하면 저 는 Jan Daciuk 의 Onfly ADFA Minimization 알고리즘 을 일찍 실 현 했 기 때 문 입 니 다. match key 가 저 에 게 영감 을 준 후에 어느 날 갑자기 기발 한 생각 이 떠 올 랐 습 니 다. match key 의 de 와 결합 되 었 습 니 다.lim, Daciuk 의 알고리즘 에 대해 이론 적 으로 일반화 되 었 습 니 다. add adfa tail, 이 adfa tail 은 복잡 한 DAG 구 조 를 가 질 수 있 습 니 다. 만약 에 그 여러 개의 가능 한 주음 을 이 adfa tail 에 넣 으 면 문 제 는 절반 이 해결 되 고 나머지 절반 은 DFA 의 반전 입 니 다. 간단 한 일 입 니 다!
………………
…………
……
그 다음 에 영감 이 계속 오 면 다 정규 표현 식 이 일치 합 니 다. 모든 정규 표현 식 에 delim + ID 를 추가 하면 대부분의 문제 가 해결 되 고 나머지 절반 은 순수한 공정 기술 문제 입 니 다.
그 다음 에 최적화 와 일반화 문제 가 생 겼 습 니 다. 지금까지 제 DFA 다 정규 일치 알고리즘 은 정규 표현 식 의 submatch 를 얻 을 수 있 습 니 다.
더 많은 것 을 알 고 싶 으 시 면 참고 하 십시오: 다 정규 표현 식 일치 도구 의 용법