문자열에 주어진 배열에 문자열이 포함되어 있는지 알아내는 빠른 알고리즘

약 50 개의 키워드와 약 50000 개의 문자열 목록이 있습니다. 적어도 하나의 키워드가 포함되어 있으면 모든 문자열을 확인합니다. 일치하는 키워드 또는 일치하는 키워드의 수에 관심이 없습니다. 가능한 한 빨리 "진정한"또는 "거짓"만을 원합니다.문자열에 주어진 배열에 문자열이 포함되어 있는지 알아내는 빠른 알고리즘

class MyEnumerableExtension 
{ 
    public static bool ContainsAny(this string searchString, IEnumerable<string> keywords) 
    { 
     return keywords.Any(keyword => searchString.Contains(keyword)) 
    } 
} 

bool foundAny = "abcdef".ContainsAny(new string[] { "ac", "bd", "cd" });

출처

2010-11-18 VVS

본질적으로 오늘의 다른 질문과 동일하지 않습니다 Efficient algorithm for finding all keywords in a text 일치하는 항목을 찾으면 수정해야합니다.

출처

2010-11-18 13:43:11

아니요. 두 가지 우려가 있습니다. 하나는 주어진 키워드 목록에있는 키워드가 들어있는 문자열을 찾는 것이고, 다른 하나는 다른 키워드를 사용하여 발견 된 문자열을 토큰 화하는 것입니다. 키워드 목록 이 목록은 서로 다른 목적을 가지고 있습니다. – VVS

좋습니다.하지만 해결 방법은 두 곳에서 똑같은 명제입니다 (이 경우 일치하는 항목이 발견되면 다시 돌아 오기 위해 변경)? –

아, 끝날 때까지 읽어야 했어. 나는 네가 옳다고 생각한다. 나는 하나의 키워드가 발견 된 후에 돌아 오도록 알고리즘을 수정할 수있다. 이후 키워드 트리를 작성해야하므로 매우 빠른 솔루션이어야합니다. – VVS

은 문자열의 집합에 대한 텍스트를 검색 할 수 multiple algorithms을 있습니다

그래서, 나는 지금까지 내 현재 LINQ 버전을 능가하는 성능을 거기 알고리즘이 내기.

출처

2010-11-18 13:42:15 Carra

Knuth-Morris-Pratt algorithm을 구현할 수 있습니다.

출처

2010-11-18 13:42:33

한 단어를 검색하면 더 쉽게 검색 할 수 있습니다. 위키피디아 http://en.wikipedia.org/wiki/String_searching_algorithm #Algorithms_using_finite_set_of_patterns –

빠른 분석을 통해 반복적으로 키워드를 검색하고 있음을 알 수 있습니다. 모든 키워드에 대해 한 번에 검색 할 수 있다면 알고리즘이 전반적으로 개선되어야합니다. Regex 표현식은이를 수행하고 "컴파일 된"옵션과 결합하여 모든 키워드에 대해 문자열을 단일 전달하므로 성능이 향상되기 시작해야합니다. 그러나 키워드가 여러 개인 경우에만 도움이됩니다. 여기 당신을 도울 수있는 빠른 아이디어가 있지만, 실제로 알고리즘에 대한 성능을 테스트하지는 않았습니다.

 string[] keywords = { "ac", "bd", "cd" }; 
     string[] tosearch = { "abcdef" }; 
     string pattern = String.Join("|", keywords); 
     Regex regex = new Regex(pattern, RegexOptions.Compiled); 
     foundAny = regex.IsMatch(String.Join("|", tosearch));

또한 그러나, 특수 문자 이스케이프 시퀀스로 극복 할 수있다.이만큼 어떤 정규식 특수 문자 (및 검색 문자열을 포함하지 않는 키워드가 파이프 기호를 포함하지 않는로 작동 유의하고, 내가 한 것처럼 검색 문자열을 조인 할 필요가 없습니다.

출처

2010-11-18 14:03:06 Les

문자열에 주어진 배열에 문자열이 포함되어 있는지 알아내는 빠른 알고리즘

답변

관련 문제