檢測使用滑動窗口概念生成的文件中的重複項

我正在處理項目，我必須解析文本文件並將字符串劃分爲用戶指定長度的子字符串。然後我需要檢測結果中的重複項。檢測使用滑動窗口概念生成的文件中的重複項

所以原來的文件應該是這樣的：在文件

ORIGIN 
    1 gatccaccca tctcggtctc ccaaagtgct aggattgcag gcctgagcca ccgcgcccag 
    61 ctgccttgtg cttttaatcc cagcactttc agaggccaag gcaggcgatc agctgaggtc 
    121 aggagttcaa gaccagcctg gccaacatgg tgaaacccca tctctaatac aaatacaaaa 
    181 aaaaaacaaa aaacgttagc caggaatgag gcccggtgct tgtaatccta aggaaggaga 
    241 ccaccactcc tcctgctgcc cttcccttcc ccacaccgct tccttagttt ataaaacagg 
    301 gaaaaaggga gaaagcaaaa agcttaaaaa aaaaaaaaaa cagaagtaag ataaatagct

我環路，併產生一個線串的，然後使用line.toCharArray()在得到的線條滑動，並根據用戶規範劃分。因此，如果子字符串長度爲4的結果是這樣的：

GATC 
ATCC 
TCCA 
CCAC 
CACC 
ACCC 
CCCA 
CCAT 
CATC 
ATCT 
TCTC 
CTCG 
TCGG 
CGGT 
GGTC 
GTCT 
TCTC 
CTCC 
TCCC 
CCCA 
CCAA

這裏是我的分裂碼：

try { 
    scanner = new Scanner(toSplit); 
    while (scanner.hasNextLine()) { 
     String line = scanner.nextLine(); 
     char[] chars = line.toCharArray(); 
     for (int i = 0; i < chars.length - (k - 1); i++) { 
      String s = ""; 
      for(int j = i; j < i + k; j++) { 
       s += chars[j]; 
      } 
      if (!s.contains("N")) { 
       System.out.println(s); 
      } 
     } 
    } 
}

我的問題是：給定輸入文件可以是巨大的，如何我可以檢測結果中的重複項嗎？

來源

2015-06-25 H.K

是否很重要的是，結果是在相同的順序輸入？ –

是的，它是重要的 –

請注意，您可以將A，C，G，T編碼爲0,1,2,3的2位，對於長度爲4的子串，所有可能的組合給予4^4 == 256個可能性：您可以記住一個大小爲256的數組中的字符串的最後一個位置，並將輸出的碰撞作爲數組中的一系列塊替換爲有效位置 – BeyelerStudios

如果您想檢查重複項，Set將是保存和測試數據的理想選擇。請告訴您在哪個上下文中檢測重複項：單詞，行或「輸出字符」。

來源

2015-06-25 13:58:37

我需要檢測單詞（子字符串）重複 –

要做到這一點的唯一方法，通過重寫分裂成第三個文件並逐行讀取它後的結果？我看到[鏈接]解決方案（http://stackoverflow.com/questions/996041/deleting-duplicate-lines-in-a-file-using-java）但現在我無法拆分文件並使用相同的文件檢測重複... –

我不會將結果重寫到另一個文件中。你可以用'Set wordSet = new HashSet （）;'在啓動時創建一個新的Set，提取一個字使用 'String word =「extracted」; （wordSet.contains（word））{ // ... duplicate } else { wordSet.add（word）; }' –

你可以做這樣的事情：

Map<String, Integer> substringMap = new HashMap<>(); 
int index = 0; 
Set<String> duplicates = new HashSet<>();

爲你拉出來的文件每個substring，它只有當它不是重複添加到substringMap（或者如果它是一個重複的，將其添加到duplicates ）：

if (substringMap.putIfAbsent(substring, index) == null) { 
    ++index; 
} else { 
    duplicates.add(substring); 
}

然後你可以使出渾身子輕鬆：

String[] substringArray = new String[substringMap.size()]; 
for (Map.Entry<String, Integer> substringEntry : substringMap.entrySet()) { 
    substringArray[substringEntry.getValue()] = substringEntry.getKey(); 
}

瞧！原始順序的輸出數組，沒有重複項，加上一組所有重複的子字符串，性能非常好。

來源

2015-06-25 14:16:23

原則上這是一個很好的答案，但對於大量數據（如OP指出的），這是低效的（與散列相比）。我也認爲OP想要*檢測重複*不會消除它們（正如您最後的片段所暗示的那樣）。 – BeyelerStudios

@BeyelerStudios正如我在我的回答中所說的，如果需要，可以使用HashSet，並在Subsequence類中重寫'hashCode'。我在我的例子中選擇不這樣做，因爲這對於更大的子字符串大小不起作用。爲了檢測重複但不消除它們，您可以在比較器中添加額外的代碼，每次發現重複時都會發出備註。 –

你錯了：set（和擴展HashSet）保證可以添加'！a.equals（b）'的獨特元素'a'，'b''不依賴於它們的'hashCode（） '，'HashSet'確實包含了你插入的所有唯一字符串！編輯：[演示]（http://ideone.com/QyRKyF） – BeyelerStudios

您可以使用bloom filter或散列表來檢測可能的重複，然後對文件進行第二遍檢查以檢查這些「重複候選者」是否是真正的重複。

實施例與哈希表：

// First we make a list of candidates so we count the times a hash is seen 
int hashSpace = 65536; 
int[] substringHashes = new int[hashSpace]; 
for (String s: tokens) { 
    substringHashes[s.hashCode % hashSpace]++; // inc 
} 

// Then we look for words that have a hash that seems to be repeated and actually see if they are repeated. We use a set but only of candidates so we save a lot of memory 
Set<String> set = new HashSet<String>(); 
for (String s: tokens) { 
    if (substringHashes[s.hashCode % hashSpace] > 1) { 
    boolean repeated = !set.add(s); 
    if (repeated) { 
     // TODO whatever 
    } 
    } 
}

來源

2015-06-25 15:33:01 aalku

檢測使用滑動窗口概念生成的文件中的重複項

回答

相關問題