가장 빠른 서브스트링 검색 알고리즘은 무엇입니까?

가장 빠른 서브스트링 검색 알고리즘은 무엇입니까?

자, 그럼 바보처럼 들리지는 않겠네요. 문제/요구 사항을 좀 더 명확하게 설명하겠습니다.

• 니들(패턴)과 건초 스택(검색 텍스트)은 모두 C 스타일의 늘 종단 문자열입니다.길이 정보는 제공되지 않습니다.필요에 따라 계산해야 합니다.
• 함수는 첫 번째 일치로 포인터를 반환해야 합니다.NULL일치하는 것을 찾을 수 없는 경우.
• 실패 사례는 허용되지 않습니다.즉, 스토리지 요건이 일정하지 않은(또는 일정하지 않은) 알고리즘에는 할당 실패에 대한 폴백 케이스가 필요합니다(폴백 케어의 퍼포먼스는 최악의 퍼포먼스에 기여합니다).
• 구현은 C로 진행되지만 코드 없이 알고리즘(또는 이러한 알고리즘에 대한 링크)에 대한 적절한 설명도 괜찮습니다.

...그리고 "최고속"이라는 의미도 있습니다.

• 결정론O(n)어디에n= 건초 더미 길이. (그러나 일반적으로 다음과 같은 알고리즘의 아이디어를 사용할 수 있습니다.)O(nm)(예를 들어, 롤링 해시)가 보다 견고한 알고리즘과 조합되어 결정론적 정보를 얻을 수 있는 경우O(n)결과)를 참조해 주세요.
• 실행하지 않음(측정 가능, 몇 개의 클럭)if (!needle[1])특히 가장 일반적인 경우일 가능성이 높은 매우 짧은 바늘에 대해서는 순진한 무차별적인 힘 알고리즘보다 더 나쁘다.(무조건 과도한 전처리 오버헤드는 좋지 않습니다.병리적인 바늘의 선형 계수를 개선하려고 하기 때문에 가능한 바늘을 희생합니다.)
• 임의의 니들 및 건초 더미를 지정하면 널리 구현된 다른 알고리즘과 동등하거나 더 나은 성능(검색 시간 50% 이하)을 얻을 수 있습니다.
• 이러한 조건과는 별개로, 저는 "가장 빠른" 정의의 끝을 열어두고 있습니다.적절한 답변은 "가장 빠른" 접근방식을 고려하는 이유를 설명해야 합니다.

현재 구현 속도는 glibc의 Two-Way 구현 속도보다 약 10~8배 느립니다(입력 속도에 따라 다름).

업데이트: 현재 최적의 알고리즘은 다음과 같습니다.

• 길이가 1인 바늘의 경우,strchr.
• 길이가 2-4인 바늘의 경우 기계어를 사용하여 2-4바이트를 한 번에 비교합니다.비트 시프트를 사용하여 16비트 또는 32비트 정수로 바늘을 프리로드하고 반복할 때마다 건초 스택에서 오래된 바이트/새로운 바이트를 사이클합니다.건초 스택의 모든 바이트는 정확히 한 번 읽혀지며 0(문자열 끝) 및 16비트 또는 32비트 비교에 대한 체크가 발생합니다.
• 길이가 4보다 큰 바늘의 경우 창의 마지막 바이트에만 적용되는 잘못된 시프트 테이블(Boyer-Moore 등)과 함께 Two-Way 알고리즘을 사용합니다.1kb 테이블을 초기화할 때의 오버헤드를 피하기 위해 많은 중간 길이의 니들에서는 순손실이 발생할 수 있으므로 시프트 테이블 내의 어떤 엔트리가 초기화되는지 비트어레이(32바이트)를 유지하고 있습니다.설정되지 않은 비트는 니들에 나타나지 않는 바이트 값에 해당하므로 전체 니들 길이 이동이 가능합니다.

제 마음속에 남아 있는 큰 의문점은 다음과 같습니다.

• 불량 교대표를 더 잘 활용할 수 있는 방법이 있을까요?Boyer-Moore는 뒤로(오른쪽에서 왼쪽으로) 스캔하여 가장 잘 활용하지만, Two-Way는 왼쪽에서 오른쪽으로 스캔해야 합니다.
• 일반적인 경우(메모리 부족 상태 또는 2차 성능 조건 없음)에 대해 유일하게 실행 가능한 후보 알고리즘은 정렬된 알파벳에 대한 양방향과 문자열 일치입니다.하지만 다른 알고리즘이 최적의 경우 쉽게 감지할 수 있는 경우가 있을까요?확실히 많은 사람들이O(m)(어디서)m공간 알고리즘의 바늘 길이)는m<100선형 시간만 필요로 하는 바늘에 대한 쉬운 테스트가 있다면 최악의 경우 2차 알고리즘을 사용하는 것도 가능할 것이다.

보너스 포인트:

• 니들과 건초 더미가 둘 다 올바른 형식의 UTF-8이라고 가정하면 성능을 향상시킬 수 있습니까? (바이트 길이가 다양한 문자의 경우 올바른 형식의 것은 니들과 건초 더미 사이에 몇 가지 문자열 정렬 요건을 부과하고 헤드 바이트가 일치하지 않을 경우 자동으로 2-4 바이트 시프트를 허용합니다.그러나 이러한 제약으로 인해 이미 제공되는 최대 접미사 계산, 우수한 접미사 이동 등을 넘어서는 것이 있습니까?)

주의: 실제로 얼마나 뛰어난 성능을 발휘하는지는 몰라도 대부분의 알고리즘에 대해서는 잘 알고 있습니다.여기 좋은 레퍼런스가 있습니다.그러면 알고리즘에 대한 레퍼런스를 코멘트나 코멘트로 계속 제공하지 않게 됩니다.http://www-igm.univ-mlv.fr/ ~ lecroq / string / index . http :

2011년에 출판된 Dany Breslauer, Roberto Grossi 및 Filippo Mignosi의 "Simple Real-Time Constant-Space String Matching" 알고리즘일 가능성이 높다고 생각합니다.

업데이트:

2014년에 저자들은 다음과 같은 개선 사항을 발표했다.최적의 패킹 스트링 매칭을 실현합니다.

저는 이 토론에서 인용된 기술 보고서를 보고 놀랐습니다. 저는 위의 Sustik-Moore라는 이름의 알고리즘의 저자 중 한 명입니다. (논문에서는 이 용어를 사용하지 않았습니다.)

여기서 강조하고 싶은 것은 알고리즘의 가장 흥미로운 점은 각 문자를 한 번에 검사한다는 것을 증명하는 것이 매우 간단하다는 것입니다.이전 Boyer-Moore 버전에서는 각 문자가 최대 3회, 최대 2회까지 검토된다는 것을 증명했으며, 이러한 증명은 더 많이 관련되어 있었다(서류의 인용 참조).따라서 나는 이 변형을 제시하고 연구하는 데 있어서도 교훈적인 가치를 발견한다.

이 백서에서는 이론적 보증을 완화하면서 효율성을 지향하는 추가적인 변화도 설명합니다.그것은 짧은 논문이고, 내 생각에 그 자료는 일반 고등학교 졸업생들이 이해할 수 있어야 한다.

우리의 주된 목표는 이 버전을 더 개선할 수 있는 다른 사람들에게 알리는 것이었습니다.문자열 검색은 매우 다양하며, 이 아이디어가 이점을 가져올 수 있는 모든 것을 생각할 수 없습니다. (고정 텍스트와 변경 패턴, 고정 패턴 다른 텍스트, 전처리 가능/불가능, 병렬 실행, 큰 텍스트에서 일치하는 부분 집합 찾기, 오류 허용, 근접 일치 등)

바늘과 건초 더미로 구성된 테스트 라이브러리를 구축합니다.브루트 포스를 포함한 여러 검색 알고리즘에 대한 테스트를 프로파일링합니다.데이터에 가장 적합한 것을 선택합니다.

Boyer-Moore는 좋은 접미사 표와 함께 나쁜 문자 표를 사용합니다.

Boyer-Moore-Horspool은 잘못된 문자 테이블을 사용합니다.

Knuth-Morris-Pratt는 부분 일치 테이블을 사용합니다.

Rabin-Karp은 실행 중인 해시를 사용합니다.

이들 모두 서로 다른 수준으로 비교를 줄이기 위해 오버헤드를 교환하기 때문에 실제 성능은 바늘과 건초 더미의 평균 길이에 따라 달라집니다.초기 오버헤드가 많을수록 입력이 길수록 좋습니다.바늘이 매우 짧으면, 맹렬한 힘이 이길지도 모른다.

편집:

다른 알고리즘은 기본 쌍, 영어 구문 또는 단일 단어를 찾는 데 가장 적합합니다.모든 입력에 대해 하나의 최선의 알고리즘이 있다면, 그 알고리즘은 공개되었을 것입니다.

다음의 작은 테이블을 생각해 보세요.물음표마다 최적의 검색 알고리즘이 다를 수 있습니다.

                 short needle     long needle
short haystack         ?               ?
long haystack          ?               ?

이 그래프는 각 축의 입력 범위가 짧은 그래프에서 긴 그래프여야 합니다.이러한 그래프에 각 알고리즘을 플롯 했을 경우, 각 알고리즘의 시그니처는 다릅니다.일부 알고리즘은 패턴의 반복이 많아 유전자 검색과 같은 용도에 영향을 미칠 수 있습니다.전체 성능에 영향을 미치는 다른 요인으로는 동일한 패턴을 여러 번 검색하고 동시에 다른 패턴을 검색하는 것이 있습니다.

샘플 세트가 필요하다면 구글이나 위키피디아 같은 사이트를 긁어모은 후 결과 페이지에서 html을 삭제할 것입니다.검색 사이트의 경우 단어를 입력한 다음 제안된 검색 구문 중 하나를 사용합니다.필요에 따라서, 몇개의 다른 언어를 선택합니다.웹 페이지를 사용하면 모든 텍스트가 중간 정도의 짧은 텍스트이므로 긴 텍스트를 얻을 수 있도록 페이지를 합치십시오.공용 도메인 서적, 법적 기록 및 기타 많은 텍스트 본문도 찾을 수 있습니다.또는 사전에서 단어를 선택하여 무작위로 콘텐츠를 생성할 수도 있습니다.그러나 프로파일링의 요점은 검색할 콘텐츠의 종류에 대해 테스트하는 것이므로 가능하면 실제 샘플을 사용하십시오.

나는 짧고 길게 모호하게 남겼다.바늘은 짧게는 8자 이하, 중간은 64자 이하, 길게는 1k 이하라고 생각합니다.건초 더미는 짧게는 2^10 이하, 중간은 2^20 이하, 길게는 2^30 문자라고 생각합니다.

가장 빠른 것은 현재 S에 의한 EPSM입니다.파로와 O.M. 쿨렉치.https://smart-tool.github.io/smart/ 를 참조해 주세요.

SIMD SSE 4.2(x86_64 및 aarch64)용으로 최적화된 "Exact Packed String Matching"입니다.모든 사이즈에서 안정적이고 최적의 성능을 발휘합니다.

링크한 사이트에서는 199개의 고속 문자열 검색 알고리즘과 일반 알고리즘(BM, KMP, BMH)이 상당히 느립니다.EPSM은 이러한 플랫폼에서 언급된 다른 모든 기능보다 뛰어납니다.그것도 최신작이에요.

업데이트 2020: EPSM은 최근 AVX용으로 최적화되었으며 여전히 가장 빠릅니다.

가장 빠른 서브스트링 검색 알고리즘은 컨텍스트에 따라 달라집니다.

1. 알파벳 크기(예를 들어 DNA 대 영어)
2. 바늘 길이

2010년 논문 '정확한 문자열 매칭 문제: 포괄적인 실험 평가'에서는 51개의 알고리즘(알파벳 크기와 바늘 길이)에 대한 런타임 표를 제공하고 있으므로 상황에 가장 적합한 알고리즘을 선택할 수 있습니다.

이러한 알고리즘에는 모두 C 구현과 테스트 스위트가 있습니다.

http://www.dmi.unict.it/~faro/smart/smartms.http://http://www.dmi.unict.it/

사용자가 가리키는 http://www-igm.univ-mlv.fr/~lecroq/string/index.http 링크는 가장 잘 알려져 있고 조사된 문자열 매칭 알고리즘의 훌륭한 소스이자 요약입니다.

대부분의 검색 문제에 대한 해결책에는 전처리 오버헤드, 시간 및 공간 요구사항과 관련된 트레이드오프가 포함됩니다.모든 경우에서 단일 알고리즘이 최적화되거나 실용적인 것은 아닙니다.

스트링 검색의 특정 알고리즘을 설계하는 것이 목적이라면, 그 외의 내용은 무시해 주세요.일반화된 스트링 검색 서비스 루틴을 개발하려면 다음을 시도해 보십시오.

이미 언급한 알고리즘의 구체적인 장점과 단점을 검토하는 데 시간을 할애해 주십시오.관심 있는 문자열 검색 범위 및 범위를 포함하는 알고리즘 세트를 찾는 것을 목표로 검토를 수행합니다.그런 다음 분류기 함수를 기반으로 프런트 엔드 검색 셀렉터를 구축하여 주어진 입력에 가장 적합한 알고리즘을 목표로 합니다.이렇게 하면 작업을 수행하는 데 가장 효율적인 알고리즘을 사용할 수 있습니다.이는 알고리즘이 특정 검색에 매우 적합하지만 성능이 저하되지 않을 때 특히 효과적입니다.예를 들어, 무차별적인 힘은 길이가 1인 바늘에 가장 적합하지만 바늘 길이가 늘어날수록 빠르게 감소합니다. 따라서 서스티크-무어 알고리딤은 (작은 알파벳에 비해) 더 효율적일 수 있습니다. 바늘이 길고 큰 경우에는 KMP 또는 Boyer-Moore 알고리즘이 더 나을 수 있습니다.이는 가능한 전략을 설명하기 위한 예에 불과합니다.

다중 알고리즘 접근법은 새로운 아이디어가 아닙니다.몇 개의 상용 Sort/Search 패키지에 채용되어 있다고 생각합니다(예를 들어 메인프레임에서 일반적으로 사용되는 SYNCSORT는 몇 가지 정렬 알고리즘을 구현하고 휴리스틱스를 사용하여 주어진 입력에 가장 적합한 것을 선택합니다).

예를 들어, 본 문서에서 설명한 것처럼 각 검색 알고리즘은 성능에 큰 차이를 가져올 수 있는 여러 가지 변형이 있습니다.

서비스를 벤치마킹하여 추가 검색 전략이 필요한 영역을 분류하거나 선택기 기능을 보다 효과적으로 조정할 수 있습니다.이 방법은 빠르거나 쉽지는 않지만 잘하면 매우 좋은 결과를 얻을 수 있습니다.

보다 빠른 "일치하는 단일 문자 검색"(ala)strchr) 알고리즘입니다.

중요사항:

• 이러한 함수는 (선행|추적) 0의 수/카운트를 사용합니다.gcc컴파일러 고유-__builtin_ctz이러한 기능은 이 작업을 수행하는 명령이 있는 기계(예: x86, ppc, arm)에서만 빠릅니다.

• 이들 함수는 타깃아키텍처가 32비트 및 64비트의 비정렬 부하를 실행할 수 있다고 가정합니다.타겟 아키텍처가 이 기능을 지원하지 않는 경우 읽기를 올바르게 정렬하기 위해 몇 가지 시작 로직을 추가해야 합니다.

• 이러한 기능은 프로세서 중립입니다.대상 CPU에 벡터 명령이 있으면 더 나은 작업을 수행할 수 있습니다.예를 들어, 다음 함수는 SSE3를 사용하며 스캔된 바이트를 XOR로 수정하여 다음 이외의 바이트를 찾을 수 있습니다.0. Mac OS X 10.6 (x86_64)가 가동되는 2.66GHz Core 2 노트북에서 수행된 벤치마크:

  • 843.433 MB/s (용)strchr
  • 2656.742 MB/s (용)findFirstByte64
  • 13094.479 MB/s (용)strlen

...32비트 버전:

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (_x == 0u)   ? 0 : (__builtin_clz(_x) >> 3) + 1; })
#else
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu);                    (__builtin_ctz(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte32(unsigned char *ptr, unsigned char byte) {
  uint32_t *ptr32 = (uint32_t *)ptr, firstByte32 = 0u, byteMask32 = (byte) | (byte << 8);
  byteMask32 |= byteMask32 << 16;
  while((firstByte32 = findFirstZeroByte32((*ptr32) ^ byteMask32)) == 0) { ptr32++; }
  return(ptr + ((((unsigned char *)ptr32) - ptr) + firstByte32 - 1));
}

... 및 64비트 버전:

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (_x == 0ull) ? 0 : (__builtin_clzll(_x) >> 3) + 1; })
#else
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full);                    (__builtin_ctzll(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte64(unsigned char *ptr, unsigned char byte) {
  uint64_t *ptr64 = (uint64_t *)ptr, firstByte64 = 0u, byteMask64 = (byte) | (byte << 8);
  byteMask64 |= byteMask64 << 16;
  byteMask64 |= byteMask64 << 32;
  while((firstByte64 = findFirstZeroByte64((*ptr64) ^ byteMask64)) == 0) { ptr64++; }
  return(ptr + ((((unsigned char *)ptr64) - ptr) + firstByte64 - 1));
}

2011/06/04 편집 OP는 코멘트 중에 이 솔루션에 「불능의 버그」가 있는 것을 지적하고 있습니다.

읽기 권한 없이 매핑되지 않은 페이지 또는 페이지에 액세스할 수 있는 검색 바이트 또는 널 터미네이터를 통해 읽을 수 있습니다.문자열 함수가 정렬되지 않으면 큰 읽기를 사용할 수 없습니다.

이는 기술적으로 사실이지만 코멘트에서 OP가 제안하는 방식을 포함하여 1바이트보다 큰 청크로 동작하는 거의 모든 알고리즘에 적용됩니다.

전형적인strchr구현은 순진하지 않지만 당신이 제공한 것보다 훨씬 효율적입니다.가장 널리 사용되는 알고리즘에 대해서는 http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord 를 참조해 주세요.

얼라인먼트 자체와도 전혀 관계가 없습니다.실제로 이는 사용 중인 대부분의 일반적인 아키텍처에서 논의된 동작을 유발할 수 있지만 이는 마이크로아키텍처 구현 세부사항과 더 관련이 있습니다. 즉, 정렬되지 않은 판독값이 4K 경계(일반적으로)에 걸쳐 있는 경우 다음 4K 페이지 경계에 매핑되지 않은 경우 해당 판독값이 프로그램 종료 장애를 일으킵니다.

그러나 이는 답변에 제시된 알고리즘의 "버그"가 아닙니다. 이 동작은 다음과 같은 기능이 있기 때문입니다.strchr그리고.strlen을 받아들이지 않다length검색 크기를 제한하는 인수입니다.검색 중char bytes[1] = {0x55};이 설명에서는 4K VM 페이지 경계의 맨 끝에 배치되어 다음 페이지는 매핑 해제되어 있습니다.strchr(bytes, 0xAA)(어디서)strchr바이트 어 어 타임 구현)도 같은 방법으로 크래시 됩니다.에 대해서도 마찬가지입니다.strchr친척사촌strlen.

미포함length인수. 고속 알고리즘에서 바이트 단위 알고리즘으로 언제 전환해야 하는지 알 수 없습니다."버그"는 "할당 크기 초과"로 읽혀질 가능성이 높으며, 이는 기술적으로 다음과 같습니다.undefined behavior다양한 C 언어 표준에 따라, 그리고 다음과 같은 것에 의해 오류로서 플래그가 지정될 것입니다.valgrind.

요약하면, 이 응답 코드와 OP에 의해 지적된 코드와 같이 보다 큰 바이트 청크로 동작하지만, 바이트의 정확한 읽기 시멘틱스가 없으면 "버기"가 될 수 있습니다.length"마지막 읽기"의 모서리 대소문자를 제어하는 인수.

이 답변의 코드는 대상 CPU가 고속일 경우 자연스러운 CPU 워드 크기 청크의 첫 번째 바이트를 빠르게 찾을 수 있는 커널입니다.ctz지시와 같다.올바르게 정렬된 자연 경계 또는 어떤 형태로든 동작하도록 하는 등의 추가는 간단합니다.lengthbound: 고속 커널에서 벗어나 느린 바이트 단위 체크로 전환할 수 있습니다.

OP는 코멘트에도 다음과 같이 기술되어 있습니다.

ctz 최적화에 대해서는 O(1) tail 동작의 차이밖에 없습니다.작은 문자열로 성능을 향상시킬 수 있습니다(예:strchr("abc", 'a');하지만 어떤 큰 줄의 줄은 확실히 아니에요.

이 진술이 사실인지 아닌지는 해당 마이크로아키텍처에 크게 좌우됩니다.표준 4단계 RISC 파이프라인 모델을 사용하면 거의 확실하게 해당됩니다.그러나 코어 속도가 메모리 스트리밍 속도를 완전히 저하시킬 수 있는 현대의 비정상적인 슈퍼 스칼라 CPU에 대해 이것이 사실인지 아닌지는 매우 어렵습니다.이 경우 "스트리밍할 수 있는 바이트 수"에 비해 "폐기할 수 있는 명령 수"에 큰 차이가 있으므로 "스트리밍할 수 있는 각 바이트에 대해 폐기할 수 있는 명령 수"를 얻을 수 있습니다.이 크기가 충분히 크면ctz+ 교대 명령은 "무료"로 수행할 수 있습니다.

"가장 빠른 문자열"을 검색해 보고 관심 있는 항목이 있으면 저한테 물어보세요.

내 생각에 당신은 너무 많은 제한을 가하고 있다(네, 우리는 모두 최대 검색기에서 준선형 선형을 원한다). 하지만 진정한 프로그래머가 개입하려면 해시 접근법이 단순한 니프티 림보 솔루션이라고 생각합니다(짧은 2는 BNDM에 의해 잘 강화됩니다).16 패턴).

간단한 예시를 제시하겠습니다.

패턴(32바이트)을 문자열(206908949바이트)로 한 줄로 검색 중...건너뛰기 퍼포먼스 (더 큰 성능): 3041%, 6801754 건너뛰기/반복 Railgun_Quadruplet_7Hasherezade_hits/레일건_Quadruplet_7해시레자데_clocks: 0/58 레일건_쿼드러플렛_7해시레이드 퍼포먼스: 3483KB/클럭

패턴(32바이트)을 문자열(206908949바이트)로 한 줄로 검색 중...건너뛰기 퍼포먼스(더 큰 성능): 1554%, 13307181 건너뛰기/반복 Boyer_Moore_Flensburg_hits/Boyer_Moore_Flensburg_clocks: 0/83 Boyer_Moore_Flensburg_clocks: 2434KB/clock

패턴(32바이트)을 문자열(206908949바이트)로 한 줄로 검색 중...건너뛰기 퍼포먼스 (더 크게): 129%, 160239051 건너뛰기/반복2방향_히트/2방향_클럭: 0/816 양방향 퍼포먼스: 247KB/클럭

산메이스
안부 전해요

질문에서 언급하신 양방향 알고리즘(어쨌든 대단합니다!)는 최근 한 번에 여러 개의 단어를 효율적으로 사용할 수 있도록 개선되었습니다.최적의 패킹된 문자열 매칭.

I haven't read the whole paper, but it seems they rely on a couple of new, special CPU instructions (included in e.g. SSE 4.2) being O(1) for their time complexity claim, though if they aren't available they can simulate them in O(log log w) time for w-bit words which doesn't sound too bad.

I recently discovered a nice tool to measure the performance of the various available algos: http://www.dmi.unict.it/~faro/smart/index.php

You might find it useful. Also, if I have to take a quick call on substring search algorithm, I would go with Knuth-Morris-Pratt.

Use stdlib strstr:

char *foundit = strstr(haystack, needle);

It was very fast, only took me about 5 seconds to type.

A really good question. Just add some tiny bits...

1. Someone were talking about DNA sequence matching. But for DNA sequence, what we usually do is to build a data structure (e.g. suffix array, suffix tree or FM-index) for the haystack and match many needles against it. This is a different question.

2. It would be really great if someone would like to benchmark various algorithms. There are very good benchmarks on compression and the construction of suffix arrays, but I have not seen a benchmark on string matching. Potential haystack candidates could be from the SACA benchmark.

3. A few days ago I was testing the Boyer-Moore implementation from the page you recommended (EDIT: I need a function call like memmem(), but it is not a standard function, so I decided to implement it). My benchmarking program uses random haystack. It seems that the Boyer-Moore implementation in that page is times faster than glibc's memmem() and Mac's strnstr(). In case you are interested, the implementation is here and the benchmarking code is here. This is definitely not a realistic benchmark, but it is a start.

I know it's an old question, but most bad shift tables are single character. If it makes sense for your dataset (eg especially if it's written words), and if you have the space available, you can get a dramatic speedup by using a bad shift table made of n-grams rather than single characters.

이것은 Python의 검색 실장입니다.코어 전체에서 사용되고 있습니다.코멘트는 압축된 boyer-moore delta 1 테이블을 사용하고 있음을 나타냅니다.

문자열 검색은 제가 직접 꽤 광범위한 실험을 해봤지만, 여러 검색 문자열에 대한 것이었어요.Horspool과 Bitap의 어셈블리 실장은 패턴 카운트가 적은 Aho-Corasick 등의 알고리즘에 대해 독자적인 실장을 유지하는 경우가 많습니다.

예를 들어 4개의 다른 알고리즘을 구현할 수 있습니다.M분마다(경험적으로 결정됨) 현재 실제 데이터에 대해 4개 모두를 실행합니다.N개의 실행(TBD)에 대한 통계를 누적합니다.그러면 다음 M분 동안 승자만 쓰세요.

[Log stats on Wins]:이긴 적이 없는 알고리즘을 새로운 알고리즘으로 대체할 수 있도록 합니다.가장 성공적인 루틴에 최적화 노력을 집중합니다.하드웨어, 데이터베이스 또는 데이터 소스를 변경한 후에는 통계에 특히 주의하십시오.로그 날짜/타임 스탬프를 통해 알 수 있도록 가능한 한 통계 로그에 해당 정보를 포함하십시오.

퍼포먼스에 큰 영향을 미치기 때문에 여러 종류의 문자열을 사용하여 다양한 벤치마크를 작성할 수도 있습니다.알고는 자연어 검색, DNA 문자열 또는 무작위 문자열 등에 기초하여 차이를 보입니다(그리고 여기서도 다른 형태 때문에 미세한 구별이 있을 수 있습니다).

알파벳 사이즈는 많은 알고에서 바늘 사이즈와 마찬가지로 역할을 할 것이다.예를 들어 Horspool은 영어 텍스트에서는 잘하지만 알파벳 크기가 다르기 때문에 DNA에서는 잘 못하기 때문에 나쁜 문자 규칙에 대한 삶을 어렵게 만든다.Good-suffix를 도입하면 이 점이 크게 개선됩니다.

그게 최고인지는 모르겠지만, 보이어 무어와 좋은 경험을 했어요.

언급URL : https://stackoverflow.com/questions/3183582/what-is-the-fastest-substring-search-algorithm