2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 21:51 
Заслуженный участник


20/08/14
5785
Россия, Москва
mihaild в сообщении #1335385 писал(а):
А зачем нам тут графема? Давайте искать 4й code point. Его адрес в UTF32 найти могу даже я.
А кто Вам дал гарантию что 4-й code point относится к 4-му символу (который и должен сравниваться с d)? Он может относится к первому символу если предыдущие три code point были служебными (сигнатура и два раза выставляли направление письма). А может и вообще к символам не относится, если например 100 раз установили направление письма до первого печатного символа. Или если у первого/второго/третьего символа куча служебных кодов использована (ударение, умляуты, прочее). И?
mihaild в сообщении #1335385 писал(а):
Т.е. давайте искать подстроку в смысле code point, а не графем.
Т.е. вместо поиска abcd будем искать все варианты этой подстроки со всеми возможными служебными кодами и их перестановками (да плюс ещё и возможными ошибками типа многократных повторов одинаковых служебных кодов)?! Это бред. :facepalm:

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

 Профиль  
                  
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 22:19 
Заслуженный участник
Аватара пользователя


16/07/14
3110
Москва
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 гарантируют, что такие вхождения совпадают со вхождениями как последовательности графем.

 Профиль  
                  
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 22:43 
Заслуженный участник
Аватара пользователя


30/01/06
02/09/19
70490
mihaild в сообщении #1335405 писал(а):
А зачем мне эта гарантия? Если там кодпоинт, отличный от U+0064, то смело идем дальше

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

 Профиль  
                  
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 22:55 
Заслуженный участник
Аватара пользователя


16/07/14
3110
Москва
Munin в сообщении #1335411 писал(а):
Я же вам привёл пример
Это следствие неоднозначности, а не переменности длины.

 Профиль  
                  
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 23:11 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 23:16 
Заслуженный участник
Аватара пользователя


30/01/06
02/09/19
70490
mihaild в сообщении #1335418 писал(а):
Это следствие неоднозначности

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

 Профиль  
                  
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 23:20 
Заслуженный участник


20/08/14
5785
Россия, Москва
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-ми! :mrgreen:). Да, не по стандарту, но иногда может оказаться удобным, если до 4-х байтов добивать, получим всё тот же utf8, но фиксированной длины. Кто его поймёт и правильно обработает - без понятия, надо проверять, не факт что везде уже интегрировали проверку на результирующий код меньше U+110000 и не более чем четырёхбайтовость. Может быть полезно если кто-то понимает исключительно utf8 причём без строгой проверки на стандарт (а utf16 и utf32 не понимает, довольно обыденная ситуация кстати), а для чего-то нужна фиксированная длина кодов, такой вот лайфхак. :D

 Профиль  
                  
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 23:27 
Заслуженный участник
Аватара пользователя


30/01/06
02/09/19
70490
Dmitriy40 в сообщении #1335430 писал(а):
ибо строки в обработку могут приходить из внешних источников, от юзеров весьма невысокой квалификации.

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

 Профиль  
                  
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 23:33 
Заслуженный участник
Аватара пользователя


16/07/14
3110
Москва
Munin в сообщении #1335426 писал(а):
Я вам клянусь, другими кодпойнтами записать слово hangeul просто нельзя.

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

 Профиль  
                  
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 23:44 
Заслуженный участник
Аватара пользователя


30/01/06
02/09/19
70490
А преобразование в NFD имеет сложность... Dmitriy40 подскажет, какую.

 Профиль  
                  
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 23:45 
Заслуженный участник
Аватара пользователя


16/07/14
3110
Москва
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 просто нельзя
неверно.

 Профиль  
                  
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 23:53 
Заслуженный участник
Аватара пользователя


30/01/06
02/09/19
70490
한글
Хм, действительно, можно.

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

 Профиль  
                  
 
 Re: Юникод и работа с ним
Сообщение30.08.2018, 01:10 
Заслуженный участник


20/08/14
5785
Россия, Москва
mihaild в сообщении #1335440 писал(а):
Почему не найдется? Сравним U+0064 из шаблона и U+0061 из текста, увидим, что не совпадает, сдвинем шаблон до самой правой U+0061 в нем и найдем совпадение.
Действительно, тут я дал маху, не подумал что будет и третий шаг, на котором и найдётся. Каюсь.
Но вот ненахождение "bad" в тексте "bád" даже если функция сравнения символов считает "a" и "á" одинаковыми - нехорошо.

 Профиль  
                  
 
 Re: Юникод и работа с ним
Сообщение30.08.2018, 02:43 
Заслуженный участник
Аватара пользователя


27/04/09
25173
Уфа
Munin в сообщении #1335439 писал(а):
А преобразование в NFD имеет сложность... Dmitriy40 подскажет, какую.
Так один же раз делать для куска, в котором ищем, и один для искомого. Второй обычно меньше, а первый реже меняется. Ну и вообще странно бояться преобразований, когда они для того были как раз созданы, чтобы в подобных случаях применяться.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 29 ]  На страницу Пред.  1, 2

Модераторы: Toucan, maxal, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group