정규식 생성기/감속기?

Question

나는 현재 우리가 가지고있는 운영상의 어려움에 대해 동료로부터 흥미로운 질문을 받았다. 그리고 이것을 자동화하는 데 도움이 될만한 것이 있다면 (유틸리티/라이브러리/알고리즘) 무엇인가 궁금하다.

리터럴 값 목록 (우리의 경우에는 URL 임)이 있다고합시다. 우리가하고자하는 것은,이리스트에 기초하여 모든 문자 그대로의 항목들과 일치하는 하나의 정규식을 생각해내는 것입니다.

그래서, 내 목록 인 경우 :

는

http://www.example.com 
http://www.example.com/subdir 
http://foo.example.com 

가장 간단한 대답은

^(http://www.example.com|http://www.example.com/subdir|http://foo.example.com)$ 

그러나 이것은 데이터의 많은 대형 얻을, 우리는 우리가 유지하려는 길이 제한이 아래에.

현재 우리는 정규식을 수동으로 작성하지만 이것은 잘 확장되지 않으며 다른 사람의 시간을 잘 사용합니다. 모든 소스 값과 일치하는 길이가 최적 인 정규식을 찾기 위해 소스 데이터를 분해하는 자동화 된 방법이 있습니까?

Answer 1

Aho-Corasick 일치 알고리즘은 여러 문자열과 일치하는 유한 오토 마톤을 구성합니다. 당신은 오토마타를 그것과 동등한 정규 표현식으로 변환 할 수 있지만, 오토 마톤을 직접 사용하는 것이 더 간단합니다. (알고리즘이하는 것입니다.)

Answer 2

나는 한 걸음 물러서서 자신이하고있는 일과 그 이유에 대해 생각하는 것이 합리적이라고 생각합니다.

모든 URL을 일치 시키려면 해당 URL 만 일치시키고 다른 URL은 일치시키지 않으려면 정규식이 필요하지 않습니다. 아마도 URL 목록의 각 항목에 대해 정확한 문자열 비교를 수행하여 허용 가능한 성능을 얻을 수 있습니다.

정규식이 필요한 경우, 조정하려는 변수의 차이점은 무엇입니까? 나는. 입력의 어느 부분이 축 어적으로 일치해야하며, 어디에서 흔들리는 방이 있습니까?

성능상의 이유로 문자열의 고정 된 목록과 일치시키기 위해 정말로 regexp를 사용하려면 예제와 같이 모든 입력 문자열을 함께 묶는 메서드를 작성하기 만하면됩니다 . 장면 뒤에서 regexp 일치를 수행하는 상태 머신은 매우 똑똑하고 일치하는 대안에 공통적 인 (따라서 중복 된) 부분 문자열이있는 경우 더 느리게 실행되지 않습니다.

Answer 3

다른 두 개의 응답에서 큐를 가져 와서 일치시킬 필요가있는 것은 문자열 문자열을 매치 시키거나 (천천히), 문자열에 맞는 간단한 FSM을 구성하는 것이 더 좋습니다 (빠름).

실제로 정규식은 FSM을 만든 다음 입력 내용을 일치시킵니다. 따라서 입력 값이 이전에 알려진 집합의 집합 인 경우에는 자동 생성을 시도하는 대신 FSM을 직접 만들 수 있습니다. 정규식.

Aho-Corasick은 이미 제안되었습니다. 그것은 빠르지 만 구현하기 까다로울 수 있습니다. 어쨌든 Trie에 모든 문자열을 넣은 다음 그 문자열을 대신 쿼리합니다 (전체 문자열과 일치하므로 하위 문자열을 검색하지 않으므로).

Answer 4

세트의 모든 문자열과 비교하려는 경우에만 trie 또는 compressed trie 또는 더 나은 directed acyclic word graph을 사용하십시오. 후자는 URL IMO에 특히 효율적입니다.

하지만 정규식을 포기해야합니다.

Answer 5

Emacs 유틸리티 함수 regexp-opt (source code)은 원하는 문자열을 고정 문자열에서만 사용할 수 있지만 유용한 시작점 일 수 있습니다.

Answer 6

오늘 나는 그것을 조사하고있었습니다. 찾지 못했기 때문에 도구를 만듭니다. kemio.com.ar/tools/lst-trie-re.php

오른쪽에 목록을 넣은 다음 제출하고 왼쪽에 regexp를 가져옵니다. 그것의하지 학대를 수행 var re=new RegExp(/..../,"mib");

하십시오

내가 좋아하는 (내가 JS 파일에 넣어) 단어의 6KB의 목록을 시도하고, 4KB의 정규 표현식을 생산했다.

Answer 7

정규식 자동 생성기는 here입니다. 이 도구에는 웹 인터페이스가 있으며 Genetic Programming을 사용하여 몇 가지 예에서 정규식을 생성합니다. Java 또는 JavaScript 정규식 엔진에 사용할 수있는 구문 중에서 선택할 수 있습니다. 우리의 연구 그룹에 의해 개발되었고 GECCO 2012 회의에서 발표되었습니다.

urls = ['http://www.example.com','http://www.example.com/subdir','http://foo.example.com'] 
as_regex = [hachoir_regex.parse(url) for url in urls] 
reduce(lambda x, y: x | y, as_regex) 

는 다음을 병합을 코드는 먼저 각 URL에 대한 간단한 정규식 유형을 생성

http://(www.example.com(|/subdir)|foo.example.com) 

단순화 된 정규 표현식을 작성

Answer 8

이 작업을 수행하는 쉬운 방법은 파이썬의 hachoir_regex 모듈을 사용하는 것입니다 이 값은 reduce 단계에서 |입니다.