Лексикографічний порядок

Лексикографічний порядок — відношення лінійного порядку на множині кортежів ${\displaystyle \Sigma ^{*}}$; ${\displaystyle \Sigma }$ — упорядкований алфавіт. Свою назву лексикографічний порядок отримав по аналогії з сортуванням по алфавіту в словнику.

Нехай у списку букв алфавіту ${\displaystyle \Sigma }$ порядок букв фіксований, тобто завжди один і той самий. Тоді цей список визначає повне впорядкування букв, які назвемо відношення передування і позначимо ${\displaystyle <=}$ (${\displaystyle a_{i}<=a_{j}}$, якщо ${\displaystyle a_{i}}$ передує ${\displaystyle a_{j}}$ у списку букв). На основі відношення передування букв — будуємо відношення передування слів, визначене наступним чином: Нехай дано слова ${\displaystyle a_{1}=a_{11}...a_{1m}}$ та ${\displaystyle a_{2}=a_{21}...a_{2m}}$, тоді ${\displaystyle a_{1}<=a_{2}}$, якщо виконується перший або другий пункт.

1. ${\displaystyle a_{1}=\beta a_{i}g,a_{2}=\beta a_{j}d}$ та ${\displaystyle a_{i}<=a_{j}}$ (β, g, d — деякі слова, можливо, порожні, ${\displaystyle a_{i}}$ та ${\displaystyle a_{j}}$ — букви)
2. ${\displaystyle a_{2}=a_{1}\beta }$, де β — непорожнє слово.

Це відношення задає повне впорядкування множин всіх кінцевих слів у алфавіті «${\displaystyle \Sigma }$», яке називається лексикографічним упорядкуванням слів.

Приклади

• Приклад лексикографічного упорядкування є упорядкування слів в словнику. Вважається, що букви можна порівнювати, порівнюючи їх номери в абетці. Тоді лексикографічний порядок — це, наприклад, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ, або А < АА < ААА < ААБ < ААВ < АБ < Б < … < ЯЯЯ.

Ліс <= літо (випадок — 1 визначення: β = лі, с <= т, g — пусто; d = о), тому слово «ліс» розташоване в словнику раніше слова «літо», ліс <= лісовик (випадок — 2 визначення: β = овик).

• Якщо розглянути числа в позиційних системах числення (наприклад, у двійковій або десятковій системі) як слова в алфавіті цифр, то їх лексикографічний порядок збігається із звичайним, якщо всі числа, які порівнюємо мають однакове число розрядів. У загальному випадку ці два види упорядкування можуть не збігатися: наприклад, 10<1073 і 20<1073, але 10 <= 1073, а 20 =>1073. Для того щоб вони збігалися необхідно вирівняти число розрядів у всіх чисел, які порівнюємо, дописуючи зліва нулі. У наведеному прикладі отримаємо 0020 <= 1073. Таке вирівнювання автоматично відбувається при запису цілих чисел в ЕОМ. Послідовність чисел у будь-якій системі числення, записаних у фіксованій розрядній сітці (000, 001, 002, 003, 004, 005, …, 999).

• Лексикографічне упорядкування для дат виду 06.09.99 (шосте вересня 1999 року) не збігається з природним упорядкуванням дат від ранніх до пізніх, наприклад 06.09.99 лексикографічно «більше» п'ятого числа будь-якого місяця другого року. Щоб зростання дат збігалося з лексикографічним упорядкуванням, цифри потрібно виставити в такому порядку рік, потім місяць, потім день: 99.09.06. Цей аспект врахований в форматі ISO 8601.

Див. також

• Лінійно впорядкована множина
• Система числення