2024. 1. 10. 20:15ㆍ프로그래밍 공부/Data Structure
12.1 문자열 연산
문서 처리는 급속하게 컴퓨터의 지배적인 기능 중 하나가 되어가고 있다.
컴퓨터는 문서를 편집하거나, 문서를 검색하거나, 인터넷을 통해 문서를 운반하거나,
프린터나 컴퓨터 화면에 문서를 표시하는 데 사용된다.
ex) 인터넷 문서 형식 HTML과 XML: 주로 멀티미디어 컨텐츠를 위한 태그가 추가된 텍스트 형식
인터넷의 수 테라바이트의 정보를 이해하는 것은 상당한 양의 텍스트 처리를 요구한다.
텍스트 처리 알고리즘은
흥미로운 응용 프로그램을 가지고 있을 뿐만 아니라
몇 가지 중요한 알고리즘 설계 패턴을 강조한다.
브루트 포스(brute-force) 방법 :
종종 비효율적이지만 적용 가능성이 넓다.
ex) 패턴 일치 문제
그리디(greedy) 방법:
종종 어려운 문제에 대한 해결책을 근사화할 수 있고 일부 문제의 경우 실제로 최적의 알고리즘을 생성한다.
ex) 텍스트 압축
동적 계획법(다이나믹 프로그래밍, dynamic programming) 설계 패턴:
일부 특수한 경우에 적용하여 해결하는 데 지수 시간이 필요한 다항식 시간의 문제를 해결할 수 있다.
ex) 텍스트 유사성
텍스트 처리
텍스트를 처리하는 알고리즘의 핵심에는 문자열을 처리하는 방법이 있다.
문자열은 과학적, 언어적, 인터넷 응용을 포함한 매우 다양한 출처에서 나올 수 있다.
실제로 다음은 그러한 문자열의 예이다:
P = "CGTAAACTGCTTTAATCAAACGC"
S = "http://java.datastructures.net ".
첫 번째 문자열 P: DNA 응용
두 번째 문자열 S: 이 책에 첨부된 웹사이트의 인터넷 주소(URL)
일반적인 문자열 처리 작업 중 몇 가지는 큰 문자열을 더 작은 문자열로 바꾸는 것이다.
이러한 작업의 결과로 발생하는 조각에 대해 말할 수 있도록
m개의 문자를 가진 문자열 P의 부분 문자열(substring)을 사용하여
P[i]P[i + 1]P[i + 2] ... P[j] 형태의 문자열을 참조한다.
즉, 인덱스 i에서 인덱스 j까지 P의 문자로 구성된 문자열인 0 ≤ i ≤ j ≤ m-1을 포함한다.
엄밀히 말하면 문자열이 실제로 자체의 부분 문자열임을 의미하므로
(i = 0 및 j = m - 1을 취함),
적절한 부분 문자열: i > 0 또는 j - 1로 제한하는 부분 문자열 ex) "TTAATC"
부분 문자열을 참조하는 표기법을 단순화하기 위해 P[i..j]를 사용하여
인덱스 i에서 인덱스 j로 P의 부분 문자열을 표시한다.
즉, P[i..j]=P[i]P[i+1]...P[j].
P의 접두사(prefix): 0 ≤ i ≤ m-1일 때 P[0..i] 형태의 부분 문자열 ex) "CGTAA"
P의 접미사(suffix): 0 ≤ i ≤ m - 1일 때 P[i..m - 1] 형태의 부분 문자열 ex) "CGC"
널 문자열(null string) : i > j이면 P[i..j], 이 때 길이가 0이다.
null 문자열은 접두사이자 다른 문자열의 접미사이다.
문자열의 개념을 상당히 일반적으로 사용할 수 있도록
일반적으로 T와 P의 문자가 유니코드 문자 집합과 같이
잘 알려진 문자 집합에서 명시적으로 나오도록 제한하지 않는다.
기호 σ: 문자 집합 또는 문자가 나올 수 있는 알파벳을 나타낸다.
알파벳 σ의 크기는 | σ|로 표시되고 고정 상수라고 가정한다.
왜냐하면 대부분의 문서 처리 알고리즘은 기본 문자 집합이 유한한 응용 프로그램에서 사용되기 때문이다.
문자열 연산에는 두 가지 버전이 있고 자바에서의 정의는 다음과 같다.
1) String 클래스
수정할 수 없는 문자열(immutable string)을 표현한다.
실제로 문자열을 수정하지 않고 단순히 문자열에 대한 정보를 반환한다.
2) StringBuffer 클래스
수정할 수 있는 문자열(mutable string)을 표현한다.
자신이 적용하는 문자열을 수정한다.
12.1.1 Java String 클래스
Java String 클래스의 주요 연산은 다음과 같다:
length ():
S의 길이 n을 반환한다.
charAt(i):
인덱스가 S인 문자를 반환한다.
startsWith(Q):
Q가 S의 접두사인지 확인한다.
endsWith(Q):
Q가 S의 접미사인지 확인한다.
substring(i,j):
부분 문자열 S[i,j]를 반환한다.
concat(Q):
S와 Q의 연결, 즉 S+Q를 반환한다.
equals(Q):
Q가 S와 같은지 결정한다.
indexOf(Q):
Q가 S의 부분 문자열이면 S에서 Q의 첫 번째 시작하는 인덱스를 반환하고
그렇지 않으면 -1을 반환한다.
이 컬렉션은 수정할 수 없는 문자열에 대한 일반적인 연산을 형성한다.
예제 12.1: 문자열 S = "abcdefghijklmnop"에서 수행되는 다음과 같은 일련의 연산을 고려한다:
| 연산 | 출력 |
| length() | 16 |
| charAt(5) | 'f' |
| concat("qrs") | "abcdefghijklmnopqrs" |
| endsWith("javapop") | false |
| indexOf("ghi") | 6 |
| startsWith("abcd") | true |
| substring(4,9) | "efghij" |
12.2절에서 논의하는 indexOf(Q) 메소드를 제외하고,
위의 모든 메소드는 문자열을 문자 배열로 표현하는 것만으로 쉽게 구현되며,
이는 자바의 표준 문자열 구현이다.
12.1.2 Java String Buffer 클래스
Java StringBuffer 클래스의 주요 메소드는 다음과 같다:
append(Q):
S를 S+Q로 대체하여 S+Q를 반환한다.
insert(i, Q):
인덱스 i에서 시작하는 S 내부에 Q를 삽입하여 얻은 문자열이 되도록
S를 반환하고 업데이트한다.
reverse():
문자열 S를 뒤집어서 반환한다.
setCharAt(i,ch):
인덱스 i에 해당하는 문자를 ch로 설정한다.
charAt(i):
문자열 S에서 인덱스 i에 해당하는 문자를 반환한다.
인덱스 i가 문자열의 인덱스의 경계를 벗어날 경우 오류 조건이 발생한다.
charAt 메소드를 제외하고 대부분의 String 클래스 메소드는
Java의 StringBuffer 객체 S에서 즉시 사용할 수 없다.
다행히 Java StringBuffer 클래스는
String 메소드에 접근하는 데 사용할 수 있는
String 버전 S를 반환하는 toString() 메소드를 제공한다.
예제 12.2: 처음에 S = "abcdefghijklmnop"인 가변 문자열에 대해
수행되는 다음과 같은 일련의 연산을 생각해 보자:
| 연산 | S |
| append("qrs") | "abcdefghijklmnopqrs" |
| insert(3,"xyz") | "abcxyzdefghijklmnopqrs" |
| reverse() | "srqponmlkjihgfedzyxcba" |
| setCharAt(7,'W') | "srqponmWkjihgfedzyxcba" |
12.2 패턴 매칭 알고리즘
문자열에 대한 고전적인 패턴 매칭(pattern matching) 문제:
길이가 n인 텍스트 문자열 T와 길이가 m인 패턴 문자열 P가 주어지며,
P가 T의 부분 문자열인지 여부를 찾고자 한다.
일치의 개념은 T의 부분 문자열이 문자별로 P와 일치하는 어떤 인덱스 i에서 시작하여
T[i] = P[0], T[i + 1] = P[1], ..., T[i + m-1] = P[m - 1]이 되는 것이다.
즉, P = T[i..i + m - 1]이다.
따라서, 패턴 매칭 알고리즘으로부터의 출력은
패턴 P가 T 내에 존재하지 않는다는 것을 나타내거나
또는 P와 일치하는 부분 문자열 T 내의 시작 인덱스를 나타내는 정수일 수 있다.
이것은 정확히 Java String 인터페이스의 indexOf 메소드에 의해 수행되는 계산이다.
또는, T와 일치하는 부분 문자열 P가 시작되는 모든 인덱스를 찾는 것을 원할 수도 있다.
이 섹션에서는 (난이도가 증가하는) 세 가지 패턴 매칭 알고리즘을 제시한다.
12.2.1 브루트 포스
브루트 포스(brute force) 알고리즘 설계 패턴:
일반적인 상황에서 일반적으로 관련된 입력의 가능한 모든 구성을 열거하고,
이 모든 열거된 구성 중 가장 좋은 것을 선택한다.
(쉽게 설명하면 계산 노가다)
우리가 찾고자 하는 것이 있을 때나 어떤 함수를 최적화하고 싶을 때 알고리즘 설계를 위한 강력한 기법이다.
이 기법을 적용하여 브루트 포스 패턴 매칭 알고리즘을 설계할 때,
패턴 매칭 문제를 해결하기 위해 아마도 가장 먼저 생각할 수 있는 알고리즘을 도출한다.
단순히 T에 대한 P의 가능한 모든 배치를 테스트한다.
코드 단편 12.1에 나타난 이 알고리즘은 매우 간단하다.
코드 조각 12.1: 브루트 포스 패턴 매칭.
Algorithm BruteForceMatch(T,P):
Input: Strings T (text) with n characters and P (pattern) with m characters
Output: Starting index of the first substring of T matching P, or an indication
that P is not a substring of T
for i ← 0 to n - m {for each candidate index in T} do
j ← 0
while (j < m and T[i + j] = P[j]) do
j ← j + 1
if j = m then
return i
return "There is no substring of T matching P."
성능
브루트 포스 패턴 매칭 알고리즘은 이보다 더 단순할 수가 없었다.
두 개의 중첩 루프로 구성되는데,
외부 루프는 텍스트 내 패턴의 모든 가능한 시작 인덱스를 통해 인덱싱되고
내부 루프는 패턴의 각 문자를 통해 인덱싱되어 텍스트 내 잠재적으로 해당하는 문자와 비교된다.
따라서 이러한 철저한 검색 접근 방식에서 브루트 포스 패턴 매칭 알고리즘의 정확성은 바로 나타난다.
최악의 경우 브루트 포스 패턴 매칭의 실행 시간은 좋지 않다.
그러나 T의 각 후보 인덱스에 대해 최대 m개의 문자 비교를 수행하여
P가 현재 인덱스에서 T와 일치하지 않는다는 것을 발견할 수 있기 때문이다.
코드 조각 12.1을 참조하면
외부 for문은 최대 n − m+ 1회 실행되고
내부 루프는 최대 m회 실행되는 것을 알 수 있다.
브루트 포스 대입 방법의 실행 시간: O((n − m+ 1)m) → O(nm)
m = n/2일 때 이 알고리즘의 실행 시간: O(n^2)
예제 12.3:
텍스트 문자열 T = "abacaabaccabacabaabb"
그리고 패턴 문자열 P= "abacab"
이 주어졌다고 가정한다.
그림 12.1에서는 T와 P에 대한 브루트 포스 패턴 매칭 알고리즘의 실행을 보여준다.
그림 12.1:
브루트 포스 패턴 일치 알고리즘의 실행 예.
알고리즘은 위에 숫자 레이블로 표시된 27개의 문자 비교를 수행한다.
12.2.2 보이어-무어 알고리즘
처음에는 패턴 P를 하위 문자열로 찾기 위해 항상 T의 모든 문자를 검사해야 한다고 느낄 수 있다.
하지만 항상 그런 것은 아니다.
이 섹션에서 연구하는 보이어-무어(Boyer-Moore,BM) 패턴 일치 알고리즘은
때때로 P와 T에 있는 상당 부분의 문자 간의 비교를 피할 수 있기 때문이다.
유일한 주의 사항은 다음과 같다.
브루트 포스 대입 알고리즘은 잠재적으로 제한되지 않은 알파벳에서도 작동할 수 있지만
BM 알고리즘은 알파벳이 고정된 유한 크기라고 가정한다.
알파벳의 크기가 적당하고 패턴의 길이가 비교적 길 때 가장 빠르게 작동한다.
따라서 BM 알고리즘은 문서에서 단어를 검색하는 데 이상적이다.
이 섹션에서는 Boyer와 Moore의 원래 알고리즘의 단순화된 버전을 설명한다.
BM 알고리즘의 주요 아이디어는
잠재적으로 시간을 절약해 주는 두 가지 휴리스틱을 추가하여
브루트 포스 알고리즘의 실행 시간을 향상시키는 것이다.
대략적으로 말하면 이러한 휴리스틱은 다음과 같다.
거울보기 휴리스틱(Looking-Glass Heuristic):
T에 대해 P의 가능한 배치를 테스트할 때
P의 끝에서 비교를 시작하고 P의 앞쪽으로 뒤로 이동한다.
문자 점프 휴리스틱: T에 대한 P의 가능한 배치를 테스트하는 동안
텍스트 문자 T[i] = c와 해당 패턴 문자 P[j]의 불일치가 다음과 같이 처리된다.
c가 P의 어디에도 포함되어 있지 않으면 P를 T[i]를 완전히 지나서 이동한다
(P의 어떤 문자와도 일치할 수 없기 때문이다).
그렇지 않으면 P에서 문자 c가 T[i]와 정렬될 때까지 P를 이동한다.
이러한 휴리스틱을 곧 공식화할 것이지만 직관적인 수준에서는 통합된 팀으로 작동한다.
거울보기 휴리스틱은 P와 T의 전체 문자 그룹 간의 비교를 피할 수 있도록 다른 휴리스틱을 설정한다.
이 경우 적어도 뒤로 이동하면 목적지에 더 빨리 도달할 수 있다.
T의 특정 위치에서 P를 고려하면
문자 점프 휴리스틱을 사용하여 P를 T에 비해 크게 이동하여 불필요한 비교를 많이 피할 수 있다.
문자 점프 휴리스틱은 T에 대한 P의 잠재적 배치 테스트 초기에 적용될 수 있다면 큰 성과를 거둘 수 있다.
따라서 문자 점프 휴리스틱을 문자열 패턴 일치 알고리즘에 통합할 수 있는 방법을 정의하는 작업을 시작하겠다.
이 경험적 방법을 구현하기 위해
알파벳에서 문자 c를 가져와 패턴과 일치하지 않는 텍스트에서 c와 동일한 문자가 발견되면
패턴 P를 얼마나 멀리 이동할 수 있는지 특성화하는 함수 last(c)를 정의한다.
특히 last(c)를 다음과 같이 정의한다.
• c가 P에 있는 경우 last(c)는 P에서 c가 나타나는 마지막(가장 오른쪽) 인덱스이다.
그렇지 않으면 관례적으로 last(c) = − 1을 정의한다.
문자를 배열의 인덱스로 사용할 수 있으면 마지막 함수를 조회 테이블로 쉽게 구현할 수 있다.
P가 주어지면 O(m+|σ|) 시간에 이 테이블을 계산하는 방법을 간단한 연습으로 남겨둔다.
이 마지막 함수는 문자 점프 휴리스틱을 수행하는 데 필요한 모든 정보를 제공한다.
코드 조각 12.2에서는 BM 패턴 일치 알고리즘을 보여준다.
코드 조각 12.2: Boyer-Moore 패턴 일치 알고리즘.
Algorithm BMMatch(T,P):
Input: Strings T (text) with n characters and P (pattern) with m characters
Output: Starting index of the first substring of T matching P, or an indication
that P is not a substring of T
compute function last
i ← m - 1
j ← m - 1
repeat
if P[j] = T[j] then
if j = m then
return i {a match!}
else
i ← i - 1
j ← j - 1
else
i ← i + m - min(j, 1 + last(T[i])) { jump step }
j ← m - 1
until i > n - 1
return "There is no substring of T matching P."
점프 단계는 그림 12.2에 설명되어 있다.
그림 12.2:
코드 조각 12.2 알고리즘의 점프 단계 그림.
여기서 l = last(T[i])라고 한다.
두 가지 경우를 구별한다:
(a) 1 +l ≤ j, 여기서 패턴을 j − l 단위로 이동한다.
(b) j < 1 + l, 여기서 패턴을 한 단위만큼 이동한다.
그림 12.3에서는 예제 12.3과 유사한 입력 문자열에 대한 Boyer-Moore 패턴 일치 알고리즘의 실행을 보여준다.
그림 12.3: BM 패턴 매칭 알고리즘의 그림.
알고리즘은 숫자 레이블로 표시되는 13개의 문자 비교를 수행한다.
BM 패턴 일치 알고리즘의 정확성은 방법이 바뀔 때마다
가능한 일치 항목을 "건너뛰지" 않는다는 것이 보장된다는 사실에서 비롯된다.
last(c)는 P에서 c가 마지막으로 나타나는 위치이다.
BM 알고리즘의 최악의 실행 시간: O(nm+|σ|)
즉, 마지막 함수의 계산에는 O(m+|σ|) 시간이 걸리고,
실제 패턴 검색에는 최악의 경우 O(nm) 시간이 걸리며,
이는 브루트 포스 대입 알고리즘과 동일하다.
최악의 경우를 달성하는 텍스트 패턴 쌍의 예는 다음과 같다.
그러나 영어 텍스트의 경우 최악의 성능을 달성할 가능성이 낮다.
이 경우 BM 알고리즘은 종종 텍스트의 많은 부분을 건너뛸 수 있기 때문이다.
(그림 12.4 참조) 영어 텍스트에 대한 실험적 증거는
5개의 문자 패턴 문자열에 대해 문자당 수행된 평균 비교 횟수가 0.24임을 보여준다.
그림 12.4: 영어 텍스트에 대한 Boyer-Moore 실행의 예.
BM 패턴 일치 알고리즘의 Java 구현은 코드 조각 12.3에 나와 있다.
코드 조각 12.3: BM 패턴 일치 알고리즘의 Java 구현이다.
알고리즘은 두 가지 정적 메소드로 표현된다.
BMmatch 메소드는 일치를 수행하고 보조 메소드인 LastFunction을 호출하여
문자의 ASCII 코드로 인덱스된 배열로 표현되는 마지막 함수를 계산한다.
BMmatch 메소드는 기존 값 - 1을 반환하여 일치 항목이 없음을 나타낸다.
/** Simplified version of the Boyer-Moore (BM) algorithm, which uses
* only the looking-glass and character-jump heuristics.
* @return Index of the beginning of the leftmost substring of the text
* matching the pattern, or -1 if there is no match. */
public static int BMMatch(String text,String pattern) {
int last = buildLastFunction(pattern);
int n = text.length();
int m = pattern.length();
int i = m - 1;
if (i > n - 1)
return -1; // no match if pattern is longer than text
int j = m - 1;
do {
if (pattern.charAt(j) == text.charAt(i))
if (j == 0)
return i; // match
else { // looking-glass heuristic: proceed right-to-left
i--;
j--;
}
else { // character-jump heuristic
i = i + m - min(j, 1 + last[text.charAt(i)]);
j = m - 1;
}
} while (i <= n - 1);
return -1; // no match
}
public static int[] buildLastFunction(String pattern) {
int[] last = new int[128]; // assume ASCII character set
for (int i = 0; i < 128; i++); {
last[i] = - 1; // initialize array
}
for (int i = 0; i < pattern.length(); i++); {
last[pattern.charAt(i)] = i; // implicit cast to integer ASCII code
}
return last;
}
실제로 Boyer-Moore(BM) 알고리즘의 단순화된 버전을 제시했다.
원래 BM 알고리즘은 문자 점프 휴리스틱보다 패턴을 더 많이 이동할 때마다
부분적으로 일치하는 텍스트 문자열에 대한 대체 이동 휴리스틱을 사용하여
실행 시간 O(n + m + |σ|)을 달성한다.
이 대체 이동 휴리스틱은
다음에 논의할 Knuth-Morris-Pratt 패턴 일치 알고리즘의 주요 아이디어를 적용하는 것을 기반으로 한다.
12.2.3 커누스-모리스-프랫 알고리즘
예제 12.3에 제공된 것과 같이
문제의 특정 인스턴스에 대한 브루트 포스 대입 및 BM 패턴 일치 알고리즘의 최악의 성능을 연구할 때
심각한 비효율성을 발견해야 한다.
특히 텍스트에 대한 패턴의 잠재적 배치를 테스트하는 동안 많은 비교를 수행할 수 있지만
텍스트에서 일치하지 않는 패턴 문자를 발견하면
이러한 비교를 통해 얻은 모든 정보를 버리고 패턴의 다음 증분 배치로 처음부터 다시 시작한다.
이 섹션에서 설명하는 커누스-모리스-프랫(Knuth-Morris-Pratt 또는 "KMP") 알고리즘은
이러한 정보 낭비를 방지하고
이를 통해 최악의 경우 최적인 O(n + m)의 실행 시간을 달성한다.
즉, 최악의 경우 패턴 일치 알고리즘은
텍스트의 모든 문자와 패턴의 모든 문자를
적어도 한 번 검사해야 한다.
실패 함수
KMP 알고리즘의 주요 아이디어:
P의 적절한 이동을 나타내는 실패 함수 f를 계산하기 위해
패턴 문자열 P를 전처리하여 이전에 수행한 비교를 최대한 재사용할 수 있도록 하는 것
실패 함수 f(j): P[1..j]의 접미사인 P의 가장 긴 접두사의 길이
(여기에는 P[0..j]를 넣지 않았다).
또한 f(0) = 0이라는 규칙을 사용한다.
나중에 실패 함수를 효율적으로 계산하는 방법에 대해 논의하겠다.
이 실패 함수의 중요성은 패턴 자체 내에서 반복되는 부분 문자열을 "인코딩"한다는 것이다.
예제 12.4: 예제 12.3의 패턴 문자열 P = "abacab"을 생각해 보자.
문자열 P에 대한 Knuth-Morris-Pratt(KMP) 실패 함수 f(j)는 다음 표에 나와 있다.
| i | 0 | 1 | 2 | 3 | 4 | 5 |
| P[j] | a | b | a | c | a | b |
| f(j) | 0 | 0 | 1 | 0 | 1 | 2 |
코드 조각 12.4에 표시된 KMP 패턴 일치 알고리즘은
텍스트 문자열 T를 패턴 문자열 P와 비교하여 점진적으로 처리한다.
일치하는 항목이 있을 때마다 현재 인덱스가 증가한다.
반면에 불일치가 있고 이전에 P에서 진행한 경우
실패 함수를 참조하여 P에서 T에 대해 P를 계속 확인해야 하는 새 인덱스를 결정한다.
그렇지 않으면 (불일치가 있었고 우리는 P의 시작 부분에 있음)
간단히 T의 인덱스를 증가시킨다 (그리고 P의 인덱스 변수를 시작 부분에 유지한다).
T에서 P 일치 항목을 찾거나 T에 대한 인덱스가 T의 길이인 n에 도달할 때까지
(PinT 패턴을 찾지 못했음을 나타냄)
이 프로세스를 반복한다.
코드 조각 12.4: KMP 패턴 일치 알고리즘.
Algorithm KMPMatch(T,P):
Input: Strings T (text) with n characters and P (pattern) with m characters
Output: Starting index of the first substring of T matching P, or an indication
that P is not a substring of T
f ← KMPFailureFunction(P) {construct the failure function f for P}
i ← 0
j ← 0
while i < n do
if P[j] = T[j] then
if j = m - 1 then
return i - m + 1 {a match!}
else
i ← i - 1
j ← j - 1
else if j > 0 {no match, but we have advanced in P} then
j ← f(j - 1) { j indexes just after prefix of P that must match }
else
i ← i + 1
return "There is no substring of T matching P."
KMP 알고리즘의 주요 부분은 while 루프로,
반복할 때마다 T의 문자와 P의 문자를 비교한다.
이 비교 결과에 따라 알고리즘은
1) T와 P의 다음 문자로 이동하거나
2) P의 새 후보 문자에 대한 실패 함수를 참조하거나
3) T의 다음 인덱스로 다시 시작한다.
이 알고리즘의 정확성은 실패 함수의 정의에 따른다.
건너뛴 모든 비교는 실제로 불필요하다.
왜냐하면 실패 함수는 무시된 모든 비교가 중복되도록 보장하기 때문이다.
즉, 동일한 일치 문자를 다시 비교하는 작업이 포함된다.
그림 12.5: KMP 패턴 일치 알고리즘을 보여준다.
이 패턴의 실패 함수 f는 예제 12.4에 나와 있다.
알고리즘은 숫자 레이블로 표시되는 19개의 문자 비교를 수행한다.
그림 12.5에서는 예제 12.3과 동일한 입력 문자열에 대한 KMP 패턴 일치 알고리즘의 실행을 보여준다.
패턴의 문자와 텍스트의 문자 사이의 비교 중 하나를 다시 실행하지 않으려면 실패 함수를 사용하자.
또한 이 알고리즘은 동일한 문자열에 대해 실행되는 브루트 포스 알고리즘보다
전체 비교 횟수가 적다는 점에 유의하자(그림 12.1).
성능
실패 함수 계산을 제외하면
KMP 알고리즘의 실행 시간은 while 루프의 반복 횟수에 명확하게 비례한다.
분석을 위해 k = i − j를 정의하겠다.
직관적으로 k: 패턴 P가 텍스트 T에 대해 이동된 총량
알고리즘 실행 전체에서 k ≤ n이 있다는 점에 유의하자.
루프가 반복될 때마다 다음 세 가지 경우 중 하나가 발생한다.
• T[i] = P[j]이면 i는 1만큼 증가하고 j도 1만큼 증가하므로 k는 변하지 않는다.
• T[i] ≠ P[j]이고 j > 0이면 i는 변하지 않고 k는 적어도 1만큼 증가하는데,
이 경우 k는 i - j에서 i - f (j - 1)로 바뀌기 때문에,
이는 f (j - 1) < j이기 때문에 양이다.
• T[i] ≠ P[j]이고 j = 0이면 j는 변하지 않으므로
i는 1만큼 증가하고 k는 1만큼 증가한다.
따라서 루프가 반복될 때마다 i 또는 k는 적어도 1만큼(아마도 둘 다) 증가한다.
따라서 KMP 패턴 일치 알고리즘에서 while 루프의 총 반복 횟수는 최대 2n이다.
물론 이 한계를 달성하려면 P에 대한 실패 함수를 이미 계산했다고 가정한다.
KMP 실패 함수 구성
실패 함수를 구성하기 위해 코드 조각 12.5에 표시된 방법을 사용한다.
이는 KMPMatch 알고리즘과 매우 유사한 "부트스트래핑" 프로세스이다.
KMP 알고리즘에서와 같이 패턴을 자체와 비교한다.
일치하는 두 문자가 있을 때마다 f(i) = j + 1로 설정한다.
알고리즘 실행 전체에서 i > j이므로 f(j − 1)는 사용해야 할 때 항상 정의된다.
코드 조각 12.5:
KMP 패턴 일치 알고리즘에 사용되는 실패 함수 계산.
알고리즘이 실패 함수의 이전 값을 어떻게 사용하여 새 값을 효율적으로 계산하는지 확인하라.
Algorithm KMPFailureFunction(P):
Input: String P (pattern) with m characters
Output: The failure function f for P, which maps to j to the length of the longest
prefix of P that is a suffix of P[1..j]
i ← 0
j ← 0
f(0) ← 0
while i < m do
if P[j] = P[i] then
{we have match, but advanced in P}
f(i) ← j + 1
i ← i + 1
j ← j + 1
else if j > 0 then
{ j indexes just after a prefix of P that must match }
j ← f(j - 1)
else
{ we have no match here }
f(i) ← 0
i ← i + 1
알고리즘 KMPFailureFunction의 실행 시간: O(m)
분석은 KMPMatch 알고리즘과 유사하다.
따라서 다음을 갖는다:
명제 12.5:
Knuth-Morris-Pratt 알고리즘은
O(n + m) 시간에 길이가 n인 텍스트 문자열과 길이가 m인 패턴 문자열에 대해 패턴 일치를 수행한다.
KMP 패턴 일치 알고리즘의 Java 구현은 코드 조각 12.6에 나와 있다.
코드 조각 12.6: KMP 패턴 일치 알고리즘의 Java 구현이다.
알고리즘은 두 가지 정적 메소드로 표현된다.
메소드 KMPmatch: 매칭을 수행하고 보조 메소드인 ComputeFailFunction을 호출한다.
보조 메소드 ComputeFailFunction: 배열로 표현되는 실패 함수를 계산한다.
메소드 KMPmatch: 기존 값 -1을 반환하여 일치 항목이 없음을 나타낸다.
public static int KMPMatch(String text, String pattern) {
int n = text.length();
int m = pattern.length();
int[] fail = computeFailFunction(pattern);
int i = 0;
int j = 0;
while (i < n) {
if (pattern.charAt(j) == text.charAt(i))
if (j == m - 1)
return i - m + 1; // match
i++;
j++;
}
else if (j > 0)
j = fail[j - 1];
else
i++;
}
return -1; // no match
}
public static int[] computeFailFunction(String pattern) {
int[] fail = new int[pattern.length()];
fail[0] = 0;
int m = pattern.length();
int j = 0;
int i = 1;
while (i < m) {
if (pattern.charAt(j) == text.charAt(i)) { // j + 1 characters match
fail[i] = j + 1;
i++;
j++;
}
else if (j > 0) // j follows a matching prefix
j = fail[j - 1];
else { // no match
fail[i] = 0;
i++;
}
}
return fail;
}
12.3 트라이
이전 섹션에서 제시한 패턴 매칭 알고리즘은
패턴을 전처리하여(KMP 알고리즘의 실패 함수 또는 BM 알고리즘의 마지막 함수 계산)하여
텍스트에서 검색 속도를 높인다.
이 섹션에서는 보완적인 접근 방식을 취한다.
즉, 텍스트를 전처리하는 문자열 검색 알고리즘을 제시한다.
이 접근 방식은 일련의 쿼리가 고정 텍스트에 대해 수행되어
텍스트 전처리의 초기 비용이 각 후속 쿼리의 속도 향상으로 보상되는 애플리케이션에 적합하다
(ex: 셰익스피어의 햄릿에서 패턴 일치를 제공하는 웹 사이트
또는 Hamlet 주제에 대한 웹 페이지를 제공하는 검색 엔진).
트라이(trie): 빠른 패턴 일치를 지원하기 위해 문자열을 저장하는 트리 기반 자료 구조
트라이의 주요 응용 분야는 정보 검색이다.
실제로 "트라이(trie)"라는 이름은 "retrieval(검색)"이라는 단어에서 유래되었다.
게놈 데이터베이스에서 특정 DNA 서열을 검색하는 것과 같은 정보 검색 응용 프로그램에서
모두 동일한 알파벳을 사용하여 정의된 문자열 모음 S를 받게 된다.
트라이를 지원하는 기본 쿼리 작업은 패턴 일치와 접두사 일치(prefix matching)이다.
후자의 작업에는 문자열 X가 제공되고 X가 접두사로 포함된 S의 모든 문자열을 찾는 작업이 포함된다.
12.3.1 표준 트라이
S의 어떤 문자열도 다른 문자열의 접두사가 되지 않도록
S를 알파벳 σ의 s개 문자열 집합으로 설정한다.
S의 표준 트리(standard trie)는 다음 속성을 갖는 순서 트리 T이다(그림 12.6 참조).
• 루트를 제외한 T의 각 노드에는 σ라는 문자가 표시된다.
• T 내부 노드의 자식 순서는 알파벳 σ의 표준 순서에 의해 결정된다.
• T는 S의 문자열과 각각 연관된 외부 노드들을 가지므로,
루트에서 T의 외부 노드 v로의 경로 상의 노드들의 라벨들의 연결이 v와 연관된 S의 문자열을 산출한다.
따라서 트리 T는 루트에서 T의 외부 노드까지의 경로가 있는 S의 문자열을 나타낸다.
S의 어떤 문자열도 다른 문자열의 접두사가 아니라고 가정하는 것이 중요하다.
이를 통해 S의 각 문자열은 T의 외부 노드와 고유하게 연관된다.
각 문자열 끝에 원래 알파벳 σ에 없는 특수 문자를 추가하여 항상 이 가정을 충족할 수 있다.
표준 트라이 T의 내부 노드는 1에서 d 사이의 자식을 가질 수 있다.
d: 알파벳의 크기
컬렉션 S의 일부 문자열에서 첫 번째 문자에 대해 루트 r에서 해당 자식 중 하나로 이동하는 가장자리가 있다.
게다가, T의 루트로부터 깊이 i의 내부 노드 v로의 경로는
S의 문자열 X의 i개의 문자 접두사 X[0..i - 1]에 대응한다.
실제로, 집합 S의 문자열에서 접두사 X[0..i - 1]를 따를 수 있는 각각의 문자 c에 대하여,
문자 c로 라벨링된 v의 자식이 존재한다.
이와 같이, 트라이는 문자열들의 집합 사이에 존재하는 공통 접두사들을 간결하게 저장한다.
그림 12.6:
문자열 {bear, bell, bid, Bull, buy, Sell, stock, stop}에 대한 표준 트라이.
알파벳에 문자가 두 개만 있는 경우
트라이는 본질적으로 이진 트리이며 일부 내부 노드에는 자식이 하나만 있을 수 있다
(즉, 부적절한 이진 트리일 수 있음).
일반적으로 알파벳에 d개의 문자가 있는 경우
트라이는 각 내부 노드가 1개에서 d개 사이의 자식을 갖는 다중 방향 트리가 된다.
또한 표준 트라이에는 d개 미만의 하위 노드가 있는 내부 노드가 여러 개 있을 가능성이 높다.
예를 들어, 그림 12.6에 표시된 트라이에는 자식이 하나만 있는 여러 내부 노드가 있다.
노드에 문자를 저장하는 트리를 사용하여 트라이를 구현할 수 있다.
다음 제안은 표준 트라이의 몇 가지 중요한 구조적 특성을 제공한다.
명제 12.6:
크기가 d인 알파벳에서 전체 길이가 n인 s개의 문자열 집합 S를 저장하는
표준 트라이는 다음과 같은 속성을 갖는다.
• T의 모든 내부 노드에는 최대 d개의 하위 노드가 있다.
• T에는 s개의 외부 노드가 있다.
• T의 높이는 S에서 가장 긴 문자열의 길이와 같다.
• T의 노드의 개수는 O(n)이다.
트라이의 노드 수에 대한 최악의 경우는
비어 있지 않은 공통 접두사를 공유하는 두 문자열이 없을 때 발생한다.
즉, 루트를 제외한 모든 내부 노드에는 하나의 자식이 있다.
문자열 집합 S에 대한 트리 T는 키가 S의 문자열인 딕셔너리를 구현하는 데 사용될 수 있다.
즉, 루트에서 X의 문자가 나타내는 경로를 추적하여 문자열 X에 대한 검색을 수행한다.
이 경로가 추적될 수 있고 외부 노드에서 종료되면 X가 딕셔너리에 있다는 것을 알 수 있다.
예) 그림 12.6의 트리에서 "bull"에 대한 경로 추적은 외부 노드에서 끝난다.
경로를 추적할 수 없거나 경로를 추적할 수 있지만
내부 노드에서 끝나는 경우 X는 딕셔너리에 없다.
그림 12.6의 예에서 "bet"에 대한 경로는 추적할 수 없으며
"be"에 대한 경로는 내부 노드에서 끝난다.
그런 단어는 딕셔너리에도 없다.
이 딕셔너리 구현에서는 전체 문자열(키) 대신 단일 문자가 비교된다.
크기가 m인 문자열을 검색하는 데 걸리는 시간이 O(dm)임을 쉽게 알 수 있다.
(d: 알파벳의 크기)
실제로 우리는 T의 최대 m + 1개 노드를 방문하고 각 노드에서 O(d) 시간을 소비한다.
일부 알파벳의 경우 해시 테이블이나 검색 테이블에 구현된 문자 딕셔너리를 사용하여
노드에서 소요되는 시간을 O(1) 또는 O(logd)로 향상시킬 수 있다.
그러나 d는 대부분의 응용에서 상수이므로
방문한 노드당 O(d) 시간이 걸리는 간단한 접근 방식을 고수할 수 있다.
위의 논의에서 우리는 트라이를 사용하여
단어 일치라고 하는 특별한 유형의 패턴 일치를 수행할 수 있다.
단어 일치(word matching):
여기서 주어진 패턴이 텍스트의 단어 중 하나와 정확하게 일치하는지 확인하려고 한다.
(그림 12.7 참조)
단어 일치는 패턴이 텍스트의 임의 하위 문자열과 일치할 수 없고
해당 단어 중 하나만 일치하므로
표준 패턴 일치와 다르다.
트라이를 사용하면 길이가 m인 패턴에 대한 단어 일치는 O(dm) 시간이 걸린다.
(d: 알파벳의 크기)
알파벳의 크기가 일정한 경우
(자연어 및 DNA 문자열의 텍스트의 경우)
쿼리에는 패턴 크기에 비례하여 O(m) 시간이 걸린다.
이 체계의 간단한 확장은 접두사 일치 쿼리를 지원한다.
그러나 텍스트에서 패턴이 임의로 발생하는 경우
(예: 패턴이 단어의 적절한 접미사이거나 두 단어에 걸쳐 있음)는
효율적으로 수행될 수 없다.
문자열 집합 S에 대한 표준 트라이를 구성하려면
문자열을 한 번에 하나씩 삽입하는 증분 알고리즘을 사용할 수 있다.
S의 어떤 문자열도 다른 문자열의 접두사가 아니라는 가정을 상기해 보자.
문자열 X를 현재 트라이 T에 삽입하려면
1. T에서 X와 관련된 경로를 추적하려고 한다.
X는 T에 이미 존재하지 않으며, S의 어떤 문자열도 다른 문자열의 접두사가 아니므로,
X의 끝에 도달하기 전에 T의 내부 노드 v에서 경로 추적을 중지할 것이다.
2. X의 나머지 문자를 저장하기 위해 v의 새로운 노드 자손 체인을 만든다.
X를 삽입하는 시간: O(dm)
(m: X의 길이, d: 알파벳의 크기)
집합 S에 대한 전체 트라이를 구성하는 데 걸리는 시간: O(dn)
(n: S 문자열의 전체 길이)
그림 12.7: 표준 트라이를 사용한 단어 일치 및 접두사 일치:
(a) 검색할 텍스트;
(b) 텍스트의 단어에 대한 표준 트라이
(stop word라고도 알려진 관사와 전치사는 제외),
외부 노드에는 단어 위치 표시가 추가된다.
표준 트라이의 단점
표준 트라이에는 잠재적인 공간 비효율성이 있다.
즉, 표준 트라이에는 자식이 하나만 있는 노드가 잠재적으로 많으며 이러한 노드의 존재는 낭비이다.
12.3.2 압축 트라이
압축 트라이(compressed trie):
표준 트리와 유사하지만 트리의 각 내부 노드에 최소한 두 개의 하위 노드가 있음을 보장한다.
단일 하위 노드 체인을 개별 가장자리로 압축하여 이 규칙을 적용한다.
(그림 12.8 참조)
T를 표준 트라이라고 하자.
v가 하나의 자식을 갖고 루트가 아닌 경우 T의 내부 노드 v가 중복된다(redundant)고 말한다.
예를 들어, 그림 12.6의 트리에는 8개의 중복 노드가 있다.
또한 다음과 같은 경우 k ≥ 2 간선의 체인 (v0,v1)(v1,v2)...(vk−1,vk)이 중복된다고 가정해 보겠다.
• vi는 i = 1, ..., k−1 1인 경우 중복된다.
• v0 및 vk는 중복되지 않다.
k ≥ 2 간선의 각 중복 체인 (v0,v1) ... (v(k−1),vk)을 단일 간선 (v0,vk)으로 대체하고,
노드 v1,...,vk의 레이블 연결로 vk에 라벨을 다시 붙이면 T를 압축 트라이로 변환할 수 있다.
그림 12.8: Bear, Bell, Bid, Bull, Buy, Sell, Stock, Stop 문자열에 대한 압축 트리.
이를 그림 12.6에 표시된 표준 트라이와 비교해 보자.
따라서 압축 트라이의 노드에는
개별 문자가 아닌 컬렉션에 있는 문자열의 부분 문자열인 문자열로 레이블이 지정된다.
표준 트라이에 비해 압축 트라이가 가지는 장점
1. 압축 트라이의 노드 수가 문자열의 수에 비례한다.
2. 문자열의 전체 길이에 비례한다.
명제 12.7:
크기 d의 알파벳에서 s개의 문자열 모음 S를 저장하는 압축 트라이는 다음과 같은 속성을 갖는다.
• T의 모든 내부 노드에는 최소한 두 개의 자식과 대부분의 d 자식이 있다.
• T에는 s개의 외부 노드가 있다.
• T의 노드 수는 O(s)이다.
세심한 독자는 경로 압축이 노드 레이블의 해당 확장으로 상쇄되기 때문에
경로 압축이 상당한 이점을 제공하는지 궁금해할 수 있다.
실제로 압축된 트라이는 기본 구조에
이미 저장된 문자열 컬렉션에 대한 보조 인덱스 구조로 사용될 때만 실제로 유리하며
컬렉션에 있는 문자열의 모든 문자를 실제로 저장할 필요는 없다.
예를 들어, 문자열 모음 S가 문자열 S[0], S[1], ..., S[s − 1]의 배열이라고 가정한다.
노드의 레이블 X를 명시적으로 저장하는 대신
X = S[i][j..k]와 같이 정수의 삼중항(i, j, k)으로 암시적으로 표현한다.
즉, X는 j번째부터 k번째까지 포함된 문자로 구성된 S[i]의 하위 문자열이다.
(그림 12.9의 예를 참조하자. 또한 그림 12.7의 표준 트라이와 비교하자.)
그림 12.9:
(a) 배열에 저장된 문자열 모음 S.
(b) S에 대한 압축된 트리의 간결한 표현.
이 추가 압축 방식을 사용하면 트라이 자체의 전체 공간을
표준 트라이의 O(n)에서 압축 트라이의 O(s)로 줄일 수 있다.
(n: S에 있는 문자열의 전체 길이, s: 숫자)
물론 S에 다른 문자열을 저장해야 하지만 그럼에도 불구하고 트라이를 위한 공간을 줄인다.
다음 섹션에서는 문자열 컬렉션을 컴팩트하게 저장할 수 있는 응용을 제시한다.
12.3.3 접미사 트라이
문자열 X의 접미사 트라이(suffix trie) or 접미사 트리(suffix tree) or 위치 트리(position tree):
컬렉션 S의 문자열이 모두 문자열 X의 접미사인 경우의 트라이
ex) 그림 12.10a는 문자열 "minimize"의 8개 접미사에 대한 접미사 트라이를 보여준다.
접미사 트라이의 경우 이전 섹션에 제시된 압축 표현을 더욱 단순화할 수 있다.
즉, 각 정점의 레이블은 문자열 X[i..j]를 나타내는 쌍(i,j)이다.
(그림 12.10b 참조)
X의 어떤 접미사도 다른 접미사의 접두사가 아니라는 규칙을 만족시키기 위해
원래 알파벳 σ에 없는 $로 표시된 특수 문자를 X의 끝에 (그리고 모든 접미사에) 추가할 수 있다.
즉, 문자열 X의 길이가 n인 경우
i = 0,...,n − 1에 대해 n 문자열 X[i..n − 1]$ 집합에 대한 트라이를 만든다.
공간 절약
접미사 트라이를 사용하면 압축 트라이에 사용되는 기술을 포함하여
여러 공간 압축 기술을 사용하여 표준 트라이에 비해 공간을 절약할 수 있다.
이제 접미사 트라이에 대해 트라이를 간결하게 표현하는 이점이 분명해졌다.
길이가 n인 문자열 X의 접미사의 총 길이는 다음과 같다.
1 + 2 + .... + n = n(n + 1) / 2
X의 모든 접미사를 명시적으로 저장하려면 O(n^2) 공간이 필요하다.
그럼에도 불구하고 접미사 트라이는 다음 명제에서 공식적으로 언급된 것처럼
O(n) 공간에서 암시적으로 이러한 문자열을 나타낸다.
명제 12.8:
길이 n의 문자열 X에 대한 접미사 트라이 T의 간결한 표현은 O(n) 공간을 사용한다.
건설
우리는 섹션 12.3.1에 주어진 것과 같은 증분 알고리즘을 사용하여
길이 n의 문자열에 대한 접미사 트라이를 구성할 수 있다.
이 구성에는 접미사의 전체 길이가 n 단위로 2차이기 때문에 O(d n^2) 시간이 걸린다.
그러나 길이가 n인 문자열에 대한 (컴팩트) 접미사 트라이는
일반적인 시도와는 다른 특수 알고리즘을 사용하여 O(n) 시간에 구성될 수 있다.
그러나 이 선형 시간 구성 알고리즘은 상당히 복잡하므로 여기서는 보고하지 않는다.
그럼에도 불구하고 우리는 다른 문제를 해결하기 위해 접미사 트라이를 사용하려고 할 때
이 빠른 구성 알고리즘의 존재를 활용할 수 있다.
그림 12.10:
(a) 문자열 X = "minimize''에 대한 접미사 트라이 T.
문자열 X의 접미사: e, ze, ize, mize, imize, nimize, inimize, minimize
(b) 쌍 (i,j)가 X[i..j]를 나타내는 T의 압축 표현.
접미사 트라이 사용
문자열 X에 대한 접미사 트라이 T는
텍스트 X에 대한 패턴 일치 쿼리를 효율적으로 수행하는 데 사용될 수 있다.
즉, T에서 P와 연관된 경로를 추적하여 패턴 P가 X의 하위 문자열인지 여부를 확인할 수 있다.
해당 경로를 추적할 수 있는 경우에만 X의 하위 문자열이다.
패턴 일치 알고리즘의 세부 사항은 코드 조각 12.7에 나와 있으며
접미사 트라이의 압축 표현에서 노드 레이블에 대해 다음과 같은 추가 속성을 가정한다.
노드 v에 레이블 (i,j)이 있고
Y가 루트에서 v(포함)까지의 경로와 연관된 길이 y의 문자열인 경우
X [j − y + 1. .j] =Y이다.
이 속성을 사용하면 일치 항목이 발생할 때 텍스트에서 패턴의 시작 인덱스를 쉽게 계산할 수 있다.
.
코드 조각 12.7:
접미사 트라이를 사용한 패턴 일치.
(start(v),end(v))로 노드 v의 레이블을 나타낸다.
즉, v와 연관된 텍스트의 하위 문자열을 지정하는 인덱스 쌍이다.
Algorithm suffixTrieMatch(T,P):
Input: Compact suffix trie T for a text X and pattern P
Output: Starting index of a substring of X matching P or an indication that P
is not a substring of X
p ← P.length() { length of suffix of the pattern to be matched }
j ← 0 { start of suffix of the pattern to be matched }
v ← T.root()
repeat
f ← true { flag indicating that no child was successfully processed }
for each child w of v do
i ← start(v)
if P[j] = T[i] then
{ process child w }
x ← end(w) - i + 1
if p ≤ x then
{ suffix is shorter than or of the same length of the node label }
if P[j..j + p - 1] = X[i..i + p - 1] then
return i - j { match }
else
return "P is not a substring of X"
else
{ suffix is longer than the node label }
if P[j..j + x - 1] = X[i..i + x - 1] then
p ← p - x { update suffix length }
j ← j + x { update suffix start length }
v ← w
f ← false
break out of the for loop
until f or T.isExternal(v)
return "P is not a substring of X"
suffixTrieMatch 알고리즘의 정확성은 다음 이벤트 중 하나가 발생할 때까지
패턴 P의 문자를 한 번에 하나씩 일치시키는 트라이 T를 검색한다는 사실에서 따른다.
• 패턴 p와 완전히 일치한다.
• 불일치가 발생한다(break 없이 for 루프가 종료되어 발견됨).
• 외부 노드를 처리한 후에도 일치해야 할 P 문자가 남아 있다.
m: 패턴 P의 크기, d: 알파벳의 크기
suffixTrieMatch 알고리즘의 실행 시간을 결정하기 위해 다음과 같은 관찰을 수행한다.
• 트라이의 최대 m + 1개 노드를 처리한다.
• 처리된 각 노드에는 최대 d개의 하위 노드가 있다.
• 처리된 각 노드 v에서 v의 각 하위 w에 대해
최대 한 번의 문자 비교를 수행하여 v의 하위 항목을 다음에 처리해야 하는지 결정한다
(이는 v의 하위 항목을 색인화하기 위해 빠른 딕셔너리를 사용하여 개선될 수 있음).
• 처리된 노드 전체에서 최대 m개의 문자 비교를 수행한다.
• 각 문자 비교에 O(1) 시간을 소비한다.
성능
알고리즘 suffixTrieMatch가 O(dm) 시간에 패턴 일치 쿼리를 수행한다고 결론을 내린다
(그리고 접미사 트라이에 있는 노드의 하위 항목을 색인화하기 위해
딕셔너리를 사용하는 경우 더 빠르게 실행될 수 있다).
실행 시간은 텍스트 X의 크기에 의존하지 않는다.
또한 실행 시간은 패턴 크기에 따라 선형이다.
즉, 일정한 크기의 알파벳의 경우 O(m)이다.
따라서 접미사 트라이는
일련의 패턴 일치 쿼리가 고정 텍스트에 대해 수행되는 반복적인 패턴 일치 응용에 적합하다.
이 섹션의 결과를 다음 제안으로 요약한다.
명제 12.9:
X: 크기가 d인 알파벳의 n개 문자로 구성된 텍스트 문자열
시간에 X에 대한 패턴 일치 쿼리를 수행하는 시간: O(dm)
(m: 패턴의 길이)
공간 사용: O(n)
X의 접미사 트라이 구성 시간: O(dn)
12.3.4 검색 엔진
World Wide Web에는 방대한 양의 텍스트 문서(웹 페이지)가 포함되어 있다.
웹 크롤러(Web crawler): 웹 페이지에 대한 정보를 수집하는 프로그램
이 정보는 특수 딕셔너리 데이터베이스에 저장된다.
웹 검색 엔진(search engine):
사용자가 이 데이터베이스에서 관련 정보를 검색할 수 있으며
이를 통해 주어진 키워드가 포함된 웹의 관련 페이지를 식별할 수 있는 프로그램
이 섹션에서는 검색 엔진의 단순화된 모델을 제시한다.
역 파일
역 인덱스(inverted index) 또는 역 파일(inverted file):
검색 엔진이 저장하는 핵심 정보로 키-값 쌍(w, L)을 저장하는 딕셔너리
(w: 단어, L: 단어 w를 포함하는 페이지 모음)
인덱스 용어(index terms): 본 딕셔너리에 포함된 핵심어(단어)
가능한 한 큰 어휘항목과 고유명사의 집합이어야 한다.
발생 리스트(occurence list): 본 딕셔너리의 요소
가능한 한 많은 웹 페이지를 포함해야 한다.
다음으로 구성된 자료 구조를 사용하여 역 인덱스를 효율적으로 구현할 수 있다.
1. 용어의 발생 리스트를 저장하는 배열(특정 순서 없음)
2. 인덱스 용어의 집합에 대한 압축된 트라이이다.
여기서 각 외부 노드는 연관된 용어의 발생 리스트 색인을 저장한다.
발생 리스트를 트라이 외부에 저장하는 이유
트라이 자료 구조의 크기를 내부 메모리에 맞도록 충분히 작게 유지하기 위해서
대신 전체 크기가 크기 때문에 발생 리스트를 디스크에 저장해야 한다.
자료 구조를 사용하면 단일 키워드에 대한 쿼리는 단어 일치 쿼리와 유사하다(섹션 12.3.1 참조).
즉, 트라이에서 키워드를 찾고 연관된 발생 리스트를 반환한다.
여러 개의 키워드가 지정되고 원하는 출력이 지정된 모든 키워드를 포함하는 페이지인 경우
트라이를 사용하여 각 키워드의 발생 리스트를 검색하고 교차점을 반환한다.
교차점 계산을 용이하게 하기 위해 각 발생 리스트는 주소 또는 딕셔너리로 정렬된 시퀀스로 구현되어야 한다
(예를 들어 섹션 11.6에서 논의된 일반 병합 계산 참조).
특정 키워드가 포함된 페이지 리스트를 반환하는 기본 작업 외에도
검색 엔진은 반환된 페이지의 관련성을 기준으로 순위(ranking)를 지정하여 중요한 추가 서비스를 제공한다.
검색 엔진을 위한 빠르고 정확한 순위 알고리즘을 고안하는 것은
컴퓨터 연구원과 전자 상거래 회사에게 중요한 과제이다.
12.4 텍스트 압축
이 섹션에서는 중요한 텍스트 처리 작업인 텍스트 압축(text compression)을 고려한다.
이 문제에서는 ASCII 또는 유니코드 문자 집합과 같은 일부 알파벳을 통해 정의된 문자열 X가 제공되며
X를 작은 이진 문자열 Y(문자 0과 1만 사용)로 효율적으로 인코딩하려고 한다.
텍스트 압축의 활용
1. 텍스트 압축은 모뎀 회선이나 적외선 연결과 같은 낮은 대역폭 채널을 통해 통신하고
텍스트를 전송하는 데 필요한 시간을 최소화하려는 모든 상황에서 유용하다.
2. 텍스트 압축은 대용량 문서 모음을 보다 효율적으로 저장하여
고정 용량 저장 장치에 가능한 한 많은 문서를 저장할 수 있도록 하는 데에도 유용하다.
이 섹션에서 살펴보는 텍스트 압축 방법은 이다.
ASCII 및 유니코드 시스템과 같은 표준 인코딩 체계는
고정 길이 이진 문자열을 사용하여 문자를 인코딩한다
(ASCII 시스템에서는 7비트, 유니코드 시스템에서는 16비트).
허프만 코드(Huffman code):
문자열 X에 최적화된 가변 길이 인코딩을 사용하는 텍스트 압축 방법
최적화는 문자 빈도(frequency)의 사용을 기반으로 하며,
각 문자 c에 대해 문자열 X에 c의 횟수의 카운트 f(c)로 나타낸다.
허프만 코드는 짧은 코드의 단어 문자열을 사용하여 빈도가 높은 문자를 인코딩하고
긴 코드의 단어 문자열을 사용하여 빈도가 낮은 문자를 인코딩함으로써
고정 길이 인코딩에 비해 공간을 절약한다.
문자열 X를 인코딩하기 위해
X의 각 문자를 고정 길이 코드 단어에서 가변 길이 코드 단어로 변환하고
X에 대한 인코딩 Y를 생성하기 위해 이러한 모든 코드 단어를 연결한다.
모호성을 피하기 위해 다음과 같다.
인코딩에 있는 어떤 코드 단어도 인코딩에 있는 다른 코드 단어의 접두사가 아니라고 주장한다.
이러한 코드를 접두어 코드(prefix code)라고 하며 X를 되찾기 위해 Y의 디코딩을 단순화한다.
(그림 12.11 참조)
이러한 제한이 있더라도 가변 길이 접두어 코드로 인한 절감 효과는 상당할 수 있다.
문자 빈도에는 큰 차이가 있다
(거의 모든 음성 언어의 자연어 텍스트의 경우처럼).
X에 대한 최적의 가변 길이 접두사 코드를 생성하기 위한
허프만의 알고리즘은 코드를 나타내는 이진 트리 T의 구성을 기반으로 한다.
루트를 제외한 T의 각 노드는 코드 단어의 비트를 나타내며,
각 왼쪽 자식은 "0"을 나타내고 각 오른쪽 자식은 "1"을 나타낸다.
각 외부 노드 v는 특정 문자와 연관되어 있으며
해당 문자에 대한 코드 워드는
T의 루트에서 v까지의 경로에 있는 노드와 연관된 비트 시퀀스로 정의된다.
(그림 12.11 참조)
각 외부 노드 v는 빈도 f(v)를 가진다.
빈도(frequency) f(v): 단순히 v와 관련된 문자의 X에 있는 빈도
또한, 각 내부 노드 T에 v에 빈도 f(v)를 가진다.
빈도 f(v)는 루트를 둔 부분 트리의 모든 외부 노드의 주파수의 합이다.
그림 12.11:
입력 문자열 X에 대한 허프만 코드의 예 그림
= "a fast runner need never be afraid of the dark.":
(a) X의 각 문자 빈도;
(b) 문자열 X에 대한 허프만 트리 T.
문자 c에 대한 코드는 T의 루트에서 c가 저장된 외부 노드까지의 경로를 추적하고
왼쪽 자식을 0에 연결하고 오른쪽 자식을 1에 연결하여 얻는다.
예를 들어 "a"의 코드는 010이고 "f"의 코드는 1100이다.
12.4.1 허프만 코딩 알고리즘
허프만 코딩 알고리즘은
단일 노드 이진 트리의 루트 노드가 되는 문자열 X의 d개의 개별 문자 각각으로 시작한다.
알고리즘은 일련의 라운드로 진행된다.
각 라운드에서 알고리즘은 빈도가 가장 작은 두 개의 이진 트리를 가져와 단일 이진 트리로 병합한다.
나무가 하나만 남을 때까지 이 과정을 반복한다.
(코드 조각 12.8을 참조하자.)
Huffman 알고리즘의 while문의 각 반복은
힙으로 표시되는 우선순위 큐를 사용하여 O(logd) 시간에 구현될 수 있다.
또한 각 반복은 Q에서 두 개의 노드를 가져와서 하나를 추가한다.
이 프로세스는 Q에 정확히 하나의 노드가 남기 전에 d − 1번 반복된다.
허프만 알고리즘의 실행 시간: O(n + dlogd)
이 알고리즘의 정확성에 대한 완전한 정당화는 여기서 우리의 범위를 벗어나지만,
그 직관은 간단한 아이디어에서 비롯된다는 점에 주목한다.
즉, 모든 최적의 코드는 두 개의 가장 낮은 빈도 문자인 a와 b에 대한 코드 워드가
마지막 비트에서만 다른 최적 코드로 변환될 수 있다.
a와 b가 문자 c로 대체된 문자열에 대한 인수를 반복하면 다음이 제공된다.
명제 12.10:
허프만의 알고리즘은 O(n + dlogd) 시간에 d 개의 개별 문자를 사용하여
길이가 n인 문자열에 대한 최적의 접두사 코드를 구성한다.
코드 조각 12.8: 허프만 코딩 알고리즘.
Algorithm Huffman(X):
Input: Strings X of length n with d distinct characters
Output: Coding tree for X
Compute the frequence f(c) of each character c of X.
Initialize a priority queue Q.
for each character c in X do
Create a single-node binary tree T storing c.
Insert T into Q with key f(c).
while Q.size() > 1 do
f1 ← Q.min().key()
T1 ← Q.removeMin()
f2 ← Q.min().key()
T2 ← Q.removeMin()
Create a new binary tree T with left subtree T1 and left subtree T2.
Insert T into Q with key f1 + f2.
return tree Q.removeMin()
12.4.2 그리디 방법
최적의 인코딩을 구축하기 위한 허프만의 알고리즘은
그리디 방법(greedy method)이라는 알고리즘 설계 패턴을 적용한 예이다.
이 디자인 패턴은 구조의 일부 속성을 최소화하거나 최대화하면서
일부 구조를 구성하려는 최적화 문제에 적용된다.
그리디 방법 패턴의 일반 공식은 브루트 포스 대입 방법 패턴만큼 간단하다.
그리디 방법을 사용하여 주어진 최적화 문제를 해결하기 위해 일련의 선택을 진행한다.
시퀀스는 잘 이해된 시작 조건에서 시작하여 해당 초기 조건에 대한 비용을 계산한다.
그런 다음 패턴은 현재 가능한 모든 선택 중에서
최상의 비용 개선을 달성하는 결정을 식별하여
반복적으로 추가 선택을 하도록 요청한다.
이 접근 방식이 항상 최적의 솔루션으로 이어지는 것은 아니다.
그러나 이것이 효과가 있는 몇 가지 문제가 있으며
그러한 문제는 탐욕 선택 특성(greedy-choice property)을 가지고 있다고 한다.
이는 잘 정의된 시작 조건에서 시작하여 일련의 지역적 최적 선택
(즉, 당시에 사용할 수 있는 가능성 중에서 현재 최선의 선택)을 통해
전역 최적 조건에 도달할 수 있다는 특성이다.
최적의 가변 길이 접두사 코드를 계산하는 문제는 탐욕 선택 속성을 갖는 문제의 한 예일 뿐이다.
12.5 텍스트 유사성 테스트
유전학과 소프트웨어 엔지니어링에서 발생하는 일반적인 텍스트 처리 문제는
두 텍스트 문자열 간의 유사성을 테스트하는 것이다.
유전학 응용에서 두 문자열은 DNA의 두 가닥에 해당할 수 있으며,
예를 들어 두 개인에게서 나올 수 있으며,
해당 DNA 서열에 공통된 긴 하위 서열이 있는 경우
유전적으로 관련이 있는 것으로 간주된다.
마찬가지로, 소프트웨어 엔지니어링 애플리케이션에서
두 문자열은 동일한 프로그램에 대한 두 버전의 소스 코드에서 나올 수 있으며,
한 버전에서 다음 버전으로 어떤 변경이 이루어졌는지 확인할 수 있다.
실제로 두 문자열 사이의 유사성을 결정하는 것은
Unix와 Linux 운영 체제에 텍스트 파일을 비교하기 위한
diff라는 프로그램이 함께 제공되는 일반적인 작업으로 간주된다.
12.5.1 최장 공통 부분 수열 문제
두 문자열 간의 유사성을 정의할 수 있는 여러 가지 방법이 있다.
그럼에도 불구하고 우리는 문자열과 그 하위 시퀀스를 사용하여
이 문제의 간단하면서도 일반적인 버전을 추상화할 수 있다.
문자열 X = x0x1x2 ... x(n−1)이 주어지면
X의 하위 시퀀스는 xi1 xi2 ...xik 형식의 임의의 문자열이며,
여기서 ij < ij+1은 반드시 연속적이지는 않지만
그럼에도 불구하고 X에서 순서대로 가져온 문자열이다.
예시) 문자열 AAAG는 문자열 CGATAATTGAGA의 부분 시퀀스이다.
문자열의 하위 문자열 개념은 섹션 12.1에 정의된 문자열의 부분 문자열 개념과 다르다.
문제 정의
최장 공통 부분 수열 문제(LCS, Longest Common Subsequence):
일부 알파벳 위에 X = x0x1x2 ...xn-1 및 Y = y0y1y2 ... ym-1의 두 문자열이 주어지고
X와 Y 둘 모두의 하위 시퀀스인 가장 긴 문자열 S를 찾도록 요청받는 문제
가장 긴 공통 부분 수열 문제를 해결하는 한 가지 방법은
X의 모든 부분 수열을 열거하고 Y의 부분 수열이기도 한 가장 큰 부분 수열을 취하는 것이다.
X의 각 문자가 부분 수열에 포함되거나 포함되지 않기 때문에
잠재적으로 2^n개의 서로 다른 부분 수열이 있을 수 있다.
X는 Y의 하위 시퀀스인지 여부를 결정하는 데 각각 O(m) 시간이 필요하다.
따라서 이러한 브루트 포스 접근 방식은
O((2^n)m) 시간에 실행되는 지수 시간 알고리즘을 생성하므로 매우 비효율적이다.
이 섹션에서는 다이나믹 프로그래밍(dynamic programming)이라는 알고리즘 설계 패턴을 사용하여
이보다 훨씬 빠르게 가장 긴 공통 부분 시퀀스 문제를 해결하는 방법에 대해 설명한다.
12.5.2 다이나믹 프로그래밍
기하급수적인 시간이 필요한 것처럼 보이는 문제를 해결하기 위해
다항식 시간 알고리즘을 생성할 수 있는 알고리즘 기술은 거의 없다.
다이나믹 프로그래밍(dynamic programming)은 그러한 기술 중 하나이다.
또한 다이나믹 프로그래밍 기술을 적용하여 생성된 알고리즘은 일반적으로 매우 간단하다.
테이블을 채우는 데 필요한 중첩 루프를 설명하는 데 몇 줄의 코드만 필요한 경우가 많다.
다이나믹 프로그래밍 솔루션의 구성 요소
다이나믹 프로그래밍 기술은
주로 무언가를 수행하는 "최상의" 방법을 찾고자 하는 최적화 문제에 사용된다.
"무언가"를 수행하는 다양한 방법의 수는 기하급수적으로 늘어나는 경우가 많으므로
가장 작은 문제 크기를 제외하고는 최선을 찾는 브루트 포스 대입 검색이 계산상 불가능하다.
그러나 문제에 우리가 활용할 수 있는 일정량의 구조가 있는 경우에는
다이나믹 프로그래밍 기술을 이러한 상황에 적용할 수 있다.
이 구조에는 다음 세 가지 구성 요소가 포함된다.
단순 하위 문제:
전역 최적화 문제를 하위 문제로 반복적으로 나누는 방법이 있어야 한다.
더욱이 i, j, k 등과 같은 몇 가지 지수만으로
하위 문제를 정의하는 간단한 방법이 있어야 한다.
하위 문제 최적화:
전역 문제에 대한 최적의 솔루션은 최적의 하위 문제 솔루션으로 구성되어야 한다.
차선의 하위 문제를 포함하는 전역적으로 최적인 솔루션을 찾을 수 없어야 한다.
하위 문제 중첩:
관련되지 않은 하위 문제에 대한 최적의 솔루션에는
공통 하위 문제가 포함될 수 있다.
다이나믹 프로그래밍 알고리즘의 일반적인 구성 요소를 제공한 후
이를 가장 긴 공통 부분 수열 문제에 적용하는 방법을 보여준다.
12.5.3 LCS 문제에 동적 프로그래밍 적용하기
동적 계획법을 사용하면 지수 시간보다 훨씬 빠르게 가장 긴 공통 부분 수열 문제를 해결할 수 있다.
위에서 언급한 바와 같이 동적 프로그래밍 기법의 핵심 구성 요소 중 하나는
하위 문제 최적화 및 하위 문제 중첩 속성을 만족하는 단순 하위 문제를 정의하는 것이다.
LCS 문제에서 길이가 각각 n과 m인 두 개의 문자열 X와 Y가 주어졌고,
X와 Y의 부분 수열인 가장 긴 문자열 S를 찾으라는 요청을 받았다.
X와 Y는 다음과 같다.
문자열인 경우,
하위 문제를 정의하는 데 사용할 자연적인 인덱스 집합,
즉 문자열 X와 Y에 대한 인덱스가 있다.
따라서 하위 문제를 L[i, j] 값을 계산하는 문제로 정의하겠다.
X[0..i] = x0x1x2... xi 및 Y[0..j] = y0y1y2 ... yj의 하위 시퀀스인
가장 긴 문자열의 길이를 나타낸다.
이 정의를 통해 최적의 하위 문제 해법으로 L[i,j]를 다시 작성할 수 있다.
이 정의는 두 가지 경우 중 어떤 경우에 해당하는지에 따라 달라진다.
(그림 12.12 참조)
• xi = yj.
이 경우 X[0..i]의 마지막 문자와 Y[0..j]의 마지막 문자가 일치한다.
이 문자가 X[0..i]와 Y[0..j]의 가장 긴 공통 부분 수열에 속한다고 주장한다.
이 주장을 정당화하기 위해 그것이 사실이 아니라고 가정해 보겠다.
가장 긴 공통 부분 수열 xi1xi2...xik = yj1yj2 ...yjk가 있어야 한다.
xik = xi 또는 yjk = yj이면 ik =i 및 jk = j를 설정하여 동일한 시퀀스를 얻는다.
또는 xjk ≠ xi이면 끝에 xi를 추가하여 훨씬 더 긴 공통 부분 수열을 얻을 수 있다.
따라서 X[0..i]와 Y[0..j]의 가장 긴 공통 부분 수열은 xi로 끝난다.
그러므로 xi = yj인 경우 L[i,j]=L[i−1,j − 1] + 1이다.
• xi ≠ yj.
이 경우 xi와 yj를 모두 포함하는 공통 부분 수열을 가질 수 없다.
즉, xi로 끝나는 공통 하위 시퀀스나
yj로 끝나는 공통 하위 시퀀스를 가질 수 있지만
둘 다는 아닐 수도 있다.
그러므로 xi ≠yj인 경우 L[i, j] = max{L[i −1,j], L[i, j−1]}이다.
i = 0 또는 j = 0인 경계 사례에서 이 두 방정식을 모두 이해하기 위해
i = −1, 0, 1,...n − 1에 대해 L[i, − 1] = 0을 할당한다.
그리고 j = −1,0,1,...,m−1인 경우 L[−1, j] = 0이다.
위의 L[i,j] 정의는 하위 문제 최적화를 만족한다.
왜냐하면 하위 문제에 대한 가장 긴 공통 부분 수열을 갖지 않으면
가장 긴 공통 부분 수열을 가질 수 없기 때문이다.
또한 하위 문제 해법 L[i, j]는
여러 다른 문제(즉, 문제 L[i+ 1, j], L[i,j+ 1] 및 L[i+ 1))에 사용될 수 있기 때문에
하위 문제 중첩을 사용한다.
그림 12.12: 가장 긴 공통 부분 수열 알고리즘의 두 가지 경우:
(a) xi = yj; (b) xi ≠ yj.
알고리즘은 일치 항목이 아닌 L[i,j] 값만 저장한다.
LCS 알고리즘
L[i, j]의 정의를 알고리즘으로 바꾸는 것은 실제로 매우 간단하다.
i = 0 또는 j = 0인 경계 경우에 대해 (n+ 1) × (m + 1) 배열 L을 초기화한다.
즉, i = −1,0,1,..., n − 1에 대해 L[i, − 1] = 0,
그리고 j = −1,0,1,..., m − 1에 대해 L[− 1, j] = 0을 초기화한다.
(이는 표기법을 약간 남용한 것이다.
실제로는 0부터 시작하여 L의 행과 열을 색인화해야 하기 때문이다.)
그런 다음 X와 Y의 가장 긴 공통 부분 수열의 길이인
L[n − 1, m − 1]을 얻을 때까지
L에 값을 반복적으로 구축한다.
코드 조각 12.9에서는
이 접근 방식이 어떻게 최장 공통 부분 시퀀스(LCS) 문제에 대한
동적 프로그래밍 솔루션을 제공하는지에 대한
의사 코드 설명을 제공한다.
코드 조각 12.9: LCS 문제에 대한 동적 프로그래밍 알고리즘.
Algorithm LCS(X,Y):
Input: Strings X and Y with n and m elements, respectively
Output: for i = 0,...,n - 1, j = 0,...,m - 1 the length L[i, j] of a longest
string that is a subsequence of both the string X[0...i] = x0x1x2...xi and the.
string Y[0...j] = y0y1y2...yj.
for i ← -1 to n - 1 do
L[i, -1] ← 0
for j ← 0 to m - 1 do
L[-1, j] ← 0
for i ← 0 to n - 1 do
for j ← 0 to m - 1 do
if xi = yj then
L[i, j] ← L[i - 1, j - 1] + 1
else
L[i, j] ← max{L[i - 1, f], L[i, j - 1]}
return array
성능
코드 조각 12.9 알고리즘의 실행 시간은
외부 루프가 n번 반복되고 내부 루프가 m번 반복되는
두 개의 중첩 for 루프에 의해 지배되기 때문에 분석하기 쉽다.
루프 내부의 if 문과 할당에는 각각 O(1) 기본 작업이 필요하므로
이 알고리즘은 O(nm) 시간에 실행된다.
따라서 동적 프로그래밍 기술은
가장 긴 공통 부분 수열 문제에 적용되어
LCS 문제에 대한 지수 시간 브루트 포스 솔루션보다 크게 향상될 수 있다.
알고리즘 LCS(코드 조각 12.9)는
가장 긴 공통 부분 수열(L[n − 1,m − 1]에 저장됨)의 길이를 계산하지만
부분 수열 자체는 계산하지 않는다.
다음 명제에서 볼 수 있듯이 간단한 후처리 단계를 통해
알고리즘이 반환한 배열 L에서 가장 긴 공통 부분 수열을 추출할 수 있다.
명제 12.11:
n개의 문자로 구성된 문자열 X와 m개의 문자로 구성된 문자열 Y가 주어지면
O(nm) 시간 내에 X와 Y의 가장 긴 공통 부분 수열을 찾을 수 있다.
이유: 알고리즘 LCS는 가장 긴 공통 부분 수열의 길이인
L[n − 1,m − 1]을 O(nm) 시간으로 계산한다.
L[i, j] 값의 테이블이 주어지면
가장 긴 공통 부분 수열을 구성하는 것은 간단하다.
한 가지 방법은 L[n, m]에서 시작하여 테이블을 통해 다시 작업하여
뒤에서 앞으로 가장 긴 공통 부분 수열을 재구성하는 것이다.
임의의 위치 L[i, j]에서 xi = yj인지 확인할 수 있다.
이것이 사실이라면 e이면 xi를 하위 시퀀스의 다음 문자로 취하여
(xi가 발견된 이전 문자 앞에 있다는 점에 유의)
L[i − 1,j − 1] 옆으로 이동할 수 있다.
xi ≠ yj이면 L[i, j − 1] 및 L[i −1,j] 중 더 큰 것으로 이동할 수 있다. (그림 12.13 참조)
경계 셀(i = − 1 또는 j = −1)에 도달하면 멈춘다.
이 방법은 O(n + m) 추가 시간 내에 가장 긴 공통 부분 수열을 구성한다.
그림 12.13: 배열 L로부터 가장 긴 공통 부분 수열을 구성하는 알고리즘의 그림.
'프로그래밍 공부 > Data Structure' 카테고리의 다른 글
| 13장 그래프(2) (1) | 2024.01.14 |
|---|---|
| 13장 그래프(1) (1) | 2024.01.13 |
| 11장 집합, 정렬, 선택(2) (2) | 2024.01.07 |
| 11장 정렬, 집합, 선택(1) (1) | 2024.01.05 |
| 10장 탐색 트리(2) (1) | 2024.01.05 |