Quel algorithme pouvez-vous utiliser pour trouver des phrases en double dans une chaîne?

Question

Étant donné une chaîne arbitraire, quelle est une méthode efficace de recherche d'expressions en double? On peut dire que les phrases doivent être plus longues qu’une certaine longueur pour être incluses.

Idéalement, vous obtiendriez le nombre d'occurrences pour chaque phrase.

Answer 1

Comme les personnes précédentes, mentionnent que l’arborescence des suffixes est le meilleur outil pour le poste. Mon site préféré pour les arbres de suffixes est http://www.allisons.org/ll/ AlgDS / Arbre / Suffixe / . Il énumère toutes les utilisations utiles des arborescences de suffixes sur une page et intègre une application de test js pour tester les chaînes et utiliser des exemples.

Answer 2

En théorie

• Un tableau de suffixes est la "meilleure" réponse, car peut être implémenté pour utiliser l’espace linéaire et le temps afin de détecter les sous-chaînes dupliquées. Cependant - la mise en œuvre naïve prend en fait du temps à O (n ^ 2 log n) pour trier les suffixes, et il n’est pas tout à fait évident de la réduire à O (n log n), encore moins à O (n), bien que vous puissiez lire les papiers liés si vous voulez.
• Un arbre de suffixe peut prendre un peu plus de mémoire (encore linéaire). Cependant, il est plus facile à implémenter de construire rapidement car vous pouvez utiliser quelque chose comme une idée de tri radix lorsque vous ajoutez des éléments à l’arborescence (voir le lien wikipedia du nom pour plus de détails).
• Le algorithme KMP convient également à soyez conscient de ce qui est spécialisé pour rechercher très rapidement une sous-chaîne particulière dans une chaîne plus longue. Si vous n’avez besoin que de ce cas particulier, utilisez simplement KMP et inutile de créer un index de suffixe en premier.

En pratique

J'imagine que vous analysez un document contenant des mots en langage naturel (par exemple, en anglais) et que vous souhaitez réellement utiliser les données que vous collectez.

Dans ce cas, vous voudrez peut-être simplement effectuer une rapide analyse n-gram . pour certains petits n, tels que n = 2 ou 3. Par exemple, vous pouvez segmenter votre document en une liste de mots en supprimant les signes de ponctuation, la mise en majuscule et les mots dérivés (exécuter, exécute les deux - > 'exécuter') jusqu'à augmenter les correspondances sémantiques. Il vous suffit ensuite de créer une carte de hachage (telle que hash_map en C ++, un dictionnaire en python, etc.) de chaque paire de mots adjacents avec le nombre d’occurrences jusqu’à présent. En fin de compte, vous obtenez des données très utiles qui ont été très rapides à coder, et pas très lentes à exécuter.

Answer 3

Les

arbres de suffixe constituent un bon moyen de mettre en œuvre cette solution. Le bas de cet article contient des liens vers des implémentations dans différentes langues.

Answer 4

Comme jmah l'a dit, vous pouvez utiliser des tableaux de suffixes / tableaux de suffixes pour cela.

Il existe une description d'un algorithme que vous pouvez utiliser ici (voir Section 3.1 ).

Vous trouverez une description plus détaillée dans le livre cité (Gusfield, 1997), à savoir

supposons que vous obteniez un tableau trié A avec n entrées (i = 1,2,3, ..., n)

Algo(A(i))
{
  while i<>n
  {
    temp=A[i];
    if A[i]<>A[i+1] then
    {     
      temp=A[i+1];
      i=i+1;
      Algo(A[i])
    }
    else if A[i]==A[i+1] then
      mark A[i] and A[i+1] as duplicates
  }
}

Cet algo fonctionne à l'heure O (n).

Answer 5

Answer 6

Answer 7

supposons que vous obteniez un tableau trié A avec n entrées (i = 1,2,3, ..., n)

Algo(A(i))
{
  while i<>n
  {
    temp=A[i];
    if A[i]<>A[i+1] then
    {     
      temp=A[i+1];
      i=i+1;
      Algo(A[i])
    }
    else if A[i]==A[i+1] then
      mark A[i] and A[i+1] as duplicates
  }
}

Cet algo fonctionne à l'heure O (n).

Answer 8

Answer 9

Answer 10