Inverted Index (Ters Index) Nedir? Arama Sistemleri Metni Nasıl Aranabilir Hale Getirir?

Inverted index veya ters indeks, bir bilgi koleksiyonundaki terimleri bu terimlerin bulunduğu belgelerle eşleyen veri yapısıdır. Böylece bir arama sistemi her sorguda bütün belgeleri baştan sona okumak yerine, sorgudaki terimlerin hangi belgelerde bulunduğunu önceden hazırlanmış bir yapı üzerinden bulabilir.

En basit haliyle ilişki şöyledir:

m8      → Doküman 1, Doküman 2
civata  → Doküman 1, Doküman 2, Doküman 3
ölçü    → Doküman 1, Doküman 3

Buradaki yön önemlidir. Belgeleri açıp içindeki kelimeleri aramak yerine sistem, bir terimden o terimin bulunduğu belgelere doğru lookup yapar.

Stanford’un Introduction to Information Retrieval kitabı inverted index’i Information Retrieval’ın temel veri yapılarından biri olarak tanımlar. Yapının iki ana bileşeni vardır: terimleri tutan bir dictionary ve her terim için ilgili belge kimliklerini tutan postings list yapıları.^[1]

Bu yazıda inverted index’in neden gerekli olduğunu, dictionary ve postings list’in nasıl çalıştığını, belgelerin index’e nasıl dönüştürüldüğünü ve bu veri yapısının retrieval ile ranking içindeki sınırlarını inceleyeceğiz.

Inverted index neden gereklidir?

Information Retrieval sistemleri, büyük koleksiyonlardan kullanıcının bilgi ihtiyacına uygun olabilecek içerikleri verimli biçimde bulmak zorundadır.

Bunun en basit ama en verimsiz yöntemlerinden biri, her sorgu geldiğinde koleksiyondaki bütün belgeleri tek tek okumaktır.

Örneğin sorgumuz:

m8 civata

olsun.

Naif bir sistem şöyle çalışabilir:

Doküman 1'i oku
→ "m8" var mı?
→ "civata" var mı?

Doküman 2'yi oku
→ "m8" var mı?
→ "civata" var mı?

Doküman 3'ü oku
...

Doküman 1.000.000'u oku
...

Koleksiyon büyüdükçe bütün belgeleri her sorguda yeniden taramak pahalı hale gelir.

Inverted index bu problemi farklı şekilde ele alır. Belgeler sorgu gelmeden önce işlenir ve terimler, bu terimlerin bulunduğu belgelerle ilişkilendirilir.

Sonuçta query geldiğinde sistem doğrudan:

m8 → hangi belgelerde?

civata → hangi belgelerde?

sorusuna cevap verebilir.

Stanford’un klasik örneğinde de term-document matrisinin büyük bölümünün boş olduğu gösterilir. Her olası term-document ilişkisini saklamak yerine yalnızca gerçekten oluşan eşleşmelerin tutulması inverted index fikrinin temelidir.^[1]

Inverted index’in temel avantajı yalnız depolama değildir; sorgu zamanında ilgili belgelerin çok daha verimli biçimde bulunabilmesini sağlamasıdır.

Inverted index neden “ters” indeks olarak adlandırılır?

Normalde bir belgeyi şu yönde düşünebiliriz:

DOKÜMAN
↓
TERİMLER

Örneğin:

Doküman 1
→ m8
→ civata
→ ölçü

Doküman 2
→ paslanmaz
→ m8
→ civata

Inverted index bu ilişkiyi sorgu açısından ters yönde organize eder:

TERİM
↓
DOKÜMANLAR

Yani:

m8
→ Doküman 1
→ Doküman 2

civata
→ Doküman 1
→ Doküman 2

ölçü
→ Doküman 1

paslanmaz
→ Doküman 2

Stanford kaynaklarında da inverted index’in her terimden, terimin geçtiği belgelere doğru bir mapping oluşturduğu anlatılır.^[1]

Bu nedenle “ters” kelimesi, verinin yanlış veya tersten saklandığı anlamına gelmez. Lookup yönünün belge → terim yerine terim → belge olmasıyla ilgilidir.

Inverted index’in temel bileşenleri nelerdir?

Basit bir inverted index iki ana bölümden oluşur:

1. Dictionary
2. Postings lists

Dictionary nedir?

Dictionary, index içerisinde bulunan benzersiz terimlerin organize edildiği yapıdır.

Örneğin üç belgeden oluşan küçük bir koleksiyonumuz olsun:

D1: m8 civata ölçüleri
D2: paslanmaz m8 civata
D3: m10 civata anahtar ölçüsü

Sadeleştirilmiş dictionary şu terimleri içerebilir:

anahtar
civata
m8
m10
ölçü
paslanmaz

Stanford terminolojisinde vocabulary terimlerin kümesini, dictionary ise bu terimleri tutan veri yapısını ifade etmek için kullanılır.^[1]

Gerçek sistemlerde dictionary yalnızca kelimelerin listesinden ibaret olmak zorunda değildir. Terimlerle ilişkili document frequency gibi istatistiklere veya ilgili postings list’in konumuna erişim bilgilerine de bağlanabilir.

Postings list nedir?

Postings list, belirli bir terimin hangi belgelerde bulunduğunu gösteren listedir.

Yukarıdaki örneği index’e dönüştürelim:

m8
→ D1, D2

m10
→ D3

civata
→ D1, D2, D3

ölçü
→ D1, D3

paslanmaz
→ D2

anahtar
→ D3

Bir terim için listede yer alan her kayıt posting, bu kayıtların tamamı ise postings list olarak adlandırılır.

En basit non-positional index’te posting yalnızca bir document ID olabilir. Daha gelişmiş index yapılarında posting; term frequency, positions veya başka metadata da taşıyabilir.^[1]

Bir inverted index nasıl oluşturulur?

Inverted index sorgu geldiği anda sıfırdan oluşturulmaz. Index, retrieval sırasında hız kazanabilmek için önceden hazırlanır.

Stanford’un temel index construction modeli şu adımlarla başlar:^[1]

1. Belgeleri topla.
2. Metni token’lara ayır.
3. Gerekli linguistic preprocessing veya normalization işlemlerini uygula.
4. Term-document ilişkilerini oluştur.
5. Kayıtları term ve document ID üzerinden organize et.
6. Dictionary ve postings list’leri üret.

Basit bir örnek üzerinden ilerleyelim.

1. Belge koleksiyonu

D1: M8 civata ölçüleri
D2: Paslanmaz M8 civata
D3: M10 civata anahtar ölçüsü

2. Tokenization

Metin, sistemin kullanacağı daha küçük birimlere ayrılır.

D1 için:

M8
civata
ölçüleri

3. Normalization ve text analysis

Sistem kullanılan analyzer’a göre bazı dönüşümler uygulayabilir. Bunlar örneğin:

• büyük-küçük harf normalizasyonu,
• stemming veya lemmatization,
• stop word işlemleri,
• karakter normalizasyonu

olabilir.

Örneğin öğretim amacıyla:

M8
↓
m8

gibi bir lowercase normalizasyonu uygulanabilir.

Ancak burada önemli bir sınır vardır:

Her arama sistemi aynı tokenization veya normalization kurallarını kullanmaz.

Elasticsearch de full-text indexing sırasında text analysis pipeline’ının tokenizer ve token filter’lara bağlı olduğunu, lowercasing, stemming veya stop-word işlemlerinin kullanılan analyzer’a göre değişebildiğini açıklar.^[3]

Dolayısıyla bu örnekler genel IR mantığını göstermek içindir; Google Search’ün metni birebir bu kurallarla işlediği anlamına gelmez.

4. Term-document kayıtları

Belgeler işlendikten sonra sistem şu tür ilişkiler oluşturabilir:

m8 → D1
civata → D1
ölçü → D1

paslanmaz → D2
m8 → D2
civata → D2

m10 → D3
civata → D3
anahtar → D3
ölçü → D3

5. Aynı terimler gruplanır

anahtar → D3

civata
→ D1
→ D2
→ D3

m8
→ D1
→ D2

m10 → D3

ölçü
→ D1
→ D3

paslanmaz → D2

Ortaya çıkan yapı artık query sırasında terimden belge listesine hızlı biçimde gidilmesini sağlar.

Bir query inverted index üzerinde nasıl çalışır?

Basit bir Boolean query düşünelim:

m8 AND civata

Index’teki postings list’ler:

m8
→ D1, D2, D7, D11

civata
→ D1, D2, D5, D7, D15

İki terimin de bulunduğu belgeleri arıyorsak postings list’lerin kesişimi alınabilir:

m8      → D1, D2, D7, D11
civata  → D1, D2, D5, D7, D15
          ───────────────────
sonuç   → D1, D2, D7

Böylece sistem bütün document collection’ı yeniden okumak yerine çok daha küçük postings list’ler üzerinde işlem yapabilir.

Stanford’un Boolean retrieval modeli de AND sorgularını sıralanmış postings list’lerin birleştirilmesi ve kesişimi üzerinden açıklar.^[1]

Bu örnek özellikle Boolean retrieval’ı göstermek için sadeleştirilmiştir. Modern ranked retrieval sistemlerinde query processing yalnızca iki postings listesini kesiştirmekten ibaret değildir.

Posting yalnızca document ID mi tutar?

Hayır.

En basit inverted index şu şekilde olabilir:

m8
→ D1
→ D3
→ D7

Ancak daha zengin postings şu tür bilgiler taşıyabilir:

m8

D1
term frequency: 3
positions: 4, 18, 41

D3
term frequency: 1
position: 9

Elastic’in full-text search dokümantasyonunda da postings list’lerin document ID yanında term frequency ve term position gibi metadata taşıyabildiği açıklanır.^[3]

Bu bilgiler farklı search özelliklerini destekleyebilir.

Term frequency

Bir terimin belge içinde kaç kez geçtiğini gösterir.

Örneğin:

D1 → "m8" 3 kez
D2 → "m8" 1 kez

Bu bilgi bazı lexical scoring modellerinde kullanılabilir.

Term positions

Terimin belge içinde hangi token pozisyonlarında bulunduğunu gösterebilir.

Örneğin:

D1

m8:
[6, 21]

civata:
[7, 22]

Bu bilgi phrase veya proximity query’leri için önemlidir.

Positional index nedir?

Basit bir inverted index yalnızca bir terimin hangi belgelerde bulunduğunu biliyorsa şu iki belgeyi birbirinden ayırmak zor olabilir:

D1:
"m8 civata ölçüleri"

D2:
"m8 anahtar kullanırken civata ölçüsünü kontrol edin"

İki belgede de:

m8
civata

terimleri bulunabilir.

Ancak kullanıcı tam phrase olarak:

"m8 civata"

arıyorsa terimlerin yalnız aynı belgede bulunması yeterli değildir. Birbirlerine göre konumlarının da bilinmesi gerekir.

Positional index bu nedenle posting içinde term positions bilgisini tutabilir:

m8
D1: [4]

civata
D1: [5]

Burada iki terimin ardışık pozisyonlarda bulunduğu görülebilir.

Stanford positional index modelinde postings; document ID yanında terimin belge içindeki pozisyonlarını da saklar. Bu yapı phrase ve proximity query’lerinin verimli biçimde değerlendirilmesine yardımcı olur.^[2]

Forward yapı ile inverted index arasındaki fark nedir?

İki farklı lookup yönünü birbirinden ayırmak faydalıdır.

Yaklaşım	Lookup yönü	Basit örnek
Document-centric / forward yapı	Document → Terms veya fields	D1 → m8, civata, ölçü
Inverted index	Term → Documents	m8 → D1, D2, D7

Inverted index, bir terimi bildiğinizde o terimi içeren belgeleri bulmak için optimize edilmiştir.

Apache Lucene’in güncel dokümantasyonu da postings + term dictionary yapısını, bir term’den o term’ü içeren ordered document listesine verimli lookup sağlayan inverted index olarak açıklar. Aynı dokümantasyon, postings üzerinden ters yönde document → terms lookup yapmanın doğrudan verimli olmadığını belirtir.^[4]

Lucene bu nedenle farklı erişim ihtiyaçları için postings dışında stored fields, doc values, point values ve vector values gibi başka veri yapıları da kullanır.^[4]

Inverted index ile ranking aynı şey midir?

Hayır.

Inverted index bir veri yapısıdır.

Temel görevi:

Bir terimin hangi belgelerde bulunduğuna verimli biçimde erişmek.

Ranking ise farklı bir problemdir:

Bulunan veya değerlendirilen belgelerden hangileri sorgu için daha relevant ve hangi sırada gösterilmeli?

Bir arama sisteminde indexing, retrieval ve ranking farklı problemleri çözer. Bu katmanların daha geniş search pipeline içindeki yerini arama motorlarının nasıl çalıştığını anlattığım genel sistem haritasında inceleyebilirsiniz.

Ancak inverted index ranking sistemlerine veri sağlayabilir.

Örneğin postings veya dictionary yapısından elde edilen:

• term frequency,
• document frequency,
• term positions,
• document statistics

gibi bilgiler lexical scoring modellerinde kullanılabilir.

Elasticsearch örneğinde full-text sonuçların relevance scoring’i varsayılan olarak BM25 ile yapılır ve term frequency, document frequency ve document length gibi istatistiklerden yararlanılır.^[3]

Burada iki yanlış eşitlikten kaçınmak gerekir:

Inverted Index ≠ BM25

Inverted Index ≠ Ranking Algorithm

Inverted index retrieval ve scoring için kullanılabilecek bilgileri organize eder; scoring modelinin kendisi değildir.

Google’ın index’i ile inverted index aynı şey midir?

Bu iki kavramı birebir eşitlemek doğru değildir.

Inverted index, Information Retrieval ve özellikle lexical text retrieval sistemlerinde kullanılan temel veri yapılarından biridir.

Ancak “Google index’i” dediğimizde çok daha geniş bir arama altyapısından söz ederiz. Google Search’ün üretim index mimarisinin bütün iç detayları kamuya açık değildir.

Bu nedenle:

Google bütün web'i tek bir inverted index'e koyar.

gibi bir ifade kullanmak aşırı basitleştirme olur.

Bu yazı Google’ın özel ve kamuya açıklanmamış production mimarisini modellemiyor. Inverted index’in genel Information Retrieval ve lexical search sistemlerindeki rolünü açıklıyor.

Benzer biçimde Google’da bir URL’nin indexlenmesi ile inverted index veri yapısı aynı kavram değildir.

İlki bir arama motorunun içeriği işleyip arama sırasında kullanabileceği sistemlere dahil etmesiyle ilgili daha geniş bir süreçtir. İkincisi ise belirli retrieval problemlerini çözmek için kullanılabilen bir veri organizasyonudur.

Inverted index ile vector index arasındaki fark nedir?

Inverted index özellikle lexical retrieval dünyasının temel yapılarından biridir.

Basitleştirilmiş biçimde:

INVERTED INDEX

term
↓
documents

Dense veya semantic retrieval sistemlerinde ise içerikler ve query’ler vector representation’lara dönüştürülebilir.

Basit kavramsal model:

VECTOR INDEX

query vector
↓
yakın document vectors

Apache Lucene güncel dokümantasyonunda postings tabanlı inverted index yapılarından ayrı olarak KnnVectorValues üzerinden dense vector’ların nearest-neighbor search için indexlenebildiğini de açıklar.^[4]

Bu iki yaklaşımın farklı güçlü ve zayıf tarafları vardır.

Inverted index:

• lexical term matching için güçlüdür,
• exact terms üzerinde verimli çalışabilir,
• term statistics üzerinden scoring sistemlerini destekleyebilir.

Dense vector retrieval ise:

• öğrenilmiş representations üzerinden benzerlik arayabilir,
• birebir aynı terimlerin bulunmadığı bazı semantik ilişkileri yakalayabilir.

Modern search sistemlerinde iki yaklaşım birbirinin zorunlu alternatifi değildir. Birlikte de kullanılabilirler.

Bu ayrımı sonraki Search Systems yazılarında lexical search, dense retrieval ve hybrid search üzerinden daha ayrıntılı ele alacağız.

Inverted index SEO açısından neden önemlidir?

Bir SEO uzmanının inverted index implementasyonu yazması gerekmez. Ancak veri yapısının mantığını anlamak, arama sistemlerine dair bazı yanlış zihinsel modelleri temizler.

1. Arama sistemi belgeyi her sorguda baştan okumaz

Bir web sayfası arama sisteminde kullanılabilir hale gelirken içerik önceden işlenebilir ve aranabilir representations oluşturulabilir.

Bu nedenle kullanıcı sorgu gönderdiğinde bütün web’in o anda yeniden okunması gerekmez.

2. “Keyword sayfada geçiyor mu?” sorusu retrieval’ın tamamı değildir

Inverted index terim-document ilişkisini verimli biçimde bulmayı sağlar. Ancak bir belgenin gerçekten relevant olup olmadığı ve hangi sırada gösterileceği daha geniş bir problemdir.

Bu yüzden:

Keyword geçiyor
≠
Sayfa en relevant sonuç

ayrımı önemlidir.

3. Keyword stuffing ranking modeli değildir

Bir terimin document içinde daha fazla geçmesi bazı lexical scoring modellerinin değerlendirdiği istatistiklerden biri olabilir. Ancak relevance yalnızca tekrar sayısından oluşmaz.

Modern search sistemleri ranking için çok daha geniş sinyal ve modeller kullanabilir.

Dolayısıyla inverted index’i anlamanın sonucu:

“O zaman keyword’ü 40 kez yazmalıyım.”

değil, tam tersidir.

Indexing ve term statistics ile relevance ve ranking aynı şey değildir.

4. Indexlenmek ile bir query için iyi aday olmak farklı problemlerdir

Bir sayfanın search index içerisinde bulunması, her sorgu için relevant aday olacağı anlamına gelmez.

Bu ayrım önceki Information Retrieval yazısındaki information need, query ve relevance ilişkisiyle doğrudan bağlantılıdır.

Örneğin:

Query:
m8 civata

şu farklı kullanıcı ihtiyaçlarını temsil edebilir:

• M8 civata satın almak.
• M8 civata ölçülerini öğrenmek.
• M8 için uygun anahtar ölçüsünü bulmak.

Bir index bu terimlerle ilişkili belgeleri bulmayı kolaylaştırabilir. Fakat hangi belgenin kullanıcının gerçek ihtiyacına en uygun olduğunu belirlemek relevance ve ranking problemidir.

5. Search sistemi bilgisi site mimarisi kararının yerine geçmez

Bir arama sisteminin veriyi nasıl işlediğini anlamak yararlıdır; ancak bu bilgi hangi URL’nin hangi kullanıcı ihtiyacını karşılaması gerektiğini kendi başına belirlemez.

Search-system bilgisinin sayfa rolü, site mimarisi, içerik ownership ve uygulama önceliklerine nasıl dönüştürülebileceğini SEO stratejisini teknik altyapı, mimari ve içerikle birlikte planladığım framework’te ele alıyorum.

Inverted index hakkında bilinmesi gereken temel ayrımlar

Karıştırılan kavramlar	Temel fark
Document → Terms ≠ Term → Documents	Inverted index sorgu açısından term’den ilgili document’lara lookup sağlar.
Dictionary ≠ Postings List	Dictionary terimleri organize eder; postings list terimin bulunduğu document kayıtlarını tutar.
Posting ≠ Postings List	Posting tek bir term-document kaydıdır; postings list aynı terime ait kayıtların listesidir.
Inverted Index ≠ Ranking	Index veri yapısıdır; ranking adayların hangi sırayla sunulacağını değerlendiren problemdir.
Inverted Index ≠ BM25	BM25 bir lexical scoring yaklaşımıdır; inverted index scoring için gerekli bazı istatistikleri sağlayabilir.
Google Index ≠ Tek Bir Inverted Index	Inverted index genel lexical retrieval veri yapısıdır; Google Search’ün tüm production index mimarisini bununla eşitlemek doğru değildir.
Inverted Index ≠ Vector Index	Biri term-document lookup’a, diğeri vector representations arasındaki yakınlık aramasına dayanabilir.

Basit bir inverted index örneğini baştan sona inceleyelim

Üç belge kullanalım:

D1
M8 civata ölçüleri ve diş adımı

D2
Paslanmaz M8 civata satın al

D3
M10 civata anahtar ölçüsü

Öğretim amacıyla text analysis sonrasında şu terimlerin oluştuğunu varsayalım:

D1
m8
civata
ölçü
diş
adım

D2
paslanmaz
m8
civata
satın
al

D3
m10
civata
anahtar
ölçü

Inverted index:

adım
→ D1

al
→ D2

anahtar
→ D3

civata
→ D1, D2, D3

diş
→ D1

m8
→ D1, D2

m10
→ D3

ölçü
→ D1, D3

paslanmaz
→ D2

satın
→ D2

Şimdi query:

m8 ölçü

olsun.

Postings:

m8
→ D1, D2

ölçü
→ D1, D3

Basit bir Boolean AND yaklaşımında kesişim:

D1

olur.

Ancak bu sonuçtan şu yanlış çıkarımı yapmamalıyız:

D1 her modern search sistemi için kesin olarak birinci sırada gösterilir.

Bu örnek yalnız inverted index üzerinden lexical candidate matching mantığını gösterir.

Gerçek ranked retrieval sistemlerinde document frequency, term frequency, document length, field information, farklı query operators veya çok daha gelişmiş modeller devreye girebilir.

Inverted index’in sınırı nedir?

Inverted index güçlüdür ama her search probleminin tek cevabı değildir.

Özellikle yalnız lexical term relations üzerinden çalışıldığında:

• eş anlamlı ifadeler,
• farklı kelimelerle anlatılan benzer kavramlar,
• semantik yakınlık,
• çok geniş doğal dil ihtiyaçları

için ek yöntemlere ihtiyaç duyulabilir.

Bu, inverted index’in eski veya gereksiz olduğu anlamına gelmez.

Aksine lexical retrieval hâlâ birçok search sisteminin temel parçalarından biridir. Modern sistemler inverted index tabanlı lexical retrieval’ı vector retrieval, reranking veya başka retrieval yaklaşımlarıyla birleştirebilir.

Buradan sonra ne öğrenmek gerekir?

Inverted index’in temel mantığını anladıktan sonra sıradaki soru artık daha anlamlıdır:

Bir query ile document arasındaki relevance yalnız kelime eşleşmesine göre mi değerlendirilir?

Cevap hayır.

Klasik lexical retrieval sistemleri term statistics ve scoring modellerinden yararlanabilir. Modern dense retrieval sistemleri ise query ve document’ları öğrenilmiş vector representations üzerinden karşılaştırabilir.

Bu nedenle Search Systems öğrenme yolundaki doğal sonraki adım lexical search ile dense retrieval arasındaki farkı anlamaktır.

Arama sistemlerinin diğer bileşenlerini ve bu seride yayımlanan teknik içerikleri Search Systems bölümünde takip edebilirsiniz.

Kaynaklar ve teknik referanslar

1. Manning, Raghavan ve Schütze — Introduction to Information Retrieval: Boolean Retrieval
2. Stanford — Positional Indexes
3. Elastic Docs — How Full-Text Search Works
4. Apache Lucene 10.3 — Index Package Documentation
5. Manning, Raghavan ve Schütze — Introduction to Information Retrieval