Karakter Dizisi İndeksleme Yapıları
Karakter dizisi indeksleme yapıları, bir metni aranabilir bir forma (trie'lar, sonek ağaçları veya sonek dizileri gibi) ön işleme tabi tutarak, daha sonraki birçok örüntü sorgusunun ve tekrarlar ile ortak alt diziler hakkındaki soruların hızlı bir şekilde yanıtlanabilmesini sağlamaktadır.
Tanım
Karakter dizisi indeksleme yapısı, bir metinden (veya karakter dizisi kümesinden) oluşturulan ve metin hakkında verimli sorguları destekleyen bir veri yapısıdır. Bu sorgular, bir örüntünün olup olmadığı ve nerede geçtiği, en uzun tekrarlayan alt dizi veya iki metnin en uzun ortak alt dizisi gibi konuları içermekte olup, genellikle metnin öneklerini veya soneklerini temsil ederek gerçekleştirilmektedir.
Kapsam
Bu konu, hızlı tekrarlayan sorgulamalar için karakter dizilerini indeksleyen veri yapılarını kapsamaktadır: karakter dizisi kümeleri için trie'lar (önek ağaçları), doğrusal zamanda örüntü araması için bir metnin tüm soneklerini temsil eden sonek ağaçları, bunların alan açısından verimli karşılığı olan sonek dizileri ve en uzun ortak önek dizisi gibi destekleyici yapılar. Bu yapılarının oluşturma algoritmalarını ve hızlandırdıkları sorguları ele almakta olup, metni ön işlemden geçirmeyen tek seferlik örüntü eşleştirmeyi dışlamaktadır.
Temel sorular
- Bir trie, önek tabanlı arama için bir karakter dizisi kümesini nasıl düzenlemektedir?
- Bir sonek ağacı, örüntü sorgularının örüntü uzunluğuyla orantılı zaman almasını sağlayacak şekilde tüm sonekleri nasıl temsil etmektedir?
- Sonek dizileri, daha az bellek kullanarak benzer gücü nasıl elde etmektedir?
- Bu yapıları verimli bir şekilde, ideal olarak doğrusal zamanda oluşturan yapım algoritmaları nelerdir?
- Bu indeksler hangi metin problemlerini (tekrarlar, ortak alt diziler) zarif bir şekilde çözmektedir?
Anahtar kavramlar
- trie (önek ağacı)
- sonek ağacı
- sonek dizisi
- en uzun ortak önek dizisi
- çevrimiçi yapım
- en uzun tekrarlayan alt dizi
- en uzun ortak alt dizi
- alan-zaman değiş tokuşları
Temel kuramlar
- Sonek ağaçları ve doğrusal zamanda yapım
- Bir sonek ağacı, bir metnin her sonekini kompakt bir şekilde temsil ederek, bir örüntünün kendi uzunluğuyla orantılı bir zamanda aranmasına olanak tanımaktadır; Ukkonen'in algoritması, metin uzunluğuyla doğrusal zamanda çevrimiçi olarak bu yapıyı oluşturmaktadır.
- Alan açısından verimli bir indeks olarak sonek dizileri
- Bir sonek dizisi, tüm soneklerin sıralanmış düzenini düz bir tamsayı dizisinde saklamaktadır; en uzun ortak önek dizisi ile birleştirildiğinde, bir sonek ağacından çok daha az bellek kullanarak hızlı örüntü aramayı desteklemektedir.
Klinik önem
Metin indeksleri, büyük ölçekli arama ve biyoinformatik alanlarına güç katmaktadır: sonek dizileri ve ilgili sıkıştırılmış indeksler, genom okuma hizalayıcılarının ve tam metin arama motorlarının temelini oluşturmaktadır; trie'lar otomatik tamamlama ve IP yönlendirme tablolarını desteklemektedir; bu yapılar, yeniden taramanın çok maliyetli olacağı durumlarda devasa metinler üzerinde tekrarlayan sorguları pratik hale getirmektedir.
Tarihçe
Peter Weiner, sonek ağaçlarını 1973 yılında tanıtmıştır; daha basit doğrusal zamanlı yapılar McCreight (1976) ve Ukkonen (1995) tarafından geliştirilmiştir. Manber ve Myers, 1990 yılında daha alan açısından verimli bir alternatif olarak sonek dizilerini tanıtmış ve sıkıştırılmış ve FM-indeksleri üzerine yapılan sonraki çalışmalar bu fikirleri çok büyük metinlere ve genomlara genişletmiştir.
Öne çıkan isimler
- Peter Weiner
- Edward McCreight
- Esko Ukkonen
- Udi Manber
- Gene Myers
- Dan Gusfield
İlgili konular
Temel eserler
- ukkonen1995
- manber1993
- gusfield1997
Sıkça sorulan sorular
- Sonek ağacı yerine ne zaman sonek dizisi kullanmalıyım?
- Sonek dizileri, sonek ağaçlarına göre önemli ölçüde daha az bellek kullanmakta ve iyi önbellek davranışına sahip olmaları nedeniyle genomlar gibi büyük metinler için tercih edilmektedir. Sonek ağaçları daha fazla yapıyı doğrudan ortaya koymakta ve bazı algoritmaları kavramsal olarak daha basit hale getirebilmektedir, ancak daha yüksek alan maliyetiyle; sonek dizileri ve en uzun ortak önek dizisi, bu gücün çoğunu geri kazandırmaktadır.
- Bir trie ne işe yaramaktadır?
- Bir trie, ortak önekler aracılığıyla bir karakter dizisi kümesini saklayarak hızlı önek araması, otomatik tamamlama ve sıralı geçiş sağlamaktadır. Sözlükler, otomatik tamamlama önerileri ve anahtarların ortak başlangıçlara sahip olduğu IP yönlendirme gibi en uzun önek eşleştirmesi için oldukça uygundur.