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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
Слова записаны в лексикографическом порядке, если для любых <tex> ~i < ~j </tex> выполняется неравенство <tex> ~S_i < ~S_j </tex>, где <tex> ~S_i </tex> и <tex> ~S_j </tex> слова с номерами <tex> ~i </tex> и <tex> ~j </tex>.
+
Слова записаны в лексикографическом порядке, если для любых <tex> i<j </tex> выполняется неравенство <tex> S_i<S_j </tex>, где <tex> S_i </tex> и <tex> S_j </tex> слова с номерами <tex> i </tex> и <tex> j </tex>.
 
 
Что же значит, что слово <tex> ~A </tex> меньше слова <tex> ~B </tex>, и как вообще можно сравнивать слова?
 
  
 
Говорят, что слово <tex> ~A </tex> меньше слова <tex> ~B </tex>, если:
 
Говорят, что слово <tex> ~A </tex> меньше слова <tex> ~B </tex>, если:
Строка 8: Строка 6:
 
1. Слово <tex> ~A </tex> является префиксом слова <tex> ~B </tex>
 
1. Слово <tex> ~A </tex> является префиксом слова <tex> ~B </tex>
  
2. Ни одно из слов не является префиксом другого, но существует <tex> i </tex>  <tex> \ge 0 </tex> такое, что для всех <tex> j < i </tex> выполнено неравенство <tex> A_j = B_j </tex>, а <tex> A_i < B_i </tex>. Элементы слова мы можем сравнивать, так как это элементы алфавита, а на алфавите задан строгий порядок.
+
2. Cуществует <tex> i </tex>  <tex> \ge 0 </tex> такое, что для всех <tex> j < i </tex> выполнено неравенство <tex> A_j = B_j </tex>, а <tex> A_i < B_i </tex>. Элементы слова мы можем сравнивать, так как это элементы алфавита, а на алфавите задан строгий порядок.
  
 
Приведем псевдокод сравнения слов:
 
Приведем псевдокод сравнения слов:

Версия 06:54, 19 ноября 2011

Определение

Слова записаны в лексикографическом порядке, если для любых [math] i\lt j [/math] выполняется неравенство [math] S_i\lt S_j [/math], где [math] S_i [/math] и [math] S_j [/math] слова с номерами [math] i [/math] и [math] j [/math].

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

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

2. Cуществует [math] 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. Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ.
  3. Эти слова тоже записаны в лексикографическом порядке: азбука, бог, борода, сон, сонный.