Статья 6. Коллация: Unicode Collation Algorithm и CLDR¶

Почему простая сортировка не работает?¶

Наивная лексикографическая сортировка — по числовому значению кодовых точек — даёт неправильный результат для большинства реальных языков:

sorted(['ёж', 'Ель', 'елка', 'Ёж'])
# ['Ель', 'Ёж', 'елка', 'ёж']  — неправильно!
# Проблемы:
# 1. Регистр: 'Е' (U+0415) < 'е' (U+0435) по кодовой точке
# 2. Ё/ё (U+0401/U+0451) стоят не рядом с Е/е по кодовым точкам

Для корректной сортировки нужно учитывать:

• Регистр (обычно не важен на первом уровне)
• Диакритику (é и e — почти одно и то же)
• Языковые правила (в шведском ä идёт после z, в немецком ü = ue)
• Числа внутри строк (натуральная сортировка: "file10" > "file9")

1. Unicode Collation Algorithm (UCA)¶

UCA (Unicode Technical Standard #10) — стандартный алгоритм сортировки Unicode. Спецификация: https://www.unicode.org/reports/tr10/

Принцип: многоуровневые веса¶

Каждый символ (или последовательность символов) получает ключ сортировки — набор числовых весов на нескольких уровнях:

Сравнение идёт сначала по всем L1-весам строки, потом L2, потом L3, потом L4. Это означает: apricot < azimuth (L1), но café < cafe только на уровне L2.

DUCET — Default Unicode Collation Element Table¶

Файл allkeys.txt содержит весовую таблицу для всех символов Unicode. Это таблица по умолчанию (без учёта языка).

# Фрагмент allkeys.txt:
0041  ; [.1C47.0020.0008] # LATIN CAPITAL LETTER A
0061  ; [.1C47.0020.0002] # LATIN SMALL LETTER A
00E9  ; [.1C5A.0020.0002] # LATIN SMALL LETTER E WITH ACUTE
0065  ; [.1C5A.0020.0002] # LATIN SMALL LETTER E

Формат: code_point ; [.L1.L2.L3]

Обратите внимание: A и a имеют одинаковый L1 (1C47), но разный L3 (0008 vs 0002). Значит, при strength=primary они равны. При strength=tertiary — A > a.

Контракции (contractions)¶

Некоторые последовательности символов имеют вес как единое целое:

# Чешское ch — одна "буква", должна быть после h
0063 0068 ; [.1CC6.0020.0002] # ch (special Czech contraction)

Экспансии (expansions)¶

Один символ → несколько весовых элементов:

# Немецкое ß раскрывается в ss при сортировке
00DF ; [.1CE3.0020.0002][.1CE3.0020.0002] # ß → ss+ss

2. CLDR — Common Locale Data Repository¶

UCA с DUCET — это только базовые правила. Для каждого языка могут быть свои. CLDR (https://cldr.unicode.org/) — хранилище локальных данных Unicode.

Примеры locale-специфичных правил:

Tailoring¶

ICU позволяет кастомизировать правила через синтаксис tailoring:

# ICU правила для немецкого phonebook:
& ae << ä << Ä
& oe << ö << Ö
& ue << ü << Ü
& ss << ß

3. Алгоритм UCA: шаги¶

1. Нормализация: применить NFD к входной строке.
2. Получение весов: для каждого символа (или контракции) найти запись в DUCET. Если символа нет — использовать implicit weights (вычисляемые из кодовой точки).
3. Построение Sort Key: объединить все L1-веса, разделитель 0000, все L2-веса, разделитель 0000, все L3-веса (и т. д. до нужного уровня strength).
4. Сравнение: лексикографически сравнить Sort Key как числовые массивы.

"café" sort key:
  L1: [cafe-weights] [0000]
  L2: [accent-weights] [0000]
  L3: [case-weights]

3.5. Как сортировать правильно: примеры кода¶

Python — PyICU¶

import icu

# Сортировка с учётом локали
collator = icu.Collator.createInstance(icu.Locale('ru_RU'))
words = ['ёж', 'Ель', 'елка', 'Ёж', 'еж']
result = sorted(words, key=collator.getSortKey)
print(result)
# ['Ель', 'Ёж', 'елка', 'ёж', 'еж']  — ё рядом с е, регистр игнорируется

# Уровни сравнения (strength)
collator.setStrength(icu.Collator.PRIMARY)   # только базовые буквы
collator.setStrength(icu.Collator.SECONDARY) # + диакритика
collator.setStrength(icu.Collator.TERTIARY)  # + регистр (по умолчанию)

# Сравнение двух строк напрямую
result = collator.compare('ё', 'е')
# -1 (меньше), 0 (равно), 1 (больше)

# Немецкий phonebook (ü → ue)
de_phone = icu.Collator.createInstance(icu.Locale('de@collation=phonebook'))
sorted(['Müller', 'Mueller', 'Meier'], key=de_phone.getSortKey)
# ['Meier', 'Mueller', 'Müller']  — Müller = Mueller в phonebook

JavaScript — Intl.Collator¶

// Базовая сортировка с учётом русского языка
const col = new Intl.Collator('ru');
console.log(['ёж', 'Ель', 'елка', 'Ёж'].sort(col.compare));
// ['Ель', 'Ёж', 'елка', 'ёж']  — ё рядом с е, регистр игнорируется

// Числа внутри строк (natural sort)
const natural = new Intl.Collator('ru', { numeric: true });
console.log(['file10', 'file2', 'file1'].sort(natural.compare));
// ['file1', 'file2', 'file10']  — правильно!

// Сравнение без учёта регистра и диакритики
const base = new Intl.Collator('en', { sensitivity: 'base' });
console.log(base.compare('café', 'cafe'));  // 0 — равны на base-уровне
console.log(base.compare('Ёж', 'ёж'));      // 0 — равны

Встроенный sorted vs PyICU¶

# Стандартный Python — неправильно для русского
sorted(['ёж', 'Ель', 'елка'])
# ['Ель', 'елка', 'ёж']  — ё в конце из-за кодовой точки U+0451

# PyICU — правильно
import icu
col = icu.Collator.createInstance(icu.Locale('ru_RU'))
sorted(['ёж', 'Ель', 'елка'], key=col.getSortKey)
# ['Ель', 'елка', 'ёж']  — ё рядом с е

4. ICU — International Components for Unicode¶

ICU (https://icu.unicode.org/) — стандартная реализация UCA и CLDR. Написана на C++ (icu4c) и Java (icu4j). Используется в: - Chrome, Firefox, Safari - Android, iOS - Python (через PyICU) - Java (java.text.Collator использует ICU) - Node.js (встроен через V8/ICU)

Ключевые файлы исходников ICU для коллации¶

icu4c/source/i18n/
├── ucol.cpp          # основной API collation
├── ucol_imp.h        # внутренние структуры
├── collation.h       # базовые типы весов
├── collationdata.h   # структуры данных таблиц
├── collationiterator.cpp  # итератор по символам для collation
└── collationkeys.cpp # построение sort keys

icu4c/source/data/coll/
├── root.txt          # DUCET (root collation)
├── ru.txt            # русские правила
├── de.txt            # немецкие правила
├── sv.txt            # шведские правила
└── ...

Strength в ICU¶

ICU поддерживает уровни сравнения (strength):

• PRIMARY — только основные буквы
• SECONDARY — + диакритика
• TERTIARY — + регистр (по умолчанию)
• QUATERNARY — + пунктуация

5. Алгоритм implicit weights (для символов без записи в DUCET)¶

CJK иероглифы, не перечисленные в DUCET, получают веса автоматически:

Implicit L1 = (AAAA + block_offset) + (code_point_in_block)

Это гарантирует, что все символы Unicode имеют какой-то порядок.

6. Natural Sort (натуральная сортировка)¶

Для строк с числами (file1, file10, file2) нужна особая логика:

Обычная сортировка:  file1, file10, file2   (неправильно)
Natural sort:        file1, file2, file10   (правильно)

Реализуется через дополнительный L4-уровень или предобработку.