Ecrire un meilleur tri naturel (que le mien)

Question

J'ai ajouté une réponse à cette question ici: Sorting List<String> in C# qui appelle un ordre de tri naturel, un qui gère les nombres incorporés. Ma mise en œuvre, cependant, est naïve, et au lieu de tous les messages sur la façon dont les applications ne gèrent pas Unicode correctement en supposant des choses (test de Turquie quelqu'un?), Je pensais que je demanderais de l'aide pour écrire un meilleure mise en œuvre. Ou, s'il existe une méthode intégrée de .NET, s'il vous plaît dites-moi :)

Mon implémentation pour la réponse dans cette question passe juste par les chaînes, en comparant caractère par caractère, jusqu'à ce qu'il rencontre un chiffre dans les deux. Ensuite, il extrait les chiffres consécutifs des deux chaînes, ce qui peut entraîner des longueurs variables, des tampons les plus courts avec les zéros de tête, puis les compare.

Cependant, il y a des problèmes avec cela. Par exemple, que se passe-t-il si vous avez dans la chaîne x deux points de code qui forment ensemble le caractère È, mais dans l'autre chaîne vous avez un seul code, celui qui est ce caractère.

Mon algorithme échouerait sur ceux-ci, car il traiterait le codepoint diacritique comme un seul caractère, et le comparerait au È de l'autre chaîne.

Quelqu'un peut-il me guider vers la façon de gérer correctement? Je veux un support pour spécifier un objet CultureInfo pour gérer des problèmes de langage, comme comparer "ss" avec "ß" en Allemagne, et des choses similaires.

Je pense que j'ai besoin d'obtenir mon code pour énumérer les "caractères réels" (je ne connais pas le terme réel ici) au lieu des points de code individuels.

Quelle est la bonne approche?

En outre, si « naturel » signifie « l'homme moyen attendent de travailler », je voudrais ajouter les choses suivantes à méditer:

• Qu'en est-dates et heures?
• Qu'en est-il des valeurs à virgule flottante?
• Existe-t-il d'autres séquences considérées comme «naturelles»?
  • Jusqu'où cela devrait-il être étiré? (Am Stram Gram)

Answer 1

Ceci est déjà disponible dans Windows, le shell utilise un ordre de tri naturel lors de l'organisation des fichiers dans une fenêtre de l'Explorateur. La fonction de comparaison utilisée est exportée et disponible pour tout programme, au moins depuis Windows 2000. Alors que P/Invoke n'est pas la meilleure solution, elle a l'avantage considérable d'avoir été testée des milliards de fois au cours des 10 dernières années. Et trier les chaînes d'une manière que l'utilisateur connaît déjà bien.

La gestion des signes diacritiques fait déjà partie de .NET, la méthode string.Normalize() en prend soin.

Voici un exemple de programme qui l'utilise, il trie correctement les chaînes comme demandé dans le fil d'origine:

using System; 
using System.Collections.Generic; 
using System.Runtime.InteropServices; 

class Program { 
    static void Main(string[] args) { 
     string[] arr = new string[] { "1", "5", "3", "6", "11", "9", "NUM1", "NUM0" }; 
     Array.Sort(arr, new LogicalComparer()); 
     foreach (string s in arr) Console.WriteLine(s); 
     Console.ReadLine(); 
    } 
} 
class LogicalComparer : IComparer<string> { 
    public int Compare(string x, string y) { 
     return StrCmpLogicalW(x.Normalize(), y.Normalize()); 
    } 
    [DllImport("shlwapi.dll", CharSet = CharSet.Unicode, ExactSpelling = true)] 
    private static extern int StrCmpLogicalW(string s1, string s2); 
} 

Answer 2

Je ne sais pas beaucoup sur .NET, mais comme il est aussi une question algorithmiques, voici mes deux cents:

Je vais essayer diviser la chaîne en jetons, probablement en utilisant des expressions régulières. Ensuite, vous pouvez comparer le jeton de chaînes par jeton, en utilisant une fonction de comparaison appropriée en fonction du type de jeton.

Plus précisément:

1. Définir des expressions régulières pour les dates, les chiffres, les mots, ... Le dernier de ceux-ci devraient être une expression qui correspond à tout fallback caractère.
2. Essayez chaque expression, la plus spécifique en premier, jusqu'à ce que l'une d'entre elles corresponde au début des deux chaînes
3. Extrayez la pièce correspondant et comparez-la à l'aide de la fonction de comparaison appropriée.
4. En cas d'égalité, enlever le match dès le début des deux chaînes et recommencer depuis l'étape 2.

En utilisant des expressions régulières, il devrait également être possible de soutenir unicode, si vous n'utilisez pas [a-zA-Z] mais bon classes de caractères comme [:alpha:]. En ce qui concerne la comparaison des différentes formes de È, vous pouvez essayer de commencer par la chaîne normalize.