Вікіпедія

Лексикографічний порядок: відмінності між версіями

Інтерактивний перегляд історії
[неперевірена версія][неперевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
Немає опису редагування
Немає опису редагування
Рядок 1:
'''Лексикографічний порядок''' &nbsp;— [[Лінійно впорядкована множина|відношення лінійного порядку]] на множині [[кортеж]]ей <math>\Sigma^*</math>; <math>\Sigma</math> &nbsp;— упорядкований алфавіт. Свою назву лексикографічний порядок отримав по аналогії з сортуванням по [[абетка|алфавіталфавіту]]у в [[словник|словнику]]у.
 
Нехай у списку букв алфавіту ''<math>\Sigma</math>'' порядок букв фіксований, тобто завжди один і той самий. Тоді цей список визначає повне упорядоченнявпорядкування букв, які назвемо відношення передування і позначимо <math> <= </math> ( <math> a_i <= a_j </math>, якщо <math> a_i </math> передує <math> a_j </math> у списку букв ). На основі відношення передування букв - будуємо відношення передування слів, визначене наступним чином:▼
На основі відношення передування букв&nbsp;— будуємо відношення передування слів, визначене наступним чином:
Нехай дано слова a_1<math> a_{1} = a_11a_{11} …... a_1ma_{1m} </math> та a_2<math> a_{2} = a_21a_{21} …... a_2ma_{2m} </math>, тоді <math> a_1 <= a_2 </math>, якщо виконується перший або другий пункт.▼
1)#<math> a_1 = βba_{i} a_ig g, a_2 = βa_j ka_{j}d та </math> a_iта </math> a_{i} <= <math> a_ja_{j} </math> (b (β, g , d –k&nbsp;— деякі слова, можливо, пусті, <math> a_i a_{i}</math> та <math> a_ja_{j} </math> –&nbsp;— букви), або▼
#<math> a_2 = a_{1}b</math>, де b - не порожнє слово.
2) a_2 = a_1 β, де β – не порожнє слово. Це відношення задає повне впорядкування множин всіх кінцевих слів у алфавіті ''"<math>\Sigma</math>''", яке називається лексикографічним упорядкуванням слів. ▼
 
▲Нехай у списку букв алфавіту ''<math>\Sigma</math>'' порядок букв фіксований, тобто завжди один і той самий. Тоді цей список визначає повне упорядочення букв, які назвемо відношення передування і позначимо <math> <= </math> ( <math> a_i <= a_j </math>, якщо <math> a_i </math> передує <math> a_j </math> у списку букв ). На основі відношення передування букв - будуємо відношення передування слів, визначене наступним чином:
▲Нехай дано слова a_1 = a_11 … a_1m та a_2 = a_21 … a_2m, тоді <math> a_1 <= a_2 </math>, якщо
▲ 1) a_1 = β a_i g, a_2 = βa_j d та <math> a_i </math> <= <math> a_j </math> (β, g, d – деякі слова, можливо, пусті, <math> a_i </math> та <math> a_j </math> – букви), або
▲ 2) a_2 = a_1 β, де β – не порожнє слово. Це відношення задає повне впорядкування множин всіх кінцевих слів у алфавіті ''<math>\Sigma</math>'', яке називається лексикографічним упорядкуванням слів.
 
== Приклади ==
 
*приклад Приклад лексикографічного упорядкування є упорядкування [[слово|слів]] в [[словник|словнику]]у. Вважається, що [[буква|букви]] можна порівнювати, порівнюючи їх номери в [[абетка|абетці]]. Тоді лексикографічний порядок&nbsp;— це, наприклад, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ, або А < АА < ААА < ААБ < ААВ < АБ < Б < … < ЯЯЯ. Ліс <= літо (випадок 1 визначення: β = лі, с <= т, g – пусто; d = о), тому слово «ліс» розташоване в словнику раніше слова «літо», ліс <= лісовик (випадок 2 визначення: β = овик).
*Якщо розглянути числа в [[Позиційні системи числення|позиційних системах числення]] (наприклад, у двійковій або десятковій системі) як слова в алфавіті цифр, то їх лексикографічний порядок співпадає із звичайним, якщо всі числа, які порівнюємо мають однакове число розрядів. У загальному випадку ці два вида упорядкування можуть не співпадати: наприклад, 10<1073 і 20<1073, але 10 <= 1073, а 20 =>1073. Для того щоб вони співпали необхідно вирівняти число розрядів у всіх чисел, які порівнюємо, дописуючи зліва нулі. У наведенному прикладі отримаємо 0020 <= 1073. Таке вирівнювання автоматично відбувається при запису цілих чисел в ЕОМ. Послідовність [[число|чисел]] в будь-якій [[система числення|системі числення]], записаних в фіксованій розрядній сітці (000, 001, 002, 003, 004, 005, …, 999). ▼
Ліс <= літо (випадок - 1 визначення: β = лі, с <= т, g&nbsp;— пусто; d = о), тому слово «ліс» розташоване в словнику раніше слова «літо», ліс <= лісовик (випадок - 2 визначення: β = овик).
*Лексикографічне упорядкування для чисел виду 06.09.99 (шосте вересня 1999 року) не співпадає природнім упорядкуванням дат від ранніх до пізніх, наприклад 06.09.99 лексикографічно «старше» третього числа любого місяця другого року. Щоб зростання дат співпадало з лексикографічним упорядкуванням, зазвичай цифри потрібно «перевернути» тобто рік помістити зліва: 99.09.06.▼
 
▲* Якщо розглянути числа в [[Позиційні системи числення|позиційних системах числення]] (наприклад, у двійковій або десятковій системі) як слова в алфавіті цифр, то їх лексикографічний порядок співпадає із звичайним, якщо всі числа, які порівнюємо мають однакове число розрядів. У загальному випадку ці два вида упорядкування можуть не співпадати: наприклад, 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.
 
 
== Див. також ==
Отримано з https://uk.wikipedia.org/wiki/Лексикографічний_порядок