Comment puis-je effectuer une opération "starts-with" sensible à la culture à partir du milieu d'une chaîne de caractères ?

Question

J'ai une exigence qui est relativement obscure, mais j'ai l'impression que devrait être possible en utilisant la BCL.

Pour le contexte, je parsagerai une chaîne de date/heure en Heure de Noda . Je maintiens un curseur logique pour ma position dans la chaîne d'entrée. Ainsi, alors que la chaîne complète peut être "3 janvier 2013", le curseur logique peut se trouver au "J".

Maintenant, je dois analyser le nom du mois, en le comparant à tous les noms de mois connus pour la culture :

• Sensible à la culture
• Insensiblement au cas par cas
• Juste à partir du point du curseur (pas plus tard ; je veux voir si le curseur "regarde" le nom du mois du candidat)
• Rapidement
• ... et j'ai besoin de savoir ensuite combien de caractères ont été utilisés.

El code actuel pour ce faire fonctionne généralement, en utilisant CompareInfo.Compare . C'est en fait comme ceci (juste pour la partie correspondance - il y a plus de code dans la vraie chose, mais ce n'est pas pertinent pour la correspondance) :

internal bool MatchCaseInsensitive(string candidate, CompareInfo compareInfo)
{
    return compareInfo.Compare(text, position, candidate.Length,
                               candidate, 0, candidate.Length, 
                               CompareOptions.IgnoreCase) == 0;
}

Toutefois, cela suppose que le candidat et la région que nous comparons aient la même longueur. C'est bien la plupart du temps, mais no bien dans certains cas particuliers. Supposons que nous ayons quelque chose comme :

// U+00E9 is a single code point for e-acute
var text = "x b\u00e9d y";
int position = 2;
// e followed by U+0301 still means e-acute, but from two code points
var candidate = "be\u0301d";

Maintenant, ma comparaison va échouer. Je pourrais utiliser IsPrefix :

if (compareInfo.IsPrefix(text.Substring(position), candidate,
                         CompareOptions.IgnoreCase))

mais :

• Cela m'oblige à créer une sous-chaîne, ce que je préfère éviter. (Je considère Noda Time comme étant effectivement une bibliothèque système ; les performances d'analyse syntaxique peuvent très bien être importantes pour certains clients).
• Il ne me dit pas jusqu'où avancer le curseur ensuite.

En réalité, je soupçonne fortement que cela ne se produira pas très souvent... mais j'aimerais vraiment... comme pour faire la bonne chose ici. J'aimerais aussi pouvoir le faire sans avoir à devenir un expert d'Unicode ou à le mettre en œuvre moi-même :)

(soulevée en tant que bug 210 en temps Noda, au cas où quelqu'un voudrait suivre une éventuelle conclusion).

J'aime l'idée de normalisation. Je dois vérifier cela en détail pour a) l'exactitude et b) les performances. En supposant que je peut de le faire fonctionner correctement, je ne suis toujours pas sûr qu'il vaille la peine de le changer - c'est le genre de chose qui sera probablement jamais en réalité, mais pourrait nuire aux performances de tous mes utilisateurs :(

J'ai également vérifié la BCL, qui ne semble pas non plus gérer ce problème correctement. Exemple de code :

using System;
using System.Globalization;

class Test
{
    static void Main()
    {
        var culture = (CultureInfo) CultureInfo.InvariantCulture.Clone();
        var months = culture.DateTimeFormat.AbbreviatedMonthNames;
        months[10] = "be\u0301d";
        culture.DateTimeFormat.AbbreviatedMonthNames = months;

        var text = "25 b\u00e9d 2013";
        var pattern = "dd MMM yyyy";
        DateTime result;
        if (DateTime.TryParseExact(text, pattern, culture,
                                   DateTimeStyles.None, out result))
        {
            Console.WriteLine("Parsed! Result={0}", result);
        }
        else
        {
            Console.WriteLine("Didn't parse");
        }
    }
}

Changer le nom du mois personnalisé en "bed" avec une valeur de texte de "bEd" est très bien interprété.

Ok, quelques points de données supplémentaires :

• Le coût de l'utilisation de Substring y IsPrefix est significatif mais pas horrible. Sur un échantillon de "Friday April 12 2013 20:28:42" sur mon ordinateur portable de développement, cela fait passer le nombre d'opérations d'analyse que je peux exécuter en une seconde d'environ 460K à environ 400K. Je préférerais éviter ce ralentissement si possible, mais ce n'est pas le cas. trop mauvais.

• La normalisation est moins réalisable que je ne le pensais, car elle n'est pas disponible dans les bibliothèques de classes portables. Je pourrais potentiellement l'utiliser juste pour les constructions non-PCL, permettant aux constructions PCL d'être un peu moins correctes. L'impact sur les performances des tests de normalisation ( string.IsNormalized ) ramène les performances à environ 445 000 appels par seconde, ce qui me convient. Je ne suis toujours pas sûr qu'il fasse tout ce dont j'ai besoin - par exemple, un nom de mois contenant "ß" devrait correspondre à "ss" dans de nombreuses cultures, je crois... et la normalisation ne le fait pas.

Answer 1

J'examinerai d'abord le problème des casemappings nombreux<->un/plusieurs et séparément de la gestion des différentes formes de normalisation.

Par exemple :

x heiße y
  ^--- cursor

Correspondances heisse mais déplace alors le curseur 1 de trop. Et :

x heisse y
  ^--- cursor

Correspondances heiße mais déplace ensuite le curseur 1 fois de moins.

Cela s'applique à tout caractère qui n'a pas une correspondance simple de un à un.

Il faudrait connaître la longueur de la sous-chaîne qui a effectivement été trouvée. Mais Compare , IndexOf etc. jeter cette information. Cela pourrait être possible avec des expressions régulières, mais l'implémentation ne fait pas la distinction entre majuscules et minuscules et ne correspond donc pas à ß a ss/SS en mode insensible à la casse, même si .Compare y .IndexOf faire. Et il serait probablement coûteux de créer de nouvelles regex pour chaque candidat de toute façon.

La solution la plus simple consiste à stocker en interne les chaînes de caractères sous forme pliée en casse et à effectuer des comparaisons binaires avec les candidats pliés en casse. Vous pouvez alors déplacer correctement le curseur avec seulement .Length puisque le curseur est destiné à la représentation interne. Vous récupérez également la plupart des performances perdues en n'ayant pas à utiliser CompareOptions.IgnoreCase .

Malheureusement, il n'y a pas de fonction de pliage de cas intégrée et le pliage de cas du pauvre ne fonctionne pas non plus parce qu'il n'y a pas de mappage de cas complet - la fonction ToUpper méthode ne tourne pas ß en SS .

Par exemple, cela fonctionne en Java (et même en Javascript), étant donné que la chaîne de caractères est en forme normale C :

//Poor man's case folding.
//There are some edge cases where this doesn't work
public static String toCaseFold( String input, Locale cultureInfo ) {
    return input.toUpperCase(cultureInfo).toLowerCase(cultureInfo);
}

Il est amusant de noter que la comparaison des cas ignorés de Java ne fait pas le pliage complet des cas comme celui de C#. CompareOptions.IgnoreCase . Ils sont donc opposés à cet égard : Java fait le casemapping complet, mais le pliage de cas simple - C# fait le casemapping simple, mais le pliage de cas complet.

Il est donc probable que vous ayez besoin d'une bibliothèque tierce pour mettre en cascade vos chaînes avant de les utiliser.

---

Avant de faire quoi que ce soit, vous devez être sûr que vos chaînes de caractères sont en forme normale C. Vous pouvez utiliser cette vérification rapide préliminaire optimisée pour le latin script :

public static bool MaybeRequiresNormalizationToFormC(string input)
{
    if( input == null ) throw new ArgumentNullException("input");

    int len = input.Length;
    for (int i = 0; i < len; ++i)
    {
        if (input[i] > 0x2FF)
        {
            return true;
        }
    }

    return false;
}

Cela donne des faux positifs mais pas de faux négatifs, je ne m'attends pas à ce que cela ralentisse du tout 460k parses/s lors de l'utilisation de caractères latins script même si cela doit être effectué sur chaque chaîne. Avec un faux positif, vous utiliseriez IsNormalized pour obtenir un vrai négatif/positif et seulement après cela normaliser si nécessaire.

---

Donc en conclusion, le traitement consiste à assurer la forme normale C d'abord, puis le pliage du cas. Faites des comparaisons binaires avec les chaînes traitées et déplacez le curseur comme vous le faites actuellement.

Answer 2

Voyez si cela répond à l'exigence.. :

public static partial class GlobalizationExtensions {
    public static int IsPrefix(
        this CompareInfo compareInfo,
        String source, String prefix, int startIndex, CompareOptions options
        ) {
        if(compareInfo.IndexOf(source, prefix, startIndex, options)!=startIndex)
            return ~0;
        else
            // source is started with prefix
            // therefore the loop must exit
            for(int length2=0, length1=prefix.Length; ; )
                if(0==compareInfo.Compare(
                        prefix, 0, length1, 
                        source, startIndex, ++length2, options))
                    return length2;
    }
}

compareInfo.Compare ne s'exécute qu'une fois source a commencé par prefix Si ce n'est pas le cas, alors IsPrefix renvoie à -1 ; sinon, la longueur des caractères utilisés dans source .

Cependant, je n'ai aucune idée sauf l'incrément length2 par 1 avec le cas suivant :

var candidate="ßssß\u00E9\u0302";
var text="abcd ssßss\u0065\u0301\u0302sss";

var count=
    culture.CompareInfo.IsPrefix(text, candidate, 5, CompareOptions.IgnoreCase);

---

mise à jour :

J'ai essayé d'améliorer un peu la performance, mais il n'est pas prouvé qu'il y ait un bug dans le code suivant :

public static partial class GlobalizationExtensions {
    public static int Compare(
        this CompareInfo compareInfo,
        String source, String prefix, int startIndex, ref int length2, 
        CompareOptions options) {
        int length1=prefix.Length, v2, v1;

        if(0==(v1=compareInfo.Compare(
            prefix, 0, length1, source, startIndex, length2, options))
            ) {
            return 0;
        }
        else {
            if(0==(v2=compareInfo.Compare(
                prefix, 0, length1, source, startIndex, 1+length2, options))
                ) {
                ++length2;
                return 0;
            }
            else {
                if(v1<0||v2<0) {
                    length2-=2;
                    return -1;
                }
                else {
                    length2+=2;
                    return 1;
                }
            }
        }
    }

    public static int IsPrefix(
        this CompareInfo compareInfo,
        String source, String prefix, int startIndex, CompareOptions options
        ) {
        if(compareInfo.IndexOf(source, prefix, startIndex, options)
                !=startIndex)
            return ~0;
        else
            for(int length2=
                    Math.Min(prefix.Length, source.Length-(1+startIndex)); ; )
                if(0==compareInfo.Compare(
                        source, prefix, startIndex, ref length2, options))
                    return length2;
    }
}

J'ai testé avec le cas particulier, et la comparaison est descendue à environ 3.

Answer 3

C'est en fait possible sans normalisation et sans utiliser la fonction IsPrefix .

Nous devons comparer le même nombre de éléments de texte plutôt que le même nombre de caractères, mais renvoie toujours le nombre de caractères correspondants.

J'ai créé une copie du MatchCaseInsensitive méthode de ValueCursor.cs dans le temps de Noda et l'a légèrement modifié pour qu'il puisse être utilisé dans un contexte statique :

// Noda time code from MatchCaseInsensitive in ValueCursor.cs
static int IsMatch_Original(string source, int index, string match, CompareInfo compareInfo)
{
    unchecked
    {
        if (match.Length > source.Length - index)
        {
            return 0;
        }

        // TODO(V1.2): This will fail if the length in the input string is different to the length in the
        // match string for culture-specific reasons. It's not clear how to handle that...
        if (compareInfo.Compare(source, index, match.Length, match, 0, match.Length, CompareOptions.IgnoreCase) == 0)
        {
            return match.Length;
        }

        return 0;
    }
}

(Juste inclus pour référence, c'est le code qui ne sera pas comparé correctement comme vous le savez)

La variante suivante de cette méthode utilise StringInfo.GetNextTextElement qui est fourni par le cadre. L'idée est de comparer élément de texte par élément de texte pour trouver une correspondance et, si elle est trouvée, de renvoyer le nombre réel de caractères correspondants dans la chaîne source :

// Using StringInfo.GetNextTextElement to match by text elements instead of characters
static int IsMatch_New(string source, int index, string match, CompareInfo compareInfo)
{
    int sourceIndex = index;
    int matchIndex = 0;

    // Loop until we reach the end of source or match
    while (sourceIndex < source.Length && matchIndex < match.Length)
    {
        // Get text elements at the current positions of source and match
        // Normally that will be just one character but may be more in case of Unicode combining characters
        string sourceElem = StringInfo.GetNextTextElement(source, sourceIndex);
        string matchElem = StringInfo.GetNextTextElement(match, matchIndex);

        // Compare the current elements.
        if (compareInfo.Compare(sourceElem, matchElem, CompareOptions.IgnoreCase) != 0)
        {
            return 0; // No match
        }

        // Advance in source and match (by number of characters)
        sourceIndex += sourceElem.Length;
        matchIndex += matchElem.Length;
    }

    // Check if we reached end of source and not end of match
    if (matchIndex != match.Length)
    {
        return 0; // No match
    }

    // Found match. Return number of matching characters from source.
    return sourceIndex - index;
}

Cette méthode fonctionne parfaitement, du moins d'après mes scénarios de test (qui ne font que tester quelques variantes des chaînes que vous avez fournies) : "b\u00e9d" y "be\u0301d" ).

Toutefois, le GetNextTextElement crée une sous-chaîne pour chaque élément de texte. Cette mise en œuvre nécessite donc un grand nombre de comparaisons de sous-chaînes, ce qui aura un impact sur les performances.

Ainsi, j'ai créé une autre variante qui n'utilise pas GetNextTextElement mais ignore les caractères de combinaison Unicode pour trouver l'adresse réelle. longueur du match en caractères :

// This should be faster
static int IsMatch_Faster(string source, int index, string match, CompareInfo compareInfo)
{
    int sourceLength = source.Length;
    int matchLength = match.Length;
    int sourceIndex = index;
    int matchIndex = 0;

    // Loop until we reach the end of source or match
    while (sourceIndex < sourceLength && matchIndex < matchLength)
    {
        sourceIndex += GetTextElemLen(source, sourceIndex, sourceLength);
        matchIndex += GetTextElemLen(match, matchIndex, matchLength);
    }

    // Check if we reached end of source and not end of match
    if (matchIndex != matchLength)
    {
        return 0; // No match
    }

    // Check if we've found a match
    if (compareInfo.Compare(source, index, sourceIndex - index, match, 0, matchIndex, CompareOptions.IgnoreCase) != 0)
    {
        return 0; // No match
    }

    // Found match. Return number of matching characters from source.
    return sourceIndex - index;
}

Cette méthode utilise les deux aides suivantes :

static int GetTextElemLen(string str, int index, int strLen)
{
    bool stop = false;
    int elemLen;

    for (elemLen = 0; index < strLen && !stop; ++elemLen, ++index)
    {
        stop = !IsCombiningCharacter(str, index);
    }

    return elemLen;
}

static bool IsCombiningCharacter(string str, int index)
{
    switch (CharUnicodeInfo.GetUnicodeCategory(str, index))
    {
        case UnicodeCategory.NonSpacingMark:
        case UnicodeCategory.SpacingCombiningMark:
        case UnicodeCategory.EnclosingMark:
            return true;

        default:
            return false;
    }
}

Je n'ai pas fait d'évaluation comparative, donc je ne sais pas vraiment si la méthode la plus rapide est réellement plus rapide. Je n'ai pas non plus effectué de tests approfondis.

Mais cela devrait répondre à votre question sur la façon d'effectuer une correspondance de substrats sensible à la culture pour des chaînes de caractères qui peuvent inclure des caractères de combinaison Unicode.

Voici les cas de test que j'ai utilisés :

static Tuple<string, int, string, int>[] tests = new []
{
    Tuple.Create("x b\u00e9d y", 2, "be\u0301d", 3),
    Tuple.Create("x be\u0301d y", 2, "b\u00e9d", 4),

    Tuple.Create("x b\u00e9d", 2, "be\u0301d", 3),
    Tuple.Create("x be\u0301d", 2, "b\u00e9d", 4),

    Tuple.Create("b\u00e9d y", 0, "be\u0301d", 3),
    Tuple.Create("be\u0301d y", 0, "b\u00e9d", 4),

    Tuple.Create("b\u00e9d", 0, "be\u0301d", 3),
    Tuple.Create("be\u0301d", 0, "b\u00e9d", 4),

    Tuple.Create("b\u00e9", 0, "be\u0301d", 0),
    Tuple.Create("be\u0301", 0, "b\u00e9d", 0),
};

Les valeurs du tuple sont :

1. La chaîne source (meule de foin)
2. La position de départ dans la source.
3. La chaîne de correspondance (aiguille).
4. La longueur de correspondance attendue.

L'exécution de ces tests sur les trois méthodes donne ce résultat :

Test #0: Orignal=BAD; New=OK; Faster=OK
Test #1: Orignal=BAD; New=OK; Faster=OK
Test #2: Orignal=BAD; New=OK; Faster=OK
Test #3: Orignal=BAD; New=OK; Faster=OK
Test #4: Orignal=BAD; New=OK; Faster=OK
Test #5: Orignal=BAD; New=OK; Faster=OK
Test #6: Orignal=BAD; New=OK; Faster=OK
Test #7: Orignal=BAD; New=OK; Faster=OK
Test #8: Orignal=OK; New=OK; Faster=OK
Test #9: Orignal=OK; New=OK; Faster=OK

Les deux derniers tests testent le cas où la chaîne source est plus courte que la chaîne de correspondance. Dans ce cas, la méthode originale (temps Noda) réussira également.