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

Эта статья о сопоставлении в библиотеке, информации и информатике. Для использования в других целях см. Сопоставление (значения).

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

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

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

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

Заказ

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

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

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

По алфавиту

Основная статья: Алфавитный порядок

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

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

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

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

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

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

Радикально-штриховая сортировка

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

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

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

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

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

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

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

Самый простой вид автоматической сортировки основан на числовых кодах символов в набор символов, Такие как ASCII кодирование (или любое из его суперсеты Такие как Unicode ), при этом символы упорядочиваются в возрастающем числовом порядке их кодов, и этот порядок распространяется на строки в соответствии с основными принципами алфавитного порядка (математически говоря, лексикографический порядок ). Таким образом, компьютерная программа может обрабатывать персонажей а, б, C, d, и $ как заказано $, C, а, б, d (соответствующие коды ASCII $ = 36, а = 97, б = 98, C = 67, и d = 100). Следовательно, строки, начинающиеся с C, M, или же Z будет отсортировано перед строками с нижним регистром а, би т. д. Иногда это называют ASCIIбетальный порядок. Это отличается от стандартного алфавитного порядка, особенно из-за упорядочения заглавных букв перед всеми строчными (и, возможно, обработки пробелов и других небуквенных символов). Поэтому он часто применяется с определенными изменениями, наиболее очевидным из которых является преобразование регистра (часто в верхний регистр по историческим причинам[примечание 1]) перед сравнением значений ASCII.

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

Тем не менее, проблемы остаются обычными, когда алгоритм должен охватывать более одного языка. Например, в Немецкий словари слово ökonomisch находится между Offenbar и ольфакториш, пока турецкий словари лечить о и ö разными буквами, поместив оюн перед öbür.

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

Сортировка ключей

«Ключ сортировки» перенаправляется сюда. Ключи сортировки в Википедии см. WP: SORTKEY.

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

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

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

Правильная сортировка десятичных знаков немного сложнее, потому что в разных регионах используются разные символы для десятичная точка, а иногда тот же символ, используемый как десятичная точка также используется как разделитель, например «Раздел 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, ...). (Альтернативный метод указания элементов списка без их нумерации - использовать маркированный список.)

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

Смотрите также

Примечания

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

Рекомендации

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

внешняя ссылка