사전식 순서

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 형식 언어 이론에서의 정의
3. 성질
4. 예시
- 4.1. 단어 정렬
- 4.2. 숫자 및 날짜 정렬
5. 응용
참조

1. 개요

사전식 순서는 여러 집합의 원소를 묶어 만든 곱집합에 정의되는 순서로, 단어, 숫자, 날짜 등을 정렬하는 데 사용된다. 각 집합이 정렬된 순서를 가질 때, 곱집합의 원소들을 구성 요소의 순서에 따라 비교하여 순서를 정한다. 형식 언어 이론에서는 단어의 길이나 알파벳 순서를 기준으로 단어를 정렬하는 데 활용되며, 조합론에서는 부분 집합을 정렬하는 데 사용된다. 또한 ISO 8601 날짜 표기법처럼 실생활의 날짜 정렬에도 적용된다.

2. 정의

사전식 순서는 주어진 순서 집합들의 원소들로 구성된 순열들을 정렬하는 방법이다. 예를 들어, 알파벳 순서에 따라 단어를 정렬하는 것이 사전식 순서의 한 예이다.

수학적으로 사전식 순서는 다음과 같이 정의된다. $I,\le)$가 정렬 집합이고, 각 $i\in I$에 대하여 $(X_i,\le)$가 부분 순서 집합이라고 하자. 그렇다면 곱집합 $\prod_{i\in I}X_i$ 위의 '''사전식 순서'''는 다음과 같은 부분 순서이다.

:$x\le y\iff x=y\lor x_{\min\{j\in I\colon x_j\ne y_j\}}
만약 모든 \(X_i$가 전순서 집합이라면, $\prod_{i\in I}X_i$ 또한 전순서 집합이다. 만약 모든 $X_i$가 정렬 집합이고 $I$가 유한 집합이라면, $\prod_{i\in I}X_i$ 또한 정렬 집합이다.
예시:

두 부분 순서 집합 $A$와 $B$가 주어졌을 때, 데카르트 곱 $A \times B$의 사전식 순서는 다음과 같이 정의된다.
$(a, b) \leq \left(a^{\prime}, b^{\prime}\right) \text{ iff } a < a^{\prime} \text{ or } \left(a = a^{\prime} \text{ and } b \leq b^{\prime}\right)$

이 결과는 부분 순서이다. 만약 $A$와 $B$가 각각 전순서 집합이라면, 결과 역시 전순서가 된다. 따라서 두 전순서 집합의 사전식 순서는 그들의 곱 순서의 선형 확장이다.

첨자 집합 $I$로 첨자화된 전순서 집합의 족 $(A_i)_{i \in I}$가 주어졌다고 하자. 이때, 직접곱 집합 $\prod_{i \in I} A_i$ 위에 다음과 같이 정의된 순서는 $\prod_{i \in I} A_i$ 위의 사전식 순서라고 불린다.

:$(a_i)_i < (b_i)_i \iff a_j < b_j \quad (j = \min \left\{ i \in I \mid a_i \ne b_i \right\})$.

$I$가 유한 집합 $\{1, ... , n\}$인 경우, $A_1, ... , A_n$를 전순서 집합이라고 할 때, 직접곱 집합 $A_1 \times \cdots \times A_n$ 위의 사전식 순서는 다음과 같다.

$a = (a_1, ... , a_n)$ 와 $b = (b_1, ... , b_n)$를 $A_1 \times \cdots \times A_n$의 원소라고 하자.

1. $a_1$과 $b_1$이 다르고, $a_1 < b_1$이라면 $a < b$이다.

2. $a_1 > b_1$라면 $a > b$이다.

3. $a_1 = b_1$이라면 $a_2$와 $b_2$를 비교한다.

이러한 조작을 반복하여 $a$와 $b$ 사이의 대소 관계가 결정된다.

사전식 순서의 중요한 성질은 정렬성을 보존한다는 것이다. 즉, 순서 집합 $A$와 $B$가 정렬 순서 집합이라면 사전식 순서를 부여한 직접곱 집합도 정렬 순서 집합이 된다.

2. 1. 형식 언어 이론에서의 정의

X

를 전순서 집합이며, "알파벳 집합"이라고 부른다고 가정한다.

X\sqcup\{\bullet\}

에 $\bullet\le x\;\forall x\in X$ 와 같은 전순서를 부여한다.

그러면

X

의 클레이니 스타

X^*

의 원소

s\in X^*

는 함수 \s\colon\mathbb Z^+\to X\sqcup\{\bullet\}\)로 생각할 수 있다. 이 경우 어떤

k_0\in\mathbb Z^+\cup\{0\}

에 대하여 다음이 성립한다.

$s(k)\in X\;\forall k\le k_0$
$s(k)=\bullet\;\forall k>k_0$

이때,

k_0

은

s

의 길이이다. 따라서,

X^*

는 $(X\sqcup\{\bullet\})^{\mathbb Z^+}$의 부분집합이다. $(X\sqcup\{\bullet\})^{\mathbb Z^+}$에 사전식 순서를 부여하고 이를

X^*

에 국한하면,

X^*

위의 전순서가 정의된다. 이는 사전에 쓰이는 문자열 정렬 방식과 동일하다.

어휘집의 단어들은 사전과 백과사전에서 사용되는 관례적인 순서를 따르며, 이는 단어를 구성하는 기호의 알파벳 순서에 기반한다. 사전식 순서는 기호의 순서가 주어졌을 때 단어의 순서를 공식화하는 방법이다.

공식적인 개념은 알파벳이라고 불리는 유한 집합에서 시작하며, 이는 전순서 집합이다. 즉, A의 서로 다른 두 기호 a와 b에 대해, a < b 또는 b < a이다.

A의 ''단어''는 기호가 없는 빈 시퀀스

\varepsilon

을 포함하여 A의 기호로 구성된 유한한 시퀀스이다. 이러한 모든 유한 단어 집합에 대한 사전식 순서는 다음과 같이 단어를 정렬한다.

1. 길이가 같은 두 단어

a = a_1a_2...a_k

와

b = b_1b_2...b_k

의 순서는 두 단어가 다른 첫 번째 위치 i (단어의 시작부터 계산)에서 기호의 알파벳 순서에 따라 결정된다. 즉,

a_i < b_i

일 때

a < b

이다.

2. 두 단어의 길이가 다른 경우, 일반적인 사전식 순서는 더 짧은 단어의 끝에 "공백" (A의 모든 요소보다 작은 특수 기호)을 채워 동일한 길이를 만든 후, 위와 같이 단어를 비교한다.

조합론에서는 더 짧은 시퀀스가 항상 더 긴 시퀀스보다 작은 규칙을 사용하기도 한다. 이러한 사전식 순서의 변형을 shortlex order라고 한다.

사전식 순서에서 "Thomas"는 "Thompson"보다 먼저 나타나는데, 다섯 번째 글자('a'와 'p')가 다르며, 알파벳에서 'a'가 'p'보다 먼저 나오기 때문이다.

사전식 순서의 중요한 속성은 각 n에 대해, 길이 n의 단어 집합이 사전식 순서로 정렬된다는 것이다(알파벳이 유한한 경우).^[3]^[1] 즉, 길이 n의 단어의 모든 감소하는 시퀀스는 유한하다. 그러나 ''모든'' 유한 단어의 집합이 정렬된다는 것은 아니다. 예를 들어, {b, ab, aab, aaab, ... } 단어의 무한 집합에는 사전식으로 가장 먼저 나오는 요소가 없다.

3. 성질

$(I,\le)$ 가 정렬 집합이고, 각 $i\in I$ 에 대하여 $(X_i,\le)$ 가 부분 순서 집합이라고 하자. 그렇다면 곱집합 $\prod_{i\in I}X_i$ 위의 사전식 순서는 다음과 같은 부분 순서이다.

: $x\le y\iff x=y\lor x_{\min\{j\in I\colon x_j\ne y_j\}}$

만약 모든 $X_i$ 가 전순서 집합이라면, $\prod_{i\in I}X_i$ 또한 전순서 집합이다. 만약 모든 $X_i$ 가 정렬 집합이며 $I$ 가 유한 집합이라면, $\prod_{i\in I}X_i$ 또한 정렬 집합이다.

사전식 순서의 중요한 속성 중 하나는 각 $n$ 에 대해, 길이 $n$ 의 단어 집합은 사전식 순서로 정렬된다는 것이다(알파벳이 유한한 경우). 즉, 길이 $n$ 의 단어의 모든 감소하는 시퀀스는 유한하다.^[3]^[1] ''모든'' 유한 단어의 집합이 정렬된다는 것은 사실이 아니다. 예를 들어, {b, ab, aab, aaab, ... } 단어의 무한 집합에는 사전식으로 가장 먼저 나오는 요소가 없다.

많은 응용 분야에서 잘 정렬된 집합이 필요하므로 사전식 순서의 변형이 종종 사용된다. 쇼트렉스 순서 또는 준 사전식 순서라고도 불리는 이 잘 정렬된 집합은 먼저 단어의 길이를 고려하는 것으로 구성된다 (만약 ${\text{length}}(a) < {\text{length}}(b)$ 이면, $a < b$ ). 길이가 같으면 사전식 순서를 사용한다. $A$ 에 대한 순서가 잘 정렬되어 있다면, 쇼트렉스 순서도 마찬가지이다.^[1]^[2]

사전식 순서는 정렬된 집합들의 ''n''-원 데카르트 곱에 대한 순서를 정의하며, 이 집합들이 모두 전순서 집합일 때 전체 순서가 된다.

자연수 또는 더 일반적으로 정렬된 집합에 의해 인덱싱되는 경우, 정렬된 집합의 무한한 집합족에 대한 사전식 순서를 정의할 수 있다. 이 일반화된 사전식 순서는 각 인자 집합이 전순서 집합일 때 전체 순서가 된다. 유한한 경우와 달리, 잘 정렬된 집합들의 무한 곱은 사전식 순서에 의해 반드시 잘 정렬되는 것은 아니다. 예를 들어, 가산 무한 이진 수열의 집합은 잘 정렬되어 있지 않다. 정확히 하나의 $1$ 을 갖는 수열의 부분 집합은 사전식 순서에서 최소 원소를 갖지 않는다.^[3]

사전식 순서의 중요한 성질 중 하나는 정렬성을 보존한다는 것이다. 즉, 순서 집합 $A$ 와 $B$ 가 정렬 순서 집합이라면 사전식 순서를 부여한 직접곱 집합도 정렬 순서 집합이 된다.

4. 예시

사전식 순서는 사전뿐만 아니라 숫자와 날짜에도 널리 사용된다.

로마 숫자는 두 숫자 중 어느 것이 더 작은지 즉시 알 수 없다는 단점이 있다. 반면에, 힌두-아라비아 숫자 시스템의 위치 기수법을 사용하면 자연수에 대한 자연 순서가 사전식 순서의 shortlex와 동일하기 때문에 숫자 비교가 쉽다.

십진법으로 쓰인 실수의 경우, 소수점 왼쪽 부분은 이전과 같이 비교하고, 같다면 소수점 오른쪽 부분을 사전식 순서로 비교한다.

ISO 8601 표준은 날짜를 YYYY-MM-DD로 표현하여, 날짜를 나타내는 문자 시퀀스에 대한 사전식 순서가 연대순과 일치하도록 한다. 이는 사전식 순서의 비사전적 사용의 예시이다.

4. 1. 단어 정렬

전순서 집합

X

를 '알파벳 집합'이라 하고,

X\sqcup\{\bullet\}

에

\bullet\le x\;\forall x\in X

와 같은 전순서를 부여한다.

X

의 클레이니 스타

X^*

의 원소

s\in X^*

는 함수

s\colon\mathbb Z^+\to X\sqcup\{\bullet\}

로 나타낼 수 있다. 이때, 어떤

k_0\in\mathbb Z^+\cup\{0\}

에 대하여 다음이 성립한다.

:

s(k)\in X\;\forall k\le k_0

:

s(k)=\bullet\;\forall k>k_0

여기서

k_0

은

s

의 길이다. 따라서

X^*

는

(X\sqcup\{\bullet\})^{\mathbb Z^+}

의 부분집합이다. 이 경우,

(X\sqcup\{\bullet\})^{\mathbb Z^+}

에 사전식 순서를 부여하고 이를

X^*

에 국한하면,

X^*

위의 전순서가 정의된다. 이는 사전에 사용되는 문자열 정렬 방법과 같다.

4. 2. 숫자 및 날짜 정렬

로마 숫자 시스템에서는 두 숫자 중 어느 것이 더 작은지 즉시 파악하기 어렵다. 반면, 힌두-아라비아 숫자 시스템의 위치 기수법을 사용하면 자연수에 대한 자연 순서가 사전식 순서의 shortlex와 동일하기 때문에 숫자 비교가 쉽다. 위치 기수법에서 자연수는 일련의 숫자 자릿수로 표현되며, 자릿수가 더 많거나 (선행 0을 무시하고) 자릿수가 같고 서로 다른 첫 번째 (가장 중요한) 숫자가 더 크면 다른 숫자보다 크다.

십진법으로 쓰인 실수의 경우, 소수점 왼쪽은 이전과 같이 비교하고, 같다면 소수점 오른쪽을 사전식 순서로 비교한다. '여백' 패딩은 후행 "0" 숫자이다.

음수를 고려할 때는 음수 비교를 위해 순서를 반대로 해야 한다. 이는 사람에게는 문제가 되지 않지만, 컴퓨터에게는 부호 테스트에 시간이 걸릴 수 있다. 그래서 컴퓨터에서 부호 있는 정수를 표현하기 위해 2의 보수 표현을 사용하기도 한다.

사전식 순서의 비사전적 사용 예시로 날짜에 대한 ISO 8601 표준이 있다. ISO 8601은 날짜를 YYYY-MM-DD로 표현한다. 이 방식은 날짜를 나타내는 문자 시퀀스에 대한 사전식 순서가 연대순과 일치한다는 장점이 있다. 즉, 더 이른 서기 날짜는 9999년까지의 더 늦은 날짜보다 사전식 순서에서 더 작다. 이러한 날짜 정렬은 별도의 정렬 알고리즘 없이 날짜를 쉽게 컴퓨터로 정렬할 수 있게 해준다.

5. 응용

조합론 외에도 사전식 순서는 다양한 분야에서 응용된다.

컴퓨터 과학 분야에서는 문자열을 사전식으로 정렬하는 알고리즘이 널리 사용된다. 예를 들어, ISO 8601 날짜 형식(YYYYMMDD)은 연, 월, 일을 나타내는 숫자를 이어 붙여 표현하는데, 이 형식은 문자열을 사전식 순서로 정렬하면 시간 순서대로 정렬되는 특징을 갖는다. 단, 연도는 4자리, 월과 일은 2자리 숫자로 표현해야 한다. 예를 들어, 1월은 '01'과 같이 표현한다.

수학의 다항식 연산에서도 사전식 순서가 활용된다. 그뢰브너 기저 계산과 같은 알고리즘에서는 단항식 순서를 사용하는데, 그중 하나가 사전식 순서이다. 단항식 순서는 단항식의 모노이드 구조와 호환되어야 하며, 그뢰브너 기저의 경우 모든 비상수 단항식이 단항식 1보다 커야 한다는 조건이 추가된다.

$\{1, \ldots, 6\}$ 의 3-부분 집합들의 순서. 빨간색 사각형은 집합, 파란색은 증가 수열, 회색은 지시 함수를 십진법으로 변환한 것이다. 회색 숫자는 colexicographical 순서로 번호가 매겨지고 0부터 시작하는 $\{1, \ldots, 6\}$ 의 모든 부분 집합에서 부분 집합의 순위이다. 사전식(lex) 및 colexicographical(colex) 순서는 맨 위에 있고 해당 역순서(rev)는 맨 아래에 있다.

5. 1. 조합론

조합론에서, 주어진 집합

S

의 유한 부분 집합을 열거해야 할 때가 많기 때문에 정렬해야 한다. 이를 위해

S

에 대한 순서를 선택한다. 그런 다음,

S

의 부분 집합을 정렬하는 것은 그것을 증가 수열로 변환하는 것과 같다. 결과 수열에 대한 사전식 순서는 부분 집합에 대한 순서를 유도하며, 이를 사전식 순서라고도 한다.

이러한 맥락에서, 일반적으로 먼저 기수별로 부분 집합을 정렬하는 것을 선호하며, 이는 shortlex 순서에서와 같다. 따라서, 고정된 기수의 부분 집합에 대한 순서만 고려한다.

예를 들어, 자연수의 자연 순서를 사용하여

S = \{1, 2, 3, 4, 5, 6\}

의 세 개의 원소로 구성된 부분 집합에 대한 사전식 순서는 다음과 같다.

: 123 < 124 < 125 < 126 < 134 < 135 < 136 < 145 < 146 < 156 < 234 < 235 < 236 < 245 < 246 < 256 < 345 < 346 < 356 < 456

주어진 자연수의 기수를 갖는 유한 부분 집합을 정렬하기 위해, 사전 역순(colexicographical order, colex)이 종종 더 편리하다. 모든 초기 세그먼트가 유한하기 때문에, 사전 역순은 자연수와

n

개의 자연수 집합 사이의 순서 동형 사상을 정의한다. 이는 사전식 순서의 경우와는 다른데, 사전식 순서에서는 예를 들어 모든

n > 2

에 대해

12n < 134

가 성립한다.

'''사전 역순'''은 유한 수열을 왼쪽에서 오른쪽으로 읽는 대신 오른쪽에서 왼쪽으로 읽음으로써 얻는 사전식 순서의 변형이다. 보다 정확하게는, 두 수열 간의 사전식 순서는 다음과 같이 정의된다.

:

a_1a_2...a_k

<^lex

b_1b_2...b_k

(

a_i

와

b_i

가 다른 첫 번째

i

에 대해

a_i

<

b_i

인 경우)

사전 역순은 다음과 같이 정의된다.

:

a_1a_2...a_k

<^colex

b_1b_2...b_k

(

a_i

와

b_i

가 다른 마지막

i

에 대해

a_i

<

b_i

인 경우)

일반적으로 사전 역순과 사전식 순서의 차이는 크지 않다. 그러나 증가하는 수열을 고려할 때, 일반적으로 부분 집합을 코딩할 때 두 순서는 크게 다릅니다.

예를 들어, 두 자연 정수의 증가하는 수열(또는 집합)을 정렬할 때, 사전식 순서는 다음과 같이 시작된다.

: 12 < 13 < 14 < 15 < ... < 23 < 24 < 25 < ... < 34 < 35 < ... < 45 < ...,

그리고 사전 역순은 다음과 같이 시작된다.

: 12 < 13 < 23 < 14 < 24 < 34 < 15 < 25 < 35 < 45 < ...

주어진 길이의 증가하는 수열에 대한 사전 역순의 주요 속성은 모든 초기 세그먼트가 유한하다는 것이다. 즉, 주어진 길이의 증가하는 수열에 대한 사전 역순은 자연수와 순서 동형 사상을 유도하며, 이러한 수열을 열거할 수 있다. 이것은 예를 들어 Kruskal–Katona 정리의 증명에서 조합론에서 자주 사용된다.^[1]

5. 2. 단항식 순서

다항식을 다룰 때, 덧셈의 교환 법칙 때문에 항의 순서는 보통 중요하지 않다. 하지만 다항식의 나눗셈 같은 일부 알고리즘에서는 항을 특정 순서대로 나열해야 한다. 다변수 다항식에 대한 주요 알고리즘 중 상당수는 그뢰브너 기저와 관련이 있는데, 이를 위해서는 단항식 순서를 선택해야 한다. 단항식 순서는 전순서이며, 단항식의 모노이드 구조와 호환된다. 여기서 "호환"이란 모노이드 연산이 곱셈으로 표현될 때

a < b

이면

ac < bc

임을 의미한다. 이러한 호환성은 다항식에 단항식을 곱해도 항의 순서가 바뀌지 않는다는 것을 뜻한다. 그뢰브너 기저의 경우, 모든 비상수 단항식이 단항식 1보다 커야 한다는 추가 조건이 필요하다. 그러나 이 조건은 접선 원뿔 계산을 위한 알고리즘과 같이 다른 관련 알고리즘에는 적용되지 않는다.

그뢰브너 기저는 변수 개수가 고정된 다항식에 대해 정의되므로, 단항식 (예:

x_1 x_2^3 x_4 x_5^2

)을 지수 벡터 (여기서는 [1, 3, 0, 1, 2])로 나타내는 것이 일반적이다. 변수의 개수가

n

개이면, 모든 단항식 순서는

\Z^n

의 단항식 순서를

\N^n

으로 제한한 것이다 (분류에 대해서는

\Z^n

의 군 순서 참고).

이러한 허용 가능한 순서 중 하나가 바로 사전식 순서이다. 역사적으로 그뢰브너 기저를 정의하는 데 처음 사용되었으며, 다른 순서와 구별하기 위해 순수 사전식 순서라고도 불린다.

또 다른 순서로는 먼저 전체 차수를 비교한 후, 사전식 순서를 사용하여 같은 차수를 갖는 것들을 구별하는 방법이 있다. 이 순서는 사전식 순서나 차수 역 사전식 순서가 일반적으로 더 나은 특성을 가지기 때문에 널리 사용되지는 않는다.
차수 역 사전식 순서는 먼저 전체 차수를 비교하고, 전체 차수가 같으면 역 사전식 순서를 사용하는 방식이다. 즉, 두 개의 지수 벡터가 주어졌을 때,

[a_1, \ldots, a_n] < [b_1, \ldots, b_n]

다음 중 하나에 해당하면

a_1+ \cdots+ a_n < b_1+ \cdots+ b_n,

또는

a_1+ \cdots+ a_n = b_1+\cdots+ b_n \quad \text{ and }\quad a_i  >b_i \text{ for the largest } i \text{ for which } a_i \neq b_i.

이다.

이 순서에서는 1차 단항식들이 해당 미지수와 같은 순서를 가집니다 (역 사전식 순서를 사용했을 때는 그렇지 않다). 같은 전체 차수를 갖는 두 변수의 단항식을 비교할 때, 이 순서는 사전식 순서와 같다. 그러나 더 많은 변수가 있는 경우에는 그렇지 않다. 예를 들어, 세 변수를 갖는 2차 단항식의 지수 벡터에 대해 차수 역 사전식 순서는 다음과 같다.

[0, 0, 2] < [0, 1, 1] < [1, 0, 1] < [0, 2, 0] < [1, 1, 0] < [2, 0, 0]

반면 사전식 순서에서는 같은 지수 벡터들이 다음과 같이 정렬된다.

[0, 0, 2] < [0, 1, 1] < [0, 2, 0] < [1, 0, 1] < [1, 1, 0] < [2, 0, 0].

차수 역 사전식 순서의 유용한 특징은 동차 다항식이 가장 작은 미지수의 배수일 필요충분조건은 그 선도 단항식 (가장 큰 단항식)이 이 가장 작은 미지수의 배수라는 것이다.

5. 3. 사회적 응용

ISO 8601 날짜 형식은 YYYYMMDD(Y는 연, M은 월, D는 일) 형태로 표기하며, 단순한 문자 배열의 정렬 알고리즘만으로 시간 순서대로 정렬할 수 있다. 이 알고리즘이 제대로 작동하려면 연도는 4자리 숫자, 월과 일은 2자리 숫자로 표기해야 한다. 예를 들어 한 자리 숫자로 표기되는 날짜에는 0을 붙여 '01'과 같이 표기한다.

참조

_[1] 서적 Term Rewriting and All That Cambridge University Press
_[2] 서적 Information and randomness. An algorithmic perspective https://archive.org/[...] Springer-Verlag
_[3] 서적 Ordered Sets Springer
_[4] 간행물 Term orderings on the polynomial ring Springer Berlin Heidelberg
_[5] 논문 Admissible Orders and Linear Forms ACM 1987-05

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com