Как я могу выполнить чувствительную к культуре операцию "начинается с" из середины строки?

Ответ 1

Я рассмотрю проблему с множеством ↔ one/many casemappings сначала и отдельно от обработки различных форм нормализации.

Например:

x heiße y
  ^--- cursor

Соответствует heisse, но затем слишком сильно перемещает курсор 1. А:

x heisse y
  ^--- cursor

Соответствует heiße, но затем слишком медленно перемещает курсор 1.

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

Вам нужно знать длину подстроки, которая была фактически сопоставлена. Но Compare, IndexOf..etc выбросьте эту информацию. Это может быть возможно с помощью регулярных выражений, но реализация не делает полного сгибания флага и поэтому не соответствует ß до ss/SS в режиме без учета регистра, даже если .Compare и .IndexOf сделать. И, вероятно, было бы дорого создавать новые регулярные выражения для каждого кандидата в любом случае.

Самое простое решение - просто хранить строки в случае сложенной формы и делать двоичные сравнения с свернутыми кандидатами. Тогда ты можешь правильно переместите курсор с помощью .Length, поскольку курсор предназначен для внутреннего представления. Вы также получаете большую часть потерянной производительности назад от необходимости использовать CompareOptions.IgnoreCase.

К сожалению, встроенная функция fold fold отсутствует, а сбой фальшивого футляра не работает либо из-за отсутствия полного отображения случаев - метода ToUpper не превращает ß в SS.

Например, это работает в Java (и даже в Javascript), заданной строкой, которая находится в нормальной форме C:

//Poor man 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);
}

Забавно отметить, что сравнение Java с игнорированием случаев не делает полный фальцовочный склад, как С# CompareOptions.IgnoreCase. Поэтому они противоположны в этом отношении: Java делает полный casemapping, но простой футляр складной - С# делает простой casemapping, но полный футляр складной.

Таким образом, вероятно, вам понадобится библиотека сторонних разработчиков, чтобы сбросить свои строки перед их использованием.

Прежде чем делать что-либо, вы должны быть уверены, что ваши строки находятся в нормальной форме C. Вы можете использовать эту предварительную быструю проверку, оптимизированную для латинского 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;
}

Это дает ложные срабатывания, но не ложные негативы, я не ожидаю, что он будет замедлять 460k parses/s вообще при использовании латинских символов script, даже если это необходимо выполнить для каждой строки. С ложным положительным вы использовали бы IsNormalized, чтобы получить истинный отрицательный/положительный и только после этого нормализовать, если необходимо.

Ответ 2

Посмотрите, соответствует ли это требованиям..:

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 выполняет только один раз source, начинающийся с prefix; если это не так, то IsPrefix возвращает -1; в противном случае длина символов, используемых в source.

Однако я понятия не имею, кроме приращения length2 на 1 со следующим случаем:

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

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

обновление:

Я попытался улучшить немного перформанса, но не доказано, есть ли ошибка в следующем коде:

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

Я тестировал с конкретным случаем, а сравнение - примерно до 3.

Ответ 3

Это действительно возможно без нормализации и без использования IsPrefix.

Нам нужно сравнить одинаковое количество текстовых элементов, в отличие от того же количества символов, но все же вернуть количество совпадающих символов.

Я создал копию метода MatchCaseInsensitive из ValueCursor.cs в Noda Time и немного изменил его, чтобы его можно было использовать в статическом контексте

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

(Только что приведенный для справки, это код, который не будет правильно сравнивать, как вы знаете)

В следующем варианте этого метода используется StringInfo.GetNextTextElement, который предоставляется каркасом. Идея состоит в том, чтобы сравнить текстовый элемент с помощью текстового элемента, чтобы найти совпадение, и если найдено, верните фактическое количество совпадающих символов в исходной строке:

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

Этот метод работает отлично, по крайней мере, в соответствии с моими тестовыми примерами (которые в основном просто проверяют несколько вариантов строк, которые вы указали: "b\u00e9d" и "be\u0301d").

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

Итак, я создал другой вариант, который не использует GetNextTextElement, но вместо этого пропускает Unicode, комбинируя символы, чтобы найти фактическую длину совпадения в символах:

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

Этот метод использует следующие два помощника:

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

Я не занимался какой-либо маркировкой, поэтому я не знаю, быстрее ли ускоренный метод. Я также не проводил расширенных испытаний.

Но это должно ответить на ваш вопрос о том, как выполнить культурно-зависимое подстрочное сопоставление для строк, которые могут включать в себя символы Unicode, объединяющие символы.

Это те тесты, которые я использовал:

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

Значения кортежей:

• Исходная строка (haystack)
• Исходная позиция в источнике.
• Строка соответствия (игла).
• Ожидаемая длина совпадения.

Выполнение этих тестов по трем методам дает этот результат:

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

Последние два теста проверяют случай, когда исходная строка короче строки соответствия. В этом случае исходный (метод времени Noda) также будет успешным.