2009-08-11 11 views
65

Me gustaría tener algún tipo de función de comparación de cadenas que preserve el orden natural . ¿Hay algo como esto integrado en Java? No puedo encontrar nada en el String class, y el Comparator class solo conoce dos implementaciones.Comparación de cadenas de orden de clasificación natural en Java: ¿está integrado?

Puedo hacer mi propia versión (no es un problema muy difícil), pero prefiero no volver a inventar la rueda si no es necesario.

En mi caso específico, tengo cadenas de versiones de software que quiero ordenar. Entonces quiero que "1.2.10.5" se considere mayor que "1.2.9.1".


Por orden "natural", quiero decir que compara las cadenas de la forma en que un humano podría compararlos, en lugar de ordenar especie "ascii-BETICAL" que sólo tiene sentido para los programadores. En otras palabras, "image9.jpg" es menor que "image10.jpg", y "album1set2page9photo1.jpg" es menor que "album1set2page10photo5.jpg", y "1.2.9.1" es menor que "1.2.10.5"

+0

divertido, todo el mundo - volver a leer la pregunta y eliminar las respuestas publicadas !! .. :) ¡Creo que este es el poder de DOWNVOTE! :);) – OscarRyz

+2

BTW. Numérico no es el orden natural cuando se habla de cadenas, por lo que la pregunta es un poco engañosa. – OscarRyz

+1

Nada de eso incluido en mi conocimiento. Cuando se codifica toma menos tiempo que pedir SO, generalmente corro para mi propia rueda ... :) – glmxndr

Respuesta

49

en Java el significado "natural" orden es orden "lexicográfico", por lo que no hay ninguna aplicación en el núcleo como el que usted está buscando para.

Hay implementaciones de código abierto.

Aquí hay uno:

NaturalOrderComparator.java

Asegúrese de leer el:

Cougaar Open Source License

espero que esto ayude!

+0

gracias. revisé la pregunta para aclarar lo que quise decir con "natural" – Kip

+1

Me encanta SO, solo hurgando al azar, y aquí hay una solución rápida a algo que he pospuesto durante la última semana. Ese es un enlace muy útil, ¡gracias! (Y la licencia es compatible con nuestro proyecto) –

+4

Al elegir una implementación de código abierto como esta, debe asegurarse de que hagan exactamente lo que esperaban. Muchos se centran en proporcionar un orden que se ve intuitivo y bonito en una interfaz de usuario. A veces aceptan y saltan espacios en blanco, omiten ceros a la izquierda y lo más importante coloca cadenas más cortas antes de cadenas más largas cuando son equivalentes. La cadena 1.020 se colocará después de 1.20. Si lo está usando para determinar si dos versiones son iguales, puede obtener un falso negativo en este caso. Es decir. cuando compruebo que compareTo() devuelve 0. – sigget

8

Implementos de cadenas Comparable, y eso es lo que el ordenamiento natural es en Java (comparando el uso de la interfaz comparable). Puede colocar las cadenas en un TreeSet u ordenar usando las clases Collections o Array.

Sin embargo, en su caso no desea "ordenamiento natural" que realmente desea un comparador personalizado, que luego puede utilizar en el método Collections.sort o el método Arrays.sort que toma un comparador.

En términos de la lógica específica que está buscando implementar dentro del comparador, (números separados por puntos) no conozco ninguna implementación estándar existente de eso, pero como dijo, no es un problema difícil.

EDITAR: En su comentario, su enlace obtiene here, que hace un trabajo decente si no le molesta el hecho de que es sensible a mayúsculas y minúsculas. Aquí está el código modificado para permitir que pase en el String.CASE_INSENSITIVE_ORDER:

/* 
    * The Alphanum Algorithm is an improved sorting algorithm for strings 
    * containing numbers. Instead of sorting numbers in ASCII order like 
    * a standard sort, this algorithm sorts numbers in numeric order. 
    * 
    * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com 
    * 
    * 
    * This library is free software; you can redistribute it and/or 
    * modify it under the terms of the GNU Lesser General Public 
    * License as published by the Free Software Foundation; either 
    * version 2.1 of the License, or any later version. 
    * 
    * This library is distributed in the hope that it will be useful, 
    * but WITHOUT ANY WARRANTY; without even the implied warranty of 
    * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 
    * Lesser General Public License for more details. 
    * 
    * You should have received a copy of the GNU Lesser General Public 
    * License along with this library; if not, write to the Free Software 
    * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 
    * 
    */ 

    import java.util.Comparator; 

    /** 
    * This is an updated version with enhancements made by Daniel Migowski, 
    * Andre Bogus, and David Koelle 
    * 
    * To convert to use Templates (Java 1.5+): 
    * - Change "implements Comparator" to "implements Comparator<String>" 
    * - Change "compare(Object o1, Object o2)" to "compare(String s1, String s2)" 
    * - Remove the type checking and casting in compare(). 
    * 
    * To use this class: 
    * Use the static "sort" method from the java.util.Collections class: 
    * Collections.sort(your list, new AlphanumComparator()); 
    */ 
    public class AlphanumComparator implements Comparator<String> 
    { 
     private Comparator<String> comparator = new NaturalComparator(); 

     public AlphanumComparator(Comparator<String> comparator) { 
      this.comparator = comparator; 
     } 

     public AlphanumComparator() { 

     } 

     private final boolean isDigit(char ch) 
     { 
      return ch >= 48 && ch <= 57; 
     } 

     /** Length of string is passed in for improved efficiency (only need to calculate it once) **/ 
     private final String getChunk(String s, int slength, int marker) 
     { 
      StringBuilder chunk = new StringBuilder(); 
      char c = s.charAt(marker); 
      chunk.append(c); 
      marker++; 
      if (isDigit(c)) 
      { 
       while (marker < slength) 
       { 
        c = s.charAt(marker); 
        if (!isDigit(c)) 
         break; 
        chunk.append(c); 
        marker++; 
       } 
      } else 
      { 
       while (marker < slength) 
       { 
        c = s.charAt(marker); 
        if (isDigit(c)) 
         break; 
        chunk.append(c); 
        marker++; 
       } 
      } 
      return chunk.toString(); 
     } 

     public int compare(String s1, String s2) 
     { 

      int thisMarker = 0; 
      int thatMarker = 0; 
      int s1Length = s1.length(); 
      int s2Length = s2.length(); 

      while (thisMarker < s1Length && thatMarker < s2Length) 
      { 
       String thisChunk = getChunk(s1, s1Length, thisMarker); 
       thisMarker += thisChunk.length(); 

       String thatChunk = getChunk(s2, s2Length, thatMarker); 
       thatMarker += thatChunk.length(); 

       // If both chunks contain numeric characters, sort them numerically 
       int result = 0; 
       if (isDigit(thisChunk.charAt(0)) && isDigit(thatChunk.charAt(0))) 
       { 
        // Simple chunk comparison by length. 
        int thisChunkLength = thisChunk.length(); 
        result = thisChunkLength - thatChunk.length(); 
        // If equal, the first different number counts 
        if (result == 0) 
        { 
         for (int i = 0; i < thisChunkLength; i++) 
         { 
          result = thisChunk.charAt(i) - thatChunk.charAt(i); 
          if (result != 0) 
          { 
           return result; 
          } 
         } 
        } 
       } else 
       { 
        result = comparator.compare(thisChunk, thatChunk); 
       } 

       if (result != 0) 
        return result; 
      } 

      return s1Length - s2Length; 
     } 

     private static class NaturalComparator implements Comparator<String> { 
      public int compare(String o1, String o2) { 
       return o1.compareTo(o2); 
      } 
     } 
    } 
+6

"Clasificación natural" es el término ampliamente utilizado para clasificar "image9. jpg "como menos que" image10.jpg ". es "natural" porque así es como los clasificaría un ser humano, a diferencia de la clasificación antinatural "ascii-betical" que hacen las computadoras por defecto. http://www.codinghorror.com/blog/archives/001018.html – Kip

+0

He actualizado la pregunta para ser más claro al respecto – Kip

+0

En el enlace codinghorror que publica, tiene un enlace que llega a esto, que tiene una implementación de Java: http://www.davekoelle.com/alphanum.html – Yishai

9

He probado tres implementaciones de Java mencionadas aquí por otros y encontré que su trabajo es ligeramente diferente pero ninguno como era de esperar.

Tanto AlphaNumericStringComparator y AlphanumComparator no ignoran los espacios en blanco de manera que se coloca antes de pic2pic 1.

Por otro lado NaturalOrderComparator ignora no solo los espacios en blanco sino también todos los ceros a la izquierda para que sig[1] preceda a sig[0].

En cuanto al rendimiento AlphaNumericStringComparator es ~ x10 más lento que los otros dos.

+0

tiene que ser así, ya que AlphaNumericStringComparator está usando regex (que de todos modos es una mala idea) –

2

¿Qué le parece usar el método split() de String, analizar la cadena numérica y compararlos uno por uno?

@Test 
public void test(){ 
    System.out.print(compare("1.12.4".split("\\."), "1.13.4".split("\\."),0)); 
} 


public static int compare(String[] arr1, String[] arr2, int index){ 
    // if arrays do not have equal size then and comparison reached the upper bound of one of them 
    // then the longer array is considered the bigger (--> 2.2.0 is bigger then 2.2) 
    if(arr1.length <= index || arr2.length <= index) return arr1.length - arr2.length; 
    int result = Integer.parseInt(arr1[index]) - Integer.parseInt(arr2[index]); 
    return result == 0 ? compare(arr1, arr2, ++index) : result; 
} 

no el registro de los casos de esquina, pero que debería funcionar y es bastante compacto

+0

esto es más limitado: solo maneja cadenas que son listas de números de números enteros. Me gustaría comparar "user1album12photo4.jpg" a "user1album13photo4.jpg" – Kip

+0

cierto ... solo me enfoqué en las cadenas de versión del software. lo siento, pero aún así, personalmente me gusta la solución – bennidi

1

Se concats los dígitos, a continuación, compara. Y si no es aplicable, continúa.

public int compare(String o1, String o2) { 
if(o1 == null||o2 == null) 
    return 0; 
for(int i = 0; i<o1.length()&&i<o2.length();i++){ 
    if(Character.isDigit(o1.charAt(i)) || Character.isDigit(o2.charAt(i))) 
    { 
    String dig1 = "",dig2 = "";  
    for(int x = i; x<o1.length() && Character.isDigit(o1.charAt(i)); x++){        
     dig1+=o1.charAt(x); 
    } 
    for(int x = i; x<o2.length() && Character.isDigit(o2.charAt(i)); x++){ 
     dig2+=o2.charAt(x); 
    } 
    if(Integer.valueOf(dig1) < Integer.valueOf(dig2)) 
     return -1; 
    if(Integer.valueOf(dig1) > Integer.valueOf(dig2)) 
     return 1; 
    }  
if(o1.charAt(i)<o2.charAt(i)) 
    return -1; 
if(o1.charAt(i)>o2.charAt(i)) 
    return 1; 
} 
return 0; 

}

0

podría ser una respuesta tardía. Pero mi respuesta puede ayudar a alguien más que necesita un comparador como este.

He verificado algunos otros comparadores también. Pero el mío parece poco eficiente que otros que comparé. También probé la que Yishai ha publicado. El mío solo toma la mitad del tiempo que el mencionado para los datos del conjunto de datos alfanuméricos de 100 entradas.

/** 
* Sorter that compares the given Alpha-numeric strings. This iterates through each characters to 
* decide the sort order. There are 3 possible cases while iterating, 
* 
* <li>If both have same non-digit characters then the consecutive characters will be considered for 
* comparison.</li> 
* 
* <li>If both have numbers at the same position (with/without non-digit characters) the consecutive 
* digit characters will be considered to form the valid integer representation of the characters 
* will be taken and compared.</li> 
* 
* <li>At any point if the comparison gives the order(either > or <) then the consecutive characters 
* will not be considered.</li> 
* 
* For ex., this will be the ordered O/P of the given list of Strings.(The bold characters decides 
* its order) <i><b>2</b>b,<b>100</b>b,a<b>1</b>,A<b>2</b>y,a<b>100</b>,</i> 
* 
* @author kannan_r 
* 
*/ 
class AlphaNumericSorter implements Comparator<String> 
{ 
    /** 
    * Does the Alphanumeric sort of the given two string 
    */ 
    public int compare(String theStr1, String theStr2) 
    { 
     char[] theCharArr1 = theStr1.toCharArray(); 
     char[] theCharArr2 = theStr2.toCharArray(); 
     int aPosition = 0; 
     if (Character.isDigit(theCharArr1[aPosition]) && Character.isDigit(theCharArr2[aPosition])) 
     { 
      return sortAsNumber(theCharArr1, theCharArr2, aPosition++); 
     } 
     return sortAsString(theCharArr1, theCharArr2, 0); 
    } 

    /** 
    * Sort the given Arrays as string starting from the given position. This will be a simple case 
    * insensitive sort of each characters. But at any given position if there are digits in both 
    * arrays then the method sortAsNumber will be invoked for the given position. 
    * 
    * @param theArray1 The first character array. 
    * @param theArray2 The second character array. 
    * @param thePosition The position starting from which the calculation will be done. 
    * @return positive number when the Array1 is greater than Array2<br/> 
    *   negative number when the Array2 is greater than Array1<br/> 
    *   zero when the Array1 is equal to Array2 
    */ 
    private int sortAsString(char[] theArray1, char[] theArray2, int thePosition) 
    { 
     int aResult = 0; 
     if (thePosition < theArray1.length && thePosition < theArray2.length) 
     { 
      aResult = (int)theArray1[thePosition] - (int)theArray2[thePosition]; 
      if (aResult == 0) 
      { 
       ++thePosition; 
       if (thePosition < theArray1.length && thePosition < theArray2.length) 
       { 
        if (Character.isDigit(theArray1[thePosition]) && Character.isDigit(theArray2[thePosition])) 
        { 
         aResult = sortAsNumber(theArray1, theArray2, thePosition); 
        } 
        else 
        { 
         aResult = sortAsString(theArray1, theArray2, thePosition); 
        } 
       } 
      } 
     } 
     else 
     { 
      aResult = theArray1.length - theArray2.length; 
     } 
     return aResult; 
    } 

    /** 
    * Sorts the characters in the given array as number starting from the given position. When 
    * sorted as numbers the consecutive characters starting from the given position upto the first 
    * non-digit character will be considered. 
    * 
    * @param theArray1 The first character array. 
    * @param theArray2 The second character array. 
    * @param thePosition The position starting from which the calculation will be done. 
    * @return positive number when the Array1 is greater than Array2<br/> 
    *   negative number when the Array2 is greater than Array1<br/> 
    *   zero when the Array1 is equal to Array2 
    */ 
    private int sortAsNumber(char[] theArray1, char[] theArray2, int thePosition) 
    { 
     int aResult = 0; 
     int aNumberInStr1; 
     int aNumberInStr2; 
     if (thePosition < theArray1.length && thePosition < theArray2.length) 
     { 
      if (Character.isDigit(theArray1[thePosition]) && Character.isDigit(theArray1[thePosition])) 
      { 
       aNumberInStr1 = getNumberInStr(theArray1, thePosition); 
       aNumberInStr2 = getNumberInStr(theArray2, thePosition); 

       aResult = aNumberInStr1 - aNumberInStr2; 

       if (aResult == 0) 
       { 
        thePosition = getNonDigitPosition(theArray1, thePosition); 
        if (thePosition != -1) 
        { 
         aResult = sortAsString(theArray1, theArray2, thePosition); 
        } 
       } 
      } 
      else 
      { 
       aResult = sortAsString(theArray1, theArray2, ++thePosition); 
      } 
     } 
     else 
     { 
      aResult = theArray1.length - theArray2.length; 
     } 
     return aResult; 
    } 

    /** 
    * Gets the position of the non digit character in the given array starting from the given 
    * position. 
    * 
    * @param theCharArr /the character array. 
    * @param thePosition The position after which the array need to be checked for non-digit 
    *  character. 
    * @return The position of the first non-digit character in the array. 
    */ 
    private int getNonDigitPosition(char[] theCharArr, int thePosition) 
    { 
     for (int i = thePosition; i < theCharArr.length; i++) 
     { 
      if (!Character.isDigit(theCharArr[i])) 
      { 
       return i; 
      } 
     } 
     return -1; 
    } 

    /** 
    * Gets the integer value of the number starting from the given position of the given array. 
    * 
    * @param theCharArray The character array. 
    * @param thePosition The position form which the number need to be calculated. 
    * @return The integer value of the number. 
    */ 
    private int getNumberInStr(char[] theCharArray, int thePosition) 
    { 
     int aNumber = 0; 
     for (int i = thePosition; i < theCharArray.length; i++) 
     { 
      if(!Character.isDigit(theCharArray[i])) 
      { 
       return aNumber; 
      } 
      aNumber += aNumber * 10 + (theCharArray[i] - 48); 
     } 
     return aNumber; 
    } 
} 
+0

El '++' en la llamada 'sortAsNumber()' no tiene ningún efecto (y sería incorrecto; omitiría el primer dígito). –

6

Eche un vistazo a esta implementación. Debe ser lo más rápido posible, sin expresiones regulares, manipulación de matrices o llamadas a métodos, solo un par de indicadores y muchos casos.

Esto debería ordenar cualquier combinación de números dentro de las cadenas y soportar correctamente los números que son iguales y avanzar.

public static int naturalCompare(String a, String b, boolean ignoreCase) { 
    if (ignoreCase) { 
     a = a.toLowerCase(); 
     b = b.toLowerCase(); 
    } 
    int aLength = a.length(); 
    int bLength = b.length(); 
    int minSize = Math.min(aLength, bLength); 
    char aChar, bChar; 
    boolean aNumber, bNumber; 
    boolean asNumeric = false; 
    int lastNumericCompare = 0; 
    for (int i = 0; i < minSize; i++) { 
     aChar = a.charAt(i); 
     bChar = b.charAt(i); 
     aNumber = aChar >= '0' && aChar <= '9'; 
     bNumber = bChar >= '0' && bChar <= '9'; 
     if (asNumeric) 
      if (aNumber && bNumber) { 
       if (lastNumericCompare == 0) 
        lastNumericCompare = aChar - bChar; 
      } else if (aNumber) 
       return 1; 
      else if (bNumber) 
       return -1; 
      else if (lastNumericCompare == 0) { 
       if (aChar != bChar) 
        return aChar - bChar; 
       asNumeric = false; 
      } else 
       return lastNumericCompare; 
     else if (aNumber && bNumber) { 
      asNumeric = true; 
      if (lastNumericCompare == 0) 
       lastNumericCompare = aChar - bChar; 
     } else if (aChar != bChar) 
      return aChar - bChar; 
    } 
    if (asNumeric) 
     if (aLength > bLength && a.charAt(bLength) >= '0' && a.charAt(bLength) <= '9') // as number 
      return 1; // a has bigger size, thus b is smaller 
     else if (bLength > aLength && b.charAt(aLength) >= '0' && b.charAt(aLength) <= '9') // as number 
      return -1; // b has bigger size, thus a is smaller 
     else if (lastNumericCompare == 0) 
      return aLength - bLength; 
     else 
      return lastNumericCompare; 
    else 
     return aLength - bLength; 
} 
0

El uso de RuleBasedCollator también puede ser una opción. Aunque debe agregar todas las reglas de orden de forma anticipada, por lo que no es una buena solución si también desea tener en cuenta números más grandes.

Agregar personalizaciones específicas como 2 < 10 es bastante fácil y podría ser útil para clasificar identificadores de versiones especiales como Trusty < Precise < Xenial < Yakkety.

RuleBasedCollator localRules = (RuleBasedCollator) Collator.getInstance(); 

String extraRules = IntStream.range(0, 100).mapToObj(String::valueOf).collect(joining(" < ")); 
RuleBasedCollator c = new RuleBasedCollator(localRules.getRules() + " & " + extraRules); 

List<String> a = asList("1-2", "1-02", "1-20", "10-20", "fred", "jane", "pic01", "pic02", "pic02a", "pic 5", "pic05", "pic 7", "pic100", "pic100a", "pic120", "pic121"); 
shuffle(a); 

a.sort(c); 
System.out.println(a); 
Cuestiones relacionadas