algorithme de recherche

Question

Je suis à la recherche d'un algorithme de recherche efficace pour obtenir le plus longle plus court motif répété dans une collection (~ 2k des entiers), où ma collection est faite de ce motif répété que (il n'y a pas de bruit entre les motifs répétés), mais la dernière occurrence du motif peut être incomplète.

Exemples: J'ai [2,4,1, 2,4,1, 2,4,1, 2,4,1, 2,4,1]
Je voudrais recieve: [2,4,1]

J'ai: [21,1,15,22, 21,1,15,22, 21,1,15,22, 21,1,15]
Je voudrais recieve: [21,1,15,22]

J'ai: [3,2,3,2,5]
Je voudrais recevoir: [] (il n'y a pas de modèle)

(espaces ajoutés uniquement pour plus de lisibilité)

Answer 1

L'algorithme très direct ressemblerait à ceci (en Python, mais devrait y avoir aucun problème pour traduire en Javascript):

def check(a, width): 
    '''check if there is a repeated pattern of length |width|''' 
    for j in range(width, len(a)): 
    if a[j] != a[j-width]: 
     return False 
    return True 

def repeated(a): 
    '''find the shortest repeated pattern''' 
    for width in range(1, len(a)): 
    if check(a, width): 
     return a[:width] 
    return [] 

Cela devrait également être assez efficace, puisque la plupart du temps la boucle check() reviendra à droite dans la première itération, de sorte que vous fondamentalement seulement itérer sur la liste une fois.

Answer 2

Essayez de construire votre groupe initial en commençant par le début en ajoutant un numéro au groupe jusqu'à ce que vous obteniez un nombre identique au premier du groupe (le nombre précédent se termine) le motif). Utilisez-le comme motif de test et passez-le en faisant correspondre le motif jusqu'à ce que vous obteniez un échec. Si vous faites correspondre l'ensemble de la collection (avec votre traitement spécial de fin), cela représente un candidat. Revenez à l'endroit où vous avez trouvé votre correspondance initiale, puis continuez à construire votre groupe jusqu'à ce que vous obteniez un autre numéro correspondant au premier de votre motif. Répétez, en remplaçant votre candidat chaque fois que vous en trouvez un plus long. Lorsque votre motif est de la même longueur que l'arrêt de la collection (celui-ci ne correspond pas). Si vous avez un candidat qui sera le plus long modèle.

Answer 3

Je pense que vous pourriez aborder ce problème en considérant la période du modèle. La période d'une suite A [] est le plus petit entier T tel que A [i + T] = A [i] pour tout i. Dans votre cas, lorsque vous trouvez la période T, vous avez terminé, puisque A [0..T-1] est le motif le plus court que vous recherchez. Commencez donc par une période T de petite taille possible et testez si la séquence satisfait la propriété périodique. Si oui, vous avez terminé (cela ne se produit réellement que lorsque tous les éléments sont identiques). Pour tout T plus grand, vous devez tester si A [i + T] = A [i] pour i = 0..A.len-T-1. Ceci est juste une simple boucle.

Answer 4

Vous pouvez optimiser votre recherche en observant que la longueur de votre collection doit être un multiple de votre longueur de motif. Si votre collection a une taille qui est premier, la seule longueur de motif possible est 1, c'est-à-dire que tous les éléments doivent être identiques!