Algorithmus um zwei Strings auf Gleichheit zu prüfen?

Matt B. OP #3457915
Lesenswert?
• ▲
▼ 
Hallo,

folgende Ausgangssituation:
- Ich bekomme von einem Gerät einen Standort verbal übermittelt
- Im Normalfall beinhaltet der Standort lediglich den Strassennamen und 
die Hausnummer (z.B. "Hauptstrasse 1")
- In manchen Fällen kann es sein, dass in der Zeichenfolge noch weiter 
Informationen stecken, welche manuell ergänzt werden (z.B. "Kreuzung 
Hauptstrasse Seitenstrasse")
- Wegen der manuellen Ergänzungsmöglichkeit können Tippfehler nicht 
ausgeschlossen werden
- Eine genormte Syntax für die manuelle Ergänzung gibt es nicht
- Es kann jedoch davon ausgegangen werden, dass die für den Standort 
wichtigere Strasse zuerst gekannt wird
- Es werden definitiv nur Strassen einer Stadt empfangen, das heisst, es 
gibt keine zwei Strassen mit dem gleichen Namen

Nun soll der empfangene Standort aber von einem Programm automatisch 
verarbeitet werden. Das heisst, ich muss aus dem empfangenen String die 
Strasse auswerten.

Ein kleines Programm habe ich schon geschrieben.
In dem Programm liegen alle Strassen der Stadt in einem Array vor.

Beim Empfang eines Standortes wird zunächst geprüft, ob der empfangene 
Standort (Strassenname ohne Hausnummer) ein Element innerhalb des Arrays 
ist.

Ist dies der Fall kann er so wie er ist weiter verarbeitet werden.

Wird er aber nicht gefunden, führe ich bislang eine Korrelation zwischen 
dem empfangenen Standort-String und jedem Strassennamen aus meinem Array 
durch. Hierfür stelle ich die beiden Zeichenkette gedanklich 
übereinander und prüfe "spaltenweise", wieviele Zeichen übereinstimmen. 
Danach verschiebe ich die beiden Strings zueinder um ein Zeichen und 
prüfe erneut wieviele Zeichen übereinstimmen.

Beispiel:
Empfangener Standort: "Kreisverkehr Hauptstrasse Nebenstrasse"
Korrelationsstring:   "Hauptstrasse"

Die "x" unter den beiden Strings zeigen eine Übereinstimmung der Zeichen 
an.

1. Durchlauf:  "Kreisverkehr Hauptstrasse Nebenstrasse"
               "Hauptstrasse"
                       x


2. Durchlauf:  "Kreisverkehr Hauptstrasse Nebenstrasse"
               " Hauptstrasse"


3. Durchlauf:  "Kreisverkehr Hauptstrasse Nebenstrasse"
               "  Hauptstrasse"

...

14. Durchlauf:  "Kreisverkehr Hauptstrasse Nebenstrasse"
                "             Hauptstrasse"
                             xxxxxxxxxxxxx
...

27. Durchlauf:  "Kreisverkehr Hauptstrasse Nebenstrasse"
                "                          Hauptstrasse"
                             x            x     xxxxxxx

Das Programm funktioniert soweit.
Aber hat jemand vielleicht noch eine andere Idee? Zumal dieses Verfahren 
einiges an Zeit benötigt.

Danke schon mal!

Gruss
matt
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Matt B. OP #3457925
Lesenswert?
• ▲
▼ 
Hallo Kaj,

ich programmiere in Python. Aber das ist eigentlich egal.

Prinzipiell ist die strcmp-Funktion nicht schlecht. Bei meinem Beispiel 
mit dem Kreisverkehr würde diese aber nicht funktionieren.
Man könnte ihn dafür aber an den Leerstellen mit einer Split-Funktion 
aufteilen...
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Malte _. Persönliche Seite #3457936
Lesenswert?
• ▲
▼ 
Wenn du gegebenenfalls Schreibfehlter ausschließen willst, such mal nach 
Vorlesungsfolien zum "Forward Algorithmus". Die Wikipediaartikel sind 
leider viel zu dürftig und gegebenenfalls unverständlich.
Kurz gesagt: Nen haufen Wahrscheinlichkeitsrechnung, welcher Buchstabe 
nach Welchem Buchstaben in deinem Straßenlexikon wie häufig vorkommt.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Kaj Gast #3457987
Lesenswert?
• ▲
▼ 
Stefan Noack schrieb:
> Innerhalb einer Stadt (z.B. Berlin) kann es zwei Straßen mit gleichem
> Namen geben
Jap, kann ich bestaetigen. :D Ist sehr lustig wenn man bei Google Maps 
ne Strasse sucht, aber keine Plz hat, und sich dann wundert, das man 
vorm falschen Haus steht und das auch noch auf der anderen Seite von 
Berlin :D

Zur Sache:
Ich denke Regulaereausdruecke koennten dir helfen. Wenn es Python ist, 
schau mal hier rein: 
http://openbook.galileocomputing.de/python/python_kapitel_15_002.htm#mj0cde82e9966520be22a4f0e68fb21b1b
Ist zwar fuer Python 2.5 aber das ist ziemlich egal.

Gruesse
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Andy P. #3458618
Lesenswert?
• ▲
▼ 
Als Ausgleich gegen Tippfehler (z.b. Goggles "meinten Sie") hilft die 
Levenstein-Distanz. Weil das aber rechenaufwändig ist, such dir ein 
einbindbares C-Modul (gibts das bei Python?). Auch Standardersetzungen 
könnten hilfreich sein:
s/stra[ss?|z|ß]e/str/ oder s/\s+/\s/
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Kaj Gast #3458703
Lesenswert?
• ▲
▼ 
Andy P. schrieb:
> Weil das aber rechenaufwändig ist, such dir ein
> einbindbares C-Modul (gibts das bei Python?)
Ja, man kann C/C++ in Python einbinden und so zum Beispiel die Funktion 
printf(...) aufrufen.
Anders herum Funktioniert es ebenso, also Python in C/C++ einbinden.
Aber fuer Python gibt es selber auch schon sehr viele externe Module, 
z.B. fuer Serielle Kommunikation, 3D-Digramme und und und. Man koennte 
fast sagen: fast alles, was es fuer C/C++ gibt, gibt es auch fuer 
Python.
Ich empfehle die Pythonversion 2.7 oder 3.2 und hoeher. Wobei noch nicht 
alles was es fuer 2.7 gibt, schon nach 3.2 portiert wurde.

Gruesse
Antwort Zitieren Bearbeiten Löschen Beitrag melden
chris Gast #3458804
Lesenswert?
• ▲
▼ 
Hier eine Soundex implementierung.

1
#!/usr/bin/env python

2
# -*- coding: utf-8 -*-

3
def soundex(name, len=4):

4
    """ soundex module conforming to Knuth's algorithm

5
        implementation 2000-12-24 by Gregory Jorgensen

6
        public domain

7
    """

8
 

9
    # digits holds the soundex values for the alphabet

10
    digits = '01230120022455012623010202'

11
    alphabet='ABCDEFGHIJKLMNOPQRSTUVWXYZ'

12
    sndx = ''

13
    fc = ''

14
 

15
    # dictionary of german umlauts

16
    umlauts = {}

17
    umlauts['ü'] = 'u'

18
    umlauts['ä'] = 'a'

19
    umlauts['ö'] = 'o'

20
    umlauts['ß'] = 's'

21
 

22
    # replace any umlaut

23
    for umlaut in umlauts:

24
        name = name.lower().replace(umlaut, umlauts[umlaut])

25
 

26
    # dictionary of german digraphs

27
    digraphs = {}

28
    digraphs['ph'] = 'f'

29
    digraphs['ts'] = 'z'

30
    digraphs['sch'] = 'sh'

31
    #digraphs['dt'] = 't'

32
    #digraphs['ck'] = 'k'

33
 

34
    # replace any similar sounding digraphs

35
    for digraph in digraphs:

36
        name = name.lower().replace(digraph, digraphs[digraph])

37
 

38
    # translate alpha chars in name to soundex digits

39
    for c in name.upper():

40
        if c.isalpha():

41
            if not fc: fc = c   # remember first letter

42
            d = digits[ord(c)-ord('A')]

43
            # duplicate consecutive soundex digits are skipped

44
            if not sndx or (d != sndx[-1]):

45
                sndx += d

46
 

47
    # replace first digit with first alpha character

48
    sndx = fc + sndx[1:]

49
 

50
    # remove all 0s from the soundex code

51
    sndx = sndx.replace('0','')

52
 

53
    # return soundex code padded to len characters

54
    return (sndx + (len * '0'))[:len]
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren