Сортировка — это сборка письменной информации в стандартном порядке. Многие системы сопоставления основаны на числовом порядке или алфавитном порядке , а также на их расширениях и комбинациях. Сортировка является фундаментальным элементом большинства офисных систем хранения документов , библиотечных каталогов и справочников .
Параметры сортировки отличаются от классификации тем, что сами классы не обязательно упорядочены. Однако даже если порядок классов не имеет значения, идентификаторы классов могут быть членами упорядоченного набора, что позволяет алгоритму сортировки упорядочить элементы по классам.
Формально говоря, метод сопоставления обычно определяет общий порядок набора возможных идентификаторов, называемых ключами сортировки, что, следовательно, создает общий предварительный порядок набора элементов информации (элементы с одним и тем же идентификатором не размещаются в каком-либо определенном порядке).
Алгоритм сопоставления, такой как алгоритм сопоставления Unicode, определяет порядок посредством сравнения двух заданных строк символов и принятия решения, какая из них должна идти раньше другой. Если порядок определен таким образом, можно использовать алгоритм сортировки для помещения в этот порядок списка любого количества элементов.
Основное преимущество сопоставления заключается в том, что оно позволяет пользователю быстро и легко найти элемент в списке или подтвердить его отсутствие в списке. В автоматических системах это можно сделать с помощью алгоритма двоичного поиска или интерполяционного поиска ; Ручной поиск может быть выполнен с использованием примерно аналогичной процедуры, хотя часто это делается неосознанно. Другие преимущества заключаются в том, что можно легко найти первый или последний элемент в списке (скорее всего, это будет полезно в случае числовых данных) или элементы в заданном диапазоне (опять же полезно в случае числовых данных, а также с данные в алфавитном порядке, когда можно быть уверенным только в первых нескольких буквах искомого предмета или предметов).
Строки, представляющие числа, можно сортировать на основе значений чисел, которые они представляют. Например, «−4», «2,5», «10», «89», «30 000». Чистое применение этого метода может обеспечить лишь частичный порядок строк, поскольку разные строки могут представлять одно и то же число (как в случае «2» и «2.0» или, когда используется экспоненциальная запись , «2e3» и «2000»).
Аналогичный подход можно применить к строкам, представляющим даты или другие элементы, которые можно упорядочить в хронологическом порядке или каким-либо другим естественным образом.
Алфавитный порядок является основой многих систем сопоставления, в которых элементы информации идентифицируются строками, состоящими в основном из букв алфавита . Порядок строк зависит от существования стандартного порядка букв рассматриваемого алфавита. (Система не ограничивается алфавитами в строгом техническом смысле; языки, в которых используется слоговое письмо или абугида , например чероки , могут использовать тот же принцип упорядочения, при условии, что существует установленный порядок используемых символов.)
Чтобы решить, какая из двух строк стоит первой в алфавитном порядке, сначала сравниваются их первые буквы. Строка, первая буква которой встречается раньше в алфавите, стоит первой в алфавитном порядке. Если первые буквы одинаковые, то сравниваются вторые буквы и так далее, пока порядок не будет определен. (Если в одной строке заканчиваются буквы для сравнения, то она считается первой; например, «телега» стоит перед «тележной лошадью».) Результатом расположения набора строк в алфавитном порядке является то, что слова с одинаковым первым словом буквы группируются вместе, а внутри такой группы группируются слова с одинаковыми первыми двумя буквами и так далее.
Заглавные буквы обычно рассматриваются как эквиваленты соответствующих им строчных букв. (Информацию об альтернативных методах обработки в компьютеризированных системах см. в разделе «Автоматическая сортировка» ниже.)
При использовании алфавитного порядка могут применяться определенные ограничения, сложности и специальные соглашения:
В некоторых языках правила со временем изменились, поэтому в старых словарях может использоваться другой порядок, чем в современных. Кроме того, сортировка может зависеть от использования. Например, в немецких словарях и телефонных справочниках используются разные подходы.
Некоторые арабские словари, такие как двуязычный «Словарь современного письменного арабского языка» Ганса Вера , группируют и сортируют арабские слова по семитическому корню . [1] Например, слова китаба ( كتابة «письмо»), китаб ( كتاب «книга»), катиб ( كاتب «писатель»), мактаба ( مكتبة «библиотека»), мактаб ( مكتب «офис»), мактуб ( مكتوب «судьба» или «написанный») объединяются под трехбуквенным корнем k - t - b ( ك ت ب ), который означает «письмо». [2]
Другой формой сопоставления является сортировка по радикалам и штрихам , используемая для неалфавитных систем письма, таких как ханзи в китайском языке и кандзи в японском языке , тысячи символов которых не поддаются упорядочиванию по соглашению. В этой системе выявляются общие компоненты персонажей; на китайском языке они называются радикалами , а логографические системы происходят от китайского языка. Затем символы группируются по их основному радикалу, а затем упорядочиваются по количеству штрихов пера внутри радикалов. Когда нет очевидного радикала или более одного радикала, определяющим является соглашение, которое используется для сопоставления. Например, китайский иероглиф 妈 (означающий «мать») сортируется как шестистрочный иероглиф под трехстрочным основным радикалом 女.
Радикально-штриховая система громоздка по сравнению с алфавитной системой, в которой есть несколько символов, и все они однозначны. Выбор того, какие компоненты логограммы составляют отдельные радикалы и какой радикал является первичным, не однозначен. В результате логографические языки часто дополняют радикально-штриховой порядок алфавитной сортировкой фонетического преобразования логографов. Например, кандзи-слово Tōkyō (東京) можно отсортировать так, как если бы оно было написано японскими иероглифами слогового алфавита хирагана как «то-у-ки- йо -у» (とうきょう), используя обычный порядок сортировки для этих слов. персонажи. [ нужна цитата ]
In addition, Chinese characters can also be sorted by stroke-based sorting. In Greater China, surname stroke ordering is a convention in some official documents where people's names are listed without hierarchy.
When information is stored in digital systems, collation may become an automated process. It is then necessary to implement an appropriate collation algorithm that allows the information to be sorted in a satisfactory manner for the application in question. Often the aim will be to achieve an alphabetical or numerical ordering that follows the standard criteria as described in the preceding sections. However, not all of these criteria are easy to automate.[3]
The simplest kind of automated collation is based on the numerical codes of the symbols in a character set, such as ASCII coding (or any of its supersets such as Unicode), with the symbols being ordered in increasing numerical order of their codes, and this ordering being extended to strings in accordance with the basic principles of alphabetical ordering (mathematically speaking, lexicographical ordering). So a computer program might treat the characters a, b, C, d, and $ as being ordered $, C, a, b, d (the corresponding ASCII codes are $ = 36, a = 97, b = 98, C = 67, and d = 100). Therefore, strings beginning with C, M, or Z would be sorted before strings with lower-case a, b, etc. This is sometimes called ASCIIbetical order. This deviates from the standard alphabetical order, particularly due to the ordering of capital letters before all lower-case ones (and possibly the treatment of spaces and other non-letter characters). It is therefore often applied with certain alterations, the most obvious being case conversion (often to uppercase, for historical reasons[note 1]) before comparison of ASCII values.
Во многих алгоритмах сопоставления сравнение основано не на числовых кодах символов, а на основе последовательности сопоставления (последовательности, в которой предполагается, что символы находятся в целях сопоставления), а также других правил упорядочивания, соответствующих данное приложение. Это может послужить для применения правильных соглашений, используемых для алфавитного порядка на рассматриваемом языке, правильной работы с буквами с разными регистрами, измененными буквами , орграфами , конкретными сокращениями и т. д., как упомянуто выше в разделе «Алфавитный порядок» и подробно в разделе «Алфавитный порядок» . заказать статью. Такие алгоритмы потенциально довольно сложны и, возможно, требуют нескольких проходов по тексту. [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, ...). (Альтернативный метод обозначения элементов списка без их нумерации — использование маркированного списка .)
Когда для целей перечисления используются буквы алфавита , существуют определенные языковые соглашения относительно того, какие буквы используются. Например, опускаются русские буквы Ъ и Ь (которые на письме используются только для изменения предшествующей согласной ), а также обычно также Ы , Й и Ё. Кроме того, во многих языках, использующих расширенную латиницу , измененные буквы часто не используются при перечислении.
