Сортировка — это сборка письменной информации в стандартном порядке. Многие системы сопоставления основаны на числовом порядке или алфавитном порядке , а также на их расширениях и комбинациях. Сортировка является фундаментальным элементом большинства офисных систем хранения документов , библиотечных каталогов и справочников .
Параметры сортировки отличаются от классификации тем, что сами классы не обязательно упорядочены. Однако даже если порядок классов не имеет значения, идентификаторы классов могут быть членами упорядоченного набора, что позволяет алгоритму сортировки упорядочить элементы по классам.
Формально говоря, метод сопоставления обычно определяет общий порядок набора возможных идентификаторов, называемых ключами сортировки, что, следовательно, создает общий предварительный порядок набора элементов информации (элементы с одним и тем же идентификатором не размещаются в каком-либо определенном порядке).
Алгоритм сопоставления, такой как алгоритм сопоставления Unicode, определяет порядок посредством сравнения двух заданных строк символов и принятия решения, какая из них должна идти раньше другой. Если порядок определен таким образом, можно использовать алгоритм сортировки для помещения в этот порядок списка любого количества элементов.
Основное преимущество сопоставления заключается в том, что оно позволяет пользователю быстро и легко найти элемент в списке или подтвердить его отсутствие в списке. В автоматических системах это можно сделать с помощью алгоритма двоичного поиска или интерполяционного поиска ; Ручной поиск может быть выполнен с использованием примерно аналогичной процедуры, хотя часто это делается неосознанно. Другие преимущества заключаются в том, что можно легко найти первый или последний элемент в списке (скорее всего, это будет полезно в случае числовых данных) или элементы в заданном диапазоне (опять же полезно в случае числовых данных, а также с данные в алфавитном порядке, когда можно быть уверенным только в первых нескольких буквах искомого предмета или предметов).
Строки, представляющие числа, можно сортировать на основе значений чисел, которые они представляют. Например, «−4», «2,5», «10», «89», «30 000». Чистое применение этого метода может обеспечить лишь частичный порядок строк, поскольку разные строки могут представлять одно и то же число (например, «2» и «2.0» или, когда используется экспоненциальная запись , «2e3» и «2000»).
Аналогичный подход можно применить к строкам, представляющим даты или другие элементы, которые можно упорядочить в хронологическом порядке или каким-либо другим естественным образом.
Алфавитный порядок является основой многих систем сопоставления, в которых элементы информации идентифицируются строками, состоящими в основном из букв алфавита . Порядок строк зависит от существования стандартного порядка букв рассматриваемого алфавита. (Система не ограничивается алфавитами в строгом техническом смысле; языки, в которых используется слоговое письмо или абугида , например чероки , могут использовать тот же принцип упорядочения, при условии, что существует установленный порядок используемых символов.)
Чтобы решить, какая из двух строк стоит первой в алфавитном порядке, сначала сравниваются их первые буквы. Строка, первая буква которой встречается раньше в алфавите, стоит первой в алфавитном порядке. Если первые буквы одинаковые, то сравниваются вторые буквы и так далее, пока порядок не будет определен. (Если в одной строке заканчиваются буквы для сравнения, то она считается первой; например, «телега» стоит перед «тележной лошадью».) Результатом расположения набора строк в алфавитном порядке является то, что слова с одинаковым первым словом буквы группируются вместе, а внутри такой группы группируются слова с одинаковыми первыми двумя буквами и так далее.
Заглавные буквы обычно рассматриваются как эквиваленты соответствующих им строчных букв. (Информацию об альтернативных методах обработки в компьютеризированных системах см. в разделе «Автоматическая сортировка» ниже.)
При использовании алфавитного порядка могут применяться определенные ограничения, сложности и специальные соглашения:
В некоторых языках правила со временем изменились, поэтому в старых словарях может использоваться другой порядок, чем в современных. Кроме того, сортировка может зависеть от использования. Например, в немецких словарях и телефонных справочниках используются разные подходы.
Некоторые арабские словари, такие как двуязычный « Словарь современного письменного арабского языка» Ганса Вера , группируют и сортируют арабские слова по семитическому корню . [1] Например, слова китаба ( كتابة «письмо»), китаб ( كتاب «книга»), катиб ( كاتب «писатель»), мактаба ( مكتبة «библиотека»), мактаб ( مكتب «офис»), мактуб ( مكتوب «судьба» или «написанный») объединяются под трехбуквенным корнем k - t - b ( ك ت ب ), который означает «письмо». [2]
Другой формой сопоставления является сортировка по радикалам и штрихам , используемая для неалфавитных систем письма, таких как ханзи в китайском языке и кандзи в японском языке , тысячи символов которых не поддаются упорядочиванию по соглашению. В этой системе выявляются общие компоненты персонажей; на китайском языке они называются радикалами , а логографические системы происходят от китайского языка. Затем символы группируются по их основному радикалу, а затем упорядочиваются по количеству штрихов пера внутри радикалов. Когда нет очевидного радикала или более одного радикала, определяющим является соглашение, которое используется для сопоставления. Например, китайский иероглиф 妈 (означающий «мать») сортируется как шестистрочный иероглиф под трехстрочным основным радикалом 女.
Радикально-штриховая система громоздка по сравнению с алфавитной системой, в которой есть несколько символов, и все они однозначны. Выбор того, какие компоненты логограммы составляют отдельные радикалы и какой радикал является первичным, не однозначен. В результате логографические языки часто дополняют радикально-штриховой порядок алфавитной сортировкой фонетического преобразования логографов. Например, кандзи-слово Tōkyō (東京) можно отсортировать так, как если бы оно было написано японскими иероглифами слогового алфавита хираганы как «то-у-ки- йо -у» (とうきょう), используя обычный порядок сортировки для этих слов. персонажи. [ нужна цитата ]
Кроме того, китайские иероглифы также можно сортировать по штрихам . В Большом Китае порядок написания фамилий является соглашением в некоторых официальных документах, где имена людей перечисляются без иерархии.
Когда информация хранится в цифровых системах, сопоставление может стать автоматизированным процессом. Затем необходимо реализовать соответствующий алгоритм сопоставления , который позволит сортировать информацию удовлетворительным образом для рассматриваемого приложения. Часто целью является достижение алфавитного или числового порядка, который соответствует стандартным критериям, описанным в предыдущих разделах. Однако не все эти критерии легко автоматизировать. [3]
Самый простой вид автоматической сортировки основан на числовых кодах символов в наборе символов , таком как кодировка ASCII (или любой из ее надмножеств , таких как Unicode ), при этом символы упорядочиваются в возрастающем числовом порядке их кодов, и это упорядочение распространяется на строки в соответствии с основными принципами алфавитного упорядочения (математически говоря, лексикографического упорядочения ). Таким образом, компьютерная программа может обрабатывать символы a , b , C , d и $ как упорядоченные $ , C , a , b , d (соответствующие коды ASCII: $ = 36, a = 97, b = 98, C = 67 и d = 100). Таким образом, строки, начинающиеся с C , M или Z, будут сортироваться перед строками с строчными буквами a , b и т. д. Иногда это называется ASCIIbetical order . Это отличается от стандартного алфавитного порядка, особенно из-за расположения заглавных букв перед всеми строчными (и, возможно, обработки пробелов и других небуквенных символов). Поэтому он часто применяется с определенными изменениями, наиболее очевидным из которых является преобразование регистра (часто в верхний регистр по историческим причинам [примечание 1] ) перед сравнением значений ASCII.
Во многих алгоритмах сопоставления сравнение основано не на числовых кодах символов, а на основе последовательности сопоставления (последовательности, в которой предполагается, что символы находятся в целях сопоставления), а также других правил упорядочивания, соответствующих данное приложение. Это может послужить для применения правильных соглашений, используемых для алфавитного порядка на рассматриваемом языке, правильной работы с буквами с разными регистрами, измененными буквами , орграфами , конкретными сокращениями и т. д., как упомянуто выше в разделе «Алфавитный порядок» и подробно в разделе «Алфавитный порядок». заказать статью. Такие алгоритмы потенциально довольно сложны и, возможно, требуют нескольких проходов по тексту. [3]
Тем не менее, проблемы все еще распространены, когда алгоритм должен охватывать более одного языка. Например, в немецких словарях слово ökonomisch стоит между offenbar и olfaktorisch , в то время как турецкие словари рассматривают o и ö как разные буквы, помещая oyun перед öbür .
Стандартным алгоритмом сопоставления любого набора строк, состоящих из любых стандартных символов Юникода, является алгоритм сопоставления Юникода . Это можно адаптировать для использования соответствующей последовательности сопоставления для данного языка, настроив его таблицу сопоставления по умолчанию. Несколько таких доработок собраны в Common Locale Data Repository .
В некоторых приложениях строки, по которым сопоставляются элементы, могут отличаться от отображаемых идентификаторов. Например, The Shining можно отсортировать как Shining, The (см. Алфавитный порядок выше), но все равно может потребоваться отобразить его как The Shining . В этом случае можно сохранить два набора строк: один для отображения, а другой для сопоставления. Строки, используемые для сопоставления таким образом, называются ключами сортировки .
Иногда желательно упорядочить текст со встроенными числами, используя правильный числовой порядок. Например, «Рисунок 7b» идет перед «Рисунком 11a», хотя в Unicode «7» идет после «1» . Это можно распространить на римские цифры . Такое поведение не особенно сложно реализовать, пока сортируются только целые числа, хотя оно может значительно замедлить сортировку. Например, Microsoft Windows делает это при сортировке имен файлов .
Правильная сортировка десятичных дробей немного сложнее, поскольку в разных локалях используются разные символы для десятичной точки , а иногда один и тот же символ, используемый в качестве десятичной точки, также используется в качестве разделителя, например «Раздел 3.2.5». Не существует универсального ответа на вопрос, как сортировать такие строки; любые правила зависят от приложения.
В некоторых контекстах цифры и буквы используются не столько как основа для установления порядка, сколько как средство маркировки уже заказанных товаров. Например, таким способом часто «нумеруются» страницы, разделы, главы и т.п., а также элементы списков. Серии маркировки, которые можно использовать, включают обычные арабские цифры (1, 2, 3, ...), римские цифры (I, II, III, ... или i, ii, iii, ...) или буквы (A , B, C, ... или a, b, c, ...). (Альтернативный метод обозначения элементов списка без их нумерации — использование маркированного списка .)
Когда для целей нумерации используются буквы алфавита , существуют определенные языковые соглашения относительно того, какие буквы используются. Например, опускаются русские буквы Ъ и Ь (которые на письме используются только для изменения предшествующей согласной ), а также обычно также Ы , Й и Ё. Кроме того, во многих языках, использующих расширенную латиницу , измененные буквы часто не используются при перечислении.