Prefiks Ağacları ilə Sürətli Mətn Axtarışı

Prefiks ağacı effektiv mətn əməliyyatları üçün nəzərdə tutulmuş verilənlər strukturudur. Böyük mətn kolleksiyalarında sürətli axtarış, əlavə və pattern uyğunlaşdırma əməliyyatlarını bizə imkan verir.

Prefiks ağacları, mətn redaktorlarında avtomatik tamamlama funksiyalarından bioinformatikada mürəkkəb DNT ardıcıllığı analizinə qədər gündəlik istifadə etdiyimiz bir çox texnologiyaların arxasında gizlənmiş qəhrəmanlardır.

Prefiks Ağaclarının İşləmə Prinsipi

Prefiks ağacı, düyünlərdən ibarətdir. Hər bir düyün bir simvolu təmsil edir. Məsələn, “salam” sözündən belə bir prefiks ağacı yarada bilərik:

s-a-l-a-m

Prefiks ağaclarının əsas üstünlüklərindən biri ümumi prefiksləri olan sətir coxluqlarında yaddaşa qənayət etmək qabiliyyətidir. Məsələn, əgər “maşın”, “maşınçı” və “maşınqayırma” sətirlər varsa, onlar “maşın” üçün ortaq bir yolu paylaşacaq və sonra ayrılacaqlar.

m-a-ş-ı-n*-q-a-y-ı-r-m-a*
        |
        c - ı*

Hər hansı sətri axtardığımız zaman kökdən başlayırıq və axtarış sətirindəki simvollar üzərindən bir-bir iterasiya edirik. Əgər cari simvol ağacda mövcuddursa, növbəti simvola keçirik. Əgər bütün simvollar tapılırsa, o zaman həmin sətir prefiks ağacının çoxluğuna daxil olunmuş sayılır. Fikir versək, biz ancaq axtarış simvolu nə qədərdirsə, o qədər iterasiya edirik, bu çox effektiv bir axtarış sayılır. Ona görə də vaxt mürəkkəbliyi O(m)-dir, burada m - axtarış sətrinin uzunluğudur. Biz bu haqqda daha ətraflı danışacağıq.

Axtarış sözü "maşın":

Ağac:
m-a-ş-ı-n*-q-a-y-ı-r-m-a*
        |
        c - ı*

Addımlar:
1. "m" - var, növbəti "a"
2. "a" - var, növbəti "ş"
3. "ş" - var, növbəti "ı"
4. "ı" - var, növbəti "n"
5. "n" - var, növbəti "q" ya "c"
6. Söz coxluqda mövcuddur: çünki "n" düyünündə bayraq var. 
Davam etməyə ehtiyac yoxdur.

Axtarış sözü "maşa":

Ağac:
m-a-ş-ı-n*-q-a-y-ı-r-m-a*
        |
        c - ı*

Addımlar:
1. "m" - var, növbəti "a"
2. "a" - var, növbəti "ş"
3. "ş" - var, növbəti "ı"
4. Söz coxluqda mövcud deyil: çünki növbəti "a" deyil.

Axtarış sözü "maşınqayırma":

Ağac:
m-a-ş-ı-n*-q-a-y-ı-r-m-a*
        |
        c - ı*

Addmılar:
1. "m" - var, növbəti "a"
2. "a" - var, növbəti "ş"
3. "ş" - var, növbəti "ı"
4. "ı" - var, növbəti "n"
5. "n" - var, növbəti "q" ya "c"
6. "q" - var, növbəti "a"
7. "a" - var, növbəti "y"
8. "y" - var, növbəti "ı"
9. "ı" - var, növbəti "r"
10. "r" - var, növbəti "m"
11. "m" - var, növbəti "a"
12. "a" - var
13. Söz coxluqda mövcuddur: "a" düyünündə bayraq var.

Kodun Yazilmasi

Gəlib çatdıq ən maraqlı məqamına! Gəlin indi kod yazaq. Burada istənilən proqramlaşdırma dilində yazıla bilər, gəlin TypeScript-də yazaq. Kodumuz çox sadə olacaq, iki sinifdən ibarət olacaq, sonra sözləri əlavə edib axtarışı işə salacağıq və nəticələrə baxacağıq. Birinci kodu oxuyun və çalışın məntiqi başa düşəsiniz, əgər çətinlik olsa, aşağıda daha ətraflı izah var.

// Düyün sinifi
class Düyün {
  constructor(
    public növbətiDüyünlər = {},
    public sözünSonudurmı = false
  ) {}
}

// Prefiks ağacı sinifi  
class PrefiksAğacı {
  private başDüyün: Düyün;

  constructor() {
    this.başDüyün = new Düyün();
  }

  public sözüƏlavəEt(söz: string): void {
    let carıDüyün = this.başDüyün;
    for (const simvol of söz) {
      if (!carıDüyün.növbətiDüyünlər[simvol]) {
        carıDüyün.növbətiDüyünlər[simvol] = new Düyün();
      }
      carıDüyün = carıDüyün.növbətiDüyünlər[simvol];
    }
    carıDüyün.sözünSonudurmı = true;
  }

  public sözüAxtar(söz: string): boolean {
    let carıDüyün = this.başDüyün;
    for (const simvol of söz) {
      if (!carıDüyün.növbətiDüyünlər[simvol]) {
        return false;
      }
      carıDüyün = carıDüyün.növbətiDüyünlər[simvol];
    }
    return carıDüyün.sözünSonudurmı;
  }
}

// PrefiksTree sinifindən bir obyekt yaradırıq
const ağac = new PrefiksAğacı();

// Sözləri ağaca əlavə edirik
ağac.sözüƏlavəEt("maşın")
ağac.sözüƏlavəEt("maşınqayırma")
ağac.sözüƏlavəEt("maşa")

// Sözləri axtarırıq
console.log(ağac.sözüAxtar("maşın")); // doğru
console.log(ağac.sözüAxtar("maşa")); // doğru
console.log(ağac.sözüAxtar("maşınqayırma")); // doğru
console.log(ağac.sözüAxtar("maaş")); // yalan
console.log(ağac.sözüAxtar("maşınka")); // yalan

Prefiks Ağacının Yaradılması

Prefiks ağacının yaradılması, ağacın baş düyününü təyin etməklə başlayır. Bu düyün, ağacın başlanğıc nöqtəsidir və digər növbəti düyünlər bu kök düyünün üsaqları sayılır. Düyün sinifi, ağacın düyününü təmsil edir və növbətiDüyünlər (uşaq düyünlər) və sözünSonudurmı (sözün sonu olub-olmaması bayrağı) xüsusiyyətlərini ehtiva edir. PrefiksAğacı sinifi isə prefiks ağacını təmsil edir və başDüyün (kök düyün) adlı özəl xüsusiyyəti ehtiva edir.

Sözlərin Əlavə Edilməsi

Sözlərin ağaca əlavə edilməsi prosesi, sözüƏlavəEt metodu ilə həyata keçirilir. Bu metod, sözün hər simvolu üçün ağacı gəzir. Əgər simvol üçün növbəti düyün mövcud deyilsə, yeni bir düyün yaradılır. Sözün sonuna çatdıqda, son düyünün sözünSonudurmı xüsusiyyəti true olaraq işarələnir.

Sözlərin Axtarılması

Sözlərin ağacda axtarılması prosesi, sözüAxtar metodu ilə həyata keçirilir. Bu metod, sözün hər simvolu üçün ağacı gəzir. Əgər simvol üçün uşaq düyün tapılmazsa, söz ağacda mövcud deyil və metod false qaytarır. Əgər bütün simvolları keçərək və sözünSonudurmı işarələnmiş bir düyünə çatırsa söz ağacda mövcuddur və metod true qaytarır.

Kodla burada oynaya bilərsiniz.

Vaxt Kompleksliyi

Prefiks ağacları üzərində əməliyyatların vaxt kompleksliyi onun ən cəlbedici xüsusiyyətlərindən biridir. Ağac qurulduqdan sonra, uzunluğu m olan bir sətrin axtarışı ən pis halda O(m) vaxt alır. Yeni sətir əlavə etmə vaxtı da effektivdir. Uzunluğu m olan yeni sətir əlavə etmək yalnız O(m) vaxt tələb edəcək. Ümumi uzunluğu n olan bir verilənlər dəstəsi üçün ağacın quruluşu O(n) vaxt tələb edə bilər, ən pis halda O(n^2).

Sürət Testinin Nəticələri (Benchmarklar)

Prefiks ağaclarının effektivliyini göstərmək üçün benchmark nəticələrinə baxaq. Burada biz sadə iterativ metodla prefiks ağacı metodunu müqayisə edirik.

Bu benchmarklar 1 milyon ingilis sözündən ibarət bir verilənlər coxluğu üzərində aparılmışdır, 1000 təsadüfi söz üçün axtarışlar edilmişdir.

Prefiks ağacının yaddaş istifadəsi nisbətən yüksək olsa da, müasir sistemlərdə istifadə oluna bilər, xüsusilə də təmin etdiyi performans üstünlükləri nəzərə alındıqda.