Stringler, Algoritma Tasarımı ve Analizi

Hüseyin · 2 Kas 2024

Stringler, metni temsil etmek için kullanılan karakter dizileridir. Programlamadaki en temel veri türlerinden biridir ve metin verilerini depolamak ve işlemek gibi çeşitli amaçlar için kullanılırlar.

Anahtar Kavramlar:

String Representation: Dizeler ASCII ve Unicode gibi farklı karakter kodlamaları kullanılarak temsil edilebilir.
Immutability: Birçok programlama dilinde dizgiler değişmezdir, yani bir kez oluşturulduktan sonra içerikleri değiştirilemez.
String Indexing: Dizeler genellikle 0'dan başlayarak indekslenir ve tek tek karakterlere erişime izin verir.

String İşlemleri ve Özellikleri

Temel İşlemler:

Creation: Dizeler değişmez gösterim veya kurucular kullanılarak oluşturulabilir.
Concatenation: Operatörler veya yöntemler kullanılarak iki veya daha fazla dizginin birleştirilmesi.
Repetition: Bir dizeyi belirli sayıda tekrarlama.

Özellikler:

Indexing and Slicing: Tek tek karakterlere ve alt dizelere erişme.
Immutability: Bazı dillerde dizeler oluşturulduktan sonra değiştirilemez.
Character Encoding: Çok dilli metin desteği için UTF-8 gibi kodlama şemalarını anlama.

Dize İşleme Paradigmaları Arasındaki Farklar

Dizeler vs. Karakter Dizileri:

Dizeler: Manipülasyon ve sorgulama için yerleşik yöntemlerle daha üst düzey soyutlama.
Karakter Dizileri: Tek tek karakterlerin doğrudan manipüle edilebildiği alt düzey veri yapısı.

Örnek:

Dizeler: Java String, Python str
Karakter Dizileri: C char[]

Strings vs. StringBuilder/StringBuffer:

Dizeler: Değişmez, her değişiklik için yeni string nesneleri ile sonuçlanır.
StringBuilder/StringBuffer: Değişebilir, yeni nesneler oluşturmadan dizelerin değiştirilmesine izin verir.

Örnek:

StringBuilder/StringBuffer: Java StringBuilder, C++ std::stringstream

Dize Eşleştirme Algoritmaları için Örnekler

Dize eşleştirme algoritmaları, daha büyük bir dize (metin) içindeki bir alt dizenin (desen) oluşumlarını bulmak için kullanılır. Aşağıda üç popüler dize eşleştirme algoritmasının uygulamaları bulunmaktadır: Kaba Kuvvet, Knuth-Morris-Pratt (KMP), Boyer-Moore ve Rabin-Karp.
Kaba Kuvvet Dize Eşleştirme

Brute Force algoritması, deseni metin üzerinde her seferinde bir karakter kaydırarak ve karakterleri karşılaştırarak metinde desenin varlığını kontrol eder.

İşte bir Python uygulaması:

Python:

def brute_force_string_match(text, pattern):
    n = len(text)
    m = len(pattern)

    # Iterate through each possible starting position in text
    for i in range(n - m + 1):
        # Check for pattern match starting at position i
        for j in range(m):
            if text[i + j] != pattern[j]:
                break
        else:
            # If inner loop completes without breaking, a match is found
            print(f"Pattern found at index {i}")

# Example usage
text = "ababcababcabcabc"
pattern = "abc"
brute_force_string_match(text, pattern)

Knuth-Morris-Pratt (KMP) Algoritması

KMP algoritması, daha önce eşleştirilmiş karakterlerin üzerinden atlamak için kısmi bir eşleşme tablosu (En Uzun Önek Soneki veya LPS dizisi olarak da bilinir) kullanarak gereksiz karşılaştırmalardan kaçınarak verimliliği artırır.

İşte bir Python uygulaması:

Python:

def get_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def find_all_matches_kmp(text, pattern):
    n, m = len(text), len(pattern)
    if m > n:
        return []
    if m == n:
        return [0] if pattern == text else []

    lps = get_lps(pattern)
    i, j = 0, 0
    matches = []
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1

        if j == m:
            matches.append(i - j)
            j = lps[j - 1]
        elif i < n and text[i] != pattern[j]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

    return matches

# Example usage
text = "abxabcabcabydhjbjabcabyjfd"
pattern = "abcaby"
result = find_all_matches_kmp(text, pattern)
print(result)

Boyer-Moore Algoritması

Boyer-Moore algoritması, iki sezgisel yöntem kullanarak örüntüyü içermediği garanti edilen metin bölümlerini atlayarak arama verimliliğini artırır: Kötü Karakter Kuralı ve İyi Sonek Kuralı.

İşte bir Python uygulaması:

Python:

def preprocess_bad_character(pattern):
    bad_char = {}
    m = len(pattern)
    for i in range(m):
        bad_char[pattern[i]] = i
    return bad_char

def preprocess_good_suffix(pattern):
    m = len(pattern)
    good_suffix = [0] * m
    f = [-1] * m
    k = m - 1
    for j in range(m - 2, -1, -1):
        if pattern[j + 1] != pattern[k]:
            k = j + 1
        f[j] = k
    for i in range(m - 1):
        good_suffix[m - f[i] - 1] = i + 1
    return good_suffix

def boyer_moore_search(text, pattern):
    n, m = len(text), len(pattern)
    if m > n:
        return []

    bad_char = preprocess_bad_character(pattern)
    good_suffix = preprocess_good_suffix(pattern)
    matches = []
    i = 0

    while i <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1
        if j < 0:
            matches.append(i)
            i += good_suffix[0] if i + m < n else 1
        else:
            i += max(good_suffix[j + 1] if j + 1 < len(good_suffix) else 1,
                     j - bad_char.get(text[i + j], -1))

    return matches

# Example usage
text = "abxabcabcabydhjbjabcabyjfd"
pattern = "abcaby"
result = boyer_moore_search(text, pattern)
print(result)

Rabin-Karp Algoritması

Rabin-Karp algoritması metindeki deseni bulmak için hashing kullanır. Desen ve metnin aynı uzunluktaki tüm alt dizeleri için hash değerleri hesaplar ve bunları karşılaştırır.

İşte bir Python uygulaması:

Python:

def rabin_karp(text, pattern, d=256, q=101):
    n, m = len(text), len(pattern)
    if m > n:
        return []

    # Precompute hash values
    p = 0  # Hash value for pattern
    t = 0  # Hash value for text
    h = 1  # The value of d^(m-1) % q
    matches = []

    # Compute the hash value of pattern and first window of text
    for i in range(m):
        p = (d * p + ord(pattern[i])) % q
        t = (d * t + ord(text[i])) % q
        if i < m - 1:
            h = (h * d) % q

    # Check for matches
    for i in range(n - m + 1):
        if p == t:
            if text[i:i + m] == pattern:
                matches.append(i)

        if i < n - m:
            t = (d * (t - ord(text[i]) * h) + ord(text[i + m])) % q
            t = (t + q) % q  # Ensure t is non-negative

    return matches

# Example usage
text = "abcabcabcdabcdabc"
pattern = "abcd"
result = rabin_karp(text, pattern)
print(result)

Stringler, Algoritma Tasarımı ve Analizi

Daha fazla seçenek

Hüseyin

Üye