Bool'scher Suchalgorithmus

Aziz

Guten Abend!

Ich benötige einen Algorithmus der einen Suchstring so ähnlich wie Google parsen kann um damit Volltextsuchen durchführen zu können. Unterstützt werden müssen folgende Operatoren:

AND (implizit durch Leerzeichen)
OR ( od. senkrechter Strich: | )
NOT ( od. Minuszeichen - )
Phrase ( gekennzeichnet durch Anführungsstriche: e.g. "die flinke Maus" )
Wildcards ( e.g.: "die * Maus" )

Kann mir wer zu dieser Problemstellung irgendeinen Anhaltspunkt liefern?
Literatur (kostenlos wenn's geht), "fertige (Teil-)Lösungen" (muss natürlich nicht exakt auf mein Problem passen, es muss nur relevant in der Problemlösung sein), Ideen etc. diesbezüglich würden mich sehr freuen!

PS:. Vielleicht wäre es bedeutsam zu erwähnen, dass ich mich mit regulären Ausdrücken hervorragend auskenne. Nur wenns um's Parsen geht bin ich eine Niete...

ChockoCookie

boost::tokenizer

[edit]
Um nochn paar worte dazu zu schreiben:

Quotes haben die höchste priorität, also erst rausfinden was von "" umschlossen ist, das wird in nachfolgenden Durchläufen nicht mehr zerteilt. zB ein erster tokenizer durchlauf nach ".
Überlegen wie du die Priorität/Reichweite der anderen Operatoren festlegst.
Tokenizer durchläufe nach den anderen Operatoren, je nach Priorität.

Wenn dus ein bisschen komplizierter/einfacher (ist Ansichtssache) haben willst, ist auch boost::spirit für den job geeignet.
[/edit]

Aziz

Danke, werd mich mal damit befassen. Andere Vorschläge sind immer noch willkommen

otze

@chocko tokenizer ist damit schlichtweg überfordert.
"ich bin ein String" will man als ganzes haben, und nicht als 4 separate token

Aziz

Ich versuche momentan mein Problem mit boost::spirit zu lösen. Ich kann die aktuelle Version mit VC7 leider nicht kompilieren. In der config Header von boost::spirit wird absichtlich ein Fehler erzeugt, da mein Compiler nicht unterstützt wird.

Hat wer Rat?

Dann hol dir doch das Visual C++ 2003 Toolkit mit dem 7.1 Compiler. Ist umsonst.

otze

oder mingw, der wird auch unterstützt.
aber für sone triviale aufgabe sollte man nicht unbedingt boost::spirit rausholen, das ding ist doch ne spur zu mächtig.

Aziz

Ok das Toolkit hab ich installiert und in VC7 hab ich in den Einstellungen die neuen Ordner hinzugefügt. Ich krieg jetzt folgenden Fehler:

error LNK2001: unresolved external symbol __check_commonlanguageruntime_version

aber für sone triviale aufgabe sollte man nicht unbedingt boost::spirit rausholen, das ding ist doch ne spur zu mächtig.

Das kannst du laut sagen. Wenn ich nur die Dokumentation von boost::spirit durchlese schau ich immer so
Soll ich das lieber mit dem tokenizer von boost lösen, oder kannst du mir eine andere Idee vorschlagen?

ChockoCookie

otze schrieb:

@chocko tokenizer ist damit schlichtweg überfordert.
"ich bin ein String" will man als ganzes haben, und nicht als 4 separate token

Wieso, man muss ja leerzeichen nicht zu den trennzeichen geben

otze

hast du gelesen, worum es hier geht?

suchbegriffe: Hallo wurzel Panzer "eine schöne Blumenwiese"

ich weis nicht, wie die einzelnen suchfunktionen das handhaben, aber normalerweise sind die ersten 3 suchwörter einzeln anzusiedeln, dh jeder beitrag bei dem eines dieser wörter vorkommt wird angezeigt. Dh die 3 wörter müssen jeweils 1 separates tokens ein, da sie durch Leerzeichen getrennt sind,muss der tokenizer auf leerzeichen eingestellt sein. Bei "eine schöne blumenwiese" werden nur all jene seiten angezeigt, die die genaue wortgruppe "eine schöne Blumenwiese" enthalten, am sinnvollsten ist das antürlich rauszubekommen, wenn das nicht 3 separate token sind ;),dh tokenizer dürfte hier nicht nach den leerzeichen trennen.

Wäre doch auch nicht sonderlich kompliziert, das selbst zu implementieren, etwa so:

überprüfe das erste Zeichen des Strings: ist das ein " dann ermittle die Position des nächsten " und schneide den Teilstring vom ersten " bis zum zweiten " aus dem String raus - entferne gegebenenfalls noch die " und du hast dein Token.
ansonsten, ermittle die position des nächstens leerzeichens, falls keins mehr da ist, bist du fertig
schneide den Teilstring vom Beginn bis zur position des leerzeichens aus dem String raus - und du hast dein Token

Naja, zumindest wenn du string benutzt, sollte das doch nicht so kompliziert sein...

Mfg, smasher1985

ChockoCookie

otze schrieb:

... dh tokenizer dürfte hier nicht nach den leerzeichen trennen.

Daher auch mein Vorschlag mit mehreren Tokenizerdurchläufen (Siehe oben).

otze

ChockoCookie schrieb:

otze schrieb:

... dh tokenizer dürfte hier nicht nach den leerzeichen trennen.

Daher auch mein Vorschlag mit mehreren Tokenizerdurchläufen (Siehe oben).

super idee,nur dass die sache ca 3mal so komplex ist, wie sich den tokenizer selber zu schreiben

ChockoCookie

otze schrieb:

super idee,nur dass die sache ca 3mal so komplex ist, wie sich den tokenizer selber zu schreiben

Wohl kaum.

foreach(tokenizedBy(string, '"')){
    if( token == '"' ){
        token++;
        result += token;
        token++;
        continue;
    }
    foreach( tokenizedBy(token, '+-|') ){
        // dürfte klar sein
    }
}

Man gewinnt zwar nicht viel, aber komplexer ist es auch nicht. Ich verfolge nur gern den Ansatz "Soviel wie möglich in vorhandene und getestete Libraries verschieben".

Korbinian

es gibt recht hübsche algorithmen zur teilstring suche. einer (name vergessen) ist z.b., dann man einfach mal das vergleichen anfängt:

orig: [suche die nadel in dieters heuhaufen] pattern: [dieters heuhaufen]
#1:   [d]  
#2:    [d]
#...:       [d]
#3:         [di]
#4:         [die]
#5: (fail!)      [d]
#6:               [d]
#...:                     [d]
#7:                       [die]
#...:                     [dieters heuhaufen]

es wird also erstmal nach dem übereinstimmenden 1. buchstaben gesucht. dann sukzessive erweitern, bei fehlschlag bei aktuellem index+1 (also nach dem falschen zeichen) von vorn anfangen.
wenn du das jetzt für jedes pattern machst, bekommst du jeweils eine liste mit offsets. ist diese leer -> nicht gefunden
die auswertung, was nun ausgegeben werden soll,kannst du dann über die logische verknüpfung berechnen

otze

ChockoCookie schrieb:

foreach(tokenizedBy(string, '"')){
    if( token == '"' ){
        token++;
        result += token;
        token++;
        continue;
    }
    foreach( tokenizedBy(token, '+-|') ){
        // dürfte klar sein
    }
}
Man gewinnt zwar nicht viel, aber komplexer ist es auch nicht. Ich verfolge nur gern den Ansatz "Soviel wie möglich in vorhandene und getestete Libraries verschieben".

es gibt in c++ kein foreach.

Ich verfolge nur gern den Ansatz "Soviel wie möglich in vorhandene und getestete Libraries verschieben".

ich verfolge den ansatz: wenn dein problem durch eine lib ohne viel zusätzliche arbeit gelöst werden kann, dann benutz sie.

ChockoCookie

otze schrieb:

es gibt in c++ kein foreach.

OMG *andenkopfpatsch* wie konnte ich das nur vergessen. Ich hätte gedacht es wäre offensichtlich, das der Code oben PSEUDOCODE ist. Schon allein dadurch, das ich normale Codetags und keine CPP Codetags benutzt habe.

Aber abgesehn davon, finde ich wäre das ursprüngliche Problem am elegantesten so zu lösen, das die Anfrage in eine boost Regular expression umgeformt wird, und damit die Daten durchsucht.