Сопоставление

редактировать
Сборка записанной информации в стандартном порядке

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

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

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

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

Содержание

  • 1 Порядок
    • 1.1 Числовой и хронологический
    • 1.2 По алфавиту
  • 2 Радикальная сортировка
  • 3 Автоматизация
    • 3.1 Клавиши сортировки
    • 3.2 Проблемы с числами
  • 4 Маркировка заказанных элементов
  • 5 См. Также
  • 6 Примечания
  • 7 Ссылки
  • 8 Внешние ссылки

Упорядочивание

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

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

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

Алфавитный

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

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

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

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

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

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

Сортировка по радикалам

См. Также Индексирование китайских иероглифов

Другой формой сопоставления является сортировка по радикалам и штрихам, используемая для неалфавитных системы письма, такие как ханзи в китайском и кандзи в японском, тысячи символов которых не поддаются упорядочиванию по соглашению. В этой системе идентифицируются общие компоненты символов; они называются радикалами в китайских и логографических системах, производных от китайского. Затем символы группируются по их основному радикалу, а затем упорядочиваются по числу штрихов пера внутри радикалов. Когда нет очевидного радикала или более одного радикала, используется соглашение, которое используется для сопоставления. Например, китайский иероглиф 妈 (означающий «мать») сортируется как шеститрачный символ под трехстрочным первичным радикалом 女.

Система радикалов и штрихов громоздка по сравнению с алфавитной системой, в которой есть несколько знаков, все однозначно. Выбор того, какие компоненты логографа содержат отдельные радикалы, а какой радикал является первичным, не однозначен. В результате логографические языки часто дополняют порядок радикалов и штрихов алфавитной сортировкой фонетического преобразования логографов. Например, слово кандзи Tōkyō (東京) может быть отсортировано так, как если бы оно было записано японскими иероглифами слогового письма хирагана как «to-u-ki- yo -u "(と う き ょ う), используя обычный порядок сортировки для этих символов.

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

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

Автоматизация

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

Самый простой вид автоматической сортировки основан на числовых кодах символов в наборе символов, например, 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. Это отклоняется от стандартного алфавитного порядка, в частности, из-за упорядочения заглавных букв перед всеми строчными (и, возможно, обработки пробелов и других небуквенных символов). Поэтому он часто применяется с определенными изменениями, наиболее очевидным из которых является преобразование регистра (часто в верхний регистр по историческим причинам) перед сравнением значений ASCII.

Во многих алгоритмах сопоставления сравнение основано не на числовых кодах символов, а со ссылкой на последовательность сопоставления - последовательность, в которой предполагается, что символы приходят для цель сопоставления - а также другие правила упорядочивания, соответствующие данному приложению. Это может служить для применения правильных соглашений, используемых для алфавитного упорядочения в рассматриваемом языке, правильного обращения с буквами с разным регистром, измененными буквами, диграфами, определенными аббревиатурами и т. Д. упомянуто выше в разделе Алфавитный порядок и подробно в статье Алфавитный порядок. Такие алгоритмы потенциально довольно сложны и, возможно, требуют нескольких проходов по тексту.

Тем не менее, проблемы все еще распространены, когда алгоритм должен охватывать более одного языка. Например, в словарях немецкого слово ökonomisch стоит между offenbar и olfaktorisch, тогда как словари турецкого трактуют o и ö как разные буквы, помещая oyun перед öbür.

Стандартный алгоритм сопоставления любого набора строк, состоящих из любых стандартных символов Unicode, - это алгоритм сопоставления Unicode. Это можно адаптировать для использования соответствующей последовательности сопоставления для данного языка, настроив его таблицу сопоставления по умолчанию. Несколько таких настроек собраны в Common Locale Data Repository.

Sort keys

В некоторых приложениях строки, по которым сравниваются элементы, могут отличаться от отображаемых идентификаторов. Например, «Сияние» можно отсортировать как «Сияние», «Сияние» (см. Алфавитный порядок выше), но все же может потребоваться отображение его как «Сияние». В этом случае можно сохранить два набора строк: один для отображения, а другой - для сопоставления. Строки, используемые для сопоставления таким образом, называются ключами сортировки.

Проблемы с числами

Иногда желательно упорядочить текст со встроенными числами, используя правильный числовой порядок. Например, «Рисунок 7b» идет перед «Рисунок 11a», хотя «7» стоит после «1» в Unicode. Его можно расширить до римских цифр. Такое поведение нетрудно добиться, если сортировать только целые числа, хотя это может значительно замедлить сортировку. Например, Microsoft Windows делает это при сортировке имен файлов.

Правильная сортировка десятичных знаков немного сложнее, потому что разные языковые стандарты используют разные символы для десятичной точки, и иногда тот же символ, который используется в качестве десятичной точки , также используется в качестве разделителя, например «Раздел 3.2.5». Универсального ответа на вопрос, как сортировать такие строки, не существует; любые правила зависят от приложения.

Порядок возрастания чисел отличается от алфавитного, например 11 идет в алфавитном порядке перед 2. Это можно исправить с помощью ведущих нулей : 02 идет в алфавитном порядке перед 11. См., Например, ISO 8601.

Также -13 идет в алфавитном порядке после -12, хотя это меньше. В случае отрицательных чисел, чтобы привести порядок возрастания в соответствии с алфавитной сортировкой, необходимы более решительные меры, такие как добавление константы ко всем числам, чтобы все они были положительными.

Маркировка заказанных товаров

В некоторых контекстах цифры и буквы используются не столько как основа для создания заказа, сколько как средство маркировки товаров, которые уже заказаны. Например, страницы, разделы, главы и т.п., а также элементы списков часто «нумеруются» таким образом. Маркировочные серии, которые могут использоваться, включают обычные арабские цифры (1, 2, 3,...), римские цифры (I, II, III,... или i, ii, iii,...) или букв (A, B, C,... или a, b, c,...). (Альтернативный метод указания элементов списка без их нумерации - использовать маркированный список .)

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

См. Также

Примечания

Ссылки

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

Найдите сборку или алфавитную в Викисловаре, бесплатный словарь.
Последняя правка сделана 2021-05-15 14:47:46
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте