[자료 구조/알고리즘] 문자열

문자열은 연속된 문자들이 그룹화되어 구성된 자료 구조이다. 따라서 데이터를 그룹화한 추상 자료형인 컬렉션(collection)의 다양한 자료 구조로 문자열을 구조화할 수 있으며 다양한 자료 구조 탐색 알고리즘을 사용하여 부분 문자열들을 탐색 및 비교하는 등의 문제를 해결할 수 있다.

선형 컬렉션

그래프

문자열을 그래프 자료 구조로 구조화하여 부분 문자열을 탐색 및 비교하는 경우 노드는 일반적으로 문자열의 특정 위치(인덱스) 또는 상태를 가리키며, 간선은 노드 간의 전환(문자열을 조작하여 다른 문자열로 만드는 것)이나, 관계(두 문자열 간 관계) 등을 가리킨다.

하나의 문자열을 그래프로 구조화하여 부분 문자열을 탐색 및 비교하는 경우, 그래프 구조화의 예는 다음과 같다.

• 노드: 문자열의 인덱스를 노드로 간주한다. 각 노드는 인덱스까지의 문자열을 나타낸다. 길이가 N인 문자열에 대해 0부터 N까지 총 N+1개의 노드가 존재한다. 노드 0은 빈 문자열, 노드 N은 문자열 전체이다.
• 간선: 문자열의 부분 문자열을 간선으로 간주한다. 예를 들어, 문자열 ABCD에서 노드 0과 노드 1의 간선은 문자열 A이다. 노드 1과 노드 3의 간선은 문자열 BC이다.

두 문자열의 부분 문자열을 탐색 및 비교하여 두 문자열의 관계를 탐색하는 경우, 그래프 구조화의 예는 다음과 같다.

• 노드: 두 문자열 각각의 인덱스 쌍을 노드로 간주한다. 노드 (i, j)는 첫 번째 문자열의 i번째와 두 번째 문자열의 j번째 인덱스를 가리킨다.
• 간선: 두 문자열을 비교하며 다음 상태로 이동하는 연산을 간선으로 간주한다.

문자열을 그래프로 구조화하면 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색 알고리즘과 같은 그래프 탐색 알고리즘을 사용하여 문제를 해결할 수 있다.

문자열 분할

하나의 문자열을 분할하여 특정 단어 집합으로 구성할 수 있는지 확인하는 문제는 그래프 탐색 알고리즘을 사용하여 해결할 수 있다.

너비 우선 탐색을 사용하여 문제를 해결하는 과정은 다음과 같다.

1. 노드: 문자열의 각 인덱스를 노드로 간주한다. 노드 0은 빈 문자, 노드 1은 첫 번째 문자를 가리킨다.
2. 간선: 단어 집합에 분할 문자열이 존재할 경우 간선으로 간주한다. 노드 1의 간선을 만들기 위해 인덱스 1부터 인덱스 N까지 N개의 부분 문자열 중 단어 집합에 존재하는지 확인하여 존재할 경우 해당 인덱스의 노드를 간선으로 연결한다.
3. 자료 구조 준비: 단어 집합에서 단어의 존재 여부를 빠르게 검색하기 위해 셋 자료 구조를 사용한다. 탐색 대상 노드를 저장하기 위해 큐 자료 구조를 사용한다. 이미 방문한 노드를 관리하기 위해 배열 자료 구조를 사용한다.
4. 그래프 탐색: 큐에 노드 0을 추가한 후 꺼낸다. 노드 0의 방문 여부를 설정한다. 인덱스 0부터 N까지의 부분 문자열 중 단어 집합에 존재하는지 확인한다. 존재할 경우 해당 인덱스의 노드를 큐에 넣는다. 큐에서 노드를 꺼낸 후 위 과정을 큐가 빌 때까지 반복한다. 인덱스가 문자열 길이와 동일할 경우 문자열의 끝에 도달한 것이며 문자열 분할이 성공적으로 이루어진 것으로 판단하여 반복문을 종료한다.

깊이 우선 탐색을 사용하여 문제를 해결하는 과정은 다음과 같다.

1. 노드: 문자열의 각 인덱스를 노드로 간주한다. 노드 0은 빈 문자, 노드 1은 첫 번째 문자를 가리킨다.
2. 간선: 단어 집합에 분할 문자열이 존재할 경우 간선으로 간주한다. 노드 1의 간선을 만들기 위해 인덱스 1부터 인덱스 N까지 N개의 부분 문자열 중 단어 집합에 존재하는지 확인하여 존재할 경우 해당 인덱스의 노드를 간선으로 연결한다.
3. 자료 구조 준비: 단어 집합에서 단어의 존재 여부를 빠르게 검색하기 위해 셋 자료 구조를 사용한다. 탐색 대상 노드를 저장하기 위해 스택 자료 구조를 사용한다. 이미 방문한 노드를 관리하기 위해 배열 자료 구조를 사용한다.
4. 그래프 탐색: 스택에 노드 0을 추가한 후 꺼낸다. 노드 0의 방문 여부를 설정한다. 인덱스 0부터 N까지의 부분 문자열 중 단어 집합에 존재하는지 확인한다. 존재할 경우 해당 인덱스의 노드를 스택에 넣는다. 스택에서 노드를 꺼낸 후 위 과정을 스택이 빌 때까지 반복한다. 인덱스가 문자열 길이와 동일할 경우 문자열의 끝에 도달한 것이며 문자열 분할이 성공적으로 이루어진 것으로 판단하여 반복문을 종료한다.

트라이 자료 구조

트라이(trie) 자료 구조란 문자열 검색을 위한 트리 자료 구조의 일종이다. 여러 문자열을 트라이 자료 구조로 구성한 후 특정 문자열을 매우 빠른 속도로 검색할 수 있다. 트라이 자료 구조는 텍스트 자동 완성, 다음 단어 예측, 근사 문자열 매칭(approximate string matching), 맞춤법 검사 등에 활용된다. 트라이 자료 구조를 활용한 문자열 탐색은 이진 탐색 트리(binary search tree) 보다 효율적이다. 트라이 자료 구조는 주로 연관 배열이나 알파벳 크기만큼의 고정 배열을 사용해 문자열을 분산시켜 노드에 문자를 하나씩 저장한다.

트라이 자료 구조에서 루트 노드는 빈 문자열이며, 모든 자식 노드는 부모 노드와 공통 접두사를 공유한다. 문자열 탐색 시 탐색 대상 문자열과의 공통 접두사를 비교해가며 탐색하므로 트라이를 접두사 트리(prefix tree)라고도 한다.

문자열 저장 시 루트 노드에서 자식 노드로 내려가며 문자열을 앞에서 부터 한 문자씩 노드의 키로 저장한다. 노드의 자식 노드는 접미사의 일부가 되며, 노드의 부모 노드는 접두사의 일부가 된다.

문자열 전체를 노드의 키로 저장하는 이진 탐색 트리와 달리 트라이는 노드 또는 간선에 하나의 문자를 저장한다. 루트 노드에서부터 특정 노드까지의 경로는 부분 문자열이 된다. 노드 간 연결은 문자열 전체가 아닌 개별 문자에 의해 결정된다. 키의 종료(문자열의 끝)는 노드의 종단 플래그로 표시한다.

이진 탐색 트리와 트라이의 차이점은 다음과 같다.

• 이진 탐색 트리: 각 노드에 문자열 전체를 키로 저장한다. 문자열 탐색 시 현재 노드의 키와 탐색 대상 키를 비교해 나간다. 노드 삽입 시 삽입 대상 키와 노드의 키를 비교한 후 노드의 위치를 결정한다. 이진 탐색 트리에서 각 노드는 특정 문자열을 나타낸다.
• 트라이: 각 노드에 문자를 키로 저장한다. 문자열 탐색 시 탐색 대상 키의 첫 번째 문자부터 마지막 문자까지 한 문자씩 따라가며 노드의 키와 비교해 나간다. 노드 삽입 시 삽입 대상 문자열을 한 문자씩 노드의 키와 비교한 후 노드의 위치를 결정한다. 트라이에서 각 노드는 그 자체로 특정 문자열을 나타내는 것이 아니며, 루트 노드에서부터 특정 노드까지의 경로가 특정 문자열을 나타낸다.