패턴 매칭은 컴퓨터 과학 및 기타 여러 분야에서 널리 사용됩니다. 패턴 일치 알고리즘은 더 큰 텍스트 또는 데이터 세트 내에서 패턴을 검색하는 데 사용됩니다. 패턴 매칭을 위한 가장 유명한 알고리즘 중 하나는 보이어-무어 알고리즘은 1977년에 처음 출판되었습니다. 이 기사에서는 C의 패턴 일치 알고리즘과 작동 방식에 대해 설명합니다.
패턴 매칭 알고리즘이란 무엇입니까?
패턴 일치 알고리즘은 더 큰 데이터 또는 텍스트 집합 내에서 패턴을 찾는 데 사용됩니다. 이러한 알고리즘은 패턴을 더 큰 데이터 세트 또는 텍스트와 비교하고 패턴이 존재하는지 여부를 결정하는 방식으로 작동합니다. 패턴 일치 알고리즘은 대규모 데이터 세트에서 패턴을 빠르게 검색할 수 있게 해주기 때문에 중요합니다.
전가산기 회로
무차별 대입 패턴 일치 알고리즘:
무차별 패턴 매칭(Brute Force Pattern Matching)은 가장 간단한 패턴 매칭 알고리즘입니다. 패턴의 문자를 텍스트의 문자와 하나씩 비교하는 작업이 포함됩니다. 모든 문자가 일치하면 알고리즘은 텍스트에서 패턴의 시작 위치를 반환합니다. 그렇지 않은 경우 알고리즘은 텍스트의 다음 위치로 이동하고 일치하는 항목을 찾거나 텍스트 끝에 도달할 때까지 비교를 반복합니다. 무차별 대입 알고리즘의 시간 복잡도는 다음과 같습니다. 오(MXN) , 어디 중 텍스트의 길이를 나타냅니다. N 패턴의 길이를 나타냅니다.
단순한 패턴 매칭 알고리즘:
Naive Pattern Matching 알고리즘은 Brute Force 알고리즘을 개선한 것입니다. 텍스트의 일부 위치를 건너뛰어 불필요한 비교를 방지합니다. 알고리즘은 패턴을 첫 번째 위치의 텍스트와 비교하기 시작합니다. 문자가 일치하면 다음 위치로 이동하여 비교를 반복합니다. 문자가 일치하지 않으면 알고리즘은 텍스트의 다음 위치로 이동하고 패턴을 텍스트와 다시 비교합니다. Naive 알고리즘의 시간 복잡도는 다음과 같습니다. 오(MXN) , 그러나 대부분의 경우 Brute Force 알고리즘보다 빠릅니다.
크누스-모리스-프랫 알고리즘:
그만큼 크누스-모리스-프랫(KMP) 알고리즘은 더욱 발전된 패턴 매칭 알고리즘입니다. 이는 불일치가 발생할 때 불필요한 비교를 피하기 위해 텍스트와 패턴에 대한 일부 정보를 사용할 수 있다는 관찰을 기반으로 합니다. 알고리즘은 패턴에 대한 정보가 포함된 테이블을 미리 계산합니다. 테이블은 불일치가 발생할 때 건너뛸 수 있는 패턴 문자 수를 결정합니다. 시간 복잡도 KMP 알고리즘은 O(M+N) .
보이어-무어 알고리즘:
가장 널리 사용되는 패턴 매칭 알고리즘 중 하나는 보이어-무어 연산. 이 알고리즘은 Robert S. Boyer와 J Strother Moore가 1977년에 처음 발표했습니다. 그만큼 보이어-무어 알고리즘은 대부분의 다른 패턴 일치 알고리즘과 마찬가지로 왼쪽에서 오른쪽이 아닌 오른쪽에서 왼쪽으로 더 큰 데이터 또는 텍스트 세트와 패턴을 비교합니다.
그만큼 보이어-무어 알고리즘에는 잘못된 문자 규칙과 좋은 접미사 규칙이라는 두 가지 주요 구성 요소가 있습니다. 잘못된 문자 규칙은 패턴의 문자를 데이터 또는 텍스트의 해당 문자와 비교하여 작동합니다. 문자가 일치하지 않으면 알고리즘은 일치하는 문자를 찾을 때까지 패턴을 오른쪽으로 이동합니다. 좋은 접미사 규칙은 패턴의 접미사를 데이터 또는 텍스트의 해당 접미사와 비교합니다. 접미사가 일치하지 않으면 알고리즘은 일치하는 접미사를 찾을 때까지 패턴을 오른쪽으로 이동합니다.
그만큼 보이어-무어 알고리즘은 효율성으로 유명하며 많은 응용 프로그램에서 널리 사용됩니다. 이는 사용 가능한 가장 빠른 패턴 일치 알고리즘 중 하나로 간주됩니다.
C에서 Boyer-Moore 알고리즘 구현:
구현하려면 보이어-무어 C의 알고리즘에서는 잘못된 문자 규칙을 정의하는 것부터 시작할 수 있습니다. 배열을 사용하여 패턴에서 각 문자의 마지막 발생을 저장할 수 있습니다. 이 배열은 불일치가 발생할 때 패턴을 오른쪽으로 얼마나 멀리 이동해야 하는지 결정할 수 있습니다.
다음은 C에서 잘못된 문자 규칙을 구현하는 방법에 대한 예입니다.
C 코드 복근
C 코드:
void bad_character_rule(char *pattern, int pattern_length, int *bad_char) { int i; for (i = 0; i <no_of_chars; i++) bad_char[i]="-1;" for (i="0;" i < pattern_length; bad_char[(int) pattern[i]]="i;" } pre> <p>In this example, we first initialize the array to -1 for all characters. We then iterate through the pattern and update the array with the last occurrence of each character in the pattern.</p> <p>Next, we can implement the good suffix rule. We can use an array to store the length of the longest suffix of the pattern that matches a suffix of the data or text. This array can be used to determine how far we need to move the pattern to the right.</p> <hr></no_of_chars;>