Лексикографический порядок — различия между версиями
(→Сравнение слов) |
(→Сравнение слов) |
||
Строка 11: | Строка 11: | ||
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. Ни одно из слов не является префиксом другого, но существует <tex> i </tex> <tex> \ge 0 </tex> такое, что для всех <tex> j < i </tex> выполнено неравенство <tex> A_j = B_j </tex>, а <tex> A_i < B_i </tex>. Элементы слова мы можем сравнивать, так как это элементы алфавита, а на алфавите задан строгий порядок. |
Приведем псевдокод сравнения слов: | Приведем псевдокод сравнения слов: |
Версия 07:24, 18 ноября 2011
Определение
Пусть дано линейно упорядоченное множество
— алфавит. Словом назовем упорядоченное множество элементов алфавита . Тогда если на алфавите задан порядок, то порядок задан и на слове . Тогда говорят, что множество слов задано в лекcикографическом порядке, если для любого и любого таких, что выполнено, что слово меньше, чем слово .Рассмотрим сравнение объектов, состоящих из элементов, на которых задан порядок. Если нам даны два объекта
и , то меньше, чем , если объект является префиксом , либо если первые элементов объектов совпадают, а .Сравнение слов
Что же значит, что слово
меньше слова , и как вообще можно сравнивать слова?Говорят, что слово
меньше слова , если:1. Слово
является префиксом слова2. Ни одно из слов не является префиксом другого, но существует
такое, что для всех выполнено неравенство , а . Элементы слова мы можем сравнивать, так как это элементы алфавита, а на алфавите задан строгий порядок.Приведем псевдокод сравнения слов:
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 = //Длины строк и все символы равны
Примеры
- Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999).
- Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ.