Karp&Rabin Algorithmus

[Neutral General]

Hi,

Also bin ma bisschen im Internet rumgesurft und hab das hier gefunden.
Der Algorithmus ist doch um aus einem Bild Buchstaben herauszufiltern oder versteh ich das falsch?
Wenn ich das richtig versteh dann würde ich das noch besser verstehn :D
Gibt es irgendeine Seite oder irgendjemand der mir das besser und detailierter erklären kann? :)

Der Link: http://www.grundstudium.info/algorit...00000000000000

Gruß
Neutral General

[Der_Unwissende]

Hi,
ehrlich gesagt liegt Theoretische Informatik schon etwas zurück und es kann sein dass ich mich irre, aber es müsste sich eigentlich eher um einen Algorithmus handeln, der sehr effizient die Position eines Teilstrings liefert. Kann sogar etwas allgemeiner sein (Muster aus Ganzem), aber wichtig wahr vor allem die asymptotische Laufzeit. Ist glaube ich auch kein ganz trivialer Algorithmus gewesen.
Jedenfalls findest du mit Sicherheit eine der besten Erklärungen im Cormen (irgendwas mit Algorithmen im Namen)

Gruß Der Unwissende

[DGL-luke]

Also wikipedia weiß dazu mir als unbedarftem Suchamschinenebenutzer auch einiges zu sagen... http://de.wikipedia.org/wiki/Karp-Rabin-Algorithmus

[marabu]

Zitat:

Zitat von Der_Unwissende

ehrlich gesagt liegt Theoretische Informatik schon etwas zurück

Was soll ich denn da erst sagen...

Zitat:

Zitat von Der_Unwissende

es müsste sich eigentlich eher um einen Algorithmus handeln, der sehr effizient die Position eines Teilstrings liefert.

Volltreffer.

Zitat:

Zitat von Der_Unwissende

Ist glaube ich auch kein ganz trivialer Algorithmus gewesen.

Eher doch, würde ich sagen.

[equote="Sedgewick schreibt in 'Algorithms' zum Thema 'String Searching'"]... In 1980 R. M. Karp and M. O. Rabin ... came up with an algorithm almost as simple as the brute-force algorithm ... Furthermore, their algorithm extends easily to two-dimensional patterns and text, which makes it more useful than the others for picture processing.[/equote]
Hier noch ein Link für eine C-Implementierung (1-dimensional): klick

Grüße vom marabu

[Der_Unwissende]

Zitat:

Zitat von marabu

Zitat:

Zitat von Der_Unwissende

Ist glaube ich auch kein ganz trivialer Algorithmus gewesen.

Eher doch, würde ich sagen.

Hm, dann habe ich den wohl verwechselt, änder ich einfach mal in Knuth-Morris-Pratt war nicht ganz trivial (sollte ich doch jetzt lieber nachschauen, was? Also ohne Gewähr, sind aber die einzigen beiden String Matching Algorithmen die mir gerade einfallen. Kann natürlich auch nur sein, dass die Laufzeitberechnung nicht so wirklich trivial war, hm, man wird doch alt)

Gruß Der Unwissende