Hallo zusammen,
ich bin in Python immer noch recht frisch und frage mich gerade, wie man
Python-typisch die folgende Aufgabe lösen würde: Ich habe eine Liste von
strings:
1
l = ['Wetter', 'Wasser', 'Gucken']
Jetzt will ich eine Liste erzeugen, die aus den unterscheidbaren
Anfangsbuchstaben besteht, also hier:
1
anapher = ['We', 'Wa', 'G']
In C würde ich jetzt in einer Doppelschleife mit strcmp jeden string
gegen jeden String vergleichen, in Matlab ein Array erzeugen und
spaltenweise auf doppelte Einträge prüfen.
Wie wäre die Python-Vorgehensweise?
Viele Grüße
W.T.
Worst case: genauso wie in c, für jedes Paar gemeinsamen Anfang Zeichen
für Zeichen bestimmen O(n^3). Innerer Vergleich kann mit
os.path.commonprefix gemacht werden.
Kleverer: Suffix (prefix) baum aufbauen, Blätter prunen. Das sollte in
O(n*Logn) machbar sein
Florian F. schrieb:> Kleverer: Suffix (prefix) baum aufbauen, Blätter prunen. Das sollte in> O(n*Logn) machbar sein
Meine Liste wird wohl nie 20 Einträge überschreiten. Das klingt für mich
nach overkill.
Ich hab's jetzt so gelöst, aber irgendwie wirkt das auch mich untypisch
für Python:
1
""" Compare two strings the old fashioned way: Return value will be the index
2
of the first mis-matching character or 0 if strings are equal """
3
def strcmp(s1:str, s2:str) -> int:
4
if s1 == s2:
5
return 0
6
7
if len(s2) < len(s1):
8
s1, s2 = s2, s1
9
10
i = 0;
11
for c1, c2 in zip(s1, s2):
12
i += 1
13
if c1 != c2:
14
return i
15
16
17
18
""" Aus einer Liste von Strings diese derart am Ende kürzen, dass die
19
Anfangs-Zeichenketten gerade noch unterscheidbar sind """
Was ist das gewünschte Ergebnis, wenn ein Wort Präfix eines anderen
Wortes ist?
Beispiel:
["Was", "Wasser"]
Ist das Ergebnis dann ["Was"] oder ["Was", "Wass"]?
Abradolf L. schrieb:> Was ist das gewünschte Ergebnis, wenn ein Wort Präfix eines anderen> Wortes ist?
Stimmt. Der Fall ist oben nicht abgedeckt. So passt das besser und
liefert auch das gewünschte Ergebnis:
1
""" Compare two strings the old fashioned way: Return value will be the index
2
of the first mis-matching character or 0 if strings are equal """
3
def strcmp(s1:str, s2:str) -> int:
4
if s1 == s2:
5
return 0
6
7
if len(s2) < len(s1):
8
s1, s2 = s2, s1
9
10
i = 0;
11
for c1, c2 in zip(s1, s2):
12
i += 1
13
if c1 != c2:
14
return i
15
16
return len(s1)+1
17
18
19
20
""" Aus einer Liste von Strings diese derart am Ende kürzen, dass die
21
Anfangs-Zeichenketten gerade noch unterscheidbar sind """
22
def anapher(s:list) -> list:
23
s = s.copy()
24
n = len(s)
25
idx = [0] * n
26
for i in range(n):
27
for j in range(n):
28
if i != j:
29
idx[i] = max(idx[i], strcmp(s[i], s[j]))
30
31
for i in range(n):
32
# Funktioniert nur, weil auf Indices out of range zugegriffen werden kann:
Walter T. schrieb:> Stimmt. Der Fall ist oben nicht abgedeckt.
Jetzt noch die Preisfrage: doppelte Wörter erlaubt oder nicht?
["Sahne","Milch","Fisch","Milch"] = ?
Abradolf L. schrieb:> Jetzt noch die Preisfrage: doppelte Wörter erlaubt oder nicht?
Für den Anwendungsfall nicht.
Do you really want to format drive C ?: _Y_es|_Y_es
Sehr gut. Zweimal eine Abwertung meiner Quelltexte. Ich nehme an, daß
das daran liegt, daß hier jemand gerade eine viel bessere Lösung im Kopf
hat, aber nicht besonders schnell tippen kann.
Walter T. schrieb:> In C würde ich jetzt in einer Doppelschleife mit> strcmp jeden string gegen jeden String vergleichen,> in Matlab ein Array erzeugen und spaltenweise auf> doppelte Einträge prüfen.>> Wie wäre die Python-Vorgehensweise?
Keine Ahnung.
Ich würde aber erstmal einen Algorithmus entwerfen
und nicht gleich ein Programm.
Beispielsweise kommt mir die Idee lukrativ vor, die
Liste erstmal zu sortieren und vorrangig die String-
distanz jedes Elementes zu Vorgänger und Nachfolger
zu betrachten.
Walter T. schrieb:> Stimmt, das sieht wirklich sehr pythonisch aus. Danke für die Anregung!
Nur die Laufzeit (falls relevant) ist absolut grausam.
Egon D. schrieb:> Beispielsweise kommt mir die Idee lukrativ vor, die> Liste erstmal zu sortieren und vorrangig die String-> distanz jedes Elementes zu Vorgänger und Nachfolger> zu betrachten.
Von welcher Distanz sprichst du? Levenshtein?
Weiter oben wurde die richtige Spur schon erwähnt wenns
ressourcensparend sein soll: Ein Trie.
Abradolf L. schrieb:> Walter T. schrieb:>> Stimmt, das sieht wirklich sehr pythonisch aus. Danke>> für die Anregung!>> Nur die Laufzeit (falls relevant) ist absolut grausam.
Naja, bei Walters Vorschlägen konnte auch ich als
Nicht-Pythonier ungefähr raten, was abgeht -- Fabians
Programm dagegen ist in einer hermetisch verschlossenen
Geheimsprache geschrieben. Ich hoffe, das ist nicht das
wesentliche Ziel einer "pythonischen" Formulierung...
> Egon D. schrieb:>> Beispielsweise kommt mir die Idee lukrativ vor, die>> Liste erstmal zu sortieren und vorrangig die String->> distanz jedes Elementes zu Vorgänger und Nachfolger>> zu betrachten.>> Von welcher Distanz sprichst du? Levenshtein?
Weiss nicht... nein... wohl nicht.
Man kann die Strings als gebrochene Zahlen zwischen 0
und 1 (in einem passenden Zahlensystem) auffassen; die
lexikographische Sortierung der Strings entspricht einer
Sortierung der Zahlen nach der Größe. Die "Distanz",
die ich oben meinte, ist in diesem Bild einfach die
Differenz der Zahlen.
Je kleiner diese Differenz ist, desto länger muss das
eindeutige Präfix sein. Da die Differenz zwischen
direkten Nachbarn in der sortierten Liste am geringsten
ist, ist das der ungünstigste Fall für das eindeutige
Präfix.
Daher sollte es meiner Meinung nach genügen, die
Differenz jedes Elementes zu Vorgänger und Nachfolger
zu bestimmen und das längere der sich ergebenden
Präfixe zu nehmen.
> Weiter oben wurde die richtige Spur schon erwähnt> wenns ressourcensparend sein soll: Ein Trie.
Das nimmt sich inhaltlich nichts -- allerdings können
Scriptsprachen i.d.R. mit sortierten Listen von Hause
aus umgehen, weswegen ich diese Formulierung bevorzugen
würde.
Egon D. schrieb:> Ich hoffe, das ist nicht das> wesentliche Ziel einer "pythonischen" Formulierung...
Nö, das ist es nicht. Aber er vermeidet so weit wie möglich Indizes
durchzulaufen und Einzelvergleiche. Stattdessen werden lieber blockweise
Listen aufgebaut.
Und soooo merkwürdig sind die Konstrukte nicht. Eigentlich gibt es nur
zwei Zeilen, die man nicht ohne ein Wort Python zu verstehen, sofort
verstehen würde.
fabian schrieb:> sub = check_word[:n + 1]
Hier wird ein Substing von 0:n+1 erzeugt, also quasi sub =
strncpy(check_word, n+1)
fabian schrieb:> unique_sub_found = not any([word.startswith(sub) for word in words
if word != check_word])
Und das ist eigentlich die einzige wirklich Python-typische
Merkwürdigkeit, dass man eine for-Schleife, die ein array [] erzeugt,
einfach ohne das array vorher zu deklarieren in die eckigen Klammern
schreibt. Das ist die ersten beiden Male merkwürdig, danach aber sehr
praktisch, weil es in vielen Fällen Wegwerf-Zwischenvariablen erspart
(und obendrein etwas schneller ist).
Der R- und Matlabber würde so schreiben:
Walter T. schrieb:> Egon D. schrieb:>> Ich hoffe, das ist nicht das>> wesentliche Ziel einer "pythonischen" Formulierung...>> Nö, das ist es nicht. Aber er vermeidet so weit wie> möglich Indizes durchzulaufen und Einzelvergleiche.> Stattdessen werden lieber blockweise Listen aufgebaut.> [...]
Hmm. Wohl insgesamt ein Missverständnis.
Ich hatte Deine ursprüngliche Frage so verstanden, dass
Du einen guten Algorithmus suchst, der Dein Problem löst,
und diesen dann in Python implementieren willst.
Offensichtlich wolltest Du aber lediglich die Implementierung
Deines Algorithmus in Python diskutieren.
Mein Fehler.
Egon D. schrieb:> Weiss nicht... nein... wohl nicht.>> Man kann die Strings als gebrochene Zahlen zwischen 0> und 1 (in einem passenden Zahlensystem) auffassen; die> lexikographische Sortierung der Strings entspricht einer> Sortierung der Zahlen nach der Größe. Die "Distanz",> die ich oben meinte, ist in diesem Bild einfach die> Differenz der Zahlen.>> Je kleiner diese Differenz ist, desto länger muss das> eindeutige Präfix sein. Da die Differenz zwischen> direkten Nachbarn in der sortierten Liste am geringsten> ist, ist das der ungünstigste Fall für das eindeutige> Präfix.> Daher sollte es meiner Meinung nach genügen, die> Differenz jedes Elementes zu Vorgänger und Nachfolger> zu bestimmen und das längere der sich ergebenden> Präfixe zu nehmen.
Kannst du dieses Prosa etwas mit griffigen Definitionen und Beispielen
unterfüttern? So dass man dann auch eine Laufzeitabschätzung machen
kann?
Ich frage aus ehrlichem Interesse, dass man das mal mit einer
Trie-Lösung vergleichen kann.
Abradolf L. schrieb:> Kannst du dieses Prosa etwas mit griffigen> Definitionen und Beispielen unterfüttern?
Leider nicht.
Ich bin darauf gestoßen, als ich neulich in einer
Scriptsprache (Tcl) eine Methode gesucht habe,
Verzeichnisbäume und -teilbäume zu verwalten. In der
Wikipädie hat sich absolut nichts zur Abbildung von
Bäumen auf Listen gefunden; das hat mich gleich
schon frustriert.
> So dass man dann auch eine Laufzeitabschätzung> machen kann?
Naja, die Laufzeitabschätzung an sich ist nicht
schwierig.
Das Sortieren der Schlüsselwortliste geht in n*log(n),
und das einmalige Durchmustern der sortierten Liste,
um jedes Element mit Vorgänger und Nachfolger zu
vergleichen, ist linear in der Länge der Liste. Wenn
man die mittlere Zahl an Zeichen dazunimmt, die zu
vergleichen sind, landet man vermutlich bei m*n.
Woran es bei mir hängt, das ist die Frage nach der
KORREKTHEIT.
Kernpunkt ist letztlich meine Behauptung, dass ein
bestimmtes Element der Liste das längste gemeinsame
Präfix nie mit IRGENDEINEM anderen Element der Liste
haben kann, sondern STETS nur mit dem Vorgänger oder
dem Nachfolger in der sortierten Liste.
Intuitiv ist (mir) klar, dass das so sein muss, aber
ein Beweis fehlt.
Das Ziel ist letztlich, durch die Sortierung die
äußere Schleife im n^3-Algorithmus von Walter
einzusparen.
> Ich frage aus ehrlichem Interesse, dass man das> mal mit einer Trie-Lösung vergleichen kann.
Ja, das wäre interessant.
Egon D. schrieb:> Intuitiv ist (mir) klar, dass das so sein muss, aber> ein Beweis fehlt.
Schreibe den Algorithmus mal konkret auf und zeige die Arbeitsweise an
einem Beispiel und dann kann man weiter sehen. Vielleicht lockt das auch
den Foren-Godfather Yalu hinterm Ofen vor, dann gibt es ganz sicher eine
qualifizierte Aussage.
Abradolf L. schrieb:> Kannst du dieses Prosa etwas mit griffigen> Definitionen und Beispielen unterfüttern?
Ach so... Nachtrag -- Beispiel:
Originalbeitrag von Walter:
1
l = ["Wetter", "Wasser", "Gucken"]
Sortierte Liste:
1
"Gucken"
2
"Wasser"
3
"Wetter"
gemeinsame Präfixe:
1
2
prefix("Gucken","Wasser") = ""
3
prefix("Wasser","Wetter") = "W"
Die eindeutigen Strings müssen logischerweise ein Zeichen
länger sein als die gemeinsamen Präfixe:
1
2
"Gucken" --> "G"
3
"Wasser" --> "Wa"
4
"Wetter" --> "We"
Das ist genau die Liste, die Walter auch ermittelt hatte.
Mehrfache Worte in der Liste erledigen sich von selbst,
wenn man die Liste beim Sortieren "unifiziert". Wenn
bestimmte Worte Präfixe anderer Worte sind, müsste man
die Einträge der sortierten Liste alle um ein angehängtes
Leerzeichen ergänzen, dann wird "Was " von "Wasser"
unterscheidbar.
w = ['Apple', 'Application', 'Character', 'Dwarf', 'Dragon', 'Water', 'Watermelon']
Sortierte Liste (Einträge um Trennzeichen verlängert):
1
2
"Apple "
3
"Application "
4
"Character "
5
"Dwarf "
6
"Dragon "
7
"Water "
8
"Watermelon "
Liste der gemeinsamen Präfixe:
1
2
prefix("Apple ","Application ") = "Appl"
3
prefix("Application ","Character ") = ""
4
prefix("Character ","Dwarf ") = ""
5
prefix("Dwarf ","Dragon ") = "D"
6
prefix("Dragon ","Water ") = ""
7
prefix("Water ","Watermelon ") = "Water"
Liste der eindeutigen Strings:
1
2
"Apple" --> "Apple"
3
"Application" --> "Appli"
4
"Character" --> "C"
5
"Dwarf" --> "Dw"
6
"Dragon" --> "Dr"
7
"Water" --> "Water "
8
"Watermelon" --> "Water"
Das ist (bis auf die Veränderung bei "Water ") die Liste,
die auch Fabian erhalten hat.
Man erkennt auch, dass man immer mit Vorgänger UND Nach-
folger vergleichen und das längere Präfix wählen muss. Daraus,
dass "Application" und "Character" ein leeres gemeinsames
Präfix haben, folgt NICHT "Application --> A", weil ja für
die Unterscheidung von "Application" und "Apple" schon
"Appl"+"i" notwendig ist.
Wobei beim Sortieren exakt gleich viel Vergleiche wie bei der Suche der
Anfangs-Zeichenkette notwendig sind. Wobei die Idee nicht schlecht ist.
Solide Sortieralgorithmen bringt Python von Haus aus mit.
Walter T. schrieb:> Wobei beim Sortieren exakt gleich viel Vergleiche> wie bei der Suche der Anfangs-Zeichenkette notwendig> sind.
Möglich. Ich konnte mangels Python-Kenntnissen halt
nicht erkennen, ob ihr "jeden gegen jeden" vergleicht
oder irgendwie cleverer vorgeht.
> Solide Sortieralgorithmen bringt Python von Haus> aus mit.
Ja, das war die Idee dabei: Sortieren ist fast immer
schon eingebaut (in Tcl ja auch) -- warum also nicht
das Brett an der dünnsten Stelle bohren und nur eine
sortierte Liste durchmustern.
Der Makel ist bis jetzt aber noch, dass der Beweis
der Korrektheit fehlt -- ich GLAUBE zwar daran, aber
ich WEISS es nicht.
Walter T. schrieb:> Ich hab's jetzt so gelöst, aber irgendwie wirkt das auch mich untypisch> für Python:
Ja, da tun einem die Augen weh!
hier mal meine Lösung:
1
l = ["Wetter", "Wasser", "Gucken", "Geh", "Was", "Wellen", "was"]
2
3
#Vergleicht 2 Strings und gibt die Anzahl der gleichen Zeichen zurück
4
5
def strcmp(s1, s2):
6
try:
7
for i in range(len(s1)):
8
#s1 ist an Stelle i anders als s2
9
if s1[i] != s2[i]:
10
return i
11
#s2 ist kürzer als s1 und an allen Stellen gleich wie s1
Egon D. schrieb:> Mehrfache Worte in der Liste erledigen sich von selbst,> wenn man die Liste beim Sortieren "unifiziert". Wenn> bestimmte Worte Präfixe anderer Worte sind, müsste man> die Einträge der sortierten Liste alle um ein angehängtes> Leerzeichen ergänzen, dann wird "Was " von "Wasser"> unterscheidbar.
Das ist eine Krücke und entspricht auch nicht der ursprünglichen
Aufgabe, denn die Lösung von ["Water", "Watermelon"] sollte ja
beispielsweise sein:
["Water", "Waterm"]
Eine Krücke ist es deshalb, weil du die Eingabemenge veränderst und du
den nutzbaren Zeichensatz limitierst.
Bei ["Water", "Water is wet"] bricht der Algo dann auch. Das Ergebnis
sollte dann sein ["Water", "Water "], aber du würdest
["Water ", "Water i"] liefern.
Damit ist die Korrektheit in Bezug auf die Aufgabe widerlegt.
Und mit einem Trie kriegt man auch lineare Laufzeit und
Speicherverbrauch hin.
Aus der Hüfte geschossen wäre mein Trie-Algorithmus wie folgt (werde
morgen nochmal intensiver darüber nachdenken, evtl. mal implementieren
:-) ):
Gegeben sei ein Trie zur Eingabemenge der Wörter. Knoten die ein
Wortende darstellen bezeichne ich im Folgenden als Wortknoten. Die
Wurzel ist für mich das leere Wort.
Im Bild auf Wiki wären das die eingekreisten Knoten:
https://de.wikipedia.org/wiki/Trie
Nun zum Algo:
- Jeder Wortknoten der kein Blatt ist, sind Präfixe von anderen Wörtern
und gehören zur Ergebnismenge
Für jedes Blatt tu folgendes:
- Wiederhole: Geh zum Elterknoten, wenn er kein Wortknoten ist und nur
ein Kind hat und nicht die Wurzel ist.
- Dieser Knoten gehört zur Ergebnismenge
Damit hat man die Ergebnismenge. Im Bild auf Wiki kann mans
nachvollziehen:
[Java, Rad, Rand, Rau, Raum, Rose]
"Rad" und "Rau" sind Nichtblatt-Wortknoten, gehören also zur
Ergebnismenge.
Für "Java" geht man den ganzen Weg bis zum J, da man nur auf
Nichtwortknoten mit einem Kind trifft auf dem Weg nach oben. -> J zur
Ergebnismenge
"Rand" geht man bis "Ran", da "Ra" mehrere Kinder hat. -> "Ran" zur
Ergebnismenge
"Raum" gehört zum Ergebnis, weil der Elter ein Wortknoten ist
"Rose" geht man bis zu "Ro", weil "R" mehrere Kinder hat"
Ergebnis: ["J", "Rad", "Ran", "Rau", "Raum", "Ro"]
Linearer Speicher (wenn man den Trie cleverer als im Bild dargestellt
implementiert, oder den längsten String als konstanten Platzverbrauch
als obere Grenze definiert), Lineare Laufzeit
Karl schrieb:> def anapher(l):> an = []> l.sort()> for i in range(len(l)):> pre = 0> for j in range(len(l)):> if i == j:> pass> else:> pre=max(strcmp(l[i],l[j]),pre)> print(l[i],pre)> an.append(l[i][:pre+1])> return an>>> print(anapher(l))
Hübsch.
Du gehst ja von einer sortierten Liste aus. Meine
(bis jetzt unbewiesene) Behauptung ist, dass man eine
der beiden geschachtelten Schleifen weglassen können
müsste und zum Ausgleich den Vergleich so ähnlich wie
1
2
pre = max(strcmp(l[i-1],l[i]),strcmp(l[i],l[i+1]))
macht. Schleife darf natürlich nur vom zweiten zum
vorletzten Element laufen; das erste und das letzte
müssen separat behandelt werden.
Thread beobachten
Seitenaufteilung abschalten