Karakter Dizilerinde Anagram Bulma Algoritması

Anagram, iki kelimenin ya da karakter dizisinin, aynı harflerden oluşması anlamına gelir. Örneğin, “elma” ve “male” kelimeleri birer anagramdır çünkü her iki kelime de aynı harfleri içerir. Anagram bulma, özellikle metin işleme ve veri analizinde sıkça karşılaşılan bir problem olup, birçok farklı algoritma ile çözülebilir. Bu yazıda, Anagram Bulma Algoritmasını detaylı bir şekilde inceleyecek ve çeşitli yöntemlerle nasıl uygulanabileceğini göreceğiz.

Anagram Nedir?

Anagram, iki kelimenin ya da karakter dizisinin aynı harflerden oluştuğu, ancak harflerin diziliş sırasının farklı olduğu durumlardır. Örneğin:

• “listen” ve “silent” birer anagramdır.
• “evil” ve “vile” kelimeleri de anagramdır.

Anagram bulma problemi, iki kelimenin anagram olup olmadığını kontrol etme ya da büyük bir karakter dizisinde belirli bir kelimenin anagramlarını bulma gibi şekillerde karşımıza çıkabilir.

Anagram Bulma Algoritmaları

Anagram bulmak için birkaç farklı yöntem vardır. Şimdi bu yöntemleri inceleyelim.

1. Yöntem: Sıralama Yöntemi

Bu yöntem oldukça basittir ve iki kelimenin anagram olup olmadığını bulmak için kullanılır. İki kelimeyi sıralar ve ardından sıralanmış halleri karşılaştırılır. Eğer aynı harflerden oluşuyorlarsa anagramdırlar.

Python ile Sıralama Yöntemi

def anagram_mi(kelime1, kelime2):
return sorted(kelime1) == sorted(kelime2)

Bu algoritma, her iki kelimeyi sıralar ve sıralı hallerinin eşit olup olmadığını kontrol eder. Eğer iki sıralı kelime aynıysa, kelimeler anagramdır.

Zaman Karmaşıklığı: Bu yöntemin zaman karmaşıklığı sıralama işlemi nedeniyle O(n log n)‘dir. Burada n, kelimenin uzunluğudur.

2. Yöntem: Karakter Sayma (Frequency Counting) Yöntemi

Bu yöntemde, her iki kelimenin karakterlerinin frekansını (tekrar sayısını) tutarız ve bu frekansları karşılaştırırız. Eğer tüm karakterlerin frekansları aynıysa, kelimeler anagramdır.

Python ile Karakter Sayma Yöntemi

from collections import Counter

def anagram_mi(kelime1, kelime2):
return Counter(kelime1) == Counter(kelime2)

Burada Counter fonksiyonu, her iki kelimenin karakterlerinin frekansını sayar. Eğer bu frekanslar birbirine eşitse, kelimeler anagramdır.

Zaman Karmaşıklığı: Bu yöntemin zaman karmaşıklığı O(n)‘dir, çünkü her karakteri bir kez saymamız yeterlidir.

3. Yöntem: Hash Map Kullanımı

Hash tabanlı bir çözümde, iki kelimenin karakterlerini bir hash tablosunda tutarız. Her iki kelime için aynı karakterlerin aynı sayıda olup olmadığını kontrol ederiz. Bu yöntem, frekans sayma yöntemine benzer ancak daha verimli veri yapılarına dayanır.

Python ile Hash Map Yöntemi

def anagram_mi(kelime1, kelime2):
if len(kelime1) != len(kelime2):
return False

sayac = {}

for harf in kelime1:
sayac[harf] = sayac.get(harf, 0) + 1

for harf in kelime2:
if harf not in sayac or sayac[harf] == 0:
return False
sayac[harf] -= 1

return True

Bu algoritma, önce ilk kelimenin karakterlerini sayarak bir hash tablosu oluşturur, sonra ikinci kelimenin karakterlerini hash tablosundan eksilterek kontrol eder. Eğer tüm değerler sıfır olursa, kelimeler anagramdır.

Zaman Karmaşıklığı: Bu algoritma da O(n) zaman karmaşıklığına sahiptir, çünkü her karakter yalnızca bir kez işlenir.

Büyük Bir Dizide Anagram Bulma

Bazen sadece iki kelimenin anagram olup olmadığını kontrol etmek yeterli olmayabilir. Büyük bir karakter dizisinde belirli bir kelimenin anagramlarını bulmak isteyebiliriz. Bu durumda, kayan pencere (sliding window) ve hashing gibi algoritmalar kullanarak hızlıca anagramlar bulunabilir.

Python İle Kayan Pencere Yöntemi

def anagram_bul(dizi, kelime):
kelime_uzunlugu = len(kelime)
kelime_sayaci = Counter(kelime)
sonuc = []

for i in range(len(dizi) – kelime_uzunlugu + 1):
pencere = dizi[i:i + kelime_uzunlugu]
if Counter(pencere) == kelime_sayaci:
sonuc.append(i)

return sonuc

Bu kod, büyük bir dizide belirli bir kelimenin anagramlarını bularak anagramların başlangıç indekslerini döndürür. Örneğin, “abc” kelimesinin anagramlarını bulmak için büyük bir dizide her kayan pencerede anagram kontrolü yaparız.

Zaman Karmaşıklığı: Bu yöntem, kayan pencere ve karakter sayma işlemleri nedeniyle O(n) zaman karmaşıklığına sahiptir.

Örnekler Üzerinde Anagram Algoritmaları

Örnek 1: “listen” ve “silent” Anagram mı?

kelime1 = “listen”
kelime2 = “silent”
print(anagram_mi(kelime1, kelime2)) # True

Sonuç: Bu iki kelime anagramdır çünkü aynı harflerden oluşurlar.

Örnek 2: “apple” ve “papel” Anagram mı?

kelime1 = “apple”
kelime2 = “papel”
print(anagram_mi(kelime1, kelime2)) # True

Sonuç: Bu iki kelime de anagramdır çünkü aynı harfleri içerirler.

Örnek 3: Büyük Dizide Anagram Bulma

dizi = “cbaebabacd”
kelime = “abc”
print(anagram_bul(dizi, kelime)) # [0, 6]

Sonuç: “abc” kelimesinin anagramları 0. ve 6. pozisyonlarda bulunmuştur.

Zaman Karmaşıklığı Karşılaştırması

Yöntem	Zaman Karmaşıklığı
Sıralama Yöntemi	O(n log n)
Karakter Sayma Yöntemi	O(n)
Hash Map Yöntemi	O(n)
Kayan Pencere Yöntemi	O(n)

• Sıralama Yöntemi, küçük dizilerde uygulanabilir olsa da, sıralama işlemi nedeniyle büyük dizilerde yavaş çalışabilir.
• Karakter Sayma ve Hash Map Yöntemleri, hem zaman hem de bellek açısından daha verimlidir.
• Kayan Pencere Yöntemi, büyük dizilerde belirli bir kelimenin anagramlarını bulmak için kullanışlıdır.

Anagram Bulmanın Kullanım Alanları

1. Metin Analizi ve Veri Madenciliği: Anagram bulma algoritmaları, büyük metinlerde dil işleme ve veri madenciliği için kullanılır.
2. Kriptografi: Anagramlar, bazı şifreleme yöntemlerinde mesajları karıştırmak ve gizlemek için kullanılabilir.
3. Oyun Geliştirme: Kelime oyunlarında ve bulmacalarda anagramlar, oyuncuların karşısına çıkabilecek problemler arasında yer alır.

Sonuç

Anagram bulma problemi, metin işleme dünyasında sıkça karşılaşılan ve çeşitli algoritmalarla çözülebilen bir problemdir. Sıralama, karakter sayma ve hash tabanlı yöntemler, anagram bulmak için yaygın olarak kullanılan tekniklerdir. Hangi yöntemin kullanılacağı, problemin boyutuna ve veri setinin büyüklüğüne bağlıdır.