My proposal (Ters Metin İndeksinin Düz Metin İndeksi Kullanılarak Oluşturulması ve Uygulamaları )received the intramural support from Istanbul Technical University and granted with the project number BAP-MGA-2019-42224 with a budget of approximately 50K TL starting at 15 October 2019 and ending date is 15 August 2020.

 

Proje Özeti:

Bir metnin üzerinde hızlı arama gerçekleştirebilmek için, o metnin indeksinin oluşturulması gereklidir. Bu amaçla genel olarak kullanılan tam-metin (full-text) tarama indeksleri sonek ağaçlari (suffix tree), sonek katarları (suffix array) ve Burrows—Wheeler dönüşümü (BWT) şeklinde belirmektedir.

Bazı durumlarda ilgili metnin tersi üzerinde de hızlı arama gereksinimi ortaya çıkabilmektedir. Örneğin hataya karşı toleranslı bazı eşleştirme algoritmaları metin üzerinde hem sağdan sola hem de soldan sağa tarama gerçekleştirmektedir. Bir diğer uygulama biyoenformatik alanında olup, DNA’nın ters ipliğinden (reverse strand) gelen okumaların da olabileceği gerçeği ile referans genom üzerine hizalama işleminde yine hedef dizinin tersten taranmasına da ihtiyaç duyulmaktadır. Bu gibi durumlar için ters metnin indekslenmesi, hem indeks için kullanılan hafızayı iki katına çıkarmakta, hem de ters indeksin hesaplanma yükünü eklemektedir.

Bu projede amaçlanan, ayrı bir ters metin indeksi kullanmadan ters taramanın düz metin üzerindeki indeksten yapılabilmesinin araştırılmasıdır. Bu amaçla düz metin indeksinin ters metin hakkında ortaya koyduğu bilgi detaylı olarak incelenecektir.  Ana hedef sadece tek yönlü indeks kullanılarak çift yönlü aramanın sağlanmasıdır. Bu hedefe ulaşılmasının temel kazanımı mevcut sistemlerde ilgili uygulamaların kullandığı hafıza yükünü yarıya indirmektir.