Suffix Array - String Algoritmaları

Suffix dizisi, verilmiş olarak verilen stringe ait tüm suffixlerin alfabetik olarak sıralanmış halidir. Suffix array eğer elinizde bir suffix tree varsa, bu ağaç üzerinde DFS algoritmasını işletilmesi ile elde edilebilir.

Suffix array veri yapısının, suffix tree'den avantajları, geliştirilmiş bellek performansı ve keşleme özelliğidir.

Önreğin;

"banana" için.

0 banana                          5 a …
more ...

En basit hali ile text arama işlemi - String Algoritmaları

Text işlemlerinde, bir dizgi içerisinde dizgi aramadaki en basit çözümü inceleyeceğiz.

txt[] =  "THIS IS A TEST TEXT"
pat[] = "TEST"
Output: 10
txt[] =  "AABAACAADAABAAABAA"
pat[] = "AABA"
Output: 0,9,13

Çözüm aşağıdaki gibi olacaktır.

def search(text, pattern):
    m, n = len(pattern), len(text)
    for i in range(n - m + 1 …
more ...

KMP Algoritmasi - String Algoritmaları

Bir diğer string arama algoritmalarından olan KMP algoritmasına bakacağız.

Örnek olarak;

txt =  "THIS IS A TEST TEXT"
pat = "TEST"
Output : 10

ve

txt =  "AABAACAADAABAAABAA"
pat = "AABA"
Output : 0, 9, 13

Bir önceki yazıda en kaba hali ile bir text içerisinde nasıl başka bir text aramasının yapılacağını incelemiştik. O algoritma O …

more ...

Suffix Tree - String Algoritmaları

Biyoinformatik'de adı sıkça geçen algoritmalardan olan suffix tree veri yapısı bir dizgi model(pattern) eşleştirme algoritmasıdır.Örneğin elinizde uzun bir dizgi olsun ve siz bu dizgi içinde alt dizgiler aramak ve hatta bu dizgilerden kaç adet bulunduğunu öğrenmek istiyorsunuz.İşte bu veri yapısı bu işlemleri kolaylaştırmak ile birlikte gayet hızlı …

more ...