Trouver des séquences courantes dans une chaîne

Question

Comment puis-je trouver des séquences courantes dans une chaîne en Java?

La chaîne est une longue séquence de chiffres et je souhaite trouver les séquences de chiffres les plus courantes.

Answer 1

Je suppose que cela dépend de combien de temps les séquences sont que vous recherchez.

Ce que je ferais est d'utiliser un Guava Multiset, de parcourir la séquence, d'écrire toutes les sous-séquences dans le multiset et de trier cela par occurrence. Voici un exemple d'implémentation:

public static String getMostFrequentSequence(final String input, final int patternLength) { 
    final Multiset<String> multiset = HashMultiset.create(); 
    final int length = patternLength < 0 ? input.length() : Math.min(patternLength, input.length()); 
    for (int l = 2; l < length; l++) { 
     for (int o = 0; o < input.length() - l; o++) { 
      multiset.add(input.substring(o, o + l)); 
     } 
    } 
    return Ordering.from(new Comparator<Entry<String>>() { 
     public int compare(final Entry<String> o1, final Entry<String> o2) { 
      return 
      ComparisonChain.start() 
      .compare(o1.getCount(), o2.getCount()) 
      .compare(o1.getElement(), o2.getElement()) 
      .result(); 
     } 
    }).max(multiset.entrySet()).getElement(); 
} 

Et sur la performance: Cette méthode de test prend environ une seconde sur ma machine pour une longueur illimitée et environ 25 millisecondes lorsque je limite la longueur du motif 12 caractères

public static void main(final String[] args) throws Exception { 
    final StringBuilder sb = new StringBuilder(); 
    final Random random = new Random(); 
    for (int i = 0; i < 1000; i++) { 
     sb.append(random.nextInt(10)); 
    } 
    final long t1 = System.currentTimeMillis(); 
    final String input = sb.toString(); 
    System.out.println(input); 
    System.out.println(getMostFrequentSequence(input, -1)); 
    System.out.println(System.currentTimeMillis() - t1); 
    final long t2 = System.currentTimeMillis(); 
    System.out.println(getMostFrequentSequence(input, 12)); 
    System.out.println(System.currentTimeMillis() - t2); 
} 

Answer 2

Pour une longueur donnée de nombres, vous pouvez placer ensuite tous dans une ArrayList, les trier et compter le nombre de doublons (ils seront côte à côte) Vous aurez toujours moins de 1000 entrées.