17

在芬兰语中，我们排序W后V（如英语），但因为W不是芬兰本土字母，所以它被视为 的变体V，按等于 排序V，但在两个词之间的唯一区别是 的情况V下W，然后V-version 首先排序。一个例子说明了正确的顺序：

Vatanen, Watanen, Virtanen

在芬兰语中V，andW被整理为Aand Á。Á排序为A，但在唯一不同的情况下，无重音的优先。相同的规则适用于所有其他重音字母，但Å,Ä和Ö在 Z 之后单独整理。

问题：以预定义的方式对此类变体进行排序的最佳算法是什么？（例如[Watanen, Vatanen, Virtanen]到[Vatanen, Watanen, Virtanen]）？

另外：这个问题与扩展以涵盖http://cldr.unicode.org/index/cldr-spec/collat​​ion -guidelines 中定义的其他变体有关，因为该技术很可能是同样，这个问题的答案有利于尽可能广泛的受众，并且可以使排序算法与 Unicode CLDR 中定义的排序规则兼容。Unicode CLDR 定义了字母之间的三个级别的差异：一级（基本字母）、二级（重音字母）和三级（字符大小写）。

我曾想过某种数组准备，比如在数字排序中，我们可以用零填充所有数字，使它们与字符串一样。一个例子： Array[file1000.jpg, file3.jpg, file22.jpg]可以通过以下方式填充零来准备使其与字符串可比：[file1000.jpg, file0003.jpg, file0022.jpg]. 由于数组的准备，我们可以使用原生 Array.sort() 快速排序。

目标语言是 Javascript，它不支持基于排序的排序，所以自定义排序功能必须自己制作。该算法是首选，但如果您也有代码，则值得 +1。

4

5 回答 5

14

自从您最初提出这个问题以来，JavaScript 终于获​​得了一些不错的语言环境支持，包括排序规则。

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

该文档实际上并没有很清楚地表明芬兰语支持现代和传统的排序顺序，但我已经尝试过并且它们是。

要获得传统订单的整理者，您需要传递一个“花哨的”语言代码字符串：fi-u-co-trad. 对于“改革后”的排序顺序，有fi-u-co-reformed. 这分解为：

  • fi- 芬兰语的 ISO 639 语言代码。
  • u- 启用 Unicode 功能/选项。（没有很好的记录）
  • co- 整理选项。
  • trad- 传统的排序顺序。我阅读了有关西班牙语的此选项，但通过测试发现它也适用于芬兰语。（没有很好的记录）
  • reformed- 改革排序顺序。似乎是“传统”的反义词。如果您既不指定也不trad指定，这可能在某些浏览器和其他浏览器上。reformeddefaulttradreformed

编码：

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 -> 改革的 ["Vatanen", "Virtanen", "Watanen"]
默认值：fi -> 默认值 [“Vatanen”、“Virtanen”、“Watanen”]

在 Google Chrome 中进行了测试，根据我在网上阅读的内容，它在这方面落后于 Firefox。

于 2015-04-25T13:17:49.753 回答
8

我今天遇到了这个问题并遇到了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似乎可以很好地对芬兰语字符串进行排序，我想它也适用于许多其他语言环境。

于 2017-03-21T12:57:19.857 回答
4

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

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

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

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

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

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

VATANEN:  [22, 1, 20, 1, 15, 5, 15, 0, 0, 0]
VÁTANEN:  [22, 1, 20, 1, 15, 5, 15, 0, 1, 0] (if there were such a place)
WATANEN:  [22, 1, 20, 1, 15, 5, 15, 1, 0, 0]
VIRTANEN: [22, 9, ...]

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

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

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

           -------primary---------  --2ary-  ------tertiary-----
VÁTANEN:  [22, 1, 20, 1, 15, 5, 15, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
Vátenen:  [22, 1, 20, 1, 15, 5, 15, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1]
WATANEN:  [22, 1, 20, 1, 15, 5, 15, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

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

上面的方案没有考虑二合字母和三合字母，尽管它们很容易添加，但要小心。（在初级排序中，也可能在二级和三级排序中，二合字母需要为两个字符使用一个代码。）与非西班牙程序员的普遍看法相反，自 1994 年以来，西班牙语就不再是这样的例子，大约 20 年前，当 RAE 规定“ch”按字母顺序排列在“cg”和“ci”之间，而不是像以前那样在“c”和“d”之间。我相信一些讲荷兰语的人仍然希望同时找到“ij”和“y”，匈牙利人可能仍然尊重构成他们的字母表的复杂的二合字母和三合字母集合，但总的来说，用于字母排序的复杂机械方案正在消失，

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

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

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

于 2012-09-27T16:03:46.427 回答
0

我认为应该这样做：

var variants = ["AÁÀ", "VW", … ];

// Build a map that links variants with their base letter (for quick access)
var map = {}, chars = "";
for (var i=0; i<variants.length; i++) {
    var variant = variants[i], char = variant.charAt(0);
    for (var j=1; j<variants[i].length; j++)
        map[variant.charAt(j)] = char;
    chars += variant.substr(1);
}
// and a simple regular expression, containing a character class of all variant chars
var regex = new RegExp("["+chars+"]","g");

function sortFinnish(arr) {
    // each word is replaced by an array [literal],
    // containing 0) the word 1) the normalized word
    for (var i=0; i<arr.length; i++)
        arr[i] = [ arr[i], arr[i].replace(regex, function(m) {
            // every variant character is replaced by its base letter
            return map[m];
        }) ];
    // then sort that array with a custom compare function:
    arr.sort(function(a, b) {
        // at first by the normalized words,
        // i.e. variants count the same as their bases
        if (b[1] > a[1]) return -1;
        if (b[1] < a[1]) return 1;
        // else the normalized words are the same
        // - return a comparsion of the actual words
        if (b[0] > a[0]) return -1;
        if (b[0] < a[0]) return 1;
        return 0;
    });
    // after that, replace each of the arrays with the actual word again
    for (var i=0; i<arr.length; i++)
        arr[i] = arr[i][0];
    return arr;
}

@performance：好的，我找到了一种不使用自定义比较功能的方法，根据http://jsperf.com/sort-mapped-strings.sort()，[在某些环境中] 可能会更快一些。诀窍是使用具有返回要排序的字符串的方法的对象：.toString()

    function SortString(actualvalue) {
        this.val = actualvalue;
        // the value-to-sort-by is a normalized version, concatenated by a space
        // with the actual value so that the actual value is compared when the
        // normalized ones are the same.
        // ! does not work with values that contain spaces !
        // we'd need to use something like \u0001 instead
        var sortval = actualvalue.replace(regex, function(m) {
            // every variant character is replaced by its base letter
            return map[m];
        }) + " " + actualvalue;
        this.toString = function(){ return sortval; };
    }
    for (var i=0; i<arr.length; i++)
        arr[i] = new SortString(arr[i]);
    // when comparing, the sortstring is used as the object's representation:
    arr.sort();
    // after that, replace the objects with the actual words again:
    for (var i=0; i<arr.length; i++)
        arr[i] = arr[i].val;
于 2012-09-27T15:34:51.697 回答
0

这里表达了多级排序的标准方法：http: //unicode.org/reports/tr10/

原则是使用基于区域设置的定制来覆盖默认 Unicode 排序元素表（DUCET， http://www.unicode.org/Public/UCA/latest/allkeys.txt）中表达的顺序。DUCET 是字符的基本排序顺序。如果语言环境有一些不能或不适合在 DUCET 中实施的特殊规则，则需要进行剪裁。

http://unicode.org/Public/cldr/22/core.zip中的目录 core/common/collat​​ion/有 87 个 xml 文件。fi.xml 中的芬兰剪裁示例：

<collation type="standard" >
    <rules>
    <!-- SNIP -->
        <reset>V</reset>
            <s>w</s>
            <t>W</t>
    <!-- SNIP -->
    </rules>
</collation>

基于语言环境的排序实现起来相当繁琐，为了足够快，需要在尽可能低的（机器）级别使用资源，所以我认为最好等到Javascript 本身就支持它。

但可能等待永无止境：Javascript仍然缺乏对数字排序的支持，这在机器级别应该很容易实现。

如果某个编码人员有足够的动力在 Javascript 中实现基于语言环境的排序，我会很高兴看到结果并在我身边支持它。

于 2012-09-29T12:10:29.893 回答