hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
파싱 표현 문법 정의
파싱 표현식 문법의 각 비단말은 본질적으로 재귀 하향 파서의 파싱 함수를 나타내며, 해당 파싱 표현식은 함수를 구성하는 "코드"를 나타낸다. 각 파싱 함수는 개념적으로 입력 문자열을 인수로 받아 다음 결과 중 하나를 반환한다:
단일 단말(즉, 리터럴)로 구성된 원자 파싱 표현식은 입력 문자열의 첫 번째 문자가 해당 단말과 일치하는 경우 성공하며, 이 경우 입력 문자를 소비한다. 그렇지 않으면 표현식은 실패 결과를 반환한다. 빈 문자열로 구성된 원자 파싱 표현식은 항상 어떤 입력도 소비하지 않고 사소하게 성공한다.
비단말 A로 구성된 원자 파싱 표현식은 비단말 함수 A에 대한 재귀 호출을 나타낸다. 비단말은 실제로 어떤 입력도 소비하지 않고 성공할 수 있으며, 이는 실패와는 다른 결과로 간주된다.
시퀀스 연산자 e1 e2는 먼저 e1을 호출하고, e1이 성공하면 e1이 소비하지 않고 남은 입력 문자열의 나머지 부분에 대해 e2를 호출하고 결과를 반환한다. e1 또는 e2 중 하나라도 실패하면 시퀀스 표현식 e1 e2는 실패한다(입력을 소비하지 않음).
선택 연산자 e1 / e2는 먼저 e1을 호출하고, e1이 성공하면 즉시 결과를 반환한다. 그렇지 않고 e1이 실패하면 선택 연산자는 e1을 호출했던 원래 입력 위치로 퇴각검색하지만, 대신 e2를 호출하여 e2의 결과를 반환한다.
0개 이상, 1개 이상, 선택적 연산자는 각각 하위 표현식 e의 0개 이상, 1개 이상, 0개 또는 1개의 연속된 반복을 소비한다. 그러나 문맥 자유 문법 및 정규 표현식과는 달리, 이 연산자들은 항상 탐욕적으로 작동하여 가능한 한 많은 입력을 소비하며 절대 퇴각검색하지 않는다. (정규 표현식 매처는 탐욕적으로 일치시키려 시도하지만, 일치에 실패하면 퇴각검색하여 더 짧은 일치를 시도할 수 있다.) 예를 들어, 표현식 a*는 입력 문자열에서 연속적으로 사용 가능한 가능한 한 많은 a를 항상 소비하며, 표현식 (a* a)는 첫 번째 부분(a*)이 두 번째 부분이 일치할 a를 전혀 남기지 않기 때문에 항상 실패한다.
and-predicate 표현식 &e는 하위 표현식 e를 호출하고, e가 성공하면 성공하고 e가 실패하면 실패하지만, 어떤 경우에도 입력을 소비하지 않는다.
not-predicate 표현식 !e는 e가 실패하면 성공하고 e가 성공하면 실패하며, 어떤 경우에도 입력을 소비하지 않는다.
다음 재귀 규칙은 선택적 "else" 절이 항상 가장 안쪽의 "if"에 바인딩되도록 표준 C 스타일 if/then/else 문을 일치시킨다. 이는 '/' 연산자의 암시적 우선순위 때문이다. (문맥 자유 문법에서 이 구문은 고전적인 매달린 else 모호성을 발생시킨다.)
다음 재귀 규칙은 파스칼 스타일의 중첩 주석 구문인 (* which can (* nest *) like this *)와 일치한다. .가 임의의 단일 문자와 일치한다는 것을 기억하라.
파싱 표현식 foo &(bar)는 "foo" 텍스트와 일치하고 소비하지만, 그 뒤에 "bar" 텍스트가 오는 경우에만 그렇다. 파싱 표현식 foo !(bar)는 "foo" 텍스트와 일치하지만, 그 뒤에 "bar" 텍스트가 오지 않는 경우에만 그렇다. 표현식 !(a+ b) a는 단일 "a"와 일치하지만, 임의로 긴 a 시퀀스 뒤에 b가 오는 시퀀스의 일부가 아닌 경우에만 그렇다.
파싱 표현식 ('a'/'b')*는 임의 길이의 a와 b 시퀀스와 일치하고 소비한다. 생성 규칙 S ← 'a' S? 'b'는 간단한 문맥 자유 "매칭 언어" 를 설명한다.
다음 파싱 표현식 문법은 고전적인 비문맥 자유 언어 를 설명한다:
파싱 표현 문법 파싱 표현식 문법으로 파서 구현하기
모든 파싱 표현식 문법은 직접적으로 재귀 하향 파서로 변환될 수 있다. 그러나 문법 형식론이 제공하는 무제한 미리보기 기능 때문에 결과 파서는 최악의 경우 지수 시간 성능을 보일 수 있다.
파싱 표현 문법 파싱 표현식 문법으로 파서 구현하기
어떤 파싱 표현식 문법이라도 팩랫 파서로 변환하여 더 나은 성능을 얻을 수 있다. 팩랫 파서는 항상 선형 시간으로 실행되지만, 훨씬 더 많은 저장 공간을 필요로 한다. 팩랫 파서는 구조적으로 재귀 하향 파서와 유사한 파서의 한 형태이다. 단, 파싱 과정에서 메모이제이션을 통해 모든 상호 재귀 파싱 함수의 중간 결과를 메모이제이션하여 각 파싱 함수가 주어진 입력 위치에서 최대 한 번만 호출되도록 한다. 이러한 메모이제이션 덕분에 팩랫 파서는 많은 문맥 자유 문법과 모든 파싱 표현식 문법(문맥 자유 언어를 나타내지 않는 일부 문법 포함)을 선형 시간에 파싱할 수 있다. 메모이제이션된 재귀 하향 파서의 예는 적어도 1993년부터 알려져 있다.
팩랫 파서의 성능 분석은 모든 메모이제이션된 결과를 저장할 충분한 메모리가 있다고 가정한다. 실제로는 메모리가 부족하면 일부 파싱 함수가 동일한 입력 위치에서 두 번 이상 호출될 수 있으며, 결과적으로 파서가 선형 시간보다 더 많은 시간을 소요할 수 있다.
LL 파서 및 LR 파서도 파싱 표현식 문법에서 구축할 수 있으며, 메모이제이션 없는 재귀 하향 파서보다 최악의 경우 성능이 더 좋다. 그러나 문법 형식론의 무제한 미리보기 기능은 이때 손실된다. 따라서 파싱 표현식 문법을 사용하여 표현할 수 있는 모든 언어가 LL 또는 LR 파서로 파싱될 수 있는 것은 아니다.
피카 파서(pika parser)는 동적 계획법을 사용하여 PEG 규칙을 상향식 및 오른쪽에서 왼쪽으로 적용한다. 이는 일반적인 재귀 하향식 및 왼쪽에서 오른쪽 파싱 순서의 역이다. 역순으로 파싱하면 좌측 재귀 문제를 해결하여 좌측 재귀 규칙을 문법에 직접 사용할 수 있도록 하며, 구문 분석기에 최적의 오류 복구 기능을 부여한다. 이는 역사적으로 재귀 하향 파서에게 달성하기 어려웠던 것이다.
파싱 표현 문법 장점
많은 구문 분석 알고리즘은 문법이 먼저 불투명한 실행 가능한 형태로, 종종 어떤 종류의 자동자로 컴파일되는 전처리 단계를 필요로 한다. 파싱 표현식은 직접 실행될 수 있다(이 문서에 표시된 인간이 읽을 수 있는 PEG를 평가하기 전에 S-표현식과 같은 더 기본 형식으로 변환하는 것이 일반적으로 여전히 권장되더라도).
순수한 정규 표현식(즉, 유한 자동자를 사용하여 인식할 수 있는 언어를 설명하는 것)과 비교할 때 PEG는 훨씬 더 강력하다. 특히 PEG는 무제한 재귀를 처리할 수 있으므로 임의의 중첩 깊이까지 괄호를 일치시킨다. 정규 표현식은 기껏해야 고정된 깊이까지의 중첩을 추적할 수 있는데, 이는 유한 자동자(유한한 내부 상태 집합을 가짐)가 유한한 수의 다른 중첩 깊이만을 구별할 수 있기 때문이다. 더 이론적인 용어로, (0개 이상의  다음에 동일한 수의 가 오는 모든 문자열의 언어)는 정규 언어가 아니지만, 다음 문법으로 쉽게 파싱 표현식 언어임을 알 수 있다.
파싱 표현 문법 장점
여기서 AB !.는 시작 표현식이다. !. 부분은 "다음 문자가 없다"고 말함으로써 AB 다음에 입력이 끝남을 강제한다. 이를 위한 마법 제약 조건인 $ 또는 \Z가 있는 정규 표현식과 달리 파싱 표현식은 기본 원시 자료형만을 사용하여 입력의 끝을 표현할 수 있다.
파싱 표현식의 *, +, ?는 정규 표현식의 그것들과 유사하지만, 차이점은 이들이 엄격히 탐욕 모드로 작동한다는 것이다. 이는 궁극적으로 /가 순서 선택이기 때문이다. 결과적으로 정규 표현식으로는 일치하지만 파싱 표현식으로는 일치하지 않는 것이 있을 수 있다:
[ab]?[bc][cd]
는 유효한 정규 표현식이자 유효한 파싱 표현식이다. 정규 표현식으로서는 bc와 일치하지만, 파싱 표현식으로서는 일치하지 않는다. 왜냐하면 [ab]?가 b와 일치하고, 그 다음 [bc]가 c와 일치하여 [cd]에 아무것도 남기지 않아, 그 지점에서 시퀀스 일치가 실패하기 때문이다. [ab]?가 빈 문자열과 일치하도록 "다시 시도"하는 것은 파싱 표현식의 의미론에 명시적으로 위배된다. 이것은 특정 일치 알고리즘의 예외적인 경우가 아니라, 추구하는 동작이다.
파싱 표현 문법 장점
비결정론에 의존하는 정규 표현식조차도 해당 DFA의 모든 상태에 대해 별도의 비단말을 가지고 해당 전이 함수를 비단말의 정의로 인코딩함으로써 파싱 표현식 문법으로 컴파일될 수 있다.
는 사실상 "상태 A에서 다음 문자가 x이면 상태 B로 전이하고, 다음 문자가 y이면 상태 C로 전이한다"고 말하는 것이다. 그러나 이것은 비결정론이 정규 언어의 영역 내에서 제거될 수 있기 때문에 작동한다. 이는 반복 연산의 파싱 표현식 변형을 사용하지 않을 것이다.
PEG는 문자를 사용하여 편안하게 표현할 수 있지만, 문맥 자유 문법(CFG)은 보통 토큰을 사용하여 표현하므로 적절한 파싱 앞에 추가적인 토큰화 단계가 필요하다. 별도의 토큰화기가 없는 장점은 언어의 다른 부분(예: 내장된 미니 언어)이 쉽게 다른 토큰화 규칙을 가질 수 있다는 것이다.
파싱 표현 문법 장점
엄격한 형식적 의미에서 PEG는 CFG와 비교할 수 없을 가능성이 높지만, 실제로는 순수 CFG가 할 수 없는 많은 것들을 PEG가 할 수 있는 반면, 그 반대의 예시를 찾기는 어렵다. 특히 PEG는 C, C++, Java의 "dangling else" 문제와 같은 모호성을 자연스럽게 해결하도록 만들 수 있는 반면, CFG 기반 파싱은 종종 문법 외부의 규칙을 사용하여 이를 해결해야 한다. 또한 어떤 PEG든 위에 설명된 팩랫 파서를 사용하면 선형 시간으로 파싱할 수 있는 반면, 일반 CFG에 따른 파싱은 이진 행렬 곱셈과 점근적으로 동일하다는 것이 입증되었다(따라서 이차 또는 삼차 시간 사이일 가능성이 높다).
명백히 문맥 자유가 아닌 형식 언어의 고전적인 예시 중 하나는  언어이다. 즉, 임의의 수의  다음에 동일한 수의 가 오고, 그 다음에 동일한 수의 가 오는 언어이다. 이것 또한 다음 문법으로 일치되는 파싱 표현식 언어이다.
AB가 일치하려면, 첫 번째 의 연속 부분 뒤에 동일한 수의 가 와야 하며, 추가로 가 로 바뀌는 곳에서 BC가 일치해야 한다. 이는 해당 들 뒤에 동일한 수의 가 온다는 것을 의미한다.
파싱 표현 문법 단점
PEG 파싱은 일반적으로 팩랫 파싱을 통해 수행되며, 이는 중복 파싱 단계를 제거하기 위해 메모이제이션을 사용한다. 팩랫 파싱은 LR 파서와 같이 파스 트리의 깊이에 비례하는 대신 전체 입력 크기에 비례하는 내부 스토리지를 필요로 한다. 이것이 중요한 차이인지 여부는 상황에 따라 달라진다. 파싱이 함수로 제공되는 서비스인 경우, 파서는 반환하기 전까지 전체 파스 트리를 저장했을 것이고, 이미 그 파스 트리는 일반적으로 전체 입력 크기에 비례하는 크기를 가질 것이다. 파싱이 대신 제너레이터로 제공되는 경우 파스 트리의 일부만 메모리에 유지할 수 있지만, 이것의 타당성은 문법에 따라 달라진다. 파싱 표현식 문법은 전체 입력을 소비한 후에야 파서가 시작 부분으로 퇴각검색해야 함을 발견하도록 설계될 수 있으며, 이는 다시 전체 입력 크기에 비례하는 스토리지를 필요로 할 수 있다.
파싱 표현 문법 단점
재귀 문법과 일부 입력의 경우, 파스 트리의 깊이가 입력 크기에 비례할 수 있으므로, LR 파서와 팩랫 파서 모두 동일한 최악의 경우 점근적 성능을 가지는 것으로 보인다. 그러나 많은 도메인, 예를 들어 수기로 작성된 소스 코드에서는 표현식 중첩 깊이가 프로그램 길이에 관계없이 효과적으로 일정한 한계를 가지는데, 특정 깊이 이상으로 중첩된 표현식은 리팩터링되는 경향이 있기 때문이다. 전체 파스 트리를 유지할 필요가 없을 때, 더 정확한 분석은 입력 크기와 별도로 파스 트리의 깊이를 고려할 것이다.
파싱 표현 문법 단점
선형적 전체 복잡성을 달성하기 위해서는 메모이제이션에 사용되는 저장 공간이 개별 메모이제이션된 데이터 항목에 대한 분할 상환 상수 시간 접근을 제공해야 한다. 실제로는 문제가 되지 않는다. 예를 들어 동적으로 크기가 조정되는 해시 테이블이 이를 달성한다. 하지만 이는 포인터 산술을 사용하므로, 랜덤 접근 기계를 전제한다. 데이터 구조와 알고리즘에 대한 이론적 논의는 더 제한적인 모델(아마도 람다 대수 또는 스킴의 모델)을 전제하는 경향이 있는데, 여기서 희소 테이블은 트리로 구축되어야 하며 데이터 항목 접근은 상수 시간이 아니다. LL 파서와 같은 전통적인 파싱 알고리즘은 이에 영향을 받지 않지만, 팩랫 파서의 평판에 불이익이 된다: 팩랫 파서는 겉보기에 평판이 좋지 않은 연산에 의존한다.
반대로 보면, 이는 팩랫 파서가 실제 시스템에서 쉽게 사용할 수 있는 계산 능력을 활용하며, 오래된 파싱 알고리즘은 이를 활용하는 방법을 알지 못했다는 것을 의미한다.
파싱 표현 문법 단점
PEG는 좌측 재귀 규칙, 즉 비단말이 동일한 비단말이 가장 왼쪽에 있는 기호로 나타나는 표현식으로 확장될 수 있는 규칙을 포함하지 않으면 잘 형성되었다고 한다. 좌측에서 우측으로의 하향식 파서의 경우, 이러한 규칙은 무한 회귀를 야기한다. 즉, 파싱은 문자열에서 앞으로 나아가지 않고 동일한 비단말을 계속 확장할 것이다. 따라서 팩랫 파싱을 허용하려면 좌측 재귀를 제거해야 한다.
좌측 또는 우측이든 직접 재귀는 문맥 자유 문법에서 중요하다. 왜냐하면 재귀가 반복을 설명하는 유일한 방법이기 때문이다.
문맥 자유 문법 사용에 익숙한 사람들은 종종 동일한 관용구를 사용하기 위해 PEG를 기대하지만, 파싱 표현식은 재귀 없이 반복을 수행할 수 있다.
차이점은 생성되는 추상 구문 트리에 있다. 재귀를 사용하면 각 Sum 또는 Args가 최대 두 개의 자식을 가질 수 있지만, 반복을 사용하면 임의의 많은 자식을 가질 수 있다. 예를 들어 마이크로프로세서의 덧셈 명령어는 일반적으로 두 개의 피연산자만 허용하므로, 후속 처리 단계에서 이러한 자식 목록을 유한 차수를 가진 트리로 재구성해야 하는 경우, 좌측 결합성과 같은 속성은 PEG 지향 파싱 단계 이후에 부여될 것이다.
파싱 표현 문법 단점
따라서 좌측 재귀는 문맥 자유 관용구를 고집하지 않는 한 LL(k) 문맥 자유 파서보다 PEG 팩랫 파서에 문제를 일으킬 가능성이 실제로는 적다. 그러나 모든 재귀의 경우가 반복에 관한 것은 아니다.
예를 들어, 위 산술 문법에서 연산자 우선순위를 순서 선택으로 표현하려는 유혹이 있을 수 있다. — Sum / Product / Value는 먼저 Sum으로 보려고 시도하고(하향식으로 파싱하므로), 두 번째로 Product로 보려고 시도하고, 세 번째로 Value로 보려고 시도한다는 의미이다. — 이는 정의의 중첩을 통하는 것보다 더 간단하다. 이 (잘못 형성된) 문법은 우선순위 순서를 한 줄에만 유지하려고 한다.
불행히도 Expr을 일치시키려면 Sum이 일치하는지 테스트해야 하고, Sum을 일치시키려면 Expr이 일치하는지 테스트해야 한다. 이 항이 가장 왼쪽에 나타나기 때문에 이러한 규칙들은 해결할 수 없는 순환 정의를 이룬다. (원래 첫 번째 예시의 공식화처럼 해결될 수 있는 순환 정의도 존재하지만, 그러한 정의는 병리적 재귀를 보이지 않아야 한다.) 그러나 좌측 재귀 규칙은 항상 좌측 재귀를 제거하도록 다시 작성될 수 있다. 예를 들어, 다음 좌측 재귀 CFG 규칙:
는 플러스 연산자를 사용하여 PEG로 다시 작성될 수 있다.
간접 좌측 재귀 규칙을 다시 작성하는 과정은 일부 팩랫 파서에서 복잡하며, 특히 의미론적 동작이 관련될 때 더욱 그렇다.
일부 수정으로 전통적인 팩랫 파싱은 직접 좌측 재귀를 지원할 수 있지만, 그렇게 하면 선형 시간 파싱 속성이 손실된다. 이는 원래 PEG 및 팩랫 파싱을 사용하는 정당성이다. 오직 OMeta 파싱 알고리즘만이 추가 복잡성 없이 완전한 직접 및 간접 좌측 재귀를 지원하며(다시 말하지만, 선형 시간 복잡성은 손실된다), 모든 GLR 파서들은 좌측 재귀를 지원한다.
파싱 표현 문법 예상치 못한 동작
PEG에 대한 흔한 첫인상은 정규 표현식과 같은 반복 연산자 *+?와 미리보기 조건자 &!와 같은 특정 편의 기능과 모호성 해결을 위한 순서 선택을 가진 CFG처럼 보인다는 것이다. 이러한 이해는 언어 파서를 만들려는 목표를 가질 때 충분할 수 있지만, 파싱 표현식의 계산 능력에 대한 더 이론적인 논의에는 충분하지 않다. 특히 문맥 자유 문법의 비순서 선택 |에 내재된 비결정론은 결정론적 순서 선택 /와 매우 다르다.
PEG 팩랫 파서는 다음과 같은 모호하지 않은 비결정적 CFG 규칙을 인식할 수 없다.
LL(k) 및 LR(k) 파싱 알고리즘 모두 이 예시를 인식할 수 없다. 그러나 이 문법은 CYK 알고리즘과 같은 일반 CFG 파서에서 사용될 수 있다. 그럼에도 불구하고, 이 문제의 언어는 실제로 정규 언어(홀수 개의 x 문자열)이므로 이러한 모든 종류의 파서에서 인식될 수 있다.
PEG 파서가 xxxxxq 문자열에 대해
파싱 표현 문법 예상치 못한 동작
를 일치시키려고 시도할 때 정확히 어떤 일이 발생하는지 살펴보는 것은 유익하다. 예상대로, q에 대한 일치에 실패할 때까지 문자열의 증가하는 위치에서 비단말 S를 재귀적으로 일치시키려고 시도하며, 그 후 퇴각검색을 시작한다. 과정은 다음과 같다:
파싱 표현식에 대한 일치는 탐욕적이다. 즉, 발견된 첫 번째 성공만이 고려된다. 비록 지역적으로 선택이 가장 긴 것을 먼저 하도록 순서가 지정되어 있더라도, 이 탐욕적인 일치가 전역적으로 가장 긴 일치를 찾을 것이라는 보장은 없다.
LL(k) 및 LR(k) 파서 생성기는 입력 문법이 모호하면 완료되지 않는다. 이는 문법이 모호하지 않아야 하지만 결함이 있는 일반적인 경우에 유용한 기능이다. PEG 파서 생성기는 의도하지 않은 모호성을 가장 먼저 일치하는 것으로 해결하며, 이는 임의적일 수 있고 예상치 못한 구문 분석으로 이어질 수 있다.
PEG 문법에서 생성의 순서는 모호성 해결뿐만 아니라 일치하는 언어에도 영향을 미친다. 예를 들어, 포드(Ford)의 논문에 있는 첫 번째 PEG 예시(pegjs.org/online 표기법으로 다시 작성하고  및 로 레이블링함)를 고려하라:
파싱 표현 문법 예상치 못한 동작
포드는 후자의 PEG 규칙에서 두 번째 대안은 입력 문자열이 'a'로 시작하면 첫 번째 선택이 항상 이루어지기 때문에 결코 성공하지 못한다고 언급한다.
구체적으로,  (즉, 과 일치하는 언어)는 입력 "ab"를 포함하지만, 는 포함하지 않는다.
따라서 PEG 문법에 새로운 옵션을 추가하면 일치하는 언어에서 문자열을 제거할 수 있다. 예를 들어, 는 에 의해 일치되지 않는 문자열을 포함하는 단일 생성 문법 A = "a" "b"에 규칙을 추가한 것이다.
더욱이 PEG 문법 과 로부터 와 일치하는 문법을 구성하는 것은 항상 사소한 작업이 아니다.
이는 새로운 생성이 문자열을 제거할 수 없는 CFG와는 극명한 대조를 이룬다(모호성 형태로 문제를 도입할 수는 있지만),
그리고 에 대한 (잠재적으로 모호한) 문법은 다음과 같이 구성될 수 있다.
파싱 표현 문법 파싱 표현식 문법 이론
파싱 표현식 문법으로 인식할 수 없는 문맥 자유 언어의 구체적인 예시를 제시하는 것은 미해결 문제이다. 특히, 파싱 표현식 문법이 회문 언어를 인식할 수 있는지 여부는 미해결이다.
파싱 표현식 언어 클래스는 집합 교차 및 여집합에 대해 닫혀 있으며, 따라서 집합 합집합에 대해서도 닫혀 있다.:Sec.3.4
문맥 자유 문법의 경우와는 극명한 대조를 이루게도, 파싱 표현식 문법으로부터 파싱 표현식 언어의 요소를 생성하는 것은 불가능하다. 실제로, 파싱 표현식 문법에 의해 인식되는 언어가 비어있는지 여부를 알고리즘적으로 결정하는 것은 불가능하다! 이에 대한 한 가지 이유는 포스트 대응 문제의 모든 인스턴스가 파싱 표현식 언어가 비어있는지 결정하는 문제의 인스턴스로 환원되기 때문이다.
파싱 표현 문법 파싱 표현식 문법 이론
포스트 대응 문제의 인스턴스는 문자열(단말 기호) 쌍의 목록 으로 구성된다는 것을 상기하라. 문제는  범위의 인덱스 시퀀스 가 존재하여 을 만족하는지 결정하는 것이다. 이것을 파싱 표현식 문법으로 환원하려면, 을 임의의 서로 다른 동일한 길이의 단말 기호 문자열로 두고(이미 2개의 다른 기호가 단말 기호 알파벳에 있으면,  길이가 충분하다) 다음 파싱 표현식 문법을 고려하라.

비단말 에 의해 일치되는 모든 문자열은 일부 인덱스 에 대해  형식을 가진다. 마찬가지로 비단말 에 의해 일치되는 모든 문자열은  형식을 가진다. 따라서 에 의해 일치되는 모든 문자열은 인  형식을 가질 것이다.
온 더 플라이
온 더 플라이(On the fly)는 변경 사항이 영향을 미치는 프로세스가 진행 중인 동안 변경되는 것을 설명하는 데 사용되는 구문이다. 이는 자동차, 컴퓨터 및 요리 산업에서 사용된다. 자동차에서 온 더 플라이는 자동차가 여전히 주행 중일 때 자동차의 구성을 변경하는 것을 설명하는 데 사용될 수 있다. 자동차가 여전히 주행 중일 때 발생할 수 있는 프로세스에는 일부 자동차에서 2륜 구동과 4륜 구동 간 전환, 일부 컨버터블 자동차에서 지붕 열고 닫기가 포함된다. 컴퓨팅에서 온 더 플라이 CD 라이터는 한 CD에서 데이터를 읽어 컴퓨터 메모리에 저장하지 않고 다른 CD에 쓸 수 있다. 멀티태스킹 운영 체제에서 프로그램을 온 더 플라이로 전환한다는 것은 네이티브 및 에뮬레이트된 프로그램이나 애플리케이션을 일시 중지, 정지 또는 지연시키거나 기타 원치 않는 이벤트 없이 작업을 수행하면서 여전히 실행 중이고 병렬로 실행되는 프로그램이나 애플리케이션 간에 전환할 수 있는 기능을 의미한다. 컴퓨터 부품을 온 더 플라이로 전환한다는 것은 컴퓨터가 여전히 실행 중인 동안 컴퓨터 부품을 교체하는 것을 의미한다. 또한 프로그래밍에서 프로그램이 여전히 실행 중인 동안 프로그램을 변경하는 것을 설명하는 데 사용될 수도 있다. 레스토랑 및 기타 음식 준비와 관련된 장소에서 이 용어는 주문을 즉시 처리해야 함을 나타내는 데 사용된다.
온 더 플라이 구어적 용법
구어적으로 "온 더 플라이"는 필요할 때 만들어지는 것을 의미한다. 이 구문은 다음을 의미하는 데 사용된다.
온 더 플라이 자동차 용법
자동차 산업에서 이 용어는 차량이 엔진에 의해 구동되고 움직이는 동안 특정 작업을 수행하는 상황을 나타낸다. 4륜구동 차량과 관련하여 이 용어는 차량이 기어를 넣고 움직이는 동안 2륜 구동에서 4륜 구동으로 전환할 수 있는 기능을 설명한다. 일부 컨버터블 모델에서는 지붕을 온 더 플라이로 전기로 접을 수 있지만, 다른 경우에는 자동차를 멈춰야 한다.
수확기에서는 최신 모니터링 시스템을 통해 운전자는 곡물의 품질을 추적하면서 수확이 진행됨에 따라 회전자 속도를 온 더 플라이로 조정할 수 있다.
온 더 플라이 컴퓨터 용법
멀티태스킹 컴퓨팅에서 운영 체제는 여러 프로그램을 처리할 수 있다. 네이티브 애플리케이션이든 에뮬레이트된 소프트웨어든 모두 같은 장치에서 동시에 독립적으로, 병렬로 실행되며, 분리되거나 공유된 리소스 및 데이터를 사용하여 작업을 개별적으로 또는 함께 수행한다. 사용자는 시간 낭비나 성능 저하 없이 이러한 프로그램이나 그룹 간에 온 더 플라이로 전환하여 얻은 효과를 사용하거나 목적을 감독할 수 있다. GUI를 사용하는 운영 체제에서는 특정 소프트웨어의 활성 창(또는 유사한 역할을 하는 객체)에서 다른 소프트웨어의 다른 창으로 전환하여 이 작업을 수행하는 경우가 매우 많다.
컴퓨터는 온 더 플라이로 결과를 계산하거나 이전에 저장된 결과를 검색할 수 있다.
이는 이동식 미디어(CD-ROM, DVD 등)를 중간 매체(하드 디스크)에 먼저 저장하지 않고 직접 복사하는 것을 의미할 수 있다. 예를 들어, CD-ROM 드라이브에서 CD-라이터 드라이브로 CD-ROM을 복사하는 것이다. 복사 프로세스는 각 데이터 블록을 검색하고 즉시 대상으로 기록하여 작업 메모리에 다음 데이터 블록을 검색할 공간을 확보해야 한다.
온 더 플라이 컴퓨터 용법
암호화된 데이터 저장에 사용될 때, 데이터 스트림은 기록될 때 자동으로 암호화되고 다시 읽을 때 다시 해독되어 소프트웨어에 투명하게 적용된다. 약어 OTFE가 일반적으로 사용된다.
온 더 플라이 프로그래밍은 프로그램을 중지하지 않고 수정하는 기술이다.
유사한 개념인 핫 스와핑은 컴퓨터 하드웨어의 온 더 플라이 교체를 의미한다.
온 더 플라이 온 더 플라이 컴퓨팅
온 더 플라이 컴퓨팅(OTF 컴퓨팅)은 사용자의 필요에 맞게 소프트웨어를 자동화하고 맞춤화하는 것이다. 요구 사항 사양에 따라 이 소프트웨어는 기본 구성 요소, 즉 기본 서비스로 구성되며, 이러한 기본 구성 요소의 사용자 지정 설정이 이루어진다. 따라서 요청된 서비스는 사용자의 요청에 따라서만 컴파일된 다음, 특별히 설계된 데이터 센터에서 실행되어 사용자가 (온 더 플라이로) 생성된 서비스의 기능에 액세스할 수 있도록 한다.
온 더 플라이 레스토랑 용법
레스토랑, 카페, 연회장 등 음식 준비와 관련된 장소에서 이 용어는 주문을 즉시 처리해야 함을 나타내는 데 사용된다. 이는 이전에 제공된 요리가 먹을 수 없거나, 웨이터가 실수를 했거나 지연되었거나, 손님이 즉시 떠나야 하는 경우에 자주 발생한다.
온 더 플라이 스포츠 용법
아이스하키에서 퍽이 경기 중에 있을 때 팀이 라인 변경(선수 교체)을 하는 것은 합법적이고 흔한 일이다. 이러한 라인 변경은 "온 더 플라이"로 이루어진다고 한다.
2-3 트리
컴퓨터 과학에서 2–3 트리는 모든 자식 노드(내부 노드)가 두 개의 자식(2-노드)과 하나의 데이터 요소 또는 세 개의 자식(3-노드)과 두 개의 데이터 요소를 가지는 트리 자료 구조이다. 2–3 트리는 3차 B 트리이다. 트리의 바깥쪽에 있는 노드(리프 노드)는 자식이 없고 하나 또는 두 개의 데이터 요소를 가진다. 2–3 트리는 1970년 존 홉크로프트가 발명했다.
2–3 트리는 균형이 맞춰져 있어야 하는데, 이는 각 리프가 같은 레벨에 있다는 것을 의미한다. 따라서 노드의 각 오른쪽, 중앙, 왼쪽 서브트리는 같거나 거의 같은 양의 데이터를 포함한다.
2-3 트리 정의
내부 노드에 데이터 요소가 하나 있고 두 개의 자식이 있으면 이를 2-노드라고 한다.
내부 노드에 데이터 요소가 두 개 있고 세 개의 자식이 있으면 이를 3-노드라고 한다.
데이터 요소가 세 개인 4-노드는 트리를 조작하는 동안 일시적으로 생성될 수 있지만, 트리 내에 영구적으로 저장되지는 않는다.
T가 2–3 트리인 경우는 다음 문장 중 하나만 참일 때이다:
2-3 트리 연산
2–3 트리에서 항목을 탐색하는 것은 이진 탐색 트리에서 항목을 탐색하는 것과 유사하다. 각 노드의 데이터 요소가 정렬되어 있으므로, 탐색 함수는 올바른 서브트리와 결국 항목을 포함하는 올바른 노드로 향하게 된다.
t가 왼쪽 자식 p, 중간 자식 q, 오른쪽 자식 r을 가진 3-노드라고 가정한다. a와 b를 t의 두 데이터 요소로 두며, 이다. 네 가지 경우가 있다:
만약 d가 a 또는 b와 같으면, d는 T에 있으므로 탐색이 완료된다.
만약 이면, T를 p로 설정하고 2단계로 돌아간다.
만약 이면, T를 q로 설정하고 2단계로 돌아간다.
만약 이면, T를 r로 설정하고 2단계로 돌아간다.
삽입은 트리의 균형 속성을 유지한다.
2-노드에 삽입할 때, 새 키는 적절한 순서로 2-노드에 추가된다.
3-노드에 삽입할 때는 3-노드의 위치에 따라 더 많은 작업이 필요할 수 있다. 트리가 3-노드로만 구성되어 있다면, 노드는 적절한 키와 자식을 가진 세 개의 2-노드로 분할된다.
2-3 트리 연산
대상 노드가 부모가 2-노드인 3-노드인 경우, 키는 3-노드에 삽입되어 임시 4-노드를 생성한다. 그림에서 키 10은 6과 9를 가진 2-노드에 삽입된다. 중간 키는 9이며, 부모 2-노드로 승격된다. 이렇게 되면 6과 10의 3-노드가 남게 되며, 이는 부모 3-노드의 자식으로 유지되는 두 개의 2-노드로 분할된다.
대상 노드가 3-노드이고 부모도 3-노드인 경우, 임시 4-노드가 생성된 다음 위와 같이 분할된다. 이 과정은 루트까지 트리 위로 계속된다. 루트를 분할해야 하는 경우, 단일 3-노드의 과정이 따른다: 임시 4-노드 루트는 세 개의 2-노드로 분할되며, 그중 하나가 루트로 간주된다. 이 연산은 트리의 높이를 하나 증가시킨다.
2-3 트리 연산
비-리프 노드에서 키를 삭제하는 것은 즉각적인 선행자 또는 후속자로 대체한 다음 리프 노드에서 선행자 또는 후속자를 삭제함으로써 수행할 수 있다. 리프 노드에서 키를 삭제하는 것은 리프가 3-노드인 경우 쉽다. 그렇지 않은 경우, 임시 1-노드를 생성해야 할 수 있으며, 이는 트리를 재구성하여 흡수되거나, 삽입의 경우 임시 4-노드처럼 흡수되기 전에 반복적으로 위로 이동해야 할 수 있다. 또는 하향식과 상향식을 모두 사용하는 알고리즘을 사용할 수 있는데, 이는 내려가는 길에 임시 4-노드를 생성하고 다시 올라오면서 파괴하는 방식이다. 삭제 방법은 참조에서 더 자세히 설명한다.
2–3 트리는 레드-블랙 트리와 구조가 유사하므로, 레드-블랙 트리를 위한 병렬 알고리즘도 2–3 트리에 적용할 수 있다.
2-3-4 트리
컴퓨터 과학에서 2–3–4 트리 (또는 2–4 트리)는 사전을 구현하는 데 사용할 수 있는 자가 균형 자료 구조이다. 이 숫자는 자식 노드가 있는 모든 노드 (내부 노드)가 두 개, 세 개 또는 네 개의 자식 노드를 갖는 트리를 의미한다.
2–3–4 트리는 차수 4의 B 트리이다. 일반적인 B 트리와 마찬가지로, O(log n) 시간 내에 검색, 삽입 및 삭제를 수행할 수 있다. 2–3–4 트리의 한 가지 특징은 모든 외부 노드가 동일한 깊이에 있다는 것이다.
2–3–4 트리는 레드 링크(즉, 빨간색 자식에 대한 링크)를 3-노드 및 4-노드의 내부 링크로 해석함으로써 레드-블랙 트리와 밀접하게 관련되어 있지만, 이 대응 관계는 일대일이 아니다. 왼쪽 기울어진 레드-블랙 트리는 단일 빨간색 오른쪽 자식을 가진 노드를 금지함으로써 레드-블랙 트리를 제한하며, 이는 왼쪽 기울어진 레드-블랙 트리와 2–3–4 트리 사이에 일대일 대응을 이룬다.
2-3-4 트리 삽입
값을 삽입하려면 2–3–4 트리의 루트에서 시작한다.
현재 노드가 4-노드인 경우:
중간 값을 제거하고 저장하여 3-노드를 만든다.
남은 3-노드를 두 개의 2-노드로 분할한다(이제 사라진 중간 값은 다음 단계에서 처리된다).
이 노드가 루트 노드인 경우(따라서 부모가 없는 경우):
중간 값이 새 루트 2-노드가 되고 트리의 높이가 1 증가한다. 루트로 올라간다.
그렇지 않으면 중간 값을 부모 노드로 올린다. 부모 노드로 올라간다.
2–3–4 트리에 "25" 값을 삽입하려면:
2-3-4 트리 삭제
요소를 삭제하는 가장 간단한 방법은 요소를 그대로 두고 "삭제됨"으로 표시하여 이전 알고리즘이 삭제된 요소를 무시하도록 조정하는 것이다. 삭제된 요소는 나중에 삽입을 수행할 때 덮어쓰기하여 재사용할 수 있다. 그러나 이 방법의 단점은 트리의 크기가 줄어들지 않는다는 것이다. 트리의 요소 중 상당 부분이 삭제되면 트리는 현재 저장된 요소의 크기보다 훨씬 커지고 다른 작업의 성능이 삭제된 요소의 영향을 받아 불리해진다.
이것이 바람직하지 않은 경우, 2–3–4 트리에서 값을 제거하기 위해 다음 알고리즘을 따를 수 있다.
삭제할 요소를 찾는다.
요소가 리프 노드에 없으면 해당 위치를 기억하고, 요소의 후속 항목을 포함할 리프에 도달할 때까지 계속 검색한다. 후속 항목은 제거할 항목보다 작은 가장 큰 키 또는 제거할 항목보다 큰 가장 작은 키일 수 있다. 리프 노드가 2-노드가 아니도록 위에서 아래로 트리를 조정하는 것이 가장 간단하다. 그렇게 하면 스왑 후 빈 리프 노드가 생기지 않는다.
요소가 2-노드 리프에 있으면 아래 조정을 수행한다.
제거하려는 리프로 가는 도중에 2-노드(루트 노드 제외)가 발견되면 다음 조정을 수행한다.
2-3-4 트리 삭제
이 노드 양쪽의 형제 노드가 3-노드 또는 4-노드인 경우(따라서 1개 이상의 키를 가짐) 해당 형제 노드와 회전을 수행한다.
이 노드에 가장 가까운 다른 형제 노드의 키가 두 노드를 바라보는 부모 키로 올라간다.
부모 키는 이 노드로 내려와 3-노드를 형성한다.
원래 회전된 형제 키와 함께 있던 자식은 이제 이 노드의 추가 자식이 된다.
부모가 2-노드이고 형제 노드도 2-노드인 경우, 세 요소를 모두 결합하여 새 4-노드를 형성하고 트리를 줄인다. (이 규칙은 부모 2-노드가 루트인 경우에만 트리거될 수 있다. 경로상의 다른 모든 2-노드는 2-노드가 아니도록 수정되었을 것이기 때문이다. 이것이 여기서 "트리를 줄인다"는 것이 균형을 유지하는 이유이다. 이것은 또한 합병 작업의 중요한 가정이다.)
찾는 값에 도달하면 리프 노드에 1개 이상의 키가 있음을 확인했으므로 이제 제거된 항목의 위치에 문제없이 배치할 수 있다.
2–3–4 트리에서 삭제는 전송 및 합병이 상수 시간(O(1))으로 실행된다고 가정할 때 O(log n)이다.
2-3-4 트리 병렬 연산
2–3–4 트리는 레드-블랙 트리와 구조가 유사하므로, 레드-블랙 트리에 대한 병렬 알고리즘도 2–3–4 트리에 적용될 수 있다.
스케이프고트 트리
컴퓨터 과학에서 스케이프고트 트리(Scapegoat tree)는 1989년 아르네 안데르손이, 그리고 1993년 이갈 갈페린과 로널드 L. 리베스트가 다시 발명한 자가 균형 이진 탐색 트리이다. 이 트리는 최악의 경우  탐색 시간(n은 엔트리 개수)과 의 분할 상환 삽입 및 삭제 시간을 제공한다.
최악의 경우  탐색 시간을 제공하는 다른 대부분의 자가 균형 이진 탐색 트리와 달리, 스케이프고트 트리는 일반적인 이진 탐색 트리에 비해 노드당 추가 메모리 오버헤드가 없다: 키와 값 외에, 노드는 자식 노드에 대한 두 개의 포인터만 저장한다. 이는 스케이프고트 트리를 구현하기 쉽게 만들고, 데이터 구조 정렬 덕분에 노드 오버헤드를 최대 3분의 1까지 줄일 수 있다.
대부분의 균형 트리 알고리즘에서 사용되는 작고 점진적인 재균형 작업 대신, 스케이프고트 트리는 드물지만 비용이 많이 드는 "희생양"을 선택하여 희생양을 뿌리로 하는 서브트리를 완전한 이진 트리로 완전히 재구성한다. 따라서 스케이프고트 트리는 최악의 경우 의 갱신 성능을 가진다.
스케이프고트 트리 이론
이진 탐색 트리는 노드의 절반이 루트의 왼쪽에 있고 절반이 오른쪽에 있으면 무게 균형이 잡혀 있다고 말한다.
알파-무게 균형 노드는 완화된 무게 균형 기준을 충족하는 것으로 정의된다:
여기서 size는 재귀적으로 정의될 수 있다:
심지어 퇴화된 트리(연결 리스트)도 α=1이면 이 조건을 만족하지만, α=0.5이면 거의 완전 이진 트리만 일치한다.
알파-무게 균형 이진 탐색 트리는 또한 알파-높이 균형이어야 한다. 즉,
대우에 의해, 알파-높이 균형이 아닌 트리는 알파-무게 균형이 아니다.
스케이프고트 트리는 항상 알파-무게 균형을 유지한다고 보장되지는 않지만, 항상 느슨하게 알파-높이 균형을 유지한다. 즉,
이 높이 균형 조건의 위반은 삽입 시점에 감지될 수 있으며, 이는 무게 균형 조건의 위반이 존재해야 함을 의미한다.
스케이프고트 트리 이론
이것은 스케이프고트 트리를 레드-블랙 트리와 유사하게 만들며, 둘 다 높이에 대한 제약이 있다. 그러나 회전(또는 스케이프고트 트리의 경우, 재균형)이 발생하는 위치를 결정하는 구현 방식에서는 크게 다르다. 레드-블랙 트리는 각 노드에 추가 '색상' 정보를 저장하여 위치를 결정하는 반면, 스케이프고트 트리는 알파-무게 균형이 아닌 희생양을 찾아 재균형 작업을 수행한다. 이는 AVL 트리와 느슨하게 유사하며, 실제 회전은 노드의 '균형'에 따라 달라지지만, 균형을 결정하는 방식은 크게 다르다. AVL 트리는 모든 삽입/삭제 시 균형 값을 확인하므로 일반적으로 각 노드에 저장되지만, 스케이프고트 트리는 필요할 때만 계산할 수 있으며, 이는 희생양을 찾아야 할 때만 해당된다.
다른 대부분의 자가 균형 탐색 트리와 달리, 스케이프고트 트리는 균형에 있어 완전히 유연하다. 이들은 0.5 < α < 1인 모든 α 값을 지원한다. 높은 α 값은 재균형을 적게 발생시켜 삽입을 빠르게 하지만, 탐색과 삭제는 느려지며, 낮은 α 값은 그 반대이다. 따라서 실제 응용에서는 이러한 작업이 얼마나 자주 수행되어야 하는지에 따라 α 값을 선택할 수 있다.
스케이프고트 트리 작업
탐색은 표준 이진 탐색 트리에서 수정되지 않았으며, 최악의 경우 시간은 이다. 이는 최악의 경우 시간이 인 스플레이 트리와 대조된다. 다른 자가 균형 이진 탐색 트리에 비해 노드 메모리 오버헤드가 줄어들어 참조 국부성 및 캐싱을 더욱 향상시킬 수 있다.
삽입은 불균형 이진 탐색 트리와 동일한 기본 아이디어로 구현되지만, 몇 가지 중요한 변경 사항이 있다.
삽입 지점을 찾을 때, 새 노드의 깊이도 기록해야 한다. 이는 탐색의 각 반복 중에 증가하는 간단한 카운터를 통해 구현되며, 루트와 삽입된 노드 사이의 에지 수를 효과적으로 계산한다. 이 노드가 알파-높이 균형 속성(위에서 정의됨)을 위반하면 재균형이 필요하다.
재균형을 위해 희생양을 루트로 하는 전체 서브트리가 균형화 작업을 거친다. 희생양은 삽입된 노드의 조상 중에서 알파-무게 균형이 아닌 노드로 정의된다. 이러한 조상은 항상 하나 이상 존재한다. 그 중 하나를 재균형하면 알파-높이 균형 속성이 복원된다.
희생양을 찾는 한 가지 방법은 새 노드에서 루트로 다시 올라가서 알파-무게 균형이 아닌 첫 번째 노드를 선택하는 것이다.
스케이프고트 트리 작업
루트로 다시 올라가려면 스택에 할당되거나 부모 포인터로 사용되는 의 저장 공간이 필요하다. 이는 각 자식을 내려갈 때 부모를 가리키게 하고, 다시 올라갈 때 수정함으로써 실제로 피할 수 있다.
잠재적인 노드가 유효한 희생양인지 확인하려면 해당 노드의 알파-무게 균형 속성을 확인해야 한다. 이를 위해 정의로 돌아갈 수 있다:
그러나 세 가지 크기 중 두 가지를 이미 알고 있으므로 세 번째만 계산하면 된다는 것을 깨달으면 큰 최적화를 할 수 있다.
이를 시연하기 위해 다음 예제를 고려해보자. 루트로 다시 올라간다고 가정하면:
그러나:
이 경우는 다음과 같이 단순화된다:
여기서 x = 이 노드, x + 1 = 부모이며 size(sibling)이 실제로 필요한 유일한 함수 호출이다.
희생양을 찾으면 희생양을 루트로 하는 서브트리는 완전히 균형 잡힌 상태로 재구성된다. 이는 서브트리의 노드를 순회하여 정렬된 순서로 값을 찾고 재귀적으로 중앙값을 서브트리의 루트로 선택함으로써  시간 안에 수행할 수 있다.
스케이프고트 트리 작업
재균형 작업은  시간(서브트리 노드 수에 따라 달라짐)이 걸리므로, 삽입은 최악의 경우  시간이 걸린다. 그러나 이러한 최악의 시나리오가 분산되어 있으므로 삽입은 의 분할 상환 시간이 걸린다.
노드 v의 불균형(Imbalance)을 왼쪽 노드와 오른쪽 노드의 크기 차이의 절댓값에서 1을 뺀 값 또는 0 중 큰 값으로 정의한다. 다시 말해:
v를 뿌리로 하는 서브트리를 재구성한 직후, I(v) = 0이다.
보조 정리: v를 뿌리로 하는 서브트리를 재구성하기 직전, 

(는 빅 오메가 표기법이다.)
보조 정리의 증명:
가 재구성 직후 서브트리의 루트라고 하자. 이다. 만약 개의 퇴화 삽입(즉, 삽입된 각 노드가 높이를 1씩 증가시키는 경우)이 있다면, 
,
 이고
이다.
재구성 전에 이므로, 를 뿌리로 하는 서브트리에 개의 삽입이 있었고, 이 삽입들은 재구성으로 이어지지 않았다. 이 삽입들은 각각  시간에 수행될 수 있다. 재구성을 유발하는 마지막 삽입 비용은 이다. 총합 분석을 사용하면 삽입의 분할 상환 비용이 이라는 것이 분명해진다:
스케이프고트 트리 작업
스케이프고트 트리는 삭제가 삽입보다 쉽다는 점에서 특이하다. 삭제를 가능하게 하려면 스케이프고트 트리는 트리 데이터 구조와 함께 추가 값을 저장해야 한다. 이 속성을 MaxNodeCount라고 부르며, 이는 단순히 도달한 최고 NodeCount를 나타낸다. 전체 트리가 재균형될 때마다 NodeCount로 설정되며, 삽입 후에는 max(MaxNodeCount, NodeCount)로 설정된다.
삭제를 수행하려면 단순 이진 탐색 트리에서와 같이 노드를 제거하면 되지만,
이면 루트를 중심으로 전체 트리를 재균형하고, MaxNodeCount를 NodeCount로 설정하는 것을 잊지 말아야 한다.
이는 삭제에 최악의 경우  시간을 제공하며, 분할 상환 시간은 이다.
스케이프고트 트리가 개의 요소를 가지고 방금 재구성되었다고 가정해 보자(다시 말해, 완전 이진 트리이다). 트리가 재구성되기 전에 최대 개의 삭제가 수행될 수 있다. 이 삭제들은 각각  시간이 걸린다(요소를 찾고 삭제된 것으로 표시하는 데 걸리는 시간). 번째 삭제는 트리가 재구성되도록 하고 (또는 그냥 ) 시간이 걸린다. 총합 분석을 사용하면 삭제의 분할 상환 비용이 이라는 것이 분명해진다:
스케이프고트 트리 어원
스케이프고트 트리라는 이름은 "[...] 뭔가 잘못되었을 때 사람들이 비난할 사람(희생양)을 찾는 경향이 있다는 일반적인 지혜에 기반한다." 성경에서 스케이프고트는 다른 사람들의 죄를 의례적으로 짊어지고 쫓겨나는 동물이다.
트립 (자료 구조)
컴퓨터 과학에서 트립(Treap)과 확률적 이진 탐색 트리는 순서 있는 키의 동적 집합을 유지하고 키 간의 이진 검색 알고리즘을 허용하는 서로 밀접하게 관련된 두 가지 형태의 이진 탐색 트리 자료 구조이다. 어떤 키 삽입 및 삭제 시퀀스 후에도 트리의 모양은 무작위 이진 트리와 동일한 확률 분포를 가진 무작위 변수이다. 특히, 높은 확률로 높이는 키 수의 로그에 비례하므로 각 검색, 삽입 또는 삭제 작업은 로그 시간 안에 수행된다.
트립 (자료 구조) 설명
트립은 1989년 라이문트 자이델과 세실리아 R. 아라곤에 의해 처음 기술되었다. 그 이름은 혼성어로 트리와 힙을 합친 것이다.
이는 각 키에 (무작위로 선택된) 숫자 우선순위가 부여된 카르테시안 트리이다. 다른 이진 탐색 트리와 마찬가지로 노드의 중위 순회 순서는 키의 정렬된 순서와 같다. 트리의 구조는 힙 순서를 유지해야 한다는 요구 사항에 의해 결정된다. 즉, 모든 비리프 노드의 우선순위는 자식의 우선순위보다 크거나 같아야 한다. 따라서 일반적으로 카르테시안 트리와 마찬가지로 루트 노드는 최대 우선순위 노드이며, 왼쪽 및 오른쪽 서브트리는 해당 노드의 왼쪽과 오른쪽에 있는 정렬된 순서의 서브시퀀스에서 동일한 방식으로 형성된다.
트립 (자료 구조) 설명
트립을 설명하는 동등한 방법은 가장 높은 우선순위부터 노드를 이진 탐색 트리에 삽입하여 재조정 없이 형성될 수 있다는 것이다. 따라서 우선순위가 독립적인 무작위 숫자(두 노드가 동일한 우선순위를 가질 가능성이 거의 없도록 충분히 큰 우선순위 공간에서 분포된)라면 트립의 모양은 무작위 이진 탐색 트리의 모양과 동일한 확률 분포를 갖는다. 무작위 이진 탐색 트리는 무작위로 선택된 삽입 순서로 재조정 없이 노드를 삽입하여 형성된 탐색 트리이다. 무작위 이진 탐색 트리는 높은 확률로 로그 높이를 갖는 것으로 알려져 있으므로 트립도 마찬가지이다. 이는 퀵 정렬의 이진 탐색 트리 논증과 유사하며 퀵 정렬이 예상  시간에 실행된다. 이진 탐색 트리가 정렬의 동적 문제 버전의 해법이라면, 트립은 우선순위가 피벗 선택을 안내하는 동적 퀵 정렬에 특히 해당한다.
아라곤과 자이델은 또한 자주 접근되는 노드에 더 높은 우선순위를 부여하는 것을 제안한다. 예를 들어, 각 접근 시 무작위 숫자를 선택하고 이전 우선순위보다 높으면 해당 숫자로 노드의 우선순위를 대체하는 프로세스를 통해서이다. 이 수정은 트리가 무작위 형태를 잃게 할 것이다. 대신, 자주 접근되는 노드는 트리 루트 근처에 있을 가능성이 더 높아져 해당 노드에 대한 검색이 더 빨라질 것이다.
나오르와 니심은 공개 키 암호 시스템에서 인증 인증서를 유지하는 응용 분야를 설명한다.
트립 (자료 구조) 연산
트립은 다음 기본 연산을 지원한다:
트립에 새 키 x를 삽입하려면 x에 대한 무작위 우선순위 y를 생성한다. 트리에서 x를 이진 검색하고 이진 검색이 x에 대한 노드가 존재해야 한다고 결정하는 리프 위치에 새 노드를 생성한다. 그런 다음 x가 트리의 루트가 아니고 해당 부모 z보다 큰 우선순위 번호를 갖는 한, x와 z 사이의 부모-자식 관계를 역전시키는 트리 회전을 수행한다.
트립에서 노드 x를 삭제하려면, x가 트리의 리프이면 단순히 제거한다. x가 단일 자식 z를 가지면 트리에서 x를 제거하고 z를 x의 부모의 자식으로 만든다 (또는 x가 부모가 없으면 z를 트리의 루트로 만든다). 마지막으로 x가 두 자식을 가지면 트리에서 해당 위치를 정렬된 순서에서 즉시 후속 z의 위치와 교환하여 이전 경우 중 하나를 발생시킨다. 이 마지막 경우, 교환은 z의 힙 순서 속성을 위반할 수 있으므로 이 속성을 복원하기 위해 추가 회전을 수행해야 할 수 있다.
단일 요소 삽입, 삭제 및 조회 작업 외에도 트립에서 여러 빠른 "대량" 작업이 정의되었다: 합집합, 교집합 및 집합 차이. 이들은 두 가지 도우미 작업인 분할(split) 및 결합(join)에 의존한다.
트립 (자료 구조) 연산
트립을 두 개의 작은 트립으로 분할하려면, 키 x보다 작은 것과 키 x보다 큰 것으로 나누고, 트립의 어떤 노드의 우선순위보다도 큰 최대 우선순위를 가진 x를 트립에 삽입한다. 이 삽입 후 x는 트리의 루트 노드가 될 것이며, x보다 작은 모든 값은 왼쪽 서브트리에서, x보다 큰 모든 값은 오른쪽 서브트리에서 발견될 것이다. 이것은 트립에 단일 삽입하는 것과 동일한 비용이 든다.
트립 (자료 구조) 연산
이전 분할의 결과물인 두 트립을 결합할 때, 첫 번째 트립의 가장 큰 값이 두 번째 트립의 가장 작은 값보다 작다고 안전하게 가정할 수 있다. x 값을 가진 새 노드를 생성하고, x가 첫 번째 트립의 최대 값보다 크고 두 번째 트립의 최소 값보다 작도록 하며, 최소 우선순위를 할당한 다음 왼쪽 자식을 첫 번째 힙으로, 오른쪽 자식을 두 번째 힙으로 설정한다. 힙 순서를 수정하기 위해 필요에 따라 회전한다. 그 후, 이는 리프 노드가 될 것이며 쉽게 삭제할 수 있다. 결과는 두 원래 트립이 병합된 하나의 트립이다. 이는 효과적으로 분할을 "되돌리는" 것이며, 비용도 동일하다. 더 일반적으로, 결합 연산은 임의의 우선순위(즉, 가장 높을 필요는 없는)를 가진 키와 두 개의 트립에 대해 작동할 수 있다.
결합 알고리즘은 다음과 같다:
분할 알고리즘은 다음과 같다:
집합 A와 B를 나타내는 두 트립 t1과 t2의 합집합은 A ∪ B를 나타내는 트립 t이다. 다음 재귀 알고리즘은 합집합을 계산한다.
트립 (자료 구조) 연산
여기서 분할은 두 개의 트리를 반환하는 것으로 가정한다: 하나는 입력 키보다 작은 키를 포함하고, 다른 하나는 더 큰 키를 포함한다. (이 알고리즘은 비파괴적이지만, 제자리 파괴적 버전도 존재한다.)
교집합 알고리즘도 유사하지만, join 도우미 루틴이 필요하다. 합집합, 교집합, 차집합 각각의 복잡성은 크기 m과 n을 가진 트립의 경우 m ≤ n일 때 O(m log ⁠n/m⁠)이다. 또한, 합집합에 대한 재귀 호출은 서로 독립적이므로 병렬로 실행될 수 있다.
Split과 Union은 Join을 호출하지만 트립의 균형 기준을 직접 다루지 않는다. 이러한 구현은 일반적으로 "join-based" 구현이라고 불린다.
키의 해시 값이 우선순위로 사용되고, 구조적으로 동일한 노드가 이미 생성 시 병합된다면, 각 병합된 노드는 키 집합의 고유한 표현이 될 것이다. 주어진 키 집합을 나타내는 동시 루트 노드가 하나만 있을 수 있다면, 두 집합은 포인터 비교를 통해 동일한지 테스트할 수 있으며, 이는 상수 시간이다.
이 기술은 두 집합 간의 차이가 작을 때에도 병합 알고리즘을 빠르게 수행하도록 향상시키는 데 사용될 수 있다. 입력 집합이 동일하다면, 합집합 및 교집합 함수는 즉시 입력 집합 중 하나를 결과로 반환하며 중단할 수 있고, 차집합 함수는 빈 집합을 반환해야 한다.
d를 대칭 차이의 크기라고 하자. 수정된 병합 알고리즘은 O(d log ⁠n/d⁠)로도 제한된다.
트립 (자료 구조) 확률적 이진 탐색 트리
트립에 대한 아라곤과 자이델의 연구 이후 마르티네스와 로우라가 도입한 확률적 이진 탐색 트리는 동일한 노드를 동일한 무작위 트리 형태 분포로 저장하지만, 무작위 구조를 유지하기 위해 트리 노드 내에 다른 정보를 유지한다.
각 노드에 무작위 우선순위를 저장하는 대신, 확률적 이진 탐색 트리는 각 노드에 작은 정수(자신을 포함하여 자손의 수)를 저장한다. 이 숫자는 트리 회전 작업 중에 회전당 상수 추가 시간만으로 유지될 수 있다. n개의 노드를 이미 가진 트리에 키 x를 삽입해야 할 때, 삽입 알고리즘은 1/(n + 1)의 확률로 x를 트리의 새 루트로 배치하고, 그렇지 않으면 (키가 루트보다 작거나 큰지에 따라) x를 왼쪽 또는 오른쪽 서브트리에 삽입하기 위해 삽입 프로시저를 재귀적으로 호출한다. 자손의 수는 알고리즘에 의해 각 단계에서 무작위 선택에 필요한 확률을 계산하는 데 사용된다. 서브트리의 루트에 x를 배치하는 것은 트립에서와 같이 리프에 삽입한 다음 위로 회전시키거나, 마르티네스와 로우라가 설명한 대체 알고리즘으로 서브트리를 두 조각으로 분할하여 새 노드의 왼쪽 및 오른쪽 자식으로 사용하는 방식으로 수행할 수 있다.