문자열(컴퓨터 과학)

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "스트링" 컴퓨터 과학 – 뉴스 · 신문 · 책 · 학자 · JSTOR (2015년 3월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

현은 종종 문자로 구성된다.그것들은 DNA의 핵산 염기서열과 같은 문장과 알파벳 데이터 목록과 같은 사람이 읽을 수 있는 데이터를 저장하는 데 유용하다.

컴퓨터 프로그래밍에서 문자열은 전통적으로 문자 그대로의 상수 또는 어떤 종류의 변수로 문자열을 의미한다.후자는 원소의 변이를 허용하고 길이를 변경하거나 (생성 후) 고정시킬 수 있다.문자열은 일반적으로 데이터 유형으로 간주되며 일반적으로 일부 문자 부호화를 사용하여 일련의 요소(일반적으로 문자)를 저장하는 바이트(또는 단어)의 배열 데이터 구조로 구현되는 경우가 많다.문자열은 더 일반적인 배열이나 다른 시퀀스(또는 목록) 데이터 유형과 구조를 나타낼 수도 있다.

사용된 프로그래밍 언어와 정확한 데이터 유형에 따라 문자열로 선언된 변수는 미리 결정된 최대 길이 동안 메모리의 저장소를 정적으로 할당하거나, 가변적인 수의 요소를 보유할 수 있도록 동적 할당을 채택할 수 있다.

문자열이 소스 코드에 문자 그대로 나타나면 문자열 리터럴 또는 익명 문자열로 알려져 있다.^[1]

수학적 논리학과 이론적 컴퓨터 과학에 사용되는 형식 언어에서 문자열은 알파벳이라는 집합에서 선택하는 기호의 유한한 배열이다.

문자열 데이터 유형

문자열 데이터 형식은 형식 문자열의 개념을 모델로 한 데이터 형식이다.문자열은 매우 중요하고 유용한 데이터 유형으로 거의 모든 프로그래밍 언어로 구현된다.일부 언어에서는 원시 유형으로, 다른 언어에서는 복합 유형으로 사용할 수 있다.대부분의 고급 프로그래밍 언어의 구문은 일반적으로 어떤 방식으로 인용되는 문자열이 문자열 데이터 유형의 인스턴스를 나타내도록 허용한다. 그러한 메타 문자열을 리터럴 또는 문자열 리터럴이라고 한다.

끈 길이

형식 문자열은 임의의 유한 길이를 가질 수 있지만 실제 언어의 문자열 길이는 종종 인위적인 최대값으로 제한된다.일반적으로 문자열 데이터 유형에는 두 가지가 있는데, 이 최대 길이가 컴파일할 때 결정되는 고정 길이 문자열과 이 최대 길이가 필요한지 아닌지에 상관없이 동일한 양의 메모리를 사용하는 가변 길이 문자열이다.실행 시 실제 요구 사항(메모리 관리 참조).현대 프로그래밍 언어의 대부분의 문자열은 가변 길이 문자열이다.물론 가변 길이 문자열도 사용 가능한 컴퓨터 메모리의 크기에 따라 길이가 제한된다.문자열 길이는 별도의 정수(길이에 또 다른 인위적인 제한을 둘 수 있음)로 저장하거나 종단 문자를 통해 암시적으로 저장할 수 있으며, 일반적으로 C 프로그래밍 언어와 같이 모든 비트가 0인 문자 값이다.아래 "Null-terminated"도 참조하십시오.

문자 부호화

문자열 데이터 형식은 역사적으로 문자당 1바이트를 할당해 왔으며, 정확한 문자 집합은 지역별로 다르지만, 문자 인코딩은 프로그램(주기, 공간, 쉼표 등)이 특별히 취급하는 문자가 모든 인코딩 a에서 동일한 위치에 있었기 때문에 프로그래머가 이를 무시해도 종종 벗어날 수 있을 정도로 유사했다.프로그램이 마주칠 것이다.이러한 문자 집합은 일반적으로 ASCII 또는 EBCDIC를 기반으로 한다.만약 한 인코딩의 텍스트가 다른 인코딩을 사용하여 시스템에 표시된다면, 텍스트는 종종 읽기 쉬우나 일부 컴퓨터 사용자들은 엉망이 된 텍스트를 읽는 법을 배웠다.

중국어, 일본어, 한국어(일명 CJK) 등 로고그래픽 언어의 경우 합리적인 표현을 위해서는 256자(문자당 8비트 바이트 1개의 인코딩 제한)가 훨씬 넘는다.일반적인 해결책에는 ASCII에 대한 단일 바이트 표현을 유지하고 CJK 문자판에 2바이트 표현을 사용하는 것이 포함되었다.이러한 코드를 기존 코드에 사용함으로써 문자열의 일치 및 절단 문제가 발생했으며, 문자열의 심각도는 문자 인코딩 설계 방법에 따라 달라졌다.EUC 패밀리와 같은 일부 인코딩은 ASCII 범위의 바이트 값이 해당 ASCII 문자만 나타내므로 이러한 문자를 필드 구분자로 사용하는 시스템에 인코딩이 안전하다고 보장한다.ISO-2022 및 Shift-J와 같은 기타 인코딩IS는 이러한 보증을 하지 않아 바이트 코드의 일치를 안전하지 않게 만든다.이러한 인코딩도 "자기 동기화"가 아니어서 문자열을 찾는 데 문자열의 시작 부분까지 백업이 필요했고, 두 문자열을 함께 붙여넣어야 두 번째 문자열이 손상될 수 있었다.

유니코드는 그림을 다소 단순화시켰다.대부분의 프로그래밍 언어는 현재 유니코드 문자열을 위한 데이터 형식을 가지고 있다.유니코드가 선호하는 바이트 스트림 형식 UTF-8은 구형 멀티바이트 인코딩에 대해 위에서 설명한 문제가 발생하지 않도록 설계되었다.UTF-8, UTF-16 및 UTF-32는 프로그래머가 고정 크기 코드 단위가 "charactor"와 다르다는 것을 알도록 요구하는데, 현재 주요 난이도는 이러한 차이를 숨기려는 API가 잘못 설계되어 있다(UTF-32는 코드 구성으로 인해 코드 포인트가 "charter"가 아니다).

구현

C++, Perl, Ruby와 같은 일부 언어는 일반적으로 문자열의 내용이 생성된 후에 변경되는 것을 허용한다; 이것들은 변이 가능한 문자열이라고 불린다.Java, JavaScript, Lua, Python, Go와 같은 다른 언어에서는 값을 고정하고 변경을 하려면 새로운 문자열을 생성해야 한다. 이러한 문자열을 불변 문자열이라고 한다.불변의 문자열을 가진 이러한 언어들 중 일부는 또한 Java 및 와 같이 변이 가능한 다른 유형을 제공한다.넷스StringBuilder, 스레드 세이프 자바StringBuffer, 그리고 코코아 NSMutableString불변성에는 장점과 단점이 둘 다 있다: 불변성 문자열은 많은 복사본을 비효율적으로 생성해야 할 수 있지만, 그것들은 더 단순하고 완전히 나사산 안전하다.

문자열은 일반적으로 바이트, 문자 또는 코드 단위의 배열로 구현되며, 길이가 고정된 문자를 포함하여 개별 단위 또는 하위 문자열에 빠르게 액세스할 수 있다.하스켈과 같은 몇 개의 언어는 그들을 링크된 목록으로 대신 구현한다.

Prolog와 Erlang과 같은 일부 언어는 문자열을 문자 코드 목록으로 표시하는 규칙을 채택하는 대신 전용 문자열 데이터 형식을 전혀 구현하지 않는다.

표현

문자열의 표현은 문자 레퍼토리의 선택과 문자 부호화 방법에 크게 좌우된다.구형 문자열 구현은 ASCII에 의해 정의된 레퍼토리 및 인코딩, 또는 ISO 8859 시리즈와 같은 보다 최근의 확장으로 작동하도록 설계되었다.현대의 구현에서는 UTF-8, UTF-16과 같은 다양한 복잡한 인코딩과 함께 유니코드에 의해 정의된 광범위한 레퍼토리를 사용하는 경우가 많다.

바이트 문자열이라는 용어는 일반적으로 (읽을 수 있는) 문자의 문자열, 비트 문자열 등이 아니라, 바이트의 범용 문자열을 나타낸다.바이트 문자열은 바이트가 어떤 값도 가져갈 수 있고 어떤 데이터도 그대로 저장할 수 있다는 것을 의미하며, 이는 어떤 값도 종료 값으로 해석되어서는 안 된다는 것을 의미한다.

대부분의 문자열 구현은 해당 문자의 문자 코드를 저장하는 항목이 있는 가변 길이 배열과 매우 유사하다.주요한 차이점은 특정 인코딩의 경우 하나의 논리적 문자가 배열에서 둘 이상의 항목을 차지할 수 있다는 것이다.예를 들어, UTF-8에서는 단일 코드(UCS 코드 포인트)가 1~4바이트를 차지할 수 있고, 단일 문자는 임의의 수의 코드를 취할 수 있다.이 경우 문자열의 논리 길이(문자 수)는 배열의 물리적 길이(사용 중인 바이트 수)와 다르다.UTF-32는 문제의 첫 부분을 회피한다.

Null-종료됨

문자열의 길이는 특별한 종료 문자를 사용하여 암묵적으로 저장할 수 있다. 종종 이것은 인기 있는 C 프로그래밍 언어에 의해 사용되고 영구적으로 사용되는 모든 비트 0을 가진 NUL이다.^[2]따라서 이 표현을 일반적으로 C 문자열이라고 한다.이러한 n자 문자열의 표현은 n + 1의 공간(종단기의 경우 1)을 차지하며, 따라서 암묵적 데이터 구조다.

종료된 문자열에서 종료 코드는 어떤 문자열에서도 허용 가능한 문자가 아니다.길이 필드가 있는 문자열은 이러한 제한이 없으며 임의의 이진 데이터를 저장할 수도 있다.

8비트 16진수로 ASCII(또는 보다 현대적인 UTF-8) 표현과 함께 10바이트 버퍼에 저장된 null-종단 문자열의 예는 다음과 같다.

위의 예에서 문자열의 길이 "FRANK",는 5자이지만 6바이트를 차지한다.터미네이터 이후의 문자는 표현의 일부를 형성하지 않는다. 다른 데이터의 일부일 수도 있고 가비지의 일부일 수도 있다.(이 형식의 문자열은 이를 선언하는 데 사용된 원래 어셈블리 언어 지침의 이름을 따서 ASCIZ 문자열이라고도 한다.)

바이트 및 비트 종단

문자열을 종료하기 위해 null이 아닌 특수 바이트를 사용하는 것은 역사적으로 하드웨어와 소프트웨어 모두에 나타났지만, 때로는 인쇄 문자이기도 한 값도 함께 표시되기도 했다. $많은 조립자 시스템에 의해 사용되었고,:CDC 시스템에서 사용(이 문자는 0의 값을 가짐) 및 ZX80에서 사용됨"^[3] 이 문자가 기본 언어의 문자열 구분 기호였기 때문에

다소 유사한 IBM 1401과 같은 "데이터 처리" 기계는 왼쪽의 문자열을 구분하기 위해 특수 단어 표시 비트를 사용했으며, 여기서 오른쪽에서 작업이 시작될 것이다.이 부분은 줄의 다른 모든 부분에서 명확해야 했다.이것은 IBM 1401이 7비트 단어를 가지고 있는 동안, 거의 아무도 이것을 기능으로 사용할 생각을 하지 않았고, 7비트 할당을 ASCII 코드로 처리(예를 들어)하는 것을 무시했다는 것을 의미했다.

초기 마이크로컴퓨터 소프트웨어는 ASCII 코드가 고차 비트를 사용하지 않는다는 사실에 의존하여 문자열의 끝을 표시하도록 설정하였다.출력하기 전에 0으로 재설정해야 한다.^[4]

길이순서

문자열의 길이도 명시적으로 저장할 수 있다. 예를 들어, 문자열의 길이를 바이트 값으로 접두사를 붙임으로써 말이다.이 관습은 많은 파스칼 방언에서 사용된다; 그 결과, 어떤 사람들은 그러한 끈을 파스칼 줄 또는 P 줄이라고 부른다.문자열 길이를 바이트로 저장하면 최대 문자열 길이가 255로 제한된다.이러한 제한을 피하기 위해 개선된 P 스트링 구현은 문자열 길이를 저장하기 위해 16비트, 32비트 또는 64비트 단어를 사용한다.길이 필드가 주소 공간을 포함할 때 문자열은 사용 가능한 메모리에 의해서만 제한된다.

길이가 한정된 경우, 그것은 일반적으로 기계 단어인 일정한 공간으로 인코딩될 수 있으므로 n + k 공간을 차지하게 되며, 여기서 k는 단어의 문자 수(64비트 시스템의 8비트 ASCII의 경우 8개, 32비트 시스템의 UTF-32/UCS-4의 경우 1개)이다.길이가 제한되지 않은 경우, 길이 n을 인코딩하면 로그(n) 공간이 필요하므로(고정 길이 코드 참조), 길이 접두사 문자열은 간결한 데이터 구조로 로그(n) + 공백의 길이 n 문자열을 인코딩한다.

후자의 경우, 길이 프리픽스 필드 자체는 길이가 고정되어 있지 않기 때문에 길이 필드를 늘려야 할 정도로 문자열이 커졌을 때 실제 문자열 데이터를 이동시킬 필요가 있다.

다음은 10바이트 버퍼에 저장된 Pascal 문자열과 그 ASCII/UTF-8 표현이다.

레코드 문자열

객체 지향적인 것을 포함한 많은 언어는 문자열을 다음과 같은 내부 구조를 가진 레코드로 구현한다.

계급 끈을 매다 {   size_t 길이;   마를 뜨다 *문자 메시지를 보내다; }; 

단, 일반적으로 구현이 숨겨져 있기 때문에 멤버 기능을 통해 문자열의 접속과 수정이 필요하다. text동적으로 할당된 메모리 영역에 대한 포인터로, 필요에 따라 확장될 수 있음.문자열(C++)을 참조하십시오.

기타 표현

문자 종료 및 길이 코드 제한 문자열:예를 들어 null(NUL) 문자를 포함하는 C 문자 배열은 C 문자열 라이브러리 함수로 직접 처리할 수 없다.길이 코드를 사용하는 문자열은 길이 코드의 최대값으로 제한된다.

이 두 가지 제한은 모두 교묘한 프로그래밍으로 극복할 수 있다.

문자 종료와 관련된 문제가 없고 원칙적으로 길이 코드 한계를 극복할 수 있는 데이터 구조와 기능을 만드는 것이 가능하다.또한 런 길이 인코딩(문자 값과 길이로 반복되는 문자를 대체)과 해밍 인코딩의^{[clarification needed]} 기법을 사용하여 표현된 문자열을 최적화할 수도 있다.

이러한 표현은 흔하지만, 다른 표현은 가능하다.로프를 사용하면 삽입, 삭제 및 연결과 같은 특정 문자열 작업을 보다 효율적으로 수행할 수 있다.

텍스트 편집기의 핵심 데이터 구조는 편집 중인 파일의 현재 상태를 나타내는 문자열(문자의 순서)을 관리하는 구조다.이러한 상태는 길게 연속된 단일 문자 배열로 저장될 수 있지만, 일반적인 텍스트 편집기는 대신 대체 표현을 시퀀스 데이터 구조(갭 버퍼, 연결된 선 목록, 조각 테이블 또는 로프)로 사용하여 삽입, 삭제 및 이전 편집 취소와 같은 특정 문자열 작업을 더 효율적으로 만든다.시엔^[5]

보안 문제

문자열의 메모리 레이아웃과 저장 요구사항이 다르면 문자열 데이터에 액세스하는 프로그램의 보안에 영향을 미칠 수 있다.종료 문자가 필요한 문자열 표현은 일반적으로 종료 문자가 존재하지 않는 경우, 코딩 오류나 공격자가 고의로 데이터를 변경하여 버퍼 오버플로 문제에 노출되기 쉽다.별도의 길이 필드를 채택하는 문자열 표현도 길이를 조작할 수 있는 경우 취약하다.이러한 경우 문자열 데이터에 액세스하는 프로그램 코드는 문자열 메모리 한계 밖에서 의도치 않게 데이터에 액세스하거나 데이터를 변경하지 않도록 경계 검사를 수행해야 한다.

문자열 데이터는 사용자 입력에서 프로그램에 자주 입수된다.이와 같이 문자열의 유효성을 확인하여 예상 형식을 나타내는 것은 프로그램의 책임이다.사용자 입력에 대한 제한적이거나 아무런 유효성 검사도 수행하지 않으면 프로그램이 코드 주입 공격에 취약해질 수 있다.

리터럴 문자열

때때로 문자열은 사람이 읽을 수 있고 기계에 의해 소비되는 텍스트 파일 안에 내장되어야 한다.이것은 예를 들어 프로그래밍 언어의 소스 코드나 구성 파일에서 필요하다.이 경우 NUL 문자는 일반적으로 보이지 않고(인쇄 불가) 키보드를 통해 입력하기 어렵기 때문에 터미네이터로서 잘 작동하지 않는다.문자열 길이를 저장하는 것은 또한 길이의 수동 계산과 추적이 지루하고 오류가 발생하기 쉽기 때문에 불편할 것이다.

두 가지 일반적인 표현은 다음과 같다.

• 따옴표로 둘러싸임(ASCII 0x22 큰따옴표)"str"또는 ASCII 0x27 단일 따옴표'str'(), 대부분의 프로그래밍 언어에서 사용됨.따옴표 자체, 새 줄 문자 또는 인쇄할 수 없는 문자와 같은 특수 문자를 포함할 수 있도록 백슬래시 문자(ASCII 0x5C) 앞에 붙이는 이스케이프 시퀀스를 사용할 수 있는 경우가 많다.
• 예를 들어 Windows INI 파일에서 새 줄 시퀀스에 의해 종료됨.

비텍스트 문자열

문자열이 문자열을 매우 일반적으로 사용하는 반면, 컴퓨터 과학에서 문자열은 일반적으로 균일하게 입력된 데이터의 모든 순서를 가리킬 수 있다.예를 들어 비트 문자열 또는 바이트 문자열을 사용하여 통신 매체에서 검색된 비텍스트 이진 데이터를 나타낼 수 있다.이 데이터는 응용 프로그램의 필요성, 프로그래머의 욕구 및 사용 중인 프로그래밍 언어의 능력에 따라 문자열 특정 데이터 유형으로 표현되거나 표현되지 않을 수 있다.프로그래밍 언어의 문자열 구현이 8비트가 깨끗하지 않으면 데이터 손상이 뒤따를 수 있다.

C 프로그래머는 정의상 항상 null인 "문자의 문자열"과 동일한 배열로 저장될 수 있지만 null이 아닌 "byte 문자열" 또는 "pseudo 문자열" 사이에 뚜렷한 차이를 보인다.그러한 "바이트 문자열"에 C 문자열 취급 기능을 사용하는 것은 종종 효과가 있는 것처럼 보이지만, 나중에 보안 문제로 이어진다.^[6][7][8]

문자열 처리 알고리즘

문자열 처리 알고리즘은 여러 가지가 있는데, 각각 다양한 트레이드오프를 가지고 있다.실행 시간, 스토리지 요구 사항 등과 관련하여 경쟁 알고리즘을 분석할 수 있다.

알고리즘의 일부 범주에는 다음이 포함된다.

• 지정된 하위 문자열 또는 패턴을 찾기 위한 문자열 검색 알고리즘
• 문자열 조작 알고리즘
• 정렬 알고리즘
• 정규식 알고리즘
• 문자열 구문 분석
• 시퀀스 마이닝

고급 문자열 알고리즘은 복잡한 메커니즘과 데이터 구조를 채택하는 경우가 많은데, 그 중 접미사 트리와 유한 상태 기계 등이 있다.

스트링로지라는 이름은 1984년 컴퓨터 과학자 Zvi Galil이 문자열 처리에 사용되는 알고리즘과 데이터 구조를 문제 삼아 만들었다.^{[9][third-party source needed]}

문자열을 중심으로 한 언어 및 유틸리티

문자열은 문자열 처리 응용프로그램을 쓰기 쉽게 하기 위해 몇 개의 언어가 설계되었을 정도로 유용한 데이터 유형이다.예로는 다음과 같은 언어를 들 수 있다.

• 오크
• 아이콘
• 덤프
• 펄
• 렉시
• 루비
• 고요한
• 속물
• Tcl
• TTM

많은 유닉스 유틸리티는 간단한 문자열 조작을 수행하며 강력한 문자열 처리 알고리즘을 쉽게 프로그래밍하는 데 사용될 수 있다.파일과 유한 스트림은 문자열로 볼 수 있다.

멀티미디어 제어 인터페이스, 내장 SQL 또는 printf와 같은 일부 API는 문자열을 사용하여 해석될 명령을 보유한다.

Perl, Python, Ruby, Tcl 등 최근의 스크립팅 프로그래밍 언어는 텍스트 연산을 용이하게 하기 위해 정규 표현식을 사용한다.Perl은 특히 정규 표현식 사용으로 유명하며,^[10] 다른 많은 언어와 애플리케이션은 Perl 호환 정규 표현을 구현한다.

임의의 식을 평가하여 문자열 리터럴에 포함시킬 수 있는 Perl, Ruby 지원 문자열 보간과 같은 일부 언어.

문자열함수

문자열 함수는 문자열을 만들거나 변형 가능한 문자열의 내용을 변경하는 데 사용된다.또한 문자열 정보를 쿼리할 때도 사용된다.기능들의 집합과 그 이름은 컴퓨터 프로그래밍 언어에 따라 다르다.

문자열 함수의 가장 기본적인 예는 문자열 길이 함수인 문자열 길이 함수(종단기 문자나 문자열 내부 구조 정보를 계산하지 않음)를 반환하고 문자열을 수정하지 않는 기능이다.이 함수는 종종 이름 지어진다.length또는len예를 들어,length("hello world")11시에 돌아올거야또 다른 공통적인 기능은 연결인데, 두 개의 문자열을 추가하여 새로운 문자열을 만드는 경우, 흔히 이 연산자가 + 추가 연산자다.

일부 마이크로프로세서의 명령 집합 아키텍처는 블록 카피(예: 인텔 x86m)와 같은 문자열 작동을 직접 지원한다. REPNZ MOVSB).^[11]

형식론

σ은 알파벳이라 불리는 유한한 기호 집합(대체로 문자)이 되게 하라.기호의 성격에 대해서는 어떠한 가정도 하지 않는다.σ 위의 문자열(또는 단어)은 σ에서 기호의 임의의 유한 순서다.^[12]예를 들어 if = {0, 1}인 경우 01011은 σ 위에 있는 문자열이다.

문자열 s의 길이는 s(순서의 길이)의 기호의 수이며 음이 아닌 정수일 수 있으며, s로 표시되기도 한다.빈 문자열은 길이 0의 σ에 걸친 고유 문자열로, ε 또는 λ으로 표기된다.^[12][13]

길이 n의 σ에 걸친 모든 문자열의 집합은 σ로ⁿ 표시된다.예를 들어 if = {0, 1}인 경우 σ² = {00, 01, 10, 11}.모든 알파벳 σ에 대해 σ⁰ = {ε}에 유의하십시오.

임의 길이의 length에 걸쳐 모든 문자열의 집합은 σ의 클레인 폐쇄로 σ로^* 표시된다.σ의ⁿ 면에서는,

${\displaystyle \Sigma ^{*}=\bigcup _{n\in \mathb {N} \cup \{0\}\Sigma ^{n}}}}$

예를 들어 σ = {0, 1}이면 σ^* = { {, 0, 1, 00, 01, 01, 10, 11, 000, 001, 010, 011, ...}.비록 집합 σ^* 자체는 셀 수 없이 무한하지만 σ의^* 각 요소는 유한한 길이의 끈이다.

σ에 대한 문자열 집합(즉, σ의^* 모든 부분집합)은 σ에 대한 형식 언어라고 한다.예를 들어 σ = {0, 1}인 경우, 짝수 0을 가진 문자열 집합, { {, 1, 00, 11, 001, 010, 111, 0000, 0011, 0101, 0101, 0110, 1001, 1010, 1100, 1111, ...}이 σ을 넘는 공식 언어다.

연결 및 기함

결합은 σ에서^* 중요한 2진법이다.σ에서^* 임의의 두 문자열 s와 t의 경우, 이들의 연결은 s의 기호 순서에 이어 t의 문자 순서에 따라 정의되며 st로 표시된다.예를 들어, σ = {a, b, ..., z}인 경우 s =bear, 및 t =hug, 그 다음 st =bearhug및 ts =hugbear.

끈 연결은 연관성이 있지만 명령어는 아니다.빈 문자열 ε은 ID 요소 역할을 한다. 모든 문자열 s에 대해 εs = sε = s.따라서 σ^* 세트와 연결 연산은 σ에 의해 생성되는 자유 단모형인 단모형을 형성한다.In addition, the length function defines a monoid homomorphism from Σ^* to the non-negative integers (that is, a function ${\displaystyle L:\Sigma ^{*}\mapsto \mathbb {N} \cup \{0\}}$, such that ${\displaystyle L(st)=L(s)+L(t)\quad \forall s,t\in \Sigma ^{*}}$).

문자열 s는 t = usv인 문자열 u와 v가 존재하는 경우 하위 문자열 또는 t 인자라고 한다.관계 "은 하위 문자열"은 σ에^* 부분 순서를 정의하며, 그 중 최소 요소는 빈 문자열이다.

접두사 및 접미사

문자열 s는 t = su와 같은 문자열 u가 있으면 t의 접두사라고 한다.u가 비어 있지 않으면 s는 t의 적절한 접두사라고 한다.대칭적으로 t = us와 같은 문자열 u가 존재한다면 문자열 s는 t의 접미사라고 한다.u가 비어 있지 않으면 s는 t의 적절한 접미사라고 한다.접미사와 접두사는 t의 하위 문자열이다."의 접두사"와 "접미사"는 접두사 주문이다.

역전

문자열의 역행은 기호는 같지만 역순으로 된 문자열이다.예를 들어 s = abc(여기서 a, b, c는 알파벳의 기호)인 경우 s의 역행은 cba이다.그 자체의 역행인 끈(예: s = madam)을 팰린드롬이라고 하는데, 빈 문자열과 길이 1의 모든 문자열도 포함한다.

회전

끈 s = uv는 t가 t이면 t의 회전이라고 한다.예를 들어 if = {0, 1) 문자열 0011001은 0100110의 회전이며 여기서 u = 00110, v = 01이다.또 다른 예로, abc 문자열은 viz. abc 그 자체(u=abc, v=a), bca(u=bc, v=a), cab(u=c, v=ab)의 세 가지 다른 회전을 가지고 있다.

사전순서

문자열 집합에 대한 순서를 정의하는 것은 종종 유용하다.알파벳 Ⅱ에 총 순서(cf. 알파벳 순서)가 있으면 Ⅱ에^* 총 순서(사전순서)를 정의할 수 있다.예를 들어 σ = {0, 1}, 0 < 1인 경우^*, le의 사전 순서에는 관계 ε < 0 < 00 < 000 < ...< 0001 < 001 < 01 < 010 < 011 < 0110 < 01111 < 1 < 10 < 100 < 101 < 111 < 1111 < 11111 ...사전순서는 알파벳순이면 총계지만, 알파벳순이라도 비독점 알파벳순에 대해서는 근거가 없다.

근거가 충분한 대체 문자열 순서는 Shortlex를 참조하십시오.

문자열 연산

형식 이론에서는 일반적으로 끈에 대한 많은 추가 연산이 발생한다.이것들은 문자열 연산에 관한 기사에 나와 있다.

위상

길이 3의 이진 문자열 큐브

문자열은 그래프에서 다음과 같은 해석을 노드로 인정하며 여기서 k는 σ에서 기호의 수입니다.

• 길이 n의 고정 길이 문자열은 길이 k-1의 면이 있는 n차원 하이퍼큐브에서 정수 위치로 볼 수 있다.
• 가변 길이 문자열(유한 길이)은 완벽한 k-ary 트리의 노드로 볼 수 있다.
• 무한 문자열(그렇지 않으면 여기서 고려되지 않음)은 k-노드 전체 그래프에서 무한 경로로 볼 수 있다.

고정 길이 문자열 또는 가변 길이 문자열 집합의 자연 위상은 이산 위상이지만 무한 문자열 집합의 자연 위상은 한계 위상으로서 무한 문자열 집합을 유한 문자열 집합의 역 한계로 본다.이것은 칸토어 세트의 p-adic 번호와 일부 구조에 사용되는 구조로, 동일한 위상을 산출한다.

토폴로지의 문자열 표현 사이의 이소모르퍼시즘은 사전적 최소 문자열 회전에 따라 정규화함으로써 찾을 수 있다.

참고 항목

• Binary-safe - 입력을 Raw data stream으로 처리하는 문자열 조작 기능의 속성
• 비트 배열 - 이진수의 문자열
• C 문자열 처리 - C 문자열 처리 개요
• C++ 문자열 처리 - C++ 문자열 처리 개요
• 프로그래밍 언어(문자열 함수) 비교
• 연결 문자열 - 연결을 시작하기 위해 드라이버로 전달(예: 데이터베이스에 전달)
• 빈 문자열 - 프로그래밍 언어의 속성 및 표현
• 압축할 수 없는 문자열 - 어떤 알고리즘으로도 압축할 수 없는 문자열
• 로프(데이터 구조) — 긴 문자열을 효율적으로 조작하기 위한 데이터 구조
• 문자열 메트릭 - 문자열 간의 유사성 개념

참조

위키미디어 커먼즈에는 스트링과 관련된 미디어가 있다.