text: CT steht für: Computertomographie, medizinisches bildgebendes Verfahren Certificate Transparency, ermöglicht das Überprüfen digitaler Zertifikate in einem Logbuch Call-Transfer, vermittlungstechnisches Leistungsmerkmal Charge-Transfer, Elektronenübertragung innerhalb eines Komplexes, welcher eine intensive Farbigkeit hervorrufen kann, siehe Charge-Transfer-Komplexe Chatter-Treffen, Treffen von Mitgliedern einer Chat-Gemeinschaft an einem bestimmten Ort Centime, eine Unterteilung verschiedener Währungen Chlamydia trachomatis, ein intrazellulär lebendes parasitäres Bakterium Chrysler CT, PKW-Modell aus dem Jahr 1933, siehe Chrysler Royal Codex Tchacos, Sammelhandschrift Computertechnik, befasst sich mit der Verarbeitung von Daten und Informationen mittels digitaler oder analoger Rechnersystemen, siehe Rechnertechnik Containerterminal, Güterumschlagsplatz in Häfen Cordless Telephone, siehe Schnurlostelefon Courtage in Immobilienanzeigen, Provision des Maklers CT Arzneimittel, Hersteller von Generika CT das radio, Radiostation der Ruhr-Universität Bochum Lexus CT, japanisches Automobil Alitalia CityLiner (IATA-Code), italienische Fluggesellschaft Central Time – eine Zeitzone u. a. der USA (UTC%E2%88%926) Kfz-Kennzeichen: Bulgarien: Oblast Stara Sagora Italien: Metropolitanstadt Catania Moldau: Rajon Cantemir Montenegro: Cetinje Norwegen: Romerike in der Provinz Viken Polen: kreisfreie Stadt Toruń Rumänien: Kreis Constanța Schweden: Diplomatenkennzeichen für Panama Türkei: Corps Consulaire (weiße Schrift auf türkisfarbenem Grund) bzw. Diplomatisches Corps (grüne Schrift auf weißem Grund) Vereinigtes Königreich: Swansea Zypern: Anhänger Ortsbezeichnungen: Cape Town, siehe Kapstadt Connecticut, US-amerikanischer Bundesstaat als postalische Abkürzung die postcode area Canterbury (als Anfangsbuchstaben einer Postleitzahl aus dem Vereinigten Königreich) ČT steht für: Česká televize, öffentlich-rechtliches Fernsehen Tschechiens Ct steht für: Celtium, früherer Name für das 72. Element, siehe Hafnium Cent (Währung), hundertste Einheit des Euro oder anderer Währungen Cycle of Threshold, siehe Ct-Wert Ct steht für: Gesamt-Kohlenstoffgehalt bei Bodenproben ct steht für: eine Maßeinheit für die Fadendichte (1 ct = 1 Faden pro Zoll) Metrisches Karat, Einheit für die Masse von Schmucksteinen c. t. steht für: cum tempore, Beginn einer akademischen Veranstaltung 15 min nach der vollen Stunde, siehe Akademische Zeitangabe c’t steht für: c’t, Computerzeitschrift des hannoverischen Verlags Heinz Heise Siehe auch: Abkürzung


source: wikipedia

text: Carl Amery (Pseudonym von Christian Anton Mayer; * 9. April 1922 in München; † 24. Mai 2005 ebenda) war ein deutscher Schriftsteller und Umweltaktivist. Er war Mitglied der Gruppe 47, 1976/77 Vorsitzender im Verband deutscher Schriftsteller (VS) und von 1989 bis 1991 Präsident im PEN-Zentrum Deutschland. Von 1967 bis 1974 war Amery Mitglied der SPD, nachdem er zuvor der GVP angehört hatte. Später war Amery Gründungsmitglied der Partei Die Grünen beim Bundeskongress der Grünen in Karlsruhe am 13. Januar 1980 und Schirmherr der Wasserallianz München. Als Initiator und Mitbegründer war Amery von 1980 bis 1995 Präsident der E.-F.-Schumacher-Gesellschaft für Politische Ökologie (München). Leben und Werk Seine Kindheit verbrachte Carl Amery, Sohn des Kunsthistorikers Anton Mayer-Pfannholz, vorwiegend in Passau und Freising als Schüler des Humanistischen Gymnasiums Passau bzw. des Dom-Gymnasiums – beide Städte sollten ihre Spuren in seinem Werk hinterlassen (z. B. Passau in Der Wettbewerb und Der Untergang der Stadt Passau und Freising in Das Geheimnis der Krypta). Anschließend war Amery Stipendiat des Maximilianeums und studierte Neuphilologie an der Ludwig-Maximilians-Universität München, später dasselbe Fach, dazu Literaturtheorie und -kritik, an der Catholic University of America in Washington, D.C. Im Zweiten Weltkrieg geriet er 1943 in Tunesien in amerikanische Kriegsgefangenschaft und kehrte 1946 nach München zurück, wo er sein unterbrochenes Studium (Sprachen und Literaturwissenschaft) wieder aufnahm. Er begann zu schreiben, zunächst unter seinem leicht amerikanisierten Namen als Chris Mayer, dann wählte er sich als Pseudonym Carl Amery, wobei Amery' ein Anagramm von Mayer ist. Im November 1953 wurde sein Sohn Benedikt geboren. 1954 erschien sein erster Roman Der Wettbewerb. Inzwischen Mitglied der Gruppe 47, begründete er 1958 durch den Roman Die große Deutsche Tour seinen Ruf als Satiriker. Dieser Ruf blieb lange haften. Eine andere Seite seines Arbeitens zeigte er in der 1963 erschienenen kirchenkritischen Schrift Die Kapitulation oder Deutscher Katholizismus heute, gefolgt von Das Ende der Vorsehung. Die gnadenlosen Folgen des Christentums, in dem er dem Christentum Mitschuld an der globalen Umweltzerstörung zuwies. Dies prädestinierte Amery für die Rolle des Vordenkers der politischen Ökologie, die er mit weiteren Schriften wie insbesondere Die ökologische Chance ausfüllte und durch sein persönliches Engagement unterstrich – zunächst in der Anfangsphase bei der Partei Die Grünen, dann 1980 durch die Gründung der unabhängigen E.-F.-Schumacher-Gesellschaft, deren Vorsitzender er bis 1995 war. Von 1967 bis 1971 war Amery Direktor der Münchner Stadtbibliothek, was für ihn eine Publikationspause bedeutete. 1974 schließlich wandte er sich einem dritten Genre zu, der Science-Fiction, was damals für einen der Hochliteratur zugerechneten Autor ein überraschender Schritt war. Beeinflusst war er dabei nicht zuletzt durch Gilbert Keith Chesterton, dessen Science-Fiction-Romane er später in überarbeiteten deutschen Fassungen herausgab. Vor allem drei Romane Amerys gehören in diesen Bereich, nämlich Das Königsprojekt (1974): Der Vatikan unternimmt es, mittels einer von Leonardo da Vinci konstruierten Zeitmaschine die Geschichte zu ändern. Ziel der Congregatio secreta ad purificandos fontes (CSAPF) ist es, durch eine Geschichtsmanipulation die Krone Englands für das Haus Wittelsbach zu erobern. Doch die beiden Monsignori Sbiffio-Trulli und Doensmaker müssen erleben, dass ihre Kalkulationen geschichtlicher Notwendigkeit fehlgehen. Der Untergang der Stadt Passau (1975): Im Vorwort nennt Amery den Roman eine „Fingerübung“, zu deren Ausarbeitung ihn der Roman A Canticle for Leibowitz (deutsch: Lobgesang auf Leibowitz) des amerikanischen SF-Autors Walter M. Miller inspiriert habe. Dementsprechend erscheint der Roman in der SF-Reihe des Heyne Verlags und wird zu Amerys größtem Bucherfolg. Zum Inhalt: Nach der durch eine Seuche ausgelösten globalen Katastrophe kristallisieren sich zwei Gruppen heraus – die eine Gruppe versucht einen Wiederaufbau der Zivilisation (inklusive Elektrizität, Bürokratie und Schickeria), die andere geht zurück zu den Wurzeln der Subsistenzwirtschaft und etabliert eine Kultur auf etwa dem Niveau der Bronzezeit. Der Roman erzählt die Geschichte des sich notwendig ergebenden kulturellen Konflikts. An den Feuern der Leyermark (1979): Auch hier geht es um geschichtliche Notwendigkeit, Zufall oder Schicksal – kurz: „Was wäre gewesen, wenn ...?“. In diesem Fall: Was wäre gewesen, wenn 1866 ein bayrischer Beamter (versehentlich) eine mit Repetiergewehren ausgerüstete amerikanische Freischärlertruppe (der Sezessionskrieg in den USA war eben zu Ende) für den anstehenden Krieg gegen Preußen rekrutiert hätte? Nach der Niederlage der Preußen krempelt der anarchistisch-demokratische Freischärlerhaufen die europäische Mentalität um: Aus den Auseinandersetzungen entsteht die Centraleuropäische Eidgenossenschaft (eine alternative Europäische Union), die anarchistisch-syndikalistisch mit weitgehender Gemeindefreiheit aufgebaut ist und Frankreich und Deutschland ihrer angeblichen Erzfeindschaft entledigt. Zwei weitere mit Fantasy-Elementen durchsetzte Romane Amerys thematisieren bayrische Spiritualität: In Die Wallfahrer (1986) bewegen sich die Protagonisten auf den alten Gnadenort Tuntenhausen zu; und im Geheimnis der Krypta (1990) bildet die Krypta im Freisinger Dom (und dort die sogenannte Bestiensäule) das Zentrum der sich über drei Generationen erstreckenden Handlung, wobei die aus den Feuern der Leyermark (aber auch aus dem Königsprojekt) her bekannte Fragestellung zu einer Wissenschaft der „Sphagistik“ erhoben wird, wie die Geschichte aufgrund geringfügig veränderter Einzelbedingungen hätte ganz anders verlaufen können. Ab 1985 erschienen Amerys gesammelte Werke in Einzelausgaben im Münchner Paul List-Verlag. 2001 erklärte Amery in einem Interview, dass er aus gesundheitlichen Gründen keine weiteren Romane verfassen werde. Carl Amerys Gesundheitszustand verschlechterte sich in den letzten Lebensjahren aufgrund eines Lungenemphysems bis zu seinem Tod zunehmend. Er wurde am 30. Mai 2005 am Münchner Ostfriedhof im engsten Familienkreis beigesetzt. Die Rechte an seinen Publikationen lagen bis zu ihrem Tod 2019 bei seiner Witwe Marijane Mayer. 2007 erschien posthum der Aufsatzband Arbeit an der Zukunft, der das Fragment einer Streitschrift gegen die US-amerikanische Religiöse Rechte enthält, an der Amery bis kurz vor seinem Tod arbeitete. Auszeichnungen und Ehrungen 1973: Ludwig-Thoma-Medaille der Stadt München 1975: Ernst-Hoferichter-Preis 1979: Tukan-Preis 1979: Deutscher Preis für Denkmalschutz, Silberne Halbkugel 1984: Bayerischer Friedenspreis 1985: Kurd-Laßwitz-Preis für die Kurzgeschichte Nur einen Sommer gönnt ihr Gewaltigen 1987: Kurd-Laßwitz-Preis für den Roman Die Wallfahrer 1987: Bundesverdienstkreuz (I. Klasse) 1988: Naturschutzpreis des Bundes Naturschutz in Bayern 1988: Kurd-Laßwitz-Preis für das Hörspiel Das Penthouse-Protokoll 1989: Friedrich-Märker-Preis 1991: Phantastik-Preis der Stadt Wetzlar 1991: Kurd-Laßwitz-Preis für den Roman Das Geheimnis der Krypta 1991: Literaturpreis der Landeshauptstadt München 1996: Deutscher Fantasy-Preis 1997: Wilhelm-Hoegner-Preis Im Jahr 2007 stiftete der Verband deutscher Schriftsteller in Bayern zu seinem Gedächtnis den Carl-Amery-Literaturpreis. Werke Romane und Erzählungen Der Wettbewerb. Roman. Nymphenburger Verlagshandlung, München 1954 Die Große Deutsche Tour. Heiterer Roman. Nymphenburger Verlagshandlung, München 1958; mit einem Nachwort 1986: List, München 1986, ISBN 3-7991-6305-0; Heyne, München 1989, ISBN 3-453-03641-7 Das Königsprojekt. Roman. Piper, München/Zürich 1974, ISBN 3-492-02074-7; dtv, München 1978, ISBN 3-423-01370-2 Galopp mit der Raum-Zeit-Maschine, Rezension von Heinrich Böll. In: Die Zeit, 4. Oktober 1974 Der Untergang der Stadt Passau. Science Fiction-Roman. Heyne, München 1975, ISBN 3-453-30332-6 Rezension von Ulrich Gutmair in fluter, 19. Juli 2006 An den Feuern der Leyermark. Roman. Nymphenburger, München 1979, ISBN 3-485-00369-7; Heyne, München 1981, ISBN 3-453-30738-0 Im Namen Allahs des Allbarmherzigen. In: Peter Wilfert (Hrsg.): Tor zu den Sternen. Goldmann, München 1981, ISBN 3-442-23400-X Nur einen Sommer gönnt Ihr Gewaltigen. In: Science-fiction-Jubiläums-Band. Das Lesebuch. Heyne, München 1985, ISBN 3-453-31112-4 (erhielt den Kurd-Laßwitz-Preis) Die starke Position oder Ganz normale MAMUS. Acht Satiren. List, München 1985, ISBN 3-7991-6247-X; Heyne, München 1990, ISBN 3-453-04196-8 Die Wallfahrer. Roman. Süddeutscher Verlag, München 1986, ISBN 3-7991-6241-0; Heyne, München 1989, ISBN 3-453-03276-4 Das Geheimnis der Krypta. Roman. List, München 1990, ISBN 3-471-77019-4; Heyne, München 1992, ISBN 3-453-05650-7 Hörspiele Ich stehe zur Verfügung. ORF, 1966 Rezension von Jürgen Kolbe. In: Die Zeit, 6. Mai 1966 Finale Rettung Michigan. WDR/BR, 1982 Schirmspringer. Bayerischer Rundfunk, 1984 Das Penthouse-Protokoll. WDR/BR/HR, 1987 Der Untergang der Stadt Passau. BR, 2021 Essays und Streitschriften 1963: Die Kapitulation oder Deutscher Katholizismus heute. Rowohlt, Reinbek 1963 (Platz 1 der Spiegel-Bestsellerliste vom 3. Juli bis zum 8. Oktober 1963) 1964: (Hrsg.): Die Provinz. Kritik einer Lebensform. Nymphenburger Verlagshandlung, München 1964 1967: Fragen an Welt und Kirche. 12 Essays. Rowohlt, Reinbek 1967 1972: Das Ende der Vorsehung. Die gnadenlosen Folgen des Christentums. Rowohlt, Reinbek 1972, ISBN 3-498-00008-X. 1973: Nebenfiguren. In: Walter Jens (Hrsg.): Der barmherzige Samariter. Kreuz, Stuttgart 1973, ISBN 3-7831-0413-0, S. 19–28 1974: mit Jochen Kölsch (Hrsg.): Bayern, ein Rechts-Staat? Das politische Porträt eines deutschen Bundeslandes. Rowohlt, Reinbek 1974, ISBN 3-499-11820-3. 1976: Natur als Politik. Die ökologische Chance des Menschen. Rowohlt, Reinbek 1976, ISBN 3-498-00010-1. 1978: mit Peter Cornelius Mayer-Tasch und Klaus Michael Meyer-Abich: Energiepolitik ohne Basis. Vom bürgerlichen Ungehorsam zur energiepolitischen Wende. Fischer-TB, 1978, ISBN 3-596-24007-7. 1980: Leb wohl, geliebtes Volk der Bayern. Bertelsmann, 1980, ISBN 3-570-02107-6. Goldmann-TB, 1982. Aktualisierte Ausgabe: List, München 1996, ISBN 3-471-77026-7. 1985: Die ökologische Chance. List, München 1985, ISBN 3-7991-6271-2. Das Ende der Vorsehung und Natur als Politik in einem Band, mit einem Nachwort des Autors. Taschenbuchausgabe mit Nachwort 1990: Heyne 1991, ISBN 3-453-04444-4. 1988: Voll tiefen Mitleids. Bayerische Reflexionen zur Kieler Affäre. In: Heinz Ludwig Arnold (Hrsg.): Vom Verlust der Scham und dem allmählichen Verschwinden der Demokratie. Steidl, Göttingen 1988, ISBN 3-88243-091-5, S. 211–216 1988: Das ökologische Problem als Kulturauftrag. BIS, Oldenburg 1988, ISBN 3-8142-1013-1. 1991: Bileams Esel. Konservative Aufsätze. List, München 1991, ISBN 3-471-77021-6. 1994: Die Botschaft des Jahrtausends. Von Leben, Tod und Würde. List, München 1994, ISBN 3-471-77022-4. 1995: Wenn aber das Salz schal geworden ist... Künden die Kirchen auf der Höhe der Zeit? In: Sind die Kirchen am Ende? Pustet, Regensburg 1995, ISBN 3-7917-1455-4. 1998: Hitler als Vorläufer. Auschwitz – der Beginn des 21. Jahrhunderts? Luchterhand, München 1998, ISBN 3-630-87998-5. 2000: Du voll Unendlichkeit. In: Elisabeth Schweeger & Eberhard Witt (Hrsg.): Ach Deutschland! belleville, München 2000, ISBN 3-933510-67-8, S. 39–45 2001: mit Hermann Scheer: Klimawechsel. Von der fossilen zur solaren Kultur. Ein Gespräch mit Christiane Grefe. Kunstmann, München 2001, ISBN 3-88897-266-3. 2002: Global Exit. Die Kirchen und der Totale Markt. Luchterhand, München 2002, ISBN 3-630-88004-5, btb, München 2004, ISBN 3-442-73133-X. 2005: (Hrsg.): Briefe an den Reichtum. Luchterhand, München 2005, ISBN 3-630-87186-0. 2007: Arbeit an der Zukunft. Essays. Hrsg. von Joseph Kiermeier-Debre. Luchterhand, München 2007, ISBN 978-3-630-62123-4. Verschiedenes mit Kurt Kusenberg und Eugen Oker: Zucker und Zimt. ff. Gereimtheiten. Langewiesche-Brandt, Ebenhausen 1972, ISBN 3-7846-0066-2. Marsch, zurück auf die Bäume oder wie wir es besser machen können. Schaffstein, Dortmund 1979, ISBN 3-588-00021-6 (Jugend-Sachbuch). G. K. Chesterton oder der Kampf gegen die Kälte. Kerle, Freiburg/Heidelberg 1981, ISBN 3-600-30082-2. mit Marina Bohlmann: München. dtv, München 1982, ISBN 3-423-03708-3 (Reiseführer). mit Günter Altner, Robert Jungk und Jürgen Schneider: Lebenselemente. Feuer – Wasser – Luft – Erde. Herder, Freiburg/Basel/Wien 1985, ISBN 3-451-20178-X. mit Georg Kürzinger (Fotografien): Bayern. Bucher, München 1993, ISBN 3-7658-0811-3 (Text zu Bildband). Fleuves & turbulences (Strömungen & Wirbel). Zwischenernte eines reichgeschüttelten Reimlebens. Verlag Kuckuck & Straps (des Verlegers und Malers Fritz Gebhardt alias Eugen Oker), München 2000, ISBN 3-935276-00-1. Literatur Heinrich Böll: Nachwort zu Carl Amery „Die Kapitulation“. In: Briefe aus dem Rheinland. Schriften und Reden 1960–1963. München 1985, ISBN 3-423-10602-6, S. 224–227 (siehe auch Bölls Artikel ) Ute Bauer, Olaf Rappold und Thomas Tilsner: Interview mit Carl Amery. In: Wolfgang Jeschke (Hrsg.): Das Science Fiction Magazin # 10. Wilhelm Heyne Verlag München 1983, ISBN 3-453-31048-9, S. 117–136. Hans Werner Richter: Im Etablissement der Schmetterlinge. 21 Portraits aus der Gruppe 47. München 1986 Karl Michael Armer: Die Wallfahrer. In: Wolfgang Jeschke (Hrsg.): Das Science Fiction Jahr 1987 Band 2, Wilhelm Heyne Verlag, München 1987, ISBN 3-453-31365-8, S. 638–640. Joseph Kiermeier-Debre (Hrsg.): Carl Amery – „...ahnen, wie das alles gemeint war“. Ausstellung eines Werkes. List, München/Leipzig 1996, ISBN 3-471-79324-0 Karlheinz Steinmüller: Laudatio auf Carl Améry. Anlässlich der Verleihung des Deutschen Fantasypreises 1996. In: Wolfgang Jeschke (Hrsg.): Das Science Fiction Jahr 1997. Wilhelm Heyne Verlag, München, ISBN 3-453-11896-0, S. 635–641. Joseph Kiermeier-Debre (Hrsg.): Carl Amery: Arbeit an der Zukunft. Essays. Sammlung Luchterhand, München 2007, ISBN 978-3-630-62123-4. Götz Fenske: Begegnungen mit Carl Amery und Herbert Gruhl. In: Naturkonservativ. 2008/2009. Hrsg. von der Herbert-Gruhl-Gesellschaft e. V. Bad Schussenried 2009, ISBN 978-3-87336-904-7, S. 90–110; (Auszug auf naturkonservativ.de) Christoph F. Lorenz: Amery, Carl. In: Lexikon der Science Fiction-Literatur seit 1900. Mit einem Blick auf Osteuropa, herausgegeben von Christoph F. Lorenz, Peter Lang, Frankfurt/Main 2016, ISBN 978-3-631-67236-5, S. 193–198. Bernhard M. Baron: Carl Amery und Tirschenreuth. Eine familiäre Spurensuche. In: Heimat-Landkreis Tirschenreuth. Band 30/2018, Pressath 2018, ISBN 978-3-947247-21-9, S. 139–145. Harald Eggebrecht: Carl Amery ist tot – Der Rebell, Sprachspieler und Aufklärer. In: Süddeutsche Zeitung. 30. Mai 2005 (Nachruf: sueddeutsche.de). Tilman Urbach: Wallfahrt im Gegenwind. In: Neue Zürcher Zeitung. 31. Mai 2005 (Nachruf: nzz.ch). Dirk Knipphals: Engagement ist alles. In: Die Tageszeitung. 1. Juni 2005 (Nachruf: taz.de). Film Die Zeit, die wir noch haben, Carl Amery - ein bayerischer Querdenker, Ein Film von Vera Botterbusch, 45 Min. BR 1991 Hörfunkbeiträge Ein anderer Bayer. Zum 100. Geburtstag von Carl Amery von Bernhard Setzwein Weblinks Kiermeier-Debre, Joseph: Amery, Carl, in: NDB-online. Carl Amery Materialien auf umweltdebatte.de teleakademie: Vortrag aus dem Jahr 1988 aus der Alten Oper in Frankfurt am Main Einzelnachweise Mitglied der Deutschen Akademie für Sprache und Dichtung Autor Übersetzer Literatur (Deutsch) Science-Fiction-Literatur GVP-Mitglied SPD-Mitglied Bündnis-90/Die-Grünen-Mitglied Person (Katholische Universität von Amerika) Verband-deutscher-Schriftsteller-Funktionär Träger des Bundesverdienstkreuzes 1. Klasse Träger des Ernst-Hoferichter-Preises Träger des Kurd-Laßwitz-Preises Schriftsteller (München) Bestsellerautor (Deutschland) Maximilianeer Pseudonym Literatur (20. Jahrhundert) Deutscher Geboren 1922 Gestorben 2005 Mann


text: Chomsky-Hierarchie, gelegentlich Chomsky-Schützenberger-Hierarchie (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger), ist ein Begriff aus der theoretischen Informatik. Sie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die Hierarchiestufen unterscheiden sich darin, wie rigide die Einschränkungen für die Form zulässiger Produktionsregeln auf der jeweiligen Stufe sind; bei Typ-0-Grammatiken sind sie uneingeschränkt, bei höheren Stufen fortschreitend stärker beschränkt. Grammatiken niedrigeren Typs sind erzeugungsmächtiger als die höherer Typen. Eine Sprache, die von einer Grammatik des Typs k erzeugt wird, heißt eine Sprache des Typs k. Neben die Chomsky-Hierarchie der Grammatiken tritt in diesem Sinne eine Chomsky-Hierarchie der Sprachen. Hintergründe Formale Sprachen haben den Vorzug, mathematisch exakt analysiert werden zu können. Formalen Sprachen liegt ein vorgegebenes Alphabet (ein Zeichenvorrat) zugrunde, das häufig mit bezeichnet wird. Beliebig lange, endliche Folgen von Elementen des Alphabets werden als Wörter über dem Alphabet bezeichnet. Mengen solcher Wörter sind schließlich formale Sprachen. Die umfassendste formale Sprache über einem vorgegebenen Alphabet ist unendlich groß; sie enthält sämtliche Wörter, die durch beliebiges Zusammenfügen von Zeichen des Alphabets gebildet werden können. Sie lässt sich durch die Kleenesche Hülle des Alphabets beschreiben, also . Die kleinste formale Sprache enthält gar keine Wörter. Andere formale Sprachen bestehen nur aus wenigen Wörtern und lassen sich somit als endliche Menge notieren; beispielsweise für das Alphabet die Sprache aller Wörter der Länge zwei: . Unendliche Sprachen lassen sich begreiflicherweise nicht durch Aufzählen notieren. Um sie exakt zu beschreiben, ist ein Konzept nötig, das auch unendliche Mengen definieren kann. Hierzu werden im Rahmen der formalen Sprachen vor allem Erzeugungsverfahren benutzt. Geht man von einem vorhandenen Wort über einem Alphabet aus, lassen sich durch Semi-Thue-Systeme Wortmengen spezifizieren, die sich durch beliebig wiederholtes Anwenden von Ersetzungsregeln ergeben. Ersetzungsregeln der Form erlauben, dass in einem Wort, das ein Segment enthält, dieses Segment durch ersetzt wird. Semi-Thue-Systeme geben daher eine Ableitungsrelation zwischen Wörtern formaler Sprachen an: Zwei Wörter stehen in Relation, wenn das eine Wort durch eine Ersetzungsregel vom anderen Wort abgeleitet werden kann. Zur Beschreibung von formalen Sprachen eignen sich formale Grammatiken, ein gegenüber Semi-Thue-Systemen erweitertes und mächtigeres Konzept. Sie unterscheiden sich von Semi-Thue-Systemen darin, dass sie sogenannte Terminalsymbole und Nichtterminalsymbole kennen. Terminalsymbole einer Grammatik sind gerade alle Zeichen ihres Zeichensatzes . Die erste anwendbare Regel geht immer von einem nichtterminalen Startsymbol aus, und das Ergebnis eines Ersetzungsvorgangs gilt nur dann als Wort ihrer formalen Sprache, wenn es keine Nichtterminalsymbole enthält. Das folgende Beispiel beschreibt eine Sprache, mit der sich beliebig lange Summen der Ziffern 1, 2 und 3 ausdrücken lassen. Das dafür angemessene Alphabet ist . Die entsprechenden Terminalsymbole sind unterstrichen dargestellt, Nicht-Terminale kursiv. Die folgenden Zeilen stellen die Regeln dar. Das Startsymbol dieser Sprache ist Summe. Davon ausgehend kann man nun beliebige Regeln nacheinander anwenden, um einen gültigen Ausdruck zu erzeugen: Nicht alle unendlichen Sprachen lassen sich als formale Sprachen mit diesem Erzeugungsprinzip beschreiben, es ist aber kein tauglicheres Konzept bekannt. Ein anderer gängiger Formalismus zur Beschreibung von Sprachen sind Automatenmodelle, vor allem Turingmaschinen. Uneingeschränkte formale Grammatiken und Turingmaschinen sind bei der Beschreibung von formalen Sprachen gleichmächtig, d. h. zu jeder von einer formalen Grammatik erzeugten Sprache gibt es eine Turingmaschine, die genau diese akzeptiert, und umgekehrt. Ebenso wie verschiedene Automatenmodelle definiert wurden, definierte Chomsky in seiner Arbeit verschiedene Grammatiktypen. Durch drei fortlaufend schärfere Einschränkungen an die jeweils darin zulässigen Ersetzungsregeln stellte er eine Hierarchie aus vier Klassen von formalen Grammatiken auf, wodurch die weniger eingeschränkten Klassen die stärker regulierten Klassen jeweils echt umfassen. Das Gleiche gilt für die von den jeweiligen Grammatikklassen beschriebenen Sprachklassen: auch sie bilden eine Hierarchie. Sprachen eingeschränkteren Grammatiktyps sind üblicherweise einfacher algorithmisch zu verarbeiten – um den Preis, weniger ausdrucksmächtig zu sein. Reguläre Ausdrücke, mit denen man etwa Muster für die Suche in Texten definiert, entsprechen zum Beispiel den sehr eingeschränkten Chomsky-Grammatiken des Typs 3 (reguläre Grammatiken) und solche Textsuchen sind effektiv und schnell. Dagegen taugen Grammatiken des Typs 3 wegen ihrer Einfachheit nicht zur Beschreibung von Programmiersprachen, für die man meist weniger eingeschränkte Typ-2-Grammatiken benutzt. Die Hierarchie Die Chomsky-Hierarchie umfasst vier Typen formaler Grammatiken, gezählt von 0 bis 3. Typ 0 umfasst alle formalen Grammatiken überhaupt, also ohne Einschränkung an die Gestalt zulässiger Erzeugungsregeln. Grammatiken des Typs 1 bis Typ 3 sind dann zunehmend stärker eingeschränkt. Allein nach Definition ist eine Grammatik vom Typ 1 auch vom Typ 0, eine Grammatik vom Typ 2 auch vom Typ 1, eine Grammatik vom Typ 3 auch vom Typ 2; die Umkehrungen gelten nicht. Deshalb bilden diese Klassen eine echte Hierarchie. Bei den entsprechenden Sprachklassen zeigen Gegenbeispiele, dass ebenfalls die Umkehrungen nicht gelten, weshalb auch sie eine echte Hierarchie bilden. Chomsky forderte für Typ-1-, Typ-2- und Typ-3-Grammatiken, dass die rechte Seite von Produktionsregeln nicht kürzer als die linke Seite sein darf, was auch das leere Wort auf jeder rechten Seite einer Produktionsregel ausschließt. Heute ist man oft weniger restriktiv; die Definitionen sind oft so gefasst, dass die Hierarchie der Sprachen nicht gestört wird, sie es aber auch Grammatiken des Typs 1 (kontextsensitive Grammatiken) durch eine Ausnahmeregel erlauben, das leere Wort zu erzeugen, und den Typen 2 (kontextfreien Grammatiken) und 3 (regulären Grammatiken) sogar ohne Einschränkung das leere Wort als rechte Seite von Ersetzungsregeln gestatten. Typ-0-Grammatik (allgemeine Chomsky-Grammatik oder Phrasenstrukturgrammatik) Definition Typ-0-Grammatiken werden auch unbeschränkte Grammatiken genannt. Es handelt sich dabei um die Klasse aller formalen Grammatiken der Form , wobei ein Vokabular ist, bestehend aus der disjunkten Vereinigung eines endlichen Alphabets (Terminalsymbole) und einer Menge von Nichtterminalen (Variablen) . Das ausgezeichnete Symbol wird als Startsymbol bezeichnet und ist eine Menge von Produktionsregeln , d. h. auf der linken Seite jeder Produktionsregel steht wenigstens ein Nicht-Terminalsymbol. Für einzelne Regeln schreibt man anstelle von meistens , für die Menge der Regeln mit auf der linken Seite auch . Um die Zugehörigkeit zur Klasse der Typ-0-Grammatiken auszudrücken, schreibt man Von Typ-0-Grammatiken erzeugte Sprachen Jede Typ-0-Grammatik erzeugt eine Sprache, die von einer Turingmaschine akzeptiert werden kann, und umgekehrt existiert für jede Sprache, die von einer Turingmaschine akzeptiert werden kann, eine Typ-0-Grammatik, die diese Sprache erzeugt. Diese Sprachen sind auch bekannt als die rekursiv aufzählbaren Sprachen (oft auch semi-entscheidbare Sprachen genannt), d. h. die zugehörige Turingmaschine akzeptiert jedes Wort, das in der Sprache liegt. Bei einem Wort, das nicht in der Sprache liegt, kann es sein, dass die Turingmaschine nicht terminiert, d. h. keinerlei Auskunft über die Zugehörigkeit des Worts zur Sprache liefert. Man beachte, dass sich diese Menge von Sprachen von der Menge der rekursiven Sprachen (oft auch entscheidbare Sprachen genannt) unterscheidet, welche durch Turingmaschinen entschieden werden können. Typ-1-Grammatik (kontextsensitive Grammatik) Definition Typ-1-Grammatiken werden auch kontextsensitive Grammatiken genannt. Es handelt sich dabei um Typ-0-Grammatiken, bei denen alle Produktionsregeln die Form oder haben, wobei ein Nichtterminal und Wörter bestehend aus Terminalen () und Nichtterminalen () sind. bezeichnet das leere Wort. Die Wörter und können leer sein, aber muss mindestens ein Symbol (also ein Terminal oder ein Nichtterminal) enthalten. Diese Eigenschaft wird Längenbeschränktheit genannt. Als einzige Ausnahme von dieser Forderung lässt man zu, wenn das Startsymbol nirgends auf der rechten Seite einer Produktion auftritt. Damit erreicht man, dass die kontextsensitiven Sprachen auch das oft erwünschte leere Wort enthalten können, das dann aber immer nur in einer einschrittigen Ableitung aus dem Startsymbol selbst entsteht, und ohne für alle anderen Ableitungen die Eigenschaft zu stören, dass in jedem Teilschritt die Satzform länger wird oder gleich lang bleibt. Ist eine Grammatik kontextsensitiv, so schreibt man . Anders als bei kontextfreien Grammatiken können auf der linken Seite der Produktionen kontextsensitiver Grammatiken durchaus statt einzelner Symbole ganze Symbolfolgen stehen, sofern sie mindestens ein Nichtterminalsymbol enthalten. Von Typ-1-Grammatiken erzeugte Sprachen Die kontextsensitiven Grammatiken erzeugen genau die kontextsensitiven Sprachen. Das heißt: Jede Typ-1-Grammatik erzeugt eine kontextsensitive Sprache und zu jeder kontextsensitiven Sprache existiert eine Typ-1-Grammatik, die diese erzeugt. Die kontextsensitiven Sprachen sind genau die Sprachen, die von einer nichtdeterministischen, linear beschränkten Turingmaschine erkannt werden können; das heißt von einer nichtdeterministischen Turingmaschine, deren Band linear durch die Länge der Eingabe beschränkt ist (das bedeutet, es gibt eine konstante Zahl , sodass das Band der Turingmaschine höchstens Felder besitzt, wobei die Länge des Eingabewortes ist). Monotone Grammatiken Einige Autoren bezeichnen eine Grammatik schon dann als kontextsensitiv, wenn bis auf die Ausnahme (s. o.) alle Produktionsregeln nur die Bedingung erfüllen, d. h., dass die rechte Seite einer solchen Produktion nicht kürzer als deren linke Seite ist. Häufiger findet man dafür jedoch den Begriff der monotonen Grammatik oder der nichtverkürzenden Grammatik. Es erweist sich, dass die monotonen Grammatiken genau wieder die kontextsensitiven Sprachen erzeugen, weshalb die beiden Klassen von Grammatiken als äquivalent betrachtet werden und manche Autoren nur die eine oder die andere Grammatikklasse überhaupt behandeln. Aber nicht jede monotone Ersetzungsregel ist auch eine kontextsensitive, deshalb ist auch nicht jede monotone Grammatik eine kontextsensitive. Typ-2-Grammatik (kontextfreie Grammatik) Definition Typ-2-Grammatiken werden auch kontextfreie Grammatiken genannt. Es sind Grammatiken, für die gelten muss: In jeder Regel der Grammatik muss also auf der linken Seite genau ein nicht-terminales Symbol stehen und auf der rechten Seite kann eine beliebige nicht-leere Folge von terminalen und nichtterminalen Symbolen aus dem gesamten Vokabular stehen. Außerdem kann wie bei Typ-1-Grammatiken die Ausnahmeregel zugelassen werden, wenn auf keiner rechten Seite einer Regel vorkommt. Man schreibt Kontextfreie Grammatiken werden oft so definiert, dass die rechte Seite auch leer sein darf, also . Solche Grammatiken erfüllen nicht mehr alle Eigenschaften von Typ-2-Grammatiken und stünden nicht mehr in der von Chomsky definierten Hierarchie. Sie erfüllen aber die Bedingungen von monotonen Grammatiken. Von Typ-2-Grammatiken erzeugte Sprachen Kontextfreie Grammatiken (mit -Ausnahmeregel) erzeugen genau die kontextfreien Sprachen, jede Typ-2-Grammatik erzeugt also eine kontextfreie Sprache und zu jeder kontextfreien Sprache existiert eine Typ-2-Grammatik, die diese erzeugt. Die kontextfreien Sprachen sind genau die Sprachen, die von einem nichtdeterministischen Kellerautomaten (NPDA) erkannt werden können. Eine Teilmenge dieser Sprachen bildet die theoretische Basis für die Syntax der meisten Programmiersprachen. Siehe auch: Backus-Naur-Form (BNF) / Erweiterte Backus-Naur-Form (EBNF): ein anderes, äquivalentes Schema der Bezeichnungsweisen. Typ-3-Grammatik (reguläre Grammatik) Definition Typ-3-Grammatiken werden auch reguläre Grammatiken genannt. Es handelt sich um Typ-2-Grammatiken, bei denen auf der rechten Seite von Produktionen genau ein Terminalsymbol auftreten darf und maximal ein weiteres Nichtterminalsymbol. Die erlaubte Stellung solcher Nichtterminalsymbole muss außerdem über alle Produktionen hinweg einheitlich immer vor oder immer hinter dem Terminalsymbol sein, je nachdem spricht man auch genauer von linksregulären und rechtsregulären Grammatiken. Sie stimmen mit den links- beziehungsweise rechts-linearen Grammatiken überein, wohingegen lineare Grammatiken nicht den regulären Grammatiken entsprechen. Für linksreguläre Typ-3-Grammatiken muss also die Bedingung erfüllt sein, dass . Sie dürfen also nur linksreguläre Produktionen (Nichtterminalsymbol auf der rechten Seite in Vorderstellung) enthalten. Üblicherweise gestattet man für reguläre Grammatiken, wie auch für kontextfreie Grammatiken Regeln mit leerer rechter Seite, also . Rechtsreguläre Grammatiken erfüllen dagegen die analoge Bedingung . Diese enthalten also nur rechtsreguläre Produktionen (Nichtterminalsymbol auf der rechten Seite allenfalls in Hinterstellung). Diese Bedingung drückt auch schon die Erlaubnis leerer rechter Seiten aus. Linksreguläre und rechtsreguläre Grammatiken erzeugen genau dieselbe Sprachklasse, es gibt also zu jeder linksregulären Grammatik auch eine rechtsreguläre, die dieselbe Sprache erzeugt, und umgekehrt. Man beachte, dass beim Auftreten von linksregulären und rechtsregulären Produktionen in ein und derselben Chomsky-Grammatik diese nicht regulär ist. Die Grammatiken mit sowohl linksregulären als auch rechtsregulären Produktionen erzeugen nämlich eine echt größere Sprachklasse. Manche Autoren erlauben in den Definitionen für reguläre / linksreguläre / rechtsreguläre Grammatiken überall dort, wo hier in Produktionen nur ein einzelnes Nichtterminalzeichen stehen darf, auch eine beliebige nichtleere terminale Zeichenkette. An der Erzeugungsmächtigkeit der Klassen ändert sich dadurch nichts. Man schreibt für reguläre Grammatiken . Von Typ-3-Grammatiken erzeugte Sprachen Reguläre Grammatiken erzeugen genau die regulären Sprachen, das heißt, jede Typ-3-Grammatik erzeugt eine reguläre Sprache und zu jeder regulären Sprache existiert eine Typ-3-Grammatik, die diese erzeugt. Reguläre Sprachen können alternativ auch durch reguläre Ausdrücke beschrieben werden und die regulären Sprachen sind genau die Sprachen, die von endlichen Automaten erkannt werden können. Sie werden häufig genutzt, um Suchmuster oder die lexikalische Struktur von Programmiersprachen zu definieren. Übersicht Die folgende Tabelle führt für die vier Grammatiktypen auf, welche Form ihre Regeln haben, welchen Namen die erzeugten Sprachen haben und welche Automatentypen diese Sprachen erkennen, also das Wortproblem zumindest semi-entscheiden (Wort in Sprache: Maschine hält in akzeptierendem Endzustand, Wort nicht in Sprache: Maschine hält nie oder hält in nicht akzeptierendem Zustand → sicher hält die Maschine also nur, wenn das Wort in der Sprache ist). Da in der Chomsky-Hierarchie für die Sprachmengen aber eine echte Teilmengenbeziehung gilt (siehe nächster Abschnitt) entscheiden z. B. Turingmaschinen selbstverständlich ebenfalls das Wortproblem für Sprachen vom Typ 1 bis 3. (entscheiden heißt: Wort in Sprache: Maschine hält in akzeptierendem Endzustand, Wort nicht in Sprache: Maschine hält in nicht akzeptierendem Zustand → irgendwann hält die Maschine und das Problem (Wort in Sprache?) ist entschieden) Außerdem wird vermerkt, gegenüber welchen Operationen die erzeugten Sprachen abgeschlossen sind. Legende für die Spalte Regeln ... endliches Alphabet (Menge der Terminalsymbole, oft auch mit bezeichnet, das aber auch bedeuten kann) ... die davon disjunkte Menge der Nichtterminalsymbole (gelegentlich auch Variablen genannt und mit bezeichnet, statt ... gesamtes Vokabular) ... Startsymbol ... leeres Wort (oft auch mit bezeichnet) ... Menge von Produktionsregeln (als Teilmenge eines kartesischen Produkts eine Relation) ... Mengen-Differenzbildung ... Kleenescher Abschluss (Hülle), siehe Kleenesche und positive Hülle ... positive Hülle, z. B. meint ... muss mindestens ein Symbol (Terminal oder ein Nichtterminal) enthalten In der obigen Tabelle werden somit mit lateinischen Großbuchstaben Nichtterminalsymbole dargestellt , mit lateinischen Kleinbuchstaben Terminalsymbole und griechische Kleinbuchstaben werden verwendet, wenn es sich sowohl um Nichtterminal als auch um Terminalsymbole handeln kann. Achtung: Bei und kann ein griechischer Kleinbuchstabe für Wörter aus mehreren Terminal- oder Nichtterminalsymbolen stehen! Legende für die Spalte Abgeschlossenheit ... Komplementbildung ... Konkatenation ... Schnittmenge ... Vereinigungsmenge ... Kleenescher Abschluss (Hülle) Chomsky-Hierarchie für formale Sprachen Eine formale Sprache ist vom Typ entsprechend der Hierarchie für Grammatiken, wenn es von einer Typ--Grammatik erzeugt wird. Formal ausgedrückt heißt das: ist vom Typ falls es eine Grammatik mit gibt. Man schreibt dann In der Chomsky-Hierarchie für formale Sprachen besteht zwischen den Sprachmengen benachbarter Ebenen eine echte Teilmengenbeziehung. Jede kontextsensitive Sprache ist rekursiv aufzählbar, aber es gibt rekursiv aufzählbare Sprachen, die nicht kontextsensitiv sind. Ebenso ist jede kontextfreie Sprache auch kontextsensitiv, aber nicht umgekehrt, und jede reguläre Sprache ist kontextfrei, aber nicht jede kontextfreie Sprache ist regulär. Formal ausgedrückt bedeutet dies für die Klassen der durch die obigen Grammatiken erzeugten Sprachen: wobei gelegentlich auch folgende Symbole verwendet werden: Beispiele für Sprachen in den jeweiligen Differenzmengen sind: ist vom Typ 1, aber nicht vom Typ 2 ist vom Typ 2, aber nicht vom Typ 3 Beweise für die Nichtzugehörigkeit bestimmter Sprachen zu den Sprachklassen und wie hier werden oft mit dem Schleifensatz geführt. Natürliche Sprachen Obwohl Chomsky seine Forschungen mit dem Ziel verfolgte, eine mathematische Beschreibung der natürlichen Sprachen zu finden, ist bis heute für keine natürliche Sprache der Nachweis einer korrekten und vollständigen formalen Grammatik gelungen. Das Problem besteht u. a. im Zusammenspiel der verschiedenen Grammatikteile, die jeweils einzelne sprachliche Phänomene modellieren. Aber auch beim praktischen Einsatz formaler Grammatiken in der Computerlinguistik kann es zu Mehrdeutigkeiten auf verschiedenen Ebenen der Sprachbetrachtung kommen; diese müssen (z. B. in der maschinellen Übersetzung) anhand des Kontextes aufgelöst werden. Literatur Einzelnachweise Theorie formaler Sprachen Compilerbau Noam Chomsky


text: Als Polymerase-Kettenreaktion (, PCR) bezeichnet man Methoden zur in vitro-Vervielfältigung von Erbsubstanz (Desoxyribonukleinsäure). Dazu werden, je nach Methode, verschiedene Formen des Enzyms DNA-Polymerase verwendet. Die Bezeichnung Kettenreaktion bedeutet in diesem Zusammenhang, dass die Produkte vorheriger Zyklen als Ausgangsstoffe für den nächsten Zyklus dienen und somit eine exponentielle Vervielfältigung ermöglichen. Bei der klassischen PCR werden diese Zyklen über ein Temperaturprogramm gesteuert. Bei der Weiterentwicklung isotherme DNA-Amplifikation erfolgt diese Vervielfältigung kontinuierlich bei konstanter Temperatur. Die PCR wird in biologischen und medizinischen Laboratorien zum Beispiel für die Erkennung von Erbkrankheiten und Virusinfektionen, für das Erstellen und Überprüfen genetischer Fingerabdrücke, für das Klonieren von Genen und für Abstammungsgutachten verwendet. Sie ist die empfindlichste und zuverlässigste Labor-Methode des direkten Erregernachweises. Entwickelt wurde die Methode durch den Biochemiker Kary Mullis im Jahr 1985. 1993 wurde ihm dafür der Nobelpreis für Chemie verliehen. Die PCR zählt heute zu den wichtigsten Methoden der modernen Molekularbiologie, und viele wissenschaftliche Fortschritte auf diesem Gebiet (z. B. im Rahmen des Humangenomprojekts) wären ohne diese Methode nicht möglich gewesen. Geschichte Anfang der 1970er Jahre kam der norwegische Postdoc Kjell Kleppe im Labor von Nobelpreisträger Har Gobind Khorana auf den Gedanken, DNA durch zwei flankierende Primer zu vervielfältigen, jedoch geriet die Idee in Vergessenheit. Die Polymerase-Kettenreaktion selbst wurde 1983 von Kary Mullis erneut erfunden. Seine Absicht war es, ein neuartiges DNA-Syntheseverfahren zu entwickeln, das DNA durch wiederholte Verdopplung in mehreren Zyklen mittels eines Enzyms namens DNA-Polymerase künstlich vervielfältigt. Sieben Jahre nach der Veröffentlichung seiner Idee wurde Mullis hierfür 1993 der Nobelpreis für Chemie verliehen. DNA-Polymerase kommt in allen Lebewesen vor und verdoppelt während der Replikation die DNA vor der Zellteilung. Dazu bindet sie sich an einen einzelnen DNA-Strang und synthetisiert mittels eines kurzen komplementären Oligonukleotids (Primer) einen dazu komplementären Strang. Bereits in Mullis’ ursprünglichem PCR-Versuch wurde das Enzym in vitro verwendet. Die doppelsträngige DNA wurde zunächst durch Erhitzen auf 96 °C in zwei Einzelstränge getrennt. Bei dieser Temperatur wurde die dabei zunächst verwendete DNA-Polymerase I von E. coli zerstört und musste daher nach jedem Erhitzen erneut zugegeben werden. Diese Folge von Arbeitsschritten musste mehrere dutzendmal in Folge wiederholt werden, um eine ausreichende Amplifikation zu erreichen. Mullis’ ursprüngliches Verfahren war daher sehr ineffizient, da es viel Zeit, große Mengen DNA-Polymerase und ständige Aufmerksamkeit erforderte. Eine entscheidende Verbesserung der PCR-Technologie brachte die Verwendung von thermostabilen DNA-Polymerasen, das heißt von Enzymen, die auch bei Temperaturen von annähernd 100 °C ihre Polymerase-Aktivität behalten und nicht denaturieren. Eine der ersten thermostabilen DNA-Polymerasen wurde aus dem in heißen Quellen lebenden thermophilen Bakterium Thermus aquaticus gewonnen und Taq-Polymerase genannt. Durch die Verwendung thermostabiler DNA-Polymerasen bestand keine Notwendigkeit mehr, ständig neue Polymerase zuzugeben, und der ganze PCR-Prozess konnte erheblich vereinfacht und automatisiert werden. Mullis arbeitete zu dieser Zeit für die kalifornische Biotech-Firma Cetus und wurde mit einer Prämie von 10.000 US-Dollar abgefunden. Diese meldete die PCR-Methode zum Patent an. Jahre später verkaufte Cetus dann die Rechte an der PCR-Methode mitsamt dem Patent für die von ihm verwendete DNA-Polymerase Taq an die Firma Roche für 300 Millionen Dollar. Das Enzym Taq wurde jedoch bereits 1980 von dem russischen Forscher Kaledin beschrieben. Aus diesem Grund wurde nach jahrelangem Rechtsstreit der Firma Roche das Patent für Taq inzwischen entzogen. Die US-Patente für die PCR-Technologie selbst liefen im März 2005 aus. Die Taq-Polymerase erfährt nach wie vor breite Anwendung. Ihr Nachteil liegt darin, dass sie manchmal Fehler beim Kopieren der DNA produziert, was zu Mutationen in der DNA-Sequenz führt. Polymerasen wie Pwo und Pfu, die aus Archaea gewonnen werden, haben einen Korrekturmechanismus, der die Anzahl der Mutationen in der kopierten DNA erheblich senkt. Prinzip PCR wird eingesetzt, um einen kurzen, genau definierten Teil eines DNA-Strangs zu vervielfältigen. Der zu vervielfältigende Bereich der DNA wird auch als Amplicon bezeichnet, die bei der PCR entstehenden Produkte als Amplifikate. Dabei kann es sich um ein Gen oder auch nur um einen Teil eines Gens handeln oder auch um nichtcodierende DNA-Sequenzen. Im Gegensatz zu lebenden Organismen kann der PCR-Prozess nur relativ kurze DNA-Abschnitte kopieren. Bei einer Standard-PCR können dies bis zu etwa dreitausend Basenpaare (3 kbp) lange DNA-Fragmente sein. Mit Hilfe bestimmter Polymerasen-Gemische, weiterer Additive in der PCR und optimalen Bedingungen können sogar Fragmente mit einer Länge von über 20–40 kbp vervielfältigt werden, was immer noch sehr viel kürzer ist als die chromosomale DNA einer eukaryotischen Zelle. Eine menschliche Zelle enthält beispielsweise etwa drei Milliarden Basenpaare pro haploidem Genom. Komponenten und Reagenzien Eine PCR benötigt mehrere grundlegende Komponenten. Diese sind: Die Original-DNA, die den zu vervielfältigenden Abschnitt enthält (Template) Zwei Primer, um auf den beiden Einzelsträngen der DNA jeweils den Startpunkt der DNA-Synthese festzulegen, wodurch der zu vervielfältigende Bereich von beiden Seiten begrenzt wird DNA-Polymerase, die bei hohen Temperaturen nicht zerstört wird, um den festgelegten Abschnitt zu replizieren (kopieren) (z. B. Taq-Polymerase) Desoxyribonukleosidtriphosphate, die Bausteine für den von der DNA-Polymerase synthetisierten DNA-Strang Mg2+ -Ionen, für die Funktion der Polymerase essentiell, stabilisieren die Anlagerung der Primer und bilden lösliche Komplexe mit den Desoxyribonucleosidtriphosphaten Pufferlösungen, die eine für die DNA-Polymerase geeignete chemische Umgebung sicherstellen Die Reaktion wird üblicherweise in Volumina von 10–200 μl in kleinen Reaktionsgefäßen (200–500 μl) in einem Thermocycler durchgeführt. Diese Maschine erhitzt und kühlt die in ihr befindlichen Reaktionsgefäße präzise auf die Temperatur, die für den jeweiligen Schritt benötigt wird. Etwaige Kondensatbildung im Deckel des Gefäßes wird durch einen beheizbaren Gerätedeckel (über 100 °C) verhindert. Die Thermocycler der ersten Generation besaßen noch keinen beheizten Deckel, weshalb bei diesen Geräten zur Vermeidung einer Verdampfung von Wasser während der PCR die Reaktionsansätze mit Mineralöl überschichtet wurden. Als Reaktionsgefäß können, je nach Probeneinsatz bzw. Heizblock des Thermocyclers, neben einzelnen 200-μl-Reaktionsgefäßen auch acht zusammenhängende 200-μl-Reaktionsgefäße oder PCR-Platten für bis zu 96 Ansätze mit 200 μl oder auch 384 Ansätze zu je 50 μl verwendet werden. Die Platten werden entweder mit einer Gummiabdeckung oder einer selbstklebenden Klarsichtfolie verschlossen. Beispiel Als allgemeines Beispiel sei hier eine typische Zusammensetzung einer PCR-Reaktion wiedergegeben. Viele Beispiele für die verschiedensten Variationen der PCR finden sich in der wissenschaftlichen Literatur in verschiedensten Kombinationen: Ablauf Der PCR-Prozess besteht aus etwa 20–50 Zyklen, die in einem Thermocycler durchgeführt werden. Die folgenden Angaben sind als Richtwerte gedacht. Meist muss eine PCR auf die spezifische Reaktion hin optimiert werden. Jeder Zyklus besteht aus drei Schritten (siehe Abbildung unterhalb): Denaturierung (Melting, Schmelzen): Zunächst wird die doppelsträngige DNA auf 94–96 °C erhitzt, um die Stränge zu trennen. Die Wasserstoffbrückenbindungen, die die beiden DNA-Stränge zusammenhalten, werden aufgebrochen. Im ersten Zyklus wird die DNA oft für längere Zeit erhitzt (Initialisierung), um sicherzustellen, dass sich sowohl die Ausgangs-DNA als auch die Primer vollständig voneinander getrennt haben und nur noch Einzelstränge vorliegen. Manche (sogenannte Hot-Start-) Polymerasen müssen durch eine noch längere anfängliche Erhitzungsphase (bis zu 15 Minuten) aktiviert werden. Primerhybridisierung (primer annealing): In diesem Schritt wird die Temperatur abgesenkt und ca. 30 Sekunden lang auf einem Wert gehalten, der eine spezifische Anlagerung der Primer an die DNA erlaubt. Die genaue Temperatur wird hierbei durch die Länge und die Sequenz der Primer bestimmt (bzw. der passenden Nukleotide im Primer, wenn durch diesen Mutationen eingeführt werden sollen = site-directed mutagenesis). Wird die Temperatur zu niedrig gewählt, können sich die Primer unter Umständen auch an nicht hundertprozentig komplementären Sequenzen anlagern und so zu unspezifischen Produkten („Geisterbanden“) führen. Wird die Temperatur zu hoch gewählt, ist die thermische Bewegung der Primer unter Umständen so groß, dass sie sich nicht richtig anheften können, so dass es zu gar keiner oder nur ineffizienter Produktbildung kommt. Die Temperatur, welche die beiden oben genannten Effekte weitgehend ausschließt, liegt normalerweise 5–10 °C unter dem Schmelzpunkt der Primersequenzen; dies entspricht meist einer Temperatur von 55 bis 65 °C. Elongation (Extension, Polymerisation, Verlängerung, Amplifikation): Schließlich füllt die DNA-Polymerase die fehlenden Stränge mit freien Nukleotiden auf. Sie beginnt am 3'-Ende des angelagerten Primers und folgt dann dem DNA-Strang. Der Primer wird nicht wieder abgelöst, er bildet den Anfang des neuen Einzelstrangs. Die Temperatur hängt vom Arbeitsoptimum der verwendeten DNA-Polymerase ab (68–72 °C). Bei diesen Temperaturen können jedoch nur ganz bestimmte Enzyme arbeiten. Oft wird hier die Taq-Polymerase genutzt. Dieser Schritt dauert etwa 30 Sekunden je 500 Basenpaare, variiert aber in Abhängigkeit von der verwendeten DNA-Polymerase. Die PCR-Produkte sind anschließend viele Tage auch bei Raumtemperatur stabil, sodass eine Weiterverarbeitung nicht sofort erfolgen muss. In vielen Laboren hat es sich etabliert, die Proben im Thermocycler nach Ende der PCR auf 4–8 °C herunter zu kühlen. Viele Hersteller raten davon jedoch ab, da aufgrund von Kondensation im Metallblock die Lebenszeit eines Cyclers mit Peltier-Element stark reduziert wird. (A) Die Ausgangs-DNA liegt zunächst als Doppelstrang vor (Pfeilrichtung: 5'→3'). (B,C) Nach der Denaturierung sind die Einzelstränge getrennt und die Primer können binden. (C,D) Die Polymerase produziert den Gegenstrang, indem sie die Primer 5'→3' (in Pfeilrichtung) verlängert. Die Produkte sind jeweils noch an einem Ende zu lang. Dies ist damit zu erklären, dass lediglich ein Startpunkt (Primer), nicht aber ein Endpunkt exakt festgelegt ist. (E,F) Im nächsten Zyklus entstehen erstmals PCR Produkte in der richtigen Länge – allerdings sind die Gegenstränge jeweils noch zu lang. (G,H) Im dritten Zyklus entsteht erstmals das PCR Produkt als Doppelstrang in der richtigen Länge (die anderen Produkte sind in H nicht dargestellt). (H,I,J) In den folgenden Zyklen vermehren sich die gewünschten Produkte exponentiell (da sie selbst als Matrize für weitere Strangsynthesen dienen), während die ungewünschten langen Produkte (siehe Produkte des ersten Zyklus) nur linear ansteigen (nur eingesetzte DNA dient als Matrix). Dies ist der theoretische Idealfall, in der Praxis fallen aber zudem in geringem Maße auch kürzere Fragmente als die gewünschte Ziel-DNA an. Diese kurzen Fragmente häufen sich vor allem in den späten Zyklen an und können durch Fehlpaarung der Primer auch zu falschen PCR Produkten werden. Daher werden bei PCR Reaktionen meist nur etwa 30 Zyklen durchlaufen, damit vorwiegend DNA der gewünschten Länge und Sequenz produziert wird. Aufreinigung von PCR-Produkten Ein PCR-Produkt kann durch Agarose-Gelelektrophorese anhand seiner Größe identifiziert werden. (Die Agarose-Gelelektrophorese ist ein Verfahren, bei der DNA in ein Agarose-Gel eingebracht wird und anschließend eine Spannung angelegt wird. Dann bewegen sich die kürzeren DNA-Stränge schneller als die längeren auf den Pluspol zu.) Die Länge des PCR-Produkts kann durch einen Vergleich mit einer DNA-Leiter, die DNA-Fragmente bekannter Größe enthält und parallel zur Probe im Gel mitläuft, bestimmt werden. Soll die PCR vor allem als quantitativer Nachweis dienen, empfiehlt sich die Real Time PCR oder die Digital PCR. PCR-Optimierung Verschiedene Methoden können eingesetzt werden, um die Synthesemengen zu steigern oder Inhibitoren der PCR zu beseitigen. Varianten Die klassische PCR ist durch zahlreiche Variationen erweitert und verbessert worden. Dadurch können verschiedene Aufgaben spezifisch angegangen werden. Alternativ zur PCR können auch verschiedene Methoden der isothermalen DNA-Amplifikation oder Ligase-Kettenreaktion verwendet werden. Agglutinations-PCR: Methode zur Bestimmung der Menge von Antikörpern. Es werden Antigene durch Antikörper isoliert und dann vermehrt. Die genaue Antikörpermenge muss aber schon vorher vorliegen, z. B. im Neutralisationshemmtest. [[Digital Polymerase Chain Reaction|Digital PCR]] (dPCR): Bei der digital PCR (dPCR) wird die DNA verdünnt und auf eine große Anzahl an Femtoliter-Reaktionsgefäßen verteilt. Pro Reaktionsgefäß entsteht entweder DNA oder nicht. Aufgenommen wird ein Digitalsignal. Durch Auszählen einer großen Anzahl an Reaktionsgefäßen kann der Anteil erfolgter Reaktionen zur Mengenbestimmung verwendet werden. Immun-PCR: Methode zur Erkennung von Antigenen. Immunoquantitative Echtzeit-PCR (irt-PCR): Manchmal müssen selbst geringe Mengen an Pathogenen wirksam erkannt werden, da sie auch einzeln für den Menschen gefährlich werden können. Die Detektionsschwelle vieler immunologischer Methoden (z. B. ELISA) kann für diese Fälle unzureichend sein, so dass man hier auf die immunoquantitative Echtzeit-PCR (immunoquantitative real-time PCR) zurückgreift. Hierbei kombiniert man die hohe Spezifität von Antikörpern mit einer qPCR. Wie beim klassischen ELISA nutzt man zwei Antikörper. Der erste wird an einer Mikrotiterplatte fixiert und erkennt das gesuchte Antigen. Daran bindet dann der zweite Antikörper. Im herkömmlichen ELISA wird der immunologische Komplex aus erstem Antikörper, Antigen und zweitem Antikörper durch eine chemische Farbreaktion sichtbar gemacht, dagegen ist in der irt-PCR der zweite Antikörper über einen Streptavidin-Biotin-Komplex mit einer 246bp-langen doppelsträngigen DNA verbunden. Wenn der immunologische Komplex entsteht, kann diese Marker-DNA durch qPCR amplifiziert, detektiert und quantifiziert werden. Diese Methode ist etwa tausendmal sensibler als ein klassischer ELISA. Inverse PCR: Amplifikation unbekannter Genbereiche. Kolonie-PCR: Nachweis von bestimmten DNA-Sequenzen in Kolonien von Bakterien oder Pilzen; als DNA-Vorlage keine gereinigte Plasmid-DNA oder chromosomale DNA, sondern aus dem Kulturmedium entnommene Bakterienkolonien. Ligation-During-Amplification: Wird häufig zur Mutagenese von Plasmiden genutzt. Zirkuläre DNA kann amplifiziert werden, wodurch ein zusätzlicher Ligationsschritt entfällt. MassTag-PCR: Kombination einer PCR mit der Massenspektrometrie. Multiplex ligation-dependent probe amplification (MLPA): Variante der Multiplex-PCR (s. unten) zur gezielten Vermehrung mehrerer ähnlicher DNA-Sequenzen. Multiplex-PCR: Es werden mehr als ein Primerpaar für die Amplifikation eines bestimmten Gens oder auch mehrerer Gene auf einmal verwendet. Die Multiplex-PCR spielt u. a. in der Diagnostik von Krankheiten eine Rolle, beispielsweise beim Lesch-Nyhan-Syndrom. Ursache für das Lesch-Nyhan-Syndrom ist eine Mutation des HPRT1-Gens, das für eine Hypoxanthin-Guanin-Phosphoribosyltransferase codiert. Das Gen hat neun Exons, in Patienten mit dem Lesch-Nyhan-Syndrom kann eines dieser Exons fehlen. Durch eine Multiplex-PCR kann dies leicht entdeckt werden. Nested-PCR: Die nested (verschachtelte bzw. geschachtelte) PCR eignet sich sehr gut, wenn nur sehr geringe Mengen der zu amplifizierenden DNA relativ zur Gesamtprobenmenge an DNA vorhanden sind. Hierbei werden zwei PCR hintereinander ausgeführt. Durch die erste PCR wird – neben unerwünschten Sequenzbereichen infolge unspezifischer Bindung der Primer – der gewünschte Abschnitt der DNA (Amplikon) erzeugt. Letztere wird für eine zweite PCR als Matrize verwendet. Durch Primer, die an Bereichen innerhalb der ersten Matrize binden (downstream der ersten Primer), wird der gewünschte Sequenzbereich mit sehr hoher Spezifität generiert. Da auch die DNA-Region der Wahl zum zweiten Mal amplifiziert wurde, entsteht ausreichend DNA für weitere Prozedere. Anwendung findet die nested-PCR beispielsweise in der Gen-Diagnostik, in der Forensik (bei sehr wenig verwertbaren Spuren wie Haaren oder Bluttropfen wie im Kriminalfall JonBenét Ramsey) oder bei phylogenetischen Untersuchungen. Auch Mikrochimärismus bei Leukozyten nach einer Bluttransfusion kann mittels nested-PCR nachgewiesen werden. PAN-PCR: Eine rechnerische Methode zur Gestaltung der Bakterientypisierung - Tests basierend auf Sequenzdaten des gesamten Genoms Quantitative Echtzeit-PCR (qPCR oder real-time PCR): Wird benutzt, um die Menge des vervielfältigten DNA-Abschnitts zu bestimmen. Im Laborjargon wird fast nur der englische Begriff real-time PCR oder quantitative PCR verwendet, kurz qPCR oder missverständlich auch rt-PCR, was aber zu Verwechslungen mit dem länger etablierten Begriff RT-PCR mit vorgeschalteter reverser Transkription führt. Bei der real-time PCR wird der Reaktion ein zunächst inaktiver Fluoreszenzfarbstoff beigemischt, der durch die DNA-Produktion aktiv wird. (Zum Beispiel, weil er sich in die DNA einlagert (wie SYBR Green) oder weil ein Quencher, der die Fluoreszenz zunächst löscht, bei der Amplifikation entfernt wird.) Bei jedem Zyklus – also „in Echtzeit“ – wird die Fluoreszenz gemessen, woraus man auf die Menge der amplifizierten DNA schließen kann. Abhängig von der ursprünglichen Anzahl an Kopien wird ein gewisser Schwellenwert des Fluoreszenzsignals früher oder später (oder gar nicht) erreicht. Wegen dieser Zusatzinformation hat die real-time PCR den Beinamen „quantitative PCR (qPCR)“. Z. B. durch die Verwendung von Standardkurven erlaubt diese Technik auch eine absolute Quantifizierung (als Kopieanzahl pro Reaktion). Obwohl Geräte und farbstoffmarkierte Reagenzien teurer sind als bei der „klassischen“ Endpunkt-PCR, ist ein Sichtbarmachen der Amplifikate auf einem Gel nicht unbedingt nötig, so dass sich Arbeit und vor allem Zeit sparen lassen. Die Technik der qPCR lässt sich auch mit einer vorgeschalteten reversen Transkription (RT) kombinieren, z. B. um RNA-Viren nachzuweisen, dann spricht man von qRT-PCR. Reverse-Transkriptase-PCR (RT-PCR): Die Amplifikation von RNA (z. B. eines Transkriptoms oder eines RNA-Virus) erfolgt in einer Reverse-Transkriptions-PCR (engl. ) über eine reverse Transkription der RNA in DNA mit einer reversen Transkriptase. In Kombination mit einer Konzentrationsbestimmung in Echtzeit (qPCR) bezeichnet man die Reaktion als qRT-PCR. Touchdown-PCR: vermeidet eine Amplifizierung unspezifischer DNA-Sequenzen. In den ersten Synthese-Zyklen wird die Annealing-Temperatur nur knapp unterhalb der Denaturierungstemperatur gewählt. Damit ist die Primerbindung und somit auch das Amplifikat höchst spezifisch. In den weiteren Zyklen wird die Annealing-Temperatur herabgesetzt. Die Primer können jetzt zwar unspezifische Bindungen eingehen, allerdings verhindern die spezifischen Replikate der frühen Reaktion eine übermäßige Amplifikation der unspezifischen Sequenzen. Ein weiterer Vorteil ist eine enorme Steigerung der Amplifikatmenge. Diese abgewandelte PCR erlaubt somit eine starke und sehr spezifische DNA-Amplifikation. Anwendungsgebiete Die PCR kommt als Methode zur Detektion und Vervielfältigung von DNA-Abschnitten in einer Vielzahl von Anwendungsgebieten zum Einsatz. Forschung Das Klonieren eines Gens – nicht zu verwechseln mit dem Klonen eines ganzen Organismus – ist ein Vorgang, bei dem ein Gen aus einem Organismus isoliert und anschließend in einen anderen eingepflanzt wird. PCR wird oft benutzt, um das Gen zu vervielfältigen, das dann in einen Vektor (ein Vektor ist ein Mittel, mit dem ein Gen in einen Organismus verpflanzt werden kann), beispielsweise ein Plasmid (ein ringförmiges DNA-Molekül), eingefügt wird (siehe Abbildung). Die DNA kann anschließend in einen anderen Organismus eingesetzt werden, in dem das Gen oder sein Produkt besser untersucht werden kann. Das Exprimieren eines klonierten Gens kann auch zur massenhaften Herstellung nutzbarer Proteine wie z. B. Arzneimittel dienen. Mutagenese ist eine Möglichkeit, die Sequenz der Nukleotide (Basen) der DNA zu verändern. Es gibt Situationen, in denen man mutierte (veränderte) Kopien eines bestimmten DNA-Strangs benötigt, um die Funktion eines Gens zu bestimmen. Mutationen können in kopierte DNA-Sequenzen auf zwei grundsätzlich verschiedene Arten während des PCR-Prozesses eingefügt werden. Gezielte Mutagenese (engl. site-directed mutagenesis) erlaubt es dem Forscher, an spezifischen Stellen auf dem DNA-Strang Mutationen zu erzeugen. Meist wird dafür die gewünschte Mutation in die Primer integriert, die für die PCR verwendet werden. Bei der gezielten bzw. stellenspezifischen Mutagenese ist mindestens einer der Primer nicht hundertprozentig identisch mit der DNA, an die er sich anlagert. Während der Amplifikation wird so eine Mutation in das DNA-Fragment eingeführt. Zufällige Mutagenese (engl. random mutagenesis) beruht hingegen auf der Verwendung von fehlerträchtigen Polymerasen (bzw. Polymerasen ohne Mechanismus zur Fehlerkorrektur) während des PCR-Prozesses. Bei der zufälligen Mutagenese können Ort und Art der Mutationen nicht beeinflusst werden und müssen erst durch eine Sequenzierung identifiziert werden. Eine Anwendung der zufälligen oder gezielten Mutagenese ist die Analyse der Struktur-Funktions-Beziehungen eines Proteins. Nach der Veränderung der DNA-Sequenz kann man das entstandene Protein mit dem Original vergleichen und die Funktion aller Teile des Proteins bestimmen. Zudem können damit auch Funktionen der Nukleinsäure selbst (mRNA-Transport, mRNA-Lokalisation etc.) untersucht werden. Gängige Methoden der DNA-Sequenzierung (Bestimmung der Nukleotid-Abfolge von DNA) basieren auf Varianten der PCR. Die Illumina Sequenzierungsmethode (Sequenzierung mit Brückensynthese) beruht auf einer Festphasen-PCR, bei der die zu sequenzierende DNA zufällig fragmentiert, mit Oligonukleotiden (Adaptersequenzen) ligiert und über komplementäre Adaptersequenzen an einer Oberfläche fixiert wird. Bei der anschließenden PCR dienen die Adaptersequenzen als Primer. Zur Sequenzierung werden hierbei spezielle Nukleotide verwendet, die mit verschiedenfarbigen fluoreszierenden Markern versehen sind. Während der Amplifikation kann über die jeweils detektierte Farbe das eingebaute Nukleotid zugeordnet werden. Andere Sequenzierungsmethoden basieren auf der Emulsions-PCR. Beispiele sind die Zwei-Basen-Sequenzierung (engl. Sequencing by Oligo Ligation Detection, SOLiD) oder das Ionen-Halbleiter-DNA-Sequenzierungssystem (Ion Torrent Sequenzierungsmethode). Medizin und Diagnostik Die Erkennung von Erbkrankheiten in einem vorliegenden Genom ist ein langwieriger und komplizierter Vorgang, der durch den Einsatz von PCR bedeutend verkürzt werden kann. Jedes Gen, das in Frage kommt, kann durch PCR mit den entsprechenden Primern amplifiziert (= vervielfältigt) und anschließend sequenziert werden (DNA sequenzieren heißt, die Sequenz der Nukleotide (oder Basen) der DNA zu bestimmen), um Mutationen aufzuspüren. Virale Erkrankungen können ebenfalls durch PCR erkannt werden, indem man die Virus-DNA vervielfältigt bzw. bei RNA-Viren diese RNA erst in DNA umschreibt und dann mittels PCR vervielfältigt (die RT-PCR). Diese Analyse kann sofort nach der Infektion erfolgen, oft Tage oder Wochen vor dem Auftreten der Symptome. Erfolgt die Diagnose so früh, erleichtert das den Medizinern die Behandlung erheblich. Darüber hinaus wird die quantitative PCR auch für die Diagnostik verwendet, z. B. um die genaue Viruslast bei einer bekannten HIV-Infektion zu bestimmen, um die Entwicklung des Therapieerfolgs nachzuvollziehen. Die PCR kann auch zu Reihenuntersuchungen eingesetzt werden. So wird sie z. B. von Blutspendediensten zur Routineuntersuchung von Blutkonserven eingesetzt. Die Empfindlichkeit des PCR-Tests erlaubt es, Proben zu sogenannten Pools (z. B. 64 Einzelproben) zusammenzufassen. Ist der Test eines Pools positiv, wird die Anzahl der zusammengefassten Proben solange verringert (meistens halbiert), bis die verursachende Probe identifiziert ist. Zur sicheren Diagnostik und Absicherung von eventuell falsch-positiven Antigen-Schnelltests bei der COVID-19-Erkrankung wird die PCR ebenfalls eingesetzt. Forensik, Paläontologie und Biologische Anthropologie Der genetische Fingerabdruck ist ein DNA-Profil, das für jedes Individuum einzigartig ist. In der Forensik wird der genetische Fingerabdruck genutzt, um kleinste Spuren von an Tatorten gefundener DNA mit der DNA von Verdächtigen zu vergleichen. Als Proben können Blut, Sperma, Speichel, Hautzellen, oder Haare mit anhaftenden Zellen dienen. Die DNA wird aus den Zellkernen der in den Proben enthaltenen Körperzellen extrahiert, aufgereinigt und analysiert. Bei der Analyse wird die PCR genutzt, um spezielle DNA-Abschnitte zu vervielfältigen, die sich in nicht-codierenden Bereichen der DNA (junk DNA) befinden und aus Wiederholungen bestimmter kurzer Sequenzen (Tandemwiederholungen) bestehen. Die Anzahl der Tandemwiederholungen (und damit die Länge der Sequenzen) sind zwischen verschiedenen Individuen sehr variabel. Da mehrere unterschiedliche DNA-Abschnitte auf die jeweilige Anzahl der Tandemwiederholungen hin untersucht werden, entsteht ein individuelles Muster aus PCR-Produkten charakteristischer Längen. Abstammungsgutachten oder Vaterschaftstests basieren ebenfalls auf dem genetischen Fingerabdruck (siehe Abbildung). In der Molekularen Phylogenie zur Untersuchung evolutionärer Verwandtschaftsverhältnisse von Organismen. Analyse alter (fossiler) DNA: Da die PCR aus nur geringen DNA-Probemengen eine beliebige Menge von Material erzeugen kann, ist sie besonders für die sehr alte aDNA geeignet, die in der Natur nur noch in für Untersuchungen nicht mehr ausreichenden Mengen vorkommt. Dabei beruhen nahezu alle wissenschaftlichen Erkenntnisgewinne in Bezug auf die aDNA und somit viele seit langem ausgestorbener Arten auf der Methode der PCR. Lebensmittelanalytik Die steigenden Anforderungen von Handel und behördlicher Lebensmittelüberwachung zur Aufklärung und Verhinderung von unlauterem Wettbewerb führten zum Einzug der Technologie in die Lebensmittelanalytik. So kann die PCR zur Identifizierung von Gewürzen in komplexen Lebensmittelmatrizes herangezogen werden. Sie kann auch zur Unterscheidung von Varietäten bei Edelkakao z. B. Criollo und Forastero eingesetzt werden. Literatur C. R. Newton, A. Graham: PCR. Introduction to Scientific Techniques. 2. Auflage. ed. BIOS Scientific Publishers, Oxford 1997, ISBN 1-872748-82-1. R. K. Saiki, D. H. Gelfand, S. Stoffel, S. J. Scharf, R. Higuchi, G. T. Horn, K. B. Mullis, H. A. Erlich: Primer-Directed Enzymatic Amplification of DNA with a Thermostable DNA Polymerase (PDF; 1,2 MB). In: Science. 239.1988, S. 487–491, PMID 2448875, Kary B. Mullis, F. Faloona, S. Scharf, R. Saiki, G. Horn, H. Erlich: Specific enzymatic amplification of DNA in vitro: the polymerase chain reaction. Cold Spring Harb Symp Quant Biol. 1986;51 Pt 1:263-73. Kary B. Mullis: The polymerase chain reaction. Birkhäuser, Boston 1994, ISBN 3-7643-3607-2. Rabinow, Paul: Making PCR: A Story of Biotechnology, University of Chicago Press, 1996, ISBN 0-226-70146-8. D. Baltimore: RNA-dependent DNA polymerase in virions of RNA tumor viruses. In: Nature 226, 1970, S. 1209–1211. Weblinks Animation der PCR mit Beschreibung (deutsch) Einzelnachweise Molekularbiologie Lebensmittelanalytik Nukleinsäure-Methode Gentechnik Wikipedia:Artikel mit Video


text: Deutschland steht für: Deutschland, mitteleuropäischer Staat historisch: das Regnum Teutonicum, nördlich der Alpen gelegener Teil des Heiligen Römischen Reiches die räumlich nicht genau bestimmte Vorstellung eines deutschsprachigen kulturellen Raums, auch bezeichnet als Teutschland, siehe Deutschland #Begriffsgeschichte: Deutsch und Deutschland den Deutschen Bund 1815 bis 1866 das Deutsche Reich 1848/1849 Deutschland 1945 bis 1949, Westdeutschland und Deutsche Demokratische Republik Personen: Heinz Deutschland (* 1934), deutscher Historiker und Diplomat Helmut Deutschland (1918–2007), deutscher Tischtennisspieler Joachim Deutschland (* 1980), deutscher Musiker Jutta Deutschland (* 1958), deutsche Balletttänzerin Wirtschaft: mehrere Schiffe, siehe Liste von Schiffen mit dem Namen Deutschland Zeche Deutschland, ehemaliges Bergwerk in Sprockhövel (1871–1925) Maschinenfabrik Deutschland, ehemaliges Maschinenbau-Unternehmen (1872–1996) Motorfahrzeugfabrik Deutschland, ehemaliger deutscher Automobilhersteller (1903–1905) LZ 7 „Deutschland“ (Luftschiff), DELAG-Zeppelin (1910) LZ 8 „Deutschland“ (Luftschiff), DELAG-Zeppelin (1910) Medien und Kultur: Deutschland. Zeitschrift für Heimatkunde und Heimatliebe. Organ für die deutschen Verkehrs-Interessen, Zeitschrift (1912–1928) Deutschland (Slime-Lied), Musiktitel (1981), siehe Slime I #Deutschland Deutschland (Böhse-Onkelz-Lied), Musiktitel (1984), siehe Der nette Mann #Deutschland Deutschland (Die-Prinzen-Lied), Musiktitel (2001) Deutschland (Muhabbet-Lied), Musiktitel (2007) Deutschland (Rammstein-Lied), Musiktitel (2019) Deutschland (Fernsehserie), Fernsehserie (2015, 2018, 2020) Siehe auch: Teutschland, 1708 errichtetes Außenwerk der Würzburger Festung Marienberg


text: Die Datenkompression (wohl lehnübersetzt und eingedeutscht aus dem englischen ) – auch (weiter eingedeutscht) Datenkomprimierung genannt – ist ein Vorgang, bei dem die Menge digitaler Daten verdichtet oder reduziert wird. Dadurch sinkt der benötigte Speicherplatz, und die Übertragungszeit der Daten verkürzt sich. In der Nachrichtentechnik wird die Komprimierung von Nachrichten aus einer Quelle durch einen Sender als Quellenkodierung bezeichnet. Grundsätzlich wird bei der Datenkompression versucht, redundante Informationen zu entfernen. Dazu werden die Daten in eine Darstellung überführt, mit der sich alle – oder zumindest die meisten – Informationen in kürzerer Form darstellen lassen. Diesen Vorgang übernimmt ein Kodierer und man bezeichnet den Vorgang als Kompression oder Komprimierung. Die Umkehrung bezeichnet man als Dekompression oder Dekomprimierung. Man spricht von verlustfreier Kompression, verlustfreier Kodierung oder Redundanzreduktion, wenn aus den komprimierten Daten wieder exakt die Originaldaten gewonnen werden können. Das ist beispielsweise bei der Kompression ausführbarer Programmdateien notwendig. Bei der verlustbehafteten Kompression oder Irrelevanzreduktion können die Originaldaten aus den komprimierten Daten meist nicht mehr exakt zurückgewonnen werden, das heißt, ein Teil der Information geht verloren; die Algorithmen versuchen, möglichst nur „unwichtige“ Informationen wegzulassen. Solche Verfahren werden häufig zur Bild- oder Videokompression und Audiodatenkompression eingesetzt. Allgemein Datenkompression findet heutzutage bei den meisten Fernübertragungen digitaler Daten statt. Sie hilft, Ressourcen bei der Übertragung oder Speicherung von Daten einzusparen, indem sie in eine Form verwandelt werden, die – abhängig von der Anwendung – möglichst minimal ist. Dabei können verlustlos nur Daten komprimiert werden, die in irgendeiner Form redundant sind. Ist keine Redundanz vorhanden – zum Beispiel bei völlig zufälligen Daten – ist verlustlose Kompression wegen der Kolmogorov-Komplexität prinzipiell unmöglich. Ebenso verbietet das Taubenschlagprinzip, dass jede beliebige Datei verlustlos komprimiert werden kann. Hingegen ist verlustbehaftete Kompression immer möglich: Ein Algorithmus ordnet die Daten danach, wie wichtig sie sind und verwirft die „unwichtigen“ dann. In der Auflistung, wie wichtig welche Bestandteile sind, kann stets mehr verworfen werden, indem die „Behalten-Schwelle“ entsprechend verschoben wird. Bei der Datenkompression ist sowohl auf Sender- als auch auf Empfängerseite Berechnungsaufwand nötig, um die Daten zu komprimieren oder wiederherzustellen. Der Berechnungsaufwand ist jedoch bei verschiedenen Kompressionsmethoden sehr unterschiedlich. So sind etwa Deflate und LZO sowohl bei Kompression und Dekompression sehr schnell, während etwa LZMA unter großem Aufwand eine besonders weitgehende Kompression – und somit möglichst kleine Datenmengen – erzielt, während komprimierte Daten sehr schnell wieder in die ursprüngliche Form zurückgewandelt werden können. Dies erzwingt je nach Anwendungsgebiet eine unterschiedliche Wahl der Kompressionsmethode. Daher sind Kompressionsmethoden entweder auf Datendurchsatz, Energiebedarf oder die Datenreduktion optimiert, und die Kompression hat somit nicht immer eine möglichst kompakte Darstellung als Ziel. Deutlich wird der Unterschied bei diesen Beispielen: Werden Video- oder Tonaufnahmen live gesendet, müssen Kompression und Wiederherstellung möglichst schnell durchgeführt werden. Qualitätseinbußen sind vertretbar, wenn dafür die maximale (mögliche) Übertragungsrate eingehalten wird. Dies gilt beispielsweise für Telefongespräche, wo der Gesprächspartner oft auch bei schlechter Tonqualität noch verstanden wird. Wird eine einzelne Datei von unzähligen Nutzern heruntergeladen, lohnt sich ein langsamer, aber sehr leistungsfähiger Kompressions-Algorithmus. Die reduzierte Bandbreite bei der Übertragung macht den Zeitaufwand der Kompression leicht wett. Bei der Datensicherung und der Archivierung von Daten muss ein Algorithmus verwendet werden, der gegebenenfalls auch in ferner Zukunft verwendet wird. In diesem Fall kommen nur verbreitete, bewährte Algorithmen in Frage, die mitunter nicht die besten Kompressionsraten aufweisen. Auch die Art der Daten ist relevant für die Auswahl der Kompressionsmethode. Zum Beispiel haben die beiden auf unixoiden Betriebssystemen gebräuchlichen Kompressions-Programme gzip und bzip2 die Eigenschaften, dass gzip nur 32.000 Bytes große Blöcke komprimiert, während bzip2 900.000 Bytes Blockgröße aufweist. Redundante Daten werden nur innerhalb dieser Blöcke komprimiert. Mitunter werden die Daten vor der Kompression noch in eine andere Darstellung transformiert. Das ermöglicht einigen Verfahren die Daten anschließend effizienter zu komprimieren. Dieser Vorverarbeitungsschritt wird Präkodierung genannt. Ein Beispiel dafür ist die Burrows-Wheeler-Transformation und Move to front bei bzip2. Das Fachgebiet der Datenkompression überschneidet sich zum Teil mit Informationstheorie und künstlicher Intelligenz, und im Bereich der verlustbehafteten Datenkompression auch mit Wahrnehmungspsychologie (s. weiter unten). Informationstheorie ist insofern betroffen, weil die Dateigröße eines bestmöglich komprimierten Datensatzes direkt den Informationsgehalt dieses Datensatzes angibt. Kann ein Kompressionsalgorithmus lernen, unter welchen Umständen auf die Zeichenkette "ABC" ein "D" folgt, muss das "D" in der komprimierten Datei gar nicht gespeichert werden – bei der Wiederherstellung der ursprünglichen Datei weiß der Algorithmus, an welchen Stellen ein "D" einzufügen ist. Obwohl noch kein derartiger Kompressionsalgorithmus in der Praxis verwendet wird, sind diverse Kompressionsverfahren, die künstliche neuronale Netzwerke und maschinelles Lernen verwenden, in Entwicklung. Grenzen der Komprimierbarkeit Verlustbehaftete Kompression Verlustbehaftete Kompression ist, wie oben beschrieben, stets möglich – die Schwelle, was als „redundant“ gilt, kann so lange heraufgesetzt werden, bis nur noch 1 Bit übrig bleibt. Die Grenzen sind fließend und werden durch den Anwendungsfall bestimmt: Zum Beispiel könnte "Das Haus ist groß" zu "Das Haus ist gr" komprimiert werden; will der Leser wissen "welche Eigenschaft hat das Haus?", so ist nicht mehr unterscheidbar, ob es "grau", "grün" oder "groß" ist. Will der Leser wissen "wurde etwas über ein Haus gesagt?", so kann das noch immer eindeutig bejaht werden. Bei verlustbehafteter Bildkompression gehen zunehmend Details verloren/werden unscharf, schließlich „verschwimmt alles“ zu einer Fläche mit einheitlicher Farbe; eine Audio-Aufnahme wird meist dumpfer und undeutlicher, sie würde nach größtmöglicher Kompression bei den meisten Algorithmen nur noch einen einfachen Sinuston aufweisen. Verlustfreie Kompression Bei verlustfreier Kompression gelten sehr viel engere Grenzen, da gewährleistet sein muss, dass die komprimierte Datei wieder in die Originaldatei rücktransformiert werden kann. Die Kolmogorow-Komplexität befasst sich mit der kleinstmöglichen "Anleitung", die notwendig ist, um aus den komprimierten Daten die Originaldaten wiederherzustellen. So zum Beispiel lässt sich die Zahl "100000000000000000000000000000000000" sehr einfach komprimieren: "Schreibe 1 und dann 35 Nullen", was eine Kompression von 36 auf 29 Zeichen darstellt. Ebenfalls lassen sich beliebig viele Nachkommastellen der Kreiszahl Pi mit ihrer Berechnungsvorschrift komprimieren – wobei der Kompressionsalgorithmus dann erkennen müsste, dass es sich um die Zahl Pi handelt. Zu beachten ist, dass bei komprimierten Dateien der Wiederherstellungs-Algorithmus ebenfalls zur Dateigröße hinzugerechnet werden müsste, da jede komprimierte Datei ohne einen solchen Algorithmus wertlos ist. So ließe sich die obige Zahl auch mit "10^35" oder "1e35" komprimieren, wobei dann der Leser von der Wiederherstellungsmethode, nämlich der Potenzschreibweise, Kenntnis haben muss. Weist eine Zeichenkette aber keinerlei erkennbare Struktur/Besonderheiten auf, dann ist eine Kompression nicht möglich – die Anleitung müsste die unveränderten Originaldaten beinhalten. Ein weiterer Grund für die Unkomprimierbarkeit mancher Daten ist das sogenannte Taubenschlagprinzip: Gibt es weniger Nistplätze für Tauben als es Tauben im Taubenschlag gibt, müssen sich zwangsläufig zwei oder mehr Tauben einen Nistplatz teilen. Auf einem n bit großen Speicherplatz kann man eine von 2n möglichen Informationen abspeichern, und auf einem Speicherplatz, der um ein bit kleiner ist, kann man folglich nur eine von halb so viel möglichen Informationen speichern: 16 bits → 216 = 65536 mögliche Informationen, 15 bits → 215 = 32768 mögliche Informationen. Unter der Annahme, man könne jede mögliche Datei um ein bit verkleinern, würde dies nach dem Taubenschlagprinzip bedeuten, dass jeder Speicherplatz gleichzeitig zwei verschiedene komprimierte Dateien enthalten müsste. Da aber in der verlustfreien Kompression eine umkehrbar eindeutige Zuordnung zwischen komprimierter und unkomprimierter Datei bestehen muss, verbietet sich dies. Gälte das Taubenschlagprinzip nicht, und gäbe es einen Algorithmus, der jede beliebige Datei um mindestens ein Bit komprimieren kann, könnte dieser rekursiv auf die jeweils komprimierte Datei angewendet werden – jede beliebige Information ließe sich auf 0 bit reduzieren. In der Praxis lassen sich nur dann bereits komprimierte Daten nochmals komprimieren, wenn im vorherigen Durchlauf ein nicht 100%ig effizienter Algorithmus verwendet wurde, welcher die Redundanz noch nicht vollständig entfernt hat (z. B. eine sehr große Datei voller Nullen wird zwei Mal mit gzip komprimiert). Aus diesen beiden Tatsachen ergibt sich die Schlussfolgerung, dass rein zufällige Daten (höchstwahrscheinlich) unkomprimierbar sind (da sie zumeist keine Struktur aufweisen), und dass zwar viele, aber nicht alle, Daten komprimiert werden können. Zwei Preisgelder, 100 Dollar für die erfolgreiche Kompression von einer Million zufälliger Ziffern und 5000 Dollar für die erfolgreiche Kompression einer Datei beliebiger Länge, die vom Preisstifter, Mike Goldman, erzeugt wird, wurden noch nicht ausbezahlt. Verlustfreie Kompression Bei der verlustfreien Kompression können die Originaldaten exakt aus den komprimierten Daten wiederhergestellt werden. Dabei geht keinerlei Information verloren. Im Wesentlichen nutzen verlustfreie Kompressionsverfahren die Redundanz von Daten aus, man spricht auch von Redundanzreduktion. Die theoretische Grundlage bildet die Informationstheorie (verwandt mit der algorithmischen Informationstheorie). Sie gibt durch den Informationsgehalt eine minimale Anzahl an Bits vor, die zur Kodierung eines Symbols benötigt werden. Verlustlose Kompressionsverfahren versuchen nun Nachrichten so zu kodieren, dass sie sich ihrer Entropie möglichst gut annähern. Text Texte, sofern sie aus Buchstaben bestehen oder als Zeichenketten abgespeichert sind, und somit nicht als Bild (Rastergrafik, typischerweise eine Bilddatei nach dem Einscannen eines Buches), belegen vergleichsweise wenig Speicherplatz. Dieser lässt sich durch ein Verfahren zur verlustfreien Kompression auf 20 % bis 10 % des ursprünglich von ihr benötigten Platzes reduzieren. Beispiele: Ausgangstext: AUCH EIN KLEINER BEITRAG IST EIN BEITRAG Kodiertext: AUCH EIN KLEINER BEITRAG IST /2 /4 Hier wurde erkannt, dass die Wörter EIN und BEITRAG zweimal auftauchen, und dadurch angegeben, dass diese mit den gerade zurückliegenden übereinstimmen. Bei genauerer Betrachtung könnte dann auch das in KLEINER enthaltene EIN entsprechend kodiert werden. Wörterbuchmethode Verwandt ist die tokenbasierte Kompression. Häufig wiederkehrende Schlüsselwörter werden durch Abkürzungen, Tokens, ersetzt. Ausgangstext: Print "Hallo"; Print "Hier" Kodiertext: 3F "Hallo"; 3F "Hier" Für die Zuordnung der Tokens zu den eigentlichen Wörtern muss entweder ein externes Wörterbuch vorhanden sein, oder in der komprimierten Datei ersichtlich/mit enthalten sein. Run length encoding (RLE) Bei der RLE, deutsch Lauflängenkodierung, werden identische Textbestandteile, die hintereinander stehen, nur einmal abgespeichert – mit der Anzahl ihrer Wiederholungen. Hier wird „ 10 Grad,“ drei Mal wiederholt: Ausgangstext: In den letzten Tagen betrug die Temperatur 10 Grad, 10 Grad, 10 Grad, und dann 14 Grad. Kodiertext: In den letzten Tagen betrug die Temperatur/3/ 10 Grad,/ und dann 14 Grad. Die Burrows-Wheeler-Transformation ist eine umkehrbare Operation, welche einen gegebenen Text so umformt, dass dieselben Buchstaben möglichst oft gleich hintereinander stehen. So können die Daten dann mit RLE komprimiert werden. Entropiekodierung Verfahren der so genannten Entropiekodierung: Huffman-Code (in modifizierter Form zum Beispiel für die Fax-Übertragung). Arithmetische Kodierung Der bekannte Morse-Code funktioniert nach einem ähnlichen Prinzip und dient als gutes Beispiel: Häufige Buchstaben der englischen Sprache (z. B. E = .) werden als kurze Codes abgespeichert, seltene als lange Codes (z. B. Q = _ _ . _). Als Beispiel ein Ausgangstext von 66 Zeichen Länge (Datenmenge 462 Bit bei 7 Bit pro Zeichen, siehe ASCII): WENN HINTER FLIEGEN FLIEGEN FLIEGEN, FLIEGEN FLIEGEN FLIEGEN NACH. Eine sehr einfache, aber nicht sehr effiziente Entropiekodierung besteht darin, alle Teile einer Nachricht (siehe Tabelle; „_“ steht für das Leerzeichen) nach ihrer Häufigkeit zu sortieren, und mittels binären Zahlen zu nummerieren: Der mit diesem Wörterbuch komprimierte Text lautet 10 100 1 1 1 101 1 1 1 11 und benötigt in binärer Kodierung 50 Bit, denn das Ergebnis enthält drei verschiedene Zeichen (0, 1 und das Trennzeichen „ “), also 2 Bit pro Zeichen. Die Trennzeichen sind hier notwendig, da dieser Code nicht präfixfrei ist. Der präfixfreie Huffman-Code, also folgendes Wörterbuch, ist effizienter, denn es führt direkt zu einem binären Ergebnis von 18 Bit Länge: 011001111000111010 In beiden Fällen muss aber auch das Wörterbuch in der komprimierten Datei abgespeichert werden – sonst lässt sich der Ausgangstext nicht rekonstruieren. Programmdateien Bei Programmdateien ist es kritisch, dass sie nach erfolgter Dekomprimierung wieder im ursprünglichen Zustand sind. Andernfalls wäre eine fehlerfreie bzw. korrekte Ausführung unwahrscheinlich. Komprimierte Programmdateien sind meist selbst wieder ausführbare Dateien. Sie bestehen aus einer Routine, die den Programmcode wieder dekomprimiert und anschließend ausführt. Dadurch ist die Kompression des Programms für den Benutzer vollkommen ‚transparent‘ (er bemerkt sie nicht). Anwendungsbeispiele sind UPX und Upack. Verlustbehaftete Kompression Bei der verlustbehafteten Kompression werden irrelevante Informationen entfernt, man spricht auch von Irrelevanzreduktion. Dabei geht ein Teil der Information aus den Originaldaten verloren, sodass aus den komprimierten Daten nicht mehr das Original rekonstruiert werden kann. Es wird ein Modell benötigt, das entscheidet, welcher Anteil der Information für den Empfänger entbehrlich ist. Verlustbehaftete Kompression findet meist in der Bild-, Video- und Audio-Übertragung Anwendung. Als Modell wird dort die menschliche Wahrnehmung zugrunde gelegt. Ein populäres Beispiel ist das Audio-Format MP3, das Frequenzmuster entfernt, die der Mensch schlecht oder gar nicht hört. Die theoretische Grundlage bildet die Rate-Distortion-Theorie. Sie beschreibt, welche Datenübertragungsrate mindestens nötig ist, um Informationen mit einer bestimmten Güte zu übertragen. Bilder, Videos und Tonaufnahmen Ton, Bild und Film sind Einsatzgebiete verlustbehafteter Kompression. Anders wären die oftmals enormen Datenmengen sehr schwer zu handhaben. Bereits die Aufnahmegeräte begrenzen das Datenvolumen. Die Reduktion der gespeicherten Daten orientiert sich an den physiologischen Wahrnehmungseigenschaften des Menschen. Die Kompression durch Algorithmen bedient sich dabei typischerweise der Wandlung von Signalverläufen von Abtastsignalen in eine Frequenzdarstellung. In der akustischen Wahrnehmung des Menschen werden Frequenzen oberhalb von ca. 20 kHz nicht mehr wahrgenommen und können bereits im Aufnahmesystem beschnitten werden. Ebenso werden existierende, leise Nebentöne in einem Klanggemisch nur schwer wahrgenommen, wenn zur exakt gleichen Zeit sehr laute Töne auftreten, so dass die unhörbaren Frequenzanteile vom Daten-Kompressions-System entfernt werden können (siehe Psychoakustik), ohne dass dies als störend vom Hörer wahrgenommen würde. Der Mensch kann bei einer Reduktion digitalisierter, akustischer Ereignisse (Musik, Sprache, Geräusche) auf Werte um etwa 192 kbit/s (wie bei vielen Internet-Downloads) kaum oder gar keine Qualitätsunterschiede zum unkomprimierten Ausgangsmaterial (so bei einer CD) feststellen. In der optischen Wahrnehmung des Menschen werden Farben weniger stark aufgelöst als Helligkeitsänderungen, daraus leitet sich die schon beim analogen Farbfernsehen bekannte YUV-422 Reduzierung ab. Kanten sind dagegen bedeutsamer, und es existiert eine biologische Kontrastanhebung (Machsche Streifen). Mit moderater Tiefpassfilterung zur Farbreduktion, zum Beispiel durch den auf DCT-Transformation basierenden JPEG-Algorithmus oder den neueren auf Wavelet-Transformation basierenden JPEG2000-Algorithmus, lässt sich die Datenmenge meist auf 10 % oder weniger der ursprünglichen Datenmenge reduzieren, ohne deutliche Qualitätsverringerungen. Bewegtbilder (Filme) bestehen aus aufeinanderfolgenden Einzelbildern. Erster Ansatz war, jedes Bild einzeln gemäß JPeg-Algorithmus zu komprimieren. Das resultierende Format ist Motion JPEG (entspricht MPEG-1, wenn dieses nur I-Frames enthält). Die heutzutage sehr viel höheren Kompressionsraten sind nur erreichbar, wenn man bei der Kodierung die Ähnlichkeit von benachbarten Bildern (engl. Frames) berücksichtigt. Dazu wird das Bild in kleinere Kästchen (typische Größen liegen zwischen 4×4 und 16×16 Pixel) zerlegt und es werden ähnliche Kästchen in schon übertragenen Bildern gesucht und als Vorlage verwendet. Die Einsparung ergibt sich daraus, dass statt des gesamten Bildinhalts nur noch die Unterschiede der an sich ähnlichen Kästchen übertragen werden müssen. Zusätzlich wird aus den Änderungen vom vorherigen zum aktuellen Bild gefolgert, in welche Richtung sich Bildinhalte wie weit verschoben haben; für den entsprechenden Bereich wird dann nur ein Verschiebungsvektor gespeichert. Kompressionsartefakte Als Kompressionsartefakte bezeichnet man Signalstörungen, die durch die verlustbehaftete Kompression verursacht werden. Anwendung in der Nachrichtentechnik Bei der Datenübertragung wird häufig die zu übertragende Datenmenge durch Kompression reduziert. In so einem Fall spricht man dann auch von Quellenkodierung. Die Quellenkodierung wird dabei häufig zusammen mit Kanalkodierung und Leitungskodierung verwendet, sollte aber nicht mit diesen verwechselt werden: Während die Quellencodierung überflüssige (redundante) Information einer Datenquelle reduziert, hat die Kanalcodierung die Aufgabe, durch zusätzlich eingebrachte Redundanz Übertragungs- bzw. Speicherfehler im Rahmen der Datenübertragung erkennen und korrigieren zu können. Die Leitungskodierung hingegen nimmt eine spektrale Anpassung des Signals an die Anforderungen des Übertragungskanals vor. Zeittafel der Kompressions-Algorithmen Die jahrhundertealte Stenografie kann als Datenkompression angesehen werden, welche der Handschrift eine möglichst hohe Datenrate verleiht 1833–1865 Entwicklung des Morse-Codes, welcher häufige Buchstaben in kurze Zeichen übersetzt und seltene Buchstaben in längere, was die Idee der Entropiekodierung vorzeichnet 1883 David Forsyth, Schachspieler und Journalist, publiziert eine Methode, mit welcher auf platzsparende Weise die Position von Schach-Figuren mit Lauflängenkodierung festgehalten wird → Forsyth-Edwards-Notation 1949 Informationstheorie, Claude Shannon 1949 Shannon-Fano-Kodierung 1952 Huffman-Kodierung, static 1964 Konzept der Kolmogorow-Komplexität 1975 Integer coding scheme, Elias 1977 Lempel-Ziv-Verfahren LZ77 1978 Lempel-Ziv-Verfahren LZ78 1979 Bereichskodierung (eine Implementierung arithmetischer Kodierung) 1982 Lempel-Ziv-Storer-Szymanski (LZSS) 1984 Lempel-Ziv-Welch-Algorithmus (LZW) 1985 Apostolico, Fraenkel, Fibonacci coding 1986 Move to front, (Bentley et al., Ryabko) 1991 Reduced Offset Lempel Ziv (ROLZ, auch LZRW4, Lempel Ziv Ross Williams) 1994 Burrows-Wheeler-Transformation (bzip2) 1995 zlib, freie Standardbibliothek für Deflate 1996 Lempel-Ziv-Oberhumer-Algorithmus (LZO), sehr schnelle Kompression 1997 Sequitur 1998 Lempel-Ziv-Markow-Algorithmus (LZMA) 2006 Hutter-Preis für beste Datenkompression 2009 PAQ, höchste Kompressionsraten auf Kosten sehr langer Laufzeit; Verwendung eines neuronalen Netzwerks (heute ZPAQ) 2011 Snappy, schneller Kodierer von Google 2011 LZ4, sehr schneller Kodierer 2013 zopfli, verbesserter Deflate-Kodierer 2015 Brotli, starke Kompression Bekannte Methoden zur Quellcodierung Datenübertragung MNP-1 bis MNP-10 (Microcom Networking Protocol) Fehlerkorrektur- und Datenkompressionsprotokolle der Firma Microcom Inc. für Modems, ein jahrelanger Standard. Wurde verbessert durch: V.42bis – Datenkompressionsprotokoll der ITU-T Biologie Sinneswahrnehmungen werden gefiltert, was auch eine Art der Kompression darstellt, genauer eine verlustbehaftete Kompression, da nur aktuell relevante Informationen wahrgenommen werden. Fehlendes wird bei Bedarf unbewusst ersetzt. So sehen menschliche Augen beispielsweise nur in einem kleinen Bereich (Fovea centralis) scharf, außerhalb dieses engen Blickfeldes werden fehlende Informationen durch Muster unbewusst ersetzt. Ebenso kann das menschliche Auge Helligkeitsunterschiede wesentlich besser wahrnehmen als Unterschiede im Farbton – diesen Umstand nutzt das in JPEG-Bildern verwendete YCbCr-Farbmodell und speichert den Farbwert mit einer wesentlich geringeren Präzision ab. Auch beim Hören werden schwache oder fehlende Signale unbewussterweise ersetzt, was sich Algorithmen wie MPEG (MP3) oder Vorbis zunutze machen. Siehe auch Kanalkodierung Canterbury Corpus Liste von Datenkompressionsprogrammen Liste von Dateinamenserweiterungen Weblinks Vergleich der Kompressionsleistung von über 250 Packprogrammen (englisch) LA – Verlustfreies Audioformat mit den angeblich höchsten Kompressionsraten (englisch) Data Compression – Systematisation by T. Strutz (englisch) Data compression FAQ (englisch) Lelewer, Debra, A.; Hirschberg, Daniel, S.: „Data Compression“; ACM Computing Surveys, 19, 1987, S. 261–297. Übersichtsartikel (englisch) Liste mit Kompressionsvergleichen (englisch) Einzelnachweise