Войти
В математике, и особенно в теории формальных языков, shortlex - это общее упорядочение для конечных последовательностей объектов, которые сами могут быть полностью упорядочены. При упорядочивании коротких строк последовательности в первую очередь сортируются по мощности (длина), причем сначала самые короткие последовательности, а последовательности одинаковой длины сортируются в лексикографический порядок. Упорядочение коротких строк также называется основанием, лексикографической длиной, военным или генеалогическим порядком.
В контексте для строк в полностью упорядоченном алфавите, порядок коротких строк идентичен лексикографическому порядку, за исключением того, что более короткие строки предшествуют более длинным строкам. Например, порядок коротких строк набора строк в английском алфавите (в обычном порядке) равен [ε, a, b, c,..., z, aa, ab, ac,..., zz, aaa, aab, aac,..., zzz,...], где ε обозначает пустую строку.
Строки в этом порядке по фиксированному конечному алфавиту могут быть помещены во взаимно однозначный порядок с сохранением порядка соответствие с неотрицательными целыми числами, дающее биективную систему нумерации для представления чисел. Упорядочение коротких строк также важно в теории автоматических групп.
.
