Wie kann ich eine kultursensitive "Starts mit" -Operation aus der Mitte einer Zeichenfolge durchführen?

Question

Ich habe eine Anforderung, die relativ obskur ist, aber es fühlt sich an wie sollte mit dem BCL möglich sein.

Für Kontext, ich analysiere eine Datum/Uhrzeit Zeichenfolge in Noda Time. Ich pflege einen logischen Cursor für meine Position innerhalb der Eingabezeichenfolge. Während also die vollständige Zeichenfolge "3. Januar 2013" sein kann, befindet sich der logische Cursor möglicherweise am "J".

Nun, ich brauche den Monatsnamen zu analysieren, es gegen alle bekannten Monatsnamen für die Kultur zu vergleichen:

• Kultur sensitiv
• Case-unsensibel
• Gerade unter dem Aspekt der Cursor (nicht später, ich sehen will, wenn die Cursor des Kandidaten Monatsnamen „auf der Suche“)
• schnell
• ... und ich muß danach wissen, wie viele Zeichen verwendet wurden

Die current code dies zu tun funktioniert in der Regel mit CompareInfo.Compare. Es ist effektiv wie folgt aus (nur für die passende Teil - es gibt mehr Code in die reale Sache, aber es ist auf das Spiel nicht relevant):

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

jedoch, dass wir die gleichen Vergleich der Kandidaten und die Region verlässt sich sein Länge. Feine die meiste Zeit, aber nicht in einigen Sonderfällen gut. Angenommen, wir haben etwas wie:

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

Jetzt wird mein Vergleich fehlschlagen. Ich konnte IsPrefix verwenden:

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

aber:

• Das hat mich erfordert einen Teil zu erstellen, die ich würde wirklich lieber vermeiden. (Ich sehe Noda Zeit als effektiv eine Systembibliothek,. Leistung Parsen gut zu einigen Kunden wichtig sein kann)
• Es gefällt mir nicht sagen, wie weit Sie die Cursor voran danach

In Wirklichkeit I stark vermuten, dass dies nicht sehr oft kommen wird ... aber ich würde wirklich wie, um das Richtige hier zu tun. Ich würde auch gerne in der Lage sein, es zu tun wirklich ohne einen Unicode-Experten zu werden oder es selbst Umsetzung :)

(Raised als bug 210 in Noda Zeit, jemand im Fall will jeden möglichen Abschluss folgen.)

Ich mag die Idee der Normalisierung. Ich muss das genau überprüfen für a) Korrektheit und b) Leistung.Vorausgesetzt, ich kann machen es richtig funktionieren, bin ich immer noch nicht sicher, ob es wert wäre, über alle zu ändern - es ist die Art von Sache, die wahrscheinlich im wirklichen Leben kommen wird, aber könnte die Leistung von verletzen alle meine Benutzer :(

ich habe auch geprüft, die BCL - die diesen richtig entweder nicht zu handhaben scheinen Beispielcode:

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

den benutzerdefinierten Monatsnamen mit einem nur „Bett“ ändern. Textwert von "bEd" pariert fein.

Okay, ein paar mehr Datenpunkte:

• Die Kosten Substring und IsPrefix der Verwendung ist signifikant, aber nicht schrecklich. Auf einer Probe von "Freitag, den 12. April 2013, 20:28:42" auf meinem Entwicklungs-Laptop ändert sich die Anzahl der Parse-Operationen, die ich in einer Sekunde ausführen kann, von ungefähr 460 K bis ungefähr 400 K. Ich würde diese Verlangsamung lieber vermeiden, aber es ist nicht zu schlecht.

• Normalisierung ist weniger durchführbar, als ich dachte - weil sie nicht in Portable Class Libraries verfügbar ist. Ich könnte es möglicherweise verwenden nur für Nicht-PCL-Builds, so dass die PCL-Builds ein wenig weniger korrekt sein. Der Performance-Hit des Tests für die Normalisierung (string.IsNormalized) nimmt die Leistung auf etwa 445K Anrufe pro Sekunde herunter, womit ich leben kann. Ich bin mir immer noch nicht sicher, ob es alles tut, was ich brauche - zum Beispiel sollte ein Monatsname, der "ß" enthält, in vielen Kulturen "ss" entsprechen, glaube ich ... und normalisieren tut das nicht. > Ein/viele casemappings erste und getrennt von der Handhabung unterschiedlicher Normalisierungsformen -

Answer 1

Ich werde das Problem vieler < betrachten.

Zum Beispiel:

x heiße y 
    ^--- cursor 

Spiele heisse aber dann bewegt den Cursor 1 zu viel. Und:

x heisse y 
    ^--- cursor 

Spiele heiße aber dann bewegt den Cursor 1 zu weniger.

Dies gilt für jedes Zeichen, das keine einfache Eins-zu-Eins-Zuordnung hat.

Sie müssten die Länge der tatsächlich gefundenen Teilzeichenfolge kennen. Aber Compare, IndexOf .. etc werfen Sie diese Informationen weg. Es könnte mit regulären Ausdrücken möglich sein, aber die Implementierung führt keine vollständige Faltung durch und passt daher nicht ß zu ss/SS in Fall-unempfindlichen Modus, obwohl .Compare und .IndexOf tun. Und es wäre wahrscheinlich teuer, für jeden Kandidaten sowieso neue Regexes zu erstellen.

Die einfachste Lösung ist es, Strings im Falle einer gefalteten Form nur intern zu speichern und binäre Vergleiche mit fallgefalteten Kandidaten durchzuführen. Dann können Sie den Cursor korrekt mit nur .Length bewegen, da der Cursor für die interne Darstellung ist.Sie erhalten auch die meisten der verlorenen Leistung zurück von CompareOptions.IgnoreCase nicht zu verwenden.

Leider gibt es keinen Fall Falzfunktion eingebaut und der Fall Faltung des armen Mannes nicht funktioniert, entweder weil es keine vollständige Fall-Mapping - die ToUpper Methode nicht ß in SS dreht.

Zum Beispiel des in Java arbeitet (und sogar in Javascript), gegeben Zeichenfolge, die in Normalform 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); 
} 

Spaß zu beachten, dass Java ignoriert Fall Vergleich nicht voll Fall macht s Falten wie C# ' CompareOptions.IgnoreCase. Sie sind also in dieser Hinsicht entgegengesetzt: Java macht volles Casemapping, aber einfache Fallfaltung - C# macht einfaches Casemapping, aber volles Fallfalten.

Es ist also wahrscheinlich, dass Sie eine 3rd-Party-Bibliothek benötigen, um Ihre Strings zu falten, bevor Sie sie verwenden.

---

Bevor etwas zu tun, Sie müssen sicher sein, dass Ihre Strings in Normalform C. Sie sind diese vorläufige für lateinische Schrift optimiert schnelle Überprüfung verwenden:

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

Dies gibt Fehlalarme aber nicht falsch Negative, ich erwarte nicht, dass es 460k Pars/s verlangsamt, wenn man lateinische Schriftzeichen benutzt, obwohl es für jeden String ausgeführt werden muss. Mit einem falsch positiven Ergebnis würden Sie IsNormalized verwenden, um eine echte negative/positive zu erhalten und erst danach normalisieren, falls erforderlich.

---

Also abschließend ist die Verarbeitung zu gewährleisten, Normalform C zuerst, dann Fall falten. Führen Sie binäre Vergleiche mit den verarbeiteten Strings durch und verschieben Sie den Cursor, während Sie ihn gerade verschieben.

Answer 2

Sehen Sie, wenn dies die Anforderung erfüllt ..:

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 führt nur einmal source begann mit prefix; wenn nicht, dann gibt IsPrefix-1 zurück; Andernfalls wird die Länge der Zeichen in source verwendet.

aber ich habe keine Ahnung, außer Schritt length2 von 1 mit folgendem Fall:

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

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

---

Update:

Ich habe versucht, ein wenig perf zu verbessern, aber. Es ist nicht bewiesen, ob es einen Fehler im folgenden Code gibt:

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

Ich habe mit dem jeweiligen Fall getestet, und der Vergleich bis etwa 3.

Answer 3

Dies ist eigentlich ohne Normalisierung und ohne Verwendung von IsPrefix möglich.

Wir müssen die gleiche Anzahl von Textelemente im Gegensatz zu der gleichen Anzahl von Zeichen vergleichen, aber immer noch die Anzahl der übereinstimmenden Zeichen zurückgeben.

Ich habe eine Kopie der MatchCaseInsensitive Methode von ValueCursor.cs in Noda Time und modifizierte es leicht erstellt, so dass es in einem statischen Kontext verwendet werden kann:

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

(Gerade als Referenz enthalten ist, ist es der Code, der gewonnen 't vergleichen richtig, wie Sie wissen)

Die folgende Variante dieser Methode verwendet StringInfo.GetNextTextElement, die von dem Framework bereitgestellt wird. Die Idee ist, Textelement von Textelement zu vergleichen, um eine Übereinstimmung zu finden, und wenn die tatsächliche Anzahl der passenden Zeichen in der Quellzeichenfolge gefunden zurück:

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

Diese Methode ganz gut zumindest nach meinem Testfall arbeitet (die im Grunde nur ein paar Varianten der Strings, die Sie zur Verfügung gestellt haben: "b\u00e9d" und "be\u0301d").

Die Methode GetNextTextElement erstellt jedoch einen Teilstring für jedes Textelement, sodass diese Implementierung viele Teilstringvergleiche erfordert - was sich auf die Leistung auswirkt.

So, habe ich eine andere Variante, die nicht GetNextTextElement nicht verwendet, sondern überspringt Zeichen Unicode Kombination der tatsächlichen Einstimmungslänge in Zeichen zu finden:

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

Diese Methode verwendet die folgenden zwei Helfer:

Ich habe keine Bankmarkierung gemacht, also weiß ich nicht wirklich, ob die schnellere Methode tatsächlich schneller ist. Ich habe auch keine erweiterten Tests gemacht.

Dies sollte jedoch Ihre Frage beantworten, wie Sie einen kultursensitiven Teilstringvergleich für Strings durchführen, die Unicode-Kombinationszeichen enthalten können.

Dies sind die Testfälle ich verwendet habe:

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

Die Tupel Werte sind:

1. Die Quelle string (Heuhaufen)
2. Die Ausgangsposition in der Quelle.
3. Die Zeichenfolge (Nadel).
4. Die erwartete Übereinstimmungslänge.

diese Tests auf die drei Methoden Laufen ergibt dieses Ergebnis:

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 

Die letzten beiden Tests testen den Fall, wenn die Quellzeichenfolge kürzer als die Vergleichszeichenfolge ist. In diesem Fall wird auch die ursprüngliche (Noda time) Methode erfolgreich sein.