KMP 또는 BM 알고리즘을 사용해 본 적이 있습니까?

Question

KMP (Knuth-Morris-Pratt) 알고리즘과 BM (Boyers-Moore) 알고리즘은 모두 좋은 문자열 검색 연산 알고리즘입니다. BM이 KMP보다 3-5 배 빠름을 압니다.

업계 소프트웨어 프로그래밍 경험에서 BM 또는 KMP 알고리즘을 사용해 본 적이 있습니까? 알고리즘이 실제로 여기서 중요합니까?

Answer 1

예를 들어 Java의 String.indexOf 함수를 살펴보면 문자열 일치에 무차별 방식을 사용하는 것으로 보입니다. 그 이유는 궁금 할 것입니다.

이유는 일부 쿼리 사전 처리가 이러한 알고리즘에서 수행되며 이는 값이 비쌀 수 있습니다 (특히 두 배열을 모두 사용하는 경우 BM의 경우). 따라서 KMP와 BM이 무차별 방식을 사용하기 전에 검색하는 문자열은 큰 크기 여야합니다.

다른 알고리즘을 사용할 때 항상 거래가 발생하며 큰 문자열을 처리 할 때 쿼리 대신 텍스트의 색인 생성 (예 : 접미어 트리)을 고려할 수 있습니다. 매번 새로운 텍스트를 다룰 때 유용합니다.

제 생각에는 이러한 알고리즘은 다소 학문적이며 특별한 상황에서만 유용합니다.

Answer 2

하드웨어에서 KMP를 한 번 구현했습니다. 하드웨어가 FPGA 인 경우 재구성 기능을 사용하여 자체 수정 회로를 사용할 수 있습니다. 이 회로는 검색 문자열을 얻습니다. 필요한 것보다 하드웨어에서 미리 컴파일하고 KMP를 만들 로직을 재구성해야합니다. 그러나 속도를 높이기 위해 많은 양의 데이터를 크롤링해야하지만 여기서도 DNA 일치 (예 : DNA 일치)가 있습니다.

Answer 3

glibc의 strstr 기능은 선형입니다. Boyer-Moore의 변종이라고 생각되는 Two-Way Algorithm을 사용합니다. 그래서, gcc에서 strstr을 사용하는 사람은 실제로 실제 문자열 검색 알고리즘을 사용하고 있습니다.

빠른 알고리즘이 중요한지 여부에 대한 질문은 IMHO는 데이터 크기가 충분히 큰 경우에만 중요합니다. 우리가하는 많은 명시 적 문자열 연산은 매우 작은 문자열 (500 자 미만)에 있습니다. 이는 문자열 작업 (예 : 데이터베이스의 전체 텍스트 검색)을 수행하지 않는다는 것을 의미하지는 않습니다. 그러나이 경우 우리는 일반적으로 데이터베이스 나 라이브러리가 우리를 위해 무거운 짐을 지도록 만듭니다. 데이터베이스 또는 라이브러리는 빠른 문자열 검색 알고리즘을 사용하므로 중요하지 않다고 말하면서 사용법이 우리에게 직접 표시되지 않습니다.