Nur zum Spaß möchte ich die bedingten Wahrscheinlichkeiten zählen, dass ein Wort (aus einer natürlichen Sprache) in einem Text erscheint, abhängig von der letzten und vorletztes Wort. I.e. Ich würde eine große Menge von z.B. Englisch Texte und zählen, wie oft jede Kombination n(i|jk)
und n(jk)
erscheint (wo j,k,i
sind Sucessive Worte).Speichern und aktualisieren Sie riesige (und sparse?) Multi-dimensionalen Array effizient bedingte Wahrscheinlichkeiten zu zählen
Der naive Ansatz wäre, ein 3-D-Array (für n(i|jk)
) zu verwenden, eine Zuordnung von Wörtern zu verwenden, um in 3 Dimensionen zu positionieren. Das Positionssuchen könnte effizient unter Verwendung von trie
s durchgeführt werden (zumindest ist das meine beste Schätzung), aber bereits für O (1000) Wörter würde ich auf Speicherbeschränkungen stoßen. Aber ich denke, dass dieses Array nur spärlich gefüllt sein würde, die meisten Einträge wären null, und ich würde so viel Speicher verschwenden. Also kein 3D-Array.
Welche Datenstruktur wäre besser geeignet für einen solchen Anwendungsfall und immer noch effizient, um viele kleine Updates zu machen, wie ich sie mache, wenn ich das Aussehen der Wörter zähle? (Vielleicht ist es eine ganz andere Art und Weise, dies zu tun?)
(Natürlich muss ich auch n(jk)
zählen, aber das ist einfach, denn es ist nur 2-D :) Die Sprache der Wahl ist C++, denke ich.
Ein bodenständiger Ansatz, nur mit STL. Könnte die beste Sache für einen Start sein. Ich mag die Art, wie man eine Map benutzt, um die (int, int) -Tupel zu speichern. – fuenfundachtzig
Nun, ich habe die Frage offen gelassen, um die Leute zu motivieren, eine alternative Antwort zu geben. Ich frage mich immer noch, ob es eine effizientere (im Hinblick auf den Speicherverbrauch) Weise gibt, die 'n (k | ij)' Tabelle zu speichern. Ich könnte mir vorstellen, dass die Karte ziemlich viel Overhead bringt? – fuenfundachtzig
@fuenfundachtzig Wenn die Tabelle spärlich ist, ist die Karte effizienter (Sie können davon ausgehen, dass die Wahrscheinlichkeit Null ist, wenn ein Schlüssel nicht in der Karte vorhanden ist). Wenn nicht, ist die dichte Datenstruktur, die alle möglichen Ergebniswahrscheinlichkeiten für eine lexikographische Anordnung von Eingaben speichert, am effizientesten (wenn die vollständige gemeinsame Verteilung notwendig ist). Wenn die gemeinsame Verteilung in unabhängige Verteilungen zerlegt werden kann, ist natürlich das Speichern dieser unabhängigen Verteilungen effizienter (siehe Lewis-Produkt-Approximationen). Dies sind nur Implementierungen der Karte. Also: Sie sollten die Antwort akzeptieren. – user