Trouver du contenu en double dans une chaîne?

Question

Comment résoudre le problème suivant:

J'ai un fichier semi-volumineux avec du texte (environ 10 pages) et je veux trouver du contenu en double dans ce texte. Pour être plus précis, donnez une chaîne, trouvez les deux plus longues chaînes identiques.

J'ai regardé la plus longue séquence commune:

http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_subsequence

Mais ces mises en œuvre prennent deux chaînes en entrée.

Peut-être qu'un service le fait déjà?

Answer 1

essayer cette

public static string FindLargestDuplicateString(
     string text) 
    { 
     var largest = string.Empty; 
     for (var i = '!'; i <= '}'; i++) 
     { 
      var l = FindLargestDuplicateStringImpl(
       text, i.ToString()); 
      if (l.Length > largest.Length) 
       largest = l; 
     } 
     return largest; 
    } 

    private static string FindLargestDuplicateStringImpl(
     string text, string currentLargest) 
    { 
     bool found = false; 
     for (var i = '!'; i <= '}'; i++) 
     { 
      var comp = currentLargest + i; 
      var last = text.LastIndexOf(comp); 
      var first = text.IndexOf(comp, 0); 
      if (first == -1 || last == -1 || first == last) 
       continue; 
      currentLargest = comp; 
      found = true; 
     } 
     return !found ? currentLargest : 
      FindLargestDuplicateStringImpl(text, currentLargest); 
    } 

Answer 2

Vous pouvez faire quelque chose comme ça

public static ArrayList<String> split(String line){ 
    line+=" "; 
    Pattern pattern = Pattern.compile("\\w*\\s"); 
    Matcher matcher = pattern.matcher(line); 
    ArrayList<String> list = new ArrayList<String>(); 
    while (matcher.find()){ 
     list.add(matcher.group()); 
    } 
    return list; 
} 

assurez-vous d'enlever toute ponctuation

public static void duplicatedWords(String s, int n){ 
    ArrayList<String> splitted = split(s); 
    System.out.println(splitted); 
    HashMap<String, Integer> map = new HashMap<String, Integer>(); 
    PriorityQueue<String> pq = new PriorityQueue<String>(splitted.size(), new myComp()); 
    for(int i = 0; i<splitted.size(); i++){ 
     if(map.get(splitted.get(i)) == null){ 
      map.put(splitted.get(i), 1); 
     } 
     else if(map.get(splitted.get(i)) == 1) { 
      map.put(splitted.get(i), map.get(splitted.get(i))+1); 
      pq.add(splitted.get(i)); 
     } 
    } 
    int size = pq.size(); 
    for(int i = 0; i<size; i++){ 
     if(i <n) 
      System.out.println(pq.remove()); 
     else 
      break; 
    } 
} 

Avec ce comparateur:

public static class myComp implements Comparator{ 
    @Override 
    public int compare(Object arg0, Object arg1) { 
     String s1 = (String)arg0; 
     String s2 = (String)arg1; 
     return s2.length()-s1.length(); 
    } 

} 

Answer 3

Voici un algorithme simple (mais inefficace): Boucle toutes les longueurs de sous-chaînes possibles, du maximum à 1. Pour chaque longueur, placez toutes les sous-chaînes de cette longueur dans un dictionnaire. Si vous trouvez un doublon, arrêtez. Ce doit être le plus grand. Voici le code C# correspondant:

public static string FindDuplicateSubstring(string s) 
    { 
     for (int len = s.Length-1; len > 0; len--) { 
      var dict = new Dictionary<string, int>(); 
      for (int i = 0; i <= s.Length - len; i++) { 
       string sub = s.Substring(i, len); 
       if (dict.ContainsKey(sub)) return sub; 
       else dict[sub] = i; 
      } 
     } 
     return null; 
    } 

Par exemple, lorsqu'il est appliqué au texte de votre question, la plus longue sous-chaîne répétée est « mise en œuvre ». Notez que les sous-chaînes qui se chevauchent sont autorisées, c'est-à-dire que l'entrée "bbbb" renvoie "bbb". Votre question ne précisait pas si vous vouliez exclure le chevauchement. Pour une approche plus rapide, voir mon autre réponse.

Answer 4

L'algorithme de la plus longue sous-séquence commune n'exige pas que les correspondances soient des sous-chaînes contiguës. Par exemple, pour les chaînes "computer" et "houseboat" la sous-séquence est "out". c'est ce que tu veux?

Si vous voulez que les correspondances soient des sous-chaînes contiguës, cela s'appelle longest repeated substring problem. Le lien décrit un algorithme de temps et d'espace linéaire utilisant des arbres de suffixes.

Si vous voulez quelque chose de court et simple, voici une approche basée sur l'algorithme LCS, mais sans table. L'idée est de boucler tous les décalages d'entiers possibles entre la sous-chaîne désirée et sa duplication. Pour chaque décalage, recherchez la plus grande correspondance contiguë en analysant la chaîne une fois. Si la chaîne d'entrée a une longueur n, il y a O (n) décalages possibles et la vérification de chaque décalage prend O (n), donc le coût total est O (n^2), avec seulement une quantité constante d'espace. (Comparez à ma réponse de dictionnaire simple qui prend l'espace O (n^3) et l'espace O (n^2).) Si vous ne voulez pas de chevauchement des correspondances (ie vous voulez que "bbbb" retourne "bb" pas "bbb"), puis en vérifiant chaque changement, vous vous arrêtez si le plus grand match dépasse le quart de travail. Voici le code C#:

public static string FindDuplicateSubstring(string s, 
               bool allowOverlap = false) 
    { 
     int matchPos = 0, maxLength = 0; 
     for (int shift = 1; shift < s.Length; shift++) { 
      int matchCount = 0; 
      for (int i = 0; i < s.Length - shift; i++) { 
       if (s[i] == s[i+shift]) { 
        matchCount++; 
        if (matchCount > maxLength) { 
         maxLength = matchCount; 
         matchPos = i-matchCount+1; 
        } 
        if (!allowOverlap && (matchCount == shift)) { 
         // we have found the largest allowable match 
         // for this shift. 
         break; 
        } 
       } else matchCount = 0; 
      } 
     } 
     if (maxLength > 0) return s.Substring(matchPos, maxLength); 
     else return null; 
    } 

Je l'ai testé ce contre ma réponse dictionnaire et donne les mêmes résultats. Mais pour une chaîne aléatoire de longueur 3000, le dictionnaire prend 15 secondes, alors que la méthode ci-dessus prend 60ms (et beaucoup moins de mémoire).