대체를 사용하여 몇 개의 정규 표현식을 연결할 수 있습니까?

Question

나는 수천 ~ 20 자의 고유 한 문자열을 검색해야하는 대용량 파일 (수백 MB)이 있습니다.

나는 (string1|string2|string3) 같은 정규 표현식을 일치하는 파이프 교대 메타 문자를 사용하여 검색 프로세스 (한 번에 하나의 문자열을 검색 대) 많은을 줄일 수 있다는 사실을 발견했습니다.

이 척도가 얼마나 잘 적용될 수 있습니까? 얼마나 많은 표현을 이렇게 연결할 수 있습니까? 어떤 시점에서 오버 플로우가 발생합니까? 이 작업을 수행하는 더 좋은 방법이 있습니까?

짧은 내 질문을 유지하기위한 노력의 일환으로 편집

, 나는 이미이 교대 방식을 사용하여 코드를 구현 한 사실을 강조하지 않았고, 나는 그것이 도움이 될 것으로 : 테스트 케이스에 전형적인 데이터 세트를 사용하면 실행 시간이 87 분에서 18 초로 단축되어 O (n * m) 대신 O (n)으로 290x 속도 향상이 가능합니다.

내 질문은 다른 사용자가 더 큰 파일과 더 많은 검색어로 훨씬 더 큰 데이터 세트를 사용하여이 코드를 나중에 실행할 때 어떻게 작동 할 것으로 기대되는지에 관한 것입니다. 최초의 O (n * m) 코드는 13 년 동안 사용 된 기존 코드였으며, 최근 작동 속도가 더 빨라진 게놈 관련 데이터 세트가 최근에 많이 지적되었습니다.

Answer 1

당신은 같은 간단한 정규식이있는 경우 (단어 1 | word2 | ... | 단어 n)를 정규식 엔진은 한 번만 입력을 통해 전달할 수있는 상태 머신을 구성합니다 문자열이 일치하는지 확인하십시오.

사이드 노트 : 이론적 인 컴퓨터 과학에서 "정규 표현식"은 단일 패스가 항상 충분하도록 정의됩니다. 그러나 실용적인 정규 표현식 구현은 정규 표현식 패턴을 구현할 수있는 기능을 추가합니다.이 정규 표현식 패턴은 항상 단일 패스 (see this example)로 구현 될 수 없습니다.

정규 표현식 패턴의 경우에도 엔진에서 거의 확실하게 단일 패스를 사용합니다. 그것은 아마도 여러 번 메모리에서 데이터를 읽는 것보다 더 빠를 것입니다 ... 그리고 디스크에서 여러 번 데이터를 읽는 것보다 훨씬 빠릅니다.

Answer 2

(word1 | word2 | .... | wordn) 형식의 정규 표현식을 사용하려는 경우 연관된 부울 배열을 만들지 않는 이유는 무엇입니까? 그것은 매우 빨라야합니다.

편집

# before the loop, set up the hash 

%words = (
    cat => 1, 
    dog => 1, 
    apple => 1, 
    .... etc 
); 

# A the loop to check a sentence 

foreach $aword (split(/ /, $sentence)) 
    if ($words{$aword}) print "Found $aword\n"; 

Answer 3

정규식의 범위에 대한 이론적 인 제한은 없지만 실제로는 특정 플랫폼 및 설치의 제한 내에서 적합해야합니다. 당신은 당신의 계획이 효과가 있는지 경험적으로 알아야하며, 나는 당신의 결과를보기를 기뻐할 것입니다.

내가 말하고자하는 한 가지는 표현식을 사용하기 전에 별도로 컴파일해야한다는 것입니다. 그 중 하나 또는 /o 옵션을 적용하여 한 번만 컴파일하십시오 (즉, 표현식의 내용이 변경되지 않는다고 약속하십시오). 이 같은 것을

my $re = join '|', @strings; 

foreach my $file (@files) { 
    my $fh = IO::File->new($file, '<') or die "Can't open $file: $!"; 
    while (<$fh>) { 
    next unless /\b(?:$re)\b/io; 
    chomp; 
    print "$_ found in $file\n"; 
    last; 
    } 
}