17

フィンランド語では(英語のように)W後に並べ替えますが、はネイティブのフィンランド語の文字ではないため、 の変形と見なされ、 と等しいように並べ替えられますが、2 つの単語の唯一の違いが である場合は, -version が最初にソートされます。例は、適切な順序を示しています。VWVVVWV

Vatanen, Watanen, Virtanen

フィンランド語ではV、 andWは and として照合されAますÁ。ÁのようにソートされAますが、それが唯一の違いである場合は、アクセントのないものが最初になります。他のすべてのアクセント付き文字にも同じ規則が適用されますが、Å,ÄとÖは Z の後に個別に照合されます。

質問: 事前定義された方法でこのようなバリアントを並べ替えるための最適なアルゴリズムは何でしょうか? (例:[Watanen, Vatanen, Virtanen]へ[Vatanen, Watanen, Virtanen])?

追加：この質問は、 http://cldr.unicode.org/index/cldr-spec/collat​​ion-guidelinesで定義されている方法で他のバリアントもカバーするように拡張することに関連しています。同じであり、この質問に対する答えは、可能な限り幅広い対象者に利益をもたらし、並べ替えアルゴリズムを Unicode CLDR で定義された照合規則と互換性を持たせることができます。Unicode CLDR では、文字間の違いを 3 つのレベルで定義しています。1 次レベル (基本文字)、2 次レベル (アクセント付き文字)、3 次レベル (大文字小文字) です。

私は、すべての数値をゼロで埋めて文字列として比較できるようにする、数値ソートのようなある種の配列の準備を考えました。例: 配列は、次のようにゼロでパディングすることにより、文字列と比較[file1000.jpg, file3.jpg, file22.jpg]できるように準備[file1000.jpg, file0003.jpg, file0022.jpg]できます。配列が準備されているため、ネイティブの Array.sort() を使用して非常に高速に並べ替えることができます。

ターゲット言語は Javascript であり、照合ベースの並べ替えがサポートされていないため、カスタム並べ替え関数を自分で作成する必要があります。アルゴリズムが優先されますが、コードもある場合は +1 の価値があります。

4

5 に答える 5

4

この問題への通常のアプローチは、マッピングのリストを使用することです (通常、リストは 3 つより長くする必要はありません。あなたの場合は 2 つです)。各マッピングは文字をシーケンス ポイントにマップします。[注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]し、2番目のマッピングを使用してに変換し[0, 0, --, 0, --, --, --]ます。WATANEN は[22, 1, 20, 1, 15, 5, 15]、最初のマッピングと 2 番目のマッピングで (まったく同じ) になり[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, ...]

これは、3 つ以上の変換テーブルに拡張できます。

たとえば、多くのアプリケーションは大文字と小文字を区別しない並べ替えのようなことを行いたいと考えていますが、他に違いがなければ文字の大文字と小文字が違います (英語では、これは通常、すべて小文字の単語の前に大文字の単語を配置することを意味します)。 、しかしどちらのオプションももっともらしいです。)

したがって、フィンランド語の場合、3 番目の変換テーブルを追加して、すべての大文字を 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] したがって、上記はマルチレベル エンコーディングの例として考えるべきであり、アルファベット順の決定的なガイドではありません。この場合、3 次コードは 1 ビットだけで構成されますが、(オランダ語のように) いくつかの文字に対して 3 つのケースがある言語がまだ存在する可能性があります。

上記のスキームは、注意して追加するのはかなり簡単ですが、digraphs と trigraphs を考慮していません。(一次順序、場合によっては二次および三次でも、有字グラフは両方の文字に対して単一のコードを持つ必要があります。) スペイン語以外のプログラマーの間で一般に信じられていることとは反対に、1994 年以来、スペイン語はこの例ではありません。ほぼ 20 年前、RAE が「ch」を以前のように「c」と「d」の間ではなく、「cg」と「ci」の間でアルファベット順に並べることを布告したときです。一部のオランダ語話者はいまだに 'ij' と 'y' を一緒に見つけることを期待しており、ハンガリー人はアルファベットを構成する複雑な連字と連字の集合を今でも尊重しているかもしれませんが、全体として、アルファベット順の複雑な機械的スキームは消滅しつつあります。

[注 1]: エンコーディングの二次部分は、一次部分が同一である単語のペアに対してのみ参照されるため、「無関係な」二次コードを挿入する必要はありません。二次コーディングに無関係と見なされる文字は、一次同等クラスのすべての単語でそのように見なされるため、二次コーディングから除外することができます。同様に、上記で行ったように、さまざまな主要な等価クラスでコードを再利用することは正当です。[v, w] は [0, 1] であり、[a, á] も同様です。明らかに、あいまいさの可能性はありません。その結果、二次エンコーディングは、シーケンス長とビット長の両方で非常に短くなる可能性があります。

[注 2]: 英語にはそのような本体はありません。スペイン語のものはReal Academia Españolaですが、アクセントがアルファベット順に考慮されていないという簡潔な観察を除けば、私の本棚にある RAE のどの出版物にも正確な照合規則は見つかりませんでした。しかし、RAE の辞書は、少なくとも私が考えることができる 2 つのケース (パパ/パパとサバナ/サバナ) では、一貫して同じ文字のアクセント付きの単語の前にアクセントのない単語を配置しているようです。

[注 3] もちろん、オリジナルも追跡する必要があるため、何らかの方法で文字列に比較キーを付ける必要があります。2 つの文字がすべてのマッピングで同じ変換を持たない限り、比較キーをキーとして使用する単純なハッシュ テーブルでこれを行うことができます。

于 2012-09-27T16:03:46.427 に答える
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 に答える
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 に答える