Arama motorlarının ilkeleri, mimarisi ve detayları
Ağ çapında arama motoru mimarisi ve süreci
Tüm ağın makro yapısı neye benziyor?
Tüm ağ aramasının makro süreci nedir?
Tüm ağ arama motorunun makro yapısı yukarıdaki şekilde gösterildiği gibidir. Çekirdek alt sistem esas olarak üç bölüme ayrılmıştır (pembe bölüm):
(1) örümcek paletli sistem
(2) searchindex indeksleme ve sorgu indeks sistemi , Bu sistem temelde iki bölüme ayrılmıştır:
Bir kısım indeks verisi oluşturmak için kullanılır build_index
Bir kısım indeks verilerini sorgulamak için kullanılır search_index
(3) sıralama puanlama sistemi
Temel veriler esas olarak iki kısma ayrılmıştır (mor kısım):
(1) Web sayfası kitaplığı
(2) Endeks verileri
Tüm ağ arama motorunun işletme özellikleri, bunun tamamen ayrı bir "yazma" ve "geri alma" sistemi olduğunu belirler:
Yazmak
Sistem bileşimi Örümcek ve arama dizini olmak üzere iki sistemle tamamlandı
giriş : Web yöneticileri tarafından oluşturulan internet sayfaları
Çıktı : İndeks verilerini ileri ve geri çevir
İşlem : Mimari diyagramda 1, 2, 3, 4 gibi
(1) Örümcek internet sayfasını alır
(2) Örümcek, İnternet web sayfalarını web sayfası kitaplığında depolar (bu, yüksek depolama gerektirir ve neredeyse tüm "World Wide Web" ayna görüntüsünü depolaması gerekir)
(3) build_index, web sayfası kitaplığından verileri okur ve kelime segmentasyonunu tamamlar
(4) build_index tersine çevrilmiş bir dizin oluşturur
Arama
Sistem bileşimi İki searchindex ve rank sistemi ile tamamlandı
giriş : Kullanıcının arama terimi
Çıktı : Arama sonuçlarının ilk sayfası sıralandı
İşlem : Mimari diyagramda a, b, c, d gibi
(A) search_index, kullanıcının arama terimini alır ve kelime segmentasyonunu tamamlar
(B) search_index, ön taramanın sonucu olan "karakter eşleştirme" sayfasını elde etmek için ters çevrilmiş dizini sorgular
(C) sıralaması, ön taramanın sonuçlarını sıralar
(D) sıralaması, sıralamanın ardından ilk sayfa sonucunu döndürür
Üçüncüsü, site arama motoru yapısı ve süreci
Sonuçta, küresel arama yapan sadece birkaç şirket var.Çoğu şirketin başarmak istediği şey aslında yerinde bir aramadır.Site içi arama motorunun makro yapısı ile tüm ağın makro yapısı arasındaki benzerlikler ve farklılıklar nelerdir?
Örnek olarak 58 aynı şehirde 10 milyar gönderi aramasını ele alırsak, yerinde arama sistemi mimarisi neye benziyor? Sitedeki arama süreci nedir?
Sitedeki arama motorunun makro yapısı yukarıdaki şekilde gösterildiği gibidir.Tüm ağ arama motorunun makro yapısı ile karşılaştırıldığında tek fark yazılır:
(1) Tüm ağ araması, örümceklerin verileri pasif bir şekilde ele geçirmesini gerektirir
(2) Site araması, dahili sistem tarafından üretilen verilerdir Örneğin, "yayınlama sistemi" oluşturulan gönderileri aktif olarak build_data sistemine gönderecektir.
Görünüşe göre "küçük" farklılıklar, mimari uygulanıyor Zorluk Ancak daha da kötüsü: tüm ağda "gerçek zamanlı" aramada "tam miktarda" web sayfası bulmak çok zordur ve sitede arama yaparken tüm verileri gerçek zamanlı olarak elde etmek kolaydır.
Üç örümcek, arama dizini ve sıralama sistemi için:
(1) Spider ve searchindex nispeten mühendislik sistemleridir
(2) Rank, işletme, strateji ve algoritmayla yakından ilgili bir sistemdir. Arama deneyimindeki fark esas olarak buradadır ve iş ve stratejinin optimizasyonunun birikmesi zaman alır. Buradaki aydınlanma şudur:
a) Google'ın deneyimi Baidu'nunkinden daha iyidir, çünkü ilki üst sıralarda yer almaktadır
b) Yerli internet şirketlerinin (360 gibi) kısa sürede Baidu dışında bir deneyime sahip bir arama motoru geliştirmesi çok zordur. Biriktirmek gerçekten zaman alır.
Dört, arama ilkesi ve temel veri yapısı
Pozitif indeks nedir?
Tersine çevrilmiş indeks nedir?
Arama süreci nasıldır?
Hangi algoritmalar ve veri yapıları kullanılacak?
Önceki içerik fazla makro ... Daha önce hiç arama motoru yapmamış öğrencilerin çoğunun ilgisini çekebilmek için veri yapısı ve algoritma kısmı önden ve biraz da ters çevrilmiş dizinden başlamaktadır.
Soru: İleri endeks nedir?
Cevapla : Varlıkları anahtara göre sorgulama süreci pozitif bir dizindir.
Kullanıcı tablosu: t_user (uid, name, passwd, age, sex), tüm satırı uid ile sorgulama işlemi pozitif bir indeks sorgusudur.
Web sayfası kitaplığı: t_web_page (url, page_content), tüm web sayfasını url ile sorgulama işlemi de bir ileri dizin sorgusudur.
Sayfa içeriğinin kelime segmentasyonundan sonra, page_content, bir Kelime segmentasyonundan sonra koleksiyon listesi < eşya > .
Basitçe, ileriye doğru indeks Harita olarak anlaşılabilir < url, liste < eşya > > , İçeriğin bir veri yapısı web sayfasından hızlı bir şekilde bulunabilir (zaman karmaşıklığı O (1)).
Soru: Tersine çevrilmiş indeks nedir?
Cevapla : Öğeye göre anahtar sorgulama işlemi ters çevrilmiş bir dizindir.
Web araması için, ters çevrilmiş indeks Harita olarak anlaşılabilir < Eşya listesi < url > > , Sorguyu içeren web sayfasının veri yapısı sorgu ile hızlı bir şekilde bulunabilir (zaman karmaşıklığı O (1)).
Örneğin, 3 web sayfası olduğunu varsayalım:
url1- > "Pekin'i seviyorum"
url2- > "Evi seviyorum"
url3- > "İyi ev"
Bu bir Ön dizin Harita < url, page_content > .
Katılımcıdan sonra:
url1- > {Ben, aşkım, Pekin}
url2- > {Ben, aşk, ev}
url3- > {Evde, güzel}
Bu bir Kelime segmentasyonundan sonra pozitif indeks Harita < url, liste < eşya > > .
Kelime segmentasyonundan sonra tersine çevrilmiş indeks :
BEN - > {url1, url2}
Aşk - > {url1, url2}
Pekin- > {url1}
Ev- > {url2, url3}
Güzel- > {url3}
Arama terimi öğesine göre sorgu terimini içeren web sayfası haritasını hızlıca bulun < Eşya listesi < url > > Ters çevrilmiş indekstir.
İleri indeks ve tersine çevrilmiş indeks, örümcek ve build_index sistemi tarafından önceden kurulmuş veri yapılarıdır. Neden bu iki veri yapısını kullanıyorsunuz? , Çünkü "kullanıcı web araması" gereksinimini hızla gerçekleştirebilir (İş gereksinimleri mimarinin uygulanmasını belirler) .
Soru: Arama süreci nasıldır?
Arama teriminin "Seviyorum" olduğunu varsayarsak, kullanıcı hangi web sayfasını alır?
(1) Participle, "Seviyorum" ortak {, } olacak, zaman karmaşıklığı O (1)
(2) Kelime segmentasyonundan sonraki her öğe için, bu öğeyi içeren web sayfalarının listesini ters çevrilmiş dizinden sorgulayın < url > , Zaman karmaşıklığı da O (1) 'dir:
BEN - > {url1, url2}
Aşk - > {url1, url2}
(3) Arama listesi < url > Kesişimi, tüm sorgu terimleriyle eşleşen sonuç sayfasıdır. Bu örnek için, {url1, url2} son sorgu sonucudur
Burada son gibi görünüyor, ama aslında değil. Kelime bölümlemenin ve ters çevrilmiş sorgunun zaman karmaşıklığı O (1) ve tüm aramanın zaman karmaşıklığı "arama listesi < url > "," Nin kesişimi Problem, iki kümenin kesişimini bulacak şekilde dönüştürülür. .
Karakter URL'leri depolama ve hesaplama için elverişli değildir. Genel olarak konuşursak, her URL'nin onu tanımlamak için sayısal bir url_id'si vardır. Açıklamada kolaylık olması için, < url > Birleşik liste < url_id > Vekil.
List1 ve list2'nin kesişim noktası nasıl bulunur?
Seçenek bir : Yerel yöntem için * için, zaman karmaşıklığı O (n * n)
Her arama terimi tarafından vurulan birçok web sayfası vardır ve O (n * n) 'nin karmaşıklığı açıkça kabul edilemez. Tersine çevrilmiş dizin, oluşturmanın başlangıcında sıralanabilir ve önceden işlenebilir ve sorun dönüştürülür. Kavşağı bulmak için iki sıralı listeye , Çok daha uygun.
Seçenek II : Sıralı listenin kesişimi, fermuar yöntemi
Sıralı set 1 {1,3,5,7,8,9}
Sıralı set 2 {2,3,4,5,6,7}
İki işaretçi ilk öğeyi işaret eder ve öğelerin boyutunu karşılaştırır:
(1) Eğer aynıysa, sonuç kümesine koyun ve bir işaretçiyi istediğiniz gibi hareket ettirin.
(2) Aksi takdirde, işaretçiyi satırın sonuna kadar daha küçük değerle hareket ettirin
Bu yöntemin avantajları:
(1) Kümedeki öğeler en fazla bir kez karşılaştırılır ve zaman karmaşıklığı O (n)
(2) Birden çok sıralı kümeler aynı anda gerçekleştirilebilir ve bu, birden çok sözcük bölümleme öğelerinin ve url_id'nin kesişimi için uygundur
Bu yöntem bir fermuarın iki dişlisi gibidir, tek tek karşılaştırılması fermuar gibidir, bu yüzden Fermuar yöntemi
üçüncü çözüm : Kova paralel optimizasyonu
Veri miktarı büyük olduğunda, url_id bölüm yatay bölümleme + paralel işlem, yaygın bir optimizasyon yöntemidir , List1 ekleyebiliyorsanız < url_id > Ve list2 < url_id > Birkaç kova aralığına bölünmüş olan her aralık, kesişimi paralel olarak bulmak için çoklu iş parçacığını kullanır ve her bir iş parçacığının sonuç kümelerinin birleşimi, nihai sonuç kümesi olarak yürütme süresini büyük ölçüde azaltabilir.
Örneğin:
Sıralı set 1 {1,3,5,7,8,9, 10,30,50,70,80,90}
Sıralı set 2 {2,3,4,5,6,7, 20,30,40,50,60,70}
Kavşağı bulun, önce gruplara ayırın:
Kepçe 1 aralığı
Kepçe 2 aralığı
3 kepçe aralığı
sonra:
Set 1,
Bir {1,3,5,7,8,9} ayarlayın
B {10,30,50,70,80,90} ayarla
C {} ayarla
Set 2,
D {2,3,4,5,6,7} ayarla
E {20,30,40,50,60,70} ayarla
Koleksiyon e {}
Her paketteki veri miktarı büyük ölçüde azaltılır ve her pakette yinelenen öğe yoktur. Çok iş parçacıklı paralel hesaplama kullanılabilir:
Paket 1'de set a ve set d'nin kesişimi x {3,5,7}
2. bölümdeki b kümesi ve e kümesinin kesişimi y {30, 50, 70}
Grup 3'te set c ve set d'nin kesişimi z {}
Son olarak, küme 1 ve küme 2'nin kesişimi, x, y ve z'nin birleşimidir, yani küme {3,5,7,30,50,70}
Dördüncü Seçenek : Bitmap yeniden optimize edildi
Veriler yatay bölümlere ayrıldıktan sonra, Her bir bölümdeki veriler bir aralıkta olmalıdır Set bu özelliği karşılıyorsa, Koleksiyonu temsil etmek için bitmap kullanabilirsiniz :
Yukarıdaki şekilde gösterildiği gibi, set1 {1,3,5,7,8,9} ve set2 {2,3,4,5,6,7} 'nin tüm elemanlarının grup değeri aralığında olduğu varsayılarak, 16 bit kullanılabilir Bu iki kümeyi açıklamak için, orijinal kümedeki x öğesi, bu 16 bit eşlemdeki x'inci bit 1'dir, şu anda iki bit eşlemin "AND'lenmiş" olması gerekir ve sonuç kümesi bit eşlemi 3, 5 ve 7 bitleri 1'dir ve orijinal kümenin kesişme noktasının {3,5,7} olduğunu gösterir.
Bitmap optimizasyonundan sonra yatay katlama, kesişme verimliliğini büyük ölçüde artırabilir, ancak zaman karmaşıklığı hala O (n)
Bitmap çok fazla sürekli alan gerektirir ve çok fazla bellek kullanır
Beşinci Seçenek : Liste atlayıcısını atla
Sıralı bağlantılı liste kümelerinin kesişimi, atlama listesi en yaygın kullanılan veri yapısıdır, sıralı küme kesişiminin karmaşıklığını O (n) 'den O (log (n))' ye kadar azaltabilir.
Küme 1 {1,2,3,4,20,21,22,23,50,60,70}
2 {50,70} ayarlayın
Kesişim gereklidir. Fermuar yöntemini kullanırsanız, 1, 2, 3, 4, 20, 21, 22 ve 23'ün hepsinin bir kez geçersiz bir şekilde geçtiğini göreceksiniz ve her bir öğenin karşılaştırılması gerekir. Zaman karmaşıklığı O (n), Her seferinde "bazı öğeleri atlayabilir misin"?
Atlama tablosu görünür:
Küme 1 {1,2,3,4,20,21,22,23,50,60,70} bir atlama listesi oluşturduğunda, birinci düzeyde yalnızca üç öğe {1,20,50} vardır ve ikinci düzey, sıradan bağlantılı listeyle aynıdır
Set 2 {50,70}, daha az öğe nedeniyle yalnızca birinci düzey bir normal bağlantılı listeye sahiptir
Bu şekilde, "fermuar" kesişimini uygulama sürecinde, setl'in göstericisi 1'den 20'ye ve sonra 50'ye atlayabilir. Ortada birçok öğe atlanabilir, tek tek karşılaştırmaya gerek yoktur , Kesişimi bulmak için atlama tablolarının zaman karmaşıklığı, arama motorlarında yaygın bir algoritma olan yaklaşık O (log (n)) 'dir.
Beş, özet
Makroskopik ve ayrıntılı çok sayıda metin var. Arama motorlarında uzmanlaşmamış çoğu öğrenci için aşağıdaki noktaları unutmayın:
(1) Tüm ağ arama motoru sistemi Üç alt sistemden oluşur: örümcek, arama dizini ve sıralama
(2) Site arama motoru ile tüm ağ arama motoru arasındaki fark Bir örümcek alt sistemi eksik mi
(3) Örümcek ve searchindex sistemleri iki mühendislik sistemidir, ancak sıralama sisteminin optimizasyonu uzun süre ayarlama ve biriktirme gerektirir
(4) İleri dizin Kelime segmentasyonunun url_id sayfası tarafından hızlı bir şekilde bulunmasından sonraki sayfa içerik listesidir. < eşya > süreci
(5) Ters indeks Kelime segmentasyonu öğesi, bu kelime segmentasyonunu içeren web sayfalarının listesini hızla bulur < url_id > süreci
(6) Kullanıcı Arama süreci , Önce kelime segmentasyonudur ve ardından her öğeye karşılık gelen listeyi bulun < url_id > , Ve son olarak kesişme belirleme sürecine geçin
(7) Sıralı kümelerin kesişimini bulma yöntemi Sahip olmak
a) İkili döngü yöntemi, zaman karmaşıklığı O (n * n)
b) Fermuar yöntemi, zaman karmaşıklığı O (n)
c) Yatay kova, çok iplikli paralel
d) işlemlerin paralelliğini büyük ölçüde geliştiren bitmap ve zaman karmaşıklığı O (n)
e) Atlama tablosu, zaman karmaşıklığı O (log (n))
-------------------------------------------------- ----------------------------
Mimarın yolu olan WeChat kamu hesabından transfer
