基于区域设置的Javascript排序,以预定义的方式对重音字母和其他变体进行排序

Question

在芬兰,我们排序W后V(如英语),但因为W不是本地芬兰字母,它被认为是一个变体V,因为它是等于其排序V,但在情况下,两个词之间的唯一区别是,V是W,然后V首先对-version进行排序.一个例子说明了正确的顺序:

Vatanen, Watanen, Virtanen

芬兰语V,W并作为A和整理Á.Á是排序的A,但如果它是唯一的差异,那么非重音的首先出现.同样的规则是针对所有其他重音字母,但是Å,Ä并且Ö在Z之后单独整理.

问题:以预定义方式对变体进行排序的最佳算法是什么？(例如,[Watanen, Vatanen, Virtanen]至[Vatanen, Watanen, Virtanen])？

补充:这个问题与http://cldr.unicode.org/index/cldr-spec/collat​​ion-guidelines中定义的其他变体的扩展有关,因为该技术很可能是同样,这个问题的答案有益于尽可能广泛的受众,排序算法可以与Unicode CLDR中定义的整理规则兼容.Unicode CLDR定义了字母之间的三个级别的差异:主要级别(基本字母),次级别(重音字母)和第三级别(字符大小写).

我已经考虑过某种类型的数组准备工作,我们可以用零填充所有数字,使它们可以作为字符串进行比较.一个例子:阵列[file1000.jpg, file3.jpg, file22.jpg]可以是准备用零这种方式,使其可比作为字符串通过填充:[file1000.jpg, file0003.jpg, file0022.jpg].由于数组的准备,我们可以使用原生Array.sort()快速排序.

目标语言是Javascript,它缺乏对基于排序规则的排序的支持,因此必须自定义排序功能.该算法是首选,但如果您还有代码,则值得+1.

Answer 1

自从您最初提出这个问题以来,JavaScript终于获得了一些体面的语言环境支持,包括整理.

阅读新的EcmaScript 6/Harmony功能Intl,特别是Intl.Collator.

文档实际上并没有明确说明现代和传统的排序顺序都支持芬兰语,但我已经尝试过它们.

要获得传统订单的整理程序,您需要传递一个"花哨"的语言代码字符串:fi-u-co-trad.对于"改革"的排序顺序有fi-u-co-reformed.这打破了:

• fi - 芬兰语的ISO 639语言代码.
• u - 启用Unicode功能/选项.(没有详细记录)
• co - 整理选项.
• trad - 传统的排序顺序.我读了关于西班牙语的这个选项,但发现它适用于芬兰语以及测试.(没有详细记录)
• reformed - 改革后的排序顺序.似乎是'trad'的反义词.如果没有指定trad,也不reformed你会得到default,这可能是trad在某些浏览器和reformed他人.

Teh codez:

var surnames = ['Watanen', 'Vatanen', 'Virtanen'];

var traColl = new Intl.Collator('fi-u-co-trad');
var refColl = new Intl.Collator('fi-u-co-reformed');
var defColl = new Intl.Collator('fi');

console.log('traditional:', traColl.resolved.requestedLocale + ' -> ' + traColl.resolved.collation, surnames.sort(function (a, b) {
  return traColl.compare(a,b);
}));

console.log('reformed:', refColl.resolved.requestedLocale + ' -> ' + refColl.resolved.collation, surnames.sort(function (a, b) {
  return refColl.compare(a,b);
}));

console.log('default:', defColl.resolved.requestedLocale + ' -> ' + defColl.resolved.collation, surnames.sort(function (a, b) {
  return defColl.compare(a,b);
}));

输出:

传统:fi-u-co-trad - > trad ["Vatanen","Watanen","Virtanen"]
改革:fi-u-co-reformed - > reformed ["Vatanen","Virtanen","Watanen"]
默认值:fi - >默认["Vatanen","Virtanen","Watanen"]

在谷歌浏览器中进行了测试,从我在线阅读的内容来看,它在这方面落后于Firefox.

Answer 2

我今天遇到了这个问题并遇到了String.prototype.localeCompare。您可以使用它arr.sort()并指定语言环境：

var names = ['Andrea', 'Ándrea', 'Àndrea', 'Äiti', 'Özmir', 'åke', 'Zorro', 'Åke'];

// Undesired order:
names.sort()
console.log('default sort', names);

// Desired order:
names.sort((nameA, nameB) => nameA.localeCompare(nameB, 'fi') > 0);
console.log('locale sort', names);

// Or since positive values are truthy, you can omit the `> 0`:
names.sort((nameA, nameB) => nameA.localeCompare(nameB, 'fi'));

// You can also control whether upper or lower case should sort first:
names.sort((nameA, nameB) => nameA.localeCompare(nameB, 'fi', {
  caseFirst: 'upper'
}));
console.log('locale sort with caseFirst option', names);

看起来该caseFirst选项在 Chrome 中有效，但目前在 Firefox 中无效。

该MDN页面包含更多的信息和可用的选项。localeCompare对芬兰语字符串进行排序似乎工作正常，我想它也适用于许多其他语言环境。

Answer 3

解决此问题的常用方法是使用映射列表（通常该列表不需要超过三个，在您的情况下两个就可以了。）每个映射将一个字符映射到一个序列点。[注3]所以在你的例子中，

\n\n

 primary:      secondary:\n  A -> 0         A -> 0\n  \xc3\x81 -> 0         \xc3\x81 -> 1\n  B -> 1         (irrelevant)\n  C -> 2\n  D -> 3\n  E -> 4\n...\n  T -> 20\n  U -> 21\n  V -> 22        V -> 0\n  W -> 22        W -> 1\n  X -> 23\n...\n

\n\n

比较算法本质上首先将单词中的每个字符转换为使用映射1，如果它们不相同，则将其用作比较。如果它们相同，则重复使用映射2（依此类推）。

\n\n

并非所有语言都如此简单，因此存在许多变体（例如，您可能会反转第 2 遍中的字符串）。

\n\n

请注意，您可以通过使比较键由翻译的串联组成来达到相同的效果。如果您进行大量比较，缓存此密钥可能是一个胜利。在这种情况下，您可以在映射中使用除第一个映射之外的特殊值来表示“不相关”。所有不相关的代码都可以省略，这通常会大大缩短比较键。

\n\n

例如，在您的示例中（但只是大写，因为键入整个映射序列会很乏味），我们将使用第一个映射将 VATANEN 转换为[22, 1, 20, 1, 15, 5, 15]，将第二个映射转换为[0, 0, --, 0, --, --, --]。WATANEN与第一个映射和第二个[22, 1, 20, 1, 15, 5, 15]映射（完全相同） 。[1, 0, --, 0, --, --, --]因此，删除--\ 的 [Note 1]，比较键将是：

\n\n

VATANEN:  [22, 1, 20, 1, 15, 5, 15, 0, 0, 0]\nV\xc3\x81TANEN:  [22, 1, 20, 1, 15, 5, 15, 0, 1, 0] (if there were such a place)\nWATANEN:  [22, 1, 20, 1, 15, 5, 15, 1, 0, 0]\nVIRTANEN: [22, 9, ...]\n

\n\n

这可以扩展到两个以上的转换表。

\n\n

例如，许多应用程序想要执行不区分大小写的排序之类的操作，但是如果没有其他差异，则字符大小写会有所不同（在英语中，这通常意味着将大写字母的单词放在全小写的单词之前） ，但这两种选择都是合理的。）

\n\n

因此，在芬兰语的情况下，我们可以添加第三个翻译表，其中所有大写字母都翻译为 0，所有小写字母都翻译为 1，所有其他字符不翻译。一些串联翻译：

\n\n

           -------primary---------  --2ary-  ------tertiary-----\nV\xc3\x81TANEN:  [22, 1, 20, 1, 15, 5, 15, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]\nV\xc3\xa1tenen:  [22, 1, 20, 1, 15, 5, 15, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1]\nWATANEN:  [22, 1, 20, 1, 15, 5, 15, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n

\n\n

这个顺序是否“正确”并不明显。事实上，除了那些拥有官方语言权威的语言之外，“正确”对于大多数语言来说意味着什么也并不明显。[注2] 因此，上述内容仅应被视为多级编码的示例，而不是字母顺序的明确指南。在这种情况下，第三级代码仅由一位组成，尽管仍然可能存在一些语言（例如荷兰语），其中几个字母存在三种情况。

\n\n

上述方案没有考虑二字母和三字母，尽管小心地添加它们相当容易。（在初级排序中，也可能在二级和三级排序中，二合字母需要为两个字符使用单一代码。）与非西班牙语程序员的普遍看法相反，西班牙语自 1994 年以来就没有出现过这种情况，大约二十年前，当 RAE 颁布法令，“ch”按字母顺序排列在“cg”和“ci”之间，而不是像以前那样在“c”和“d”之间。我相信一些荷兰语使用者仍然希望找到“ij”和“y”在一起，匈牙利人可能仍然尊重构成他们字母表的二合字母和三合字母的复杂集合，但总的来说，字母顺序的复杂机械方案正在消失，被简单的拉丁语排序所取代，可能辅以变音符号的二级排序（法语、西班牙语，显然是芬兰语、德语词典，但不是电话簿）或变音符号的初级排序（西班牙语 \xc3\xb1、丹麦语/挪威语/瑞典语元音、土耳其语）。

\n\n\n\n

[注1]：没有必要插入“不相关”的辅助代码，因为编码的辅助部分仅针对主要部分相同的单词对进行参考。由于任何被认为与次级编码无关的字母在主要等价类中的所有单词中都会被如此考虑，因此它可以从次级编码中省略。类似地，在不同的主等价类中重用代码是合法的，就像我们上面所做的那样：[v, w] 是 [0, 1]，[a, \xc3\xa1] 也是如此。显然，不存在任何含糊的可能性。因此，二次编码在序列长度和比特长度上都可以非常短。

\n\n

[注2]：英语没有这样的主体；西班牙的是Real Academia Espa\xc3\xb1ola，但我在书架上的任何 RAE 出版物中都找不到精确的校对规则，除了简洁地观察到按字母顺序不考虑重音命令。然而，RAE 的字典似乎始终将非重音单词放在具有相同字母的任何重音单词之前，至少在我能想到的两种情况下是这样—— papa/pap\xc3\xa1 和 sabana/s\xc3\xa1bana 。

\n\n

[注3] 当然，我们也需要跟踪原始数据，因此我们必须以某种方式将比较键附加到字符串上。只要在所有映射中没有两个字符具有相同的翻译，就可以通过使用比较键作为键的简单哈希表来完成此操作。

\n