Tam metin araması (Full-Text Search) nasıl çalışır?

Full-Text Search dokümanlar içinde serbest metin üzerinden arama yapılmasına olanak sağlayan, Web arama motorlarında ve web sayfalarında en çok kullanılan arama metodlarından biridir.

Full-Text Search (tam metin araması) büyük veri blokları arasından herhangi bir kaynaktan alınan metin belgeleri içinden, anahtar kelimenin aratılarak anahtar kelime ile eşleşen dokümanların bulunduğu sonuca hızlı ve daha isabetli bir şekilde erişebilmenizi sağlar.

Tam metin araması şu şekilde çalışır:
İlk önce verileri hızlıca arayabilmek için bir invented index (ters indeks) oluşturulur. Daha sonra bu indeks kullanılarak TF değeri (term frequency, geçiş sıklığı) ve IDF değeri (inverse document frequency, ters belge sıklığı) hesaplanır ve en son bulunan bu iki değer çarpılırak her bir doküman için vektörler oluşturulur ve sorgu cümlesinin vektörü ile arasındaki açı hesaplanır (cosine similarity). Sorgu vektörü ile doküman vektörü arasındaki açı ne kadar küçükse o doküman o kadar ilgili demektir.

TF-IDF değeri tam metin araması dışında belge sınıflandırma, konu modelleme ve stop-word filtreleme olmak üzere çeşitli durumlarda kullanılmaktadır.

Ters indeksleme, dokümanlarınızın içindeki her bir kelime için hangi dokümanlarda o kelimenin olduğu bilgisini tutan bir sistemdir. Ters indeksleme işleminde dokümanlardak kelimeler satırlar şeklinde bölerek onları sütun şeklinde indexler böylece performanslı bir arama yöntemi olur.

TF, terim frekansı anlamına gelir. Bir kelimenin bir belgedeki geçiş sıklığıdır.

IDF, ters belge frekansı anlamına gelir. Belge sayısının incelenen kelimeyi içeren topluluktaki belge sayısına bölümünün logaritması alınarak hesaplanır. Örneğin, belge sayımız 100 ise ve aratılan kelimemiz yalnızca 10 belgede görünüyorsa bu durumda IDF değerimiz 1’dir. Toplam doküman sayısı ile geçen doküman sayısı arasındaki fark çok büyük olabileceğinden değeri normalize etmek için logaritması alınır.

$$idf = \log{\frac{N}{n_{k}}}$$

$N$ = Toplam Belge sayısı
$n_{k}$ = k kelimesinin geçtiği belge sayısı

Ardından bulunan TF ve IDF sonuçları kelimenin belge de ne kadar önemli olduğunu bulabilmek amacıyla çarpılır. Bu sayede yaygın kelimeler ve kullanılan ekler düşük ağırlık alırken, spesifik kelimeler daha yüksek önem alır.

$$w_{ik} = tf_{ik} \cdot idf_{k}$$

$tf_{ik}$ = k kelimesinin i belgesindeki geçiş sıklığı

Doküman vektörlerinin daha sağlıklı karşılaştırılabilmesi için terimlerin ağırlıklarının normalize edilmesi gerekir.

$$N(w_{ik}) = \frac{tf_{ik} \cdot \log{\frac{N}{n_{k}}}}{\sqrt{\sum_{k=0}^{M-1} (tf_{ik})^{2} \cdot \left[ \log\left( \frac{N}{n_{k}} \right) \right] ^{2} }}$$

$M$ = Toplam kelime sayısı

Her bir kelime için elde edilmiş TF-IDF değerleri hesaplanarak doküman vektörleri oluşturulur. Örneğin Mantis ve Yazılım kelimelerinden oluşan vektör şu şekilde olacaktır.

$$\overrightarrow{D_{1}} = \left[ w_{mantis_{d1}}, w_{yazılım_{d1}} \right]$$

İlgili dokümanları bulmak için sorgu vektörü ile doküman vektörleri arasındaki yakınlığı bulmak gerekir. Bunun için de iki vektör arasındaki açı Cosine Similarity ile hesaplanarak iki vektör arasındaki benzerlik ölçülür. İki açı arasındaki fark ne kadar küçükse o kadar ilgilidir. Böylece işlenen sorgu, inverted index üzerindeki belgelerle eşleştirilir, alaka (relevans) düzeyine göre sıralanır ve kullanıcıya döndürülür.

İki vektör A ve B için kosinüs benzerliği şu formülle hesaplanır:

$$\cos(\theta) = \frac{\sum\limits_{i=1}^{n} A_i B_i}{\sqrt{\sum\limits_{i=1}^{n} A_i^2} \cdot \sqrt{\sum\limits_{i=1}^{n} B_i^2}}$$

BM25 ise TF-IDF’in geliştirilmiş bir versiyonudur ve belgelerin sıralama skorlarını hesaplamak için kullanılır. Aradığınız kelime ile en çok eşleşen belgeleri sunar. Bunu yaparken kelime sayacı, kelimelerin yeri ve kelimelerin uzunluğuna dikkat eder. Kelime sayacı ile aradığınız kelimenin dokümanda ne kadar sık geçtiğine bakar, aranılan kelimelerin dokümanda nerede geçtiğine dikkat eder, aratılan kelimenin başlıkta mı yoksa metinde mi olduğuna bakar. Aranan kelimelerin uzunluğu ve spesifikliği istenilen sonucun daha doğru olmasını sağlar. İnternette kullandığımız birçok web sitesinin arama motorunda (Solr, Elasticsearch, Opensearch, ...) bu algoritma kullanılır. Aynı zamanda e-posta filtreleme, ürün önerisi sistemleri ve chatbot’lar gibi birçok farklı yerde karşınıza çıkabilir.

SONUÇ

Bu yazının amacı Full-text Search’ün günlük hayatta kullandığımız Google, Yandex gibi arama motorlarının nasıl size istediğiniz dokümanları sunduğunu anlatmaktır. Full-text Search, kelimelerin dokümanlarla bağlantılarını çözerek istediğiniz dokümanın ne olduğunu algılayabilmek için içerisinde TF ve IDF hesaplamaları yapması ve bunlar sayesinde sorgulanan kelime ile ilişkili dokümanlara ulaşmayı sağlamaktadır. TF-IDF aslına bakılırsa sizin girdiğiniz kelimelerin alaka seviyelerini ölçerek sizin için en iyi dokümanı ortaya çıkartmak ister. Bir arama motorunda herhangi bir şey arattığınızda en üstte çıkan sitelerin her zaman konunuzla daha alakalı olduğunu fark etmişsinizdir. İşte bunun olmasının sebebi Full-Text Search’dür. Eğer Full-Text Search’ün nasıl çalıştığını algılayabilirseniz daha etkili ve işinize yarar sorgular yapabilirsiniz.

REFERANS

https://www.turhost.com/blog/tf-idf-nedir/
https://medium.com/algorithms-data-structures/tf-idf-term-frequency-inverse-document-frequency-53feb22a17c6
https://medium.com/@kamillgun/full-text-search-e22a1251539
https://erolakgul.net/2015/09/13/full-text-search-mimarisi/
https://barisakdas.medium.com/bm25-best-match-re%C5%9Fevancy-algoritmas%C4%B1-nedir-a72f4103031c