如何使用任意语言环境比较"basic_string"?

4
我重新发布了今天早些时候提交的问题,但是现在我会给出一个具体的示例以回应我收到的反馈。原始问题可以在此处找到(请注意,这不是一项作业任务):
我只是想确定C++是否使对一个basic_string 对象进行(高效的)大小写不敏感 比较,并且还考虑任意locale对象成为不可能。例如,似乎不可能编写如下所示的有效函数:
bool AreStringsEqualIgnoreCase(const string &str1, const string &str2, const locale &loc);

根据我的了解(但请有人确认),该函数必须调用给定的locale的ctype :: toupper()和collate :: compare()。 (始终使用use_facet()提取)。 然而,由于collate :: compare()特别需要4个指针参数,因此您需要为需要比较的每个字符传递这4个参数(在首先调用ctype :: toupper()之后),或者将两个字符串都转换为大写字母,然后进行单个调用以collate :: compare()。
显然,第一种方法效率低下(每个测试字符都需要传递4个指针),第二种方法要求您完全将两个字符串转换为大写(需要分配内存并不必要地复制/转换两个字符串为大写)。 我的理解是否正确,即无法以高效方式执行此操作(因为没有绕过collate :: compare()的方法)。

1
我看到你仍然喜欢发布巨大的文本墙。 - Lightness Races in Orbit
我改善了这篇帖子的格式,但你应该真正学会如何在未来的问题中做到这一点。 - yizzlez
@Lightness:已经注意到您的评论。 - MikeR
@Lightness:讽刺的是,你没有说任何可以纠正我的话。我很乐意听取建议,但我猜你应该更清楚吧。没关系,“没有问题”,现在我明白了(感谢你的洞见)。 - MikeR
@MikeR:不用谢。 - Lightness Races in Orbit
显示剩余12条评论
1个回答

17
尝试以一种一致的方式处理世界上所有书写系统中的一个小烦恼是,你所了解的关于字符的几乎一切都不正确。这使得像“不区分大小写比较”这样的事情变得棘手。实际上,要做任何形式的区域设置感知比较都很困难,而不区分大小写则更加棘手。
虽然有一些限制,但是仍然可以实现。所需算法可以使用正常编程实践(和一些静态数据的预计算)“高效”地实现,但无法像错误的算法那样高效地实现。通常可以在正确性和速度之间进行权衡,但结果并不令人愉快。虽然错误但快速的区域实现可能对那些区域设置正确的用户有吸引力,但对于那些区域设置产生意外结果的用户来说,显然是不令人满意的。
字典排序对人类不起作用。
大多数语言的区域设置(除了"C"区域设置)已经按照预期的方式处理字母大小写,即在考虑所有其他差异后仅使用大小写差异。也就是说,如果将单词列表按照区域设置的排序顺序排序,则仅在大小写不同的单词将连续出现在列表中。单词的大写字母是否位于小写字母之前或之后取决于区域设置,但不会有其他单词插入其中。
任何单次从左到右的逐字符比较(“词典排序”)都无法实现这种结果。大多数区域设置还具有其他排序怪癖,这些排序怪癖也无法满足朴素的词典排序。
如果您拥有适当的区域设置定义,则标准C++排序应该能够处理所有这些问题。但它不能仅使用对whar_t对的比较函数进行词典排序,因此C++标准库不提供该接口。
以下只是一些说明区域设置感知排序复杂性的示例;更详细的说明和更多示例可以在Unicode Technical Standard 10中找到。 重音符号放在哪里? 大多数罗曼语言(以及英语在处理借用词时)认为元音上的重音是次要特征;也就是说,单词首先按照没有重音的方式排序,然后进行第二次排序,在这次排序中,非重音字母排在重音字母之前。第三次排序需要处理大小写,而前两次排序忽略大小写。
但这对于北欧语言不起作用。瑞典语、挪威语和丹麦语的字母表中有三个额外的元音字母,它们跟在字母Z后面。在瑞典语中,这些元音字母分别写作å、ä和ö;在挪威语和丹麦语中,这些字母分别写作å、æ和ø,在丹麦语中,å有时会写成aa,使得奥胡斯成为丹麦城市按字母顺序排列的最后一个条目。
在德语中,字母 äöü 通常按照罗曼语言口音的顺序排列,但在德语电话簿(有时也包括其他字母表),它们按照写成 aeoeue 的方式进行排序,这是书写相同音素的旧风格。(许多常见姓氏对如“Müller”和“Mueller”发音相同,经常混淆,因此将它们交错排序是有道理的。当我年轻的时候,加拿大电话簿上苏格兰名字也使用了类似的约定;拼写为M'McMac的名字都被聚集在一起,因为它们都在语音上相同。)

一个符号,两个字母。或者两个字母,一个符号

德语还有符号 ß,它按照写成 ss 的方式进行排序,尽管在语音上并不完全相同。我们稍后还会再次遇到这个有趣的符号。

实际上,许多语言认为双字母甚至三字母组合是单个字母。44个字母的匈牙利字母表包括Cs、Dz、Dzs、Gy、Ly、Ny、Sz、Ty和Zs,以及各种带重音的元音字母。然而,在有关这一现象的文章中最常被提到的语言——西班牙语——在1994年停止将digraphs ch和ll视为字母,可能是因为强迫西班牙语作家遵循计算机系统比更改计算机系统来处理西班牙语digraphs更容易。 (维基百科声称这是来自“联合国教科文组织和其他国际组织”的压力;接受新的字母顺序规则需要相当长的时间,你仍然可以在南美洲国家的字母排序列表中偶尔看到“智利”在“哥伦比亚”之后。) 摘要:比较字符字符串需要多次通过,并且有时需要比较字符组 使所有内容不区分大小写 由于本地化正确地处理比较大小写,因此实际上不需要进行不区分大小写的排序。进行不区分大小写的等价类检查(“相等”测试)可能是有用的,尽管这引发了其他不精确的等价类可能会有用的问题。在某些情况下,Unicode规范化、删除重音符号甚至转录为拉丁文都是合理的,但在其他情况下则非常令人恼火。但事实证明,大小写转换也并不像你想象的那么简单。
由于存在具有Unicode代码点的双字母和三字母组合,实际上Unicode标准识别了三种情况而不是两种:小写、大写和首字母大写。最后一种情况用于将单词的第一个字母转换为大写,并且例如在克罗地亚双字母组合dž(U+01C6;一个字符)的情况下是必需的,它的大写形式是DŽ(U+01C4),标题案例是Dž(U+01C5)。“大小写不敏感”比较的理论是,我们可以(至少在概念上)将任何字符串转换为使“忽略大小写”定义的等价类中的所有成员转换为相同的字节序列的方式来转换字符串。传统上,这是通过“将字符串转换为大写字母”的方式来完成的,但事实证明,这并不总是可能或甚至正确的;Unicode标准更喜欢使用术语“大小写折叠”,我也同样如此。
C ++语言环境并不完全能胜任这项工作。

回到C++,令人遗憾的是,C++区域设置没有足够的信息来进行准确的大小写折叠,因为C++区域设置的工作假设将一个字符串大小写折叠只是顺序地、逐个地使用将代码点映射为另一个代码点的函数对字符串中的每个代码点进行大写处理。正如我们将看到的那样,这根本行不通,因此其效率问题是无关紧要的。另一方面,ICU库有一个接口可以像Unicode数据库允许的那样正确地进行大小写折叠,而且它的实现是由一些非常优秀的程序员精心设计的,所以在约束条件下它可能是尽可能高效的。因此,我强烈推荐使用它。

如果你想了解大小写折叠的困难程度,你应该阅读Unicode标准的第5.18和5.19节(第5章的PDF)。以下只是一些例子。

大小写转换不是从单个字符到单个字符的映射

最简单的例子是德语中的 ß (U+00DF),它没有大写形式,因为它从不出现在单词开头,而且传统的德语拼写法不使用全大写。标准的大写转换是 SS(或在某些情况下是 SZ),但这种转换是不可逆的;并不是所有的 ss 实例都会被写成 ß。例如,比较 grüßen 和 küssen(分别表示问候和亲吻)。在 v5.1 中,一个“大写 ß” ẞ 被添加到 Unicode 中作为 U+1E9E,但除了在全大写的街道标志中其使用是法律强制规定之外,它并不常用。对于大写 ß 的正常期望是两个字母 SS
并非所有的表意文字(可见字符)都是单个字符代码。
即使一个案例转换将单个字符映射到单个字符,它也可能无法将其表达为映射。例如,ǰ可以轻松大写为,但前者是一个单一的组合字形(U+01F0),而后者是一个带有组合车on(U+030C)的大写字母J。
还有像ǰ这样的字形存在进一步的问题:
朴素的逐字符大小写折叠可能会使正规化失效。
假设我们将ǰ大写,如上所示。那么如何将ǰ̠(如果在您的系统上无法正确呈现,则是具有下划线的相同字符,这是另一种IPA约定)大写?该组合为U+01F0,U+0320(带抬音符号的j,带下划线的组合减号),因此我们先用U+004A,U+030C替换U+01F0,然后保留U+0320: J̠̌。 这很好,但它与具有抬音符号和下划线的标准化大写J不相等,因为在正常形式中,减号变音符首先出现:U+004A,U+0320,U+030C(J̠̌,应该看起来相同)。 因此,有时(说实话很少,但有时)需要重新规范化。
撇开Unicode的怪异之处,有时大小写转换是上下文敏感的。
希腊语有许多例子展示了标记如何根据它们是单词的开头、结尾或内部而被打乱 - 您可以在Unicode标准的第七章中阅读更多相关内容 - 但一个简单而常见的情况是Σ,它有两个小写版本:σ和ς。具有一定数学背景的非希腊人可能熟悉 σ,但可能不知道它不能用于单词的末尾,必须使用ς。
  1. 最佳的大小写折叠方法是应用 Unicode 大小写折叠算法,该算法需要为每个源字符串创建一个临时字符串。然后,您可以对比两个转换后的字符串,以验证原始字符串是否属于同一等效类。对转换后的字符串进行排序顺序处理虽然可能,但比对原始字符串进行排序顺序处理要低效得多,而且在排序目的上,未转换的比较可能与转换的比较相当或更好。

  2. 理论上,如果您只关心大小写折叠的相等性,则可以线性地进行转换,但需要注意,这种转换不一定是无上下文的,并且不是简单的字符到字符的映射函数。不幸的是,C++ 区域设置没有提供执行此操作所需的数据。Unicode CLDR 更接近,但它是一个复杂的数据结构。

  3. 所有这些东西都非常复杂,充满了边缘情况(例如,请参见 Unicode 标准中关于带重音的立陶宛字母“i”的注释)。最好使用一个维护良好的现有解决方案,其中最好的例子是 ICU。


顺便说一句,我会给你的回复点赞,但显然我还没有足够的权限(我是新手)。不过我将来肯定会为其他人引用它(非常有帮助)。 - MikeR
1
好的,已勾选(感谢提示)。我同意解决这些问题的重要性,但成本也必须考虑在内。要做到“正确”,考虑到所有涉及的问题,成本就非常昂贵。从处理代理对(在我的UTF-16 Windows世界中)到尝试在本地C++语言环境框架内工作(我真的想引入ICU这样的第三方库吗),这很困难,特别是如果像Matt Austern的代码一样,在实际情况下可以合理地处理大多数情况。这是一个权衡,只因为做到“正确”可能会非常昂贵。 - MikeR
@jonathan:确实是在2008年4月的v5.1版本中添加的。我之前写过这个答案,但也许“最近”当时就有点过时了。 - rici
我碰巧拥有PDF的第一个版本,里面包含那封信,这纯属偶然,我并不知道它是在v5.1中添加的,只知道它存在于其中。我恰好没有更近期的PDF文件版本。 - Jonathan Leffler
显示剩余11条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接