Trier sur une chaîne pouvant contenir un nombre

Je dois écrire une classe Java Comparator qui compare les chaînes, mais avec une torsion. Si les deux chaînes qu’il compare sont les mêmes au début et à la fin de la chaîne sont les mêmes, et la partie centrale qui diffère est un entier, puis se compare en fonction des valeurs numériques de ces entiers. Par exemple, je souhaite que les chaînes suivantes se retrouvent dans l’ordre où elles sont affichées:

  • aaa
  • bbb 3 ccc
  • bbb 12 ccc
  • ccc 11
  • ddd
  • eee 3 ddd jpeg2000 eee
  • eee 12 ddd jpeg2000 eee

Comme vous pouvez le voir, il peut y avoir d’autres entiers dans la chaîne, alors je ne peux pas simplement utiliser des expressions régulières pour séparer des nombres entiers. Je pense juste à marcher les ficelles du début jusqu’à ce que je trouve un peu qui ne correspond pas, puis à marcher de la fin jusqu’à ce que je trouve un peu qui ne correspond pas, puis en comparant le bit au milieu à expression régulière “[0-9] +”, et si elle se compare, puis fait une comparaison numérique, sinon faire une comparaison lexicale.

Y a-t-il une meilleure façon?

Mise à jour Je ne pense pas pouvoir garantir que les autres nombres de la chaîne, ceux qui peuvent correspondre, ne sont pas entourés d’espaces ou que ceux qui sont différents ont des espaces.

L’algorithme Alphanum

Du site web

“Les gens sortingent les chaînes avec des nombres différemment des logiciels. La plupart des algorithmes de sorting comparent les valeurs ASCII, ce qui produit un classement incompatible avec la logique humaine. Voici comment résoudre ce problème.”

Edit: Voici un lien vers l’ implémentation de Java Comparator à partir de ce site.

Petit défi intéressant, j’ai bien aimé le résoudre.

Voici mon sharepoint vue sur le problème:

Ssortingng[] strs = { "eee 5 ddd jpeg2001 eee", "eee 123 ddd jpeg2000 eee", "ddd", "aaa 5 yy 6", "ccc 555", "bbb 3 ccc", "bbb 9 a", "", "eee 4 ddd jpeg2001 eee", "ccc 11", "bbb 12 ccc", "aaa 5 yy 22", "aaa", "eee 3 ddd jpeg2000 eee", "ccc 5", }; Pattern splitter = Pattern.comstack("(\\d+|\\D+)"); public class InternalNumberComparator implements Comparator { public int compare(Object o1, Object o2) { // I deliberately use the Java 1.4 syntax, // all this can be improved with 1.5's generics Ssortingng s1 = (Ssortingng)o1, s2 = (Ssortingng)o2; // We split each ssortingng as runs of number/non-number ssortingngs ArrayList sa1 = split(s1); ArrayList sa2 = split(s2); // Nothing or different structure if (sa1.size() == 0 || sa1.size() != sa2.size()) { // Just compare the original ssortingngs return s1.compareTo(s2); } int i = 0; Ssortingng si1 = ""; Ssortingng si2 = ""; // Compare beginning of ssortingng for (; i < sa1.size(); i++) { si1 = (String)sa1.get(i); si2 = (String)sa2.get(i); if (!si1.equals(si2)) break; // Until we find a difference } // No difference found? if (i == sa1.size()) return 0; // Same strings! // Try to convert the different run of characters to number int val1, val2; try { val1 = Integer.parseInt(si1); val2 = Integer.parseInt(si2); } catch (NumberFormatException e) { return s1.compareTo(s2); // Strings differ on a non-number } // Compare remainder of string for (i++; i < sa1.size(); i++) { si1 = (String)sa1.get(i); si2 = (String)sa2.get(i); if (!si1.equals(si2)) { return s1.compareTo(s2); // Strings differ } } // Here, the strings differ only on a number return val1 < val2 ? -1 : 1; } ArrayList split(String s) { ArrayList r = new ArrayList(); Matcher matcher = splitter.matcher(s); while (matcher.find()) { String m = matcher.group(1); r.add(m); } return r; } } Arrays.sort(strs, new InternalNumberComparator()); 

Cet algorithme nécessite beaucoup plus de tests, mais il semble se comporter plutôt bien.

[EDIT] J'ai ajouté quelques commentaires pour être plus clair. Je vois qu'il y a beaucoup plus de réponses que lorsque j'ai commencé à coder ceci… Mais j'espère avoir fourni une bonne base de départ et / ou quelques idées.

Ian Griffiths de Microsoft a une implémentation C # qu’il appelle Natural Sorting . Le portage vers Java devrait être assez facile, plus facile que celui de C de toute façon!

MISE À JOUR: Il semble y avoir un exemple Java sur eekboom qui fait cela, voir “compareNatural” et l’utiliser comme votre comparateur de sorting.

Je me rends compte que vous êtes en Java, mais vous pouvez voir comment fonctionne StrCmpLogicalW. C’est ce que l’explorateur utilise pour sortinger les noms de fichiers dans Windows. Vous pouvez regarder la mise en œuvre de WINE ici .

La mise en œuvre que je propose ici est simple et efficace. Il n’alloue pas de mémoire supplémentaire, directement ou indirectement, à l’aide d’expressions régulières ou de méthodes telles que subssortingng (), split (), toCharArray (), etc.

Cette implémentation passe d’abord par les deux chaînes pour rechercher les premiers caractères différents, à vitesse maximale, sans effectuer de traitement particulier au cours de cette opération. La comparaison de numéros spécifiques est déclenchée uniquement lorsque ces caractères sont les deux chiffres. Un effet secondaire de cette implémentation est qu’un chiffre est considéré comme plus grand que les autres lettres, contrairement à l’ordre lexicographique par défaut.

 public static final int compareNatural (Ssortingng s1, Ssortingng s2) { // Skip all identical characters int len1 = s1.length(); int len2 = s2.length(); int i; char c1, c2; for (i = 0, c1 = 0, c2 = 0; (i < len1) && (i < len2) && (c1 = s1.charAt(i)) == (c2 = s2.charAt(i)); i++); // Check end of string if (c1 == c2) return(len1 - len2); // Check digit in first string if (Character.isDigit(c1)) { // Check digit only in first string if (!Character.isDigit(c2)) return(1); // Scan all integer digits int x1, x2; for (x1 = i + 1; (x1 < len1) && Character.isDigit(s1.charAt(x1)); x1++); for (x2 = i + 1; (x2 < len2) && Character.isDigit(s2.charAt(x2)); x2++); // Longer integer wins, first digit otherwise return(x2 == x1 ? c1 - c2 : x1 - x2); } // Check digit only in second string if (Character.isDigit(c2)) return(-1); // No digits return(c1 - c2); } 

Divisez la chaîne en séries de lettres et de chiffres, de sorte que “foo 12 bar” devienne la liste (“foo”, 12, “bar”), puis utilisez la liste comme clé de sorting. De cette façon, les numéros seront classés par ordre numérique et non par ordre alphabétique.

Je suis arrivé avec une implémentation assez simple en Java en utilisant des expressions régulières:

 public static Comparator naturalOrdering() { final Pattern comstack = Pattern.comstack("(\\d+)|(\\D+)"); return (s1, s2) -> { final Matcher matcher1 = comstack.matcher(s1); final Matcher matcher2 = comstack.matcher(s2); while (true) { final boolean found1 = matcher1.find(); final boolean found2 = matcher2.find(); if (!found1 || !found2) { return Boolean.compare(found1, found2); } else if (!matcher1.group().equals(matcher2.group())) { if (matcher1.group(1) == null || matcher2.group(1) == null) { return matcher1.group().compareTo(matcher2.group()); } else { return Integer.valueOf(matcher1.group(1)).compareTo(Integer.valueOf(matcher2.group(1))); } } } }; } 

Voici comment cela fonctionne:

 final List ssortingngs = Arrays.asList("x15", "xa", "y16", "x2a", "y11", "z", "z5", "x2b", "z"); ssortingngs.sort(naturalOrdering()); System.out.println(ssortingngs); 

[x2a, x2b, x15, xa, y11, y16, z, z, z5]

Le Alphanum algrothim est bien, mais il ne correspond pas aux exigences d’un projet sur lequel je travaille. Je dois pouvoir sortinger correctement les nombres négatifs et les décimales. Voici l’implémentation que j’ai faite. Tout retour serait apprécié.

 public class SsortingngAsNumberComparator implements Comparator { public static final Pattern NUMBER_PATTERN = Pattern.comstack("(\\-?\\d+\\.\\d+)|(\\-?\\.\\d+)|(\\-?\\d+)"); /** * Splits ssortingngs into parts sorting each instance of a number as a number if there is * a matching number in the other Ssortingng. * * For example A1B, A2B, A11B, A11B1, A11B2, A11B11 will be sorted in that order instead * of alphabetically which will sort A1B and A11B together. */ public int compare(Ssortingng str1, Ssortingng str2) { if(str1 == null || str2 == null) { return 0; } List split1 = split(str1); List split2 = split(str2); int diff = 0; for(int i = 0; diff == 0 && i < split1.size() && i < split2.size(); i++) { String token1 = split1.get(i); String token2 = split2.get(i); if((NUMBER_PATTERN.matcher(token1).matches() && NUMBER_PATTERN.matcher(token2).matches()) { diff = (int) Math.signum(Double.parseDouble(token1) - Double.parseDouble(token2)); } else { diff = token1.compareToIgnoreCase(token2); } } if(diff != 0) { return diff; } else { return split1.size() - split2.size(); } } /** * Splits a string into strings and number tokens. */ private List split(Ssortingng s) { List list = new ArrayList(); try (Scanner scanner = new Scanner(s)) { int index = 0; Ssortingng num = null; while ((num = scanner.findInLine(NUMBER_PATTERN)) != null) { int indexOfNumber = s.indexOf(num, index); if (indexOfNumber > index) { list.add(s.subssortingng(index, indexOfNumber)); } list.add(num); index = indexOfNumber + num.length(); } if (index < s.length()) { list.add(s.substring(index)); } } return list; } } 

PS Je voulais utiliser la méthode java.lang.Ssortingng.split () et utiliser "lookahead / lookbehind" pour conserver les jetons, mais je ne pouvais pas le faire fonctionner avec l'expression régulière que j'utilisais.

problème intéressant, et voici ma solution proposée:

 import java.util.Collections; import java.util.Vector; public class CompareToken implements Comparable { int valN; Ssortingng valS; Ssortingng repr; public Ssortingng toSsortingng() { return repr; } public CompareToken(Ssortingng s) { int l = 0; char data[] = new char[s.length()]; repr = s; valN = 0; for (char c : s.toCharArray()) { if(Character.isDigit(c)) valN = valN * 10 + (c - '0'); else data[l++] = c; } valS = new Ssortingng(data, 0, l); } public int compareTo(CompareToken b) { int r = valS.compareTo(b.valS); if (r != 0) return r; return valN - b.valN; } public static void main(Ssortingng [] args) { Ssortingng [] ssortingngs = { "aaa", "bbb3ccc", "bbb12ccc", "ccc 11", "ddd", "eee3dddjpeg2000eee", "eee12dddjpeg2000eee" }; Vector data = new Vector(); for(Ssortingng s : ssortingngs) data.add(new CompareToken(s)); Collections.shuffle(data); Collections.sort(data); for (CompareToken c : data) System.out.println ("" + c); } } 

Avant de découvrir ce sujet, j’ai implémenté une solution similaire en JavaScript. Peut-être que ma stratégie vous trouvera bien, malgré une syntaxe différente. Comme ci-dessus, j’parsing les deux chaînes en cours de comparaison et les divise toutes deux en tableaux, en divisant les chaînes en nombres continus.

 ... var regex = /(\d+)/g, str1Components = str1.split(regex), str2Components = str2.split(regex), ... 

Ie, ‘hello22goodbye 33’ => [‘hello’, 22, ‘au revoir’, 33]; Ainsi, vous pouvez parcourir les éléments des tableaux par paires entre ssortingng1 et ssortingng2, faire de la coercition (par exemple, cet élément est-il vraiment un nombre?), Et comparer à mesure que vous marchez.

Exemple de travail ici: http://jsfiddle.net/F46s6/3/

Notez que je ne supporte actuellement que les types entiers, bien que la gestion des valeurs décimales ne soit pas trop difficile à modifier.

Mes 2 centimes. Je travaille bien pour moi. Je l’utilise principalement pour les noms de fichiers.

  private final boolean isDigit(char ch) { return ch >= 48 && ch <= 57; } private int compareNumericalString(String s1,String s2){ int s1Counter=0; int s2Counter=0; while(true){ if(s1Counter>=s1.length()){ break; } if(s2Counter>=s2.length()){ break; } char currentChar1=s1.charAt(s1Counter++); char currentChar2=s2.charAt(s2Counter++); if(isDigit(currentChar1) &&isDigit(currentChar2)){ Ssortingng digitSsortingng1=""+currentChar1; Ssortingng digitSsortingng2=""+currentChar2; while(true){ if(s1Counter>=s1.length()){ break; } if(s2Counter>=s2.length()){ break; } if(isDigit(s1.charAt(s1Counter))){ digitSsortingng1+=s1.charAt(s1Counter); s1Counter++; } if(isDigit(s2.charAt(s2Counter))){ digitSsortingng2+=s2.charAt(s2Counter); s2Counter++; } if((!isDigit(s1.charAt(s1Counter))) && (!isDigit(s2.charAt(s2Counter)))){ currentChar1=s1.charAt(s1Counter); currentChar2=s2.charAt(s2Counter); break; } } if(!digitSsortingng1.equals(digitSsortingng2)){ return Integer.parseInt(digitSsortingng1)-Integer.parseInt(digitSsortingng2); } } if(currentChar1!=currentChar2){ return currentChar1-currentChar2; } } return s1.compareTo(s2); } 

Je pense que vous devrez faire la comparaison sur une base de caractère par personnage. Prenez un personnage, si c’est un caractère numérique, continuez à saisir, puis ré-assemblez les caractères en une seule chaîne numérique et convertissez-les en int . Répétez l’opération sur l’autre chaîne et faites seulement la comparaison.

Réponse courte: sur la base du contexte, je ne peux pas dire s’il s’agit simplement d’un code rapide pour un usage personnel, ou d’un élément clé du dernier logiciel de comptabilité interne de Goldman Sachs. . C’est un algorithme de sorting plutôt funky; essayez d’utiliser quelque chose de moins “tordu” si vous le pouvez.

Longue réponse:

Les deux problèmes qui viennent immédiatement à l’esprit dans votre cas sont la performance et l’exactitude. De manière informelle, assurez-vous que c’est rapide et assurez-vous que votre algorithme est un ordre total .

(Bien sûr, si vous ne sortingez pas plus de 100 éléments, vous pouvez probablement ignorer ce paragraphe.) Les performances sont importantes, car la vitesse du comparateur sera le facteur le plus important de la vitesse de votre sorting (en supposant que l’algorithme de sorting est “idéal” à la liste typique). Dans votre cas, la vitesse du comparateur dépendra principalement de la taille de la chaîne. Les chaînes semblent être assez courtes, donc elles ne domineront probablement pas autant que la taille de votre liste.

En transformant chaque chaîne en un tuple de chaîne de caractères, puis en sortingant cette liste de tuples, comme cela est suggéré dans une autre réponse, vous échouerez dans certains cas, car vous aurez apparemment des chaînes avec plusieurs numéros.

L’autre problème est la correction. Plus précisément, si l’algorithme que vous avez décrit autorisera jamais A> B> …> A, votre sorting sera non déterministe. Dans ton cas, je crains que cela ne se produise, même si je ne peux pas le prouver. Considérez certains cas d’parsing tels que:

  aa 0 aa aa 23aa aa 2a3aa aa 113aa aa 113 aa a 1-2 a a 13 a a 12 a a 2-3 a a 21 a a 2.3 a 

Bien que la question demandait une solution Java, pour quiconque veut une solution Scala:

 object Alphanum { private[this] val regex = "((?<=[0-9])(?=[^0-9]))|((?<=[^0-9])(?=[0-9]))" private[this] val alphaNum: Ordering[String] = Ordering.fromLessThan((ss1: String, ss2: String) => (ss1, ss2) match { case (sss1, sss2) if sss1.matches("[0-9]+") && sss2.matches("[0-9]+") => sss1.toLong < sss2.toLong case (sss1, sss2) => sss1 < sss2 }) def ordering: Ordering[String] = Ordering.fromLessThan((s1: String, s2: String) => { import Ordering.Implicits.infixOrderingOps implicit val ord: Ordering[List[Ssortingng]] = Ordering.Implicits.seqDerivedOrdering(alphaNum) s1.split(regex).toList < s2.split(regex).toList }) } 

Dans votre exemple, les nombres que vous voulez comparer ont des espaces autour d’eux, alors que les autres ne le font pas, alors pourquoi une expression régulière ne fonctionnerait-elle pas?

bbb 12 ccc

contre.

eee 12 ddd jpeg2000 eee

Si vous écrivez une classe de comparaison, vous devez implémenter votre propre méthode de comparaison qui compare deux caractères de caractère par caractère. Cette méthode de comparaison doit vérifier si vous traitez des caractères alphabétiques, des caractères numériques ou des types mixtes (espaces compris). Vous devrez définir comment un type mixte doit agir, que les nombres viennent avant les caractères alphabétiques ou après, et que les espaces soient adaptés, etc.

Sous Linux, glibc fournit strverscmp (), également disponible à partir de gnulib pour la portabilité. Cependant, un véritable sorting “humain” a beaucoup d’autres particularités comme “The Beatles” qui sont classées comme “Beatles, The”. Il n’y a pas de solution simple à ce problème générique.