Ergebnis 1 bis 4 von 4

Thema: Effiziente Substring-Suche [Algorithmus]

  1. #1
    Quantenmechaniker
    Registriert seit
    Aug 2002
    Beiträge
    1.935
    Renommee
    283

    Effiziente Substring-Suche [Algorithmus]

    Hello zusammen,

    ich muss später erst noch meinen neuen Algorithmus untersuchen bzw. benchmarken, aber evtl. habt ihr ja schon 'ne Idee, ob das besser funktionieren kann als andere Verfahren?

    Es geht darum, dass ich so etwas wie große Quellcodes o.ä. habe, wo ich einzelne Wörter/Substrings heraus suchen muss, um diese wie Variablen zu ersetzen. Ganz allgemeine
    Frage wäre, ob es da schon etwas gibt, das diese Aufgabe gut löst? Sonst hätte ich mir kurz einen eigenen Algorithmus überlegt - weiß nur nicht, wie der jetzt genau skaliert! (^_^)´

    Jedenfalls ist einer der gewünschten Zwecke, dass ich diverse <Stream> (ob nun Prozess-I/O oder Datei-Inhalte) durch Filter-Hook()-Events gezielt auf Daten hin untersuchen mag.

    M.E. ist das eine Form der Nutzbarkeit von "Raum", also Speicherplatz. Damit wir "parallel" (viele Wörter betrachtet) zählen können. Sonst müsste ja, würde ich regulär "indexOf()",
    "replace()" o.ä. verwenden, der gesamte Stream für jeden gesuchten Substring erneut von vorne begonnen untersucht werden - oder!? Das versuche ich ja zu verhindern hiermit. ...

    Code:
    • Überprüfe das aktuelle Zeichen im Stream durch dessen Verwendung mit einer Hashtable o.ä. ... im Wert eine Zahl, die wir nun (++) inkrementieren, wenn das aktuelle Zeichen im Stream somit dem ersten Wort-Zeichen entspricht (begonnen mit (0)-Wert heißt: ohne jede relative Offset-Differenz-Verschiebung). Also erstmal (++ => =1).
    • Diese Werte-Zählung (1) verweist (als ein Zeiger quasi) nun - als relative Offset-Differenz-Verschiebung - auf das zweite Zeichen des Wortes, das wir jeweils untersuchen, welches also mit dem ersten Zeichen begonnen hatte. Somit wird im Stream++ nun das nächste Zeichen kontrolliert, ob es dem gesuchten Zeichen im Substring-Offset [1] entspricht. Wenn TRUE, wird die Zählung im Wert erneut (++) auf (2) gesetzt, für den nächsten, relativen Substr-Offset-Einzug, also zur Überprüfung der jew. gesuchten Wörter [2]. Falls aber FALSE, so wird die Werte-Zählung auf (0) zurück gesetzt - um im Anschluss das aktuelle Stream-Zeichen wieder mit dem ersten Zeichen des gesuchten Wortes zu vergleichen. Und dann alles auf's neue.
    • Sobald die Werte-Zählung der Länge des jew. gesuchten Substrings entspricht, gilt das Wort als erfolgreich gefunden! Es gilt dabei übrigens, dass je (Stream.Offset++) der Reihe zu allen gesuchten Wörten das jeweilige Zeichen kontrolliert wird → parallele Suche vieler Wörter je Schritt.
    Im Prinzip ein "Klappen"-System quasi. ... der logische Ausschluss von Information aus Such-Abfragen, sobald eine Bedingung nicht mehr stimmt. Fast so, als würde man durch den DB-Suchlauf in der Angabe gesuchter Attribute-Werte eben diverse Datensätze von der weiteren Suche ausschließen, damit die gewünschten Records schneller gefunden werden (es wird ja mit dem Reset der Werte-Zählung quasi das sonst eigentlich nachfolgende Zeichen ausgeschlossen oder so. ... hm; verständlich?
    Wäre das effizient/vorteilhaft? Oder was gibt's da evtl. für bestehende Alternativen!? Wie ist das denn bspw. mit RegExp bzw. PCRE? xD´

    1 2 3 4 5 6 7 8
    2 1 4 3 6 5 8 7
    3 4 1 2 7 8 5 6
    4 3 2 1 8 7 6 5
    5 6 7 8 1 2 3 4
    6 5 8 7 2 1 4 3
    7 8 5 6 3 4 1 2
    8 7 6 5 4 3 2 1

  2. #2
    Registered User
    Registriert seit
    Oct 2007
    Beiträge
    246
    Renommee
    234

    AW: Effiziente Substring-Suche [Algorithmus]

    Für einzelne kleine Aufgaben, würde ich das in BASH lösen. Dein Professor gibt aber schon JAVA oder C++ vor so wie es aussieht.
    Ziel soll sein, dass du den Lehrinhalt verstehst. Einfach nehmen was er vorgibt. Später im Beruf bleibt es dir überlassen.

  3. #3
    Quantenmechaniker
    Registriert seit
    Aug 2002
    Beiträge
    1.935
    Renommee
    283

    AW: Effiziente Substring-Suche [Algorithmus]

    Neee, ich studiere doch garnicht. Und ich gebe mir JavaScript selbst vor.
    Ich überlege selbst, wie ich effizient (parallel) in Strings suchen kann. ...

    1 2 3 4 5 6 7 8
    2 1 4 3 6 5 8 7
    3 4 1 2 7 8 5 6
    4 3 2 1 8 7 6 5
    5 6 7 8 1 2 3 4
    6 5 8 7 2 1 4 3
    7 8 5 6 3 4 1 2
    8 7 6 5 4 3 2 1

  4. #4
    Registered User
    Registriert seit
    Oct 2007
    Beiträge
    246
    Renommee
    234

    AW: Effiziente Substring-Suche [Algorithmus]

    effizentes suchen mit regexp oder libpre.
    Javascript ist an sich schon nicht performant.

    Entweder du schaust dir regexp an und dessen implementierung oder du schaust, wie suchmachinen es machen.
    Meist verwenden sie triplets und idexieren diese.

    Für kurze Wörter wie der/die/das oder andere 2-5 stelligen wörter kannst du eine for schleife nehmen. das ist einfacher.
    Wenn du große Text und verschiedene lange suchstrings verwenden willst dann schau die libs von oben an oder suchalgos.
    da gibt zig info in goooooogle

Aktive Benutzer

Aktive Benutzer

Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)

Ähnliche Themen

  1. Effiziente Ansteuerung von 5000 LED's???
    Von Commander-@ im Forum Naturwissenschaften & Elektronik
    Antworten: 10
    Letzter Beitrag: 12.11.2006, 10:46
  2. Suche Algorithmus für Hölzer-Spiel Erweiterung
    Von Agitator im Forum Algorithmen und sonstige Programmiersprachen
    Antworten: 2
    Letzter Beitrag: 04.01.2004, 19:05
  3. Substring
    Von Freezer Z im Forum Web Development
    Antworten: 1
    Letzter Beitrag: 14.09.2001, 19:55
  4. hilfe bei substring
    Von nightdream im Forum Web Development
    Antworten: 3
    Letzter Beitrag: 31.07.2000, 16:46

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •