Föreläsning 10

Mönstermatchning

[kapitel 11]
OH-bilder från denna föreläsning

Hur letar man snabbast i stora textmängder efter en delsträng?

Knuth-Morrit-Pratt's algoritm
Låt bli att titta tillbaka på tecken som redan behandlats.
Kräver förbearbetning av mönstret så att man känner till ifall mönstrets inledning återkommer senare i mönstret också.

Boyer-Moore's algoritm
Börja jämföra vid mönstrets slut och hoppas på att man hittar ovanliga tecken i texten.
Flytta fram mönstret så långt som möjligt beroende på var i mönstret det ovanliga tecknet finns.

Kan man förbearbeta själva textmassan så att sökningarna går fortare?

Trie-träd.
Lagringsstruktur för att snabbt hitta matchande prefixsträngar.

Komprimerade trie-träd.
Lagra bara index till originaltexten.

Suffix-trie
Trie-träd där man lagrat alla tänkbara delsträngar på ett kompakt sätt.
Otroligt snabbt för att söka efter delsträngar.

Huffman-kodning.
Komprimeringsteknik.
Vanliga tecken lagras med korta koder, ovanliga med längre.
Beskrivs naturligt som binära trie-träd.