Merhaba sevgili e-bergi okurları. Uzun bir aradan sonra bu kez e-bergi için arama motoru teknolojilerini anlatmak istiyorum. Tabii ki arama motorlarının pek çok farklı yönü ve kullandıkları pek çok teknoloji var. Örneğin İnternet’i gezip (crawl) web sayfalarının içeriklerini kopyalama, bunları bir sunucu kümesinde kaydedip dizinleme (indeksleme), siteleri popülerliklerine göre puanlama, vb. Bu yazıda metin dizinleme ve arama üzerine odaklanacağız.

Pek çok arama motorunun temel girdisi ve çıktısı metinlerdir. Dosyaların veya web sitelerinin içeriklerini kalıcı girdi, kullanıcıların girdiği sorguları (query) yani arama sözcüklerini de geçici girdi olarak görebiliriz. Çıktı olarak da bu web siteleri veya belgelerden bizim arama sözcüklerimize uyanlar bulunur. Bu temel işleme bilgi erişimi (information retrieval), bu işlemi yapan sistemlere de bilgi erişim sistemleri denir. Google, Bing, Yandex gibi arama motorları ile Lucene gibi yazılım kütüphaneleri en bilinen bilgi erişim sistemlerini oluşturur; ve bilgisayar biliminin bir alt alanı olan information retrieval alanının prensiplerine göre çalışır.

Aranan sözcükler nasıl bulunur?

Öncelikle gelin bu konuyu basit bir probleme indirgeyelim. Aşağıda listelenen, sadece birer cümlelik 8 belge olsun elimizde:

1. İnternet ve arama motorlarının gelişmesi bilgisayar kullanımını da önemli ölçüde arttırdı.
2. Bu yıl da Google en çok arama yapılan İnternet sitesi oldu.
3. Yeni bilgisayar alırken işlemci, hafıza, ekran gibi pek çok unsura dikkat etmek gerekir.
4. Dizüstü bilgisayar ve masaüstü bilgisayar arasında en önemli fark taşınabilirliktir.
5. Baş yaralanmaları geçici ve kalıcı hafıza kaybına yol açabilir.
6. Bilgisayar, kendisine verdiğimiz bilgileri istediğimizde saklayabilen, istediğimizde geri verebilen cihaza denir.
7. Bilgisayar açıldıktan hemen sonra ekranda görev çubuğu ve masaüstü simgeleri belirir.
8. Google haritalar uygulamasının baş mühendisi, blogunda yeni sürümlerini duyurdu.

Diyelim ki içinde Google sözcüğü geçen belgeleri bulmak istiyoruz. Şimdi bunu yapabilmek için basitten gelişmişe doğru üç yolu inceleyeceğiz:

1- Kelime kelime kıyaslama

En basit yöntem şüphesiz ki bu dosyaların her birini satır satır, kelime kelime okuyup aradığımız kelimenin içlerinde olup olmadığına bakmaktır ve tabii ki doğru sonuç verecektir. Ancak bu yol ne yazık ki hiç verimli değildir.

Bu küçük örnekte kolayca yapılabilen kelime kelime kıyaslama, binlerce belge veya milyarlarca web sayfası içinde arama yapmak istiyorsanız son derece uzun sürer. Eğer ki 100.000 sayfalık bir dosyalar grubunda arama yapıyorsanız, her arama için 100.000 sayfanın tamamını okumak zorundasınız. Eğer elimizdeki belge sayısına n, bir belgedeki ortalama sözcük sayısına m dersek, bu işlemin algoritmik karmaşıklığı (maliyeti) O(m*n) olacaktır.

2- Alfabetik dizinleme

Önceki tekniğin yavaşlık sorununu çözmek için elimizdeki belgeleri bir ön işlemden geçirip alfabetik olarak dizinlemeyi (indeksleme) düşünebiliriz. Yani elimizdeki bütün belgeler alfabetik olarak dizinlenecek, biz de bu dizin sayesinde aradığımız belgeye daha hızlı ulaşabileceğiz. Doğru veri yapılarını kullanmamız halinde O(log n) sürede istediğimiz sonuçları bulabiliriz.

Ancak dikkatli okuyucuların hemen fark edebileceği gibi bu durumda ancak aradığımız sözcüğün belgenin en başında olduğu sonuçları bulabiliriz. Örneğin Google sözcüğünü aradığımızda yalnızca sekiz numaralı belgeyi kolayca bulabilirdik. Ancak 2 numaralı belge, “en son” sözcükleriyle başladığı için gözümüzden kaçardı.

Bazı uygulamalarda yalnızca başlardaki eşleşmeleri bulmak istenen sonuç olabilir. Örneğin isme göre dizilmiş bir telefon defterinde kişilerin ilk adına göre arama yapmak istersek alfabetik bir dizin idealdir. Ancak birisini soyadına göre bulmak böyle bir defterde kolay olmaz. Pek çok uygulamada aradığımız sözcük belgelerin neresinde geçerse geçsin bulabilmek isteriz. Yani bu yöntem istediğimiz sonucu vermez.

3- Ters dizinleme (inverted indexing):

Peki ikinci yöntemin hız avantajıyla birincinin avantajı olan belgelerin herhangi bir yerinde geçen kelimeleri bulabilme esnekliğini nasıl birleştirebiliriz? Elimizdeki belgeleri bir bütün halinde alfabetik olarak dizmek yerine, içlerindeki kelimeleri teker teker ayrıştırıp bunları alfabetik olarak dizebilir; her kelime için de hangi belgelerin içinde geçtiğini saklayabiliriz. Örneğin, biraz önceki belgeler için aşağıda bir kısmı gösterilen listeyi çıkarabiliriz:

• arama: 1
• baş: 5 8
• bilgisayar:1 3 4 6 7
• dizüstü: 4
• ekran: 3
• google: 2 8
• görev: 7
• hafıza: 3 5
• internet: 1 2
• işlemci: 3
• masaüstü: 4 7

Elimizdeki belgeleri bu şekilde kelimelerine ayrıştırma ve bir alfabetik olarak listeleme işlemine ters dizinleme (inverted indexing) diyebiliriz. Elimizde buna benzer bir dizin varsa, sorguladığımız sözcüğün hangi belgelerde geçtiğini ikinci yöntemdeki gibi çok kısa zaman içinde bulabiliriz. Toplam sözcük sayısı n olan bir veri tabanında, bu süre O(log n) olacaktır. Üstelik ilk yöntemdeki gibi aradığımız kelime belgenin neresinde geçerse geçsin ona ulaşabiliriz. İşte günümüz modern arama motorlarının hepsi buna benzer şekilde belgeleri ve İnternet sitelerini dizinleyerek onlara hızlı bir şekilde ulaşılmasını sağlarlar.

Karmaşık sorgu tipleri

Biraz önce bir ters dizin oluşturarak tek sözcükten oluşan basit bir sorgunun ne şekilde cevaplandırılabileceğini gördük. Ancak örneğimizde sadece tek kelimeden oluşan sorguların nasıl yanıtlanabileceğini gördük. Google gibi arama motorları bize farklı türlerde sorgular yapma imkanı da sağlar.

Şimdi gelin information retrieval alanının temelini oluşturan bu teknikle bazı daha karmaşık sorguları nasıl cevaplayabiliriz buna bakalım.

Çok sözcüklü sorgular

Çoğu zaman bir arama motorunu kullanırken yalnızca tek bir sözcük değil birden fazla sözcük yazıp aratırız. Arama motorunun, bu sözcüklerin hepsini içeren belgeleri bulmasını isteriz. Bu tür aramalarda kullanıcı sorgusu da aynen diğer belgeler gibi kelimelerine ayrıştırılıp ayrı ayrı aranır ve sonuçlar birleştirilir.

Örneğin internet ve google sözcüklerinin ikisinin de geçtiği dosyaları bulmak, oluşturduğumuz ters dizin sayesinde çok kolaydır. Bu sözcüklerden “internet”in 1 ve 2 numaralı belgelerde; “google”ın da 2 ve 8 numaralı belgelerde geçtiğini hızlı bir şekilde bulduktan sonra yapmamız gereken sadece bu iki sonuç kümesinin kesişimini bulmaktır. Bu örnekte yalnızca iki numaralı belgenin bu sözcüklerden ikisini de içerdiğini görebiliriz.

İstenmeyen sözcükler

Bazen arama yaparken sonuçlar arasında istemediğimiz belgelerin de olduğunu görür, bunları elemek isteriz. Bunun bir yolu sonuçlar içerisinden belli bir kelimeyi içerenleri çıkarmaktır. Örneğin, insan beyni ile ilgili yaptığımız bir araştırmada hafıza sözcüğünü arayıp, bilgisayar bellekleriyle ilgili pek çok istemediğimiz sonucun da çıktığını görürsek, bunlar arasından bilgisayar geçenleri “hafıza -bilgisayar” şeklinde bir aramayla eleyebiliriz.

Biz bu aramayı yaptığımızda, arama motoru önce iki sözcüğün geçtiği belgeleri de dizinde bulur, sonra bu iki kümenin farkını alarak istediğimiz sonuçları bize getirir. Örneğimizdeki belgelerde hafıza 3 ve 5 numaralı belgelerde, bilgisayar da 1, 3, 4, 6 ve 7 numaralı belgelerde geçtiğine göre, içinde hafıza geçip bilgisayar geçmeyen yalnızda üçüncü belgedir.

Sözcük öbekleri

Bazen bağımsız sözcükleri değil, sözcük öbeklerini aratmak isteriz. Google benzeri arama motorlarında bunu, o sözcük grubunu tırnak içine alarak yaparız. Bu sorgu tipi de çok sözcüklü sorgulara benzer; ancak sözcükleri ayrı ayrı arattığımda aldığımız sonuçlar istediğimiz gibi olmayabilir.

Örneğin, “masaüstü bilgisayar” kavramını ararken masaüstü ve bilgisayar sözcüklerini ayrı ayrı aratıp biraz önce anlattığımız yöntemle birleştirdiğimizde 4 ve 7 numaralı belgelerin bu sözcüklerin ikisini de içerdiğini bulabiliriz. Ama bu sözcüklerin istediğimiz sırayla ve yan yana bir öbek olarak yer aldığı, yalnızca 4 numaralı belgedir.

Elimizdeki ters dizin yardımıyla olası sonuç sayısını ikiye indirdikten sonra bu belgelere teker teker bakarak sözcüklerin yan yana olup olmadığını anlamak mümkündür. Ancak çok fazla olası sonuç bulmamız durumunda bu işlem de uzun sürebilir. Alternatif olarak, elimizdeki ters dizini hazırlarken her sözcüğün hangi belgelerde geçtiği bilgisinin yanında, bu belgelerin içinde hangi pozisyonlarda, yani kaçıncı kelime olarak geçtiğini de kaydedebiliriz. Böylece aşağıda bir kısmı gösterilen, daha kapsamlı bir dizinimiz olur.

• bilgisayar: 1(6) 3(2) 4(2, 5) 6(1) 7(1)
• masaüstü: 4(4) 7(9) ...

Biraz önceki örnekte, elimizde sözcük pozisyonlarının da yer aldığı yukarıdaki gibi bir dizin olsaydı, bilgisayar sözcüğünün 4 numaralı belgede ikinci ve beşinci pozisyonlarda, 7 numaralı belgede ise birinci sözcük olarak geçtiğini anlardık. Benzer şekilde masaüstü sözcüğünün de bu belgelerde kaçıncı sözcük olarak geçtiğini bildiğimizden, yalnızca 4 numaralı belgede bunların “masaüstü bilgisayar” şeklinde yan yana yer aldığını sadece dizinimize bakarak kolayca bulabilirdik. Böylece 7 numaralı belgeyi okumamıza gerek kalmadan baştan eleyebilirdik.

Sözcük pozisyonları gibi ek bilgilerin dizinde saklanması şüphesiz ki dizinimizin boyutunu arttıracaktır. Ancak sözcük öbeği gibi aramalarda istediğimiz sonuca daha hızlı ulaşmamızı sağladığı ve arama sonuçlarının sıralanması gibi ek faydaları da olduğu için genellikle dizinlerin bir parçası olarak saklanır.

Son söz

Bu yazımızda (metin) arama motorlarının, kullanıcıların yazdığı sorgu sözcüklerini kullanarak nasıl aranan belgeleri bulduğunu ve bunun için hangi temel veri yapısının kullanıldığını anlattık. Böylece bilgi erişimi (information retrieval) alanında da kısa bir giriş yapmış olduk. Bir başka yazımızda da arama kalitesinin ölçülmesi, sonuçların sıralanması, daha çok sonuca ulaşma yöntemleri gibi daha detaylı konuları tartışmak üzere şimdilik hoşçakalın..