107

我有一个相对模糊的要求,但感觉应该可以使用 BCL。

对于上下文,我正在解析Noda Time中的日期/时间字符串。我在输入字符串中为我的位置维护一个逻辑光标。因此,虽然完整的字符串可能是“2013 年 1 月 3 日”,但逻辑光标可能位于“J”。

现在,我需要解析月份名称,将其与文化的所有已知月份名称进行比较:

  • 文化敏感
  • 不区分大小写
  • 只是从光标点开始(不是以后;我想看看光标是否在“查看”候选月份名称)
  • 迅速地
  • ...然后我需要知道使用了多少个字符

当前执行此操作的代码通常使用CompareInfo.Compare. 它实际上是这样的(仅用于匹配部分 - 真实的代码更多,但与匹配无关):

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

但是,这取决于候选对象和我们比较的区域长度相同。大多数时候很好,但在某些特殊情况下就不行了。假设我们有类似的东西:

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

现在我的比较将失败。我可以使用IsPrefix

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

但:

  • 这需要我创建一个子字符串,我真的宁愿避免。(我将 Noda Time 视为有效的系统库;解析性能对某些客户可能很重要。)
  • 它没有告诉我之后将光标前进多远

实际上,我强烈怀疑这不会经常出现......但我真的很想在这里做正确的事情。我也非常希望能够在不成为 Unicode 专家或自己实现它的情况下做到这一点:)

(在 Noda Time 中作为bug 210提出,以防有人想遵循任何最终结论。)

我喜欢标准化的想法。我需要详细检查 a) 正确性和 b) 性能。假设我可以让它正常工作,我仍然不确定它是否值得全面改变 - 这种事情可能永远不会在现实生活中真正出现,但可能会损害我所有用户的表现: (

我还检查了 BCL - 它似乎也没有正确处理这个问题。示例代码:

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

将自定义月份名称更改为仅具有“bEd”文本值的“床”可以很好地解析。

好的,还有几个数据点:

  • 使用Substringand的成本很高,IsPrefix但并不可怕。在我的开发笔记本电脑上的“2013 年 4 月 12 日星期五 20:28:42”示例中,它将我在一秒钟内可以执行的解析操作的数量从大约 460K 更改为大约 400K。如果可能的话,我宁愿避免这种减速,但这还不错

  • 规范化没有我想象的那么可行——因为它在可移植类库中不可用。我可能将它用于非 PCL 构建,从而允许 PCL 构建不太正确。标准化测试的string.IsNormalized性能损失 ( 我仍然不确定它是否能满足我的所有需求——例如,在许多文化中,包含“ß”的月份名称应该与“ss”匹配,我相信……而规范化并不能做到这一点。

4

3 回答 3

41

我将首先考虑许多<->一个/多个案例映射的问题,并将其与处理不同的规范化形式分开。

例如:

x heiße y
  ^--- cursor

匹配heisse但随后过多地移动光标 1。和:

x heisse y
  ^--- cursor

匹配heiße但随后将光标 1 移动得太少。

这将适用于没有简单的一对一映射的任何角色。

您需要知道实际匹配的子字符串的长度。但是CompareIndexOf..etc 会丢弃这些信息。使用正则表达式可能是可能的,但实现不会完全大小写折叠,因此 即使在不区分大小写模式下ß也不匹配。无论如何,为每个候选人创建新的正则表达式可能会很昂贵。ss/SS.Compare.IndexOf

最简单的解决方案是仅在内部以大小写折叠形式存储字符串,并与大小写候选进行二进制比较。然后您可以正确移动光标,.Length因为光标用于内部表示。您还可以从不必使用CompareOptions.IgnoreCase.

不幸的是,没有内置的 case fold 函数,而穷人的 case fold 也不起作用,因为没有完整的 case 映射 - 该ToUpper方法不会ß变成SS.

例如,这适用于 Java(甚至是 Javascript),给定的字符串是 Normal Form 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);
}

有趣的是,Java 的忽略大小写比较不像 C# 那样进行完全大小写折叠CompareOptions.IgnoreCase。所以他们在这方面是相反的:Java 做了完整的大小写映射,但是简单的大小写折叠——C# 做了简单的大小写映射,但是完整的大小写折叠。

因此,您可能需要一个 3rd 方库在使用它们之前对您的字符串进行大小写折叠。


在做任何事情之前,您必须确保您的字符串是正常的 C 格式。您可以使用针对拉丁脚本优化的初步快速检查:

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 解析/秒,即使它需要在每个字符串上执行。对于误报,您将使用IsNormalized获得真正的负/正,并且仅在必要时进行标准化。


所以综上所述,处理是先保证normal form C,然后case fold。对已处理的字符串进行二进制比较,并在当前移动光标时移动光标。

于 2013-04-14T16:22:54.177 回答
21

看看这是否符合要求..:

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。

于 2013-04-17T14:18:11.193 回答
9

这实际上是可能的,无需规范化且无需使用IsPrefix.

我们需要比较相同数量的文本元素而不是相同数量的字符,但仍然返回匹配字符的数量。

在 Noda Time 中从 ValueCursor.csMatchCaseInsensitive创建了该方法的副本,并对其稍作修改,以便可以在静态上下文中使用它:

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

(仅供参考,这是您所知道的无法正确比较的代码)

该方法的以下变体使用框架提供的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),
};

元组值是:

  1. 源字符串(干草堆)
  2. 源中的起始位置。
  3. 匹配字符串(针)。
  4. 预期的匹配长度。

在这三种方法上运行这些测试会产生以下结果:

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

最后两个测试是测试源字符串比匹配字符串短的情况。在这种情况下,原始(野田时间)方法也将成功。

于 2014-03-19T17:00:20.317 回答