Лексикографический порядок — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
(Определение)
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
Пусть дано линейно упорядоченное множество <tex>~E=\{e_1<e_2<e_3<...<e_k\}</tex> {{---}} алфавит. Словом назовем упорядоченное множество <tex> ~S </tex>  элементов алфавита <tex> ~A </tex>. Тогда если на алфавите <tex> A </tex> задан порядок, то порядок задан и на слове <tex> ~S </tex>. Тогда говорят, что множество слов <tex> ~A </tex> задано в лекcикографическом порядке, если для <tex>\forall i \in A </tex> <tex>\forall j \in A </tex> таких, что <tex> i < j </tex> выполнено, что слово <tex> ~A_i </tex> меньше, чем слово <tex> ~A_j </tex>.
+
Пусть дано линейно упорядоченное множество <tex>~E=\{e_1<e_2<e_3<...<e_k\}</tex> {{---}} алфавит. Словом назовем упорядоченное множество <tex> ~S </tex>  элементов алфавита <tex> ~A </tex>. Тогда если на алфавите <tex> A </tex> задан порядок, то порядок задан и на слове <tex> ~S </tex>. Тогда говорят, что множество слов <tex> ~A </tex> задано в лекcикографическом порядке, если для любого <tex> i \in A </tex> и любого <tex> j \in A </tex> таких, что <tex> i < j </tex> выполнено, что слово <tex> ~A_i </tex> меньше, чем слово <tex> ~A_j </tex>.
  
 
Рассмотрим сравнение объектов, состоящих из элементов, на которых задан порядок. Если нам даны два объекта <tex> ~P </tex> и <tex> ~Q </tex>, то <tex> ~P </tex> меньше, чем <tex> ~Q </tex>, если объект <tex> ~P </tex> является префиксом <tex> ~Q </tex>, либо если первые <tex> ~i </tex> элементов объектов совпадают, а <tex> ~P_i < ~Q_i </tex>.
 
Рассмотрим сравнение объектов, состоящих из элементов, на которых задан порядок. Если нам даны два объекта <tex> ~P </tex> и <tex> ~Q </tex>, то <tex> ~P </tex> меньше, чем <tex> ~Q </tex>, если объект <tex> ~P </tex> является префиксом <tex> ~Q </tex>, либо если первые <tex> ~i </tex> элементов объектов совпадают, а <tex> ~P_i < ~Q_i </tex>.

Версия 07:23, 18 ноября 2011

Определение

Пусть дано линейно упорядоченное множество [math]~E=\{e_1\lt e_2\lt e_3\lt ...\lt e_k\}[/math] — алфавит. Словом назовем упорядоченное множество [math] ~S [/math] элементов алфавита [math] ~A [/math]. Тогда если на алфавите [math] A [/math] задан порядок, то порядок задан и на слове [math] ~S [/math]. Тогда говорят, что множество слов [math] ~A [/math] задано в лекcикографическом порядке, если для любого [math] i \in A [/math] и любого [math] j \in A [/math] таких, что [math] i \lt j [/math] выполнено, что слово [math] ~A_i [/math] меньше, чем слово [math] ~A_j [/math].

Рассмотрим сравнение объектов, состоящих из элементов, на которых задан порядок. Если нам даны два объекта [math] ~P [/math] и [math] ~Q [/math], то [math] ~P [/math] меньше, чем [math] ~Q [/math], если объект [math] ~P [/math] является префиксом [math] ~Q [/math], либо если первые [math] ~i [/math] элементов объектов совпадают, а [math] ~P_i \lt ~Q_i [/math].

Сравнение слов

Что же значит, что слово [math] ~A [/math] меньше слова [math] ~B [/math], и как вообще можно сравнивать слова?

Говорят, что слово [math] ~A [/math] меньше слова [math] ~B [/math], если:

1. Слово [math] ~A [/math] является префиксом слова [math] ~B [/math]

2. Ни одно из слов не является префиксом другого, но [math]\exists i [/math] [math] \ge 0 [/math] такое, что для всех [math] j \lt i [/math] выполнено неравенство [math] A_j = B_j [/math], а [math] A_i \lt B_i [/math]. Элементы слова мы можем сравнивать, так как это элементы алфавита, а на алфавите задан строгий порядок.

Приведем псевдокод сравнения слов:

function isEqual(A, B : string)
   for i = 0 .. min(len(A), len(B)) - 1 //Длины равны, строки нумеруются с ноля
        if (A[i] < B[i])
            return <
        if (A[i] > B[i])
            return >
    //Одна из строк является префиксом другой
    if (len(A) < len(B))
        return <
    if (len(A) > len(B))
        return >
    return = //Длины строк и все символы равны


Примеры

  1. Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999).
  2. Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ.