Dizi Algoritmaları
Dizi algoritmaları, sembol dizilerini — metin, DNA veya diğer doğrusal verileri — örüntüleri bulmak, büyük metinleri hızlı arama için indekslemek ve dizileri benzerliğe göre hizalamak amacıyla işlemektedir.
Tanım
Dizi algoritmaları, örüntüleri bulma, hızlı arama için indeksleme ve diziler arasındaki benzerliği ölçme veya hizalama gibi sorunları çözmek amacıyla diziler — bir alfabeden alınan sonlu karakter dizileri — üzerinde çalışan prosedürler ve veri yapılarıdır.
Kapsam
Bu alan, diziler için özelleşmiş algoritmaları ve veri yapılarını kapsamaktadır: kesin ve yaklaşık örüntü eşleştirme, tekrarlanan sorgular için metni ön işleyen indeks yapıları (trie'lar, sonek ağaçları ve dizileri) ve dizileri karşılaştırmak için dizi hizalama yöntemleri. Dinamik programlama (hizalama), veri yapıları (ağaçlar ve diziler) ile hesaplamalı biyoloji, metin erişimi ve doğal dil işleme alanlarındaki uygulamalarla bağlantılıdır.
Alt konular
Temel sorular
- Bir örüntü, metinde saf karakter-karakter karşılaştırmadan daha hızlı nasıl bulunabilir?
- Büyük bir metin, sonraki birçok sorgunun hızlı olması için nasıl ön işlenir?
- İki dizi arasındaki benzerlik nasıl tanımlanır ve hesaplanır?
- Alfabe boyutu ve dizi uzunluğu, dizi algoritmalarının verimliliğini nasıl etkiler?
- Kesin eşleştirme yöntemleri, yaklaşık veya çoklu örüntü eşleştirmeye nasıl genişletilir?
Anahtar kavramlar
- alfabe ve dizi
- kesin örüntü eşleştirme
- Knuth-Morris-Pratt ve Boyer-Moore
- trie'lar
- sonek ağaçları ve sonek dizileri
- düzenleme mesafesi
- dizi hizalama
- yaklaşık eşleştirme
Temel kuramlar
- Doğrusal zamanda kesin örüntü eşleştirme
- Örüntüyü kısmi eşleşmelerden elde edilen bilgiyi kullanmak üzere ön işleyerek, Knuth-Morris-Pratt ve Boyer-Moore gibi algoritmalar, bir örüntünün tüm oluşumlarını metin uzunluğuna göre doğrusal zamanda bulmakta ve saf eşleştirmenin karesel maliyetinden kaçınmaktadır.
- Metin için indeks yapıları
- Sonek ağaçları ve sonek dizileri bir metni ön işleyerek, rastgele örüntü sorguları, tekrarlar ve en uzun ortak alt dizi sorularının hızlı bir şekilde yanıtlanabilmesini sağlamakta, böylece yapım maliyetini hızlı tekrarlanan arama ile dengelemektedir.
Klinik önem
Dizi algoritmaları, metin arama ve biyoinformatik için temel niteliktedir: örüntü eşleştirme, arama yardımcı programlarına, metin düzenleyicilerine ve izinsiz giriş tespitine güç vermektedir; sonek yapıları arama motorlarını ve genom veri tabanlarını indekslemektedir; ve dizi hizalama, moleküler biyolojide DNA, RNA ve protein dizilerini karşılaştırmak için merkezi bir role sahiptir.
Tarihçe
Verimli dizi eşleştirme, 1970'lerde Knuth-Morris-Pratt (1977) ve Boyer-Moore (1977) algoritmalarıyla ortaya çıkmıştır. Sonek ağaçları (Weiner, 1973; McCreight, 1976; Ukkonen, 1995) ve daha sonra sonek dizileri (Manber ve Myers, 1990) güçlü indeksleme sağlamış, alan Gusfield'ın 1997 tarihli metninde incelenen hesaplamalı biyoloji aracılığıyla hızla genişlemiştir.
Öne çıkan isimler
- Donald Knuth
- James H. Morris
- Vaughan Pratt
- Robert Boyer
- J Strother Moore
- Dan Gusfield
İlgili konular
Temel eserler
- knuth1977
- gusfield1997
- cormen2009
Sıkça sorulan sorular
- Neden doğrudan aramak yerine örüntüyü veya metni ön işlemek gerekir?
- Saf eşleştirme, örüntü ve metin uzunluklarının çarpımıyla orantılı zaman alabilmektedir. Örüntüyü ön işlemek (Knuth-Morris-Pratt'ta olduğu gibi) doğrusal zamanda arama sağlamakta; metni bir indekse (sonek ağacı veya dizisi) ön işlemek ise sonraki birçok sorgunun her birinin çok daha hızlı çalışmasını mümkün kılmaktadır ki bu da aynı metin tekrar tekrar arandığında karşılığını vermektedir.
- Dizi algoritmaları biyolojide nasıl kullanılmaktadır?
- DNA, RNA ve proteinler doğal olarak diziler olarak temsil edilmektedir; bu nedenle örüntü eşleştirme motifleri bulmakta, sonek yapıları hızlı arama için genomları indekslemekte ve dizi hizalama algoritmaları, evrimsel ilişkileri ve işlevi çıkarmak için diziler arasındaki benzerliği nicelendirmektedir.