Suffikstræ

Træ

En komprimeret trie der indeholder alle suffikser af en streng, brugt til effektiv strengmatching og mønstersøgning.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(m) for mønsterlængde m`
Search	`O(m) for mønstermatching`
Insertion	`O(n) for konstruktion`
Deletion	`N/A (statisk efter konstruktion)`

Beskrivelse

Suffikstræet er en af de mest kraftfulde datastrukturer til strengbehandling og mønstermatching. Den gemmer alle suffikser af en given streng i en komprimeret trie-struktur. For en streng af længde n vil der være n suffikser, men ved at bruge stikomprimering kan hele strukturen bygges i O(n) tid og plads med Ukkonens algoritme. Hver sti fra roden til et blad repræsenterer et suffiks. Suffikstræer kan løse mange strengproblemer i lineær eller næsten lineær tid: mønstermatching i O(m) for mønster af længde m, finde længste gentagne delstreng i O(n), længste fælles delstreng mellem to strenge i O(n+m), og mange flere. Strukturen er grundlaget for mange bioinformatikalgoritmer hvor DNA-sekvensmatching er kritisk. Selvom suffikstræer er utroligt kraftfulde, bruges suffiksarrays ofte i praksis fordi de bruger mindre hukommelse. Suffikstræer finder også anvendelse i teksteditorer, DNA-sekventering, datakomprimering og plagiatchecking.

Kode Eksempel

// JavaScript Suffix Tree Implementation (forenklet)
class SuffixTreeNode {
  constructor() {
    this.children = {};
    this.start = -1;
    this.end = null;
    this.suffixLink = null;
    this.suffixIndex = -1;
  }
}

class SuffixTree {
  constructor(text) {
    this.text = text + '$'; // Tilføj terminator
    this.root = new SuffixTreeNode();
    this.root.suffixLink = this.root;
    this.buildNaive();
  }

  // Naiv O(n²) konstruktion for simplicitet
  buildNaive() {
    const n = this.text.length;
    
    for (let i = 0; i < n; i++) {
      this.insertSuffix(i);
    }
  }

  insertSuffix(suffixStart) {
    let node = this.root;
    
    for (let i = suffixStart; i < this.text.length; i++) {
      const char = this.text[i];
      
      if (!node.children[char]) {
        const newNode = new SuffixTreeNode();
        newNode.start = i;
        newNode.end = this.text.length - 1;
        newNode.suffixIndex = suffixStart;
        node.children[char] = newNode;
        return;
      }
      
      node = node.children[char];
    }
  }

  // Søg efter mønster
  search(pattern) {
    let node = this.root;
    let i = 0;
    
    while (i < pattern.length) {
      const char = pattern[i];
      
      if (!node.children[char]) {
        return false;
      }
      
      node = node.children[char];
      const edgeLabel = this.getEdgeLabel(node);
      
      for (let j = 0; j < edgeLabel.length && i < pattern.length; j++, i++) {
        if (edgeLabel[j] !== pattern[i]) {
          return false;
        }
      }
    }
    
    return true;
  }

  getEdgeLabel(node) {
    if (node.start === -1) return '';
    return this.text.substring(node.start, (node.end || 0) + 1);
  }
}

// Brug
const text = "banana";
const tree = new SuffixTree(text);

console.log('Søg "ana":', tree.search('ana')); // true
console.log('Søg "app":', tree.search('app')); // false

Anvendelsesområder

•Mønstermatching i store tekster
•DNA/RNA-sekvensanalyse i bioinformatik
•Plagiatchecking
•Datakomprimeringsalgoritmer
•Teksteditorer med avanceret søgning

Fordele

✓O(m) mønstermatching for mønster af længde m
✓Kan finde alle forekomster samtidig
✓Løser mange strengproblemer i lineær tid
✓Kraftfuld til bioinformatik
✓Understøtter avancerede forespørgsler (længste gentagelse osv.)

Ulemper

✗Meget hukommelseskrævende O(n) men med høj konstant
✗Kompleks at implementere korrekt
✗Ukkonens algoritme er svær at forstå
✗Bygning tager tid selvom O(n)
✗Erstattes ofte med suffiksarrays i praksis

Eksempler fra den virkelige verden

•DNA-sekvensmatching (BLAST-algoritmer)
•Plagiatchecking-software (Turnitin)
•Strengsøgning i teksteditorer
•Datadeduplikering i lagringssystemer
•Genomsamling i bioinformatik

Relaterede strukturer

TrieSuffix ArrayAho-Corasick AutomatonKMP Algorithm