- Offizieller Beitrag
Wenn man in AutoIt ein Wort in einem Text sucht, nimmt man normalerweise StringInStr dafür oder bastelt etwas mit StringRegExp.
Das ist meistens ausreichend und auch schnell genug.
Wenn man allerdings eine "unscharfe" Suche möchte, wird es kompliziert und langsam. Die sogenannte Levenshtein-Distanz (oder in Prozent umgerechnet) gibt die Ähnlichkeit zweier Wörter zurück.
In AutoIt ist die Funktion aber sehr zeitaufwändig und wenn man einen größeren Text durchsuchen will, dauert es sehr lange.
Da ich die Levenshtein-Distanz bereits in Nim übersetzt habe, dachte ich mir, das kann ich dann doch auch für AutoIt zur Verfügung stellen (als DLL).
Die Suche habe ich dann auch gleich in Nim geschrieben, so wird es noch etwas schneller.
Edit 03.10.2020:
Ich habe den Nim-Quellcode jetzt dahingehend geändert, dass gleich alle Fundstellen (als String) zurückgegeben werden.
Das hat den Vorteil, dass bei sehr vielen Fundstellen nur ein DllCall von AutoIt aus erforderlich ist. Im Worstcase-Fall (Suchbegriff: ein Buchstabe und Null Prozent) würde sonst für jedes Wort ein Dll-Call nötig sein, was recht zeitaufwändig ist.
Edit 06.10.2020:
Die Nim-interne Funktion zur Berechnung der Levenshtein-Distance editDistanceAscii() ist deutlich effektiver, als die von mir konvertierte Funktion. Die Laufzeit des Beispiels schrumpft somit von vorher 238ms auf nunmehr 66ms.
Ich finde, das ist eine neue Version wert.
Der Nim-Sourcecode sieht so aus (zum compilieren des Codes als Dll den Compiler folgendermaßen aufrufen: nim c -d:release --app:lib FuzzySearch.nim
import strutils, std/editdistance
# Levenshtein-Distanz in Prozent berechnen
proc lsDistancePercent*(s, t: cstring): int {.stdcall,exportc,dynlib.} =
let n = max(s.len, t.len)
if n == 0 or s == t: return 100
return int(100 / n * float(n - editDistanceAscii($s, $t)))
# Ein Objekt zum speichern der Woerter
type
FuzzySearch* = ref object of RootObj
sSearch*: seq[string]
let oFS = FuzzySearch() # Objekt erstellen
# Funktion, zum erstellen der Woerter aus dem uebergebenen String
proc load*(sData: cstring): int {.stdcall,exportc,dynlib.} =
if sData == "": return 0
oFS.sSearch = splitWhitespace($sData, -1)
return 1
# Funktion, um die Anzahl der Woerter zurueckzugeben
proc getCount*(): int {.stdcall,exportc,dynlib.} =
return oFS.sSearch.len
# Funktion, um ein bestimmtes Wort zurueckzugeben
proc getWord*(iIndex: int): cstring {.stdcall,exportc,dynlib.} =
if iIndex < 0 or iIndex > oFS.sSearch.len - 1: return ""
return oFS.sSearch[iIndex]
# Funktion, fuer die Levenshtein-Suche
# Parameter:
# t = Suchbegriff
# s = ab dieser Wort-Position suchen
# p = Prozentwert, fuer die Suche
# Rueckgabe:
# Ein String mit den Positionen der gefundenen Worte (durch Kommata getrennt),
# oder ein Leerstring, wenn nicht gefunden, bzw. Fehler
proc search*(t: cstring, s, p: int): cstring {.stdcall,exportc,dynlib.} =
if oFS.sSearch.len == 0: return ""
if s > oFS.sSearch.len - 1 or s < 0: return ""
var
sReturn: seq[string]
iPercent: int = p
if iPercent > 99: iPercent = 99
if iPercent < 0: iPercent = 0
for iIndex in s + 1 .. oFS.sSearch.len - 1:
if (lsDistancePercent(oFS.sSearch[iIndex], $t) >= iPercent): sReturn.add($iIndex)
return join(sReturn, ",")
Alles anzeigen
Für die, die kein Nim installiert haben, habe ich die DLL bereits compiliert mit ins ZIP-Archiv (Anhang) gepackt.
Das AutoIt-Beispiel sieht dann so aus:
#include <Array.au3>
#AutoIt3Wrapper_UseX64=y
Global $hDll = DllOpen(@ScriptDir & '\FuzzySearch.dll')
Global $sWord1, $sWord2, $aRet, $iPos, $iPercent, $sFound
; Test 1 = Levenshtein-Distanz in Prozent
; =======================================
$sWord1 = 'Zuckerkuchen' ; diese beiden Woerter
$sWord2 = 'Butterkuchen' ; sollen verglichen werden
$aRet = DllCall($hDll, 'int', 'lsDistancePercent', 'str', $sWord1, 'str', $sWord2)
If @error Then Exit
ConsoleWrite('Übereinstimmung: ' & $aRet[0] & '%' & @CRLF) ; in $aRet[0] steht das Ergebnis (als Integerzahl, in Prozent)
; Test 2 = Die Fuzzy-Suche in einem grossen Textdokument
; ======================================================
$sWord1 = FileRead(@ScriptDir & '\bgb.txt') ; ein Textdokument laden (BGB, > 14.000 Zeilen, 1.5 MB)
$aRet = DllCall($hDll, 'int', 'load', 'str', $sWord1) ; und den Text an die DLL uebergeben
If @error Then Exit
ConsoleWrite('Load ok: ' & ($aRet[0] == 1) & @CRLF)
$aRet = DllCall($hDll, 'int', 'getCount') ; Anzahl der Woerter ermitteln
If @error Then Exit
ConsoleWrite('Count: ' & $aRet[0] & @CRLF)
$aRet = DllCall($hDll, 'str', 'getWord', 'int', 85271) ; ein bestimmtes Word aus dem Text holen
If @error Then Exit
ConsoleWrite('Word: ' & $aRet[0] & @CRLF)
$sWord2 = 'Richtlinie' ; das Suchwort
$iPos = 0 ; Startwert. Ab diesem *Wort* (*nicht* Buchstaben) wird gesucht.
$iPercent = 66 ; mit welcher Genauigkeit soll gesucht werden (in Prozent)
$iTimer = TimerInit()
; Die Rueckgabe besteht aus einem String mit den Positionen der gefundenen
; Woerter (durch Kommata getrennt) oder ein Leerstring, wenn nichts gefunden
; wurde bzw. ein Fehler aufgetreten ist.
$aRet = DllCall($hDll, 'str', 'search', 'str', $sWord2, 'int', $iPos, 'int', $iPercent)
If @error Then Exit ConsoleWrite('Error: ' & @error & @CRLF)
ConsoleWrite('Timer: ' & TimerDiff($iTimer) & @CRLF)
ConsoleWrite('Found on Position: ' & $aRet[0] & @CRLF)
DllClose($hDll)
Global $aFound = StringSplit($aRet[0], ',', 2)
_ArrayDisplay($aFound)
Alles anzeigen
Wichtig ist noch, dass ihr das AutoIt-Script als 64-Bit-Version ausführt #AutoIt3Wrapper_UseX64=y, weil Nim eine 64-Bit-DLL erstellt.
Alle Quellcodes und den Beispieltext (BGB mit 207336 Wörtern) findet ihr im ZIP-Archiv.