사전 정의 된 시드 목록에 대한 문자열 테스트를위한 가장 빠른 C ++ 알고리즘 (대소 문자 구분 안 함)

사전 정의 된 시드 목록에 대한 문자열 테스트를위한 가장 빠른 C ++ 알고리즘 (대소 문자 구분 안 함)

---

약 100 개의 미리 정의 된 문자열 인 시드 문자열 목록이 있습니다. 모든 문자열에는 ASCII 문자 만 포함됩니다.

std::list<std::wstring> seeds{ L"google", L"yahoo", L"stackoverflow"};

내 앱은 모든 문자를 포함 할 수있는 많은 문자열을 지속적으로 수신합니다. 받은 각 라인을 확인하고 씨앗이 있는지 여부를 결정해야합니다. 비교는 대소 문자를 구분하지 않아야합니다.

받은 문자열을 테스트하려면 가능한 가장 빠른 알고리즘이 필요합니다.

지금 내 앱은 다음 알고리즘을 사용합니다.

std::wstring testedStr;
for (auto & seed : seeds)
{
    if (boost::icontains(testedStr, seed))
    {
        return true;
    }
}
return false;

잘 작동하지만 이것이 가장 효율적인 방법인지는 모르겠습니다.

더 나은 성능을 얻기 위해 알고리즘을 구현하는 것이 어떻게 가능합니까?

이것은 Windows 앱입니다. 앱이 유효한 std::wstring문자열을 받습니다 .

---

최신 정보

이 작업을 위해 Aho-Corasick algo를 구현했습니다. 누군가 내 코드를 검토 할 수 있다면 좋을 것입니다. 그런 알고리즘에 대한 경험이 많지 않습니다. 구현 링크 : gist.github.com

---

Aho–Corasick 알고리즘을 사용할 수 있습니다.

문자열에 시드가 있음을 의미하는 터미널로 표시된 일부 정점에 trie / automaton을 빌드합니다.

내장되어 O(sum of dictionary word lengths)있으며 답변을 제공합니다.O(test string length)

장점 :

• 특히 여러 사전 단어와 함께 작동하며 단어 수에 의존하지 않는 검사 시간 (기억에 맞지 않는 경우를 고려하지 않는 경우 등)
• 알고리즘은 구현하기 어렵지 않습니다 (적어도 접미사 구조와 비교)

ASCII 인 경우 각 기호를 낮추어 대소 문자를 구분하지 않을 수 있습니다 (ASCII가 아닌 문자는 일치하지 않음).

---

일치하는 문자열의 양이 한정되어있는 경우, 이는 루트에서 잎까지 읽을 수있는 유사한 문자열이 비슷한 가지를 차지하도록 트리를 구성 할 수 있음을 의미합니다.

이것은 trie 또는 Radix Tree 라고도 합니다.

예를 들어, 우리는 문자열이있을 수 있습니다 cat, coach, con, conch뿐만 아니라으로 dark, dad, dank, do. 그들의 시도는 다음과 같습니다.

트리의 단어 중 하나를 검색하면 루트에서 시작하여 트리를 검색합니다. 잎으로 만드는 것은 씨앗과 일치하는 것과 일치합니다. 그럼에도 불구하고 문자열의 각 문자는 자식 중 하나와 일치해야합니다. 그렇지 않은 경우 검색을 종료 할 수 있습니다 (예 : "g"로 시작하는 단어 또는 "cu"로 시작하는 단어는 고려하지 않음).

트리를 구성하고 검색하고 즉석에서 수정하는 알고리즘에는 여러 가지가 있지만, 가장 적합한 알고리즘을 모르기 때문에 특정 솔루션 대신 솔루션에 대한 개념적 개요를 제공 할 것이라고 생각했습니다. 그것.

개념적으로, 트리를 검색하는 데 사용할 수있는 알고리즘 은 문자열의 문자가 주어진 시점에서 취할 수있는 고정 된 양의 범주 또는 값의 기수 정렬 뒤에있는 아이디어와 관련이 있습니다 .

이렇게하면 단어 목록 과 비교하여 한 단어를 확인할 수 있습니다 . 이 단어 목록을 입력 문자열의 하위 문자열로 찾고 있기 때문에 이것보다 더 많은 것이있을 것입니다.

편집 : 다른 답변에서 언급했듯이 문자열 일치를위한 Aho-Corasick 알고리즘은 문자열 일치를 수행하기위한 정교한 알고리즘으로, 트리를 통해 "바로 가기"를 가져오고 이에 수반되는 다른 검색 패턴을 갖는 추가 링크가있는 트라이로 구성됩니다. (흥미롭게도 Alfred Aho는 인기있는 컴파일러 교과서 인 Compilers : Principles, Techniques 및 Tools 뿐만 아니라 알고리즘 교과서 인 The Design And Analysis Of Computer Algorithms 에도 기고했습니다 . 그는 Bell의 전 멤버이기도합니다. Labs. Margaret J. Corasick은 자신에 대한 공개 정보가 너무 많지 않은 것 같습니다.)

---

기존 정규식 유틸리티를 사용해보아야합니다. 수동으로 처리 한 알고리즘보다 느릴 수 있지만 정규식은 여러 가능성을 일치시키는 것에 관한 것이므로 이미 해시 맵 또는 모든 문자열에 대한 간단한 비교보다 몇 배 더 빠를 것입니다. 정규식 구현은 이미 RiaD에서 언급 한 Aho–Corasick 알고리즘을 사용하고있을 수 있으므로 기본적으로 잘 테스트되고 빠른 구현을 사용할 수 있습니다.

C ++ 11이있는 경우 이미 표준 정규식 라이브러리가 있습니다.

#include <string>
#include <regex>

int main(){
     std::regex self_regex("google|yahoo|stackoverflow");
     regex_match(input_string ,self_regex);
}

나는 이것이 가능한 최고의 최소 매치 트리를 생성 할 것으로 기대하므로 정말 빠르며 신뢰할 수있을 것으로 기대합니다!

---

더 빠른 방법 중 하나는 접미사 트리 https://en.wikipedia.org/wiki/Suffix_tree 를 사용하는 것이지만이 접근 방식에는 큰 단점이 있습니다. 구성이 어렵고 데이터 구조가 어렵다는 것입니다. 이 알고리즘은 선형 복잡성 https://en.m.wikipedia.org/wiki/Ukkonen%27s_algorithm의 문자열에서 트리를 만들 수 있습니다.

---

편집 : Matthieu M.이 지적했듯이 OP는 문자열에 키워드가 포함되어 있는지 물었습니다. 내 대답은 문자열이 키워드와 같거나 공백 문자로 문자열을 분할 할 수있는 경우에만 작동합니다.

Especially with a high number of possible candidates and knowing them at compile time using a perfect hash function with a tool like gperf is worth a try. The main principle is, that you seed a generator with your seed and it generates a function that contains a hash function which has no collisions for all seed values. At runtime you give the function a string and it calculates the hash and then it checks if it is the only possible candidate corresponding to the hashvalue.

The runtime cost is hashing the string and then comparing against the only possible candidate (O(1) for seed size and O(1) for string length).

To make the comparison case insensitive you just use tolower on the seed and on your string.

---

Because number of string is not big (~100), you can use next algo:

1. Calculate max length of word you have. Let it be N.
2. Create int checks[N]; array of checksum.
3. Let's checksum will be sum of all characters in searching phrase. So, you can calculate such checksum for each word from your list (that is known at compile time), and create std::map<int, std::vector<std::wstring>>, where int is checksum of string, and vector should contain all your strings with that checksum. Create array of such maps for each length (up to N), it can be done at compile time also.
4. Now move over big string by pointer. When pointer points to X character, you should add value of X char to all checks integers, and for each of them (numbers from 1 to N) remove value of (X-K) character, where K is number of integer in checks array. So, you will always have correct checksum for all length stored in checks array. After that search on map does there exists strings with such pair (length & checksum), and if exists - compare it.

It should give false-positive result (when checksum & length is equal, but phrase is not) very rare.

So, let's say R is length of big string. Then looping over it will take O(R). Each step you will perform N operations with "+" small number (char value), N operations with "-" small number (char value), that is very fast. Each step you will have to search for counter in checks array, and that is O(1), because it's one memory block.

Also each step you will have to find map in map's array, that will also be O(1), because it's also is one memory block. And inside map you will have to search for string with correct checksum for log(F), where F is size of map, and it will usually contain no more then 2-3 strings, so we can in general pretend that it is also O(1).

Also you can check, and if there is no strings with same checksum (that should happens with high chance with just 100 words), you can discard map at all, storing pairs instead of map.

So, finally that should give O(R), with quite small O. This way of calculating checksum can be changed, but it's quite simple and completely fast, with really rare false-positive reactions.

---

As a variant on DarioOO’s answer, you could get a possibly faster implementation of a regular expression match, by coding a lex parser for your strings. Though normally used together with yacc, this is a case where lex on its own does the job, and lex parsers are usually very efficient.

Aho-Corasick , Commentz-Walter 또는 Rabin-Karp 와 같은 알고리즘이 아마도 상당한 개선을 제공 할 것이며, lex 구현이 그러한 알고리즘을 사용하는지 의심 스럽기 때문에 모든 문자열이 길면이 접근 방식이 떨어질 수 있습니다 .

이 접근 방식은 재구성없이 문자열을 구성 할 수 있어야하는 경우 더 어렵지만 flex 는 오픈 소스 이므로 코드를 잠식 할 수 있습니다.

참조 URL : https://stackoverflow.com/questions/37509461/the-fastest-c-algorithm-for-string-testing-against-a-list-of-predefined-seeds