입력에서 최소 정규 표현식을 도출합니다.

문자열을 건네 줄 때 "예"또는 "아니오"를 반환하는 원격 "에이전트"가 있습니다. 이 에이전트와 통신하는 것은 비용이 많이 드는 일이므로 긍정적이고 부정적인 피드백을받은 정규 표현식을 반복적으로 만들 수있는 라이브러리를 찾고 그 구조에 대해 지능적으로 알고 싶습니다. 이것은 내가 보내는 쪽에서 답을 캐쉬 할 수있게 해준다.입력에서 최소 정규 표현식을 도출합니다.

예를 들어 에이전트를 "양호"로 쿼리하고 "예"라고 가정합니다. 초기 파생 된 정규 표현식은 "좋은"것이어야합니다.

"goop"으로 쿼리하고 "예"라고 가정 해 봅니다. 파생 된 정규 표현식이 "good goop"이 아니라 "goo [dp]"가 될 것으로 기대합니다.

등등.

파생 된 정규식에서 역 추적이나 다른 비선형 시간 연산이 필요하지 않습니다. 아마도 생성 된 정규식은 DFA가 될 것입니다. 누구든지이 C/C++ 정규 표현식 라이브러리를 인식 할 수 있습니까? 양자 택일로, 이것이 어리석은 생각이고 내 진짜 문제에 대한 더 나은 해결책이 또한 유용한 이유가 될 것이다.

출처

2011-09-28 tgoodhart

이 질문을 "주어진 문자열 세트와 일치하는 최소 정규식을 찾는 방법"을 간단하게 할 수 있습니까? –

@Kerrek : 대충 생각 하겠지만 새 문자열을 추가하고 점진적으로 구성하는 것이 효율적이어야하는 것이 바람직합니다. –

@R 올바른 내용입니다. 배치 모델 대신 즉시 새 문자열을 추가하는 것이 중요합니다. – tgoodhart

상황에 뭔가가 빠지지 않는 한, 메모리가 멍청한 캐시를 구현할만큼 충분히 싸다고 생각합니다. 예를 들어 unordered_map <std::string, bool>입니다. 해시 맵을 작성하기 때문에 빌드가 훨씬 쉬울뿐만 아니라 더 빠를 것입니다. 이 단점은 bazillion 다른 키를 사용하여 원격 서비스를 쿼리 할 경우 가장 좋은 방법이 아닐 수 있습니다.

출처

2011-09-28 23:54:04 Matt

정규 표현식 대신 Trie을 사용할 수 있습니다.

그런 다음 각각의 새 문자열에 대해 각 문자에 대해 노드 하나를 걸으십시오. 나는 또한 당신이 마커 문자가 문자열의 끝을 원한다고 생각한다. 일단이 문자에 도달하면 노드가 존재하면 예/아니오 응답을 갖는다.

출처

2011-09-29 00:01:49 Trejkaz

이것은 테이블의 한 옵션입니다. 하지만 반복을 제외하면 좋을 것입니다. – tgoodhart

@tgoodhart 반복을 분해함으로써, 동일한 문자에 대한 연속적인 노드를 갖는 대신에 카운트가 첨부 된 노드 또는 트라이의 전체 부분만을 가질 수 있습니다. – pmr

@pmr 전체 부품. 이상적으로 생성 된 정규식은 "abcabc (? : abc)"대신 "abc {2,3}"와 같을 것입니다. – tgoodhart

입력에서 최소 정규 표현식을 도출합니다.

답변

관련 문제