[c] 가장 빠른 하위 문자열 검색 알고리즘은 무엇입니까?

좋아, 나는 바보처럼 들리지 않는다. 나는 문제 / 요구 사항을보다 명확하게 언급 할 것이다.

• 바늘 (패턴)과 건초 더미 (검색 할 텍스트)는 모두 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 바이트를 비교하십시오. . 건초 더미의 모든 바이트는 정확히 한 번 읽히고 0 (문자열 끝)과 하나의 16 비트 또는 32 비트 비교에 대한 검사가 수행됩니다.
• 길이가 4보다 큰 바늘의 경우 창의 마지막 바이트에만 적용되는 잘못된 이동 테이블 (Boyer-Moore와 같은)이있는 양방향 알고리즘을 사용하십시오. 많은 중간 길이의 바늘에 대한 순 손실 인 1kb 테이블을 초기화하는 오버 헤드를 피하기 위해 시프트 테이블의 항목이 초기화되는 비트 배열 (32 바이트)을 표시합니다. 설정되지 않은 비트는 바늘에 나타나지 않는 바이트 값에 해당하며 전체 바늘 길이 이동이 가능합니다.

내 마음에 남아있는 큰 질문은 다음과 같습니다.

• 잘못된 시프트 테이블을 더 잘 활용할 수있는 방법이 있습니까? Boyer-Moore는 뒤로 (오른쪽에서 왼쪽으로) 스캔하여 최대한 활용할 수 있지만 양방향에서는 왼쪽에서 오른쪽으로 스캔해야합니다.
• 일반적인 경우에 대해 찾은 두 가지 실행 가능한 후보 알고리즘 (메모리 부족 또는 2 차 성능 조건 없음)은 정렬 된 알파벳에서 양방향 및 문자열 일치입니다 . 그러나 다른 알고리즘이 최적 인 경우를 쉽게 감지 할 수있는 경우가 있습니까? 공간 알고리즘에서 확실히 O(m)( m바늘 길이는) 많은 부분 이 사용될 수 있습니다 m<100. 선형 시간 만 필요로하는 바늘에 대한 쉬운 테스트가있는 경우 최악의 2 차 알고리즘을 사용할 수도 있습니다.

보너스 포인트 :

• needle과 haystack이 잘 구성된 UTF-8이라고 가정하여 성능을 향상시킬 수 있습니까? (바이트 길이가 다양한 문자를 사용하면 올바른 형식으로 바늘과 건초 더미 사이에 일부 문자열 정렬 요구 사항이 적용되며 불일치하는 헤드 바이트가 발생하면 자동으로 2-4 바이트 이동이 가능합니다. 그러나 이러한 제약 조건으로 인해 최대 접미사 계산, 좋은 접미사 이동 등은 이미 다양한 알고리즘을 제공합니까?)

참고 : 실제로 알고리즘의 성능이 좋지는 않지만 대부분의 알고리즘을 잘 알고 있습니다. 사람들이 나에게 알고리즘에 대한 의견 / 답변으로 계속 언급하지 않도록 좋은 참고 자료가 있습니다. http://www-igm.univ-mlv.fr/~lecroq/string/index.html

답변

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