실제로 가장 빠른 문자열 검색 알고리즘은 무엇입니까?

수행하려는 검색 유형에 따라 다릅니다. 각 알고리즘은 특정 유형의 검색에서 특히 잘 작동하지만 검색 컨텍스트를 명시하지 않았습니다.

다음은 검색 유형에 대한 몇 가지 일반적인 생각입니다.

• Boyer-Moore : 패턴을 사전 분석하고 오른쪽에서 왼쪽으로 비교하여 작동합니다. 불일치가 발생하면 초기 분석을 사용하여 패턴이 w.r.t로 얼마나 멀리 이동할 수 있는지 결정합니다. 검색되는 텍스트. 이것은 특히 긴 검색 패턴에 적합합니다. 특히 텍스트의 모든 문자를 읽을 필요가 없기 때문에 하위 선형 일 수 있습니다.

• Knuth-Morris-Pratt : 또한 패턴을 사전 분석합니다. 하지만 패턴의 초기 부분에서 이미 일치 된 항목을 다시 사용하여 다시 일치하지 않도록합니다. 알파벳이 작은 경우 (예 : DNA 염기) 검색 패턴에 재사용 가능한 하위 패턴이 포함될 가능성이 더 높기 때문에이 방법은 매우 잘 작동 할 수 있습니다.

• Aho- Corasick : 많은 전처리가 필요하지만 여러 패턴에 대해 필요합니다. 동일한 검색 패턴을 계속해서 찾고 있다는 것을 알고 있다면 검색 당 한 번이 아니라 한 번만 패턴을 분석해야하므로 다른 것보다 훨씬 좋습니다.

따라서 CS에서 평소와 같이 전체 최고 에 대한 명확한 답은 없습니다. 이는 당면한 작업에 적합한 도구를 선택하는 문제입니다.

최악의 추론에 대한 또 다른 참고 사항 : 최악의 경우를 생성하는 데 필요한 검색 유형을 고려하고 이것은 귀하의 경우에 정말로 관련이 있습니다. 예를 들어 O(mn) Boyer-Moore 알고리즘의 최악의 복잡성은 검색 패턴과 각각 하나의 문자 만 사용하는 텍스트 (예 : in aaaaaaaaaaaaaaaaaaaaa)-이와 같은 검색을 빠르게 처리해야합니까?

댓글

• 사용할 전체 영문 알파벳 정도가 있고 질문을 업데이트했습니다. 구걸 할 때 이것으로 시작하지 않아서 죄송합니다.
• 예, 다음과 같은 검색도 빠르게 할 필요가 있습니다. 그
• Z '의 알고리즘과 manachar에 대해서도 설명해 주시겠습니까?

이 질문에 답하기에는 약간 늦었지만 Z-Algorithm가 다른 질문보다 훨씬 빠르다고 생각합니다.최악의 경우 복잡성은 O (m + n)이며 패턴 / 텍스트의 전처리가 필요하지 않습니다. 또한 다른 알고리즘에 비해 코딩도 매우 쉽습니다.

다음과 같은 방식으로 작동합니다.

예를 들어 S ="abaaba" 문자열이 있습니다. i=0 to len(S)-1에 대한 z(i) 값을 찾습니다. 설명을 시작하기 전에 몇 가지 정의를 먼저 설명하겠습니다.

z(i) = 아니요. s(i)의 프리픽스와 일치하는 S의 프리픽스 문자 수.

s(i) = ith 접미사 S.

다음은 s = "abaaba" 값.

s(0) = "abaaba" = S s(1) = "baaba" s(2) = "aaba" s(3) = "aba" s(4) = "ba" s(5) = "a" 

각각 z 값

z(0) = 6 = length(S) z(1) = 0 z(2) = 1 z(3) = 3 z(4) = 0 z(5) = 1 

알고리즘에 대한 자세한 이해는 다음 링크를 참조하세요.

http://codeforces.com/blog/entry/3107

https://www.youtube.com/watch?v=MFK0WYeVEag

이제 사전 처리 오버 헤드없이 모든 z 값을 찾으려면 O (N)이 필요합니다. 이제이 논리를 사용하여 주어진 문자열의 패턴을 일치시킬 수 있는지 궁금 할 것입니다.

예를 들어 보겠습니다. Pattern (P) : aba, Text (T) : aacbabcabaad.

P $ T 형식으로 입력합니다. ($– 패턴이나 텍스트로 표시되지 않는 모든 문자입니다. 잠시 후에 $의 중요성을 알게 될 것입니다.)

P$T = aba$aacbabcabaad

우리는 len(P) = 3을 알고 있습니다.

P$T의 모든 z 값은

z(0) = 16 = len(P$T) z(1) = 0 z(2) = 1 z(3) = 0 z(4) = 1 z(5) = 1 z(6) = 0 z(7) = 0 z(8) = 2 z(9) = 0 z(10) = 0 z(11) = 3 z(12) = 0 z(13) = 1 Z(14) = 1 Z(15) = 0 

이제 z(i) = len(P). Ans = 11. 따라서 패턴은 Ans-len(P)-1 = 7에 있습니다. -1는 $ 문자 용입니다.

이제 $ 또는 그러한 특별한 특성은 중요합니다. P = "aaa" 및 T = "aaaaaaa"를 고려하세요. 특수 문자가 없으면 모든 z(i)에 증분 값이 있습니다. 아래 공식을 사용하여 텍스트에서 패턴의 위치를 찾을 수 있습니다.

조건 : z(i)> = len(P) 및 위치 : Ans-len(P). 그러나이 경우 조건은 약간 까다 롭고 혼란스러워집니다. 저는 개인적으로 특별한 캐릭터 기법을 선호합니다.

댓글

• 여기에서 직접 설명해 주시겠습니까? 외부 사이트에 대한 링크를 갖는 것은 정교화하는 데 사용될 수 있지만 답변의 핵심은 다른 사이트에 대한 링크를 따라가는 것이 아니라 답변 자체에 있어야합니다.
• z- 알고리즘은 기본적으로 다음과 같습니다. kmp. 훨씬 빠르지 않은 것 같습니다.
• @ThomasAhle에 동의합니다. 컴퓨팅은 z 전처리입니다. 그래도 ' 좋은 설명입니다. 이 답변으로 인해 KMP 전처리에서 Z 전처리로 변환하는 O(n) 방법을 제시했습니다. 여기

사용 콘텐츠 주소 지정 가능 메모리 , 소프트웨어에서 가상 주소 지정 (문자를 문자로 가리 키기) 형태로 구현됩니다.

이것은 평균적인 문자열 일치 알고리즘에 다소 불필요합니다.

CAM은 최대 약 128 자 패턴 (ASCII 인 경우, 유니 코드 인 경우 64)까지 수많은 패턴을 동시에 일치시킬 수 있습니다. 일치시키려는 문자열의 문자 길이 당 한 번의 호출과 최대 패턴 길이의 길이 당 메모리에서 한 번의 임의 읽기입니다. 따라서 최대 90,000,000 개의 패턴을 동시에 포함하는 100,000 개의 문자 문자열을 분석하는 경우 (이렇게 큰 패턴 수를 저장하는 데 약 128GiB가 필요함) RAM에서 1,280 만 개의 임의 읽기가 필요하므로 1ms 내에 발생합니다.

다음은 가상 주소 지정이 작동하는 방식입니다.

첫 문자를 나타내는 256 개의 시작 주소로 시작하면이 문자는 다음 문자 중 256 개를 가리 킵니다. 존재하지 않으면 저장하지 않습니다.

문자를 문자에 계속 연결하면 가상 주소 지정을 가리키는 128 개의 가상 주소를 갖는 것과 같습니다.

— 작업을하지만 동시에 일치하는 900,000,000 개의 패턴을 얻으려면 마지막으로 추가 할 수있는 트릭이 하나 있습니다. — 이러한 문자 버퍼를 많이 재사용하는 것으로 시작하지만 나중에는 흩어집니다.256 개의 문자를 모두 할당하는 대신 내용을 나열하면 속도가 거의 느려지고 “용량이 100 배 증가합니다. 기본적으로 모든 문자 포인터 버퍼에 1 개의 문자 만 사용되기 때문입니다.” 이스케이프 “).

가장 가까운 이웃 문자열 일치를 얻으려면 병렬로 실행되는 많은 항목이 있고 계층 구조에서 수집하므로 편향되지 않은 오류를 분산시킵니다. 가장 가까운 이웃이 하나만 있으면 “나무의 시작 부분에 편향되어 있습니다.

댓글

• @MagnusRobertCarlWoot gavatar as roucer81, 해시 코드 충돌의 천문학적 우연이거나 동일한 이메일 주소를 가지고 있습니다. 두 계정의 동일한 개인 인 경우 " Google에 문의 " 양식을 사용하여 적절한 크레딧을받을 수 있도록 병합해야합니다. 이 답변에 대한 찬성 투표를 통해 얻은 명성.