在字符串中查找常見序列

-2

如何在Java中查找字符串中常見的序列？在字符串中查找常見序列

該字符串是一個長序列的數字，我想找到最常見的數字序列。

來源

2011-07-06 Veriton

「1111」的結果是什麼？ –

我認爲1x 1111,2x111,3x11。但這並不重要，我只需要找到最常見的序列。 – Veriton

我想這取決於你要找的序列有多長。

我要做的是使用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(); 
}

而關於性能：這種測試方法需要大約一秒鐘我的機器上無限長度約25毫秒，當我限制樣長度到12個字符

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

來源

2011-07-06 15:21:30

我希望最高的數字是2位數字。使用這種方法，你不需要做更長的字符串。特別是如果字符串是隨機的。 ;） –

@彼得我知道，但是你應該怎麼處理這些規範？ :-) –

+1：一個有趣的解決方案和努力。恕我直言，它唯一有意義的比較相同長度的字符串。 –

對於一個給定長度的數字，你可以把所有的數據放在一個ArrayList中，對它們進行排序並計算重複次數（它們將彼此相鄰）。總是少於1000個條目。

來源

2011-07-06 15:49:06

在字符串中查找常見序列

回答

相關問題