Best matching substring



  • Hallo,

    ich suche gerade nach einer guten Methode aus einem "fehlerhaften" String den besten sub-match herauszufinden. Wenn man also z.B. folgenden String hat:

    std::string text = "some text,\n value: 2.4 \nsome more text";
    

    dann wäre der interessante Teil hier das 2.4 . Der Wert wird durch den Text davor (also das "value: #.#" ) eindeutig identifiziert. Problem ist dass der Text unterschiedlich lange und auch "Fehler" enthalten kann, also etwa so:

    std::string text = "some text,\n va|ue:1.3 \nsome more text";
    

    Hier ist der Text gerade an der relevanten Stelle "kaputt". Trozdem ist er zur Suchmaske noch sehr ähnlich, man könnte ihn also noch verwenden.

    Meine Frage: Wie würde man sowas am besten lösen? String-matching Algorithmen gibt es ja haufenweise, aber welcher würde sich hier gut eignen? Und gibts da vielleicht schon was passendes in der std-lib oder in boost?



  • mhh mir faellt da spontan regex ein .[0-9].[0-9].



  • Wie kommen denn die Fehler in den Strings zustande? Sind das Benutzereingaben und man will den Leuten eine nicht ganz so strenge Syntax aufzwingen oder was anderes?


  • Mod

    Auf die Schnelle getippt, aber scheinbar funktionierend:

    #include <cstddef>
    
    constexpr std::size_t check_backwards(char const* first_s, char const* last_s,
                                          char const* first  , char const* last  ,
                                          std::size_t tolerance) {
    	std::size_t counter = 0;
    	for (; last != first and counter <= tolerance; ) {
    		if (last_s == first_s)
    			return tolerance+1; // oder last-first + counter
    		--last; --last_s;
    		if (*last_s != *last)
    			++counter;
    	}
    	return counter;
    }
    constexpr std::size_t check_forwards(char const* first_s,
                                         char const* first  ,
                                         std::size_t tolerance) {
    	std::size_t counter = 0;
    	for (; *first != '\0' and counter <= tolerance; ++first, ++first_s) {
    		if (*first_s == '\0')
    			return tolerance+1; // oder strlen(first) + counter
    		if (*first_s != *first)
    			++counter;
    	}
    	return counter;
    }
    
    // Requirements: 0 < tol < SIZE_MAX
    constexpr char const* find_similar(char const* s, char const* ss, std::size_t tol) {
    	if (*ss == '\0')
    		return s;
    	auto start = s;
    	for (; char c = *s; ++s) {
    		auto p = ss;
    		auto d = *p;
    		do {
    			if (c == d) {
    				auto i = check_backwards(start, s, ss, p, tol);
    				if (i > tol)
    					continue;
    				auto j = check_forwards(s, p+1, tol);
    				if (j <= tol and i+j <= tol) {
    					return s-(p-ss);
    				}
    			}
    		} while (d = *++p);
    	}
    
    	return nullptr;
    }
    
    #include <iostream>
    int main() {
    	std::cout << find_similar("some text,\n 1a|ue:1.3 \nsome more text", "value", 2);
    }
    


  • TheBigW schrieb:

    mhh mir faellt da spontan regex ein .[0-9].[0-9].

    War auch mein erster Gedanke, aber damit hatte ich viele false positives, weil halt nicht nur der "value" erkannt wird sondern auch andere. Da steht zum Beispiel sowas wie "something_else: 1.5" . Das würde dann auch erkannt, obwohl es quasi keine "Ähnlichkeit" hat.

    sebi707 schrieb:

    Wie kommen denn die Fehler in den Strings zustande? Sind das Benutzereingaben und man will den Leuten eine nicht ganz so strenge Syntax aufzwingen oder was anderes?

    Ich will Werte aus eingescannten Dokumenten mittels Bilderkennung extrahieren. Dafür benutz ich eine Bibliothek die auch ganz gut funktioniert, aber auch immer mal wieder Fehler erzeugt.

    Arcoth schrieb:

    Auf die Schnelle getippt, aber scheinbar funktionierend:

    Cool Danke, werd ich gleich mal intensiv testen 👍



  • happystudent schrieb:

    Arcoth schrieb:

    Auf die Schnelle getippt, aber scheinbar funktionierend:

    Cool Danke, werd ich gleich mal intensiv testen 👍

    Getestet, funktioniert wie gewünscht, Danke 🙂


Log in to reply