J'ai besoin de trouver toutes les sous-chaînes égales contre deux chaînes. J'ai essayé d'utiliser l'arborescence de suffixes pour rechercher des sous-chaînes et cela fonctionne rapidement, mais trop de mémoire (inapproprié pour ma tâche).
D'autres idées?manière efficace pour trouver des correspondances contre deux chaînes
Aho-corasick est une excellente implémentation pour faire correspondre n'importe quel nombre de chaînes avec des problèmes de performances minimes. Avez-vous essayé cela?
Je ne pense pas que l'OP a les chaînes qu'ils veulent correspondre * avant * le traitement de l'entrée. – NullUserException
Eh bien, c'est l'arbre de suffixe basé aussi. La consommation de mémoire est un problème. – jifuyo
Vous pouvez faire une fenêtre coulissante, bien que ce soit moins de mémoire, mais plus de temps.
La plus petite sous-chaîne est un caractère (en fait, le mot vide est un, mais laissons cela de côté).
Prenez le caractère 1 de la chaîne 1 et enregistrez les positions de ce caractère dans la chaîne 2 dans une sorte de structure de données, comme une carte ou un tableau.
Ensuite, vous prenez le suivant (caractère 2 de la chaîne 1) et faites la même chose.
Une fois que vous avez atteint la fin de la chaîne 1, vous recommencez, mais cette fois que vous prenez tous les deux caractères de chaîne 1 et alway avance par un caractère de vérification pour toutes les positions dans la chaîne 2.
Pour ce faire, Tant que la sous-chaîne est égale à la chaîne 1, vous comparez les chaînes 1 et 2 dans leur ensemble.
Gardez à l'esprit: quand la chaîne 2 est plus longue que la chaîne 1, vous devez avancer toute la chaîne 1 fois tous les caractères sur la chaîne 2, puisque la chaîne 1 peut être une sous-chaîne de chaîne 2.
Si la chaîne 1 est plus grand que la chaîne 2, vous pouvez arrêter de chiquer, une fois que votre sous-chaîne est plus longue que la chaîne 2, toutes les autres sous-chaînes auront été vérifiées d'ici là. Idéalement, vous finiriez par avoir une carte (qui dans sa forme la plus simple est un tableau bidimensionnel), qui contient les positions de chaque sous-chaîne de la chaîne 1 dans la chaîne 2.
Pourquoi dites-vous que l'arbre de suffixe est trop de mémoire? S'il est implémenté correctement, il consomme uniquement la mémoire O (n).
Seulement? Il consomme 20 * n de mémoire;) – jifuyo
Pouvez-vous fournir plus de détails, peut-être quelques exemples de chaînes? Votre description est un peu anémique. –
Quelque chose comme un diff ferait? – NullUserException
@NullUserException, je n'ai pas besoin de trouver des différences comme diff fait. Seules les parties correspondantes des chaînes. – jifuyo