So sammeln Sie Bigrams für ein beliebiges Gehäuse auf einem Heimcomputer

In der modernen Computerlinguistik sind Bigramme oder allgemein n-Gramm ein wichtiges statistisches Werkzeug. In diesem Artikel erklären wir Ihnen, auf welche Schwierigkeiten Sie bei der Berechnung von Bigrammen für eine große Anzahl von Texten stoßen können, und geben einen Algorithmus an, der auf jedem Heimcomputer verwendet werden kann.

Ein Bigram sind zwei Wörter, die in einem Text oder in unserem Fall in einem Textkorpus nebeneinander stehen. Zum Beispiel in einem Satz:

Es war ein heißer Sommer.
1 2 3 4 5 (das Leerzeichen nach dem Sommer ist kein Tippfehler oder Fehler)

Es wird solche Bigramme geben:

  • Es war
  • es war heiß
  • im heißen Sommer
  • im Sommer.

Bigrams bestehen streng genommen nicht aus Worten, sondern aus Token. Token, d.h. Eine unteilbare Einheit im Rahmen unserer Aufgabe ist entweder ein Wort oder ein Satzzeichen. Tokenisierung ist kein einfaches Thema, daher gehen wir davon aus, dass unser Körper bereits in Token und Angebote unterteilt ist. Um ein Angebot in eine Liste von Token umzuwandeln, genügt es, es durch ein Leerzeichen zu trennen.

Unsere Aufgabe wird es sein, diese Liste zu bekommen:

  • Das war 190360
  • es war heiß 1017
  • heißer Sommer 2621
  • im Sommer. 42146

wobei die Zahl angibt, wie oft ein Bigramm in dem gesamten Fall gefunden wird.

Manchmal gestatten wir uns, im Text den Begriff Doppelkombination als Synonym für das Wort Bigram zu verwenden.

In diesem Artikel wurde absichtlich auf alle Implementierungsdetails verzichtet Der Ansatz ist an sich interessant und es ist nicht schwierig, ihn in Ihrer bevorzugten Programmiersprache zu implementieren. Darüber hinaus enthält die Implementierung genügend interessante Details, um in einem separaten Artikel darüber zu sprechen. Die Mindestanzahl an Erläuterungen wird in Java angegeben.

Naiver Ansatz


  • durch den Rumpf laufen
  • Extrahieren Sie Bigramme aus jedem Satz
  • Lesen Sie sie mit einer Multiset-Datenstruktur (in Java ist dies Multiset) oder ConcurrentHashMultiset in Multithread-Version)

In einem relativ kleinen und sauberen Fall könnte es funktionieren, aber im allgemeinen Fall wird bei einer naiven Herangehensweise das Gedächtnis aufgebraucht, bevor Sie das gesamte Textfeld zählen können.

Fügen Sie Zwischenschnitte hinzu


Es ist sehr einfach, einen naiven Ansatz in einen funktionierenden umzuwandeln, wenn Sie ihn ein wenig modifizieren:

  • durch den Rumpf laufen
  • Extrahieren Sie Bigramme aus jedem Satz
  • Zählen Sie sie mit einem Multiset
  • Sobald wir sehen, dass der Speicher beendet ist, löschen wir den Zähler und löschen die Bigrams, die an diesem Punkt aufgetreten sind und die den Schwellenwert unterschritten haben

Diese Modifikation liefert einen vollständig funktionierenden Algorithmus, aber das Abschneiden bringt ein Problem mit sich: Neben unnötigem Rauschen wie unregelmäßigen Tippfehlern und Fehlern werden viele nützliche Informationen zu seltenen Wörtern entfernt. Wenn zum Beispiel ein Lexem (ein Satz von Wortformen) 1000-mal im Korpus vorkommt, kann jede seiner einzelnen Wortformen beispielsweise weniger als 200-mal pro Korpus vorkommen, und was können wir über doppelte Kombinationen sagen.

Unsere Aufgabe ist es, die Bigramme so ehrlich wie möglich zu zählen, ohne Zwischenschnitte zu verwenden.

Wir verwenden eine Festplatte als temporären Speicher


RAM ist jetzt relativ günstig, aber es lohnt sich immer noch. Außerdem können Sie für viele Versionen von Laptops, die größer als 16 Gigabyte sind, diese nicht installieren, wenn Sie dies wünschen - die Plattformbeschränkung. Es gibt kein Problem mit dem Speicherplatz - er kostet erheblich weniger und Sie können jederzeit ein externes Laufwerk verwenden, wenn Sie dies wünschen.

Wenn semantische Tags erwähnt werden, werden #hard_drive und #algorithm im Speicher eingeblendet und sortieren und sortierte Listen zusammenführen, die viele in der Schule in Pascal geschrieben haben. Die diesen Algorithmen zugrunde liegenden Ideen eignen sich gut zur Lösung unseres Problems.

Schematische Darstellung der Lösung des Problems


Bevor wir zu den Details übergehen, werden wir ein schematisches Diagramm der Lösung des Problems präsentieren:

  1. Teilen Sie den Fall in ungefähr gleiche Blöcke auf, z. B. jeweils 1 GB.
  2. Zählen Sie die Bigramme für jeden Block separat, sortieren Sie sie in lexikografischer Reihenfolge und schreiben Sie auf die Festplatte.
  3. Führen Sie mithilfe des Algorithmus zum Zusammenführen geordneter Listen einzelne Dateien mit zwei Kombinationen zu einer zusammen, und addieren Sie die Anzahl der Vorkommen für übereinstimmende Bigramme.

Die Größe jedes Blocks kann nach Belieben gewählt werden (lesen Sie: entsprechend der Anzahl der installierten RAM), aber bei den meisten Aufgaben ist die Größe in Gigabyte mehr als praktisch. Sie können auch mit einem monolithischen Fall arbeiten, indem Sie entsprechend der Größe des verarbeiteten Texts im Programm Kürzungen vornehmen, das Ergebnis auf der Festplatte ablegen und Datenstrukturen löschen.

Wenn Sie den Algorithmus aus der Vogelperspektive betrachten, können Sie zu den Details gehen.

Zähle die Bigramme für jeden Block


Um die optimale Architektur für einen Doppelzähler zu erstellen, werden zwei wichtige Anforderungen berücksichtigt:

  1. Wir wollen in mehreren Threads zählen.
  2. Bei der Ausgabe müssen Sie eine Liste der Bigramme in lexikografischer Reihenfolge erhalten.

Es stellt sich heraus, dass diese beiden Aufgaben effektiv zusammen gelöst werden können. Es wird vorgeschlagen, anstelle einer einstufigen Karte (ein Multiset ist im Wesentlichen eine Schlüsselzählerkarte)

ConcurrentHashMultiset

um bigrams zu berechnen, benutze eine karte von karten:

ConcurrentMap>

Das Experiment zeigt, dass die Multithread-Berechnung von Kombinationen unter Verwendung beider Datenstrukturen in ungefähr derselben Zeit durchgeführt wird, das Sortieren unter Verwendung einer Karte mit zwei Ebenen jedoch viel schneller ist, weil Sie können die Schlüssel der externen und internen Karten unabhängig voneinander sortieren.

Ein weiterer großer Vorteil einer Karte mit zwei Ebenen besteht darin, dass Sie sehr schnell zusätzliche Filter entsprechend dem Bigram durchführen können. Überprüfen Sie beispielsweise deren Eintrag im Wörterbuch oder führen Sie sogar eine Normalisierung durch (schnelle Fahrt -> schnelle Fahrt). Es ist sehr teuer, diese Vorgänge durchzuführen, bevor Sie dieselben Kombinationen gruppieren. Der gleiche Vorgang wird mehrmals ausgeführt.

Kombinieren Sie die Ergebnisse für alle Blöcke


Bei der Ausgabe des vorherigen Algorithmus haben wir also viele Dateien mit Einträgen der Form:

bigram1 count1
bigram2 count2
...
bigramN countN

wo die Schlüssel in lexikographischer Reihenfolge sortiert sind. Unsere Aufgabe ist es, diese Dateien zu einer zu kombinieren und die Anzahl der Vorkommen für übereinstimmende Schlüssel zu addieren. Die Aufgabe des Summierens der beiden Dateien wird als trivial betrachtet und ohne weitere Erklärung überlassen.

Die allgemeine Aufgabe, alle Dateien zu kombinieren, kann mit der Batteriedatei gelöst werden, indem der Reihe nach Dateien einzelner Blöcke hinzugefügt werden:

((((((N1 + N2) + N3) + N4) + N5) + N6) + N7)...

Diese Kampagne ist jedoch wirkungslos, weil Nach einer Anzahl von Iterationen, werden wir auf eine relativ große Batterie relativ kleine Dateien von einzelnen Blöcken und verwendet hinzufügen für die meiste Zeit verbringen auf das Lesen von Daten von der Platte und auf die Platte geschrieben. Es ist viel rentabler, eine solche Strategie zu entwickeln, bei der Blöcke mit ungefähr gleicher Größe bei jeder Iteration aufsummiert werden, da die übereinstimmenden Schlüssel zu einem Datensatz zusammengefasst werden und die resultierende Datei kleiner ist als die Summe der beiden ursprünglichen.

Ein Implementierungsframework für die Zusammenführungssortierung, das eine Rekursion verwendet, eignet sich hervorragend für die Implementierung. Für 15 Dateien sieht es schematisch so aus (für die Zusammenführungsfunktion ist der erste Index aktiviert, der zweite ist ausgeschlossen):

| _ Zusammenführen (0, 15) = Zusammenführen (0, 7) + Zusammenführen (7, 15)
  | _ Zusammenführen (0, 7) = Zusammenführen (0, 3) + Zusammenführen (3, 7)
    | _ Zusammenführen (0, 3) = 0 + Zusammenführen (1, 3)
      | _ merge (1, 3) = 1 + 2
    | _ Zusammenführen (3, 7) = Zusammenführen (3, 5) + Zusammenführen (5, 7)
      | _ merge (3, 5) = 3 + 4
      | _ merge (5, 7) = 5 + 6
  | _ Zusammenführen (7, 15) = Zusammenführen (7, 11) + Zusammenführen (11, 15)
    | _ Zusammenführen (7, 11) = Zusammenführen (7, 9) + Zusammenführen (9, 11)
      | _ merge (7, 9) = 7 + 8
      | _ merge (9, 11) = 9 + 10
    | _ Zusammenführen (11, 15) = Zusammenführen (11, 13) + Zusammenführen (13, 15)
      | _ merge (11, 13) = 11 + 12
      | _ Merge (13, 15) = 13 + 14

Infolgedessen führt der Algorithmus dieselben 14 Fusionen durch, arbeitet jedoch mit der Batterieoption wesentlich effizienter. Die theoretischen Speicheranforderungen des Zusammenführungsalgorithmus sind O (1), aber in der Praxis wird Speicher nur für Lese- und Schreibpuffer zugewiesen.

Abschließend


Unter Verwendung des obigen Ansatzes ist es möglich, nicht nur Bigramme in dem Fall, sondern auch n-Gramme für jedes beliebige n zu sammeln. Dort müssen Sie möglicherweise kleinere Blöcke verwenden und häufig Zwischenergebnisse auf die Festplatte werfen.

Wie wir zu Beginn sagten, verdienen Implementierungsdetails eine separate Diskussion und wir werden im nächsten Artikel darüber sprechen.

Jetzt auch beliebt: