Юникод и работа с ним

[Dmitriy40]

mihaild в сообщении #1335385 писал(а):

А зачем нам тут графема? Давайте искать 4й code point. Его адрес в UTF32 найти могу даже я.

А кто Вам дал гарантию что 4-й code point относится к 4-му символу (который и должен сравниваться с d)? Он может относится к первому символу если предыдущие три code point были служебными (сигнатура и два раза выставляли направление письма). А может и вообще к символам не относится, если например 100 раз установили направление письма до первого печатного символа. Или если у первого/второго/третьего символа куча служебных кодов использована (ударение, умляуты, прочее). И?

mihaild в сообщении #1335385 писал(а):

Т.е. давайте искать подстроку в смысле code point, а не графем.

Т.е. вместо поиска abcd будем искать все варианты этой подстроки со всеми возможными служебными кодами и их перестановками (да плюс ещё и возможными ошибками типа многократных повторов одинаковых служебных кодов)?! Это бред.

Единственное что можно реально сделать - фильтр входного текста, вырезающий из него всё лишнее и преобразующий все символы в объекты любой фиксированной длины. Но это снова убивает оптимизацию количества чтений/сравнений, придётся же всегда читать все 100% входного текста. Плюс сам этот фильтр весьма и весьма нетривиальный если делать универсальным.

[mihaild]

Dmitriy40 в сообщении #1335398 писал(а):

А кто Вам дал гарантию что 4-й code point относится к 4-му символу (который и должен сравниваться с d)?

А зачем мне эта гарантия? Если там кодпоинт, отличный от U+0064, то смело идем дальше, независимо от того, в какую графему входит этот кодпоинт (и входит ли вообще).

Dmitriy40 в сообщении #1335398 писал(а):

Т.е. вместо поиска abcd будем искать все варианты этой подстроки со всеми возможными служебными кодами и их перестановками (да плюс ещё и возможными ошибками типа многократных повторов одинаковых служебных кодов)?!

Это совершенно другая проблема - неоднозначности представления. И с ней поиск действительно становится существенно сложнее.
Не говоря уже о вопросе - хотим ли мы матчить U+0071 U+0077 и U+0077 U+0071 U+200F?

Но проблемы именно из-за неоднозначности, а не из-за переменной длины. Если скажем и шаблон, и текст получены перекодировкой из CP1251 в UTF8, то мы всё еще можем искать вхождение шаблона в текст просто как последовательности байт - свойства UTF8 гарантируют, что такие вхождения совпадают со вхождениями как последовательности графем.

[Munin]

mihaild в сообщении #1335405 писал(а):

А зачем мне эта гарантия? Если там кодпоинт, отличный от U+0064, то смело идем дальше

Я же вам привёл пример post1335175.html#p1335175 , когда в кодпойнте 한 U+D55C нет буквы ㅎ U+314E, но она там должна находиться.

[mihaild]

Munin в сообщении #1335411 писал(а):

Я же вам привёл пример

Это следствие неоднозначности, а не переменности длины.

[arseniiv]

Погодите, mihaild уже упоминал нормальные формы. Неужели приведение в одну из них оставляет проблемы неоднозначности (или хотя бы их большинство)?

[Munin]

mihaild в сообщении #1335418 писал(а):

Это следствие неоднозначности

Какая же тут неоднозначность? Я вам клянусь, другими кодпойнтами записать слово hangeul просто нельзя.

[Dmitriy40]

mihaild в сообщении #1335405 писал(а):

А зачем мне эта гарантия? Если там кодпоинт, отличный от U+0064, то смело идем дальше, независимо от того, в какую графему входит этот кодпоинт (и входит ли вообще).

Простите, но тогда Вы обсуждаете какой-то свой алгоритм. Описываемый мною (Бойер-Мур) требует сравнения именно символов, именно на конкретных местах в тексте, а не абы каких code point-ов не пойми от чего. Ну или я Вас не понимаю.

mihaild в сообщении #1335405 писал(а):

Не говоря уже о вопросе - хотим ли мы матчить U+0071 U+0077 и U+0077 U+0071 U+200F?

Более важный вопрос хотим ли мы при поиске U+0062 U+0061 U+0064 находить её в тексте U+0062 U+0061 U+0301 U+0064. Обычно - хотим (блокнот в Win7 правда не находит). И именно в этом месте возникает проблема непостоянной длины символа (в данном случае ударной a), потому что при попытке сравнения по Вашему варианту U+0064 и U+0301 получим ложь (не то сравниваем) и алгоритм поиска ошибётся. И эта ошибка поползёт дальше, так как U+0301 в алфавит искомой строки не входит и шаблон будет сдвинут снова с ошибкой и искомая строка в тексте U+0062 U+0061 U+0301 U+0064 U+0062 U+0061 U+0064 тоже не найдётся (будут сравниваться U+0064 из подстроки и последняя U+0061 из текста), хотя тут она есть прямо в изначальном виде! А Кнут-Моррис-Пратт её нашёл бы, хотя бы вторую.

mihaild в сообщении #1335405 писал(а):

Если скажем и шаблон, и текст получены перекодировкой из CP1251 в UTF8,

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

(Банальный пример)

Хранение локализации текстов во внешнем файле (даже на SD карте), причём его может редактировать и добавлять к устройству сам конечный пользователь. Представляете ЧТО там может встречаться? А выводить текст надо, хоть как-то. Это конечно не быстрый поиск, но проблема родственная.

(Свойства UTF8)

mihaild в сообщении #1335405 писал(а):

свойства UTF8 гарантируют,

Тоже нетривиальный вопрос, хоть стандарт и требует однозначности кодировки, но чисто теоретически кодовое пространство допускает добить каждый код до 6-ти байтов занулив старшие биты (или даже до 8-ми! ). Да, не по стандарту, но иногда может оказаться удобным, если до 4-х байтов добивать, получим всё тот же utf8, но фиксированной длины. Кто его поймёт и правильно обработает - без понятия, надо проверять, не факт что везде уже интегрировали проверку на результирующий код меньше U+110000 и не более чем четырёхбайтовость. Может быть полезно если кто-то понимает исключительно utf8 причём без строгой проверки на стандарт (а utf16 и utf32 не понимает, довольно обыденная ситуация кстати), а для чего-то нужна фиксированная длина кодов, такой вот лайфхак.

[Munin]

Dmitriy40 в сообщении #1335430 писал(а):

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

Хуже того, из софтин разных сторонних разработчиков, обрабатывающих Юникод по-разному.

[mihaild]

Munin в сообщении #1335426 писал(а):

Я вам клянусь, другими кодпойнтами записать слово hangeul просто нельзя.

U+D55C в NFD выглядит как U+1112 U+1161 U+11AB. Так что можно (с точки зрения стандарта).
(U+314E U+314F U+3134 в NFKC и NFKD выглядят так же)

[Munin]

А преобразование в NFD имеет сложность... Dmitriy40 подскажет, какую.

[mihaild]

Dmitriy40 в сообщении #1335430 писал(а):

Описываемый мною (Бойер-Мур) требует сравнения именно символов, именно на конкретных местах в тексте, а не абы каких code point-ов не пойми от чего.

Алгоритм Бойера-Мура - это, по определению, алгоритм поиска подстроки в строке. Одну и ту же последовательность байт мы можем рассматривать: как строку в алфавите $\{0, \ldots, 255\}$ (побайтово), строку в алфавите $\{0, \ldots, 2^{32} - 1\}$ (по-code-point-ово), строку в UTF32 (по-графемно).
В третьем варианте мы действительно не можем эффективно находить $n$-й символ. В двух первых - можем. Соответственно можем и запустить алгоритм Бойера-Мура над данной последовательностью байт как над строкой в алфавите из кодпоинтов.

Dmitriy40 в сообщении #1335430 писал(а):

и искомая строка в тексте U+0062 U+0061 U+0301 U+0064 U+0062 U+0061 U+0064 тоже не найдётся (будут сравниваться U+0064 из подстроки и последняя U+0061 из текста)

Почему не найдется? Сравним U+0064 из шаблона и U+0061 из текста, увидим, что не совпадает, сдвинем шаблон до самой правой U+0061 в нем и найдем совпадение.

Dmitriy40 в сообщении #1335430 писал(а):

Тоже нетривиальный вопрос

Тривиальный. UTF8 с overlong encoding невалиден.
(а вот вопрос "что делать с невалидным UTF8" уже нетривиален)

-- 29.08.2018, 23:46 --

Munin в сообщении #1335439 писал(а):

А преобразование в NFD имеет сложность...

Тем не менее, оно возможно, и утверждение

Munin в сообщении #1335426 писал(а):

другими кодпойнтами записать слово hangeul просто нельзя

неверно.

[Munin]

한글
Хм, действительно, можно.

Ну зато в 抱締める подстроку 抱き вы тоже не найдёте...

[Dmitriy40]

mihaild в сообщении #1335440 писал(а):

Почему не найдется? Сравним U+0064 из шаблона и U+0061 из текста, увидим, что не совпадает, сдвинем шаблон до самой правой U+0061 в нем и найдем совпадение.

Действительно, тут я дал маху, не подумал что будет и третий шаг, на котором и найдётся. Каюсь.
Но вот ненахождение "bad" в тексте "bád" даже если функция сравнения символов считает "a" и "á" одинаковыми - нехорошо.

[arseniiv]

Munin в сообщении #1335439 писал(а):

А преобразование в NFD имеет сложность... Dmitriy40 подскажет, какую.

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