Ich bin auf ein Problem gestoßen, eine Zeichenfolge in einem OCR-erkannten Text abzugleichen und die Position zu finden, in der willkürliche Toleranzen für falsche, fehlende oder zusätzliche Zeichen berücksichtigt werden können. Das Ergebnis sollte eine Position mit der besten Übereinstimmung sein, möglicherweise (nicht notwendigerweise) mit der Länge des übereinstimmenden Teilstrings.
Zum Beispiel:
%Vor%Ich habe versucht, den Levenstein-Algorithmus anzupassen, aber er funktioniert nicht richtig für Teilstrings und gibt keine Position zurück.
Der Algorithmus in Delphi wäre bevorzugt, aber jede Implementierung oder Pseudologik würde ausreichen.
Hier ist eine rekursive Implementierung, die funktioniert, aber möglicherweise nicht schnell genug ist. Das Worst-Case-Szenario ist, wenn keine Übereinstimmung gefunden werden kann und alle bis auf das letzte Zeichen in "What" an jedem Index in Where abgeglichen werden. In diesem Fall erstellt der Algorithmus für jedes Zeichen in Where Length (What) -1 + Tolerance-Vergleiche plus einen rekursiven Aufruf pro Tolerance. Da sowohl Toleranz als auch die Länge von Was sind Constnats, würde ich sagen, der Algorithmus ist O (n). Die Leistung wird linear mit der Länge von "Was" und "Wo" verringert.
%Vor%Ich habe den folgenden Code verwendet, um die Funktion zu testen:
%Vor%Für den Fall:
%Vor%es zeigt eine Übereinstimmung auf Zeichen 9, der Länge 6. Für die anderen beiden Beispiele gibt es das erwartete Ergebnis.
Tags und Links string delphi fuzzy-search