Bitte um Tipps

[TEXTiX-X]

Hallo Python-Gemeinde:

ich habe eine spannende Aufgabe bekommen unc ich möchte sicher nicht das ihr sie für mich löst. eher gesagt hab ich mich im net durchgesucht und bitte darum das ihr mir erklärt was für möglichkeiten es gäbe oder ob das so möglich ist wie ich's mir denke:

Meine Aufgabe:
ich habe eine Txt.datei in der etwa eine halbe Million Wörter drinstecken. jetzt soll ich ein programm schreiben, was erstmal nur erkennt ob Texte anderer dateien zum beispiel wörter enthalten die nicht in dieser Txt.datei enthalten sind.

quasi soll das ganz hinterher eine art Rechtschreibprogramm werden. wie bei word so i der art. und das ganze soll hinterher regelreht eine art suchmaschine, so ein web crawler werden.... aber egal denn das liegt noch garnicht direkt an

kann mir jemand hier tipps geben oder evtl. stichwörter wie das möglich ist? denn wenn ich die eine txt.datei öffne und auslese und dann noch eine zweite öffne, in der ein text ist der sagen wir mal korrigiert werden müsste dann stürzt bei mir natürlich python ab, bzw. kann python nicht mehr auf meine wörtersammlung zugreifen

[smilingbandit]

Ich bin zwar auch neu in Python, und weiß daher nicht wie genau Python eine Datei öffnet, aber ein paar Sachen kann ich dir trotzdem sagen:

Eine Datei mit über 500k Wörtern zu öffnen ist suizidal (braucht zu viel Speicher). Vor allem wenn man danach mit Hilfe dieses "Wörterbuchs" eine Datei auf Rechtschreibung überprüft. Da du dir nie sicher sein kannst, wie im Speicher / Stream die Daten angeordnet sind, hast du einen Aufwand von irgendwo O(n)=n^x in der Gegend, um eine korrekte Überprüfung vorzunehmen.

[Zap]

denn wenn ich die eine txt.datei öffne und auslese und dann noch eine zweite öffne, in der ein text ist der sagen wir mal korrigiert werden müsste dann stürzt bei mir natürlich python ab, bzw. kann python nicht mehr auf meine wörtersammlung zugreifen

Wäre vielleicht nicht schlecht wenn du uns zeigen würdest wie du die beiden Dateien öffnest. Es ist nämlich garnicht natürlich das Python dabei abstürzt. Könnte mir höchstens vorstellen das du riesige Dateien knallhart mit read() einliest und dir den Speicher voll haust....

Zu deiner eigentlichen Frage:
Ich habe diesen Absatz mit deiner Aufgabe noch nicht ganz verstanden, vielleichts liegts an mir aber ich weiss nicht was du vor hast. Und den Absatz mit dem Rechtschreibprogramm/Suchmaschine bla hab ich mal ganz ausgeblendet....

[gerold]

ich habe eine Txt.datei in der etwa eine halbe Million Wörter drinstecken. jetzt soll ich ein programm schreiben, was erstmal nur erkennt ob Texte anderer dateien zum beispiel wörter enthalten die nicht in dieser Txt.datei enthalten sind.
[...]
dann stürzt bei mir natürlich python ab, bzw. kann python nicht mehr auf meine wörtersammlung zugreifen

Hallo TEXTiX-X!

500.000 Wörter mit je 10 Zeichen und ein wenig Overhead:
500.000 * (10 + 4) = 700.000

Das sind nicht einmal 10 MB RAM den du verbrauchen würdest, wenn du die Liste komplett in den Speicher schreibst. Das ist absolut kein Problem für einen Computer der letzen Jahre.

Dass dir hier Python abstürzen soll, ist eher ein Gerücht als eine Tatsache. Das schafft Python locker.

Aber weder die Textdatei noch eine Liste ist für dein Vorhaben geeignet. Du willst ja nicht bei jedem Suchvorgang die komplette Liste durchlaufen. Für so etwas eignet sich ein Dictionary viel besser. Und wenn du nicht alles im Speicher halten möchtest, so dass es auch auf älteren Computern läuft, aber trotzdem schnell ist, dann kannst du "shelve" benutzen.

Shelve verhält sich ähnlich wie ein Dictionary, hält die Daten aber im Datesystem. Schön indiziert und schnell.

Ich rate dir dringend dazu, dich genau über dieses Thema zu informieren. --> http://www.python-forum.de/topic-6157.html

Shelve ist sehr schnell, wenn man immer nur nach einem ganzen Wort suchen möchte. Shelve kann aber nichts mit Wortteilen anfangen. In diesem Fall würde eine Datenbank besser skalieren.

mfg
Gerold

[BlackJack]

Ich würde noch gerne den Datentyp `set()` in die Runde werfen.

So eine Wortliste sollte in der Regel in den Speicher passen. `/usr/share/dict/ngerman` hat ca. 300.000 Einträge und ist ca. 4MB gross also 16 MB im Speicher als Unicode-Zeichenketten.

Das Problem muss jetzt also nur noch in kleinere, implementierbare Häppchen aufgeteilt werden. Zum Beispiel stellt sich die Frage wie man Wörter aus Textdateien extrahiert. Sonderzeichen durch Leerzeichen ersetzen und dann `split()`\en oder reguläre Ausdrücke verwenden!?

@gerold: Ich gehe von 4 Bytes pro Zeichen aus, weil es hier um natürlichsprachliche Texte geht und man da besser Unicode verwenden sollte.

[gerold]

Ich würde noch gerne den Datentyp `set()` in die Runde werfen.

Hallo BlackJack!

Jepp! Da hast du recht. Ist mir auch gerade eben eingefallen, als ich ein kleines Beispiel dafür schrieb.

Ist nicht perfekt, aber es demonstriert, dass so etwas mit Python locker machbar ist:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: iso-8859-15 -*-

WORTLISTE_DATEINAME = "wortliste.txt"
## Auszug aus der Textdatei:
#ich
#Hallo
#Welt
#du
#schöne
#Braut
#aus
#dem 
#Jenseits
#Junge

# Wortliste öffnen und alle Wörter in ein Set (=Menge) legen
#
# Da die Datei von oben nach unten durchlaufen wird, ist immer nur die aktuelle
# Zeile im Speicher. Nicht die ganze Textdatei.
f = file(WORTLISTE_DATEINAME, "rU")
try:
    woerter = set()
    for zeile in f:
        zeile = zeile.strip(" \n.()").lower() # Hinweis: strip() funktioniert erst
                                            # seit Python 2.5 auf diese Art.
        if zeile:
            woerter.add(zeile)
finally:
    f.close()

print woerter

# Prüfen ob die Wörter dieses Textes in der Wortliste enthalten sind oder nicht.
text = """
Ich bin ein sehr böser Junge aus dem Jenseits.
Das ist schön.
"""

for zeile in text.splitlines():
    for wort in zeile.split():
        wort = wort.strip(" \n.()").lower()
        if wort in woerter:
            print "%s: OK" % wort
        else:
            print "%s: Nicht in Wortliste" % wort


# Das lässt sich natürlich noch bis ins Unendliche optimieren. Es soll nur ein
# kleines Beispiel sein.

@gerold: Ich gehe von 4 Bytes pro Zeichen aus, weil es hier um natürlichsprachliche Texte geht und man da besser Unicode verwenden sollte.

Ich weiß es nicht. :K Der Ressourcenverbrauch ist damit höher. Andererseits wäre die Verwendung von Unicode in diesem Fall absolut ideal.

mfg
Gerold

[TEXTiX-X]

Hui danke für die schnellen Antworten:
also:

@smilingbandit: Ich weiß das es schwachsinn ist das jedesmal auszulesen. hab ich auch verstanden als ich das einmal hab durchlaufen lassen. ich weiß auch woran es lag das bei mir python abgestürzt ist. einmal gleiche variable benutzt. das öffnen beider dateien hat sich jetzt denk ich erledigt. da ich das nun so hab das er's macht. man kann die daten ja zum beispiel anordnen, damit sind sie richtig angeordnet. worauf ich aber eigentlich ziele ist das man das irgendwie mit einem speicher ablaufen lässt, das regelrecht der anfang eines jeden wortes des "zu durchsuchenden" Textes, wörter mit anderem anfang ausschließt.

@Zap: Bespiel: ich habe ein Programm mit einer Art Bibliothek an deutschen korrekt geschriebenen wörtern. Jetzt bringst du mir einen text und möchtest überprüfen ob jedes Wort darin richtig geschrieben ist, oder ob sich Rechtschreibfehler eingeschlichen haben. Mein programm soll dann deinen Text extern nach leerzeichen splitten (das heißt jedes wort wird einzeln gesetzt. dann wird überprüft ob sich in der Bibliothek dieses Wort so geschrieben befindet. ist das nicht der fall kann man's dann ändern. ist es drin; ist's ja super.

@gerold: danke danke du hast mein Problem denke ich verstanden. werde mich mal da durchlesen. ich hatte im netz einfach nicht gewusst was man da machen kann, kein schlüsselwort gekannt was vielleicht das tut was ich möchte.... bin weiterhin für weitere tipps empfänglich^^..

Danke schön für die Mühe liebe Python-gemeinde

[TEXTiX-X]

@ blackjack: jau super. also ich habe jetzt das so geamach das der text der überprüft werden soll, nach leerzeichen aufgeteilt wird und das sonderzeichen in leerzeichen gewandelt werden. dies wird dann in eine andere sicherungstext datei regelrecht schonmal geschrieben. in 1 wort pro zeile.

@gerold: danke ich schau mir dein beispiel mal an.... die ganzen befehle die man so in den paar tagen lernt werden immer mehr^^

[TEXTiX-X]

Also ich habe jetzt hinbekommen:

das der text aufgeteilt wird, das die wörter gesplittet werden, und einzeln in eine weiteren textdatei zwischengespeichert werden. Jetzt muss ich mit der wörtersammlung etwas amchen können. jetzt spuckt er mir hier leider nur wieder nen fehler aus -.-

Code: Alles auswählen

# -*- coding: cp1252 -*-
#Python Aufgabe 2
#Woerter in Liste einlesen, sortiern, Satzzeichen und doppelte Woerter eliminieren

import shelve


file = open("story.txt", "r")
lines = file.readlines()
file.close()

wordList = [open('vollform.txt', 'r')]
lastword = ""

for line in lines:
	words = line.split()
	for word in words:
		word = word.replace('.', '')
		word = word.replace('"', '')
		word = word.replace('!', '')
		word = word.replace('?', '')
		word = word.replace('---', '')
		word = word.replace(',', '')
		word = word.replace('“', '')
		word = word.replace('”', '')
		
		word = word.lstrip()
		wordList.append(word)

wordList.sort()
file = open("story2.txt", 'w')

for word in wordList:
		if (word != lastword):
			file.write(word + "\n")
			lastword = word
file.close()
	
file = open("story2.txt", 'r')
print file.read()
file.close()

[BlackJack]

Wenn ich mal raten müsste was für eine Fehlermeldung es ist, dann würde ich auf die Schleife ab Zeile 33 tippen, die nicht damit klarkommt, dass das erste "Wort" ein offenes Dateiobjekt ist, das Du in Zeile 12 in die Liste steckst. Was sollte das denn!?

Klammern um Bedingungen bei ``if`` sind nicht nötig.

Und hier bietet sich statt einer Liste auch schon ein `set()` an um Doubletten auszufiltern.

Das entfernen der Sonderzeichen ist auch nicht so gut gelöst. Nimm mal den Text 'Er sagte "Hallo"'. Das letzte Wort nach dem splitten ist '"Hallo"'. Dann werden die Anführungszeichen durch Leerzeichen ersetzt und das erste Leerzeichen entfernt, bleibt das Wort 'Hallo '. Man beachte das Leerzeichen am Ende. Wenn der Text über eine Programmiersprache geht und so etwas wie 'os.path.exists()` im Text steht, dann bekommt man sogar ein Wort das mittendrin Leerzeichen hat. Besser wäre es, die Sonderzeichen *vor* dem Splitten zu ersetzen.

Und Du solltest den ganzen Code in Funktionen verschwinden lassen. Mit `lastword` hast Du schon den Anfang von sehr unübersichtlichem Quelltext gemacht, weil der Name recht früh definiert, aber erst viel später benutzt wird. Ab Zeile 33 hab ich mich erst mal gefragt wo `lastword` denn herkommt.

[TEXTiX-X]

also ich habe das jetzt so gemacht:

Code: Alles auswählen

# -*- coding: cp1252 -*-

def readWordlist(filename):
    words = set()
    for line in open(filename, "r"):
        words.update(set([w for w in line.strip().split()]))
    return words

def main():
    wordList = readWordlist("vollform.txt")
    for line in open("story.txt", "r"):
        words = line.strip() \
                    .replace('.', '') \
                    .replace('"', '') \
                    .replace('!', '') \
                    .replace('?', '') \
                    .replace('---', '') \
                    .replace(',', '') \
                    .replace('“', '') \
                    .replace('”', '') \
                    .replace("'", '' ) \
                    .split()
        for w in words:
            if w in wordList:
                print w + " is in wordList\n"
            else:
                print w + " is not in wordList\n"

if __name__ == "__main__":
    main()

Die sache mit den sonderzeichen find ich ein bisschen kompliziert wie BlackJack es schon sagte. Habt ihr noch verbesserungsvorschläge?

[BlackJack]

`readWordList()` und `wordList` passen nicht so recht zu dem `set()`. Ich würde den Typ gar nicht im Namen erwähnen und es einfach `read_words()` und `words` oder `reference_words` nennen.

Beim Extrahieren der Worte würde ich den umgekehrten Weg gehen: Nicht ausfiltern was man nicht haben will, sondern gezielt die Worte mit einem regulären Ausdruck (Modul `re`) herausholen. So gibt's immer noch zig Sonderzeichen, die man eigentlich nicht als Worte haben möchte. Zum Beispiel '10%' oder das '&' in 'Smith & Wesson' und 'Es gibt auch keinen § im Duden, der das Semikolon (;) (in *Klammern*) in Texten verbietet'. Nur um mal ein paar Beispiele zu geben. Wenn man dann noch beliebige Unicode-Texte zulässt gibt's echt *Unmengen* an Zeichen die nicht zu Worten gehören. Im ersten Beitrag hast Du web crawler erwähnt: Da muss also schon mit allen möglichen Unicode-Zeichen rechnen.

[veers]

UTF-8 würde doch reichen, und das braucht meist weniger als 4 Byte pro Zeichen.

[keppla]

UTF-8 würde doch reichen, und das braucht meist weniger als 4 Byte pro Zeichen.

Kommt drauf an, wo. Ein Unicodestring hat, in python nach Aussen kein Encoding, implementiert ist er afaik aber als utf-32, will heissen: u'x' hätte eine "Nutzlast" von 4 Bytes im speicher.
Aber du hast recht, dass das resultat von u'x'.encode('utf-8') nur 1 Byte Nutzlast hat.

[BlackJack]

Die Frage ist, ob die Speicherersparnis den Aufwand lohnt, sich beim Programmieren überlegen zu müssen wo man hin- und herkodiert.

Und in Python 3.0 sind sowieso alle Zeichenketten Unicode-Zeichenketten.

[Leonidas]

implementiert ist er afaik aber als utf-32, will heissen: u'x' hätte eine "Nutzlast" von 4 Bytes im speicher.

Es gibt sowohl UCS2 als auch UCS4-Versionen von Python...

[keppla]

implementiert ist er afaik aber als utf-32, will heissen: u'x' hätte eine "Nutzlast" von 4 Bytes im speicher.

Es gibt sowohl UCS2 als auch UCS4-Versionen von Python...

Was ich eigentlich sagen wollte, war, dass man über unicodestrings keine annahmen Treffen sollte, die über länge und inhalt hinausgehen. Das intern verwendete encoding ist afaik nicht ermittelbar (ist auch gut so), und es kann eben auch mal utf32 sein.
Imho sollte man sich über sowas keine Gedanken machen (Zustimmung zu BlackJacks Post).

[Leonidas]

Das intern verwendete encoding ist afaik nicht ermittelbar (ist auch gut so), und es kann eben auch mal utf32 sein.

Direkt nicht, indirekt schon. Habe aber gerade keine UCS2-Version von Python zur Hand um das zu prüfen.

Imho sollte man sich über sowas keine Gedanken machen (Zustimmung zu BlackJacks Post).

Von mir auch Zustimmung.

[TEXTiX-X]

Kann mir einer helfen indem er mir vielleicht zeigt wie man bei meinem code alles sequentiell einlesen und abfragen kann?

Ich habe eine wörterbuch datei. da sind regelrecht richtige wörter drin. so um die 500000.

jetzt hab ich eine datei mit sätzen. eine normale text datei mit ca. 11 mb sätze.

das ganze dauert schon im moment eine lange zeit wenn ich das mit diesem code mache:

Code: Alles auswählen

# -*- coding: cp1252 -*-
import time

def readWordlist(filename):
    words = set()
    for line in open(filename, "r"):
        words.update(set([w for w in line.strip().split()]))
    return words

def main():
    start = time.time()
    wordList = readWordlist("vollform.txt")
    for line in open("sentences.txt", "r"):
        words = line.strip() \
                    .replace('.', '') \
                    .replace('"', '') \
                    .replace('!', '') \
                    .replace('?', '') \
                    .replace('---', '') \
                    .replace(',', '') \
                    .replace('“', '') \
                    .replace('”', '') \
                    .replace("'", '' ) \
                    .split()
        for w in words:
            f = open("words.txt", "w")
            g = open("wordsinvollform.txt", "w")
            if w in wordList:
                g.write(w)
            else:
                f.write(w)
                
    print time.time() - start, "s"

    print f

if __name__ == "__main__":
    main()

das ganze muss ja irgendwie praktischer berbeitet werden können das das schneller und besser geht.

p.s.: ja ich weiß das mit den sonderzeichen ist nicht gerade ideal gelöst. aber ich hab auch keine ahnung wie ich da erstmal alle sonderzeichen einlese die's gibt... noch nix im net gefunden.. *schäm, ich noob*

[TEXTiX-X]

Okay ich hab's herausgefunden.. das ganze läuft jetzt nicht mehr allzu langsam.

allerdings will man ja das ding so genau wie möglich machen.... jetzt hab ich natürlich noch ein paar sonderzeichen hinzugefügt die durch leerzeichen ersetzt werden, aber je mehr sonderzeichen ich da natürlich rein mache desto länger dauert das.

also theoretisch brauch der jetzt 45 sek für einen durchlauf:

kann mir jemand erklären wie genau ich das ganze schneller machen kann und trotzdem noch genau bin?
ich weiß das es schneller geht.... aber nicht wie-.-

Code: Alles auswählen

# -*- coding: cp1252 -*-
import time

def readWordlist(filename):
    words = set()
    for line in open(filename, "r"):
        words.update(set([w for w in line.strip().split()]))
    return words

def main():
    start = time.time()
    wordList = readWordlist("vollform.txt")
    data = readWordlist("sentences.txt")
    #positiv = ["J" , "j", "y", "yes", "jap", "Y", "Yes", "Jo"] (für erweiterung)
    #negativ = ["nein","ne","Nein","Ne","noe","Noe","n","N","nE","nope"] (für erweiterung)
    for line in data:
        words = line.strip() \
                    .replace('ue', 'ü') \
                    .replace('oe', 'ö') \
                    .replace('ae', 'ä') \
                    .replace('Ae', 'Ä') \
                    .replace('Oe', 'Ö') \
                    .replace('Ue', 'Ü') \
                    .replace('.', '') \
                    .replace('"', '') \
                    .replace('!', '') \
                    .replace('?', '') \
                    .replace('-', '') \
                    .replace(',', '') \
                    .replace('“', '') \
                    .replace('”', '') \
                    .replace('_', '') \
                    .replace(';', '') \
                    .replace('(', '') \
                    .replace(')', '') \
                    .replace('[', '') \
                    .replace(']', '') \
                    .replace('}', '') \
                    .replace('=', '') \
                    .replace('{', '') \
                    .replace(':', '') \
                    .replace("'", '' ) \
                    .replace("1", '' ) \
                    .replace("2", '' ) \
                    .replace("3", '' ) \
                    .replace("4", '' ) \
                    .replace("5", '' ) \
                    .replace("6", '' ) \
                    .replace("7", '' ) \
                    .replace("8", '' ) \
                    .replace("9", '' ) \
                    .replace("0", '' ) \
                    .split()
        for w in words:
            f = open("wordsnotinvollform.txt", "a")
            g = open("wordsinvollform.txt", "a")
            wl = w + "\n"
            if w in wordList:
                g.writelines(wl)
            else:
                f.writelines(wl)
                
    print time.time() - start, "s"


    f.close()
    g.close()
    

if __name__ == "__main__":
    main()