JavaScript Fuzzy highlighting

[Gsus]

Hallo,

ich bin gerade mal wieder auf ein interessantes Problem gestoßen, bei dem ich ein wenig Hilfe von euch gebrauchen könnte. Ich möchte gerne eine Funktion schreiben, die einen Substring innerhalb eines Strings hervorhebt. Allerdings sollte dies auf eine "fuzzy"-Art geschehen, d.h. zwischen den einzelnen Buchstaben des Substrings dürfen auch noch andere Zeichen stehen. (Für diejenigen die Sublime Text kennen/benutzen, es sollte so aussehen wie deren Suchfunktion).

Ein Beispiel:
Wenn ich die Funktion highlight anrufe mit den Parametern "An example String" als String und "AexpS" als Suchstring sollte das Resultat so aussehen: An example String.

Ich bin selber bereits relativ weit gekommen dieses Problem zu lösen, allerdings denke ich, dass es sicher eine bessere Möglichkeit gibt. Mein Ansatz:

function highlight(s, t) {
      var matcher = new RegExp(t.replace(/(.)/g, "(.*)($1)(.*)").replace(/\(\.\*\)\(\.\*\)/g, "(.*)"), "i");
      var replace = "";
      for(var i=1; i<=t.length*2+1; i++){
        if(i%2 == 1) {
          replace = replace + "$"+i;
        } else {
          replace = replace + "<strong>$"+i+"</strong>";
        }
      }
      return s.replace(matcher, replace);
    }

Dieser Code funktioniert so:

1. Jeder Buchstabe des Suchstrings t wird in Klammern gesetzt und zwischen diesen Blöcken werden (.*) platziert
2. Nun wird der neue String zusammengebaut aus den Blöcken der RegEx wobei jeder "gerade" Block hervorgehoben wird

Das ganze funktioniert "einigermaßen" in dem Sinne, dass wenn der Suchstring mehrere Male vorkommt, wird das letzte auftreten hervorgehoben. Das ist leider nicht was ich will, ich möchte dass das erste vorkommen hervorgehoben wird. Auch glaube ich, dass das zusammensetzen der RegEx in meiner Version sehr umständlich ist und bin gespannt ob ihr vielleicht einen besseren Lösungsansatz habt!

Vielen dank im Vorraus!

mfg
Gsus

 

[tleilax]

Ich tue mich ein bisschen schwer damit zu erklären, was passiert, aber ich denke, das hier dürfte Dir weiterhelfen:

https://codepen.io/tleilax/pen/jyxmD

Letztendlich baue ich da den RegExp auf, indem ich das Gesuchte in seine einzelnen Bestandteile zerlege und die Zwischenräume mit (.*?) auffülle. Parallel dazu wird gleich der Ersetzungsstring aufgebaut, denn das muss man gar nicht von Hand machen. Da kann auch die RegExp-Engine einfach für herhalten.

Guck Dir am besten mal an, was jeweils hinter den ### steht. Das erste ist der RegExp, das zweite der Ersetzungsstring. Das sollte das Verfahren verdeutlichen. Falls Du nur ein Vorkommen ersetzt haben willst, dürfte es eigentlich reichen, den Modifier 'g' zu entfernen.

 

[apolle]

Anstatt reguläre Ausdrücke zu bemühen kann man auch mit Stringfunktionen arbeiten. Zeichen in Zeichenketten suchen dürfte auch mit JavaScript kein allzu großes Problem sein, die beiden Varianten sind allerdings für die Kommandzeile.


Variante 1: Das jeweils erste Vorkommen aller im Suchstring enthaltenen Zeichen in String

Ist ein (eher unleserlicher) Einzeiler, ich habe ihn mal etwas aufgehübscht:

echo '' | \
awk -v search="AexpS" -v text="An example String" ' BEGIN{ORS=""} { \
    for (i=1;i<=length(search);i++) { \
        chr=substr(search,i,1); \
        position=index(text,chr); \
        if(position!=0) { \
            sub(chr,"<#"chr"#>",text); \
        } \
    } \
    gsub("<#","<strong>",text); \
    gsub("#>","</strong>",text); \
    print text; \
}'

Der Suchstring search wird zeichenweise abgearbeitet. Wenn chr in text vorkommt werden zwei Marker gesetzt: die Zeichenfolge '<#' davor, '#>' dahinter. Sobald der Suchstring abgenudelt ist werden die Marker ersetzt ('<#' durch '<strong>' bzw. '#>' durch </strong>') und text ausgegeben. Die Reihenfolge innerhalb des Suchstrings spielt dabei keine Rolle.

Statt der Marker könnte auch gleich '<strong>' bzw. '</strong>' eingesetzt werden. Falls der einzufügende Text aber Zeichen enthält, die auch im Suchstring vorkommen geht die Sache aber schief: Beispielsweise würde anstelle des abschließenden 'g' das aus dem vorne eingefügten '<strong>' gefunden, das Ergebnis '<stron<strong>g</strong>>A</strong>n ... <strong>S</strong>tring' ist unbrauchbar.

Um ohne Marker arbeiten zu können müssen erst alle Fundstellen ermittelt werden. Durch die Einfügungen wandern die dahinterliegende Fundstellen anderer Zeichen allerdings nach hinten, die zugehörigen Indizes müssen dann angepaßt werden. Es dürfte einfacher sein, die Fundstellen zu sortieren und dann text von hinten nach vorne abzuarbeiten.



Variante 2: Das erste Zeichen des Suchstrings im String suchen, von der Fundstelle ausgehend das nächste Vorkommen des zweiten Zeichens, ...

Auch nicht leserlicher...

echo '' | \
awk -v search="AexpS" -v text="An example String" ' BEGIN{ORS=""} { \
    for (i=1;i<=length(search);i++) { \
        chr=substr(search,i,1); \
        position=index(text,chr); \
        if (position!=0) { \
            print substr(text,1,position-1)"<strong>"chr"</strong>"; \
            text=substr(text,position+1); \
        } \
    } \
    print text; \
}'

Funktioniert im Prinzip wie oben beschrieben, Marker sind aber nicht erforderlich: text bis zum letzten Zeichen vor der Fundstelle ausgeben, dahinter das jeweilige Zeichen (chr, inkl. der Tags). Für die Suche nach dem nächsten Zeichen von search wird dann nur noch der hintere Teilstring von text ausgewertet.


Info:
sub (s, r, t) sucht in t nach der Zeichenkette s und ersetzt sie durch r
gsub (s, r, t) ebenso, ersetzt aber alle Vorkommen von s

---

Edit: x, y z seien drei aufeinanderfolgende Zeichen aus dem Suchstring. Die Suche nach x.*y liefert dann den Teilstring vom ersten 'x' bis zum letzten 'y', eine evtl dazwischen auftretende Teilfolge y.*z ist darin enthalten (Stichwort: greedy matching). Wenn ich DIch richtig verstanden habe arbeitest Du an Variante zwei, passende Strings hätten also (salopp ausgedrückt) folgenden Aufbau: "beliebig viele nicht-x, mindestens ein x, beliebig viele nicht-y, mindestens ein y, beliebig viele nicht-z, mindestens ein z, beliebig viele beliebige Zeichen"


Zusatzfrage: Was soll passieren wenn ein Zeichen des Suchstrings nicht in text vorkommt? Alle andern trotzdem hervorheben oder gar nichts hervorheben?