Memorizzazione di dati n-grammi

11

Speravo di fare un brainstorming un po 'sul tema della memorizzazione dei dati di n -gram. Nel mio progetto, sto cercando di risolvere problemi linguistici in cui conosco tutti gli elementi di dati ( n -1) e voglio indovinare statisticamente il mio n usando l'interpolazione lineare su tutto il materiale applicabile < em> n -grams. (Sì, c'è un tagger che assegna tag a parole conosciute in base al suo lessico e un albero di suffisso che cerca di indovinare il tipo di parola per le parole sconosciute, il componente n -gram discusso qui sarà incaricato di risolvere l'ambiguità.)

Il mio approccio iniziale sarebbe quello di memorizzare semplicemente tutti i n -grams osservati (per n = 1..3, cioè monogram, bigram, trigram) in rispettivi SQL database e chiamiamola un giorno. Ma i requisiti del mio progetto possono cambiare per includere altre lunghezze vettoriali ( n ), e vorrei che la mia applicazione si adattasse a 4 grammi senza molto lavoro (aggiornamento dello schema, aggiornamento del codice dell'applicazione, ecc. .); idealmente, direi semplicemente alla mia applicazione di lavorare con 4 grammi ora senza dover modificare molto (o affatto) il codice e addestrare i suoi dati da una determinata fonte di dati.

Per riassumere tutti i requisiti:

  • Possibilità di memorizzare n -gram data (inizialmente per n = {1, 2, 3}
  • Possibilità di cambiare i tipi di n -gram dovrebbero essere usati (tra le esecuzioni dell'applicazione)
  • Capacità di (ri) addestrare n -gram dati (tra le esecuzioni dell'applicazione)
  • Capacità di interrogare l'archivio dati (ad es. se ho osservato A, B, C, mi piacerebbe sapere l'oggetto osservato più frequentemente per quello che potrebbe succedere usando il mio addestrato 4-, 3-, 2-, 1- set di dati del grammo)

    L'applicazione molto probabilmente sarà pesante per la lettura, molto probabilmente i set di dati non saranno riqualificati che spesso

  • La soluzione utilizza .NET Framework (fino a 4.0)

Ora quale design sarebbe più adatto per un simile compito?

  • Una tabella fissa gestita da un server SQL (MSSQL, MySQL, ...) per ogni n (ad esempio tavoli dedicati per bi-grammi, tri-grammi, ecc.)
  • O una soluzione per database di documenti NoSQL che memorizza il primo n -1 come chiave del documento, e il documento stesso contiene il valore n -th e le frequenze osservate ?
  • O qualcosa di diverso?
posta Manny 01.04.2011 - 13:18
fonte

3 risposte

8

Dato che non conoscerai la gamma ottimale di N, vorresti sicuramente essere in grado di cambiarlo. Ad esempio, se la tua applicazione prevede la probabilità che un determinato testo sia in inglese, probabilmente vorrai usare il carattere N-gram per N 3..5. (Questo è quello che abbiamo trovato sperimentalmente.)

Non hai condiviso i dettagli sulla tua applicazione, ma il problema è abbastanza chiaro. Si desidera rappresentare i dati N-gram in un database relazionale (o soluzione basata su documenti NoSQL). Prima di suggerire una mia soluzione, potresti dare un'occhiata ai seguenti approcci:

  1. Come archiviare meglio Google ngram in un database ?
  2. Memorizzazione di n-grammi nel database in < n numero di tabelle
  3. Gestione di Google Web 1T 5 grammi con database relazionale

Ora, non avendo letto nessuno dei link sopra, suggerisco un semplice approccio al database relazionale che usa più tabelle, una per ogni dimensione di N-grammo. Puoi inserire tutti i dati in una singola tabella con le colonne massime necessarie (ad esempio, memorizzare i bigram e i trigram in ngram_4, lasciando le colonne finali nulle), ma ti consiglio di partizionare i dati. A seconda del tuo motore di database, una singola tabella con un numero elevato di righe può avere un impatto negativo sulle prestazioni.

  create table ngram_1 (
      word1 nvarchar(50),
      frequency FLOAT,
   primary key (word1));

  create table ngram_2 (
      word1 nvarchar(50),
      word2 nvarchar(50),
      frequency FLOAT,
   primary key (word1, word2));

  create table ngram_3 (
      word1 nvarchar(50),
      word2 nvarchar(50),
      word3 nvarchar(50),
      frequency FLOAT,
   primary key (word1, word2, word3));

  create table ngram_4 (
      word1 nvarchar(50),
      word2 nvarchar(50),
      word3 nvarchar(50),
      word4 nvarchar(50),
      frequency FLOAT,
   primary key (word1, word2, word3, word4));

Successivamente, ti darò una query che restituirà la parola successiva più probabile a tutte le tue tabelle ngram. Ma prima, ecco alcuni dati di esempio che dovresti inserire nelle tabelle precedenti:

  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'building', N'with', 0.5)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'hit', N'the', 0.1)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'man', N'hit', 0.2)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'the', N'bat', 0.7)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'the', N'building', 0.3)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'the', N'man', 0.4)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'with', N'the', 0.6)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'building', N'with', N'the', 0.5)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'hit', N'the', N'building', 0.3)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'man', N'hit', N'the', 0.2)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'the', N'building', N'with', 0.4)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'the', N'man', N'hit', 0.1)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'with', N'the', N'bat', 0.6)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'building', N'with', N'the', N'bat', 0.5)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'hit', N'the', N'building', N'with', 0.3)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'man', N'hit', N'the', N'building', 0.2)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'the', N'building', N'with', N'the', 0.4)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'the', N'man', N'hit', N'the', 0.1)

Per interrogare la prossima parola più probabile, dovresti usare una query come questa.

  DECLARE @word1 NVARCHAR(50) = 'the'
  DECLARE @word2 NVARCHAR(50) = 'man'
  DECLARE @word3 NVARCHAR(50) = 'hit'
  DECLARE @bigramWeight FLOAT = 0.2;
  DECLARE @trigramWeight FLOAT = 0.3
  DECLARE @fourgramWeight FLOAT = 0.5

  SELECT next_word, SUM(frequency) AS frequency
  FROM (
    SELECT word2 AS next_word, frequency * @bigramWeight AS frequency
    FROM ngram_2
    WHERE word1 = @word3
    UNION
    SELECT word3 AS next_word, frequency * @trigramWeight AS frequency
    FROM ngram_3
    WHERE word1 = @word2
      AND word2 = @word3
    UNION
    SELECT word4 AS next_word, frequency * @fourgramWeight AS frequency
    FROM ngram_4
    WHERE word1 = @word1
      AND word2 = @word2
      AND word3 = @word3
    ) next_words
  GROUP BY next_word
  ORDER BY SUM(frequency) DESC

Se aggiungi altre tabelle ngram, dovrai aggiungere un'altra clausola UNION alla query sopra. Si potrebbe notare che nella prima query ho usato word1 = @ word3. E nella seconda query, word1 = @ word2 AND word2 = @ word3. Questo perché abbiamo bisogno di allineare le tre parole nella query per i dati di ngram. Se vogliamo la prossima parola più probabile per una sequenza di tre parole, dovremo controllare la prima parola nei dati del bigram contro la ultima parola delle parole nella sequenza.

Puoi modificare i parametri di peso come desideri. In questo esempio, ho assunto che i grammi ordinali più alti "n" saranno più affidabili.

P.S. Vorrei strutturare il codice del programma per gestire un numero qualsiasi di tabelle ngram_N tramite la configurazione. Potresti cambiare dichiaratamente il programma per usare l'intervallo N-grammi N (1..6) dopo aver creato le tabelle ngram_5 e ngram_6.

    
risposta data 08.09.2011 - 13:52
fonte
2

Contrariamente a quanto suggeriscono gli altri, suggerirei di evitare qualsiasi struttura di dati più complessa di una hashmap o di un archivio di valori-chiave.

Tieni a mente i tuoi requisiti di accesso ai dati: a) Richieste al 99% - interrogare ngram "aaa-bbb-ccc" e recuperare il valore (o 0) b) richieste dell'1% - inserimento / aggiornamento di un conteggio di ngram specifici c) non c'è (c).

Il modo più efficace è recuperarlo con una singola ricerca. Puoi usare un separatore out-of-bounds (o escape) per combinare l'intero n-gram in una singola stringa (ad esempio "alpha | beta | gamma" per 3gram, "alpha" per unigram, ecc.) E solo per recuperarlo ( per l'hash di quello). È così che un bel po 'di software di PNL lo fa.

Se i dati di ngram sono piccoli (ad esempio, < 1 GB) e si adattano alla memoria, suggerirei di utilizzare un'efficace struttura di memoria in-programma (hashmaps, alberi, tentativi, ecc.) per evitare un sovraccarico; e basta serializzare / deserializzare su file flat. Se i dati di ngram sono terabyte o più, è possibile scegliere gli archivi di valori-chiave NoSQL suddivisi su più nodi.

Per prestazioni extra, potresti voler sostituire tutte le parole ovunque con gli ID interi in modo che l'algoritmo principale non veda affatto (lentamente) le stringhe; quindi è leggermente diverso implementare la stessa idea.

    
risposta data 29.05.2013 - 18:27
fonte
1

Non il più efficiente, ma semplice e integrato nel database come desideri:

Table: word
Colums:
word (int, primary key) - a unique identifier for each word
text (varchar) - the actual word

Table: wordpos
Columns:
document (int) - a unique identified for the document of this word
word (int, foreign key to word.word) - the word in this position
pos (int) - the position of this word (e.g., first word is 1, next is 2, ...)

wordpos dovrebbe avere indici su documento e pos

I bigram sono:

select word1.text as word1, word2.text as word2
from wordpos as pos1, wordpos as pos2, word as word1, word as word2
where pos1.document = pos2.document
      and pos1.pos = pos2.pos - 1
      and word1.word = pos1.word
      and word2.word = pos2.word

Quindi puoi contare () e raggruppare la tua strada verso le frequenze e le cose.

Per passare ai trigram, è facile generare questa stringa per includere una word3.

L'ho già fatto prima (anche se l'SQL lì sopra è probabilmente un po 'arrugginito). Ho optato per una serie di file flat che potevano essere cercati facilmente e poi trasmessi dal disco. Un po 'dipende dal tuo hardware come farlo meglio.

    
risposta data 28.04.2011 - 18:17
fonte

Leggi altre domande sui tag