흐름 전송 모델의 문자열 처리

이번에 요즘 유행하는(?)의 흐름 전송 모드에서의 문자열 처리는 간단하게 소개하고 싶습니다. 기술적인 내용을 기대하시는 여러분께 죄송하지만 이번에는 이런 내용을 연구했고 짧은 글입니다.
흐름 전송 모델의 문자열 대조 문제
설명하기 편리하도록 나는 문자열 대조 문제를 집중적으로 토론할 것이다.
스트리밍이라고 해서 전문본이 다 안다고 할 수는 없다. 텍스트는 한 글자씩 오고, 올 때마다 이 위치를 끝 위치로 하는 패턴이 있는지 빠르게 계산해야 한다. 물론 패턴은 미리 주어진 것이고,미리 처리할 수 있다.
그렇다면 이 설정은 이른바 온라인 알고리즘(15일째@hdbn뉴스.에도 언급된 것)이다. 그렇다. 그렇다면 무엇을 가지고 흐르는 전송 알고리즘이라고 부를까? 영역의 제약이다. 통상적으로도안 길이를 선형 구역(앞으로 도안 길이가 $$$O(m)$구역)으로 미리 처리하면 이 문제를 신속하게 해결할 수 있지만 흐름 전송 알고리즘은 욕심이 많아서 고속에서도 이 영역을 줄여야 한다.

그런 짓을 할 수 있겠어?
정리1
온라인 문자열이 문제의 확정 알고리즘과 일치하려면 $\Omega(m)$영역이 필요합니다.
R. Clifford et al., "A Black Box for Online Approximate Pattern Matching ", CPM 2008
예, 결정적 알고리즘은 안 됩니다. 따라서 대화는 난선 알고리즘으로 바뀝니다. 여기는 출력할 확률이 높지만 가끔 오류가 발생할 수 있습니다. 결정적인 것은 정확하게 대답해야 하기 때문에 $O(m)$구역을 사용할 수 없습니다.패턴 자체조차 유지하지 못하는 점을 고려하면 이 결과도 이해할 수 있지만, 실제로는 난선택에도 이 $\Omega(m)$의 영역이 필요하다는 것이다.
문자열 일치 문제의 단점
안심하세요, 2009년 이 문제에 구세주가 나타났습니다.
정리2
영역을 미리 처리한 후, 문자마다 $O (\logm) $시간 처리 모드의 존재를 확인할 수 있습니다. 오류의 확률은 $\rac {1} {n^2} 달러 ($n 달러는 텍스트 길이) 입니다.
B. Porat and E. Porat, "Exact and Approximate Pattern Matching in the Streaming Model ", FOCS 2009
보는 사람이 보면 알 수 있는 정상급 회의를 통과한 논문인데, 그나저나 한 글자 한 글자의 계산 시간을 평균적으로 분석하면 상수 시간이다.
이번에 우리는 기술적인 내용을 언급하지 않고 어떤 부분이 난선되었는지 간단히 설명할 뿐이다. 이것은 부분 문자열의 비교이다. Finger print를 사용한다. 이것은 문자열을 적당한 수치로 바꾸는 것이다. 같은 문자열이라면 숫자는 반드시 같다.어느 정도에 서로 다른 문자열은 같은 값을 가질 수 있다. 즉, 수치를 비교하는 간단한 조작을 통해 문자열을 신속하게 비교할 수 있다.
돌파 후
상술한 결과도 매우 대단한데, 이후에 또 한층 개선되었는데, 뜻밖에도...
정리
영역을 미리 처리하면 문자마다 $O(1)$시간의 처리로 그림의 존재를 판단할 수 있습니다. 오류의 확률은 $\rac{1}{n^{alpha}달러 ($\alpha>0달러) 입니다.
D. Breslauer and Z. Galil, "Real-time Streaming String-matching ", ACM Transactions on Algorithms, 2014
더 이상 할 말이 없습니다. 이것은 문자열 대조 문제입니다.
별문제
위에서 엄밀한 일치 문자열 대조 문제를 간단하게 소개했고 마지막으로 나는 다른 문제에 대해 연구하고 있는 몇 가지 문제를 열거하고 싶다.
k-일치하지 않는 문자열 일치 문제
이 문제는 그림과 같은 길이의 텍스트 부분 문자열과 $k$k 문자가 일치하지 않아도 나타나는 문자열 대조 문제입니다. (예를 들어 ab와abaa는 2 - 일치하지 않거나 3 - 일치하지 않는 문제에서 일치합니다.)실제로 위의 정리2에 소개된 논문에는 최근 결과가 R.Clifford 등 아래 논문에 실렸다.
R. Clifford et al., "The k-mismatch Problem Revisited ", SODA 2016
기타 문제
문자열 대조 문제는 위와 같은 일치하지 않는 대조를 허용하는 것 외에 와일드카드가 포함된 문자열 대조 문제, 매개 변수화된 문자열 대조 문제와 사전 대조 문제 등을 포함하는 유동 알고리즘도 제시했다.
그 밖에 문자열 대조를 제외하고 문자열의 최소 주기, 한명 거리, 회문 구조 등 문제를 계산하는 유동식 전송 모델 알고리즘도 연구했다.
최후
이번에는 짧았지만 여기까지.
유동식 전송 모델 중의 문자열 알고리즘에 대한 연구는 아직도 해야 할 일이 많고 대부분의 성과가 고위층 회의를 통과한 업계에 좋은 분야가 될 수 있다고 생각합니다.
별거 아니지만 읽어주셔서 감사합니다.