辞書順

数学において、辞書式順序（語彙順序、辞書順とも呼ばれる）は、辞書のアルファベット順を、順序付けられた記号の列、より一般的には、完全に順序付けられた集合の要素の列に一般化したものです。

辞書式順序付けには、いくつかのバリエーションと一般化があります。 1 つのバリエーションは、シーケンスの要素を考慮する前にシーケンスの長さを比較することにより、異なる長さのシーケンスに適用されます。

組合せ論で広く使用されている別の変形では、有限集合に全順序を割り当て、部分集合を昇順のシーケンスに変換し、それに辞書式順序を適用することによって、与えられた有限集合の部分集合を順序付けます。

一般化は、部分的に順序付けられた集合のn項直積上の順序を定義します。この順序は、直積のすべての因子が全順序付けされている場合にのみ全順序になります。

辞書（ある言語で使用される単語の集合）内の単語には、辞書や百科事典で使用される慣例的な順序があり、これは単語を構成する記号のアルファベットの基本的な順序に依存します。辞書式順序は、基本的な記号の順序に基づいて語順を形式化する 1 つの方法です。

正式な概念は、完全に順序付けられた有限集合 A（アルファベットと呼ばれることが多い）から始まります。つまり、A内の同じシンボルではない任意の2 つのシンボルaとb は、 a < bまたはb < a のいずれかです。

Aの単語はAの記号の有限シーケンスであり、長さ 1 で 1 つの記号を含む単語、長さ 2 で 2 つの記号を含む単語などが含まれ、記号がまったく含まれない空のシーケンスも含まれます。これらすべての有限単語の集合に対する辞書式順序は、単語を次のように並べます。 ${\displaystyle \varepsilon }$

1. 同じ長さの 2 つの異なる単語、たとえばa = a ₁ a ₂ ... a _kとb = b ₁ b ₂ ... b _kがあるとします。2つの単語の順序は、2 つの単語が異なる最初の場所i (単語の先頭から数えて) の記号のアルファベット順によって決まります。 つまり、アルファベットの基本的な順序Aにおいてa _i < b _iである場合に限り、a < bとなります。
2. 2 つの単語の長さが異なる場合、通常の辞書式順序では、短い方の単語の末尾に「空白」（Aのすべての要素よりも小さいものとして扱われる特殊な記号）が埋め込まれ、単語の長さが同じになるまで、前の場合と同様に単語が比較されます。

しかし、組み合わせ論では、2 番目のケースに対して別の規則が頻繁に使用され、短いシーケンスは常に長いシーケンスよりも小さくなります。辞書式順序のこの変形は、ショートレックス順序と呼ばれることもあります。

辞書式順序では、「Thomas」という単語は「Thompson」の前に現れます。これは、この 2 つの単語が最初に 5 番目の文字 (「a」と「p」) で異なるためであり、アルファベットでは文字「a」が文字「p」の前に来ます。これが最初の違いであるため、この場合、5 番目の文字がアルファベット順の「最も重要な違い」となります。

辞書式順序の重要な特性は、各nに対して、長さnの単語の集合が辞書式順序に従って整列していることである（アルファベットが有限である場合）。つまり、長さnの単語のすべての減少シーケンスは有限である（または同等に、すべての空でない部分集合には最小の要素がある）。^{[1] [2]}すべての有限単語の集合が整列しているというのは真実ではない。たとえば、単語の無限集合 {b、ab、aab、aaab、... } には辞書式に最も古い要素がない。

辞書式順序は辞書だけでなく、数字や日付にもよく使用されます。

ローマ数字の欠点の 1 つは、2 つの数のうちどちらが小さいかがすぐにはわからないことです。一方、ヒンドゥー - アラビア数字の位取り記数法では、自然数の自然順序が辞書式順序の変形ショートレクスと同じなので、数の比較は簡単です。実際、位取り記数法では、自然数は数値の列で表され、自然数は桁数が多い (先頭のゼロを無視) か、桁数が同じで異なる最初の (最上位) 桁が大きい場合に、自然数は他の自然数よりも大きくなります。

10 進表記で記述された実数の場合、辞書式順序のわずかに異なるバリエーションが使用されます。小数点の左側の部分は前と同じように比較され、等しい場合は小数点の右側の部分が辞書式順序で比較されます。このコンテキストでのパディング「空白」は、末尾の数字「0」です。

負の数も考慮する場合、負の数を比較する順序を逆にする必要があります。これは通常、人間にとっては問題になりませんが、コンピュータにとっては問題になる場合があります (符号のテストには時間がかかります)。これが、コンピュータで符号付き整数を表すために2 の補数表現を採用する理由の 1 つです。

辞書以外で辞書式順序を使用する別の例としては、日付に関するISO 8601標準があります。この標準では、日付を YYYY-MM-DD として表します。この書式設定スキームの利点は、日付を表す文字列の辞書式順序が年代順と一致することです。辞書式順序では、西暦 9999 年までの西暦の日付は、西暦の日付よりも小さくなります。この日付順序により、別のソート アルゴリズムが不要になり、 コンピューターによる日付のソートが容易になります。

アルファベットA上の単語のモノイドは、 A上の自由モノイドです。つまり、モノイドの要素はAの要素の有限シーケンス (単語) (長さ 0 の空シーケンスを含む) であり、演算 (乗算) は単語の連結です。単語u は、 v = uwとなる単語 w が存在する場合、別の単語vの接頭辞(または「切り捨て」)です。この定義により、空単語 ( ) はすべての単語の接頭辞であり、すべての単語はそれ自身の接頭辞です ( wの場合)。これらのケースを除外する場合は注意が必要です。 ${\displaystyle \varepsilon }$ ${\displaystyle =\varepsilon }$

この用語を使用すると、上記の辞書式順序の定義はより簡潔になります。部分的または完全に順序付けられた集合Aと、A上の2 つの単語aとb ( bは空でない) が与えられた場合、次の条件の少なくとも 1 つが満たされると、辞書式順序で a < bが成立します。

• aはbの接頭辞である
• 単語u、v、w（空の可能性もある）とAの要素xとyが存在し、

x < y

a = uxv

b =ユーユー

この定義の接頭辞条件により、は空の単語で あることに注意してください。${\displaystyle \varepsilon <b\,\,{\text{ for all }}b\neq \varepsilon ,}$${\displaystyle \varepsilon }$

が 上の全順序である場合、 の単語上の辞書式順序も 上の全順序です。しかし、一般に、アルファベットが整列していても、これは整列順序ではありません。たとえば、A = { a , b }の場合、言語{ a ⁿ b | n ≥ 0, b > ε }には辞書式順序における最小要素がありません: ... < aab < ab < b。 ${\displaystyle \,<\,}$${\displaystyle A,}$${\displaystyle A.}$${\displaystyle A}$

多くのアプリケーションでは整列順序が求められるため、辞書式順序の変形がよく使用される。この整列順序は、ショートレックス順序または準辞書式順序とも呼ばれ、まず単語の長さを考慮し（長さ( a ) < 長さ( b )の場合）、長さが等しい場合は辞書式順序を使用する。A 上の順序が整列順序である場合、ショートレックス順序についても同様である。^{[2] [3]}${\displaystyle a<b}$

辞書式順序は、順序付き集合のn項直積の順序を定義します。これは、これらの集合がすべて完全に順序付けられている場合に全順序になります。直積の要素は、すべての に対して^番目の要素が属するシーケンスです。シーケンスの辞書式順序の評価は、シーケンス内で同じ順位を持つ要素のみを比較するため、辞書式順序は順序付き集合の直積にまで拡張されます。 ${\displaystyle E_{1}\times \cdots \times E_{n}}$${\displaystyle i}$${\displaystyle E_{i}}$${\displaystyle i.}$

具体的には、2つの半順序 集合と${\displaystyle A}$${\displaystyle B,}$デカルト積上の辞書式順序 は次のように定義される。 ${\displaystyle A\times B}$$${\displaystyle (a,b)\leq \left(a^{\prime },b^{\prime }\right){\text{ if and only if }}a<a^{\prime }{\text{ or }}\left(a=a^{\prime }{\text{ and }}b\leq b^{\prime }\right),}$$

結果は半順序です。と がそれぞれ全順序である場合、結果も全順序になります。したがって、2 つの全順序集合の辞書式順序は、それらの積順序の線形拡張です。 ${\displaystyle A}$${\displaystyle B}$

無限の順序付き集合族の直積に対しても同様に辞書式順序を定義できます。ただし、その族が自然数、またはより一般的には整列した集合によってインデックス付けされている場合です。この一般化された辞書式順序は、各因子集合が完全に順序付けられている場合、全順序です。

有限の場合とは異なり、整列順序の無限積は辞書式順序で整列しているとは限りません。たとえば、可算無限の2進数列の集合（定義により、自然数から への関数の集合で、カントール空間とも呼ばれる）は整列していません。 がちょうど1つある列のサブセット（つまり、{ 100000...、010000...、001000...、... }）には、 によって誘導される辞書式順序で最小元がありません。これは、 100000... > 010000... > 001000... > ...が無限降順チェーンであるためです。^[1]同様に、無限辞書式積もノイザンではありません。これは、 011111... < 101111... < 110111 ... < ...が無限昇順チェーンであるためです。 ${\displaystyle \{0,1\},}$ ${\displaystyle \{0,1\}^{\omega }}$${\displaystyle 1}$${\displaystyle 0<1,}$

整列集合から 全順序集合への関数は、の要素のインデックスが付いたシーケンスで識別できます。したがって、辞書式順序で順序付けすることができ、2つのそのような関数については、辞書式順序は、最小の値によって決定され、${\displaystyle X}$ ${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y.}$${\displaystyle f}$${\displaystyle g,}$${\displaystyle x}$${\displaystyle f(x)\neq g(x).}$

も整列しており、有限である場合、結果として得られる順序は整列しています。 上で示したように、が無限である場合はそうではありません。 ${\displaystyle Y}$${\displaystyle X}$${\displaystyle X}$

組合せ論では、与えられた集合の有限部分集合を列挙し、順序付けなければならないことがよくあります。このために、通常は の順序を選択します。次に、の部分集合をソートすることは、それを昇順に変換することと同等です。結果として得られるシーケンスの辞書式順序により、部分集合の順序が誘導され、これは辞書式順序とも呼ばれます。 ${\displaystyle S.}$${\displaystyle S.}$${\displaystyle S}$

この文脈では、一般的には、ショートレックス順序のように、まずサブセットを基数でソートすることが好まれます。したがって、以下では、固定基数のサブセット上の順序のみを検討します。

例えば、整数の自然順序を用いると、の3つの要素の部分集合の辞書式順序は次のようになる。 ${\displaystyle 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。

自然数の与えられた濃度の有限部分集合を順序付ける場合、コレクシコグラフィー順序（下記参照）の方が便利な場合が多い。これは、すべての初期セグメントが有限であり、コレクシコグラフィー順序は自然数と自然数の集合の集合との間の順序同型性を定義するからである。これは辞書式順序には当てはまらず、辞書式順序では、例えば、すべての自然数に対して、${\displaystyle n}$${\displaystyle 12n<134}$${\displaystyle n>2.}$

を、要素が整数列である階数の自由アーベル群とし、演算は加算とする。上の群順序は全順序であり、これは加算と互換性があり、 ${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle n,}$${\displaystyle n}$${\displaystyle \mathbb {Z} ^{n}}$$${\displaystyle a<b\quad {\text{ if and only if }}\quad a+c<b+c.}$$

辞書式順序は、${\displaystyle \mathbb {Z} ^{n}.}$

^{辞書式順序は、 [4] [5]}上のすべての群順序を特徴付けるためにも使用できます。実際、実係数を持つ線型形式は、形式が線型独立である場合に単射となる、からへの写像を定義します(形式が従属している場合にも単射となることがあります。以下を参照)。この写像の像上の辞書式順序は、上の群順序を誘導します。ロビアーノの定理は、すべての群順序がこのようにして得られるというものです。 ${\displaystyle \mathbb {Z} ^{n}.}$${\displaystyle n}$ ${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle \mathbb {R} ^{n},}$${\displaystyle \mathbb {Z} ^{n}.}$

より正確には、上の群順序が与えられた場合、実係数を持つ整数形式と線型形式が存在し、から への誘導写像は次の特性を持ちます。 ${\displaystyle \mathbb {Z} ^{n},}$${\displaystyle s\leq n}$${\displaystyle s}$${\displaystyle \varphi }$${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle \mathbb {R} ^{s}}$

• ${\displaystyle \varphi }$単射である。
• から の像への同型性は、像が の辞書式順序を備えている場合の順序同型性である。${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle \varphi }$${\displaystyle \mathbb {R} ^{s}.}$

コレクシコグラフィック順序またはコレックス順序は、有限シーケンスを左から右に読むのではなく、右から左に読むことによって得られる辞書式順序の変形です。より正確には、2つのシーケンス間の辞書式順序は次のように定義されます。

a ₁ a ₂ ... a _k < ^lex b ₁ b ₂ ... b _{k 、}最初のiにおいてa _i < b _i（ただしa _iとb _iが異なる）の場合、

共辞典順序は次のように定義される。

a ₁ a ₂ ... a _k < ^colex b ₁ b ₂ ... b _k最後のiについてa _i < b _iの場合、ただしa _iとb _{i は}異なる

一般に、コレクシコグラフィー順序と辞書式順序の違いはそれほど大きくありません。ただし、サブセットをコーディングする場合など、シーケンスの増加を考慮すると、2 つの順序は大きく異なります。

例えば、2つの自然数の増加するシーケンス（または集合）を順序付ける場合、辞書式順序は次のように始まる。

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

そして、コレクシコグラフィーの順序は

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

与えられた長さの増加シーケンスのコレクシコグラフィー順序の主な特性は、すべての初期セグメントが有限であることです。言い換えると、与えられた長さの増加シーケンスのコレクシコグラフィー順序は、自然数との順序同型を誘導し、これらのシーケンスを列挙することを可能にします。これは、たとえばクラスカル-カトーナ定理の証明など、組み合わせ論で頻繁に使用されます。

多項式を考えるとき、加算は可換であるため、項の順序は一般に重要ではありません。ただし、多項式の長除算などの一部のアルゴリズムでは、項が特定の順序になっている必要があります。多変数多項式の主なアルゴリズムの多くは、グレブナー基底に関連しています。グレブナー基底は、単項式順序、つまり単項式のモノイド構造と互換性のある全順序の選択を必要とする概念です。ここで「互換性がある」とは、モノイド演算が乗法的に表される場合を意味します。この互換性は、多項式と単項式の積が項の順序を変更しないことを意味します。グレブナー基底の場合、さらに条件が満たされる必要があります。つまり、すべての非定数単項式は単項式1よりも大きいということです。ただし、この条件は、接円錐の計算アルゴリズムなど、他の関連アルゴリズムでは必要ありません。 ${\displaystyle a<b{\text{ implies }}ac<bc,}$

グレブナー基底は固定数の変数の多項式に対して定義されるため、単項式（たとえば）をその指数ベクトル（ここでは[1, 3, 0, 1, 2] ）と同一視するのが一般的です。nが変数の数である場合、すべての単項式順序はの単項式順序の への制限になります（分類については、上記の § の群順序を参照してください）。 ${\displaystyle x_{1}x_{2}^{3}x_{4}x_{5}^{2}}$${\displaystyle \mathbb {N} ^{n}}$${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle \mathbb {Z} ^{n},}$

これらの許容される順序の 1 つが辞書式順序です。これは歴史的に、グレブナー基底を定義するために最初に使用された順序であり、辞書式順序に関連する他の順序と区別するために 純粋辞書式順序と呼ばれることもあります。

もう 1 つは、まず合計次数を比較し、次に辞書式順序を使用して競合を解決することです。この順序は、辞書式順序または次数の逆辞書式順序の方が一般に優れた特性を持つため、広く使用されていません。

逆辞書式順序は、まず総次数を比較し、総次数 が 等しい場合は、共辞書式順序の逆順を使用する。つまり、2つの指数ベクトルが与えられた 場合 、$${\displaystyle [a_{1},\ldots ,a_{n}]<[b_{1},\ldots ,b_{n}]}$$$${\displaystyle a_{1}+\cdots +a_{n}<b_{1}+\cdots +b_{n},}$$$${\displaystyle 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 つの変数の単項式を比較する場合、この順序は辞書式順序と同じです。変数の数が多い場合はそうではありません。たとえば、3 つの変数の次数 2 の単項式の指数ベクトルの場合、次数逆辞書式順序は次のようになります。 $${\displaystyle [0,0,2]<[0,1,1]<[1,0,1]<[0,2,0]<[1,1,0]<[2,0,0]}$$

辞書順の場合、同じ指数ベクトルは次のように並べられる。 $${\displaystyle [0,0,2]<[0,1,1]<[0,2,0]<[1,0,1]<[1,1,0]<[2,0,0].}$$

次数逆辞書式順序の便利な特性は、同次多項式が最小の不定数の倍数となるのは、その主単項式（その大単項式）がこの最小の不定数の倍数である場合のみであるということです。

• 照合
• クリーネ・ブラウワー順序
• 辞書式優先順位- 経済学における辞書式順序の応用。
• 辞書式最適化- 辞書式に最大の要素を見つけるアルゴリズムの問​​題。
• 単位正方形上の辞書式順序位相
• テンソル抽象インデックス表記法における辞書式順序
• 辞書式に最小の文字列回転
• レキシミン注文
• ロングライン（トポロジー）
• リンドンの言葉
• スター積、部分順序を組み合わせる別の方法
• ショートレックス注文
• 全順序集合の直積上の順序

• Wikiversity の辞書式順序と共辞書式順序に関する学習教材