Algorithmus um zwei Strings auf Gleichheit zu prüfen?

[Matt B. (mattb)]

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

[Kaj (Gast)]

Ueber welche Sprache reden wir?
In C/C++ ist

strcmp

 das was du suchst.
http://www.cplusplus.com/reference/cstring/strcmp/

Gruesse

[Matt B. (mattb)]

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...

[Sauger (Gast)]

Moin,

http://xorswap.com/questions/1-implement-the-strstr-function-to-find-the-first-occurrence-of-a-substring

MfG

[Helmut L. (helmi1)]

Schau dir in C mal die Funktion strstr an.

http://home.fhtw-berlin.de/~junghans/cref/FUNCTIONS/strstr.html

[Malte _. (malte)]

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.

[Stefan N. (stefan_n)]

Matt B. schrieb:
> - Es werden definitiv nur Strassen einer Stadt empfangen, das heisst, es
> gibt keine zwei Strassen mit dem gleichen Namen

Innerhalb einer Stadt (z.B. Berlin) kann es zwei Straßen mit gleichem 
Namen geben, nur innerhalb eines Postleitzahlenbereichs ist es 
eindeutig.

[Seano L. (Gast)]

KMP ist dein Freund:
http://de.wikipedia.org/wiki/Knuth-Morris-Pratt-Algorithmus

Und weil heute Weihnachten ist gleich einen Sack voller anderer Algos:
http://de.wikipedia.org/wiki/String-Matching-Algorithmus#Weitere_Algorithmen

[Kaj (Gast)]

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

[Andy P. (bakaroo)]

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/

[Kaj (Gast)]

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

[Kaj (Gast)]

Hier nochmal 3 Links zu Levenshtein in Python:
https://pypi.python.org/pypi/python-Levenshtein/
http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance
http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python

Gruesse

[chris (Gast)]

Hier eine Soundex implementierung.

#!/usr/bin/env python
# -*- coding: utf-8 -*-
def soundex(name, len=4):
    """ soundex module conforming to Knuth's algorithm
        implementation 2000-12-24 by Gregory Jorgensen
        public domain
    """
 
    # digits holds the soundex values for the alphabet
    digits = '01230120022455012623010202'
    alphabet='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    sndx = ''
    fc = ''
 
    # dictionary of german umlauts
    umlauts = {}
    umlauts['ü'] = 'u'
    umlauts['ä'] = 'a'
    umlauts['ö'] = 'o'
    umlauts['ß'] = 's'
 
    # replace any umlaut
    for umlaut in umlauts:
        name = name.lower().replace(umlaut, umlauts[umlaut])
 
    # dictionary of german digraphs
    digraphs = {}
    digraphs['ph'] = 'f'
    digraphs['ts'] = 'z'
    digraphs['sch'] = 'sh'
    #digraphs['dt'] = 't'
    #digraphs['ck'] = 'k'
 
    # replace any similar sounding digraphs
    for digraph in digraphs:
        name = name.lower().replace(digraph, digraphs[digraph])
 
    # translate alpha chars in name to soundex digits
    for c in name.upper():
        if c.isalpha():
            if not fc: fc = c   # remember first letter
            d = digits[ord(c)-ord('A')]
            # duplicate consecutive soundex digits are skipped
            if not sndx or (d != sndx[-1]):
                sndx += d
 
    # replace first digit with first alpha character
    sndx = fc + sndx[1:]
 
    # remove all 0s from the soundex code
    sndx = sndx.replace('0','')
 
    # return soundex code padded to len characters
    return (sndx + (len * '0'))[:len]