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}$.

Voci correlate

• Relazione binaria
• Ordine alfabetico
• Ordinamento sul grado totale

Collegamenti esterni

• (EN) Eric W. Weisstein, Lexicographic Order, su MathWorld, Wolfram Research.