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

Prefiks ağacı (Trie), mətnlə bağlı əməliyyatlar üçün optimallaşdırılmış verilənlər strukturudur. Bu struktur, böyük mətn kolleksiyalarında sürətli axtarış, söz əlavə etmə və şablon uyğunlaşdırma kimi əməliyyatları asanlaşdırır.

Prefiks ağacları, mətn redaktorlarında avtomatik tamamlama funksiyalarından tutmuş bioinformatikada DNT ardıcıllıqlarının analizinə qədər geniş bir sahədə tətbiq olunur.

Sadə Prefiks Ağacı Nümunəsi

Prefiks ağacı, düyünlərdən ibarət olan bir qrafik strukturdur. Hər bir düyün bir simvolu təmsil edir və uşaqları (qonşuları) isə sonrakı simvolları göstərir. Məsələn, “salam” sözü üçün prefiks ağacı belə qurulur:

s → a → l → a → m

Bu strukturun əsas üstünlüyü, ümumi prefiksləri olan sözləri eyni yolla paylaşaraq yaddaşdan qənaət etməsidir. Məsələn, “maşın”, “maşınçı” və “maşınqayırma” sözləri üçün prefiks ağacı:

m → a → ş → ı → n*
                |
                q → a → y → ı → r → m → a*
                |
                ç → ı*

Burada * ilə işarələnmiş düyünlər sözün sonunu göstərir.

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

Prefiks ağacında axtarış prosesi kök düyündən başlayır. Axtarış sözünün hər bir simvolu üçün ağacda uyğun düyün axtarılır. Əgər cari simvol üçün düyün mövcud deyilsə, söz ağacda yoxdur. Əgər bütün simvollar uyğun gəlirsə və son düyün * ilə işarələnibsə, söz ağacda mövcuddur. Bu metodun vaxt mürəkkəbliyi O(L)-dir, burada L axtarış sözünün uzunluğudur. Bu, prefiks ağacını xüsusilə böyük mətn kolleksiyaları üçün ideal bir seçim edir.

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 Yazılması

İndi ən maraqlı hissəyə gəldik! Prefiks ağacını istənilən proqramlaşdırma dilində yazmaq mümkündür, amma biz burada TypeScript-dən istifadə edəcəyik. Kodumuz çox sadə olacaq: yalnız iki sinifdən ibarət olacaq. Birinci sinif ağacın düyünlərini təmsil edəcək, ikinci sinif isə prefiks ağacının özünü idarə edəcək. Kodu yazdıqdan sonra sözləri əlavə edib axtarışı işə salacağıq və nəticələrə baxacağıq. Əvvəlcə kodu diqqətlə oxuyun və məntiqini anlamağa çalışın. Əgər hər hansı bir çətinlik olsa, aşağıda daha ətraflı izahı var.

// Düyün sinifi
class Düyün {
  constructor(
    public qonşular = {},
    public son = false 
  ) { }
}

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

  constructor() {
    this.kök = new Düyün();
  }

  qoy(söz: string) { 
    let cari = this.kök; 
    for (const hərf of söz) {
      if (!cari.qonşular[hərf]) {
        cari.qonşular[hərf] = new Düyün();
      }
      cari = cari.qonşular[hərf];
    }
    cari.son = true;
  }

  axtar(söz: string) { 
    let cari = this.kök;
    for (const hərf of söz) {
      const düyün = cari.qonşular[hərf];
      if (!düyün) {
        return false;
      }
      cari = düyün;
    }
    return cari.son;
  }
}

// İstifadə nümunəsi
const ağac = new PrefiksAğacı();
ağac.qoy("maşın");
ağac.qoy("maşınqayırma");
ağac.qoy("maşa");

console.log(ağac.axtar("maşın"));// true
console.log(ağac.axtar("maşa")); // true
console.log(ağac.axtar("maşınqa"));// false
console.log(ağac.axtar("maaş"));// false

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

Prefiks ağacının yaradılması, ağacın kök 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 düyünlər bu kök düyünün qonşuları (uşaq düyünlər) sayılır.

// ...
constructor() {
  this.kök = new Düyün();
}
// ...

Düyün sinifi, ağacın düyününü təmsil edir və iki əsas xüsusiyyəti ehtiva edir:

1. qonşular: Hər bir simvol üçün uşaq düyünləri saxlayan obyekt.
2. son: Sözün sonu olub-olmamasını göstərən bayraq (boolean).

// ...
class Düyün {
  constructor(
    public qonşular = {},
    public son = false 
  ) { }
}
// ...

PrefiksAğacı sinifi isə prefiks ağacını təmsil edir və kök adlı özəl xüsusiyyəti ehtiva edir. Bu xüsusiyyət, ağacın başlanğıc düyününü saxlayır.

class PrefiksAğacı {
  private kök: Düyün; 
  constructor(){ /* ... */ }
  qoy(söz: string){ /* ... */ }
  axtar(söz: string){ /* ... */ }
}

Sözlərin Əlavə Edilməsi

Sözlərin ağaca əlavə edilməsi prosesi “qoy” metodu ilə həyata keçirilir. Bu metod, sözün hər bir simvolu üçün ağacı gəzir: cari düyün (kök düyündən başlayaraq) üzərində işləyir və əgər cari düyünün qonşular obyektində sözün cari simvolu yoxdursa, yeni bir düyün yaradılaraq qonşular obyektinə əlavə edilir. Sözün sonuna çatdıqda, son düyünün son xüsusiyyəti true olaraq işarələnir.

// ...
qoy(söz: string) { 
  let cari = this.kök; 
  for (const hərf of söz) {
    if (!cari.qonşular[hərf]) {
      cari.qonşular[hərf] = new Düyün();
    }
    cari = cari.qonşular[hərf];
  }
  cari.son = true;
}
// ...

Sözlərin Axtarılması

Burada, “axtar” metodu sözün hər bir simvolu üçün ağacı gəzir: əgər cari düyünün qonşular obyektində sözün cari simvolu yoxdursa, söz ağacda mövcud deyil və metod false qaytarır. Əgər bütün simvollar uğurla keçilib və son düyünün son xüsusiyyəti true olarsa, söz ağacda mövcuddur və metod true qaytarır.

// ...
axtar(söz: string) { 
  let cari = this.kök;
  for (const hərf of söz) {
    const düyün = cari.qonşular[hərf];
    if (!düyün) {
      return false;
    }
    cari = düyün;
  }
  return cari.son;
}
// ...

Kodla burada oynaya bilərsiniz.

Vaxt Kompleksliyi

Prefiks ağacının əsas əməliyyatları olan “qoy” və “axtar” üçün vaxt kompleksliyi O(L)-dir, burada L axtarılan və ya əlavə edilən sözün uzunluğudur. Hər iki əməliyyat zamanı sözün hər bir simvolu üzrə ağacda bir dəfə gəzinti edilir. Əgər sözün simvolları üçün uyğun düyünlər mövcuddursa, əməliyyat sürətli şəkildə yerinə yetirilir. Bu, prefiks ağacını xüsusilə uzun sözlər üçün ideal edir.

Sürət Testinin Nəticələri (Bençmarklar)

Prefiks ağaclarının performansını qiymətləndirmək üçün benchmark nəticələrinə baxaq. Bu müqayisədə, sadə iterativ axtarış metodu ilə prefiks ağacı metodunu yoxlayacağıq.

Testlər 1 milyon ingilis sözündən ibarət verilənlər çoxluğu üzərində aparılmış və 1000 təsadüfi söz üçün axtarış vaxtları ölçülmüşdür.

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.