2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 21:51 
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 
Аватара пользователя
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 
Аватара пользователя
mihaild в сообщении #1335405 писал(а):
А зачем мне эта гарантия? Если там кодпоинт, отличный от U+0064, то смело идем дальше

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

 
 
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 22:55 
Аватара пользователя
Munin в сообщении #1335411 писал(а):
Я же вам привёл пример
Это следствие неоднозначности, а не переменности длины.

 
 
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 23:11 
Погодите, mihaild уже упоминал нормальные формы. Неужели приведение в одну из них оставляет проблемы неоднозначности (или хотя бы их большинство)?

 
 
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 23:16 
Аватара пользователя
mihaild в сообщении #1335418 писал(а):
Это следствие неоднозначности

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

 
 
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 23:20 
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 
Аватара пользователя
Dmitriy40 в сообщении #1335430 писал(а):
ибо строки в обработку могут приходить из внешних источников, от юзеров весьма невысокой квалификации.

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

 
 
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 23:33 
Аватара пользователя
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 
Аватара пользователя
А преобразование в NFD имеет сложность... Dmitriy40 подскажет, какую.

 
 
 
 Re: Юникод и работа с ним
Сообщение29.08.2018, 23:45 
Аватара пользователя
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 
Аватара пользователя
한글
Хм, действительно, можно.

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

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

 
 
 
 Re: Юникод и работа с ним
Сообщение30.08.2018, 02:43 
Munin в сообщении #1335439 писал(а):
А преобразование в NFD имеет сложность... Dmitriy40 подскажет, какую.
Так один же раз делать для куска, в котором ищем, и один для искомого. Второй обычно меньше, а первый реже меняется. Ну и вообще странно бояться преобразований, когда они для того были как раз созданы, чтобы в подобных случаях применяться.

 
 
 [ Сообщений: 29 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group