Schnelle Ähnlichkeitssuche

[Martin Schneider]

Hallo!

Ich habe eine Access-Datenbank mit etwa 2.500 Datensätzen. Wenn ein
neuer Datensatz eingegeben wird, mache ich eine Ähnlichkeitssuche per
Levenshtein Distance über die vorhandenen Daten und biete die Top-Ten
als Auswahl an, um Dubletten zu vermeiden.

Leider ist diese Methode bei langen Strings sehr langsam. Gibt es hier
eine schnellere Alternative?

Danke für Eure Tips.

Gruß,
Martin

[unknown]

Versuch mal die Methode "triplet".

'--- Die Methode vergleicht nur die Schreibweise (nicht die
Aussprache)
'--- Der Vergleich erfolgt mit "="
'--- Text A und Text B werden in Gruppen von je drei nebeneinander
liegenden
'--- Zeichen (Triplets) zerlegt und anschließend jedes Triplet von
Text A
'--- mit jedem von Text B verglichen.
'--- Am Anfang und Ende aus zwei Zeichen mit ¬ zusätzliche Triplets
erstellen.
'--- Text A zB. "test": "¬te", "tes", "est", "st¬"

Gruß
Josef

Nähere Details inklusive offenen Modulcode findest Du unter

http://access.primary.at/downloads.htm

Vortrag "Suche nach Texten oder Nummern mit ähnlicher Schreibweise oder
Aussprache" (24., 25. und 26. Stammtisch) von Josef Syrovatka (ca. 806kB,
Version XP, ppt-Vortrag-Datei und mdb-Beispiel-Datei)

siehe Modul "bas_triplet"

Post by Martin Schneider
Hallo!
Ich habe eine Access-Datenbank mit etwa 2.500 Datensätzen. Wenn ein
neuer Datensatz eingegeben wird, mache ich eine Ähnlichkeitssuche per
Levenshtein Distance über die vorhandenen Daten und biete die Top-Ten
als Auswahl an, um Dubletten zu vermeiden.
Leider ist diese Methode bei langen Strings sehr langsam. Gibt es hier
eine schnellere Alternative?
Danke für Eure Tips.
Gruß,
Martin

[Michel Fouquet]

Hallo Martin,

Post by Martin Schneider
Ich habe eine Access-Datenbank mit etwa 2.500 Datensätzen. Wenn ein
neuer Datensatz eingegeben wird, mache ich eine Ähnlichkeitssuche per
Levenshtein Distance über die vorhandenen Daten und biete die Top-Ten
als Auswahl an, um Dubletten zu vermeiden.
Leider ist diese Methode bei langen Strings sehr langsam. Gibt es hier
eine schnellere Alternative?

unter

http://de.wikipedia.org/wiki/Levenshtein-Distanz

finden sich Verweise auf andere Verfahren wie:

Hamming-Abstand
Jaro-Metrik
Jensen-Shannon-Distanz
Soundex-Verfahren
Phonetische Suche
Pattern Matching
Sequenzalignment

unter

http://www.levenshtein.de/levenshtein_links.htm

finden sich eine Reihe von Links zu Grundlagen von approximativen
String-Abgleichsalgorithmen.

Die Levenshtein-Distanz ist zwar bei großen Datenmengen wohl eher
"langsam", aber das Beispiel der Fa. Exobyte zeigt, dass der Abgleich
auf Basis von 2,5 Mio. Daten unter 10 Millisekunden dauern kann. (Naja,
vielleicht nicht gerade in Access und mit VBA).

mfg,
Michel

[Michel Fouquet]

Post by Martin Schneider
Levenshtein Distance

nicht *ganz* OT, aber für Deine Fragestellung jedenfalls nicht
weiterführend:

The technology behind Google's great results
http://www.google.com/technology/pigeonrank.html

(Auf jeden Fall auch die abschließende Bemerkung des Textes lesen!)

Viel Spaß!
Michel

[Martin Schneider]

Danke für alle Tips.

Gruß,
Martin

[Peter Steimann]

Hallo Martin

Post by Martin Schneider
Hallo!
Ich habe eine Access-Datenbank mit etwa 2.500 Datensätzen. Wenn ein neuer
Datensatz eingegeben wird, mache ich eine Ähnlichkeitssuche per
Levenshtein Distance über die vorhandenen Daten und biete die Top-Ten als
Auswahl an, um Dubletten zu vermeiden.
Leider ist diese Methode bei langen Strings sehr langsam. Gibt es hier
eine schnellere Alternative?

Wie sieht denn der Code aus? Access-Version? Suchfeld indiziert?

[Martin Asal]

Post by Martin Schneider
Leider ist diese Methode bei langen Strings sehr langsam. Gibt es hier
eine schnellere Alternative?

Hi,

schau mal unter http://www.me-asal.de/access/modsndx.htm. Da geht es
zwar um SoundEx, aber die dort beschriebene Methode, den Code mittels
ByteArray zu beschleunigen, dürfte bei Levenshtein genauso funktionieren.

bis denn
***@rtin

[Ralf Mueller]

Hallo Martin,

Martin Schneider <***@illusion-factory.de> schrieb am 06.04.06
zum Thema: Schnelle Ähnlichkeitssuche

Post by Martin Schneider
Ich habe eine Access-Datenbank mit etwa 2.500 Datensätzen. Wenn ein
neuer Datensatz eingegeben wird, mache ich eine Ähnlichkeitssuche per
Levenshtein Distance über die vorhandenen Daten und biete die Top-Ten
als Auswahl an, um Dubletten zu vermeiden.
Leider ist diese Methode bei langen Strings sehr langsam. Gibt es
hier eine schnellere Alternative?

ich verwende eine phonetische Funktion (Phonet) zum Vergleich.
Allerdings speichere ich die phonetische Form gleich in der Datenbank
mit ab; dann ist der Vergleich mit dem Suchstring sehr flott.

Die phonetische Routine stand mal in der c't und ist in C geschrieben.
Ich habe sie dann in eine DLL verpackt.

Gruß
Ralf

[Martin Schneider]

Post by Ralf Mueller
ich verwende eine phonetische Funktion (Phonet) zum Vergleich.
Allerdings speichere ich die phonetische Form gleich in der Datenbank
mit ab; dann ist der Vergleich mit dem Suchstring sehr flott.
Die phonetische Routine stand mal in der c't und ist in C geschrieben.
Ich habe sie dann in eine DLL verpackt.

Hi!

Habe Dein Posting gerade erst gelesen. Stellst Du Deine DLL irgendwo zum
Download bereit?

Danke und Gruß,
Martin

[Ralf Mueller]

Hallo Martin,

Martin Schneider <***@illusion-factory.de> schrieb am 25.04.06
zum Thema: Re: Schnelle Ähnlichkeitssuche

Post by Martin Schneider

Post by Ralf Mueller
Die phonetische Routine stand mal in der c't und ist in C
geschrieben. Ich habe sie dann in eine DLL verpackt.

Habe Dein Posting gerade erst gelesen. Stellst Du Deine DLL irgendwo
zum Download bereit?

Nö. Aber wer will, dem schicke ich sie gerne per mail. Ist ja nicht so
groß.

Gruß
Ralf