regulärer ausdruck doppelte wörter.

[aldana]

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]

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.

[aldana]

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.

[Joghurt]

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.