J'ai une séquence d'appels SQL, que je veux utiliser pour détecter des boucles (et donc des appels SQL dupliqués inutiles), mais cela m'a fait penser à ce problème plus général.Comment détecter les répétitions dans une liste de chaînes?
Étant donné une liste, disent [a,b,c,b,c,a,b,c,b,c,a,b,b]
Est-il possible que je peux transformer en a,[[b,c]*2,a]*2,b*2
ou, [a,[b,c]*2]*2,a,b*2
C'est, détecter les répétitions (peut-être les imbriquées).
Regardez dans le Lempel-Ziv-Welsh compression algorithm. Il est construit sur la détection des répétitions dans les chaînes et en les utilisant pour la compression. Je crois que vous pouvez utiliser un Trie pour cela.
Si vous pouvez trier d'abord, alors il est facile de passer une fois de plus pour trouver des exécutions en double. Bien sûr, trier quelque chose en tant que forme libre en tant que requêtes SQL semble un peu effrayant.
Je ne suis pas un expert dans ce domaine, mais vous voudrez peut-être vérifier certains algorithmes de compression, il me semble que c'est exactement ce qu'ils font.
Si la chaîne est suffisamment grande, une approche intéressante consiste à exécuter un outil de compression (comme gzip, bzip ou 7zip). Ces outils fonctionnent en localisant les répétitions (à différents niveaux), et en les substituant par des pointeurs vers la première instance du texte (ou un dictionnaire). La compression que vous obtenez est une mesure de la répétition. Dumping le fichier (vous devrez écrire le code pour le faire) vous donnera le contenu répété.
Doute cela va fonctionner, car les programmes de compression utiliseront heureusement les sous-chaînes, et ignoreront les limites du commandement SQL. – derobert
La réponse à cette question est ici: http://stackoverflow.com/questions/6874250/lossless-hierarchical-run-length-encoding –