언제 BOYER-MOORE보다 KMP를 사용 하시겠습니까

Question

저는 현재 패턴 매칭 알고리즘에 대해 배우고 있으며이 두 알고리즘을 보았습니다. I는하기 일반 아이디어 가지고

KMP

• 는
• 가 시프트 장애 배열을 사용하여 좌우로 텍스트를 비교를 지능적
• 이 m은의 길이 O (m)를 얻어 패턴은
• 공백
• 가 O (m)에 걸리는 결함 어레이를 계산하는 문자열

에게 검색 O (n)은 시간을 소요 할 0

BM

• 는
• 나쁜 캐릭터가 점프 사용 마지막 문자에서 패턴을 비교하여 좋은 접미사는
• 는 O (m + 알파벳의 크기)
• 는 O (m + 크기 소요 테이블을 계산하는 데 걸리는 점프 알파벳), 공간
• 는

나는 다음과 같은 숨어 우연히 검색 O (n)이 있지만, 일반적으로 더 소요 우리는 많은 다른 텍스트에서 반복적으로 같은 패턴 검색하려면

크 누스 - 모리스 - 프랫 (KMP) 알고리즘은 좋은 선택이다 (참 또는 거짓)이 질문에 트리거 estion.

그래서 전제가 다른 텍스트에서 알고리즘을 실행할 때마다 전처리가 O (n)인데 BM의 경우 O (n + 알파벳) 인 이유만으로 답이 사실이라고 생각합니다. 그러나 알고리즘이 다시 실행될 때마다 새 테이블이 다시 계산된다는 올바른 가정을하고 있는지 확실하지 않습니다. 왜냐하면 텍스트가 항상 영어의 알파벳에 속한다고 말하기 때문입니다. 한 번만 테이블을 계산하고 테이블을 재사용하면됩니다. 결국이 질문에 대한 대답은 알고리즘이 모두 동일한 알파벳에 포함 된 텍스트 나 다른 텍스트에 영향을 미칠 수 있다는 사실에 달려 있습니까?

Answer 1

이론적으로 두 알고리즘 모두 "유사한"성능을가집니다. KMP는 검색 단계에서 약 2n 개의 비교를 수행하고 Boyer-Moore는 검색 단계에서 약 3n 개의 비교를 수행합니다. 최악의 경우입니다. 어느 경우에도 새로운 텍스트를 얻을 때 사전 처리를 반복해야합니다.

하지만 실제 대답은 실제로 둘 중 하나를 사용해서는 안된다는 것입니다.

두 알고리즘 모두에 필요한 선형 보조 기억 장치는 모든 여분의 메모리 액세스로 인해 현대 아키텍처에서 상당히 거친 성능을 제공합니다.

그러나 Boyer-Moore 및 KMP 뒤에있는 아이디어은 가장 빠른 문자열 일치 알고리즘을 지원합니다.KMP의 "실패 함수"아이디어와 같은 것은 실제로 알고있는 모든 실용적인 문자열 매칭 알고리즘에 사용됩니다. 당신은 일정한 추가 공간 만 필요로하면서도 선형 시간 매칭을 제공하는 on-the-fly 패턴에 대해 차선의 "실패 함수"를 계산할 수 있다는 것이 밝혀졌습니다. Boyer-Moore는 고정 패턴을 무작위 노이즈와 비교하는 "평균적인 경우"에서 선형보다 빠르며, 이는 많은 실제 상황에서 그 자체를 낳습니다.