ApproxStrUtils
Version 0.1

Diese Unit stellt einige Funktionen bereit, mit deren Hilfe man einen String in einem anderen suchen kann. Das geht mit Pos, PosEx, AnsiContainsStr, und dem ganzen Krempel. Klar, kein Problem.

Aber was macht man, wenn man auch ein paar Rechtschreibfehler erlauben will? Man sucht z.B. nach "Schifffahrt", aber der Text, in dem gesucht wird, benutzt die alte Rechtschreibung, so dass immer nur von "Schiffahrt" die Rede ist? Dann ist man hiermit genau richtig.

Diese Unit stellt einige Funktionen bereit, mit denen ein Text nach einem Muster abgesucht wird, wobei eine gewisse Anzahl von Fehlern erlaubt ist. Ein "Fehler" ist dabei:

• Ein Einfügen eines Zeichens
  
• Ein Entfernen eines Zeichens
  
• Ein Ändern eines Zeichens

Für die Informatiker: Hier gehts also um die Edit- oder Levenshtein-Distanz.

Folgende Funktionen werden bereitgestellt:

Berechnet die Edit-Distanz der beiden Strings.

Bestimmt, ob der eine String ähnlich zu dem anderen gemäß der Edit-Distanz ist.

Bestimmt, ob der Subtext im Text mit höchstens MaxError Fehlern gemäß der Edit-Distanz enthalten ist. Groß- und Kleinschreibung wird berücksichtigt.

Bestimmt, ob der Subtext im Text mit höchstens MaxError Fehlern gemäß der Edit-Distanz enthalten ist. Groß- und Kleinschreibung wird nicht berücksichtigt.

Gibt den Startindex eines Vorkommens des Subtextes im Text mit höchstens MaxError Fehlern gemäß der Edit-Distanz. Der Text wird ab der Position Offset durchsucht. Der Out-Parameter Count enthält die Länge des gefunden Vorkommens (z.B. zur Benutzung in copy).

Dasselbe wie ApproxPosEx mit Offset=1.

Liefert den Startindex des ersten Vorkommens mit minimaler Fehlerzahl zurück. Die Out-Parameter Count und BestError geben die Länge des Vorkommens bzw. die Anzahl der Fehler an.

Ich hoffe, ich habe unsinnige Eingaben soweit wie möglich abgefangen, sodass dann trotzdem was halbwegs sinnvolles als Ergebnis geliefert wird. Prinzipbedingt findet ApproxPosEx nicht wirklich alle Vorkommen (wird auch in der Demo klar), aber wenn das gesuchte Wort irgendwo ungefähr auftaucht, dann wird das auch gefunden.

Fehler und Verbesserungsvorschläge sind wie immer willkommen.

Also das sieht doch schonmal ganz gut aus!

Eine Verbesserung wäre evtl noch, dass man nicht mehr Fehler als Buchstaben zulassen darf.
Sonst kommen da leicht verwirrende und auch (wie du schon geschrieben hast) falsche Sachen bei raus.

Gruß

Stimmt natürlich, schon bei 3 Buchstaben ist "Schiffahrt" = "Schriftart", oder bei 1 Buchstabe "Bach" = "Buch", oder "Weg" (der) gleich "weg".

Für den maximalen Fehler sollte man in der Regel etwas wie Length(ASubText) Div k wählen, mit k irgendwas zwischen drölftausend und 2. Aber die Funktionen laufen (hoffentlich) nicht mehr Amok, wenn man 'a' in 'b' mit 1000 Fehlern suchen möchte. Auch der Leerstring sollte jeweils funktionieren.

Für den Rest ist dann der Programmierer verantwortlich, der das Zeug nutzt.

An genau sowas habe ich neulich auch getüftelt... und aufgegeben.
Habe mich schon geärgert das Delphi in dieser Richtung nichts brauchbares dabei hat.
Wenn man irgendwelche, von Menschen erstellten Texte, nach bestimmten Informationen durchsuchen will ist es gut eine Suchfunktion zu haben die nicht gleich bei einem Tippfehler streigt.

Ich würde die folgenden Erweiterungen, für eine besondere Betrachtung als nicht-Fehler, sehr begrüßen :
- das beachten von Buchstabendrehern,
- benachbarter Tasten auf der Tastatur als mögliche Orginalbuchstaben für einen gefundenen Buchstaben,
- Großbuchstaben innerhalb von Wörtern die direkt auf das erste groß geschriebene Zeichen am Wortanfang folgen.

Schöne Unit, das werd ich bestimmt mal brauchen können.
Was noch schön war, wär die Gleichsetzung von Umlauten und der "Umschrift", also "ä"="ae".

Auch Unicode-Support wäre sicherlich nicht schlecht. Rein von der API sieht das aber schon mal ganz gut aus. Was vielleicht auch noch ganz interessant wäre, wäre (wie von Vorpostern angedeutet) Gleichheits-Tabellen (konfigurierbar) für jegliche Funktionen.

Auch interessant wären Dinge wie:
Some_filename_with_some_encoding_-_other_stuff_[ABCDEF42].txt
vs.
SomeFilenameWithSomeEncoding - OtherStuff [ABCDEF42].txt

(Brauch man oftmals beim Vergleich von Dateinamen ...)

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Eventuell noch SoundEx implementieren. Das ist ja relativ schnell gemacht und liefert gute Ergebnisse.

SoundEx ist eine Funktion, die bei Delphi dabei ist und einen prinzipiell anderen Ansatz verfolgt. Und soetwas wie ApproxPos ist mit SoundEx nicht möglich.

@Unicode: Man bekommt auch recht brauchbare Ergebnisse, wenn man mit UTF8-kodierten Strings arbeitet und diese Funktionen hier verwendet.

Zitat:

@Unicode: Man bekommt auch recht brauchbare Ergebnisse, wenn man mit UTF8-kodierten Strings arbeitet und diese Funktionen hier verwendet.

Da Windows aber auf UTF-16 setzt (wie auch D2009), müsste man das anpassen

Da Delphi Funktionen wie UTF8Decode und UTF8Encode anbietet, ist das ganz schnell selbst erledigt, oder man passt als Anwender dieser Funktionen einfach die Parameterübergabe an.

Gausi hat folgendes geschrieben:

SoundEx ist eine Funktion, die bei Delphi dabei ist und einen prinzipiell anderen Ansatz verfolgt. Und soetwas wie ApproxPos ist mit SoundEx nicht möglich.

Nur der normale Algo, nicht das Daitch-Mokotoff Soundex Coding Naja, nicht nötig

Wie gesagt, SoundEx ist prinzipiell anders. Vor allem ist der Einsatzzweck sehr speziell und unter bestimmter Hinsicht stark eingeschränkt. Zum Beispiel lässt sich die Fehlertoleranz nicht justieren, man kann keine ähnlichen Teilworte suchen (zumindest nicht mit vernünftiger Laufzeit), und Fehler wie Buchstabendreher oder Vertipper mit Buchstaben aus einer anderen Gruppe, die aber trotzdem auf der Tastatur nahe beieinander liegen (z.B. R und T) führen direkt zur Ablehnung (oder können dazu führen).

Ich will das nicht schlecht reden, und ich sehe durchaus den vernünftigen Sinn dahinter (bei Datenbankabfragen mit Namen z.B.), aber allgemein halte ich Verfahren wie die Levenshtein-Distanz für sinnvoller, und deswegen werde ich in dieser Richtung da nichts einbauen. Außerdem ist meine Diplomarbeit durch, die unscharfe Suche in Nemp funktioniert mit den Verfahren hier (allerdings etwas abgewandelt) ungefähr 100mal so schnell wie vorher, und damit ist das Thema für mich erstmal gegessen.

Und dass "Britney Spears" und "bewährten Superzicke" nach dem SoundEx-Verfahren ähnlich sind, mag ja lustig sein, dürfte aber bei einer allgemeinen Textsuche eher lästig sein.