regulärer ausdruck doppelte wörter.

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
aldana
User
Beiträge: 12
Registriert: Donnerstag 20. April 2006, 16:29

regulärer ausdruck doppelte wörter.

Beitragvon aldana » Donnerstag 20. April 2006, 18:20

hi,
habe folgenden regulären ausdruck (mit dem ich alle doppelten wörter case insensitive in einem text suchen will). pro zeile existiert ein wort. wörter stehen am zeilenanfang.

folgender ausdruck funktioniert teilweise:
doppeltesWort=re.compile(r'^(\w+)$.*?^\1',re.DOTALL|re.M|re.I)

aber es werden wörter ausgegeben (-> groups(1)), die als wortanfang existieren. z.B.: 'zw' zu 'zwingen'

deswegen folgender ausdruck, um die gesamte zeile zu matchen:
doppeltesWort=re.compile(r'^(\w+)$.*?^\1$',re.DOTALL|re.M|re.I)

jetzt werden über groups(1) allerdings fast keine wörter mehr ausgegeben.

was ist am letzten ausdruck falsch?

vielen dank!
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Beitragvon modelnine » Donnerstag 20. April 2006, 18:26

Das folgende tut:

Code: Alles auswählen

modelnine@phoenix ~ $ python
Python 2.4.2 (#1, Apr  3 2006, 12:10:45)
[GCC 3.4.6 (Gentoo 3.4.6, ssp-3.4.5-1.0, pie-8.7.9)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import re
>>> doppeltesWort=re.compile(r'^(\w+)$(?=.*?^\1$)',re.DOTALL|re.M|re.I)
>>> doppeltesWort.findall(file("test").read())
['dies', 'ist', 'doppeltes', 'Wort']
>>>


Siehe die lookahead-Assertion (?=<zweites auftreten>), da sonst der nächste Match erst nach dem zweiten Auftreten gesucht wird.

PS: Ich finds sehr fraglich ob das wirklich der beste Weg ist um diese Aufgabe zu bewältigen. Reguläre Ausdrücke sind vielleicht toll, aber einem dict/set-basierten Ansatz für dieses hier massiv unterlegen, da sie zum einen genausoviel Speicher, zum anderen aber sehr viel mehr Laufzeit brauchen (da der String nicht einmal, sondern sehr viel häufiger gescannt werden muß, macht insgesamt Laufzeit O(n^2), während der dict/set-Ansatz immer lineare Laufzeit O(n) hat). Der re-Ansatz wäre, wenn in groups(0) nicht der gesamte Match gespeichert werden würde, dem dict-Ansatz in Form von Speicherkonsum überlegen, aber wie gesagt, da Python den gesamten Match als group(0) zurückliefert, ist er es nicht mehr.
--- Heiko.
aldana
User
Beiträge: 12
Registriert: Donnerstag 20. April 2006, 16:29

Beitragvon aldana » Donnerstag 20. April 2006, 18:48

danke, jetzt funktionierts.

ich weiß der aufwand ist O(n^2), allerdings sind die wortlisten (vertretbar) klein, insofern geht das mit der 'performanz' schon in ordnung.

aber du hast recht bei größeren wortlisten sollte auf ein hash verfahren gewechselt werden.
Benutzeravatar
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Beitragvon Joghurt » Donnerstag 20. April 2006, 19:40

aldana hat geschrieben:aber du hast recht bei größeren wortlisten sollte auf ein hash verfahren gewechselt werden.
Sprich:

Code: Alles auswählen

woerter={}
for line in open("foobar","rt"):
  for wort in line.split():
    if wort in woerter:
      print wort
    else:
      woerter[wort] = 1
Oder natürlich Set nutzen.

Wer ist online?

Mitglieder in diesem Forum: __deets__, djevil