Кіріспе

Математикада лексикографиялық немесе лексикографиялық тәртіп (кейде тексекалық тәртіп, немесе сөздік тәртібі деп те аталады) – сөздіктердегі әріптік реттің ретті символдар тізбегіне немесе, жалпы алғанда, толық реттелген жиынның элементтеріне кеңейтілген түрі. Лексикографиялық тәртіптің бірнеше түрі мен кеңейтілген нұсқалары бар. Бір түрі әртүрлі ұзындықтағы тізбектерді олардың элементтерін салыстыру алдында ұзындығы бойынша салыстыру арқылы қолданылады. Комбинаторикада кеңінен қолданылатын тағы бір түрі, берілген шекті жиынның ішкі жиындықтарын осы жиынға толық тәртіп беру арқылы және лексикографиялық тәртіп қолданылатын өсу тізбектеріне айналдыру арқылы реттейді. Кеңейтілген түрі жартылай реттелген жиынтықтардың n-арлық Картезиан көбейтіндісінде тәртіпті анықтайды; бұл тәртіп толық тәртіп болады, егер және тек қана Картезиан көбейтіндісінің барлық факторлары толық реттелген болса.

Анықтама

Лексикадағы сөздер (бір тілде қолданылатын сөздер жиынтығы) сөздіктер мен энциклопедияларда қолданылатын, сөздерді құруға қолданылатын символдардың алфавиттік ретіне байланысты белгілі бір ретпен орналасады. Лексикографиялық тәртіп – негізгі символдардың ретін ескере отырып, сөздердің ретін формалдаудың бір жолы. Бұл формальды ұғым шекті жиынтық А-дан басталады, ол көбінесе әліпби деп аталады, және толығымен реттелген. Яғни, A жиынтығындағы кез келген екі символ a және b бір-бірінен өзгеше болса, a < b немесе b < a болады. А әліпбиінің сөздері – A жиынтығынан алынған символдардың шекті тізбектері, оның ішінде бір символдан тұратын 1 ұзындығы бар сөздер, 2 символдан тұратын 2 ұзындығы бар сөздер және т.б., тіпті символдардан құралмаған бос тізбек те кіреді. Осы шекті сөздер жиынтығындағы лексикографиялық тәртіп сөздерді келесідей реттейді:

Егер екі сөз бірдей ұзындықта болса, мысалы және , онда екі сөздің реті алғашқы орындағы символдардың әліпбилік ретіне байланысты, яғни екі сөздің айырмашылығы басталатын i орнынан санап (сөздердің басынан бастап): a < b егер және тек қана ai < bi болса, бұл алфавит А-ның негізгі ретінде қарастырылады. Егер екі сөздің ұзындығы әр түрлі болса, дәстүрлі лексикографиялық тәртіпте қысқарақ сөз соңына "бос символдармен" (А жиынтығының кез келген элементінен кішірек саналатын арнайы символ) толықтырылады, осылайша екі сөздің ұзындығы теңестіріледі, содан кейін сөздер бұрынғыдай салыстырылады. Дегенмен, комбинаторикада екінші жағдай үшін басқа бір конвенция жиі қолданылады, онда қысқа тізбек әрқашан ұзын тізбектен кіші болып есептеледі. Лексикографиялық тәртіптің осы түрі кейде shortlex тәртібі деп аталады. Лексикографиялық тәртіп бойынша "Томас" сөзі "Томпсон" сөзінен бұрын келеді, себебі олар бірінші рет бесінші әріпте ('а' және 'p') айырмашылыққа ие, ал 'а' әрпі әліпбиде 'p' әрпінен бұрын тұрады. Бұл алғашқы айырмашылық болғандықтан, осы жағдайда 5-ші әріп әліпбилік реттелу үшін "ең маңызды айырмашылық" болып табылады. Лексикографиялық тәртіптің маңызды қасиеті – әр n үшін n ұзындығы бар сөздер жиынтығы лексикографиялық тәртіп бойынша жақсы реттелген (әліпби шекті болған жағдайда); яғни, n ұзындығы бар сөздердің кез келген кемітетін тізбегі шекті (немесе, эквивалентті түрде, кез келген бос емес ішкі жиынтықта ең кішкентай элемент болады). Барлық шекті сөздер жиынтығы жақсы реттелген деген тұжырым дұрыс емес; мысалы, {b, ab, aab, aaab, …} сөздерінің шексіз жиынтығы лексикографиялық тұрғыдан ең ерте элементке ие емес.

Сандық жүйелер мен даталар

Лексикографиялық тәртіп тек сөздіктерде ғана емес, сонымен қатар сандар мен күндер үшін де қолданылады. Римдік сандар жүйесінің бір кемшілігі – екі санның қайсысы кішкенерек екенін бірден анықтау қиын болуы мүмкін. Ал индус-араб сандық жүйесінің позициялық жазуында сандарды салыстыру оңай, себебі табиғи сандардағы табиғи рет, лексикографиялық тәртіптің shortlex түрімен бірдей. Шындығында, позициялық жазуда табиғи сан, сандық таңбалардың тізбегі арқылы бейнеленеді, және бір табиғи сан, егер оның таңбалары көп болса (бастапқы нөлдерді ескермейтін болса) немесе таңбалар саны бірдей болса, бірақ алғашқы (ең маңызды) ерекшеленетін таңбасы үлкен болса, басқасынан үлкен болады. Ондық нотацияда жазылған нақты сандар үшін лексикографиялық тәртіптің сәл өзгеше түрі қолданылады: ондық үтірден сол жақтағы бөліктер бұрынғыдай салыстырылады; егер олар тең болса, онда ондық үтірден оң жақтағы бөліктер лексикографиялық тәртіп бойынша салыстырылады. Бұл жағдайда, «толтыру» символы – соңғы «0» таңбасы. Теріс сандарды да ескергенде, теріс сандарды салыстыру ретін кері қайтару қажет. Бұл әдетте адамдар үшін қиындық тудырмайды, бірақ компьютерлер үшін тудыруы мүмкін (таңбаны тексеруге біраз уақыт кетеді). Осы себепті компьютерлерде сақталатын бүтін сандарды көрсету үшін екілік толықтыру тәсілі қолданылады. Лексикографиялық ретке келтірудің сөздікке жатпайтын тағы бір мысалы – ISO 8601 күндер стандарты, ол күнді YYYY MM DD түрінде көрсетеді. Бұл форматтаудың артықшылығы – күндерді көрсететін таңбалар тізбегінің лексикографиялық реті, хронологиялық ретпен сәйкес келеді: біздің заманымыздың (CE) ертерек күні, 9999 жылға дейінгі кейінгі күнден лексикографиялық тәртіп бойынша кішірек болады. Бұл күндерді реттеу, жеке реттеу алгоритміне қажеттілікті жойып, компьютерлік реттеуді жеңілдетеді.