THUNDER-2000 - WEB-PUBLISHING
Ulrichstr. 4
88527 Unlingen/Uig
Tel.: 0 73 74 / 9 10 83
Fax: 0 73 74 / 9 10 82
Mobil: 01 74 / 90 62 866
Mail: info@thunder-2000.com
|
THUNDER-2000 - WEB-PUBLISHING Tel.: 0 73 74 / 9 10 83 Mobil: 01 74 / 90 62 866 Mail: info@thunder-2000.com |
[Home] - [Magazin] - Assoziativ-Speicher
Bei Assoziativ-Speicher handelt es sich um das aus der Neuroinformatik stammende Problem, das Arbeiten des Gehirns auf den Computer zu übertragen. Dabei gilt das Prinzip, dass Eigenschaften eines Objekts gespeichert werden, um das Objekt wieder zu erkennen. Es handelt sich also um eine Art von Speicher, der auch aus verlustbehafteten Daten mit "hoher" Wahrscheinlichkeit wieder das Original rekonstruieren kann.
Zunächst die grobe und vereinfachte Theorie des menschlichen Gehirns: Dieses arbeitet auf der Basis von Nervenzellen, die sogenannten Synapsen, welche Informationen speichern können, vergleichbar einem Bit, also entweder an oder aus. Die Theorie ist nun, dass diese Synapsen für unterschiedliche Bereiche stehen, z.B. eine für süß und eine andere für sauer. In Zusammenarbeit können auch komplexere Informationen gespeichert werden, z.B. chinesisch süß-sauer.
Beispiel: ein Würfel spricht spezielle Synapsen an, z.B. die für eckig, Kanten, quadratisch und gleichzeitig werden andere Synapsen mit aktiviert. Es sind also immer Regionen im Gehirn aktiv. Diese anderen Synapsen geben uns dann die restlichen Informationen, die wir im Laufe unseres Lebens schon mit Würfeln gemacht haben.
Würfel Eigenschaften: eckig, Kanten, quadratisch, rollt nicht, Augenzahl, 6 Seiten
nicht aktive / direkt aktivierte / indirekt aktivierte Synapsen
Sollten Sie noch immer nicht überzeugt sein, dass auch Ihr Gehirn so arbeitet, dann lesen Sie mal folgenden Text:
Gmäeß eneir Sutide eneir elgnihcesn Uvinisterät, ist es nchit witihcg in wlecehr Rneflogheie die Bstachuebn in eneim Wrot snid, das ezniige was wcthiig ist, ist dass der estre und der leztte Bstabchue an der ritihcegn Pstoiion snid. Der Rset knan ein ttoaelr Bsinöldn sien, tedztorm knan man ihn onhe Pemoblre lseen. Das ist so, wiel wir nciht jeedn Bstachuebn enzelin leesn, snderon das Wrot als gseatems.
Sie werden sehen: Trotz der enormen Rechtschreibfehler können Sie den Text nahezu flüssig lesen. Ein Indiz für den Assoziativ-Speicher des menschlichen Gehirns.
Überträgt man diese Vorgehensweise jetzt noch stärker vereinfacht in die binäre Welt so kann man den Vorgang mit einer Matrix vergleichen, in welcher mehrere unterschiedliche Informationen gespeichert sind. Gibt man nun wieder einen Teil der gespeicherten Information in die Matrix so kann man durch simple Addition den Rest der Information rekonstruieren oder zumindest ähnliche Informationen finden.
Es ist offensichtlich, dass je weniger Informationen in der Matrix gespeichert sind, umso genauer und effizienter kann diese auch funktionieren. Gleichzeitig geht es nicht nur um die Informationsanzahl, sondern auch um die Informationsdichte, quasi die Anzahl der logischen 1 in der einzelnen Information. So sollte die Packungsdichte nicht die magische Grenze von 75% übersteigen. Es macht also Sinn nicht allgemeine und verbreitete Eigenschaften zu speichern, sondern eher spezielle um so die Informationsdichte zu verringern, hier ist eben weniger mehr.
 |
|
|
|
|
|
Auslesen anhand von Teilinformationen
|
|
Anwenden lassen sich Assoziativ-Speicher überall da, wo Informationen verloren gehen oder einfach nur so rekonstruiert werden müssen. (z.B. Text-, Sprach- und Bilderkennung, einfach dort wo der Faktor Mensch eine Rolle spielt)
Unter anderem kann man auch eine „unscharfe“ Volltextsuche in großen Datenmengen veranstalten. Dies kann unter Umständen eine Rechtschreibprüfung darstellen, zu dem im Folgenden näher eingegangen wird.
Zunächst überlegt man sich was das System denn so können sollte. Hauptsächlich also fehlerhafte Wörter finden und Verbesserungsvorschläge geben. Das Finden sollte kein Problem sein, ist ein Wort nicht in der Datenbank, so ist es wohl falsch. Nun zu der Suche nach Alternativen. Eine Möglichkeit ist es einfach ein SQL Statement mit den häufigsten Fehlern zu generieren und abzuschicken. Um die meisten möglichen Fehler abzufangen (Buchstabe vertauscht, verschrieben,…) muss man einen sehr langen Befehl aufschreiben, der bei einem geeigneten Artikelstamm noch mehr Zeit zur Ausführung beansprucht.
Also nun zu einem „richtigen“ System. Kurz man errechnet eine Art von Checksumme und speichert diese mit den Wörtern in der Datenbank. Dies erhöht zwar das Datenvolumen, die Vorteile überwiegen aber bei weitem.
Man überlegt sich Eigenschaften, die Wörter so haben können, z.B. ist ein „a“ enthalten oder nicht. Dies kann man natürlich mit den anderen Buchstaben ähnlich machen. Nun sind wir bei 26 Informationen (mit Sonderzeichen 30) welche aber erstens eine hohe Informationsdichte zur Folge hat, wie auch viel zu wenig um damit auch nur annähernd vernünftig zu arbeiten. Also müssen noch mehr Informationen her. Man nehme z.B. das gleiche noch einmal mit dem Anfangsbuchstagen -> sehr geringe Informationsdicht + 26 Informationen mehr. Immer noch zu wenig Informationen, denn bei etwa 200.000 Wörtern werden wahrscheinlich sehr viele Wörter Ähnlichkeit mit unserem gesuchten haben.
Eine Lösung: Buchstaben Tupel (z.B. „aa“, „ab“, „ac“, ...) nun sind dies schon mal ansehnliche 26² = 676 Eigenschaften. Zur Information: wären es bei 3er Tupeln schon 26³ = 17576 Eigenschaften. Mehr Eigenschaften können nicht schaden, aber nicht übertreiben, zuviel ist auch nicht gut, sonst geht die gewünschte „Unschärfe“ und Geschwindigkeit verloren.
Die gefundenen Eigenschaften müssen nun nur noch passend gespeichert werden. Es empfiehlt sich, dies möglichst so zu erreichen, dass vordefinierte Binäroperationen ausgeführt werden können (z.B. bei einem Feld vom Typ Integer).
Wenn man nun ein Wort falsch geschrieben hat, so berechnet man einfach, mit demselben Algorithmus, die Checksumme dieses fehlerhaften Wortes und lässt es über die Datenbank „laufen“. Was soviel heißt, man erstellt ein SQL Query, welches die Checksumme des „falschen“ Wortes mit der Checksumme der in der Datenbank gespeicherten Wörter vergleicht (Bitweise XOR). Nun zählt man noch die vorhandenen 1 (Hamming Norm) und hat die „Fehleranzahl“ (je kleiner umso besser, beste Übereinstimmung also bei 0) für dieses Wort errechnet. Nun braucht man nur die Wörter auszugeben, deren „Fehleranzahl“ am kleinsten ist.
Wie man sieht werden die „ähnlichsten“ Wörter mit einer geringen Fehlerquote gesegnet, also genau dass was eine Rechtschreibprüfung denn so braucht. Nun brauchen diese Wörter nur noch als Alternativen ausgegeben zu werden.
Hohe Fehlertoleranz in der Abfrage (je mehr Zeichen um so mehr Fehler werden toleriert)
Hohe Geschwindigkeit, da Bit-Operationen direkt und schnell ausgeführt werden
Assoziativ-Speicher sind sehr gut geeignet, um Informationen unscharf zu speichern. Dadurch erhält man eine Möglichkeit, Fehler zu tolerieren. Unser Rechtschreibungsbeispiel würde so keine Anwendung finden, da es einige kleine Details aulässt. Aber das Prinzip funktioniert einwandfrei. Auch in der Bilderkennung und –Analyse bringt diese Methode große Vorteile.(CK, überarbeitet von MB)
