Ordine lessicografico

L'ordine lessicografico è un criterio di ordinamento di stringhe costituite da una sequenza di simboli, per i quali è 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}$,

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

$n = k < 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 \ne 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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica