네트워크 스트림의 청크에서 문자열 일치

Question

서버의 들어오는 데이터를 문자열로 검색 한 다음 가능한 한 데이터를 버퍼링하지 않고 다른 문자열로 바꿔야하는 상황을 처리해야합니다.

들어오는 데이터는 여러 청크가 될 수 있습니다. 따라서 주어진 문자열이 여러 청크로 분할 될 가능성이 있습니다. 예를 들어 문자열이 'abc'이면 청크는 1 : 'aaab'& 청크 2 : 'cbbb'일 수 있습니다. 그런 다음 첫 번째 청크에서 'a'를 일치시킨 후 다음 청크에서 'b'와 일치하는 것이 있는지 기다려야합니다. 즉, 이제 첫 번째 청크를 버퍼링해야합니다. 또는 적어도 일치하는 첫 번째 청크의 문자는 두 번째 청크에 문자열의 나머지가 포함되어 있는지 파악할 때까지 버퍼링해야합니다.

그렇지 않으면 첫 번째 청크로 돌아가 문자 b에서 일치를 다시 시작해야합니다.

응용 프로그램 제약 조건을 감안할 때 버퍼링은 가능한 한 피해야합니다. 최소한의 버퍼링으로이를 수행하는 방법이 있습니까? 나에게 이것은 여러 상황에서 직면하게 될 일반적인 문제인 것처럼 보이지만 불행히도 검색 후 해결책이나 방향을 찾지 못했습니다.

Answer 1

유한 상태 머신을 살펴볼 수 있습니다. Here's 몇 가지 예가 포함 된 텍스트입니다.

"ABCD"패턴을 감지한다고 가정 해주십시오. 이 경우에는 다섯 개 가지 상태를 가질 것 :

없음 문자는

A는

AB는

이

ABC가 발견되었습니다

ABCD가 발견 된 것으로 확인되었습니다 발견 된 발견 된

기계 자체는 다음과 같이 보일 것입니다 :

  IN:A   IN:B   IN:C   IN:D 
STATE_NONE ---> STATE_A ---> STATE_AB ---> STATE_ABC ---> STATE_ABCD 
^  |    |   |    |    
|  |else   |else  |else   | 
|  v    v   v    v 
|-----<---------------<------------<-------------< 

기계는 STATE_NONE에서 꺼지고 입력을 한 번에 하나씩 처리합니다. 예를 들어 현재 상태가 STATE_A이고 B가 도착하면 STATE_AB로 이동합니다. 하지만 STATE_A에서 "C"를 얻으면 STATE_NONE으로 이동합니다. 탐지를 위해 각 단계에서 기계의 현재 상태 만 저장하면됩니다. 그러나 감지 된 패턴을 바꾸려면 각 상태에서 STATE_NONE에서 현재 상태로 가져온 마지막 몇 바이트를 저장해야합니다.

편집 :

내 상태 시스템에 몇 가지 상태 전환이 없습니다. STATE_AB에서 "A"가 도착하면 STATE_NONE이 아니라 STATE_A로 돌아 가야합니다. A, ABC 및 ABCD도 마찬가지입니다. A가 도착하면 STATE_A로 돌아갑니다. 그렇지 않으면 "ABCABCD"와 같은 패턴을 놓치게됩니다.

Answer 2

정확하게 이해하면 검색 할 패턴을 완전히 하나의 청크로 만들거나 패턴 및 청크 크기에 따라 둘 이상의 청크에 걸쳐 적용 할 수 있습니다. 패턴이 두 개의 청크에있는 경우, 첫 번째 척에서 발견 된 모든 패턴 접두어 (접미어로)를 추적 한 다음 두 번째 청크에서 해당 패턴 접미사를 접두어로 검색해야합니다. 여기서 각 패턴에 여러 패턴 검색이 필요할 수 있으며 여기에서 접미사 트리를 사용할 수 있습니다. 새 척을 받으면 이미 조사 할 패턴을 모두 알고 있습니다.우리는 그 덩어리의 접미어 트리를 만들고, 모든 검색을 수행하고, 필요에 따라 처리하고, 다음 덩어리로 이동하고, 동일한 작업을 수행 할 수 있습니다.