Hoofdstuk 6: Strings in Algoritmen

Strings zijn een fundamenteel gegevenstype in de informatica, die reeksen tekens vertegenwoordigen. De studie van algoritmen en gegevensstructuren voor het verwerken van strings is een cruciaal onderdeel van elk informatica-curriculum. In dit hoofdstuk verkennen we verschillende belangrijke string-verwerkingsalgoritmen, waaronder string-sorteringen, tries, substring-zoeken, reguliere expressies en gegevenscompressie. Deze algoritmen hebben talrijke praktische toepassingen, van tekstbewerking en documentopvraging tot bioinformatica en natuurlijke taalverwerking.

String-sorteringen

Sorteren is een fundamentele bewerking in de informatica, en het sorteren van strings is een veel voorkomende taak in veel toepassingen. Hoewel algemene sorteeralgoritmen zoals quicksort en mergesort kunnen worden gebruikt om strings te sorteren, zijn er efficiëntere algoritmen die gebruik maken van de speciale eigenschappen van strings.

Key-Indexed Counting

Key-indexed counting is een eenvoudig en efficiënt algoritme voor het sorteren van strings die zijn samengesteld uit een kleine set van onderscheiden tekens. Het basisidee is om het aantal voorkomen van elk teken te tellen en deze tellingen vervolgens te gebruiken om de positie van elke string in de gesorteerde volgorde te bepalen.

Hier is een voorbeeld van key-indexed counting in actie:

Invoer:  ["dab", "cab", "fad", "bad", "dad", "ebb", "ace"]
Uitvoer: ["ace", "bad", "cab", "dab", "dad", "ebb", "fad"]

Het algoritme werkt als volgt:

Tel de frequentie van elk teken in de strings.
Bereken de startindex voor elk teken in de gesorteerde array.
Kopieer de strings naar de gesorteerde array, waarbij de tellingen worden gebruikt om de posities te bepalen.

Key-indexed counting heeft een tijdscomplexiteit van O(n + R), waarbij n het totale aantal tekens in de strings is en R de grootte van het alfabet (het aantal onderscheiden tekens). Dit maakt het een zeer efficiënt algoritme voor het sorteren van strings met een klein alfabet.

LSD Radix Sort

Least-significant-digit-first (LSD) radix sort is een uitbreiding van key-Hier is de Nederlandse vertaling van het Markdown-bestand:

Tellen dat strings van gelijke lengte over een groot alfabet kan sorteren. Het basisidee is om de strings karakter voor karakter te sorteren, te beginnen bij het laatste karakter en naar het eerste te gaan.

Hier is een voorbeeld van LSD radix sort:

Invoer:  ["4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720", "1OHV845", "1OHV845", "2RLA629", "2RLA629", "3ATW723"]
Uitvoer: ["1ICK750", "1ICK750", "1OHV845", "1OHV845", "1OHV845", "2IYE230", "2RLA629", "2RLA629", "3ATW723", "3CIO720", "3CIO720", "4JZY524", "4PGC938"]

Het algoritme werkt als volgt:

Sorteer de strings op het laatste karakter met behulp van key-indexed counting.
Herhaal stap 1 voor elk karakter in de richting van het eerste.

LSD radix sort heeft een tijdscomplexiteit van O(w * n), waarbij w de lengte van de strings is en n het aantal strings. Dit maakt het een efficiënte keuze voor het sorteren van strings met een vaste lengte.

MSD Radix Sort

Most-significant-digit-first (MSD) radix sort is een recursieve variant van radix sort die strings van verschillende lengtes kan verwerken. Net als quicksort verdeelt MSD radix sort de array in subarrays die onafhankelijk kunnen worden gesorteerd.

Hier is een voorbeeld van MSD radix sort:

Invoer:  ["she", "sells", "seashells", "by", "the", "sea", "shore", "the", "shells", "she", "sells", "are", "surely", "seashells"]
Uitvoer: ["are", "by", "sea", "seashells", "seashells", "sells", "sells", "she", "she", "shells", "shore", "surely", "the", "the"]

Het algoritme werkt als volgt:

Verdeel de array in subarrays op basis van het eerste karakter van elke string.
Sorteer elk subarray recursief.

MSD radix sort heeft een worst-case tijdscomplexiteit van O(n * w), maar in de praktijk is het vaak sneller dan LSD radix sort voor strings met verschillende lengtes.

Tries

Een trie (uitgesproken als "try") is een boomachtige datastructuur voor het opslaan van strings die efficiënte prefix-matching en string-zoeken mogelijk maakt. Elke knoop in een trie vertegenwoordigt een karakter, en het pad van de wortel naar een knoop vertegenwoordigt een prefix van deHier is de Nederlandse vertaling van het Markdown-bestand:

Strings opgeslagen in de trie.

Hier is een voorbeeld van een trie die de strings "zee", "verkoopt", "zij", "schelpen" en "kust" opslaat:

     (root)
    /  |  \
   z   h   k
  / \     / \
 e   h   u   o
 |   |   |   |
 a   e   s   t
     |       |
     l       h
     |       |
     t       e
     |
     s

Tries ondersteunen de volgende bewerkingen:

Voeg een string toe aan de trie.
Zoek naar een string in de trie.
Verwijder een string uit de trie.
Vind alle strings met een gegeven voorvoegsel.

De tijdcomplexiteit van deze bewerkingen is O(w), waarbij w de lengte is van de string die wordt ingevoegd, gezocht of verwijderd. Dit maakt tries een zeer efficiënte gegevensstructuur voor string-gerelateerde taken.

Substring-zoeken

Substring-zoeken is het probleem van het vinden van alle voorkomens van een patroonstring binnen een grotere tekststring. Dit is een fundamenteel probleem in string-verwerking, met toepassingen in tekstbewerking, bioinformatica en vele andere domeinen.

Brute-force-zoeken

De eenvoudigste aanpak voor substring-zoeken is het brute-force-algoritme, dat elke mogelijke positie in de tekst controleert op een overeenkomst met het patroon.

Hier is een voorbeeld van brute-force-zoeken:

Tekst:    "abacadabrabracabracadabrabrabracad"
Patroon: "abracadabra"
Uitvoer:  [13]

Het brute-force-algoritme heeft een worst-case-uitvoertijd van O(n * m), waarbij n de lengte is van de tekst en m de lengte van het patroon. Hoewel eenvoudig te implementeren, kan dit inefficiënt zijn voor grote teksten en patronen.

Knuth-Morris-Pratt-algoritme

Het Knuth-Morris-Pratt (KMP)-algoritme is een efficiënt substring-zoekalgoritme dat een vooraf berekende "faalfunctie" gebruikt om onnodige vergelijkingen te vermijden.

De faalfunctie vertelt ons de lengte van het langste juiste voorvoegsel van het patroon dat ook een achtervoegsel is van het deelstring van het patroon dat we tot nu toe hebben vergeleken. Dit stelt ons in staat om "vooruit te springen" in de tekst wanneer we een mismatch vinden, in plaats van terug te gaan.

Hier is een voorbeeld van het KMP-algoritme:

Tekst:    "abacadabrabr
```Hier is de Nederlandse vertaling van het Markdown-bestand, waarbij de code-opmerkingen zijn vertaald:

acabracadabrabrabracad"
Patroon: "abracadabra"
Uitvoer: [13]

Het KMP-algoritme heeft een uitvoertijd van O(n + m), waardoor het veel efficiënter is dan de brute-force-benadering voor grote teksten en patronen.

Boyer-Moore-algoritme

Het Boyer-Moore-algoritme is een ander efficiënt substring-zoekalgoritme dat werkt door het patroonstring voor te verwerken. In tegenstelling tot KMP, dat de vergelijkingen vanaf het begin van het patroon start, start Boyer-Moore vanaf het einde en werkt achteruit.

Het sleutelidee achter Boyer-Moore is het gebruik van twee vooraf berekende functies: de "goede suffix"-functie en de "slechte teken"-functie. Deze functies stellen ons in staat om vooruit te springen in de tekst wanneer we een mismatch vinden, vergelijkbaar met KMP.

Hier is een voorbeeld van het Boyer-Moore-algoritme:

Tekst:   "abacadabrabracabracadabrabrabracad"
Patroon: "abracadabra"
Uitvoer: [13]

Boyer-Moore heeft een best-case uitvoertijd van O(n/m) en een worst-case uitvoertijd van O(n * m), maar in de praktijk is het vaak het snelste substring-zoekalgoritme voor grote alfabetten.

Reguliere expressies

Reguliere expressies zijn een krachtig hulpmiddel voor het beschrijven van patronen in strings. Ze bieden een beknopte en flexibele notatie voor het matchen, zoeken en bewerken van tekst.

Een reguliere expressie is een reeks tekens die een zoekpatroon definiëren. De eenvoudigste vorm van een reguliere expressie is een letterlijke tekenreeks, zoals "hello", die exact de tekenreeks "hello" overeenkomt. Reguliere expressies bevatten echter ook speciale tekens en constructies die complexere patronen mogelijk maken:

. (punt) komt overeen met elk afzonderlijk teken.
* (asterisk) komt overeen met nul of meer voorkomens van het voorafgaande teken of groep.
+ (plus) komt overeen met één of meer voorkomens van het voorafgaande teken of groep.
? (vraagteken) komt overeen met nul of één voorkomen van het voorafgaande teken of groep.
^ (dakje) komt overeen met het begin van een regel.
$ (dollarteken) komt overeen met het einde van een regel.
[] (vierkante haken) definiëren een tekenklasse, die overeenkomt met elk afzonderlijk tekenHier is de Nederlandse vertaling van het Markdown-bestand, waarbij de code-opmerkingen zijn vertaald:

Hier zijn enkele voorbeelden van reguliere expressies en de patronen die ze matchen:

a.b komt overeen met elke tekenreeks van drie tekens die begint met "a" en eindigt met "b", zoals "acb", "a5b" of "a b".
a*b komt overeen met elke tekenreeks die bestaat uit nul of meer "a"-tekens gevolgd door een enkele "b", zoals "b", "ab", "aab" of "aaab".
a+b komt overeen met elke tekenreeks die bestaat uit een of meer "a"-tekens gevolgd door een enkele "b", zoals "ab", "aab" of "aaab", maar niet "b".
a?b komt overeen met ofwel "ab" of "b".
^a komt overeen met elke tekenreeks die begint met "a".
a$ komt overeen met elke tekenreeks die eindigt met "a".
[aeiou] komt overeen met een willekeurig enkel klinkerkarakter.

Reguliere expressies worden ondersteund door veel programmeertalen en hulpprogramma's, waaronder Java, Python en Unix-hulpprogramma's zoals grep en sed. Ze worden veel gebruikt voor taken zoals gegevensvalidatie, tekstverwerking en loganalyse.

Gegevenscompressie

Gegevenscompressie is het proces van het coderen van informatie met behulp van minder bits dan de oorspronkelijke weergave. Dit is nuttig voor het verminderen van opslagvereisten en verzendingstijden. Er zijn twee hoofdtypen compressie: verliesvrij en met verlies. Verliesvrije compressie maakt het mogelijk om de oorspronkelijke gegevens perfect te reconstrueren uit de gecomprimeerde gegevens, terwijl compressie met verlies toestaat dat er enig informatieverlies is in ruil voor hogere compressieverhoudingen.

Run-Length Encoding

Run-Length Encoding (RLE) is een eenvoudige verliesvrije compressietechniek die herhaalde reeksen identieke symbolen (runs) vervangt door een enkel exemplaar van het symbool en een telling van het aantal keren dat het wordt herhaald.

Hier is een voorbeeld van RLE:

Invoer:  "AAAABBBCCCDDDEEE"
Uitvoer: "4A3B3C3D3E"

RLE is effectief voor gegevens met veel lange runs, zoals eenvoudige grafische afbeeldingen. Het kan echter de grootte van de gegevens daadwerkelijk vergroten als er weinig of geen runs zijn.

Huffman-codering

Huffman-codering is een verliesvrij compressie-algoritme dat variabele-lengte codes toewijst aan symbolen op basis van hun freHier is de Nederlandse vertaling van het Markdown-bestand, waarbij de code-opmerkingen zijn vertaald:

Frequenties in de invoergegevens. Frequentere symbolen krijgen kortere codes toegewezen, terwijl minder frequente symbolen langere codes krijgen.

Het algoritme werkt door een binaire boom, genaamd een Huffman-boom, van onderaf naar boven op te bouwen. Elk bladknooppunt vertegenwoordigt een symbool en zijn frequentie, terwijl elk interne knooppunt de som van de frequenties van zijn kinderen vertegenwoordigt. De boom wordt geconstrueerd door herhaaldelijk de twee knooppunten met de laagste frequenties samen te voegen totdat er slechts één knooppunt overblijft.

Zodra de boom is gebouwd, wordt de code voor elk symbool bepaald door het pad van de wortel naar het corresponderende bladknooppunt, waarbij een linkertak een "0" en een rechtertak een "1" vertegenwoordigt.

Hier is een voorbeeld van Huffman-codering:

Invoer:  "AAAABBBCCCDDDEEE"
Uitvoer: "000010011001011100101"

Huffman-boom:
      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

In dit voorbeeld krijgt "A" de code "00", "B" krijgt "01", "C" krijgt "10", "D" krijgt "110" en "E" krijgt "111". De gecomprimeerde uitvoer wordt verkregen door elk symbool in de invoer te vervangen door de bijbehorende code.

Huffman-codering is een optimale voorvoegselcode, wat betekent dat geen enkele code een voorvoegsel is van een andere code. Dit maakt ondubbelzinnige decodering van de gecomprimeerde gegevens mogelijk. Huffman-codering wordt veel gebruikt in verschillende bestandsformaten en compressie-hulpprogramma's, zoals JPEG, MP3 en ZIP.

LZW-compressie

Lempel-Ziv-Welch (LZW)-compressie is een op woordenboek gebaseerd compressie-algoritme dat een woordenboek (of codeboek) van tekenreeksen opbouwt tijdens het comprimeren van de invoer. LZW wordt veel gebruikt in bestandscompressie-hulpprogramma's en werd gebruikt in het GIF-beeldformaat.

Het sleutelprincipe achter LZW is het vervangen van tekenreeksen door enkele codes. Het leest de invoertekenreeks teken voor teken en codeert de tekenreeks in een compacte representatie door elke vaste lengte code te vervangen door een variabele lengte code. Hoe langer de tekenreeks, hoe meer ruimte er wordt bespaard door deze als één getal te coderen.

Hier is eenHier is de Nederlandse vertaling van het bestand:

Stap-voor-stap beschrijving van hoe LZW-compressie werkt:

Initialiseer het woordenboek om alle enkelteken-strings te bevatten.
Vind de langste string W in het woordenboek die overeenkomt met de huidige invoer.
Geef de woordenboekindex voor W af aan de uitvoer en verwijder W uit de invoer.
Voeg W gevolgd door het volgende symbool in de invoer toe aan het woordenboek.
Ga naar Stap 2.

Laten we een voorbeeld bekijken. Stel dat we de string "ABABABABA" willen comprimeren met LZW.

Initialiseer het woordenboek om "A" en "B" te bevatten.
De langste overeenkomst is "A". Geef de index (0) ervan af en verwijder het uit de invoer. Het woordenboek bevat nu "A", "B" en "AB".
De langste overeenkomst is "B". Geef de index (1) ervan af en verwijder het uit de invoer. Het woordenboek bevat nu "A", "B", "AB" en "BA".
De langste overeenkomst is "AB". Geef de index (2) ervan af en verwijder het uit de invoer. Het woordenboek bevat nu "A", "B", "AB", "BA" en "ABA".
De langste overeenkomst is "ABA". Geef de index (4) ervan af en verwijder het uit de invoer. Het woordenboek bevat nu "A", "B", "AB", "BA", "ABA" en "ABAB".
De langste overeenkomst is "BA". Geef de index (3) ervan af. De invoer is nu leeg.

De gecomprimeerde weergave van "ABABABABA" is dus de reeks indexen [1], wat minder bits vereist dan de oorspronkelijke ASCII-weergave.

Decompressie werkt op een vergelijkbare manier, maar in omgekeerde volgorde:

Initialiseer het woordenboek om alle enkelteken-strings te bevatten.
Lees een code X uit de invoer.
Geef de string voor X uit het woordenboek af.
Als de vorige code bestaat, voeg dan de vorige string samengevoegd met het eerste teken van de string voor X toe aan het woordenboek.
Ga naar Stap 2.

LZW-compressie is eenvoudig en snel, waardoor het een goede keuze is voor veel toepassingen. Het heeft echter ook enkele beperkingen. De grootte van het woordenboek kan aanzienlijk toenemen en veel geheugen verbruiken. Bovendien wordt het woordenboek na elke invoerblok gereset, wat de compressieratio voor kleine bestanden kan verminderen.

Ondanks deze beperkingen...Hier is de Nederlandse vertaling van het Markdown-bestand, waarbij de code-opmerkingen zijn vertaald:

ns, LZW blijft een populair en effectief compressie-algoritme, vooral voor toepassingen waarbij snelheid belangrijker is dan het bereiken van de hoogst mogelijke compressieverhoudingen.

Conclusie

In dit hoofdstuk hebben we verschillende belangrijke string-verwerkingsalgoritmen onderzocht, waaronder string-sorteringen, tries, substring-zoeken, reguliere expressies en gegevenscompressie. Deze algoritmen vormen de basis voor veel real-world toepassingen en zijn essentiële tools voor elke programmeur die met tekstuele gegevens werkt.

We zijn begonnen met het bespreken van string-sorteringen, die geoptimaliseerde sorteeralgoritmen zijn die gebruik maken van de speciale eigenschappen van strings. Key-indexed counting, LSD radix sort en MSD radix sort bieden efficiënte methoden voor het sorteren van strings op basis van hun individuele tekens.

Vervolgens hebben we tries onderzocht, een boomachtige gegevensstructuur voor het opslaan en ophalen van strings. Tries maken snel voorvoegsel-matching mogelijk en worden veel gebruikt in toepassingen zoals automatisch aanvullen en IP-routingtabellen.

Substring-zoekalgoritmen, zoals de Knuth-Morris-Pratt- en Boyer-Moore-algoritmen, stellen ons in staat om efficiënt naar patronen binnen grotere strings te zoeken. Deze algoritmen hebben talrijke toepassingen in tekstbewerking, computationele biologie en informatiewinning.

Reguliere expressies bieden een krachtige en flexibele manier om string-patronen te beschrijven. We hebben de basissyntaxis van reguliere expressies besproken en hoe ze kunnen worden gebruikt voor patroonherkenning en string-manipulatie in verschillende programmeertalen en tools.

Ten slotte hebben we gegevenscompressie-algoritmen onderzocht, die de grootte van gegevens verkleinen door redundantie en patronen binnen de invoer te benutten. We hebben run-length encoding, Huffman-codering en Lempel-Ziv-Welch-compressie behandeld, waarvan elk zijn eigen sterke en zwakke punten heeft.

Het begrijpen van deze string-verwerkingsalgoritmen en gegevensstructuren is cruciaal voor iedereen die met tekstuele gegevens werkt. Naarmate de hoeveelheid ongestructureerde gegevens blijft groeien, is het vermogen om tekstuele gegevens efficiënt te manipuleren, doorzoeken en comprimeren van essentieel belang.Here is the Dutch translation of the provided text, with the code comments translated:

Strings worden alleen maar waardevoller

Strings zullen alleen maar waardevoller worden. Door de technieken die in dit hoofdstuk worden behandeld, te beheersen, zult u goed uitgerust zijn om een breed scala aan string-verwerkingsuitdagingen in uw eigen projecten en toepassingen aan te pakken.

# Converteer een string naar uppercase
text = "hello, world!"
upper_text = text.upper()
print(upper_text)  # Output: HELLO, WORLD!
 
# Converteer een string naar lowercase
text = "PYTHON IS AWESOME"
lower_text = text.lower()
print(lower_text)  # Output: python is awesome
 
# Verwijder witruimte aan het begin en einde van een string
text = "   Hallo   "
stripped_text = text.strip()
print(stripped_text)  # Output: Hallo
 
# Vervang een substring in een string
text = "I like cats. Cats are great."
replaced_text = text.replace("cats", "dogs")
print(replaced_text)  # Output: I like dogs. Dogs are great.
 
# Splits een string op basis van een scheidingsteken
text = "apple,banana,cherry"
fruits = text.split(",")
print(fruits)  # Output: ['apple', 'banana', 'cherry']

Chapter 5 Graphs Chapter 7 Context