String Problem

[Momrad]

Hallo,

ich habe ein kleines Problem, und finde einfach den Ansatz nicht. Evtl. kann mir ja jemand einen Tip geben.

Ich habe 2 Zeichenketten, eine die z.b. ein Benutzer eingegeben hat und eine die als Vorgabe dient.

Nun sollen die Zeichenketten verglichen werden , Eingabefehler gezählt werden und das falsche bzw. fehlende Zeichen markiert werden.

z.b.

axse fghij kl qrst uvwxy <---- das war die Eingabe

abcde fghij klmno pqrst uvwxy <---- das die Vorgabe (Lösung)

a***e fghij kl*** *qrst uvwxy = 7 Fehler<--- so in etwa sollte das ergebnis aussehn


Es ist aber nur ein Beispiel, die Texte bestehen nachher aus zufälligen zeichen.



Vielleicht sehe ich den Wald vor lauter Bäumen ja auch nicht. Wäre nett wenn mir jemand einen Wink geben könnte.


gruss
Momrad

[Jan Krüger]

Das ist gar nicht mal so einfach, denn du musst dir überlegen, wie du einen Fehler definieren willst. Hier wäre es z.B. wahrscheinlich am sinnvollsten, geänderte oder zusätzlich eingefügte Zeichen als Fehler zu erkennen.

Mir fällt da spontan ein ähnliches Problem ein, das Berechnen der Edit- oder Levenshtein-Distanz. Dabei geht es darum, Änderungen (veränderte, eingefügte oder gelöschte Zeichen) zu zählen (und zwar die minimale Anzahl von Änderungen, um aus dem Startstring den Endstring zu machen. Dabei werden die Änderungen allerdings nicht markiert. Vielleicht kannst du den Algorithmus aber als Inspiration benutzen... auf der Wikipedia-Seite zu Levenshtein-Distanz wird der Algorithmus erklärt.

[DarkTom]

Erstmal ein Link für dich:
http://www.cs.sunysb.edu/~algorith/files/approximate-pattern-matching.shtml
Leider nicht so informativ wie das Buch, aber zumindest die dortigen Links auf Implementationen helfen dir vielleicht weiter.



Wie Jan schon schreibt, musst du erstmal sauber definieren, was du als Fehler/Veränderung erlaubst bzw erkennen willst. Teile uns dass ruhig auch mit, ich finde das Thema interessant. :)

Brauchst du noch mehr Infos, so sind "approximative string matching" gute Suchworte.

[Patrik Graf]

So schwer ist es nicht... ;)

Du hast 5 Zeichen pro block. Jetzt musst du jedes Zeichen der eingabe durchgehen und gegen block 1 vergleichen. Hier wäre das so:

axse fghij kl qrst uvwxy

abcde fghij klmno pqrst uvwxy

a ist korrekt, x ist nicht korrekt, nächstes Zeichen das übereinstimmernd wäre mit block 1 der lösung wäre das e, also fehlen hier b, c und d. Als nächstes nimmst du block 2 und prüfst gegen das nächste Zeichen. Deiser block stimmt komplett mit der lösung überein... usw...

Wichtig ist nur, das du nie mehr Zeichen der eingabe gegenprüfst, als du Zeichen pro Block übrig hast... denn dann wäre bei kl schluss... ;)

Hoffe das hat geholfen ;)

[Momrad]

Erst mal DANKE für die Tips ;)

Ich denke mein Beispiel war nicht ganz ausreichend^^

hier nochmal ein Beispiel:

abcde fghij klmno pqrst uvwxy abcde fghij klmno pqrst uvwxy <--- gefordert

axse fghij kl qrst uvw xy abcdf ghij klm np uvwxy <--- eingegeben.

a***e fghij kl*** *qrst uvwxy abcd* *ghij klmn* pqrst uvwxy ---> Fehler:10

@Patrik: daran hatte ich auch schon gedacht, nur tritt dann ein Problem auf wenn die Anzahl der Blöcke sich unterscheiden weil irgendwo ein space zuviel ist. Naja wird nur umfangreicher ;)

Ich denke ich werde es aber dennoch damit probieren.


Also Fehler ist erstmal grundsätzlich alles, was nicht übereinstimmt, also fehlende,falsche und überflüssige Zeichen, aber

wenn die ersten Gruppen z.B.: 'axs e fghij' wären dann sollte das Programm erkennen das 'e' zur ersten gruppe gehört.
Genauso bei den gruppen 'uvw' und 'xy'

Wenn die erste gruppe 'aexs' z.b. hieße dann wäre das 'e' aufjeden Fall falsch


Hintergrund: Ich schreibe an einem Morse-Lernprogramm, und möchte nach Prüfungen den eingegeben Text überprüfen lassen. Nun jeder gewöhnt sich dann eigene Verfahren an mit Hörfehlern umzugehen. Ich setze an den Stellen , die ich nicht gehört habe z.b. Punkte, andere schreiben einfach weiter oder spacen weiter.


Vielleicht sollte ich doch eine Regel einführen :) , ich dachte das ich alle möglichen Situationen einbauen könnte :cool:

Nochmal danke für die Links die helfen mir auf jedenfall weiter. Da mir vermutl. das mathematische Grundwissen dazu fehlt, wusste ich einfach nicht wonach ich suchen sollte. Die Algorithmen die ich fand passte irgendwie nicht zu meinem Problem.

Gruss

Momrad

[TGGC]

Tja, es ist trotzdem nicht eindeutig, was der Fehler ist, z.B.:

abdee

Ist das jetzt einmal vergessen und einmal zuviel oder doch 2 mal falschgetippt? Wo sollen die Sternchen hin?

Oder warum ist bei aexs das e falsch? Es fehlen einfach nur 3 Buchstaben. Ab wann gilt das e als korrekt? Bei abexs, abcexs oder erst bei abcdexs?


Bye, TGGC

[Momrad]

also der Vergleich einer Gruppe funktioniert ja schon das habe ich so gelöst:

Public Function getFehlerO(strTest As String, strVorgabe As String) As Integer
Dim strReverse As String
For i = 1 To Len(strTest)
strReverse = strReverse & Mid(strTest, Len(strTest) - (i - 1), 1)
Next
For i = 1 To Len(strVorgabe)
If InStr(1, strTest, Mid(strVorgabe, i, 1)) = 0 And InStr(1, strReverse, Mid(strVorgabe, i, 1)) = 0 Then
getFehlerO = getFehlerO + 1
Else
strFehler = strFehler & Mid(strVorgabe, i, 1)
End If
Next
End Function

Edit: hmpf sehe gerade was blödes ;) wollte mit den instr-Funktionen eigentlich testen, ob das Zeichen an der gleichen Stelle steht. In dieser Form ist das natürlich sinnlos die doppelte Abfrage :mauer: .

bitte verzeiht mein denglish, aber ich kann es mir einfach so besser merken^^

Ich habe eine zweite Function die genau so aussieht wie diese, allerdings beim Hochzählen des getFehler das "*" auch setzt.

Wo ich echt Probleme bekomme ist wenn wie gesagt z.b. eine ganze Gruppe weggelassen wurde oder eine Gruppe da steht die nicht hingehört.
Es könnte ja auch sein das in der Eingabe mehrere gruppen ausgelassen wurden.

gruss Momrad

PS: Mein Programm wird unter C++ laufen aber zum Testen von solchen Sachen nutze ich ganz gerne mal VB, da kenne ich mich bissl besser aus und geht schneller :D (was gegen über c/c++ nicht abwertend gemeint ist ;) )

[TGGC]

Ein Ansatz dazu ist, jede Variante (Gruppe stimmt, Gruppe zuviel, Gruppe fehlt) zu probieren und dann nach maximum Likelihood das zu wählen, was die geringste Fehlerzahl bringt.


Bye, TGGC

[Momrad]

Ein Ansatz dazu ist, jede Variante (Gruppe stimmt, Gruppe zuviel, Gruppe fehlt) zu probieren und dann nach maximum Likelihood das zu wählen, was die geringste Fehlerzahl bringt.



Danke für den Tip, ich denke das bringt mich nen grossen Schritt weiter.

gruss

Momrad

[Momrad]

So hier nochmal mein Gruppen-Vergleich


Public Function getFehler(strTest As String, strVorgabe As String) As Integer
Dim strReverse, strReverseV As String
For i = 1 To Len(strTest)
strReverse = strReverse & Mid(strTest, Len(strTest) - (i - 1), 1)
Next
For i = 1 To Len(strVorgabe)
strReverseV = strReverseV & Mid(strVorgabe, Len(strVorgabe) - (i - 1), 1)
Next
For i = 1 To Len(strVorgabe)
If (InStr(1, strTest, Mid(strVorgabe, i, 1)) <> i And InStr(1, strReverse, Mid(strReverseV, (Len(strReverseV) + 1) - i, 1)) <> (Len(strReverseV) + 1) - i) Then
getFehler = getFehler + 1
strFehler = strFehler & "*"
Else
strFehler = strFehler & Mid(strVorgabe, i, 1)
End If
Next
strFehler = strFehler & " "
End Function

Nun sollte 'abdee' als ergebnis 'ab**e' geben, da 'd' ja nicht an der richtigen Stelle steht sowohl von links-nach-rechts, als auch umgekehrt.

Damit will ich verhindern, das jemand statt 'abcde' z.b. 'baecd' eingibt.

[Momrad]

habs gelöst :D


nochmals Danke ;)

MfG

Momrad