Arama motorları nasıl çalışır?
Yazar | Code Hai
Editör | Tu Min
Önsöz
Her gün Google ve Baidu gibi arama motorlarını kullanıyoruz.Arama motorlarının nasıl uygulandığını hiç düşündünüz mü? Görünüşe göre basit olan arama aslında teknik detaylarda çok karmaşık. Arama motorlarının BT'nin tacındaki mücevher olduğunu söylemek abartı olmaz. Bugün, arama motorlarının ilkelerine kısaca bir göz atalım ve nasıl çalıştıklarını görelim. Elbette, arama motorları kapsamlı ve derindir. Bir makale tam olarak tanıtılamaz. Sadece en önemli adımları tanıtacağız. Her zaman, arama motorları bu önemli adımlardan ayrılamaz ve geri kalanı onlara tuğlalar eklemekten başka bir şey değildir. Bu nedenle, bu "kritik yollara" hakim olmak, her şeye bir göz atma amacına ulaşabilir.
Bu makale, aşağıdaki bölümlerden arama motorlarını tanıtacak ve arama motorlarının çalışma prensiplerini ve bunlarda kullanılan bazı klasik veri yapıları ve algoritmaları derinlemesine analiz edecek, okuduktan sonra kesinlikle bir şeyler kazanacağınıza inanıyorum.
Arama motoru sistem mimarisi diyagramı
Arama motorlarının çalışma prensibinin detaylı analizi
Arama motoru sistem mimarisi diyagramı
Arama motorunun genel yapısı aşağıdaki şekilde gösterilmiştir. Kabaca toplama, ön işleme, indeksleme ve sorgulama olmak üzere dört aşamaya ayrılabilir. Her adımda birçok teknik ayrıntı vardır. Her adımın çalışma prensibini aşağıda ayrıntılı olarak analiz edeceğiz.
Arama motorlarının çalışma prensibinin detaylı analizi
1. Toplayın
Tarayıcı başlangıçta nereden başlayacağını bilemez, bu nedenle ona Sina ana sayfası, Tencent ana sayfası vb. Gibi yüksek kaliteli tohum web sayfalarına bir dizi bağlantı verebiliriz. Bu ana sayfalar nispeten iyi bilinir ve Alexa sıralamasında da çok yüksektir. Bu yüksek kaliteli başlangıç web sayfalarına ulaştıktan sonra, bu web sayfalarını enine geçiş yoluyla dolaşmaya, web sayfası içeriğini taramaya, buradaki bağlantıları çıkarmaya ve bunları sürekli olarak taranacak sıraya koymaya devam edecekler ve ardından tarayıcı URL'den beklemeye devam edecektir. URL'yi tarama için tarama sırasından çıkarın, yukarıdaki işlemi tekrarlayın ...
Elbette yalnızca bir tarayıcı yeterli değildir. Birden çok tarayıcıyı paralel olarak taramaya başlayabilirsiniz, bu çok daha hızlı olacaktır.
1. Taranacak URL'nin uygulanması
Yüksek performans sağlamak için taranacak url'yi Redis'e koyabiliriz. Redis'in, kesme noktalarında sürekli taramayı desteklemek için kalıcılık işlevini etkinleştirmesi gerektiği unutulmamalıdır. Redis takılırsa, yeniden başlatıldıktan sonra uzun süreli bir işlevi olacaktır. , Taranacak son url'den tekrar taramaya başlayabilirsiniz.
2. Ağır nasıl değerlendirilir
Web sayfalarının tekrar tekrar taranmasını nasıl önleyebiliriz? URL'ler üzerinde tekilleştirme işlemleri yapmamız gerekiyor. Tekilleştirme nasıl elde edilir? Bazı insanlar, bir karma tablo kullanarak, taranacak her URL'yi karma tabloda sakladığını söyleyebilir. Taranacak URL'yi her eklediğinizde, taranıp taranmadığını belirlemek için bu karma tabloyu kullanırsınız. Bu gerçekten sorun değil, ama biz Dikkat edilmesi gereken şey, bunun büyük bir alan maliyeti gerektirmesidir. Ne kadar büyük? Hadi basit bir hesaplama yapalım. 1 milyar url olduğunu varsayalım (1 milyarın çok büyük olduğunu düşünmeyin. Google ve Baidu gibi arama motorları istedikleri sayfaları tarayacaktır. Büyüklük 1 milyardan çok daha büyük), hash tablosunda ne kadar depolama alanı gerekiyor?
Her web sayfası URL'sinin ortalama 64 bayt uzunluğa sahip olduğunu ve 1 milyar URL'nin yaklaşık 60 G bellek gerektirdiğini varsayıyoruz. Bir karma tabloyla uygulanırsa, aşırı çakışmaları önlemek için daha küçük bir yük faktörü gerekir (hash varsayılırsa) Tablonun 10 öğe ile yüklenmesi gerekir ve 20 öğe için alan, hash çakışmalarını önlemek için gerçekten tahsis edilebilir.Aynı zamanda, ister zincir depolama ister kırmızı-siyah ağaç olsun, çakışmaları ele almak için işaretçiler saklanmalıdır. Gerekli bellek 100 G'yi geçebilir ve bir çakışma olduğunda bağlantılı listedeki dizeleri karşılaştırmanız gerekir.Performans da bir kayıptır.Elbette 100 G büyük arama motorları için büyük bir sorun değil ama aslında uygulanabilecek başka bir çözüm var. 100 G'den çok daha az bellek: Bloom filtresi.
1 milyar URL için 10 milyar bit, yaklaşık 1,2 G ayırıyoruz, bu da 100 G bellekten neredeyse yüz kat daha hızlıdır! Makul bir teknik çözüm seçiminin, maliyetleri düşürme ve verimliliği artırma etkisini iyi bir şekilde sağlayabileceği görülebilir.
Elbette, bazı insanlar soru sorabilir. Bloom filtreleri yanlış değerlendirilebilir, yani, Bloom filtresi tarafından bir değerin var olmadığına karar verilirse, bu değer mevcut olmamalıdır, ancak Bloom filtresi tarafından var olduğu yargılanırsa, o zaman Bu değer mutlaka mevcut değildir. Bu durumda, Bloom filtresinin karma işlevini veya temeldeki bit eşlemin boyutunu ayarlayarak yanlış değerlendirme olasılığını olabildiğince azaltabiliriz, ancak şu anda yanlış değerlendirme devam ederse, Bu tür bir URL için, taramak iyi değildir, sonuçta, İnternette o kadar çok web sayfası var ki, birkaçını taramak zarar vermez.
3. Web sayfası saklama dosyası: doc_raw.bin
Web sayfasını taradıktan sonra web sayfası nasıl saklanmalıdır? Bazıları bir web sayfasında bir dosya depolamanın yeterli olmadığını söyler.Bu durumda 1 milyar web sayfası 1 milyar dosya saklayacaktır.Genel dosya sistemi bunu desteklemiyor, yani genellikle Web sayfasının içeriği aşağıdaki gibi bir dosyada (doc_raw.bin varsayılarak) saklanır
Tabii ki, genel dosya sisteminin 1 G gibi tek bir dosyanın boyutu için bir sınırı vardır, ardından dosya 1 G'yi aştıktan sonra yeni bir tane oluşturun.
Şekilde web sayfası kimliği nasıl oluşturulur? Açıktır ki bir url bir web sayfası kimliğine karşılık gelir, böylece bir yayıncı ekleyebiliriz. Bir web sayfasını taradıktan sonra, yayıncı ona bir kimlik atar ve web sayfası kimliğini ve url'yi bir Dosyada, aşağıdaki gibi, adın doc_id.bin olduğunu varsayarsak
İki, ön işlem
Bir web sayfasını taradıktan sonra, onu ön işlemden geçirmemiz gerekir. Elde ettiğimiz şey, web sayfasının html kodudur. < senaryo > , < stil > , < seçenek > Bu işe yaramaz etiketler ve etiketlerin içerdiği içerik kaldırılır.Bunun nasıl bulunacağı bir bilgidir.Bazı insanlar BF ve KMP gibi algoritmaların gerçekten iyi olduğunu söyleyebilir, ancak bu algoritmalar tek modelli dizi eşleştirme algoritmalarıdır ve tek bir alan dizisini sorgulama etkinliği gerçekten iyidir. , Ama hepsini bir kerede öğrenmek istiyoruz < senaryo > , < stil > , < seçenek > Bu alan dizgileri, herhangi bir iyi yol var mı? Cevap, aranacak birkaç alan dizisini aynı anda verimli bir şekilde bulabilen AC automata çok modelli dizi eşleştirme algoritmasını kullanmaktır.Ne kadar verimli ve zaman karmaşıklığı 0 (n) 'ye yakın! AC otomata çoklu model eşleştirme algoritması ilkesi tanıtılmayacaktır.Arama yapmak ve aramak için İnternet'e gidebilirsiniz.İşte size fikir sunmak için.
Bu etiketlerin başlangıç konumunu bulduktan sonra, gerisi basittir. Sonra, bu etiketlerin her biri için bitiş etiketini arayın. < /senaryo > , < / stil > , < / seçenek > Onu bulduktan sonra, başlangıç ve bitiş etiketlerini ve içlerindeki tüm içeriği kaldırın.
Yukarıdaki adımları tamamladıktan sonra, diğer html etiketlerini de kaldırmamız gerekir (etiketlerdeki içerik korunur), çünkü nihayetinde uğraşmamız gereken şey saf içeriktir (içerik, kullanıcıların aramak istediği anahtar kelimeleri içerir)
Üç, kelime segmentasyonu ve ters çevrilmiş bir dizin oluşturun
Yukarıdaki adımlarda işlenen içeriği aldıktan sonra, içeriği segmentlere ayırmamız gerekiyor Kelime segmentasyonu nedir, bir metin paragrafını tek tek kelimelere bölmektir. Örneğin, "Ben bir Çinliyim" kelimesinden sonra "ben", "am", "a" ve "çince" olmak üzere dört kelime vardır. Buradan da görülebilir ki İngilizce kelime katılımcısı nispeten basittir ve her kelime temelde kullanılır Boşlukla ayrılmış, karakter dizisi ayırıcı olarak boşlukla kesildiği sürece, kelime bölütleme etkisi temelde elde edilebilir, ancak Çince farklıdır.Kelimeler ve sözcükler arasında bölümlere ayırması daha zor olan boşluk ve başka dize bölümlemesi yoktur. Örnek olarak "Pekin Tsinghua Üniversitesine geldim" ifadesini ele alalım. Farklı modlar farklı kelime segmentasyonu sonuçları üretir. Örnek olarak github'daki ünlü jieba kelime segmentasyonu açık kaynak kitaplığını alın, aşağıdaki kelime segmentasyon modlarına sahiptir
[Tam Mod]: Ben / Gel / Pekin / Tsinghua / Tsinghua Üniversitesi / Huada / Üniversite [Doğru Mod]: I / come / Beijing / Tsinghua University [Yeni Kelime Tanımlama]: O, burada, şimdi, Netease, Hangyan, Mansion [Arama Motoru Modu]: Xiao Ming, usta, Çin'de, bilim, akademi, bilim akademisi, Çin Bilimler Akademisi, bilgisayar, bilgi işlem, daha sonra Japonya, Kyoto, Üniversite, Kyoto Üniversitesi, Japonya, yüksek lisans mezunuKelime bölümleme genellikle hazır bir eş anlamlılar sözlüğüne göre yapılır.Örneğin, eşanlamlılar sözlüğünde "Çin" kelimesi varsa, eşleştirmek için işlenmiş web sayfası metnini kullanabilirsiniz. Elbette, "de", "" ve "" gibi bazı anlamsız durdurma sözcüklerini katılımcıdan önce kaldırmamız gerekiyor.
Kelime segmentasyonundan sonra, her kelime segmenti ile metni arasındaki ilişkiyi aşağıdaki gibi elde ederiz.
Dikkatli olun, farklı web sayfası içeriğinin aynı kelime segmentasyonuna sahip olabileceğini keşfetmiş olmalısınız, bu nedenle aşağıda gösterildiği gibi aynı kelime segmentasyonuna sahip web sayfalarını birlikte gruplandırıyoruz
Bu şekilde "üniversite" araması yaptığımızda ve "üniversite" ile ilgili satırı bulduğumuzda, "üniversite" içeren tüm belge kimliklerini bulabiliriz.
Yukarıdaki "kelime segmentasyonu" + "ters çevrilmiş indeks" işlem akışını görünce, ne düşünüyorsunuz? Bu doğru, ElasticSearch arama motorunun yaptığı bu değil ve aynı zamanda ES'nin milisaniye yanıt elde etme becerisinin anahtarıdır!
Burada başka bir sorun daha var: Belirli bir kelimeye dayalı bir dizi web sayfasının kimliğini aldıktan sonra, hangi web sayfalarının sonuç ekranında ilk sıralanması gerektiği, neden Google'da genel olarak ilk sayfanın ilk birkaç satırında arama yapıyoruz İstediğimiz cevabı bulabiliriz. Bu, arama motorlarında yer alan bir başka önemli algoritmayı içerir: Google tarafından web sayfalarını sıralamak için kullanılan bir algoritma olan PageRank.Web sayfalarının önemini kabaca analiz etmek için web sayfaları arasındaki köprülerin sayısını ve kalitesini ana faktörler olarak kullanır. Puanlamak için seks. Genel olarak soru aradığımızda, ilk bir veya ikisi temelde yığın akışı sayfalarıdır; bu, Google'ın bu sayfanın oldukça ağırlıklı olduğuna inandığı anlamına gelir çünkü bu sayfa dünyadaki hemen hemen tüm programcılar tarafından kullanılır, bu da sayısız sayfa olduğu anlamına gelir. Bu web sitesine bağlantı, PageRank algoritmasına göre, doğal olarak bu web sitesinin ağırlığı, peki, aslında, PageRank'in hesaplanmasının çok fazla matematik bilgisi gerektirdiğini düşünebilirsiniz.Ne de olsa bu algoritma Google'ın temelini oluşturuyor. Eğer ilgileniyorsanız, daha fazlasını öğrenmek için internete gidebilirsiniz.
Yukarıdaki adımları tamamladıktan sonra, arama motoru web sayfasını işlemeyi bitirdi, peki kullanıcı anahtar kelimeyi girdiğinde arama motoru bize sonuçları nasıl gösteriyor?
Dört, sorgu
Kullanıcı bir anahtar kelime girdikten sonra, önce bir jetonlaştırıcı tarafından işlenmelidir. Örneğin, belirteç oluşturucunun onu "Çin" ve "" adlı iki kelimeye böldüğünü varsayarak "Çinliler" yazıyorum ve ardından ters çevrilmiş dizindeki ilgili belgeleri aramak için bu iki kelimeyi kullanıyorum
Web sayfası kimliğini aldıktan sonra, web sayfasının bağlantılarını ve içeriğini çıkarmak ve bunları azalan ağırlık sırasına göre düzenlemek için doc_id.bin ve doc_raw.bin'e gidiyoruz.
Buradaki ağırlık sadece yukarıda bahsedilen PageRank algoritmasıyla değil, aynı zamanda başka bir "TF-IDF" (https://zh.wikipedia.org/wiki/Tf-idf) algoritmasıyla da ilgilidir, gidip öğrenebilirsiniz.
Ayrıca, arama kutusuna bir arama terimi girdiğinizde, aşağıda bir dizi arama uyarısı göreceğinizi düşünüyorum.
Resimde gösterildiği gibi: Dört harfli çene girdikten sonra, aşağıda hızlı kelimelerin bir listesi görünecektir.
Bunu nasıl başaracağımızı, bir ağaç yapısından bahsetmemiz gerekiyor: Trie ağacı. Trie ağacı ayrıca sözlük ağacı, önek ağacı (önek ağacı), kelime arama ağacı olarak da adlandırılır, aşağıdaki şekilde gösterildiği gibi bir tür çok ağaçlı yapıdır:
Bu çoklu ağaç bir dizi anahtar kelimeyi temsil eder. Trie ağacının şu özelliklere sahip olduğu görülebilir:
Kök düğüm karakter içermez ve kök düğüm dışındaki her alt düğüm bir karakter içerir
Kök düğümden belirli bir düğüme, yoldan geçen karakterler düğüme karşılık gelen dizeye bağlanır.
Her düğümün tüm alt düğümleri farklı karakterler içerir
Genellikle uygulamada, düğümde bir sözcüğün (anahtar sözcük) oluşup oluşmadığını işaretlemek için düğüm yapısında bir bayrak ayarlanır.
Ayrıca bir kural, ortak öneklere sahip anahtar kelimeler (kelimeler) bulmak bizim için zor değil, Trie ağacında önekleri aynı, bu yüzden Trie ağacına önek ağacı deniyor.Bu fikirle tasarlamamız zor değil Yukarıda açıklandığı gibi arama yaparken bir dizi arama istemi kelimesini görüntüleme fikri:
Genel bir arama motoru bir eşanlamlılar sözlüğü tutar. Bu eşanlamlılar sözlüğünün, arama sayısı belirli bir eşikten (1000 gibi) büyük olan tüm dizelerden oluştuğunu varsayarsak, bu eşanlamlılar sözlüğünü bir Trie ağacı oluşturmak için kullanabiliriz, böylece kullanıcı harfleri girdiğinde , Trie ağacında arama yapmak için bu harfi önek olarak kullanabilirsiniz. Yukarıdaki makalede bahsedilen Trie ağacı bir örnektir. "Te" girdiğimizde, "te" ön ekli kelimeler olduğundan arama motorunda görüntülenecektir. Bu dizeler, kullanıcıların seçmesi için kutuda görüntülenebilir.
5. Popüler arama dizelerini bulun
Trie ağacı, hızlı sözcükleri aramak için bir önek ağacı olarak kullanılmasının yanı sıra, Trie ağacı biraz değiştirildiği sürece popüler arama dizelerini bulmaya yardımcı olmak için de kullanılabilir. En popüler 10 arama dizesini bulmak istediğimizi varsayalım, özel uygulama fikirleri aşağıdaki gibidir:
Genel arama motorlarının, kullanıcı arama terimlerini kaydetmek için özel günlükleri olacaktır.Bu kullanıcı arama terimlerini bir Trie ağacı oluşturmak için kullanıyoruz, ancak Trie ağacını biraz değiştirmemiz gerekiyor. Yukarıda belirtildiği gibi, Trie ağacı uygulandığında, Düğümün bir kelime oluşturup oluşturmadığını işaretlemek için düğümde bir bayrak ayarlayabilir veya bu bayrağı, sonlandırma karakteri olarak düğümle birlikte arama dizelerinin sayısına değiştirebilirsiniz.Her arama dizisi Trie ağacında geçilir. Çapraz geçişin son düğümündeki dize sayısına 1 ekleyin, her dizenin kaç kez arandığını sayabilirsiniz (kök düğümden düğüme giden yol arama dizesidir) ve sonra bir 10 düğüme sahip küçük üst yığın (aşağıda gösterildiği gibi, yığının en üst öğesi diğer tüm öğelerden daha küçüktür)
Resimde gösterildiği gibi: küçük üst yığındaki üst eleman diğer tüm elemanlardan daha küçüktür
Sırayla Trie ağacının düğümlerini geçin, düğümü (dizi + kez) küçük üst yığına geçirin ve arama sayısına göre küçük üst yığını sürekli olarak ayarlayın, böylece Trie ağacının düğümlerini geçtikten sonra, küçük üst yığındaki 10 düğüm en fazladır. Popüler arama dizeleri.
sonuç olarak
Bu makale kısaca arama motorlarının çalışma prensibini anlatmaktadır.Okuduktan sonra çalışma prensiplerini daha net bir şekilde anlamanız gerektiğine inanıyorum.Birçok klasik veri yapısı ve algoritmanın arama motorlarında kullanıldığını görebiliyoruz, bu yüzden artık herkes yapabilmelidir. Google ve Baidu gibi şirketlerin aday algoritması konusunda neden bu kadar yüksek gereksinimleri olduğunu anlıyorum.
Bu makale sadece arama motorlarının temel çalışma prensiplerini tanıtmaktadır, daha fazlasını anlamak için daha fazla bilgiyi kontrol etmeniz gerekmektedir.
Çin yeni bir açık kaynak çağını başlatıyor!
Hong Kong, Zoom testini Çince olarak kullanıyor ve tarif edilemez içeriği yaymak için ortadan saldırıya uğradı
360 Financein yeni baş bilim adamı: AI Labın orta ofis olmasını beklemeyin
AI görüntüsü eski fotoğrafların akıllı onarımı, efekt benim için harika
Programcının dahili beceri eğitimi serisi: Linux fiziksel belleği ve sanal bellek üzerine 10 örnek
DeFi, Rollup ile karşılaştığında, ne tür bir kıvılcım yaratacak?
