Misra – Gries özeti - Misra–Gries summary
 | Bu makale için ek alıntılara ihtiyaç var doğrulama. (Mart 2018) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin) |
Nın alanında akış algoritmaları, Misra – Gries özetleri çözmek için kullanılır sık karşılaşılan öğeler sorunu içinde veri akışı modeli. Yani, yalnızca bir kez (ve bazı rasgele sırayla) incelenebilen uzun bir girdi akışı verildiğinde, Misra-Gries algoritması hangi (varsa) değerin akışın çoğunluğunu veya daha genel olarak , akışın sabit bir kısmını oluşturan öğeler kümesi.
Misra – Gries özeti
Veri akışı modelindeki tüm algoritmalarda olduğu gibi, girdi sonludur. sıra nın-nin tamsayılar sonlu bir alandan. Algoritma bir ilişkilendirilebilir dizi Akıştan anahtar olarak değerleri ve karşılık gelen değerler olarak frekanslarının tahminlerini içeren. Bir parametre alır k Bu, hem tahminlerin kalitesini hem de kullanılan bellek miktarını etkileyen dizinin boyutunu belirler.
algoritma yanlışlıklar:[1] giriş: Pozitif bir tam sayı k Sonlu bir dizi s 1,2, ..., aralığında değerler alarakm çıktı: İlişkilendirilebilir bir dizi Bir içindeki her bir öğe için sıklık tahminleri ile s Bir : = yeni (boş) ilişkilendirilebilir dizi süre s boş değil: almak bir değer ben itibaren s Eğer ben anahtarlarda (Bir): Bir[ben] := Bir[i] + 1 Aksi takdirde | anahtarlar (Bir)| < k - 1: Bir[ben] := 1 Başka: her biri için K anahtarlarda (Bir): Bir[K] := Bir[K] - 1 Eğer Bir[K] = 0: kaldır K anahtarlardan (Bir) dönüş Bir
Özellikleri
Misra – Gries algoritması O (k(günlük (m) + günlük (n))) Uzay, nerede m akıştaki farklı değerlerin sayısı ve n akışın uzunluğudur.
En azından oluşan her öğe n/k zamanların çıktı dizisinde görünmesi garanti edilir.[1] Bu nedenle, verilerin üzerinden ikinci bir geçişte, veri için kesin frekanslar k−1 öğe, sık karşılaşılan öğeler sorununu çözmek için hesaplanabilir veya k= 2, çoğunluk sorunu. Bu ikinci geçiş O alır (kgünlük (m)) Uzay.[kaynak belirtilmeli ]
Algoritma tarafından çıkarılan özetler (diziler) birleştirilebiliriki akışın özetlerinin birleştirilmesi anlamında s ve r dizilerini anahtara ekleyerek ve sonra ortaya çıkan dizideki her sayacı yalnızca k anahtarlar kalırsa, Misra-Gries algoritmasını üzerinde çalıştırmaya kıyasla aynı (veya daha iyi) kalitede bir özetle sonuçlanır. birleştirme nın-nin s ile r.
Misal
![[icon]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png){kind=small} | Bu bölüm genişlemeye ihtiyacı var. Yardımcı olabilirsiniz ona eklemek. (Kasım 2017) |
K = 2 ve veri akışı 1,4,5,4,4,5,4,4 (n = 8, m = 5) olsun. 4'ün n / k = 4 kereden fazla olan veri akışında 5 kez göründüğünü ve dolayısıyla algoritmanın çıktısı olarak görünmesi gerektiğini unutmayın.
K = 2 ve | anahtarlar (A) | = k − 1 = 1 olduğundan, algoritmanın karşılık gelen değerine sahip yalnızca bir anahtarı olabilir. Algoritma daha sonra aşağıdaki gibi çalışacaktır (- anahtarın olmadığını gösterir):
| Akış Değeri | Anahtar | Değer |
|---|---|---|
| 1 | 1 | 1 |
| 4 | — | 0 |
| 5 | 5 | 1 |
| 4 | — | 0 |
| 4 | 4 | 1 |
| 5 | — | 0 |
| 4 | 4 | 1 |
| 4 | 4 | 2 |
Çıktı: 4
Referanslar
- ^ a b Cormode 2014.
- Misra, J .; Gries, David (1982). "Tekrarlanan elemanların bulunması". Bilgisayar Programlama Bilimi. 2 (2): 143–152. doi:10.1016/0167-6423(82)90012-0. hdl:1813/6345.
- Cormode Graham (2014). "Misra-Gries Özetleri". Kao'da Ming-Yang (ed.). Algoritmalar Ansiklopedisi. Springer ABD. s. 1–5. doi:10.1007/978-3-642-27848-8_572-1. ISBN 9783642278488.