Jak mogę wykonać zależną od kultury operację „zaczyna się od” od środka ciągu?

Mam wymaganie, które jest stosunkowo niejasne, ale wydaje mi się, że powinno być możliwe przy użyciu BCL.

Dla kontekstu analizuję ciąg daty / godziny w czasie Noda . Utrzymuję logiczny kursor dla mojej pozycji w ciągu wejściowym. Tak więc, chociaż cały ciąg może mieć postać „3 stycznia 2013 r.”, Kursor logiczny może znajdować się na „J”.

Teraz muszę przeanalizować nazwę miesiąca, porównując ją ze wszystkimi znanymi nazwami miesięcy dla kultury:

• Z wrażliwością kulturową
• Bez rozróżniania wielkości liter
• Tylko z punktu kursora (nie później; chcę sprawdzić, czy kursor „patrzy” na nazwę miesiąca kandydującego)
• Szybko
• ... a potem muszę wiedzieć, ile znaków zostało użytych

Aktualny kod to zrobić ogólnie działa, używając CompareInfo.Compare. Skutecznie działa to tak (tylko dla pasującej części - w rzeczywistości jest więcej kodu, ale nie ma to związku z dopasowaniem):

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

Jednak zależy to od tego, czy kandydat i region, który porównujemy, są tej samej długości. W porządku przez większość czasu, ale nie w niektórych szczególnych przypadkach. Załóżmy, że mamy coś takiego:

// 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";

Teraz moje porównanie się nie powiedzie. Mógłbym użyć IsPrefix:

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

ale:

• To wymaga ode mnie stworzenia podciągu, którego naprawdę wolałbym unikać. (Uważam, że czas Noda jest efektywną biblioteką systemową; wydajność analizowania może być ważna dla niektórych klientów).
• Nie mówi mi, jak daleko później przesunąć kursor

W rzeczywistości mocno podejrzewam, że nie będzie się to pojawiać zbyt często ... ale naprawdę chciałbym zrobić tutaj właściwą rzecz. Chciałbym też móc to zrobić bez zostania ekspertem od Unicode lub samodzielnego wdrażania :)

(Zgłoszony jako błąd 210 w Czasie Nody, na wypadek gdyby ktoś chciał wyciągnąć wnioski).

Podoba mi się idea normalizacji. Muszę to szczegółowo sprawdzić pod kątem a) poprawności i b) wykonania. Zakładając, że mogę sprawić, by działał poprawnie, nadal nie jestem pewien, czy warto byłoby to zmienić w ogóle - jest to coś, co prawdopodobnie nigdy nie pojawi się w prawdziwym życiu, ale może zaszkodzić wydajności wszystkich moich użytkowników: (

Sprawdziłem również BCL - który również nie wydaje się obsługiwać tego poprawnie. Przykładowy kod:

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");
        }
    }
}

Zmiana niestandardowej nazwy miesiąca na „łóżko” z wartością tekstową „bEd” parsuje dobrze.

OK, jeszcze kilka punktów danych:

• Koszt użytkowania Substringi IsPrefixjest znaczny, ale nie straszny. Na próbce „Piątek, 12 kwietnia 2013 20:28:42” na moim laptopie deweloperskim zmienia liczbę operacji analizy składniowej, które mogę wykonać w ciągu sekundy, z około 460K do około 400K. Wolałbym raczej uniknąć tego spowolnienia, jeśli to możliwe, ale nie jest tak źle.

• Normalizacja jest mniej wykonalna niż myślałem - ponieważ nie jest dostępna w przenośnych bibliotekach klas. Potencjalnie mógłbym go używać tylko do kompilacji innych niż PCL, dzięki czemu kompilacje PCL są nieco mniej poprawne. Uderzenie wydajnościowe testowania normalizacji ( string.IsNormalized) obniża wydajność do około 445 tys. Wywołań na sekundę, z czym mogę żyć. Nadal nie jestem pewien, czy robi wszystko, czego potrzebuję - na przykład nazwa miesiąca zawierająca „ß” powinna pasować do „ss” w wielu kulturach, myślę, że ... a normalizacja tego nie robi.

Najpierw rozważę problem wielu <-> jednego / wielu mapowań przypadków i oddzielnie od obsługi różnych formularzy normalizacji.

Na przykład:

x heiße y
  ^--- cursor

Pasuje, heisseale następnie przesuwa kursor o 1 za bardzo. I:

x heisse y
  ^--- cursor

Pasuje, heißeale następnie przesuwa kursor o 1 za mniej.

Będzie to miało zastosowanie do każdego znaku, który nie ma prostego odwzorowania jeden do jednego.

Musisz znać długość podciągu, który został faktycznie dopasowany. Ale Compare, IndexOf..etc rzucić tę informację dalej. To może być możliwe z wyrażeń regularnych, ale realizacja nie robi pełnego case fałdowanie i tak nie pasuje ßdo ss/SSw trybie bez uwzględniania wielkości liter choć .Comparei .IndexOfzrobić. I tak prawdopodobnie byłoby kosztowne tworzenie nowych wyrażeń regularnych dla każdego kandydata.

Najprostszym rozwiązaniem jest po prostu wewnętrzne przechowywanie łańcuchów w formie złożonej i dokonywanie porównań binarnych z kandydatami ze złożonymi wielkościami liter. Następnie możesz poprawnie przesuwać kursor za pomocą, .Lengthponieważ kursor służy do wewnętrznej reprezentacji. Możesz również odzyskać większość utraconej wydajności, ponieważ nie musisz jej używać CompareOptions.IgnoreCase.

Niestety nie ma wbudowanej funkcji zwijania przypadku, a składanie przypadku dla biedaka również nie działa, ponieważ nie ma pełnego mapowania przypadków - ToUppermetoda nie zmienia się ßw SS.

Na przykład działa to w Javie (a nawet w JavaScript), biorąc pod uwagę ciąg znaków w normalnej formie 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);
}

Przyjemnie jest zauważyć, że porównanie ignorowania wielkości liter w Javie nie wykonuje pełnego zwijania wielkości liter, jak w C # CompareOptions.IgnoreCase. Więc pod tym względem są odwrotnie: Java wykonuje pełne mapowanie wielkości liter, ale proste składanie wielkości liter - C # wykonuje proste mapowanie wielkości liter, ale pełne składanie wielkości liter.

Jest więc prawdopodobne, że potrzebujesz biblioteki innej firmy, aby złożyć struny przed ich użyciem.

Zanim cokolwiek zrobisz, upewnij się, że twoje ciągi znaków mają normalną formę C. Możesz skorzystać z tej wstępnej szybkiej kontroli zoptymalizowanej pod kątem alfabetu łacińskiego:

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;
}

Daje to fałszywe alarmy, ale nie fałszywe negatywy, nie spodziewam się, że w ogóle spowolni 460 tys. Analiz / s przy użyciu znaków alfabetu łacińskiego, mimo że musi to być wykonywane na każdym ciągu. W przypadku fałszywie dodatniego wyniku należy użyć go IsNormalizeddo uzyskania prawdziwie ujemnego / pozytywnego wyniku, a dopiero potem normalizować, jeśli to konieczne.

Sprawdź, czy spełnia to wymóg ..:

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.Comparedziała tylko raz sourcerozpoczęte z prefix; jeśli nie, to IsPrefixwraca -1; w przeciwnym razie długość znaków używanych w source.

Jednak nie mam pojęcia, oprócz przyrostu length2przez 1z następującym przypadku:

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

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

aktualizacja :

Próbowałem trochę poprawić perf., Ale nie zostało udowodnione, czy jest błąd w następującym kodzie:

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;
    }
}

Testowałem z konkretnym przypadkiem i porównanie do około 3.

Jest to faktycznie możliwe bez normalizacji i bez użycia IsPrefix.

Musimy porównać tę samą liczbę elementów tekstowych w przeciwieństwie do tej samej liczby znaków, ale nadal zwracamy liczbę pasujących znaków.

Utworzyłem kopię MatchCaseInsensitivemetody z ValueCursor.cs w Noda Time i nieznacznie ją zmodyfikowałem, aby można było jej używać w kontekście statycznym:

// 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;
    }
}

(Podany tylko w celach informacyjnych, jest to kod, który nie będzie się właściwie porównywał, jak wiesz)

Poniższy wariant tej metody używa StringInfo.GetNextTextElement, który jest udostępniany przez platformę. Chodzi o to, aby porównać element tekstowy z elementem tekstowym, aby znaleźć dopasowanie, a jeśli zostanie znaleziony, zwraca rzeczywistą liczbę pasujących znaków w ciągu źródłowym:

// 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;
}

Ta metoda działa dobrze, przynajmniej zgodnie z moimi przypadkami testowymi (które w zasadzie testują tylko kilka wariantów podanych ciągów: "b\u00e9d"i "be\u0301d").

Jednak metoda GetNextTextElement tworzy podciąg dla każdego elementu tekstowego, więc ta implementacja wymaga wielu porównań podciągów - co będzie miało wpływ na wydajność.

Stworzyłem więc inny wariant, który nie używa GetNextTextElement, ale zamiast tego pomija znaki łączące Unicode, aby znaleźć rzeczywistą długość dopasowania w znakach:

// 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;
}

Ta metoda używa następujących dwóch pomocników:

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;
    }
}

Nie robiłem żadnego benchmarkingu, więc tak naprawdę nie wiem, czy szybsza metoda jest rzeczywiście szybsza. Nie przeprowadziłem też żadnych rozszerzonych testów.

Ale to powinno odpowiedzieć na twoje pytanie, jak przeprowadzić dopasowywanie podciągów wrażliwych na kulturę dla ciągów, które mogą zawierać znaki łączące Unicode.

Oto przypadki testowe, z których korzystałem:

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),
};

Wartości krotki to:

1. Ciąg źródłowy (stóg siana)
2. Pozycja początkowa w źródle.
3. Sznur zapałkowy (igła).
4. Oczekiwana długość dopasowania.

Wykonanie tych testów trzema metodami daje taki wynik:

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

Ostatnie dwa testy sprawdzają przypadek, gdy ciąg źródłowy jest krótszy niż ciąg dopasowania. W tym przypadku oryginalna metoda (czas Noda) również się powiedzie.