文字列内の一般的なシーケンスを見つける

Question

よくあるシーケンスをJavaの文字列で見つける方法はありますか？

文字列は長い数字列で、よく出現する数字のシーケンスを探したいと思っています。

Answer 1

私は、あなたが探している順序がどれくらいあるかによって決まると思います。

Guava Multisetを使用してシーケンスを反復し、すべてのサブシーケンスをMultisetに書き込み、オカレンスでソートします。ここではサンプル実装です：

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(); 
} 

とパフォーマンスについて：私は

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

12文字までのパターンの長さを制限する場合は、この試験方法は、無制限の長さのための私のマシン上秒〜約25ミリ秒程度かかり与えられた長さの数字をArrayListに入れ、ソートして重複数を数えます（それらは互いに隣り合っています）。