Сортировка

Сортировка — это сборка письменной информации в стандартном порядке. Многие системы сопоставления основаны на числовом порядке или алфавитном порядке , а также на их расширениях и комбинациях. Сортировка является фундаментальным элементом большинства офисных систем хранения документов , библиотечных каталогов и справочников .

Параметры сортировки отличаются от классификации тем, что сами классы не обязательно упорядочены. Однако даже если порядок классов не имеет значения, идентификаторы классов могут быть членами упорядоченного набора, что позволяет алгоритму сортировки упорядочить элементы по классам.

Формально говоря, метод сопоставления обычно определяет общий порядок набора возможных идентификаторов, называемых ключами сортировки, что, следовательно, создает общий предварительный порядок набора элементов информации (элементы с одним и тем же идентификатором не размещаются в каком-либо определенном порядке).

Алгоритм сопоставления, такой как алгоритм сопоставления Unicode, определяет порядок посредством сравнения двух заданных строк символов и принятия решения, какая из них должна идти раньше другой. Если порядок определен таким образом, можно использовать алгоритм сортировки для помещения в этот порядок списка любого количества элементов.

Основное преимущество сопоставления заключается в том, что оно позволяет пользователю быстро и легко найти элемент в списке или подтвердить его отсутствие в списке. В автоматических системах это можно сделать с помощью алгоритма двоичного поиска или интерполяционного поиска ; Ручной поиск может быть выполнен с использованием примерно аналогичной процедуры, хотя часто это делается неосознанно. Другие преимущества заключаются в том, что можно легко найти первый или последний элемент в списке (скорее всего, это будет полезно в случае числовых данных) или элементы в заданном диапазоне (опять же полезно в случае числовых данных, а также с данные в алфавитном порядке, когда можно быть уверенным только в первых нескольких буквах искомого предмета или предметов).

Заказ

Числовые и хронологические

Строки, представляющие числа, можно сортировать на основе значений чисел, которые они представляют. Например, «−4», «2,5», «10», «89», «30 000». Чистое применение этого метода может обеспечить лишь частичный порядок строк, поскольку разные строки могут представлять одно и то же число (как в случае «2» и «2.0» или, когда экспоненциальная запись используется , «2e3» и «2000»).

Аналогичный подход можно применить к строкам, представляющим даты или другие элементы, которые можно упорядочить в хронологическом порядке или каким-либо другим естественным образом.

Алфавитный

Алфавитный порядок является основой многих систем сопоставления, в которых элементы информации идентифицируются строками, состоящими в основном букв алфавита . из Порядок строк зависит от существования стандартного порядка букв рассматриваемого алфавита. (Система не ограничивается алфавитами в строгом техническом смысле; языки, в которых используется слоговое письмо или абугида , например чероки , могут использовать тот же принцип упорядочения, при условии, что существует установленный порядок используемых символов.)

Чтобы решить, какая из двух строк стоит первой в алфавитном порядке, сначала сравниваются их первые буквы. Строка, первая буква которой встречается раньше в алфавите, стоит первой в алфавитном порядке. Если первые буквы одинаковые, то сравниваются вторые буквы и так далее, пока порядок не будет определен. (Если в одной строке заканчиваются буквы для сравнения, то она считается первой; например, «телега» стоит перед «тележной лошадью».) Результатом расположения набора строк в алфавитном порядке является то, что слова с одинаковым первым словом буквы группируются вместе, а внутри такой группы группируются слова с одинаковыми первыми двумя буквами и так далее.

Заглавные буквы обычно рассматриваются как эквиваленты соответствующих им строчных букв. (Альтернативные способы обработки в компьютеризированных системах см. в разделе «Автоматическая сортировка » ниже.)

При использовании алфавитного порядка могут применяться определенные ограничения, сложности и специальные соглашения:

Если строки содержат пробелы или другие разделители слов, необходимо принять решение, игнорировать ли эти разделители или рассматривать их как символы, предшествующие всем остальным буквам алфавита. Например, если выбран первый подход, то «автостоянка» будет идти после «углерода» и «карпа» (как если бы было написано «автостоянка»), тогда как во втором подходе «автостоянка» будет идти перед этими словами. два слова. Первое правило используется во многих (но не во всех) словарях , второе — в телефонных справочниках (так что Уилсон, Джим К. появляется вместе с другими людьми по имени Уилсон, Джим, а не после Уилсон, Джимбо).
С сокращениями можно обращаться так, как если бы они были написаны полностью. Например, имена, содержащие «Св.» (сокращение от английского слова Saint ) часто заказываются так, как если бы они были написаны как «Святой». В английском языке также существует традиционное соглашение, согласно которому фамилии, начинающиеся с Mc и M', указываются так, как если бы эти префиксы были написаны Mac .
Строки, представляющие личные имена, часто перечисляются в алфавитном порядке фамилий, даже если имя стоит первым. Например, Хуан Эрнандес и Брайан О'Лири следует сортировать как «Эрнандес, Хуан» и «О'Лири, Брайан», даже если они написаны иначе.
Очень распространенные начальные слова, такие как The на английском языке, часто игнорируются в целях сортировки. Таким образом, «Сияние» будет отсортировано как просто «Сияние» или «Сияние, The».
Когда некоторые строки содержат цифры (или другие небуквенные символы), возможны различные подходы. Иногда такие символы рассматриваются так, как будто они идут до или после всех букв алфавита. Другой метод заключается в сортировке чисел в алфавитном порядке, как если бы они были написаны: например, 1776 будет отсортирован так, как если бы он был написан как «семнадцать семьдесят шесть», а 24 часа в Мане , как если бы он писался как «vingt-quatre...» (французский). для «двадцать четыре»). Когда цифры или другие символы используются в качестве особых графических форм букв, как в 1337 году для leet или Se7en для названия фильма «Семь» , они могут быть отсортированы так, как если бы они были этими буквами.
В языках существуют разные соглашения об обработке измененных букв и определенных комбинаций букв. Например, в испанском языке буква ñ рассматривается как основная буква, следующая за n , а орграфы ch и ll раньше (до 1994 года) рассматривались как основные буквы, следующие за c и l , хотя теперь они расположены в алфавитном порядке как двухбуквенные комбинации. Список таких соглашений для различных языков можно найти в разделе «Алфавитный порядок § Соглашения, специфичные для языка» .

В некоторых языках правила со временем изменились, поэтому в старых словарях может использоваться другой порядок, чем в современных. Кроме того, сортировка может зависеть от использования. Например, в немецких словарях и телефонных справочниках используются разные подходы.

Сортировка корней

Некоторые арабские словари, такие как Ганса Вера двуязычный «Словарь современного письменного арабского языка» , группируют и сортируют арабские слова по семитическому корню . ^[1] Например, слова китаба ( «письмо »), китаб ( « книга »), катиб ( « писатель »), мактаба ( « библиотека »), мактаб ( « офис »), мактуб ( пишется «судьба»),» или « написанное'), объединяются под трехбуквенным корнем k - t - b ( ktb ), который обозначает "письмо". ^[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, ...). (Альтернативный метод обозначения элементов списка без их нумерации — использование маркированного списка .)

используются буквы алфавита Когда для целей нумерации , существуют определенные языковые соглашения относительно того, какие буквы используются. Например, русские буквы Ъ и Ь (которые в письменном виде используются только для изменения предшествующей согласной ), а также обычно также Ы , Й и Ё. опускаются Кроме того, во многих языках, использующих расширенную латиницу , измененные буквы часто не используются при перечислении.

См. также

Примечания

^ Исторически компьютеры обрабатывали текст только в верхнем регистре (это восходит к телеграфным соглашениям).

Ссылки

^ Абу-Хайдар, Дж. А. (1983). «Обзор словаря современного письменного арабского языка (арабско-английского)» . Бюллетень Школы восточных и африканских исследований Лондонского университета . 46 (2): 351–353. ISSN 0041-977X . JSTOR 615409 .
^ «Арабско-английский словарь Ганса Вера» . ejtaal.net . Проверено 4 июня 2023 г.
^ Перейти обратно: ^а ^б M-программирование: подробное руководство , Ричард Ф. Уолтерс, Digital Press, 1997.

Внешние ссылки

Алгоритм сопоставления Unicode : Технический стандарт Unicode № 10
Сопоставление на испанском языке. Архивировано 13 августа 2006 г. в Wayback Machine.
Сопоставление названий государств-членов Организации Объединенных Наций. Архивировано 30 августа 2005 г. в Wayback Machine.
Типографская сортировка для многих языков , предложенная в модуле «Список» каскадных таблиц стилей .
Диаграммы сопоставления : диаграммы, демонстрирующие порядок сортировки для конкретного языка в различных операционных системах и СУБД.
ICU Locale Explorer. Архивировано 11 мая 2008 г. на Wayback Machine : онлайн-демонстрация сортировки на разных языках с использованием алгоритма сортировки Unicode с международными компонентами для Unicode.

[4] Исторически компьютеры обрабатывали текст только в верхнем регистре (это восходит к телеграфным соглашениям).

[1] Абу-Хайдар, Дж. А. (1983). «Обзор словаря современного письменного арабского языка (арабско-английского)» . Бюллетень Школы восточных и африканских исследований Лондонского университета . 46 (2): 351–353. ISSN 0041-977X . JSTOR 615409 .

[2] «Арабско-английский словарь Ганса Вера» . ejtaal.net . Проверено 4 июня 2023 г.

[Walters-3] Перейти обратно: ^а ^б M-программирование: подробное руководство , Ричард Ф. Уолтерс, Digital Press, 1997.

[1]

[2]

[3]

[примечание 1]