Expliquant Le Comte Esquisse De L'Algorithme

Quelqu'un peut m'expliquer comment le Comte d'Esquisse Algorithme fonctionne? Je n'arrive toujours pas à comprendre comment les hachages sont utilisés, par exemple. J'ai du mal à comprendre ce document.

InformationsquelleAutor neilmarion | 2011-07-25
  1. 41

    Ce streaming algorithme instancie le cadre suivant.

    1. Trouver une étude randomisée en streaming algorithme dont la sortie (comme une variable aléatoire) a souhaité en attente, mais généralement de la variance élevée (c'est à dire, le bruit).

    2. Pour réduire la variance/bruit, exécuter un grand nombre de copies indépendantes en parallèle et de combiner leurs sorties.

    Généralement 1 est plus intéressant que le 2. Cet algorithme 2 est effectivement un peu hors normes, mais je vais vous parler d'1 seulement.

    Supposons que nous sommes le traitement de l'entrée

    a b c a b a .

    Avec trois compteurs, il n'y a pas besoin de hachage.

    a: 3, b: 2, c: 1

    Supposons, cependant, que nous n'avons qu'une. Il y a huit fonctions possibles h : {a, b, c} -> {+1, -1}. Voici un tableau des résultats.

     h  |
abc |  X = counter
----+--------------
+++ | +3 +2 +1 =  6
++- | +3 +2 -1 =  4
+-- | +3 -2 -1 =  0
+-+ | +3 -2 +1 =  2
--+ | -3 -2 +1 = -4
--- | -3 -2 -1 = -6
-+- | -3 +2 -1 = -2
-++ | -3 +2 +1 =  0

    Maintenant, nous pouvons calculer les attentes

                (6 + 4 + 0 + 2) - (-4 + -6 + -2 + 0)
E[h(a) X] = ------------------------------------ = 24/8 = 3
                             8

            (6 + 4 + -2 + 0) - (0 + 2 + -4 + -6)
E[h(b) X] = ------------------------------------ = 16/8 = 2
                             8

            (6 + 2 + -4 + 0) - (4 + 0 + -6 + -2)
E[h(c) X] = ------------------------------------ =  8/8 = 1 .
                             8

    Ce qui se passe ici? Pour a, dire, nous pouvons décomposer X = Y + Z, où Y est le changement dans la somme pour la as, et Z est la somme de la non-as. Par la linéarité de l'espérance, nous avons

    E[h(a) X] = E[h(a) Y] + E[h(a) Z] .

    E[h(a) Y] est une somme d'un terme pour chaque occurrence de a qui est h(a)^2 = 1, donc E[h(a) Y] est le nombre d'occurrences de a. L'autre terme E[h(a) Z] est égal à zéro, même en tenant compte de h(a), les uns les autres de la valeur de hachage est tout aussi susceptibles d'être plus ou moins une et donc contribue à zéro dans l'attente.

    En fait, la fonction de hachage n'a pas besoin d'être aléatoire uniforme, et une bonne chose: il n'y aurait aucun moyen de le stocker. Il suffit, pour que la fonction de hachage à deux à deux indépendants (tous deux valeurs de hachage sont indépendants). Pour notre exemple simple, un choix aléatoire des quatre fonctions suivantes suffit.

    abc

+++
+--
-+-
--+

    Je vais laisser les nouveaux calculs pour vous.

    • Wow! Juste quelques heures de la publication de la question, quelqu'un est venu avec une explication plus claire de l'algorithme! Merci beaucoup!!! 😀
    • Bonjour @insomniaque. Est-ce à dire que nous avons besoin de savoir à l'avance l'ensemble, dire S, où a, b et c sont des éléments de S?
    • Il suffit de connaître un sur-ensemble – il y a peut être trop grand nombre de différents éléments pour maintenir un uniforme aléatoire de fonction de hachage. Par exemple, si les éléments de données sont des n-vecteurs de bits, alors au début on peut choisir de façon aléatoire un n-vecteur de bits r et soit h(x) = 1 si r.x = 0 mod 2 et h(x) = -1 si m.r.x = 1 mod 2, où . dénote le produit scalaire.
    • (Je ne suis pas sûr si par paires hasard suffit à en faire des arguments au sujet de la variance de travail, mais c'est la saveur de l'fonctions de hachage que l'on pourrait utiliser.)
    • La grande explication, en effet!
    • En fait pratique, les fonctions de hachage peut effectivement facilement être "aléatoire uniforme", dans le sens que P[h(x)=y]=1/u si 1 <= y <= u. Le problème, c'est mutal de l'indépendance, dans le sens que P[h(x_1) = y_1 and ... and h(x_n) = y_n] = P[h(x_1) = y_1]...P[h(x_n) = y_n] qui, comme vous le dites, nécessite n log u bits de mémoire! Heureusement, comme vous le dites, nous pouvons en tirer avec beaucoup moins (quatre indépendance) pour le compte de croquis.

    InformationsquelleAutor insomniac
  2. 22

    Compter de l'esquisse est un probabiliste de la structure de données qui vous permet de répondre à la question suivante:

    La lecture d'un flux d'éléments a1, a2, a3, ..., an où il peut y avoir beaucoup d'éléments répétés, en tout temps, il va vous donner la réponse à la question suivante: combien de ai éléments avez-vous vu jusqu'à présent.

    Vous pouvez facilement obtenir une valeur exacte à chaque fois juste par le maintien de la valeur de hachage où les touches sont vos ai et des valeurs est de savoir comment de nombreux éléments que vous avez vu jusqu'à présent. Il est rapide O(1) ajouter, O(1) vérifier et de vous donner un nombre exact. Le seul problème qu'il faut O(n) de l'espace, où n est le nombre d'éléments distincts (gardez à l'esprit que la taille de chaque élément a une grande différence, parce que ça prend way more space to store this big string as a key que juste this.

    Alors, comment Comptez esquisse va vous aider? Comme dans tous les probabiliste des structures de données que vous le sacrifice de certitude pour l'espace. Le comte d'esquisse permet de sélectionner 2 paramètres: la précision des résultats ε et de la probabilité de mauvaise estimation δ.

    Pour ce faire, vous sélectionnez une famille de d deux à deux indépendants des fonctions de hachage. Ces mots compliqués dire qu'ils ne sont pas en collision souvent (en fait si les deux hachages les valeurs de la carte sur l'espace [0, m] la probabilité d'une collision est d'environ 1/m^2). Chacune de ces fonctions de hachage cartes les valeurs dans un espace [0, w]. Ainsi, vous créez une d * w de la matrice.

    Maintenant, quand vous lisez l'élément calculer chacun de d hachages de cet élément et de mettre à jour les valeurs correspondantes dans l'esquisse. Cette partie est la même pour le Comte d'esquisse et Compter-min esquisse.

    Expliquant Le Comte Esquisse De L'Algorithme

    Insomniaque joliment expliqué l'idée (le calcul de la valeur attendue) pour le compte de l'esquisse, donc je vais juste dire qu'avec le comte-min tout est encore plus simple. Vous venez de calculer d hachages de la valeur que vous souhaitez obtenir et retourner le plus petit d'entre eux. Étonnamment cette offre une excellente précision et de la probabilité de garantie, que vous pouvez trouver ici.

    L'augmentation de la gamme de fonctions de hachage, d'augmenter la précision des résultats, l'augmentation du nombre de hachages diminue la probabilité d'une mauvaise estimation:
    ε = e/w et δ=1/e^d. Une autre chose intéressante est que la valeur est toujours surestimé (si vous avez trouvé la valeur, il est probablement plus grand que la valeur réelle, mais sûrement pas plus petit).

    • J'ai trouvé cette réponse des plus utiles. Merci.
    • Ainsi, les deux comptent-croquis et min-comte-esquisse des algorithmes de résoudre le même problème, mais en a (un peu ) de manière différente ?
    InformationsquelleAutor Salvador Dali
  3. 0

    En fait, la fonction de hachage n'a pas besoin d'être aléatoire uniforme, et une bonne chose: il n'y aurait aucun moyen de le stocker. Il suffit, pour que la fonction de hachage à deux à deux indépendants (tous deux valeurs de hachage sont indépendants). Pour notre exemple simple, un choix aléatoire des quatre fonctions suivantes suffit.

    • Je pense que cela peut être préférable de laisser un commentaire ajouté à Salvador Dali réponse, parce que c'est plus de suivi. Si sa réponse devait être supprimé, par exemple, cette réponse aurait besoin d'une révision.
    InformationsquelleAutor sfafafaa