J'ai une chaîne S et je souhaite rechercher la sous-chaîne de la longueur X qui survient le plus souvent à l'art. Les sous-chaînes qui se chevauchent sont autorisées.
Par exemple, si S = "AOAOA" et X = 3, l'algorithme doit trouver "AOA" (qui apparaît 2 fois à S).
est un algorithme qui existe-t-il dans O (n) temps?
8 Réponses :
Il devrait être O (n * m) où M est la longueur moyenne d'une chaîne dans la liste. Pour de très petites valeurs de m, l'algorithme s'approchera O (n)
Étant donné qu'il y a / (n * (n-1) / sous-chaîne d'une chaîne de longueur / n /, je ne vois pas comment votre algorithme à gros décrit peut être O (n) - votre étape d'itération devrait être au moins O (n ^ 2)
@Ian Clelland: x est corrigé, n'est-ce pas?
Absolument droit - j'ai raté cela dans la description du problème.
'X' est fixe, une itération = O (n)
Ce n'est toujours pas vraiment O (n) - à chacun des n positions, vous devez examiner les caractères suivants (par exemple, produire un hachage de M caractères), de sorte que la complexité est O (nm). Le traiter comme O (n) signifie simplement que vous supposez que m est si petit que sa contribution est négligeable.
Je pense que cette réponse serait bien meilleure si elle comprenait un pseudocode.
@Chris: Je devrais cependant ajouter que je pense que o (nm) est probablement aussi bon que quiconque peut faire. Donné n caractères, vous devez examiner toutes les sous-chaînes possibles N-M et décider si deux sous-chaînes sont égales, vous devez comparer tous les caractères M de ces chaînes.
@ Jerry Coffin: Il existe des algorithmes sous-linéaires pour la recherche de sous-chaînes, par exemple [PDF] alexandrie.tue.nl/extra1/wskrap/publichtml/200407.pdf
Oui, la recherche d'une sous-chaîne peut être sublinear - mais dans ce cas, vous ne pouvez pas l'utiliser, car vous êtes intéressé par chaque éventuellement sous-chaîne, vous devez juste déterminer lequel vous avez affaire à avec à chaque étape de la plus grande chaîne.
max(freq.iteritems(), key=itemgetter(1))
complexité de FREQ [S [I: I + X]] est O (n) ... c'est un algorithme O (n ^ 2)
On dirait une question de devoirs, c'est pourquoi je n'ai pas fourni d'exemple de code.
@qjkx: Complexité de `Freq [S [S [I: I + X]] est O (x) ... c'est un algorithme O (n * x).
Je ne vois pas un moyen facile de le faire dans le temps strictement O (n), sauf si X n'est pas corrigé et peut être considéré comme une constante. Si X est un paramètre à l'algorithme, les moyens simples de faire cela seront effectivement o (n * x), car vous devrez faire des opérations de comparaison, des copies de chaîne, des hachages, etc., sur une sous-chaîne de longueur x à chaque itération.
(J'imagine, pendant une minute, que S est une chaîne multi-gigaoctet et que X est un nombre de plus d'un million, et de ne pas voir de simples façons de faire une comparaison de chaînes, ni des soustractions de hachage de longueur x, qui sont O (1) et ne dépendent pas de la taille de x)
Il serait peut-être possible d'éviter des copies de chaîne lors de la numérisation, en laissant tout en place, et d'éviter de reproduire toute la sous-chaîne - peut-être en utilisant un algorithme de hachage incrémentiel où vous pouvez ajouter un octet à la fois et supprimer Le plus ancien octet - mais je ne connais aucun algorithme de ce type qui n'entraînerait pas un grand nombre de collisions qui devraient être filtrées avec une étape de post-traitement coûteuse.
Keith Randall souligne que ce type de hachage est connu sous le nom de Rolling Hash . Cependant, il reste encore que vous devriez stocker la position de la chaîne de départ pour chaque match dans votre table de hachage, puis vérifier après avoir numérisé la chaîne que toutes vos matchs étaient vraies. Vous auriez besoin de trier la haquetable, qui pourrait contenir des entrées N-X, en fonction du nombre de correspondances trouvées pour chaque clé de hachage et vérifiez chaque résultat - probablement pas faisable dans O (n).
Clellan pourquoi nous avons besoin de réinventer la fonction de hachage. Pouvez-vous simplement y aller avec intégré à hachage?
Pourquoi supposez-vous qu'il y aura de nombreuses collisions? Un hachage de roulement approprié n'aurait pas ce problème dans des cas moyens.
Et pourquoi avez-vous besoin de stocker la position de départ? Ne faites-vous pas confiance à votre table de hachage pour garder les comptes? Une table de hachage bien conçue, qu'elle soit une adressage ouverte ou une chaînage séparée, aura des insertions de temps constantes. Cela inclut la réhabation.
Il n'y a aucun moyen de le faire dans O (n).
N'hésitez pas à bowervote-moi si vous pouvez me prouver de faux sur celui-ci, mais je n'ai rien.
Vous pouvez le faire en utilisant un Rolling Hash dans O (n) Temps (en supposant bon hachage Distribution). Un simple hachage de roulement serait le XOR des caractères de la chaîne, vous pouvez le calculer progressivement à partir du hachage de sous-chaîne précédent en utilisant seulement 2 Xors. (Voir l'entrée Wikipedia pour une meilleure hayes de roulement que XOR.) Calculez le hachage de vos substrings N-X + 1 à l'aide du hachage de roulement dans O (n) heure. S'il n'y avait pas de collision, la réponse est claire - si les collisions se produisent, vous devrez faire plus de travail. Mon cerveau fait mal à essayer de comprendre si cela peut tous être résolu dans O (n) temps.
mise à jour:
Voici un algorithme O (N) randomisé. Vous pouvez trouver le hachage supérieur dans O (n) heure en numérisant la haquetable (le garder simple, assumer aucun lien). Trouvez une chaîne de longueur X avec ce hachage (conserver un enregistrement dans la haquetable ou simplement refaire le hachage roulant). Ensuite, utilisez un O (n) String Recherche d'algorithme pour trouver toutes les occurrences de cette chaîne à l'art. Si vous trouvez le même nombre d'occurrences que vous avez enregistrées dans la haquetable, vous avez terminé.
Sinon, cela signifie que vous avez une collision de hasch. Choisissez une nouvelle fonction de hachage aléatoire et réessayez. Si votre fonction de hachage a connues (n) +1 bits et est un problème indépendant par paire [ Nous n'avons besoin que d'un algorithme de hachage de laminage indépendant aléatoire par paires.
update2:
En réalité, vous avez besoin de 2log (n) bits de hachage pour éviter toutes les collisions (N choisissez 2) car toute collision peut cacher la bonne réponse. Toujours faisable, et il ressemble à hachage par division polynomiale générale devrait faire le Truc. prob (H (s) == h (t)) <1/2 ^ {n + 1} si s! = T ], puis la probabilité que la sous-chaîne la plus fréquente de x-longueur dans S Hash a une collision avec la <= N autres sous-chaînes X de S est au plus 1/2. Donc, s'il y a une collision, choisissez une nouvelle fonction de hachage aléatoire et une nouvelle réessaye, vous n'aurez besoin que d'un nombre constant d'essais avant de réussir.
C'est le genre de hachage que je pensais - merci pour le lien. Pour plus de Brain Hurting: Vous devez supposer que les collisions se sont produites et vérifiaient chacune d'elles manuellement, alors maintenant vous êtes à O (N + X * (nombre de collisions possibles)) qui peuvent ou non plus que O (n )
Je suis confus, pourquoi ne pas utiliser HASHMAP, HASHTABLE ou HASH Fonction dans la bibliothèque Java depuis que c'est déjà bien construit.
@ user2372074: Parce que l'algorithme standard pour cela (hachage toutes les soustrées de longueur x) prend du temps O (NX). C'est pire que cet algorithme qui est O (n).
@Keith Randall a juste besoin d'être claire, pour un algorithme standard, devrait-il être la complexité de l'espace?
@ user2372074: Non, vous pouvez le faire dans O (n) mots, ou O (n lg n) bits.
Une table de hachage correctement conçue gérera des collisions pour vous, de sorte que vous n'avez même pas besoin de racancer votre cerveau à ce sujet.
C'est exactement ce que Lempel-ZIV-WELCH (LZW utilisé dans le format d'image GIF) L'algorithme de compression fait. Il trouve des octets répétés répandus et les modifient pour quelque chose de court.
Je crois que lzw est O (n) de décoder, mais plus lentement que celui de l'encode, ce qui est à la recherche de l'OP.
LZW elle-même est oui car il cherche toutes les soustractions répétées de longueur. Je disais juste qu'il pourrait utiliser un principe similaire, mais à la recherche de chaînes de longueur fixe.
Voici une version que j'ai faite dans C. J'espère que cela aide.
Vous pouvez construire un arbre de sous-chaînes. L'idée est d'organiser vos sous-chaînes comme un livre téléphonique. Vous recherchez ensuite la sous-chaîne et augmentez son compte par un.
Dans votre exemple ci-dessus, l'arborescence aura des sections (nœuds) en commençant par les lettres: 'A' et 'O'. 'A' apparaît trois fois et 'O' apparaît deux fois. Donc, ces nœuds auront un nombre de 3 et 2 respectivement.
Suivant, sous le nœud "A", un sous-noeud de 'O' apparaîtra correspondant à la sous-chaîne "AO". Cela apparaît deux fois. Sous le nœud "A" apparaît également deux fois.
Nous continuons de cette manière jusqu'à atteindre la fin de la chaîne.
Une représentation de l'arborescence pour 'ABAC' pourrait être (les nœuds du même niveau sont séparés par une virgule, des sous-nœuds sont entre crochets, les comptes apparaissent après le côlon).
A: 2 (B: 1 (A: 1 (C: 1 (C: 1 (1))), C: 1 ()), B: 1 (A: 1 (C: 1 (C: 1 (1))), C: 1 ( )
Si l'arbre est dessiné, il sera beaucoup plus évident! Ce que tout cela dit, par exemple, c'est que la chaîne 'ABA' apparaît une fois, ou la chaîne 'A' apparaît deux fois, etc. mais, le stockage est considérablement réduit et une récupération plus importante est considérablement accélérée (comparez ceci pour conserver une liste des sous- cordes).
Pour savoir quelle sous-chaîne est la plus répétée, faites une première recherche de profondeur de l'arborescence, chaque fois qu'un nœud de feuille est atteint, notez le nombre de comptes et conservez une piste du plus haut.
Le temps de fonctionnement est probablement quelque chose comme O (log (n)) non sûr, mais certainement mieux que O (n ^ 2).
Mais comment ajoutez-vous exactement toutes les sous-chaînes à votre structure de données (qui semble être une trie)?
En parcourant la trie en prenant une lettre à la fois de la sous-chaîne en question. Si vous atteignez un nœud de feuille avant d'atteindre la fin de la sous-chaîne, vous commencez à ajouter des nœuds à la trie, une pour chaque lettre.
Quelle est la sous-chaîne en question? Sauf si vous utilisez une sorte de fenêtre coulissante
Vous devriez extraire toutes les sous-chaînes. Commencez au premier personnage et remplissez la lettre Trie une lettre à la fois jusqu'à atteindre la fin de la chaîne. Puis passez au deuxième caractère, puis rincez et répétez. La trie est simplement un mécanisme de garde des enregistrements.
Vous avez orthographié "Lenght" et "Exemple". Corriger est "longueur" et "exemple"