Download presentation
Presentation is loading. Please wait.
1
Lexicographical order VS canonical order
凌弘毅
2
这个序和字典序的区别在哪里？ 问题：如何利用这个形式体系来定义字典序？
3
Lexicographical order
Consider a finite set A, often called alphabet, which is totally ordered. The lexicographic order is a total order on the sequences of elements of A, often called words on A, which is defined as follows. Given two different sequences of the same length, a1a2...ak and b1b2...bk, the first one is smaller than the second one for the lexicographical order, if ai<bi (for the order of A), for the first i where ai and bi differ. To compare sequences of different lengths, the shorter sequence is usually padded at the end with enough "blanks"
4
Difference 当两个word的长度相同的时候, Lexicographical order 和 canonical order 是一样的。 当两个word长度不同的时候, 判断方式不一样。
5
example Apple , zoo Lexicographical order：apple < zoo
canonical order : zoo < apple
6
Definition for Lexicographical order
7
Thank you
Similar presentations
