Ordre lexicogràfic

En matemàtiques, l'ordre lexicogràfic (també conegut com a ordre alfabètic o producte lexicogràfic) és una generalització de l'ordre alfabètic que s'aplica a les paraules quan s'analitzen cadascuna de les seves lletres.

Definició

Donats dos conjunts parcialment ordenats A i B, l'ordre lexicogràfic sobre el producte cartesià A × B es defineix com

(a,b) ≤ (a′,b′) si i només si a < a′ o (a = a′ i b ≤ b′).

El resultat és un ordre parcial. Si tant A com B són totalment ordenats, llavors el resultat també és totalment ordenat. L'ordre lexicogràfic de dos conjunts totalment ordenats és, doncs, una extensió lineal del seu ordre producte.

Més en general, es pot definir l'ordre lexicogràfic sobre el producte cartesià de n conjunts ordenats, així com sobre la unió de conjunts ordenats.

Motivació i usos

L'origen del terme ordre lexicogràfic prové de la generalització arran de l'ordre de les paraules d'un diccionari o enciclopèdia: una seqüència de lletres (és a dir, una paraula)

a₁a₂ ... a_k

apareix en un diccionari abans d'una seqüència

b₁b₂ ... b_k

si i només si el primer índex i on a_i i b_i són diferents, a_i és anterior a b_i a l'alfabet.

Aquesta comparació assumeix que les dues seqüències tenen la mateixa longitud. Si no és així, hom pot afegir espais en blanc al final de la paraula més curta, fins a igualar les longituds, i establir que un espai en blanc apareix a l'alfabet abans que qualsevol altre símbol. Aquest procediment s'aplica també en els diccionaris. També es pot aplicar aquesta tècnica per ordenar frases. Vegeu l'article Ordre alfabètic.

Per exemple, la paraula "raonable" apareix als diccionaris abans que "raonament" perquè la lletra 'b' apareix abans que la 'm' a l'alfabet. Les 5 primeres lletres d'ambdues paraules són les mateixes, "raona", i a partir de la sisena lletra són diferents. Com que la primera diferència apareix a la sisena lletra, aquesta esdevé la més significativa a l'hora d'establir l'ordenació.

Un ordre lexicogràfic no té per què coincidir amb l'ordre alfabètic convencional. Per exemple, l'ordre numèric dels punts de codi d'Unicode no sempre correspon a les ordenacions alfabètiques tradicionals dels caràcters, que pot variar d'idioma a idioma. És a dir, l'ordre lexicogràfic induït pel punt de codi permet ordenar les cadenes de caràcters en un ordre canònic inambigu, però no les "alfabetitza" necessàriament en el sentit convencional.

Una propietat important de l'ordre lexicogràfic és que preserva la bona ordenació de productes finits; en particular, si A i B són conjunts ben ordenats, llavors el conjunt producte A × B amb l'ordre lexicogràfic és també un bon ordre.^[1] L'ordre lexicogràfic també preserva la propietat noetheriana; el producte lexicogràfic de dues (o de qualsevol nombre finit de) relacions noetherianes és també noetherià.^[2]

Una utilitat important de l'ordre lexicogràfic ve donada per l'esquema de formatat de dates ISO 8601, que estableix que una data s'ha d'expressar com AAAA-MM-DD. Aquesta ordenació de les dates porta a un algorisme d'ordenació senzill, on simplement s'han d'ordenar les dates en aquest format de la forma habitual com a cadenes de caràcters, i així s'obté un ordre cronològic. Per tal que aquest sistema funciona, però, cal que els anys estiguin sempre expressats amb 4 dígits, i que els mesos i els dies sempre estiguin expressats amb 2 dígits, completant amb un "0" per l'esquerra si és necessari; per exemple, els dies d'un sol dígit s'han d'expressar com '01', '02', ..., '09'.

Una altra generalització de l'ordre lexicogràfic apareix en la teoria de l'elecció social (teoria d'eleccions). Considerem una elecció amb 4 candidats A, B, C i D, on cada votant expressa la seva elecció ordenant de més a menys preferit els candidats, i suposem que el resultat és el següent:

18%	17%	33%	32%
A	B	C	D
B	A	D	B
C	C	A	A
D	D	B	C

El mètode de votació MinMax és un mètode de Condorcet simple que compta els vots segons un sistema de tots contra tots, i que jutja cada candidat segons la seva derrota més àmplia dos a dos (és a dir, s'emparellen tots els candidats contra tots). El guanyador és el candidat amb la derrota dos a dos més petita. En aquest exemple:

La derrota més gran d'A ve donada per D: 65% (33%+32%) prefereixen D sobre A.
La derrota més gran de B ve donada per D: 65% (33%+32%) prefereixen D sobre B.
La derrota més gran de C ve donada per A (o per B): 67% (18%+17%+32%) prefereixen A sobre C (i B sobre C).
La derrota més gran de D ve donada per C: 68% (18%+17%+33%) prefereixen C sobre D.

MinMax declara un empat entre A i B, ja que les derrotes més grans per ambdós són d'un 65%. Això és com dir que "raonable" i "raonament" haurien d'aparèixer al mateix lloc en un ordre alfabètic perquè comencen per la mateixa lletra. En canvi, si les derrotes es comparen de forma lexicogràfica, tenim el mètode MinLexMax. Segons MinLexMax, com que les derrotes més grans d'A i B són de la mateixa grandària, s'ha de comparar la següent derrota més gran:

La següent derrota més gran d'A és: cap.
La següent derrota més gran de B ve donada per A: 51% (18%+33%) prefereixen A sobre B.

Com que la següent derrota més gran de B és més àmplia que la següent derrota més gran d'A, MinLexMax escull A. Això té més sentit que l'empat MinMax, ja que una majoria prefereix A sobre B. A finalitza per davant de B segons MinLexMax, pel mateix motiu que "raonable" apareix abans que "raonament" en l'ordre alfabètic.

Una altra utilitat del principi minlexmax en teoria de l'elecció social és en el mètode de votació dels parells classificats (ranked pairs). Encara que el procediment de parells classificats construeix de forma eficient l'ordre final, el resultat d'aquest procediment és equivalent a trobar quina d'entre totes les ordenacions possibles és millor segons una comparació minlexmax. En aquest cas, hom pot comparar lexicogràficament dos possibles ordres de finalització mitjançant l'observació de les majories en el punt on difereixen, per tal de veure quina de les dues ordenacions inverteix la major d'aquestes majories; aquest ordre és el pitjor de les dues. (Les majories on les dues ordenacions coincideixen són irrellevants en el mateix sentit que "raona" és irrellevant quan es compara alfabèticament "raonable" i "raonament". Les paraules "raonable" i "raonament" es comparen emprant la primera lletra on difereixen, de la mateixa maneea que el sistema de parells classificats comparen dos ordres de finalització emprant la majoria més gran on difereixen.) En l'exemple anterior, l'ordre de finalització segons el mètode de parells classificats és ABCD (que acaba escollint A). ABCD afirma les majories que prefereixen A sobre B, A sobre C, B sobre C i C sobre D, i inverteix les majories que prefereixen D sobre A i D sobre B. La majoria més gran invertida a ABCD és del 65%. L'altra única ordenació que no inverteix una majoria més gran és BACD, que també inverteix un 65%. ABCD és una ordenació millor que BACD perquè el conjunt de majories on ABCD i BACD difereixen és {la majoria que prefereix A sobre B} i BACD inverteix la majoria més gran en aquest conjunt. (Càlculs similars mostren que ABCD és millor que qualsevol altra ordenació de finalització.)

A continuació es mostra un exemple que il·lustra que MinLexMax i el mètode de parells classificats no són equivalents: suposem que hi ha quatre candidats A, B, C i D, i suposem que les 6 majories dos a dos són:

56% prefereixen A sobre B
55% prefereixen B sobre C
54% prefereixen C sobre A
53% prefereixen A sobre D
52% prefereixen B sobre D
51% prefereixen C sobre D

MinLexMax (i MinMax) escullen D. El mètode de parells classificats determina l'ordenació ABCD, que té D en últim lloc (i proclama A com a guanyador).

Cas de productes múltiples

Suposem que $\{A_{1},A_{2},\cdots ,A_{n}\}$ és una n-tupla de conjunts, amb ordres totals respectius $\{<_{1},<_{2},\cdots ,<_{n}\}$ . L'ordre alfabètic $<^{d}$ de $A_{1}\times A_{2}\times \cdots \times A_{n}$ és:

(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})

Això és, si un dels termes $a_{m}<_{m}b_{m}$ i tots els termes precedents són iguals.

Col·loquialment, $a_{1}$ representa la primera lletra, $a_{2}$ la segona, i així successivament, quan mirem en un diccionari, d'aquí el nom.

Això es pot expressar d'una manera més elegant amb una definició recursiva d'ordenació de qualsevol conjunt $C=A_{j}\times A_{j+1}\times \cdots \times A_{k}$ representada per $<^{d}(C)$ .

Amb aquesta notació, se satisfà

a<^{d}(A_{i})a'\iff (a<_{i}a')

(a,b)<^{d}(A_{i}\times B)(a',b')\iff a<^{d}(A_{i})a'\lor (a=a'\ \land \ b<^{d}(B)b')

on $B=A_{i+1}\times A_{i+2}\times \cdots \times A_{n}$ .

En altres paraules: es comparen els primers termes. Si són iguals, llavors comparem els segons termes, i així successivament. La relació entre els primers termes que no són iguals determina la relació entre la totalitat dels elements.

Al contrari que el cas finit, el producte cartesià infinit de conjunts be lrdenats no té per què ser necessàriament ben ordenat segons l'ordre lexicogràfic. Per exemple, el conjunt de successions binàries infinites numerables (per definició, el conjunt de funcions dels nombres naturals en {0, 1}, també conegut com l'espai de Cantor {0, 1}^ω) no és ben ordenat; el subconjunt de successions que tenen exactament un 1 (és a dir, { 100000..., 010000..., 001000..., ... }) no té un element mínim per l'ordre lexicogràfic induït per 0 < 1, perquè 100000... > 010000... > 001000... > ... és una cadena descendent infinita.^[1] Anàlogament, el producte lexicogràfic infinit tampoc no és noetherià, perquè 011111... < 101111... < 110111 ... < ... és una cadena ascendent infinita.

Grups i espais vectorials

Si els conjunts són grups ordenats, llavors el resultat és un grup no arquimedià, perquè per exemple n(0,1) < (1,0) per a qualsevol n.

Si els conjunts són espais vectorials ordenats sobre R (en particular, el propi R), llavors el resultat és també un espai vectorial ordenat.

Generalitzacions

Ordenació de seqüències de longituds diferents

Donat un conjunt A parcialment ordenat, les consideracions anteriors permeten definir de manera natural un ordre parcial lexicogràfic $<^{\mathrm {d} }$ sobre el monoide lliure A* format pel conjunt de successions finites d'elements d'A, amb l'operació definida per la concatenació de successions, de la següent forma:

u<^{\mathrm {d} }v

si

$u$ és un prefix de $v$ , o
$u=wau'$ i $v=wbv'$ , on $w$ és el prefix comú més llarg de $u$ i $v$ , $a$ i $b$ són membres d'A tals que $a<b$ , i $u'$ i $v'$ són membres d'A*.

Si < és un ordre total sobre A, llavors <^d és un ordre lexicogràfic sobre A*. Si A és un alfabet finit i totalment ordenat, llavors A* és el conjunt de totes les paraules sobre A. Tot i això, aquest no és, en general, un bon ordre, encara que ho sigui sobre l'alfabet A; per exemple, si A = {a, b}, el llenguatge {aⁿb | n ≥ 0} no té un element mínim: ... <^d aab <^d ab <^d b. Un bon ordre per a cadenes de caràcters, basat en l'ordre lexicogràfic, és l'ordre shortlex, encara que no és noetherià.^[2]

Es pot definir l'ordre shortlex com el producte lexicogràfic de dos ordres:

l'ordenació de cadenes de caràcters per la seva longitud, i
la unió (disjunta) d'ordres de cadenes de caràcters finites de qualsevol longitud, amb algun ordre (habitualment, l'ordre lexicogràfic).^[2]

De manera semblant, també és possible comparar una cadena de caràcters finita i una d'infinita, o també dues cadenes infinites.

Es pot modelitzar la comparació de cadenes de diferents longituds si, a les cadenes finites, s'hi adjunten per la dreta repeticions d'algun valor especial que sigui menor que qualsevol element de l'alfabet.

Aquesta ordenació és l'habitual per a cadenes de caràcters, com l'ordenació de diccionaris i índexs.

Ordre quasi-lexicogràfic

L'ordre quasi-lexicogràfic (o ordre shortlex) sobre el monoid lliure A^∗ basat en un alfabet ordenat A ordena les cadenes de caràcters per longitud, de tal manera que la cadena buida aparegui en primer lloc, i després per ordre lexicogràfic en Aⁿ, donades dues cadenes de longitud n.^[3]

Altres generalitzacions

Considerem el conjunt de funcions f d'un conjunt ben ordenat X a un conjunt totalment ordenat Y. Donades dues funcions f i g, l'ordre ve determinat pel més petit x tal que f(x) ≠ g(x).

Si Y també és ben ordenat i X és finit, llavors l'ordre resultant és un bon ordre. Com s'ha vist abans, si X és infinit, l'ordre no és, en general, un bon ordre.

Si X és infinit i Y té més d'un element, llavors el conjunt Y^X no és numerable.

Alternativament, considerem les funcions f d'un conjunt X amb un bon ordre invers cap a un conjunt ben ordenat Y amb mínim 0, restringida a aquelles funcions que són no-nul·les només en un subconjunt finit de X. El resultat és un bon ordre. Podem considerar, respectivament, un bon ordre X i aplicar-hi l'ordre lexicogràfic, on un x més alt vol dir una posició significativa. Això correspon a l'exponenciació de nombres ordinals Y^X. Si tant X com Y són numerables, llavors el conjunt resultant també és numerable.

Exemple: Monomis

En àlgebra, és habitual ordenar els termes d'un polinomi, definint una ordenació sobre els monomis en les variables indeterminades. Aquest detall s'acostuma a obviar quan els humans manipulen polinomis, però cal tenir-lo en compte amb detall en computació algebraica, per exemple quan es vol automatitzar un test d'igualtat de polinomis.

Més específicament, la definició de bases de Gröbner i el seu càlcul estan fonamentats en com escollir una ordenació dels monomis. Per tal de definir aquesta ordenació, s'identifica cada monomi (per exemple, $x_{1}x_{2}^{3}x_{4}x_{5}^{2}$ ) amb el seu vector d'exponents (per exemple, [1,3,0,1,2]), i s'escull un ordre sobre aquests vectors d'enters. Aquest ordre ha de complir algunes condicions addicionals per tal que sigui admissible de cara a les bases de Gröbner; vegeu Ordre monomial per a més detalls i les condicions d'admissibilitat.

Un d'aquests ordres admissibles és l'ordre lexicogràfic. Un altre ordre és l'ordre de grau total, que consisteix a comparar primer els graus totals, i després resoldre els conflictes emprant l'ordre lexicogràfic. Més en general, tot ordre admissible es pot definir com l'ordre lexicogràfic sobre els valors d'un conjunt de n formes lineals a coeficients reals, amb aquest ordre aplicat al vector dels exponents (aquí, n és el nombre de variables).^[4]

Fraccions decimals

Per a la part decimal de les fraccions decimals, a < b és cert igualment per a l'ordre numèric i l'ordre lexicogràfic sobre les respectives representacions digitals, sempre que no es tinguin en compte les expressions finalitzades amb un 9 periòdic, com 0,399999..., ni les finalitzades amb un 0 periòdic. Amb aquestes restriccions, existeix una bijecció que preserva l'ordre entre els nombres i les expressions decimals.

Ordre colexicogràfic

L'ordre colexicogràfic o colex és una estructura d'ordenació natural del producte cartesià de dos o més conjunts ordenats. Donats dos conjunts parcialment ordenats A i B, es defineix l'ordre colexicogràfic sobre el producte cartesià A × B com:

(a,b) ≤ (a′,b′) si i només si b < b′ o (b = b′ i a ≤ a′).

El resultat és un ordre parcial. Si tant A com B són totalment ordenats, llavors el resultat també és un ordre total.

En general, hom pot també definir l'ordre colexicogràfic sobre el producte cartesià de n conjunts ordenats. Suposem que $\{A_{1},A_{2},\ldots ,A_{n}\}$ és una n-tupla de conjunts, cadascun amb el seu ordre total respectiu $\{<_{1},<_{2},\ldots ,<_{n}\}$ . L'ordre colex $<^{\text{colex}}$ de $A_{1}\times A_{2}\times \cdots \times A_{n}$ és:

(a_{1},a_{2},\dots ,a_{n})<^{\text{colex}}(b_{1},b_{2},\dots ,b_{n})\iff

(\exists \ m>0)\ (\forall \ i>m)(a_{i}=b_{i})\land (a_{m}<_{m}b_{m})

A continuació es presenta una ordenació sobre els subconjunts de 3 elements del conjunt $\{1,2,3,4,5,6\}$ , basada en l'ordenació colex de les ternes obtinguda escrivint els elements de cada subconjunt en ordre ascendent:

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

L'ordre colexicogràfic s'utilitza en el Teorema de Kruskal-Katona.

Ordre lexicogràfic invers

L'ordre lexicogràfic invers (o revlex) és una variació habitual de l'ordre lexicogràfic, on es comparen els elements de dreta a esquerra, és a dir, l'element més significatiu és el de la dreta. Un exemple d'ordre revlex és un diccionari de rimes.

En el cas de monomis, es poden ordenar els exponents de manera descendent, començant per la primera variable; per exemple:

x^{2}yz^{2}<xy^{3}z^{2}

Referències

↑ ^1,0 ^1,1 Harzheim, Egbert. Ordered Sets. Springer, 2006, p. 88–89. ISBN 978-0-387-24222-4.
↑ ^2,0 ^2,1 ^2,2 Baader, Franz; Nipkow, Tobias. Term Rewriting and All That. Cambridge University Press, 1999, p. 18-19. ISBN 978-0-521-77920-3.
↑ Calude, Cristian S. Information and randomness. An algorithmic perspective. Springer-Verlag, 1994, p. 1 (EATCS Monographs on Theoretical Computer Science). ZBL 0922.68073. ISBN 3-540-57456-5.
↑ Weispfenning, Volker «Admissible Orders and Linear Forms». SIGSAM Bulletin. ACM [New York, NY, USA], 21, 2, maig 1987, pàg. 16–18. DOI: 10.1145/24554.24557.

Vegeu també

[Harzheim-1] 1,0 ^1,1 Harzheim, Egbert. Ordered Sets. Springer, 2006, p. 88–89. ISBN 978-0-387-24222-4.

[BaaderNipkow1999-2] 2,0 ^2,1 ^2,2 Baader, Franz; Nipkow, Tobias. Term Rewriting and All That. Cambridge University Press, 1999, p. 18-19. ISBN 978-0-521-77920-3.

[3] Calude, Cristian S. Information and randomness. An algorithmic perspective. Springer-Verlag, 1994, p. 1 (EATCS Monographs on Theoretical Computer Science). ZBL 0922.68073. ISBN 3-540-57456-5.

[4] Weispfenning, Volker «Admissible Orders and Linear Forms». SIGSAM Bulletin. ACM [New York, NY, USA], 21, 2, maig 1987, pàg. 16–18. DOI: 10.1145/24554.24557.

[1]

[2]

[3]

[4]