Armazenamento de dados n-grama

Eu esperava refletir um pouco sobre o assunto de armazenar dados de n- grama. No meu projeto, estou tentando resolver problemas linguísticos em que conheço todos os itens de dados ( n -1) e quero adivinhar estatisticamente meu n usando interpolação linear em todos os n- gramas aplicáveis . (Sim, existe um marcador que atribui marcadores a palavras conhecidas de acordo com seu léxico e uma árvore de sufixos que tenta adivinhar o tipo de palavra para palavras desconhecidas; o componente n -gram discutido aqui será encarregado de resolver a ambuguidade.)

Minha abordagem inicial seria simplesmente armazenar todos os dados de n- gramas observados (para n = 1..3, isto é, monograma, bigram, trigram) nos respectivos bancos de dados SQL e chamá-lo por dia. Mas os requisitos do meu projeto podem mudar para incluir outros comprimentos de vetores ( n ), e eu gostaria que meu aplicativo se adaptasse a 4 gramas sem muito trabalho (atualização do esquema, atualização do código do aplicativo etc.); idealmente, eu simplesmente diria ao meu aplicativo para trabalhar com 4 gramas agora sem ter que alterar muito o código (ou nada) e treinar seus dados a partir de uma determinada fonte de dados.

Para resumir todos os requisitos:

• Capacidade de armazenar dados de n- gramas (inicialmente para n = {1, 2, 3}
• Capacidade de alterar quais tipos de n- gramas devem ser usados ​​(entre as execuções de aplicativos)
• Capacidade de (re) treinar dados do diagrama n (entre execuções do aplicativo)

• Capacidade de consultar o armazenamento de dados (por exemplo, se eu tiver observado A, B, C, eu gostaria de saber o item mais frequentemente observado para o que pode ser seguido usando meus conjuntos de dados treinados de 4, 3, 2, 1 grama )

  O aplicativo provavelmente terá muita leitura, os conjuntos de dados provavelmente não serão treinados com frequência

• A solução emprega o .NET Framework (até 4.0)

Agora, qual projeto seria mais adequado para essa tarefa?

• Uma tabela fixa gerenciada por um servidor SQL (MSSQL, MySQL, ...) para cada n (por exemplo, tabelas dedicadas para bi-gramas, tri-gramas, etc.)
• Ou uma solução de banco de dados de documentos NoSQL que armazena o primeiro n -1 como a chave do documento, e o próprio documento contém o n- ésimo valor e as frequências observadas?
• Ou algo diferente?

Como você não conhece a faixa ideal de N, você definitivamente deseja alterá-la. Por exemplo, se seu aplicativo predizer a probabilidade de um determinado texto ser inglês, você provavelmente desejaria usar o N-gramas de caracteres para N3..5. (Foi o que descobrimos experimentalmente.)

Você não compartilhou detalhes sobre seu aplicativo, mas o problema é claro o suficiente. Você deseja representar dados N-gram em um banco de dados relacional (ou solução baseada em documento NoSQL). Antes de sugerir uma solução própria, dê uma olhada nas seguintes abordagens:

1. Como armazenar melhor os ngrams do Google em um banco de dados?
2. Armazenando n-gramas no banco de dados em <n número de tabelas
3. Gerenciamento do Google Web 1T de 5 gramas com banco de dados relacional

Agora, não tendo lido nenhum dos links acima, sugiro uma abordagem de banco de dados relacional simples usando várias tabelas, uma para cada tamanho de N-grama. Você pode colocar todos os dados em uma única tabela com o máximo de colunas necessárias (por exemplo, armazenar bigrams e trigramas no ngram_4, deixando as colunas finais nulas), mas recomendo particionar os dados. Dependendo do mecanismo do banco de dados, uma única tabela com um grande número de linhas pode afetar negativamente o desempenho.

  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));

A seguir, apresentarei uma consulta que retornará a próxima palavra mais provável, considerando todas as suas tabelas ngram. Mas primeiro, aqui estão alguns dados de exemplo que você deve inserir nas tabelas acima:

  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)

Para consultar a próxima palavra mais provável, use uma consulta como esta.

  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 você adicionar mais tabelas ngram, precisará adicionar outra cláusula UNION à consulta acima. Você pode notar que, na primeira consulta, usei word1 = @ word3. E na segunda consulta, word1 = @ word2 AND word2 = @ word3. Isso ocorre porque precisamos alinhar as três palavras na consulta para os dados ngram. Se desejarmos a próxima palavra mais provável para uma sequência de três palavras, precisamos verificar a primeira palavra nos dados do bigram com a última palavra das palavras na sequência.

Você pode ajustar os parâmetros de peso conforme desejar. Neste exemplo, assumi que gramas ordinais "n" mais altos serão mais confiáveis.

PS: Eu estruturaria o código do programa para lidar com qualquer número de tabelas ngram_N via configuração. Você pode alterar declarativamente o programa para usar o intervalo N-grama N (1..6) após criar as tabelas ngram_5 e ngram_6.

Ao contrário do que os outros estão sugerindo, sugiro evitar estruturas de dados mais complexas que um mapa de hash ou um armazenamento de valores-chave.

Lembre-se de seus requisitos de acesso a dados: a) 99% de solicitações - consulte o ngram "aaa-bbb-ccc" e recupere o valor (ou 0) b) 1% de solicitações - inserindo / atualizando uma contagem de ngram específico c) não há (c)

A maneira mais eficaz é recuperá-lo com uma única pesquisa. Você pode usar um separador fora dos limites (ou com escape) para combinar o n-grama completo em uma única sequência (por exemplo, "alpha | beta | gamma" para 3gram, "alpha" para unigrama, etc.) e apenas buscar isso ( pelo hash disso). É assim que muitos softwares de PNL fazem isso.

Se os dados do seu ngram forem pequenos (digamos, <1 gb) e caberem na memória, sugiro usar uma estrutura de memória eficiente no programa (hashmaps, árvores, tentativas etc.) para evitar sobrecarga; e apenas serialize / desserialize para arquivos simples. Se seus dados ngram forem terabytes ou mais, você poderá escolher armazenamentos de valores-chave NoSQL divididos em vários nós.

Para um desempenho extra, convém substituir todas as palavras em todos os lugares por IDs inteiros para que seu algoritmo principal não veja nenhuma string (lenta); então é um pouco diferente implementar a mesma ideia.

Não é o mais eficiente, mas simples e integrado ao banco de dados como você deseja:

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, ...)

O wordpos deve ter índices no documento e na pos.

bigrams são:

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

Então você pode contar () e agrupar o seu caminho para frequências e outras coisas.

Para mudar para trigramas, é fácil gerar essa sequência para incluir uma palavra3.

Eu já fiz isso antes (na verdade, o SQL lá em cima provavelmente está um pouco enferrujado). Eu me conformei com um conjunto de arquivos simples que poderiam ser buscados facilmente e depois transferidos para fora do disco. Meio que depende do seu hardware como fazê-lo melhor.

Ao tentar melhorar as pesquisas simples dos meus aplicativos em bigrams e trigramas a partir de unigramas, vi a sua pergunta.

Se um dos requisitos é a capacidade de consultar um sistema de arquivos ou banco de dados distribuído, isso também pode ser interessante para você: o artigo Pibiri e Venturini 2018 "Manipulando Maciços Conjuntos de Dados N-Gram de Forma Eficiente" descreve uma maneira eficiente de armazenar dados n-grama em termos de tempo de execução e espaço. Eles ofereceram sua implementação em https://github.com/jermp/tongrams

Cada "n" de n-gramas é mantido em uma tabela separada, acessada por uma função hash perfeita mínima, com recursos de seleção e consulta muito rápidos. As tabelas são estáticas e construídas pelo código principal usando a entrada no formato de arquivos de texto em gramas do Google.

Ainda não usei o código, mas há muitas maneiras de se fazer com os requisitos abertos de onde são as suas consultas.

Uma maneira: se o equivalente .NET de um servlet for usado com um banco de dados ou armazenamento de dados e se você precisar economizar espaço de armazenamento, armazenar uma tabela ngram em formato binário no banco de dados / armazenamento de dados como uma tabela é uma opção (um banco de dados / tabela de armazenamento de dados para o arquivo estático resultante do código ngram eficiente para todos os 1 gramas, outro para todos os 2 gramas, etc.). As consultas seriam executadas invocando o código n-grama eficiente (empacotado para ser acessível pelo seu servlet). É uma solução alternativa para criar um banco de dados distribuído que esteja usando o código n-gram eficiente para acessar os arquivos em um sistema de arquivos distribuído. Observe que as tabelas binárias de banco de dados / armazenamento de dados têm a restrição de tamanho de arquivo do sistema de arquivos subjacente.