Ordine lessicografico

L'ordine lessicografico è un criterio di ordinamento di stringhe costituite da una sequenza di simboli per cui è già presente un ordine interno. La regola di ordinamento corrisponde a quella utilizzata nei dizionari, da cui deriva il nome, anche se è estesa ad un qualunque insieme di simboli.

Definizione

Un alfabeto finito totalmente ordinato di simboli è un insieme $\Sigma =\left(\delta _{1},\delta _{2},....\delta _{n}\right)$ , dotato di un ordine totale $\delta _{1}<\delta _{2}<\,\ldots <\delta _{n}$ .

Date due sequenze di simboli

I=\delta _{i_{1}}\delta _{i_{2}}\ldots \delta _{i_{n}}

J=\delta _{j_{1}}\delta _{j_{2}}\ldots \delta _{j_{m}}

,

si dice che $I<J$ se esiste un numero $k\in \mathbb {N}$ per cui $\delta _{i_{1}}\delta _{i_{2}}\ldots \delta _{i_{k}}=\delta _{j_{1}}\delta _{j_{2}}\ldots \delta _{j_{k}}$ e vale una delle seguenti relazioni:

\delta _{i_{k+1}}<\delta _{j_{k+1}}

k=n\land n<m

.

Algoritmo di confronto

La regola data sopra è equivalente al seguente algoritmo di confronto:

si pone $n=1$
si confrontano i simboli nella posizione n-esima della stringa:
- se una delle due stringhe non possiede l'elemento n-esimo, allora è minore dell'altra e l'algoritmo termina
- se entrambe le stringhe non possiedono l'elemento n-esimo, allora sono uguali e l'algoritmo termina
- se i simboli sono uguali, si passa alla posizione successiva della stringa ( $n\rightarrow n+1$ )
- se questi sono diversi, il loro ordine è l'ordine delle stringhe

L'ordine lessicografico sull'insieme prodotto

Data una famiglia di insiemi ${\mathcal {A}}=\left\{A_{1},\,A_{2},\,\ldots ,\,A_{n}\right\}$ , con i rispettivi ordini totali $\left\{<_{1},\,<_{2},\,\ldots ,\,<_{n}\right\}$ , l'ordine lessicografico dell'insieme prodotto

A_{1}\times A_{2}\times \ldots \times A_{n}

è dato da

(a_{1},a_{2},\dots ,a_{n})<^{d}(b_{1},b_{2},\dots ,b_{n})\iff (\exists \ m>0)\ (\forall \ i<m)(a_{i}=b_{i})\land (a_{m}<_{m}b_{m})

.

Con questa regola ogni posizione della stringa può corrispondere a simboli e criteri di ordinamento diversi; per $A_{1}=A_{2}=\ldots =A_{n}=\Sigma$ , con lo stesso ordine totale, si ottiene la definizione precedentemente data.

Proprietà

La relazione tra stringhe definita dall'insieme lessicografico è di ordine parziale stretto e gode pertanto della proprietà transitiva e asimmetrica.

Monomi

In algebra, e particolarmente in algebra computazionale è fondamentale avere un ordinamento sui termini di un polinomio, ovvero un ordine monomiale; questo problema può essere risolto con una variante dell'ordine lessicografico. In pratica, dato un alfabeto ordinato di variabili $x_{1},x_{2},\ldots$ si possono ordinare tutti i monomi considerando dapprima l'esponente di $x_{1}$ , quindi l'esponente di $x_{2}$ e così via, finché non si trova una differenza tra gli esponenti. A questo punto si considera minore il monomio per cui l'esponente è minore.

In simboli, se $\mathbf {a} =x_{1}^{a_{1}}x_{2}^{a_{2}}\ldots$ e $\mathbf {b} =x_{1}^{b_{1}}x_{2}^{b_{2}}\ldots$ , con $a_{i},b_{i}\in \mathbb {Z}$ , sono due monomi, e $k$ è il minimo valore per cui $a_{k}\neq b_{k}$ , allora $\mathbf {a} <\mathbf {b} \Leftrightarrow a_{k}<b_{k}$ , e $\mathbf {a} >\mathbf {b} \Leftrightarrow a_{k}>b_{k}$ .