Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
   
  •  
    Biologie
    Themen der Chemie
    Deutsch online artikel
    Englisch / Englische
    Franzosisch
    Geographie
    Geschichte
    Informatik
    Kunst
    Mathematik / Studium
    Musik
    Philosophie
    Physik
    Recht
    Sport
    Wirtschaft & Technik



    Biographie

    Impressum

informatik artikel (Interpretation und charakterisierung)

Textsuche


1. Java
2. Viren



Brute Force Dieser Suchalgorithmus durchsucht einen Text nach einem Muster. Dabei vergleicht er die aktuelle Stelle des Musters mit der aktuellen Stelle im Text. Tritt ein ,Mismatch' auf wird das Muster um eine Stelle verschoben und neu verglichen, sonst wird die aktuelle Stelle des Musters und des Textes um eine Stelle erhöht und weiter verglichen. Selbst wenn das Muster nahezu komplett durchsucht wurde und erst zum Schluß ein ,Mismatch' auftaucht wird das Muster nur um eine Stelle verschoben.

Algorithmus:
int search (char *p, char *a) // p ... Suchmuster

{ // a ... durchsuchter Text
int i, j, m = strlen (p), n = strlen (a);
for (i = 0, j = 0; j < m && i < n; i++, j++)
while (a[i] != p[j]) {

i-= j - 1;
j = 0;

}
if (j == m) return i-m;

else return i;

}
Durch dieses Verfahren kommt es zu vielen doppelten Vergleichen.
Suchaufwand: maximal: n * m

n ... Länge des Musters
m ... Länge des Textes
Knuth-Morris-Pratt (KMP)
Der Algorithmus von KMP stellt eine wesentliche Verbesserung gegenüber dem Brute-Force-Algorithmus dar. Diese Verbesserung wird durch eine Vorverarbeitung des Musters erreicht. In dieser Vorverarbeitung wird ermittelt, ab welcher Stelle des Textes frühestens ein nächster Vergleich des gesamten Musters beginnen kann. Es wird ein Array verwendet, um zu bestimmen, an welcher Stelle im Muster zurückzukehren ist, wenn eine Nichtübereinstimmung festgestellt wurde.
Es sind niemals mehr als n + m Zeichenvergleiche notwendig.
Boyer-Moore
Im Gegensatz zu den vorherigen Algorithmen wird das Muster nicht von links nach rechts mit dem Text verglichen, sondern umgekehrt. Der Vergleich beginnt also immer an der letzten Stelle im Muster. Tritt eine Nichtübereinstimmung auf, wird die Distanz berechnet, um die das Muster verschoben wird, bevor ein erneuter Vergleich ausgeführt wird.
Die Berechnungen für die Verschiebung des Musters sind nur von dem Zeichen im Text abhängig, das die Nichtübereinstimmung verursacht hat. Darüber hinaus spielt es eine Rolle, ob und an welcher Position das Zeichen im Muster auftaucht. Dies führt dazu, daß man für jedes Zeichen des Alphabets einen Eintrag in einem Array reserviert, der die Größe der möglichen Verschiebungen nach rechts angibt, wenn das Zeichen eine Nichtübereinstimmung verursacht. Das Array wird mit delta bezeichnet und enthält für jedes Element, das nicht im Muster verkommt m und ansonsten den Abstand des rechtesten Vorkommens des Zeichens bis zum Musterende.
Der Algorithmus von Boyer-Moore kann im ungünstigsten Fall n * m Schritte benötigen. Im Idealfall hingegen nur n / m Schritte.

Algorithmus:
// Berechnung von delta for (c = ´A´; c

 
 




Datenschutz

Top Themen / Analyse
ALOHA - Protokolle
IMPULSDIAGRAMME + SPEZIFIKATIONEN
Diascanner
Erwerbungswege erforderlicher Kompetenzen für das Informationszeitalter.
Was ist eigentlich ein Programm?
Grobe Einführung in die PHP Syntax
Die "r"-Befehle
Soundkarten
Herstellerspezifische und offene Netze
MINIMOT-Kleinbohrmaschinen-Komplettset





Datenschutz

Zum selben thema
Netzwerk
Software
Entwicklung
Windows
Programm
Unix
Games
Sicherheit
Disk
Technologie
Bildung
Mp3
Cd
Suche
Grafik
Zahlung
Html
Internet
Hardware
Cpu
Firewall
Speicher
Mail
Banking
Video
Hacker
Design
Sprache
Dvd
Drucker
Elektronisches
Geschichte
Fehler
Website
Linux
Computer
A-Z informatik artikel:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #

Copyright © 2008 - : ARTIKEL32 | Alle rechte vorbehalten.
Vervielfältigung im Ganzen oder teilweise das Material auf dieser Website gegen das Urheberrecht und wird bestraft, nach dem Gesetz.