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

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

---

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

• 바늘 (패턴)과 건초 더미 (검색 할 텍스트)는 모두 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와 같은)이있는 양방향 알고리즘을 사용하십시오. 많은 중간 길이의 바늘에 대한 순 손실 인 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

---

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

Boyer-Moore 는 접미사 테이블이 좋은 잘못된 문자 테이블을 사용합니다.

Boyer-Moore-Horspool 은 잘못된 문자표를 사용합니다.

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

Rabin-Karp 는 해시 실행을 사용합니다.

그들은 모두 다른 정도의 비교를 위해 오버 헤드를 교환하므로 실제 성능은 바늘과 건초 더미의 평균 길이에 달려 있습니다. 초기 오버 헤드가 많을수록 입력이 길수록 좋습니다. 바늘이 매우 짧으면 무차별적인 힘이 이길 수 있습니다.

편집하다:

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

다음의 작은 테이블에 대해 생각해보십시오. 각 물음표마다 다른 최상의 검색 알고리즘이있을 수 있습니다.

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

이것은 각 축에서 더 짧거나 더 긴 입력 범위를 갖는 그래프 여야합니다. 이러한 그래프에 각 알고리즘을 플로팅하면 각각 다른 서명을 갖게됩니다. 일부 알고리즘은 패턴에서 많은 반복이 발생하여 유전자 검색과 같은 용도에 영향을 줄 수 있습니다. 전체 성능에 영향을 미치는 다른 요소로는 동일한 패턴을 두 번 이상 검색하고 다른 패턴을 동시에 검색하는 것입니다.

If I needed a sample set, I think I would scrape a site like google or wikipedia, then strip the html from all the result pages. For a search site, type in a word then use one of the suggested search phrases. Choose a few different languages, if applicable. Using web pages, all the texts would be short to medium, so merge enough pages to get longer texts. You can also find public domain books, legal records, and other large bodies of text. Or just generate random content by picking words from a dictionary. But the point of profiling is to test against the type of content you will be searching, so use real world samples if possible.

나는 짧고 긴 모호함을 남겼습니다. 바늘의 경우 8 자 이하, 중간자 64 자 이하, 1k 자 이하로 짧게 생각합니다. 건초 더미의 경우 2 ^ 10 미만, 중간 2 ^ 20 미만, 최대 2 ^ 30 자 정도로 생각합니다.

---

2011 년에 출판 된 Dany Breslauer, Roberto Grossi, Filippo Mignosi 의 "Simple Real-Time Constant-Space String Matching" 알고리즘 일 것입니다.

최신 정보:

2014 년에 저자는 다음과 같은 개선 사항을 발표했습니다. 최적의 묶음 문자열 일치로 .

---

http://www-igm.univ-mlv.fr/~lecroq/string/index.html는 당신이이 가장 잘 알려진 및 연구 문자열 매칭 알고리즘의 일부의 훌륭한 소스 및 요약 포인트 연결합니다.

대부분의 검색 문제에 대한 솔루션에는 사전 처리 오버 헤드, 시간 및 공간 요구 사항과 관련하여 트레이드 오프가 포함됩니다. 모든 경우에 단일 알고리즘이 최적이거나 실용적이지는 않습니다.

문자열 검색을 위해 특정 알고리즘을 설계하는 것이 목표라면, 나머지 말을 무시하십시오. 일반화 된 문자열 검색 서비스 루틴을 개발하려면 다음을 시도하십시오.

Spend some time reviewing the specific strengths and weaknesses of the algorithms you have already referenced. Conduct the review with the objective of finding a set of algorithms that cover the range and scope of string searches you are interested in. Then, build a front end search selector based on a classifier function to target the best algorithm for the given inputs. This way you may employ the most efficient algorithm to do the job. This is particularly effective when an algorithm is very good for certain searches but degrades poorly. For example, brute force is probably the best for needles of length 1 but quickly degrades as needle length increases, whereupon the sustik-moore algoritim더 작은 바늘보다 더 효율적일 수 있고, 더 긴 바늘과 더 큰 알파벳의 경우 KMP 또는 Boyer-Moore 알고리즘이 더 나을 수 있습니다. 다음은 가능한 전략을 설명하기위한 예일뿐입니다.

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

각 검색 알고리즘은 예를 들어이 백서에서 설명하는 것처럼 성능에 큰 차이를 만들 수있는 몇 가지 변형이 있습니다 .

Benchmark your service to categorize the areas where additional search strategies are needed or to more effectively tune your selector function. This approach is not quick or easy but if done well can produce very good results.

---

I was surprised to see our tech report cited in this discussion; I am one of the authors of the algorithm that was named Sustik-Moore above. (We did not use that term in our paper.)

I wanted here to emphasize that for me the most interesting feature of the algorithm is that it is quite simple to prove that each letter is examined at most once. For earlier Boyer-Moore versions they proved that each letter is examined at most 3 and later 2 times at most, and those proofs were more involved (see cites in paper). Therefore I also see a didactical value in presenting/studying this variant.

In the paper we also describe further variations that are geared toward efficiency while relaxing the theoretical guarantees. It is a short paper and the material should be understandable to an average high school graduate in my opinion.

Our main goal was to bring this version to the attention of others who can further improve on it. String searching has so many variations and we alone cannot possibly think of all where this idea could bring benefits. (Fixed text and changing pattern, fixed pattern different text, preprocessing possible/not possible, parallel execution, finding matching subsets in large texts, allow errors, near matches etc., etc.)

---

The fastest substring search algorithm is going to depend on the context:

1. the alphabet size (e.g. DNA vs English)
2. the needle length

The 2010 paper "The Exact String Matching Problem: a Comprehensive Experimental Evaluation" gives tables with runtimes for 51 algorithms (with different alphabet sizes and needle lengths), so you can pick the best algorithm for your context.

All of those algorithms have C implementations, as well as a test suite, here:

http://www.dmi.unict.it/~faro/smart/algorithms.php

---

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.

---

Here's Python's search implementation, used from throughout the core. The comments indicate it uses a compressed boyer-moore delta 1 table.

I have done some pretty extensive experimentation with string searching myself, but it was for multiple search strings. Assembly implementations of Horspool and Bitap can often hold their own against algorithms like Aho-Corasick for low pattern counts.

---

A faster "Search for a single matching character" (ala strchr) algorithm.

Important notes:

• These functions use a "number / count of (leading|trailing) zeros" gcc compiler intrinsic- __builtin_ctz. These functions are likely to only be fast on machines that have an instruction(s) that perform this operation (i.e., x86, ppc, arm).

• These functions assume the target architecture can perform 32 and 64 bit unaligned loads. If your target architecture does not support this, you will need to add some start up logic to properly align the reads.

• These functions are processor neutral. If the target CPU has vector instructions, you might be able to do (much) better. For example, The strlen function below uses SSE3 and can be trivially modified to XOR the bytes scanned to look for a byte other than 0. Benchmarks performed on a 2.66GHz Core 2 laptop running Mac OS X 10.6 (x86_64) :

  • 843.433 MB/s for strchr
  • 2656.742 MB/s for findFirstByte64
  • 13094.479 MB/s for strlen

... a 32-bit version:

#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));
}

... and a 64-bit version:

#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));
}

Edit 2011/06/04 The OP points out in the comments that this solution has a "insurmountable bug":

it can read past the sought byte or null terminator, which could access an unmapped page or page without read permission. You simply cannot use large reads in string functions unless they're aligned.

This is technically true, but applies to virtually any algorithm that operates on chunks that are larger than a single byte, including the method suggested by the OP in the comments:

A typical strchr implementation is not naive, but quite a bit more efficient than what you gave. See the end of this for the most widely used algorithm: http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

It also really has nothing to do with alignment per-se. True, this could potentially cause the behavior discussed on the majority of common architectures in use, but this has more to do with microarchitecture implementation details- if the unaligned read straddles a 4K boundary (again, typical), then that read will cause a program terminating fault if the next 4K page boundary is unmapped.

But this isn't a "bug" in the algorithm given in the answer- that behavior is because functions like strchr and strlen do not accept a length argument to bound the size of the search. Searching char bytes[1] = {0x55};, which for the purposes of our discussion just so happens to be placed at the very end of a 4K VM page boundary and the next page is unmapped, with strchr(bytes, 0xAA) (where strchr is a byte-at-a-time implementation) will crash exactly the same way. Ditto for strchr related cousin strlen.

Without a length argument, there is no way to tell when you should switch out of the high speed algorithm and back to a byte-by-byte algorithm. A much more likely "bug" would be to read "past the size of the allocation", which technically results in undefined behavior according to the various C language standards, and would be flagged as an error by something like valgrind.

In summary, anything that operates on larger than byte chunks to go faster, as this answers code does and the code pointed out by the OP, but must have byte-accurate read semantics is likely to be "buggy" if there is no length argument to control the corner case(s) of "the last read".

The code in this answer is a kernel for being able to find the first byte in a natural CPU word size chunk quickly if the target CPU has a fast ctz like instruction. It is trivial to add things like making sure it only operates on correctly aligned natural boundaries, or some form of length bound, which would allow you to switch out of the high speed kernel and in to a slower byte-by-byte check.

The OP also states in the comments:

As for your ctz optimization, it only makes a difference for the O(1) tail operation. It could improve performance with tiny strings (e.g. strchr("abc", 'a'); but certainly not with strings of any major size.

Whether or not this statement is true depends a great deal on the microarchitecture in question. Using the canonical 4 stage RISC pipeline model, then it is almost certainly true. But it is extremely hard to tell if it is true for a contemporary out-of-order super scalar CPU where the core speed can utterly dwarf the memory streaming speed. In this case, it is not only plausible, but quite common, for there to be a large gap in "the number of instructions that can be retired" relative to "the number of bytes that can be streamed" so that you have "the number of instructions that can be retired for each byte that can be streamed". If this is large enough, the ctz + shift instruction can be done "for free".

---

Just search for "fastest strstr", and if you see something of interest just ask me.

In my view you impose too many restrictions on yourself (yes we all want sub-linear linear at max searcher), however it takes a real programmer to step in, until then I think that the hash approach is simply a nifty-limbo solution (well reinforced by BNDM for shorter 2..16 patterns).

Just a quick example:

Doing Search for Pattern(32bytes) into String(206908949bytes) as-one-line ... Skip-Performance(bigger-the-better): 3041%, 6801754 skips/iterations Railgun_Quadruplet_7Hasherezade_hits/Railgun_Quadruplet_7Hasherezade_clocks: 0/58 Railgun_Quadruplet_7Hasherezade performance: 3483KB/clock

Doing Search for Pattern(32bytes) into String(206908949bytes) as-one-line ... Skip-Performance(bigger-the-better): 1554%, 13307181 skips/iterations Boyer_Moore_Flensburg_hits/Boyer_Moore_Flensburg_clocks: 0/83 Boyer_Moore_Flensburg performance: 2434KB/clock

Doing Search for Pattern(32bytes) into String(206908949bytes) as-one-line ... Skip-Performance(bigger-the-better): 129%, 160239051 skips/iterations Two-Way_hits/Two-Way_clocks: 0/816 Two-Way performance: 247KB/clock

Sanmayce,
Regards

---

The Two-Way Algorithm that you mention in your question (which by the way is incredible!) has recently been improved to work efficiently on multibyte words at a time: Optimal Packed String Matching.

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.

---

You could implement, say, 4 different algorithms. Every M minutes (to be determined empirically) run all 4 on current real data. Accumulate statistics over N runs (also TBD). Then use only the winner for the next M minutes.

Log stats on Wins so that you can replace algorithms that never win with new ones. Concentrate optimization efforts on the winningest routine. Pay special attention to the stats after any changes to the hardware, database, or data source. Include that info in the stats log if possible, so you won't have to figure it out from the log date/time-stamp.

---

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.

---

You might also want to have diverse benchmarks with several types of strings, as this may have a great impact on performance. The algos will perform differenlty based on searching natural language (and even here there still might be fine grained distinctions because of the different morphologoies), DNA strings or random strings etc.

Alphabet size will play a role in many algos, as will needle size. For instance Horspool does good on English text but bad on DNA because of the different alphabet size, making life hard for the bad-character rule. Introducing the good-suffix allieviates this greatly.

---

Use stdlib strstr:

char *foundit = strstr(haystack, needle);

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

---

I don't know if it's the absolute best, but I've had good experience with Boyer-Moore.

---

This does not directly answer the question but if the text is very large, how about dividing it into overlapping sections (overlap by a pattern length), then simultaneously search the sections using threads. With regards to fastest algorithm, Boyer-Moore-Horspool I think is one of the fastest if not the fastest among variants of Boyer-Moore. I posted a couple of Boyer-Moore variant (I don't know their name) in this topic Algorithm faster than BMH (Boyer–Moore–Horspool) Search.

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