Trier sur une chaîne de caractères qui peut contenir un nombre

Question

J'ai besoin d'écrire une classe Java Comparator qui compare des chaînes de caractères, mais avec une particularité. Si les deux chaînes de caractères qu'elle compare sont identiques au début et à la fin de la chaîne, et que la partie centrale qui diffère est un nombre entier, alors elle compare sur la base des valeurs numériques de ces nombres entiers. Par exemple, je veux que les chaînes de caractères 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 nombres entiers dans la chaîne, et je ne peux donc pas utiliser des expressions régulières pour extraire n'importe quel nombre entier. Je pense simplement parcourir les chaînes depuis le début jusqu'à ce que je trouve un bit qui ne correspond pas, puis parcourir depuis la fin jusqu'à ce que je trouve un bit qui ne correspond pas, puis comparer le bit du milieu à l'expression régulière "[0-9]+", et s'il y a comparaison, faire une comparaison numérique, sinon faire une comparaison lexicale.

Y a-t-il un meilleur moyen ?

Mise à jour Je ne pense pas pouvoir garantir que les autres chiffres de la chaîne, ceux qui peuvent correspondre, n'ont pas d'espaces autour d'eux, ou que ceux qui diffèrent ont des espaces.

Answer 1

L'algorithme Alphanum

Extrait du site web

"Les gens trient les chaînes de caractères avec des chiffres différemment des logiciels. La plupart des algorithmes de tri comparent les valeurs ASCII, ce qui produit un ordre qui n'est pas conforme à la logique humaine. Voici comment y remédier."

Edit : Voici un lien vers le Mise en œuvre du comparateur Java de ce site.

Answer 2

Petit défi intéressant, j'ai pris plaisir à le résoudre.

Voici ma vision du problème :

String[] 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.compile("(\\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
    String s1 = (String)o1, s2 = (String)o2;
    // We split each string as runs of number/non-number strings
    ArrayList sa1 = split(s1);
    ArrayList sa2 = split(s2);
    // Nothing or different structure
    if (sa1.size() == 0 || sa1.size() != sa2.size())
    {
      // Just compare the original strings
      return s1.compareTo(s2);
    }
    int i = 0;
    String si1 = "";
    String si2 = "";
    // Compare beginning of string
    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 doit être testé plus en profondeur, 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.

Answer 3

Ian Griffiths de Microsoft a une implémentation C# qu'il appelle Triage naturel . Le portage vers Java devrait être assez facile, plus facile que depuis le C en tout cas !

UPDATE : Il semble y avoir un exemple Java sur eekboom qui fait cela, voyez le "compareNatural" et utilisez-le comme votre comparateur pour trier.

Answer 4

Je réalise que vous êtes en Java, mais vous pouvez regarder comment StrCmpLogicalW fonctionne. C'est ce que l'Explorer utilise pour trier les noms de fichiers dans Windows. Vous pouvez regarder l'implémentation de WINE aquí .

Answer 5

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 tri. De cette façon, les chiffres seront classés par ordre numérique, et non par ordre alphabétique.