Локализовать сортировку в Javascript, сортировать буквы с акцентом и другие варианты в предопределенном виде

Ответ 1

Обычный подход к этой проблеме заключается в использовании списка сопоставлений (обычно список не должен быть длиннее трех, и в вашем случае это будет два). Каждое сопоставление отображает символ в точку последовательности. [Примечание 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).

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

Например, в вашем примере (но просто в верхнем регистре, потому что было бы утомительно вводить всю последовательность отображения), мы бы перевели VATANEN, используя первое сопоставление с [22, 1, 20, 1, 15, 5, 15] и со вторым отображением на [0, 0, --, 0, --, --, --]. WATANEN будет [22, 1, 20, 1, 15, 5, 15] (точно так же) с первым отображением, а [1, 0, --, 0, --, --, --] со вторым. Поэтому, отбрасывая -- [Примечание 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 года, почти двадцать лет назад, когда 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] Конечно, нам нужно также отслеживать оригиналы, поэтому нам нужно как-то прикрепить ключи сравнения к строкам. Пока два символа не имеют одинакового перевода во всех сопоставлениях, это можно сделать с помощью простой хеш-таблицы, используя ключ сравнения в качестве ключа.

Ответ 2

С момента, когда вы первоначально задали этот вопрос, JavaScript наконец-то приобрел некоторую достойную поддержку локалей, в том числе для сортировки.

Прочитайте новый Особенности EcmaScript 6/Harmony Intl и, в частности, Intl.Collator.

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

Чтобы получить коллатор для традиционного порядка, вам нужно передать строку "fancy" language code: 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 → реформированы [ "Ватанен", "Виртанен", "Ватанен" ]
default: fi → default [ "Vatanen", "Virtanen", "Watanen" ]

Протестировано в Google Chrome, которое, из того, что я читаю в Интернете, отстает от Firefox в этом материале.

Ответ 3

У меня была эта проблема сегодня и наткнулся на 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);

Ответ 4

Я думаю, что это должно сделать это:

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: Хорошо, я нашел способ использовать .sort() без специальной функции сравнения, которая может быть даже немного быстрее [в некоторых средах] в соответствии с http://jsperf.com/sort-mapped-strings. Хитрость заключается в использовании объектов с помощью метода .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 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;

Ответ 5

Здесь описывается стандартный способ многоуровневой сортировки: http://unicode.org/reports/tr10/

Принцип заключается в том, чтобы использовать привязки на основе локали для переопределения порядка, выраженного в таблице элементов сортировки Unicode по умолчанию (DUCET, http://www.unicode.org/Public/UCA/latest/allkeys.txt). DUCET - это базовый порядок сортировки символов. Трейлеры необходимы, если в локали есть специальные правила, которые не могут или не могут быть реализованы в DUCET.

В директории core/common/collation/in http://unicode.org/Public/cldr/22/core.zip содержится 87 xml файлов. Пример финских портретов в файле fi.xml:

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

Локальная сортировка довольно утомительна для реализации, и для того, чтобы быть достаточно быстрым, требуется использовать ресурсы на минимально возможном (машинном) уровне, поэтому я прихожу к мнению, что это лучше всего дождаться, когда Javascript поддерживает его изначально.

Но может и ждать никогда не заканчивается: Javascript не имеет поддержки для численного сортировки, который должен быть очень прост в реализации на уровне машины.

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