Это текстовая версия доклада с Java Rock Star Meetup, с которым выступал Александр Ланцов — ведущий разработчик Мир Plat.Form. Если вы больше любите смотреть видео, то смотрите запись доклада на YouTube или VK Видео.

---

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

Даны две строки. Проверьте, является ли первая строка перевёрнутой версией второй.

boolean isReversed(String a, String b)

Например:

isReversed("hello", "olleh") -> true
isReversed("racecar", "racecar") -> true
isReversed("test", "test") -> false

Формулировка кажется максимально понятной и прямолинейной. В этот момент легко подумать, что повезло: задача элементарная, не решить её невозможно. Но это только на первый взгляд. Давайте посмотрим, что может пойти не так.

Очевидное решение

Решение напрашивается само собой: пишем функцию, которая принимает две строки и возвращает true или false. С самого начала стоит показать свои навыки оптимизации: если длины строк не совпадают, то сразу выходим. После этого берем массив символов первой строки, разворачиваем его классическим способом — меняем местами первый и последний символ, второй и предпоследний и так далее. Затем собираем строку из этого массива и сравниваем со второй строкой. Все выглядит предельно разумно.

boolean isReversed(String a, String b) {
    if (a.length() != b.length()) {
        return false;
    }

    int len = a.length();
    char[] arr = a.toCharArray();

    for (int i = 0; i < len / 2; i++) {
        var tmp = arr[i];
        arr[i] = arr[len - i - 1];
        arr[len - i - 1] = tmp;
    }

    var str = new String(arr);
    return str.equals(b);
}

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

isReversed("привет ?", "? тевирп") -> false

Надо разбираться, почему.

Почему ломаются эмодзи

Чтобы понять, в чем проблема, придётся немного уйти в историю Unicode.

Когда Unicode только придумывался, его разработчики предположили, что все используемые символы мира получится вместить в примерно 65 тысяч уникальных значений. Из этого следовало простое решение: если один символ всегда укладывается в два байта, значит можно завести тип фиксированной длины и считать, что на этом вопрос закрыт. На этом, в частности, исторически строился смысл типа char в Java: единица хранения одного символа. Эта идея тогда выглядела разумной.

Но дальше, как оно это обычно и бывает, реальность оказалась сложнее: новых используемых символов становилось все больше. Сегодня это уже далеко не 65 тысяч и даже не 90 тысяч; в Unicode огромное количество символов, включая современные эмодзи, а не так давно вышедший стандарт Unicode 17.0 определяет почти 160 тысяч уникальных символов.

Unicode — стандарт кодирования символов. Он сам по себе задает не конкретное байтовое представление, а задает соответствие между символом и его codepoint. Codepoint — числовое значение, соответствующее конкретному символу. Например, у латинской заглавной буквы A codepoint равен U+0041, у смайлика ? — U+1F604. Однако есть техническое ограничение на количество символов: в Unicode можно закодировать не больше 1 114 112 уникальных codepoints. Unicode не говорит, как конкретно в виде байтов представить конкретный codepoint, за это отвечают конкретные кодировки: UTF-8, UTF-16, UTF-32.

И вот здесь начинаются тонкости.

Символ заглавной буквы латинского алфавита A (U+0041) в различных кодировках выглядит следующим образом:

UTF-32: 00 00 00 41
UTF-16:       00 41
UTF-8 :          41

Тут всё логично и понятно.

Возьмем символ посложнее — эмодзи ? (U+1F604):

UTF-32: 00 01 F6 04
UTF-16: D8 3D DE 04
UTF-8 : F0 9F 98 84

В случае с UTF-16 и UTF-8 байтовое представление не соотносится с codepoint очевидным способом.

Рассмотрим представление в UTF-8 и представим его в виде отдельных битов:

На первый взгляд ничего непонятно. Однако в этом есть внутренняя структура.

Во-первых, в начале у нас записано четыре единичных бита, идущих подряд, что означает, что этот codepoint кодируется с помощью четырех байт. В UTF-8 символы имеют переменную длину в байтовом представлении. Если бы было три единицы в начале, то наш символ кодировался бы тремя байтами, если две, то двумя. Но если бы символ кодировался только одним байтом, то его первый бит был бы равен нулю. В этой кодировке есть специальная комбинация битов в начале остальных байтов: 10. Это индикатор того, что этот байт промежуточный, он не является начальным

Затем выписываем все оставшиеся биты (убрав из байтового представления символа биты для кодирования длины и битовые индикаторы), приводим к шестнадцатеричной форме и получаем значение, соответствующее codepoint символа: 1F604

C UTF-16 всё сложнее. Почему? Когда UTF-16 только проектировался, то разработчики думали, что любой символ можно закодировать с помощью одного из 65 536 уникальных значений. Соответственно, когда эта иллюзия развеялась, им пришлось придумать какую-то хитрую схему.

Чтобы понять эту хитрую схему, нам надо от нашего codepoint отнять специальную магическую константу: 0x10000.

Затем нам надо разбить получившееся число F604 (в двоичном виде: 1111011000000100) на два участка по 10 двоичных разрядов (дополняя нулями): 0000111101 и 1000000100

Берем первые 10 бит, прибавляем к ним специальную константу D800 и получаем два байта: D8 3D. Эти два байта называются первым (верхним) суррогатом (high surrogate)

Берем вторую половинку из 10 битов, прибавляем к ней специальную константу DC 00.

Они образуют второй (нижний) суррогат (low surrogate)

Оба этих суррогата образуют пару, то есть вы не можете использовать либо верхний, либо нижний суррогат по отдельности. Они всегда должны использоваться вместе, потому что таким образом кодируют какой-то отдельный специальный codepoint. По отдельности верхние и нижние суррогаты никакой символ не кодируют. В чём тогда была ошибка нашей реализации задачи о перевороте строки?

 Наша строка с эмодзи на конце кодировалась следующей последовательностью байтов:

В UTF-16 не любой символ может быть закодирован с помощью двух байт; в этом случае он задается двумя парами байт — верхнего и нижнего суррогатами. Когда мы переворачиваем массив char, порядок этих суррогатов ломается.

После верхнего суррогата должен идти нижний суррогат, а после переворота сначала будет идти нижний суррогат, и только потом его парный верхний суррогат. С точки зрения UTF-16, это некорректная строка. По этой же причине наша реализация не работает. Как же починить?

Сделаем некоторое тривиальное исправление. Уже понятно, что в логике проверки надо использовать не отдельные char, а codepoint-ы символов.

Если посмотреть в API строк, то можно обнаружить специальный метод, который называется codePoints(). Берём этот метод и переворачиваем строку не из массива двухбайтных char, а из массива его codepoint-ов, затем переворачиваем и создаём новую строку, по которой делаем сравнение:

boolean isReversed(String a, String b) {
    if (a.length() != b.length()) {
        return false;
    }

    int len = a.length();
    int[] arr = a.codePoints().toArray();

    for (int i = 0; i < len / 2; i++) {
        var tmp = arr[i];
        arr[i] = arr[len - i - 1];
        arr[len - i - 1] = tmp;
    }

    var str = new String(arr, 0, arr.length);
    return str.equals(b);
}

На первый взгляд это уже гораздо лучше. Базовые примеры работают. А что насчет строк с эмодзи?

isReversed("hello", "olleh") -> true
isReversed("привет :)", "): тевирп") -> true
isReversed("привет ?", "? тевирп") -> 

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException Index 8 out of bounds for length 8

Тут выясняется следующая проблема: раньше оперировали массивом char, а теперь работаем с массивом codepoint-ов. Длина этих массивов может и не совпадать, что и приводит к исключению во время исполнения из-за обращения по индексу вне границ массива. Чтобы исправить эту ошибку нужно использовать правильную длину от массива:

boolean isReversed(String a, String b) {
    if (a.length() != b.length()) {
        return false;
    }

    int[] arr = a.codePoints().toArray();
    int len = arr.length;

    for (int i = 0; i < len / 2; i++) {
        var tmp = arr[i];
        arr[i] = arr[len - i - 1];
        arr[len - i - 1] = tmp;
    }

    var str = new String(arr, 0, arr.length);
    return str.equals(b);
}

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

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

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

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

Графемные кластеры

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

Здесь появляется понятие, без которого дальше разобраться не получится: графемный кластер (grapheme cluster). Графемный кластер — единица письменности, которая воспринимается как один символ. В дальнейшем для упрощения будем называть их просто графемами.

Когда человек смотрит на строку, он читает её как последовательность графем. Но Unicode устроен иначе. Например, одна графема может состоять:

• из одного codepoint:

  A → U+0041

  ? → U+1F604

• из двух codepoint:

  é → [ U+0065 , U+0301 ]

• и даже из нескольких десятков codepoint! Популярный на излёте нулевых способ написания пугающих текстов-страшилок  (https://en.wikipedia.org/wiki/Zalgo_text ) использовал как раз этот способ.

Codepoint эмодзи человека и идущий за ним codepoint-модификатор оттенка кожи должны отобразиться как один эмодзи человека с изменённым цветом кожи.

Флаги — это вообще отдельный случай. Для каждой страны они кодируются не как один уникальный codepoint, а с помощью пары из двух специальных codepoint-ов, используемых для кодирования региона. Например, флаг Гуама задается последовательностью [U+1F1EC, U+1F1FA], а флаг Уганды как [U+1F1FA, U+1F1EC].

Поэтому для переворота и сравнения строк так, как их воспринимает человек, нужно работать в терминах графем, а не отдельных codepoint-ов.

Но вот неприятная новость: у String нет методов для работы именно с графемами. В стародавние времена с выходом Java 1.1 появился малоизвестный класс BreakIterator, который можно использовать для итерирования по тексту. Удивительно, но в Java 20 его доработали так, что теперь он умеет итерироваться по отдельным графемным кластерам в строке!

Причём он умеет как идти вперед (от самой первой графемы), так и итерироваться в обратную сторону: от самой последней графемы до первой. Давайте снова попробуем исправить функцию isReversed().

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

boolean isReversed(String a, String b) {
    if (a.length() != b.length()) {
        return false;
    }

    StringBuilder sb = new StringBuilder();
    BreakIterator bi = BreakIterator.getCharacterInstance();
    bi.setText(a);

    int end = bi.last(); // идем в обратном порядке
    for (int start = bi.previous(); start != BreakIterator.DONE; end = start, start = bi.previous()) {
       sb.append(a, start, end);
    }
    var str = sb.toString();
    return str.equals(b);
}

Хорошие новости: примеры с флагами начинают работать корректно, как и с эмодзи.

Нормализация

К сожалению, это ещё не всё:

Проблема состоит в том, что конкретный графемный кластер может быть закодирован в разные последовательности codepoint-ов. Например, один и тот же (с точки зрения носителя письменности) символ Ǻ можно закодировать несколькими способами:

• U+01FA

• U+00C5 + U+0301

• U+212B + U+0301

• U+0041 + U+030A + U+0301

• U+FF21 + U+030A + U+0301

Казалось бы, зачем учитывать столько вариантов? Иногда проверка на эквивалентность может оказаться существенной:

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

В одном режиме Unicode старается свернуть строки в более компактную последовательность codepoint-ов, в другом — наоборот, разжать. В данной статье конкретные детали алгоритмов нормализации рассматриваться не будут, просто посмотрим результат их работы:

Исходные символы: «é» [U+00E9]

                                   «é» [U+0065, U+0301] 

После NFC/NFKC: «é» [U+00E9]

                                «é» [U+00E9]

После NFD/NFKD: «é» [U+0065, U+0301]

                                «é» [U+0065, U+0301]

Теперь понятно, что в нашей реализации функции была неверна самая первая строка: если строки не равны по длине в двухбайтовых char — это не означает, что они точно не равны друг другу с точки зрения носителя языка. Эту “оптимизацию” убираем совсем.

Исправление же такое: перед логикой сравнения нужно нормализовать обе строки с помощью одного из алгоритмов и только после этого работать со строками

Если нужна только каноническая эквивалентность, обычно выбирают NFC; мы для примера возьмём NFKC, не погружаясь в детали этих алгоритмов:

boolean isReversed(String a, String b) {
    a = Normalizer.normalize(a, Normalizer.Form.NFKC);
    b = Normalizer.normalize(b, Normalizer.Form.NFKC);

    StringBuilder sb = new StringBuilder();
    BreakIterator bi = BreakIterator.getCharacterInstance();
    bi.setText(a);

    int end = bi.last();
    for (int start = bi.previous(); start != BreakIterator.DONE; end = start, start = bi.previous()) {
       sb.append(a, start, end);
    }

    var str = sb.toString();
    return str.equals(b);
}

Казалось бы, задачу доделали, и теперь все случаи корректно учитываются.

Однако, добавив к исходной формулировке всего одно слово, можно превратить задачу в ещё больший кошмар. Это слово: «регистронезависимо» .

Регистронезависимость

И проблема здесь не только в том, что нужно вызвать toLowerCase() или toUpperCase().

На самом деле с регистром в Unicode всё устроено куда сложнее. Для регистронезависимого сравнения Unicode-строк обычно используют case folding. Что нужно учесть?

Во-первых, регистров в некоторых языках не два, а три: lowercase (строчный), uppercase (заглавный), titlecase (заголовочный), а в некоторых понятия регистра нет совсем.

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

В-третьих, приведение регистра может зависеть от контекста, например от положения символа в слове: греческая заглавная буква Σ (сигма) приводится к строчной σ в середине слова; но если эта буква последняя в слове, то используется другой символ ς.

Но самый проблемный язык в контексте регистронезависимости — это турецкий ??.

Этот язык ломает наивные представления программистов о том, как должны работать toUpperCase() и toLowerCase(). В чём проблема?

Есть латинская I и i, которые для носителя английского выглядят естественной парой верхнего и нижнего регистра:

I [U+0049] lower → i [U+0069]

В 1928 году из-за реформ турецкий алфавит был латинизирован. В результате, часть букв турецкого языка является обычными латинскими, а часть — специфичными именно для этого языка. Поэтому получились следующие правила:

I [U+0049] lower → ı [U+0131]

İ [U+0130] lower → i [U+0069]

Таким образом, codepoint латинской заглавной буквы I соответствует не обычная строчная латинская i, а турецкая буква ı (выглядит как i без точки и звучит как звук «ы»).

Codepoint турецкой заглавной буквы İ (выглядит как I с точкой и произносится как «и») при переводе регистра соответствует обычная строчная латинская i.

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

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

Выводы

Стандарт Unicode достаточно сложен, потому что человеческие языки устроены сложно.

• Со строками можно работать на разных уровнях: байты, двухбайтовые char в Java, codepoint-ы и графемы. Их не надо путать между собой.

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

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