Можно ли написать обобщенную функцию обращения строк, которая работает для всех локализаций и типов строк?

16

Я просто смотрел презентацию Джона Скита (с Тони Пони) из Dev-Days.

Хотя «написать функцию обратного преобразования строк» ​​- это кодирование интервью 101 - я не уверен, что на самом деле можно написать общую функцию обратного преобразования строк, конечно, не такую, которая работает во всех локализациях и всех типах строк.

Помимо определения, является ли входная строка ascii, UTF8, UTF16 (фиксированная и переменная длина) и т. Д.
Есть код «применить акцент к следующему символу» (U + 0301), который выделил Джон. Кроме того, существуют лигатуры, которые могут отображаться или не отображаться или кодироваться в виде двойных символов.

Кажется, что «перевернуть строку» на самом деле является одной из самых сложных задач информатики!

Мартин Беккет
источник
Нет, попробуйте проблему остановки, чтобы сделать что-то на шаг вперед, но проще объяснить людям.
JB King
Будучи несубъективным техническим вопросом, я бы рискнул сказать, что он лучше подошел бы к StackOverflow (хотя, пожалуйста, не размещайте его там повторно, он будет перенастроен, если достаточно людей проголосует, чтобы закрыть его здесь).
Петер Тёрёк
1
Зависит от языка программирования. Например, в Ruby это так же просто, как "stressed".reverse: p
Марсело
Великий философский вопрос. FWIW, Java StringBuilder получает правильные суррогаты, но не объединители
kdgregory
2
«Перевернуть эту строку на месте с помощью Java» - хороший вопрос с подвохом. :)
Скотт С Уилсон

Ответы:

5

Да. Если мы получим строку, мы можем полностью изменить каждый символ.

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

Если вы выполняете какие-либо манипуляции со строками в C #, используйте культуру инвариантов при записи и чтении, и вы можете безопасно ими манипулировать. В противном случае, подготовьтесь к провалу вызова турецкой поддержки.

ToUpper () выглядит так невинно, но это грандиозный сбой, ожидающий своего появления.

Джон Рейнор
источник
2
Другой вопрос - для чего кто-либо когда-либо использует обратную строку (кроме интервью Q)? Мне это когда-либо требовалось только для низкоуровневой буферизации портов ввода-вывода - и даже тогда почти никогда на самом деле со строками
Мартин Беккет
@ Мартин - Согласен. Может быть, для программы английского языка, чтобы найти палидромы? Я не думаю, что я использовал это, кроме как решить вопрос викторины.
Джон Рейнор
@ Мартин правда. Я думаю, что это сделано только по иронии судьбы. :)
Скотт С Уилсон
2

В общем, когда задают этот вопрос, он предполагает US-ASCII. Дело не столько в том, чтобы проверить знание человеком Unicode (хотя это было бы интересным продолжением), а в том, чтобы понять, понимают ли они, как работают указатели. Удивительное количество людей не может сделать такую ​​арифметику указателей.

Скотт К Уилсон
источник
2
"Как бы это не с Unicode?" хороший дополнительный вопрос
Мартин Беккет
Хорошо, но, возможно, несколько продвинуто - в конце концов, «перевернуть эту строку на месте» - вопрос интервью начального уровня. Вы, вероятно, не спросите бывалого человека о чем-то таком простом, если, возможно, он не очень стеснительный и вы пытаетесь согреть его.
Скотт С Уилсон
1

В качестве вопроса об интервью обычно задают технические моменты, связанные с заменой 8-битных элементов на месте, чтобы изменить их порядок (независимо от того, какие символы они могут на самом деле представлять).

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

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

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

Обычно вы хотите начать с преобразования любого другого представления в UCS-4 (он же UTF-32). Для этого вы, как правило, предпочитаете полагаться на ввод пользователя, чем пытаться выяснить это самостоятельно. В некоторых случаях вы можете быть уверены, что определенная последовательность октетов не соответствует правилам конкретной схемы кодирования, но вы можете редко (если вообще когда-либо) быть уверенным, что она следует определенной схеме кодирования.

Следующий шаг не является обязательным. Вы можете нормализовать ввод для одной из четырех форм нормализации Unicode. В этом случае вы, вероятно, захотите применить преобразование «NFKC»: декомпозиция совместимости с последующей канонической композицией. Это будет (где это возможно) преобразовывать объединяющиеся диакритические формы (такие как U + 301, которые упоминал Джон) в единые кодовые точки (например, «A» с «U + 301» будет преобразовано в «латинскую заглавную A с острым»). , U + 00C1).

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

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

Затем вы (опять же, по желанию) применяете другой процесс нормализации Unicode, такой как NFD (каноническая декомпозиция). Это превратит вышеупомянутую «латиницу A с острым» обратно в две кодовые точки - «латинская заглавная A» и «комбинация острый». Однако если ваш ввод содержит U + 00C1 для начала, он также преобразует это в две кодовые точки.

Затем вы кодируете последовательность кодовых точек UCS-4 в нужное кодирование (UTF-8, UTF-16 и т. Д.)

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

Джерри Гроб
источник
Я не сталкивался с U + 301 до того, как Джон поднял его. Я не могу понять, зачем это нужно в юникоде с глифами для всех акцентированных символов - я полагаю, это обратная совместимость
Мартин Беккет
@Martin: на самом деле существует довольно много комбинаций диакритических знаков (весь диапазон от U + 0300 до U + 036F, хотя от U + 0363 до U + 036F в лучшем случае устарели). Предварительно составленные символы предоставлены для некоторых наиболее распространенных возможностей, и объединение диакритических знаков для всего остального необходимого.
Джерри Коффин
Слишком много лишней памяти, нормализации и конвертации. Просто итерируйте символы и меняйте порядок составных кодовых единиц на месте. Затем измените порядок всех кодовых единиц на месте.
Дедупликатор