1. 개요
String여러 문자들이 순서대로 나열된 것.
2. 정의
공집합이 아닌 기호들의 유한집합 [math(\Sigma)]를 알파벳이라 하자. [math(\Sigma)]에 대해 이항 연산 [math(\cdot)]으로 닫혀 있는 클리니 클로저(kleene closure) [math(\Sigma^\ast)]의 원소를 문자열이라 한다.이때 이항 연산 [math(\cdot)]은 접속(concatenation) 또는 붙여쓰기(juxtaposition) 연산이라고 부르며 [math(w\cdot v)]는 [math(w)]의 모든 문자 다음에 [math(v)]의 모든 문자가 오는 문자열을 의미한다. 예를 들어 [math(a)]가 [math(\alpha_1\alpha_2\alpha_3\dots\alpha_n)]인 문자열이고 [math(b)]가 [math(\beta_1\beta_2\beta_3\dots\beta_m)]인 문자열이라면, [math(\alpha\cdot\beta)]는 [math(\alpha_1\alpha_2\alpha_3\dots\alpha_n\beta_1\beta_2\beta_3\dots\beta_m)]이 된다. 접속 연산의 표기는 곱셈과 마찬가지로 생략할 수 있다. 즉, [math(wv)]는 [math(w\cdot v)]를 뜻한다.
문자열의 길이는 해당 문자열에 속한 기호의 갯수이며 [math(|w|)]로 표기한다. 길이가 0인 문자열을 특별히 공문자열(empty string)이라고 하며 주로 [math(\epsilon)]으로 표시한다.[1] 접속 연산은 길이를 보존하기 때문에 [math(\forall w,v\in\Sigma^\ast)]에 대해 [math(|wv|=|w|+|v|)]가 성립한다.
위 정의를 사용해 클리니 클로저를 엄밀하게 정의하면 다음과 같다:[2]
- [math(\epsilon\in\Sigma^\ast)]
- [math(\forall\sigma\in\Sigma(\sigma\in\Sigma^\ast))]
- [math(\forall w,v\in\Sigma^\ast(wv\in\Sigma^\ast))]
- [math(\forall w\in\Sigma^\ast\exists\sigma\in\Sigma\exists v\in\Sigma^\ast(w=\sigma v))]
3. 프로그래밍 언어에서
문자열은 가장 기본적인(primitive) 자료구조 중 하나이며, 대부분의 언어에서 직/간접적으로 지원하고 있다. 직접적으로 지원된다는 말은 언어 문법이나 기능 수준에서의 지원을, 간접적으로 지원된다는 말은 주로 표준 라이브러리나 규약 수준에서의 구현을 통해 지원됨을 의미한다.메모리에서의 효율적인 구현 때문에 위의 형식언어론적 정의에 더해 몇몇 공학적인 특징들이 추가된다. 가장 먼저 알파벳의 크기 차이가 있는데, 일반적인 경우 알파벳 집합은 유니코드 전체이지만, C언어와 같이 유니코드 표준보다 오래된 언어의 경우 알파벳 집합을 아스키 코드로만 가정한다. 때문에 임의 크기의 알파벳을 바이트 유한수열 형태인 선형 메모리로 직렬화하는 함수가 필요해지게 된다. 이를 위해 주로 UTF-8이 사용되지만 [math(\mathcal O(1))] 속도의 임의 접근(random access)이 불가능해지기 때문에 UTF-16을 사용해 구현된 언어들도 다수 존재한다.
또한 무한한 길이를 가질 수 있는 이론적 정의에 비해 현실적으로 문자열의 크기는 유한할 수밖에 없고, 이를 효율적으로 다루기 위해 길이를 문자열 자료구조의 일부로 포함시키기도 한다. 길이를 별도로 포함하지 않는 대표적인 예시는 C의 C스트링, 길이를 기록하는 대표적인 예시는 C++의
std::string 등이 있다. 문자열을 정적으로 스택에 할당하지 않고 동적 할당으로 만들어내는 경우, 효율적인 구현을 위해 초기 할당한 길이를 나타내는 capacity 등 별도의 메타데이터를 기록하기도 한다.3.1. 리터럴
| 프로그래밍 언어 문법 | |
| {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: 0 -10px -5px; word-break: keep-all" | 프로그래밍 언어 문법 C(포인터 · 구조체 · size_t) · C++(클래스 · 이름공간 · 상수 표현식 · 특성) · C# · Java · Python(함수 · 모듈) · Kotlin · MATLAB · SQL · PHP · JavaScript(표준 내장 객체) · Haskell(모나드) |
| 마크업 언어 문법 HTML · CSS | |
| 개념과 용어 함수(인라인 함수 · 고차 함수 · 콜백 함수 · 람다식) · 리터럴 · 문자열 · 상속 · 예외 · 조건문 · 반복문 · 참조에 의한 호출 · eval · 네임스페이스 · 호이스팅 | |
| 기타 #! · == · === · deprecated · NaN · null · undefined · 배커스-나우르 표기법 | }}}}}} |
| 프로그래밍 언어 목록 · 분류 · 문법 · 예제 |
프로그래밍 언어에서 상수로써의 문자열을 삽입하기 위해 사용하는 토큰. 위의 조건을 만족하면서 개발자가 프로그래밍 언어 내에 입력하기 편하게 이스케이프 문자 등 여러 특징을 가지고 있다.
일반적으로 여는 문자로 시작해 닫는 문자로 끝나며, 보통 이 여는 문자와 닫는 문자는 동일하기 때문에 여닫는 문자로 부른다. 여닫는 문자로
"(쌍따옴표)가 주로 쓰이나, '(따옴표)가 쓰이기도 한다. 주로 문자와 문자열을 다르게 취급[3]하는 언어의 경우 문자열 리터럴을 "로, '를 문자 리터럴로 사용하는 편.많은 경우 문자열 리터럴 안에 개행을 넣을 수 없다.[4] 때문에 개행을 넣기 위해선
\n 등의 이스케이프 문자나 별도의 특수한 문자열 토큰을 사용하게 되는데, 이는 언어마다 매우 차차이가 심하다.3.2. 언어별 상세
3.2.1. CString
C언어에서 문자열을 메모리에서 표현하는 방식. 주로 일반적인char[] 배열의 포인터와 비슷하지만 문자열의 끝이 Null로 끝난다는 특징이 있다. 이 특징 때문에 UTF-8과 호환되지 않는다.3.2.2. 기타
- Python에는 몇몇 문자열 상수와 포매팅 함수를 정의하는
string모듈이 있다. - JavaScript - 내부적으로 UTF-16을 사용한다.# 따옴표나 개행을 이스케이프 없이 as-is로 입력할 수 있는
`(tagged string literal)이 ES6 표준부터 도입되었다.
4. 문자열 알고리즘
형식 언어적 정의에 따른 자유 모노이드와 그 수학적 특성에 기반해 동작하는 알고리즘들. 다만 단순히 문자열이 들어간다고 모두 문자열 알고리즘인 것은 아니다. 예를 들어 정렬 알고리즘 등은 문자열의 특성에 의존하지 않기 때문에 문자열 알고리즘이 아니다.5. 관련 문서
[1] ε-NFA와 ε closure의 그 ε이 맞다. ε은 주로 이론 컴퓨터 과학에서 쓰이는 표현이며, 대수학에서는 교재에 따라 [math(\text{-})]로 표기하기도 한다.[2] [math(\displaystyle\Sigma^\ast=\bigcup\Sigma^n)] 형태의 정의도 흔히 쓰인다. 다만 이 경우 알파벳 집합의 접속과 제곱 등등을 따로 정의해야 한다. 이런 방식의 정의는 구성적 정의로, 아래의 공리적 정의에 비해 몇몇 장점이 있다. 특히 4번째 조건의 경우 대수학에서 흔히 'no junk condition'이라고 하는 장치인데, 구성적 정의를 택하게 되면 이런 조건을 명시할 필요가 없어진다![3] 근본적으로 모든 문자 또한 길이 1의 벡터에 대응하지만 메모리 내부에서는 값으로 표현하는지 포인터로 표현하는지의 차이가 발생하기 때문이다.[4] any member of the source character set except the double-quote, backslash, or new-line character. - C11 standard 70p