Linux Fu: Sağlama Toplamları ile Yuvarlayın


Sadece daha iyi bir algoritma seçmenin daha iyi olacağı bir şeyi optimize etmek için ne kadar sıklıkla zaman harcadığımıza sık sık şaşırıyoruz. Matematikçi Gauss’un okuldayken 1’den 100’e kadar olan tam sayıları toplaması için çok uğraştığı hakkında eski bir hikaye vardır. Diğer öğrenciler her sayıyı zahmetle toplarken, Gauss 100+1’in 101 ve 99 + 2’nin 99 + 2 olduğunu fark etti. ayrıca 101. Bil bakalım 98 + 3 nedir? Tabii ki, 101. Böylece, 101’e ulaşan 50 çift olduğunu kolayca bulabilir ve cevabın 5.050 olduğunu bilirsiniz. Ne kadar hızlı eklerseniz ekleyin, o algoritmayı bilen birini yenmeniz olası değildir. İşte size bir soru: Büyük bir metniniz var ve onu aramak istiyorsunuz. En iyi yol nedir?

Tabii ki, bu dolu bir soru. En iyi birçok anlama gelebilir ve uğraştığınız veri türüne ve hatta kullandığınız makinenin türüne bağlı olacaktır. Sadece bir dizi arıyorsanız, elbette kaba kuvvet algoritmasını yapabilirsiniz. Diyelim ki Savaş ve Barış metninde “mahkum” kelimesini arıyoruz:

  1. Savaş ve Barış’ın ilk harfiyle başlayın
  2. Geçerli harf, mevcut “mahkum” harfiyle aynı değilse, bir sonraki harfe geçin, “mahkum”daki mevcut harfi sıfırlayın ve başka harf kalmayana kadar 2. adıma dönün.
  3. Mevcut harfler aynı ise hükümlünün bir sonraki harfine geçin ve metnin o anki harfini unutmadan bir sonraki harfle karşılaştırın. Aynıysa, “mahkum” da başka harf kalmayana kadar bu adımı tekrarlayın (bu noktada bir eşleşmeniz var). Aynı değilse, mevcut “mahkum” harfini sıfırlayın ve ayrıca metnin orijinal mevcut harfine geri dönün ve ardından bir sonraki harfe geçerek 2. adıma dönün.

Bunu İngilizce olarak tarif etmek gerçekten zor. Ancak, başka bir deyişle, bir eşleşme bulana kadar metni karakter karakter arama dizesiyle karşılaştırın. Bu işe yarar ve aslında bazı modern donanımlarla bunun için hızlı kodlar yazabilirsiniz. Daha iyisini yapabilir miyiz?

Daha İyi Algoritmalar

Temel arama

Yine, gerçekten daha iyi tanımınıza bağlıdır. Metnin neredeyse aradığımız ama tam olarak olmayan birçok dize içerdiğini varsayalım. Örneğin, Savaş ve Barış muhtemelen içinde “the” kelimesinin birçok tekrarını barındırır. Ama aynı zamanda hedef kelimemizi içeren “orada”, “o zaman” ve “diğer” kelimeleri de vardır. Kısa olduğu için çok da önemli olmayan “the” kelimesi için, peki ya büyük arama dizilerini gözden geçiriyor olsaydınız? (Bilmiyorum – DNA genom verileri falan.) Çıkmazları kovalamak için çok zaman harcarsınız. Mevcut metnin aradığınız 200 karakterden 199’unu içerdiğini keşfettiğinizde, hayal kırıklığı yaratacaktır.

Başka bir dezavantaj var. Dizenin nerede eşleştiğini ve dolayısıyla nerede eşleşmediğini söylemek kolay olsa da, eşleşmediğinde yalnızca küçük bir ekleme veya silme olup olmadığını anlamak zordur. Bu gibi araçlar için önemlidir diff ve rsync sadece neyin uyuştuğunu bilmek istemedikleri yerde, işlerin neden uyuşmadığını anlamak isterler.

bakıyordu rsyncaslında, bu nasıl olduğunu görmemi sağladı rsync yuvarlanan bir sağlama toplamı kullanarak iki dosyayı karşılaştırır. Her uygulama için olmayabilir, ancak hile çantanızda olması ilginç bir şey. Açıkçası, bu “yuvarlanan sağlama toplamı” algoritmasının en iyi kullanımlarından biri tam olarak nasıl rsync onu kullanır. Yani, dosyaların ne zaman farklı olduğunu çok hızlı bir şekilde bulur ama aynı zamanda ne zaman aynı hale döndüklerini bulmak için makul bir iş yapabilir. Referans çerçevesini yuvarlayarak, rsync bir şeyin eklendiğini veya silindiğini algılayabilir ve uygun değişiklikleri uzaktan yaparak ağ bant genişliğinden tasarruf edebilir.

Arayışında

Ancak, büyük metin aramalarını işlemek için aynı stratejiyi kullanabilirsiniz. Bunu yapmak için, öğeleri kolayca yerleştirip çıkarabilen bir karma algoritmaya ihtiyacınız var. Örneğin, sağlama toplamı algoritmasının çok basit olduğunu varsayalım. Her harf için ASCII kodlarını birlikte eklemeniz yeterlidir. Yani “AAAB” dizisi 65 + 65 + 65 + 66 veya 261’e hash olur. Şimdi bir sonraki karakterin bir C, yani “AAABC” olduğunu varsayalım. İlk A’yı (65) çıkararak ve bir C (67) ekleyerek ikinci konumdan başlayarak sağlama toplamını hesaplayabiliriz. Elbette bu küçük veri seti ile aptalca, ancak her hash hesaplamak istediğinizde sayılara yüzlerce eklemek yerine, şimdi her birini bir toplama ve çıkarma ile yapabilirsiniz.

Daha sonra arama dizimiz için hash değerini hesaplayabilir ve aynı uzunluktaki dosyanın hashlerini hesaplamaya başlayabiliriz. Hash kodları uyuşmuyorsa eşleşme olmadığını anlarız ve devam ederiz. Eşleşirlerse, karmalar genellikle kesin olmadığı için muhtemelen eşleşmeyi doğrulamamız gerekir. İki dize aynı karma değere sahip olabilir.

Bununla birlikte, bununla ilgili birkaç sorun var. Yalnızca tek bir dize arıyorsanız, karma hesaplamanın maliyeti pahalıdır. En kötü durumda, her karakter için bir karşılaştırma, bir toplama ve bir çıkarma yapmanız gerekecek, ayrıca bir karma çarpışmanız olduğunda belki bazı testler yapmanız gerekecek: aynı karmaya sahip, aslında eşleşmeyen iki dize. Normal şemada, yanlış pozitifler için bazı boşa giden testlerle birlikte her karakter için bir test yapmanız yeterli olacaktır.

Karma algoritmasını optimize etmek için daha meraklı karma yapabilirsiniz. Ancak bunun hesaplanması da daha pahalıdır, bu da ek yükü daha da kötüleştirir. Ancak, ya hepsi aynı uzunlukta bir dizi benzer dizi arıyorsanız? Sonra hash’i bir kez hesaplayabilir ve kaydedebilirsiniz. Bundan sonraki her arama çok hızlı olacaktır çünkü birçok çıkmazı araştırmak için sadece geri gitmek için zaman kaybetmezsiniz.

“” için arama yaparken “” noktasında bir çarpışma ile karma arama

Karma algoritmam çok basit ama çok iyi değil. Örneğin, örnekte, fazladan bir karşılaştırmaya neden olacak bir yanlış pozitif olduğunu görebilirsiniz. Elbette, daha iyi karma algoritmalar mevcuttur, ancak her zaman bir çarpışma olasılığı vardır.

Bu karma stratejisini kullanma arasındaki fark ne kadar? karar verdim öğrenmek için küçük bir kod yaz. Yeterince etkileşim üzerinde sıfırlanacakları için, arama modeli karma değerini ve yuvarlanan karmanın ilk bölümünü hesaplamanın maliyetini göz ardı etmeye karar verdim.

hükümlü

Project Gutenberg’in Savaş ve Barış metninde “mahkum” kelimesini ararsanız, bunun 3,3 milyon karakterde yalnızca dört kez geçtiğini görürsünüz. Normal bir arama bunu anlamak için yaklaşık 4,4 milyon karşılaştırma yapmak zorundaydı. Hash algoritması, 4,3 milyonun hemen altında kolayca kazanır. Ancak karma hesaplama onu mahveder. Toplama ve çıkarmayı iki karşılaştırmayla aynı maliyet olarak sayarsanız, bu toplamda yaklaşık 5,8 milyon sözde karşılaştırma ekler.

Bu tipik mi? Muhtemelen “mahkum” için çok fazla yanlış pozitif yoktur. Kodu, çok sayıda yanlış isabet alması gereken “the” kelimesiyle çalıştırırsanız, geleneksel algoritma yaklaşık 4,5 milyon karşılaştırma yapar ve karma algoritma için ayarlanmış toplam yaklaşık 9,6 milyondur. Böylece yanlış pozitiflerin normal algoritmayı nasıl etkilediğini görebilirsiniz.

Benim cansız karma algoritmamın, bazı faydaları aşındıran çok sayıda yanlış karma pozitif ile sonuçlandığını da not edeceksiniz. Daha karmaşık bir algoritma yardımcı olabilir, ancak aynı zamanda bazı ön hesaplamalara da mal olur, bu nedenle düşündüğünüz kadar yardımcı olmaz. Rastgele bir dize için neredeyse herhangi bir karma algoritmada bazı çarpışmalar olacaktır. Elbette, küçük arama dizileri için karma, arama dizisi olabilir ve bu mükemmel olur, ancak genel durumda bu mümkün değildir.

Kod, karmaları kaydetmez, ancak kaydettiğini ve ilk aramanın yanlış pozitif oranının ortalama olarak olduğunu varsayalım. Bu, karmalar önceden hesaplandıktan sonra arama başına 100.000’den biraz daha fazla karşılaştırma kaydettiğimiz anlamına gelir. Yani bir kez 60 kadar dizi aramak zorunda kaldığınızda, başa baş gelirsiniz. 600 dize ararsanız – ancak hepsinin aynı boyutta olması gerektiğini unutmayın – kolay karşılaştırma kodundan biraz tasarruf edebilirsiniz.

Aslında zamanlama yapmadım çünkü her bir kod parçasını optimize etmek istemedim. Genel olarak, daha az işlem, daha fazla işlemden daha iyi olacaktır. Kodun verimliliğini artırmanın birçok yolu vardır ve ayrıca arama dizesini biraz analiz ederseniz uygulayabileceğiniz bazı buluşsal yöntemler vardır. Ama ben sadece her bir algoritmanın metni aramak için ne kadar harcadığına dair içgüdüsel hissimi doğrulamak istedim.

yansımalar

İlk başta kodunu okuduktan sonra bunu düşünmeye başladım. rsync ve yedekleme programı kup. Bunun için bir isim olduğu ortaya çıktı, Rabin-Karp algoritması. Yanlış pozitifleri azaltabilen ve birkaç ekstra verimlilik puanı alabilen bazı daha iyi karma işlevleri vardır.

Amacım ne? Bir RK aramasının bazı şeyler için en iyi yaklaşımınız olduğunu önermiyorum. Bundan bir avantaj elde etmek için gerçekten çok sayıda sabit boyutlu arama içeren büyük bir veri setine ihtiyacınız var. gibi bir şey düşünürseniz rsync, iki çok uzun dizenin eşit olabileceği yerleri aramak için gerçekten karmaları kullanıyor. Ancak bu tuhaf algoritmaların mantıklı olabileceği durumlar olduğunu düşünüyorum, bu yüzden onlar hakkında bilmeye değer. Küçük bir kod yazarak ve bir algoritmanın diğerinden ne kadar daha iyi veya daha kötü olduğuna dair bazı tahminler alarak sezgilerinize meydan okumak da eğlencelidir.


Kaynak : https://hackaday.com/2022/06/22/linux-fu-roll-with-the-checksums/

Yorum yapın

SMM Panel