Überprüfen, ob Buchstaben in einem String in der richtigen Reihenfolge vorkommen

[Jawi]

Hallo zusammen,

ich würde gerne ein Skript schreiben, mit dem ich überprüfen kann, ob eine Abkürzung zu einem Wort passen könnte. Dazu würde ich gerne überprüfen, ob die Buchstaben eines Strings ein einem anderen String in der gleichen Reihenfolge vorkommen.
Mein Problem ist, dass ich nicht weiß, wie ich geschickt mit doppelten Buchstaben umgehen soll ohne mich in einer großen Anzahl von Schleifen zu verlaufen.
Beispiel: Wort 'hallihallo'
'alo' könnte also eine richtige Abkürzung sein, 'ila' jedoch nicht.

Ich wäre sehr dankbar für jegliche Hilfe oder Anregungen!

Schöne Grüße
Jawi

[Sirius3]

Wie würdest Du das Problem mit Papier und Bleistift lösen? Versuche das genau Schritt für Schritt zu beschreiben.

[nezzcarth]

Wenn ich das richtig verstehe, suchst du die längste gemeinsame Teilsequenz (LCS). Dafür gibt es bereits existierende Algorithmen. In deinem Fall könnte es interessant sein, den ersten Buchstaben fest auf die erste Position zu setzen.

[__blackjack__]

@nezzcarth: Wenn man das als LCS ansieht ist das nur der erste Schritt, als zweites wäre dann der Test ob die Abkürzung der LCS entspricht, denn die muss ja komplett enthalten sein. Oder anders: LCS ist ein allgemeineres Problem und vielleicht schon einen Tick zu kompliziert gedacht IMHO.

[nezzcarth]

@__blackjack__:

Ja genau, an so etwas hatte ich gedacht. Wenn man die LCS hat (d.h, ist es ja trivial:

Code: Alles auswählen

In [1]: def lcs(first, second):
   ...:     # …                                                                                                                         

In [2]: def check_abbreviation(word, abbreviation): 
   ...:     # lcs durchführen und mit Abk. vergleichen (2 Zeilen)
   ...:     # …                                                                                                                                                                           

In [3]: check_abbreviation('benevolent dictator for life', 'bdfl')                                                                                                                            
Out[3]: True

In [4]: check_abbreviation('benevolent dictator for life', 'bfdl')                                                                                                                            
Out[4]: False

In [5]: check_abbreviation('et cetera', 'etc')                                                                                                                                                
Out[5]: True

Ich habe das vorgeschlagen, weil man sich da selbst keinen Algorithmus erarbeiten, sondern "nur" einen existenten implementieren muss, oder, wenn man das darf, eine Implementierung übernehmen kann. Aber das kann man als Übung natürlich auch mal machen; besonders kompliziert ist der ja auch nicht.

[__blackjack__]

In QBasic könnte man das so lösen:

Code: Alles auswählen

DECLARE FUNCTION isAbbrv% (a AS STRING, b AS STRING)

DIM s AS STRING
s = "hallihallo"
PRINT isAbbrv("alo", s)
PRINT isAbbrv("ila", s)

FUNCTION isAbbrv% (a AS STRING, b AS STRING)
  DIM i AS INTEGER, j AS INTEGER
  IF LEN(a) = 0 OR LEN(a) > LEN(b) THEN
    isAbbrv = 0
  ELSE
    i = 1
    FOR j = 1 TO LEN(b)
      IF MID$(a, i, 1) = MID$(b, j, 1) THEN
        i = i + 1
        IF i > LEN(a) THEN EXIT FOR
      END IF
    NEXT
    isAbbrv = i > LEN(a)
  END IF
END FUNCTION

[LeSchakal]

Ich würde mir die String-Methode split() genauer anschauen.

Mit

Code: Alles auswählen

string.split(letter, maxsplit=1)

erhältst du eine Liste, die den Teil vor letter sowie den Teil nach letter enthält.
Für den nächsten Buchstaben brauchst du dir nur das zweite Element dieser Liste anzuschauen.
Wenn der Buchstabe nicht vorkommt, enthält die Liste nur ein Element.

[Jawi]

Vielen vielen Dank für die vielen Ideen! Ich hätte leider noch keine Zeit es auszuprobieren, werde es mir aber morgen oder nächste Woche genauer anschauen.
Liebe Grüße
Jawi

[PyFM]

Ich würde das wie folgt machen:

Code: Alles auswählen

def istAbkuerzung (Wort, Abkuerzung):
	istAbk = True
	for i in Abkuerzung:
		if i in Wort:
			Wort = Wort [Wort.index(i)+1:]
		else: istAbk = False
	return istAbk 

Anwendung:

Code: Alles auswählen

>>> istAbkuerzung("hallihallo", "alo")
True
>>> istAbkuerzung("hallihallo", "ila")
False
>>>

Da du scheinbar noch recht neu in Python bist, versuche alles Zeile für Zeile zu verstehen und experimentiere was die einzelnen Zeilen machen. Um sich sowas selber ganz einfach zu erarbeiten, überlege dir immer, was du genau machen willst: Zum Beispiel möchtest du hier, das der zweite Buchstabe hinter dem ersten steht. Also musst du alles inklusive des ersten Prüfbuchstaben "wegschneiden" um sicher zu stellen, das der zweite Buchstabe auch wirklich erst dahinter steht.

[Sirius3]

@PyFM: Variablennamen schreibt man wie Funktionen klein. Benutze keine Abkürzungen, das macht das Lesen nur unnötig schwer. Eingerückt wird mit 4 Leerzeichen pro Ebene, keine Tabs.
`i` ist ein schlechter Name, vor allem, wenn es sich um ein Zeichen handelt.
Das Flag `istAbk` ist gar nicht nötig, da man die Schleife bei False gleich per `return` verlassen kann.

Code: Alles auswählen

def ist_abkuerzung(wort, abkuerzung):
    for zeichen in abkuerzung:
        if zeichen not in wort:
            return False
        wort = wort[wort.index(zeichen) + 1:]
    return True

[LeSchakal]

Oder mit meiner präferierten split-Methode:

Code: Alles auswählen

def is_abbreviation(abbr, string):
    for letter in abbr:
        try:
            string = string.split(letter,1)[1]
        except IndexError:
            return False
    return True

[nezzcarth]

Ein leerer String kann keine Abkürzung haben und keine Abkürzung sein. Außerdem kann eine Abkürzung maximal so lang wie das Wort selbst sein. Diese Fälle/Optimierunge sollten in einer Version, die man ernsthaft verwenden möchte, alle berücksichtigt sein

[Sirius3]

@nezzcarth: bei leerem String hast Du Recht, aber ob eine Optimierung wegen zu langer Abkürzung nötig ist, bezweifle ich.

Code: Alles auswählen

def is_abbreviation(abbreviation, string):
    if not abbreviation:
        return False
    for letter in abbreviation:
        _, found, string = string.partition(letter)
        if not found:
            return False
    return True

oder

Code: Alles auswählen

def is_abbreviation(abbreviation, string):
    if not abbreviation:
        return False
    try:
        index = 0
        for letter in abbreviation:
            index = string.index(letter, index) + 1
    except ValueError:
        return False
    return True

[nezzcarth]

@Sirius3: Die Längenprüfung ist vor allem für pathologische Fälle sinnvoll. Wenn jemand systematisch viele zu lange Abkürzungen da hineingibt (oder zum Beispiel die Abkürzung und das Word vertauscht), macht es schon einen Unterschied, ob die die Funktion das sofort feststellt, oder erst nach ein paar Iterationen.

Ich habe zum Spaß mal alle deutschen Gesetzestitel und die Abkürzungen (as-is, ohne Normalisierungen) in allen (Titel vs Abkürzugen sowie beides kombiniert gegeneinander) durchgetestet und komme auf eine (nicht repräsentative) Zeitersparnis im Bereich 0,2 bis 1,8 Sekunden. Jetzt kann man sich überlegen, ob das die zwei Zeilen mehr wert sind.

[LeSchakal]

@nezzcarth schrieb:

Ein leerer String kann keine Abkürzung haben und keine Abkürzung sein. Außerdem kann eine Abkürzung maximal so lang wie das Wort selbst sein. Diese Fälle/Optimierunge sollten in einer Version, die man ernsthaft verwenden möchte, alle berücksichtigt sein

Funktioniert doch gut:

Code: Alles auswählen

def is_abbreviation(abbr, string):
    for letter in abbr:
        try:
            string = string.split(letter,1)[1]
        except IndexError:
            return False
    return True

Code: Alles auswählen

>>> is_abbreviation('abk', '')
False
>>> is_abbreviation('abkürzung', 'abk')
False
>>>

Und ob ein leerer String keine Abkürzung sein soll oder vielmehr für alles Abkürzung ist, darüber kann man streiten.