일치하는 문자열 패턴에 가장 적합한 (런타임 성능) 응용 프로그램 또는 패턴 또는 코드 또는 라이브러리가 무엇입니까?

Question

나는 문자열 패턴과 일치하는 적절한 방법을 찾아 내려고 노력했습니다. 내가하려는 일에 관해서 최대한 많은 정보를 제공하기 위해 최선을 다할 것입니다.

가장 간단한 것은 특정 패턴이 있으며 우리는이 패턴 중 어느 것이 완전하게 또는 부분적으로 주어진 요청과 일치하는지 알고 싶습니다. 지정된 패턴은 거의 변하지 않습니다. 요청 량은 하루에 약 10K이지만 결과는 최대한 빨리 제공되어야하므로 런타임 성능이 최우선 순위입니다.

저는 C#에서 어셈블리 컴파일 정규 표현식을 사용하려고 생각했지만 올바른 방향으로 향하고 있는지 확실하지 않습니다.

시나리오 :
데이터 파일 :
는 이제 데이터가 알려진 스키마 형식의 XML 요청으로 제공되는 가정하자. 5 ~ 20 행의 데이터가 있습니다. 각 행에는 10-30 개의 열이 있습니다. 각 열은 사전 정의 된 패턴의 데이터 만 가질 수도 있습니다. 예 :

1. A1- "3 자리"다음에 "이 올 것입니다." "2 자리"로 follwed - [0-9] {3} [0-9] {2}

2. A2-는 수 "숫자"로 follwoed "1 개 문자"것 -. [AZ] [0 -9] {4}

   샘플은 것 같은 뭔가 :

<Data> 
    <R1> 
    <A1>123.45</A1> 
    <A2>A5567</A2> 
    <A4>456EV</A4> 
    <An>xxx</An> 
    </R1> 
</Data> 

규칙 파일 :

Rule ID A1     A2  
1001  [0-9]{3}.45  A55[0-8]{2} 
2002  12[0-9].55   [X-Z][0-9]{4} 
3055  [0-9]{3}.45  [X-Z][0-9]{4} 

규칙 위치 - 규칙 ID를 일종의 비트 마스크로 저장하려고합니다.
그래서 규칙 ID는 다음 문자열 위치로

Rule ID  Location (from left to right) 
1001   1 
2002   2 
3055   3 

패턴 파일을 나열됩니다 : 이제

Column Pattern    Rule Location 
A1  [0-9]{3}.45   101 
A1  12[0-9].55    010 
A2  A55[0-8]{2}   100 
A2  [X-Z][0-9]{4}   011 

하자 (이 최종 구조, 그러나 다만 생각하지 않습니다)의 어떻게 든 가정 (시간을 절약하기 위해 검색을 어떻게 제한 할 것인지 확실하지 않음) 정규 표현식을 실행하고 A1 열만이 A1 패턴과 A2 패턴과 일치하는지 확인합니다. 나는 이렇게 "규칙 위치"

Column Pattern    Rule Location 
A1  [0-9]{3}.45   101 
A2  A55[0-8]{2}   100 

• 에 대한 때라도 reults를 끝낼 것 그리고 loctions의 각 나에게 위치 (1) 제공 - 1001 - 완전한 일치를.
• 각 루프에서 XOR을 수행 위치 3 - 3055 - 부분 일치를 제공합니다.
  1001 : 내가 찾고 있어요 최종 reulsts는

(즉 이 부분 일치 잘못입니다 결과 로 1001과 3055을 반환 것 때문에, 의도적는 OR을 수행하지 입니다) 일치하는 결과에 대한 설명

012 : 부분 일치

시작 Edit_1 - - 3055 완전한 일치


• 전체 일치 - 주어진 규칙의 패턴 중 이 모두 일치하면 입니다.

• 부분 일치 - 해당 규칙에있는 패턴 중 이 모두 일치하지 않을 경우 이 일치하지만 최소한 하나의 패턴이 과 일치합니다.

  예 전체 일치 (AND) :
  규칙 ID 1001이 A1 (101) 및 A2 (100)와 일치합니다. 101과 100에서 첫 번째 문자를 보면 "1"입니다. AND-1 AND 1을 수행하면 결과는 1입니다. 따라서 위치 1, 즉 1001은 완전한 일치입니다.

  XOR (Exmple Partial Match) :
  A1 (101)에 대해 규칙 ID 3055가 일치합니다. 101과 100에서 마지막 문자를 보면 "1"과 "0"입니다. XOR-1 XOR 0을 수행하면 결과는 1입니다. 따라서 위치 3 즉 3055는 부분 일치입니다.
  끝 Edit_1

입력 :
데이터는 XML 요청 일종의 제공됩니다. 하나의 데이터 노드 만 사용하는 100K 데이터 노드 또는 100K 요청의 경우 큰 요청 일 수 있습니다.
규칙 :
작성 및 편집하기 쉽게 일치 값을 일종의 패턴으로 저장해야합니다. 대략 100K 개의 규칙이 있다고 가정 해 봅시다.

출력 :
완전하고 부분적으로 일치하는 규칙을 알아야합니다.

기본 설정 :
나는 C#에서 할 수있는 많은 코딩 작업을 원합니다. 그러나 성능이 크게 향상되면 다른 언어를 사용할 수 있습니다.

"입력"과 "출력"은 필자의 요구 사항이며 "출력"을 관리하는 방법은 중요하지 않습니다. 그것은 빠르다, 각 데이터 노드가 약 1 초 안에 처리되어야한다고 말할 수 있어야한다.

질문 :

1. 이 거기에 기존의 패턴이나 framewroks이 작업을 수행하려면?
2. Regex 올바른 경로를 사용하고 있습니다 어셈블리를 구체적으로 컴파일했습니다 정규식?
3. Regex를 사용하면 결국 A1 패턴에 대해서만 지정할 수 있습니다. 은 A1 열과 일치합니까?
4. 비트 유형 패턴에서 규칙 위치를 지정하는 경우 ANDs 및 XOR이 100K charcter 길어지면 어떻게 처리합니까?

내가 생각해야하는 제안이나 옵션이 있습니다. 그들이 완전히 일치하는 경우에만 당신을 알려줍니다 정규 표현식 API는, 그들이 부분적으로 일치하지

Answer 1

감사합니다 .... 따라서 정규 표현식 API의 변형으로 여러 개의 정규 표현식을 한 번에 일치시킬 수 있으며 결국에는 완전히 일치하는 부분과 부분적으로 일치하는 부분을 알 수 있습니다. 이상적으로는 런타임에 컴파일을 피할 수 있도록 패턴 세트를 사전 컴파일 할 수있게하는 것입니다.

그런 다음 AI 패턴과 A2 패턴, A2 패턴과 A2 패턴을 비교할 수 있습니다. 그런 다음 부분 및 정규 표현식 목록으로 무언가를하십시오.

나쁜 소식은이 소프트웨어를 구현 한 소프트웨어가 없다는 것입니다.

좋은 소식은 http://swtch.com/~rsc/regexp/regexp1.html에 설명 된 전략이이를 구현할 수 있어야한다는 것입니다. 특히 State 세트를 확장하면 동시에 여러 패턴의 현재 상태에 대한 정보를 가질 수 있습니다. 이 State 세트의 확장 세트는 더 복잡한 상태 다이어그램이되고 (더 많은 물건을 추적하기 때문에) 최종적으로 더 복잡한 반환 (일련의 상태 세트를 반환)이지만 런타임은 생성되지 않습니다 하나의 패턴 또는 50과 일치하는지 여부에 관계없이 조금 변경되었습니다.