문자열

string / 文字列

여러 문자들이 순서대로 나열된 것. 또는 이를 표현한 자료구조.

공집합이 아닌 기호들의 유한집합 $\Sigma$를 알파벳이라 하자. $\Sigma$의 원소들을 나열한 유한 수열을 문자열이라 한다.

$\Sigma$로부터 파생(generate)되는 모든 문자열의 집합을 클레이니 클로저(Kleene closure, 클레이니 폐포) $\Sigma^\ast$[유래][이칭]라고 하며, $\Sigma^\ast$라고 표기한다. 해당 집합의 원소를 알파벳 $\Sigma$에 대한 문자열이라고 한다.

이때 $\Sigma^\ast$는 문자열 접속(concatenation) 또는 붙여쓰기(juxtaposition)의 이항연산 $\cdot$에 대해 닫혀 있다. 두 문자열의 접속 $w\cdot v$란 $w$의 모든 문자 다음에 $v$의 모든 문자가 오는 문자열을 의미한다. 예를 들어 $a$가 $\alpha_1\alpha_2\alpha_3\dots\alpha_n$인 문자열이고 $b$가 $\beta_1\beta_2\beta_3\dots\beta_m$인 문자열이라면, $\alpha\cdot\beta$는 $\alpha_1\alpha_2\alpha_3\dots\alpha_n\beta_1\beta_2\beta_3\dots\beta_m$이 된다. 접속 연산의 표기는 곱셈과 마찬가지로 생략할 수 있다. 즉, $wv$는 $w\cdot v$를 뜻한다.

문자열의 길이는 해당 문자열에 속한 기호의 개수이며 $|w|$로 표기한다. 길이가 0인 문자열을 특별히 공문자열(empty string)이라고 하며 주로 $\epsilon$으로 표시한다.[3] 접속 연산은 길이를 보존하기 때문에 $\forall w,v\in\Sigma^\ast$에 대해 $|wv|=|w|+|v|$가 성립한다.

접속 연산이 결합법칙을 만족하므로, $\Sigma^\ast$는 $\epsilon$을 항등원으로 하는 자유 모노이드로 볼 수 있다.

일반적으로 알파벳 집합 $\Sigma$가 전순서 집합이면 문자열에도 적절한 순서를 부여할 수 있다. 우선 두 문자열을 이루는 문자를 앞에서부터 차례대로 비교해 나가며, 한 문자가 같은 위치의 다른 문자보다 작거나 크다면 한 문자열이 다른 문자열보다 작거나 크다고 판단한다. 이 과정에서 한 문자열의 끝에 도달한다면, 길이가 짧은 쪽의 문자열이 길이가 긴 쪽의 문자열보다 작다고 평가한다.

이를 순서 $(\Sigma, \leq_\Sigma)$에 대해 다음과 같이 $(\Sigma^\ast, \leq_{\Sigma^\ast})$로 엄밀하게 나타낼 수 있다.[4]

예를 들어, "app"은 "apple"보다 작다. 앞에서부터 순서대로 비교하면 "a", "p", "p" 순서이며, "app"의 길이는 3, "apple"의 길이는 5로 이 경우 길이가 더 짧은 "app"이 더 작은 문자열이 된다. 반대로 "apply"는 "apple"보다 큰 문자열로, 순서대로 맨 앞의 "a", "p", "p", "l" 까지는 같으나 "y"와 "e"에서 차이가 발생하고, 일반적인 알파벳 순서에서 y가 e보다 뒤에 오기 때문이다. 공문자열 $\epsilon$는 제일 작은 문자열이다.

이를 흔히 사전식 순서(lexicographical order) 또는 혼동이 없다는 가정하에 단순히 알파벳순 순서(alphabetical order)라고 한다.

사전식 순서는 문자열이 가지는 중요한 특징으로, 문자열 정렬 알고리즘이나 트라이 등 여러 자료구조 및 알고리즘을 구현할 때 널리 활용된다.

문자열은 가장 기본적인(primitive) 자료구조 중 하나이며, 대부분의 언어에서 직/간접적으로 지원하고 있다. 직접적으로 지원된다는 말은 언어 문법이나 기본 자료형 수준에서의 지원을, 간접적으로 지원된다는 말은 주로 표준 라이브러리나 규약 수준에서의 구현을 통해 지원됨을 의미한다.

메모리에서의 효율적인 구현 때문에 위의 형식언어론적 정의에 더해 몇몇 공학적인 특징들이 추가된다. 가장 먼저 알파벳의 크기 차이가 있는데, 일반적인 경우 알파벳 집합은 유니코드 전체이지만, C언어와 같이 유니코드 표준보다 오래된 언어의 경우 알파벳 집합을 아스키 코드로만 가정하는 경우가 있다. 때문에 임의 크기의 알파벳을 바이트 유한수열 형태인 선형 메모리로 직렬화하는 함수가 필요해지게 된다. 이를 위해 주로 UTF-8이 사용되지만 $\mathcal O(1)$ 속도의 임의 접근(random access)이 불가능해지기 때문에 UTF-16을 사용해 구현된 언어들도 다수 존재한다.

또한 무한한 길이를 가질 수 있는 이론적 정의에 비해 현실적으로 문자열의 크기는 유한할 수밖에 없고, 이를 효율적으로 다루기 위해 길이를 문자열 자료구조의 일부로 포함시키기도 한다. 길이를 별도로 포함하지 않는 대표적인 예시는 C의 C스트링, 길이를 기록하는 대표적인 예시는 C++의 std::string 등이 있다. 문자열을 정적으로 스택에 할당하지 않고 동적 할당으로 만들어내는 경우, 효율적인 구현을 위해 초기 할당한 길이를 나타내는 capacity 등 별도의 메타데이터를 기록하기도 한다.

많은 언어에서 문자열은 불변(immutable)하게 참조되도록 구현된다. 저수준 언어로 갈수록 .rodata 등에 저장되는 정적 문자열과 실행 도중 할당되는 동적 문자열을 구분하게 되며, 후자의 경우 문자열 내용을 직접적으로 수정할 수 있는 다양한 방법이 주어진다. 반면 고수준 언어로 갈수록 세세한 차이가 추상화로 인해 숨겨지게 되며, 대부분 컴파일러 최적화와 가비지 컬렉터가 실제 문자열 연산의 내부 구현을 담당하게 된다.

프로그래밍 언어에서 상수로써의 문자열을 삽입하기 위해 사용하는 토큰. 위의 조건을 만족하면서 개발자가 프로그래밍 언어 내에 입력하기 편하게 이스케이프 문자 등 여러 특징을 가지고 있다.

일반적으로 여는 문자로 시작해 닫는 문자로 끝나며, 보통 이 여는 문자와 닫는 문자는 동일하기 때문에 여닫는 문자로 부른다. 여닫는 문자로 "(쌍따옴표)가 주로 쓰이나, '(따옴표)가 쓰이기도 한다. 주로 문자와 문자열을 다르게 취급[5]하는 언어의 경우 문자열 리터럴을 "로, '를 문자 리터럴로 사용하는 편.

많은 경우 문자열 리터럴 안에 개행을 넣을 수 없다.[6] 때문에 개행을 넣기 위해선 \n 등의 이스케이프 문자나 별도의 특수한 문자열 토큰을 사용하게 되는데, 이는 언어마다 천차만별이다.

이러한 이스케이프 등의 처리를 간소화 또는 의도하지 않은 이스케이프 해석을 막기 위해, 언어에 따라 raw string literal을 위한 별도의 문법을 지원하기도 한다.

string interpolation

언어마다 부르는 용어가 천차만별이라, string formatting, string substitution, template string이라고도 한다. 문자열의 중간에 내용을 동적으로 삽입하기 위해 문자열 리터럴에 자리 채움자를 작성하고, 이후 실제 표현식, 변수 등의 값을 집어넣어 완성된 문자열을 얻어내는 문법을 말한다.

구현에 따라 크게 자리 채움자를 사용하는 방법, 식별자를 사용하는 방법, 임의의 표현식을 사용하는 방법으로 구분되며, 언어에 따라 이들 중 일부 또는 전부를 구현하는 경우도 있다.

자리 채움자를 사용하는 경우, 고정된 문자열을 작성하고 값이 채워져야 하는 부분에 특정한 문법으로 표시를 한 후, 추가되어야 하는 값을 문자열 외부에 나열한다. 이 경우 임의의 표현식을 사용할 수 있고, 가능한 경우 동적으로 템플릿 문자열을 생성할 수도 있다.[7] 하지만 값을 문자열 바깥에 두어야 하고, 자리 표시자에 의미를 나타내는 변수명이 아닌 단순한 기호만 써야 하기에 가독성이 떨어지는 단점이 있다. 아래는 C 예제이다.

sprintf(buf, "%s 점수: %d점 (오답률 %d%)", "수학", 88, 12);

자리 표시자에 식별자를 집어넣어 해당 식별자에 담긴 값을 바로 삽입하는 방법도 널리 쓰인다. 주로 스크립트 언어에서 구현하기 쉬운데, 컴파일 언어의 경우 컴파일 과정에서 식별자의 이름 정보가 사라지기 때문이다. 다만, 컴파일 언어로 구현이 불가능한 것은 아니기에 구현 방법 무관하게 널리 쓰인다. 자리 채움자를 사용하는 방법보다는 직관적이지만, 반드시 삽입될 변수를 미리 선언해 두어야 해서 간단한 수식, 연산 등을 사용해 서식을 일부 수정하려고 하더라도 새 변수를 선언해야 하는 단점이 있다. 아래는 셸 스크립트 예제이다.

echo "에러 로그는 $HOME/logs/error/$SESSION_ID.txt 에 저장되었습니다."

이외에도 문자열 중간에 어떠한 표현식이든 삽입할 수 있도록 하는 방법이 존재하며, 가장 높은 자유도를 가진다. 이 경우 언어 스펙 상 하나의 문자열 토큰으로 구현할 수 없기에 구현은 더욱 복잡해지는 편이며, 렉서에서 별다른 처리를 하지 않는다면 표현식 채움자 문법 사이에 개행을 얼마든지 넣을 수 있다. 아래는 ES6 JavaScript 예시이다.

`${file} 파일은 ${Math.floor((new Date - editedAt) / 60000)}분 전 마지막으로 갱신되었습니다.`

  자세한 내용은 문자열 인터닝 문서를 참고하십시오.

C언어에서 문자열을 메모리에서 표현하는 방식. 주로 일반적인 char[] 배열의 포인터와 비슷하지만 문자열의 끝이 Null로 끝난다는 특징이 있다. 이 특징 때문에 UTF-8과 호환되지 않으며, 할당되는 길이는 항상 문자 전체의 개수 + 1(null 바이트)이 된다.

  자세한 내용은 C스트링 문서를 참고하십시오.

파스칼에서 문자열을 메모리에 저장하는 방식.

NULL 문자로 문자열의 끝을 탐지하는 CString과 달리 문자열의 길이를 맨 앞에 저장한다. 그에 따라 NULL문자를 포함한 Raw형식의 어레이도 메모리 안전하게 접근할 수 있으며 메모리의 시작 지점부터 NULL을 탐색하는 과정이 필요하지 않고 문자열의 길이를 탐색해 메모리에 이어쓰기 (concatenation)를 하는 경우에도 끝의 메모리 주소를 즉각적으로 탐지 할 수 있으며, (O(n) vs O(1)) 이에 따라 바이트 단위로 복사해야 하는 CString과 달리 프로세서의 레지스터 크기 단위로 빠르게 복사할 수 있으며 길이를 저장하는 특성상 UTF-8등과 같은 가변길이를 저장하는 것이 가능하다.

C++ (std::string), Java (String), Rust (std::string)와 같은 비교적 모던 언어들의 경우 CString이 아닌 PString을 쓰는 경향이 있다.

이 때문에 바이너리에 값을 저장하는 시리얼라이징, 디시리얼라이징 관점에서 CString이 아닌 PString 형식으로 값을 저장하기도 한다.

형식 언어적 정의에 따른 자유 모노이드와 그 수학적 특성에 기반해 동작하는 알고리즘들. 다만 단순히 문자열이 들어간다고 모두 문자열 알고리즘인 것은 아니다. 예를 들어 정렬 알고리즘 등은 문자열의 특성에 의존하지 않기 때문에 문자열 알고리즘이 아니다.

  자세한 내용은 문자열 알고리즘 문서를 참고하십시오.