Stockage de données n-gram

J'espérais faire un petit remue-méninges sur le sujet du stockage des données à n programmes . Dans mon projet, j'essaie de résoudre des problèmes linguistiques où je connais tous les éléments de données ( n -1) et je veux deviner statistiquement mon n en utilisant une interpolation linéaire sur tous les n -grammes applicables . (Oui, il existe un tagueur qui attribue des balises à des mots connus en fonction de son lexique et un arbre de suffixes qui essaie de deviner le type de mot pour les mots inconnus; le composant à n- grammes discuté ici sera chargé de résoudre l'ambiguïté.)

Mon approche initiale serait de simplement stocker tous les n- grammes observés (pour n = 1..3, c'est-à-dire monogramme, bigramme, trigramme) dans des bases de données SQL respectives et de l'appeler un jour. Mais les exigences de mon projet peuvent changer pour inclure d'autres longueurs de vecteur ( n ), et je voudrais que mon application s'adapte à 4 grammes sans beaucoup de travail (mise à jour du schéma, mise à jour du code d'application, etc.); idéalement, je dirais simplement à mon application de travailler avec 4 grammes maintenant sans avoir à changer beaucoup (ou pas du tout) de code et à former ses données à partir d'une source de données donnée.

Pour résumer toutes les exigences:

• Possibilité de stocker n données -gram (initialement pour n = {1, 2, 3}
• Possibilité de changer les types de n -grammes à utiliser (entre les exécutions d'application)
• Capacité à (re) former les données de n-programmes (entre les exécutions d'application)

• Possibilité d'interroger le magasin de données (par exemple, si j'ai observé A, B, C, j'aimerais connaître l'élément le plus fréquemment observé pour ce qui pourrait suivre en utilisant mes ensembles de données formés de 4, 3, 2, 1 gramme )

  L'application sera probablement lourde en lecture, les ensembles de données ne seront probablement pas recyclés aussi souvent

• La solution utilise le .NET Framework (jusqu'à 4.0)

Maintenant, quelle conception conviendrait le mieux à une telle tâche?

• Une table fixe gérée par un serveur SQL (MSSQL, MySQL, ...) pour chaque n (ex. Tables dédiées aux bi-grammes, tri-grammes, etc.)
• Ou une solution de base de données de documents NoSQL qui stocke le premier n -1 comme la clé du document et le document lui - même contient la n valeur -ème et les fréquences observées?
• Ou quelque chose de différent?

Étant donné que vous ne connaissez pas la plage optimale de N, vous voulez certainement pouvoir la changer. Par exemple, si votre application prédit la probabilité qu'un certain texte soit anglais, vous voudrez probablement utiliser des caractères N-grammes pour N 3..5. (C'est ce que nous avons découvert expérimentalement.)

Vous n'avez pas partagé les détails de votre application, mais le problème est suffisamment clair. Vous souhaitez représenter des données N-gramme dans une base de données relationnelle (ou une solution basée sur des documents NoSQL). Avant de suggérer ma propre solution, vous voudrez peut-être examiner les approches suivantes:

1. Comment stocker au mieux les ngrams Google dans une base de données?
2. Stockage de n-grammes dans la base de données dans <n nombre de tables
3. Gestion du Google Web 1T 5 grammes avec la base de données relationnelle

Maintenant, n'ayant lu aucun des liens ci-dessus, je suggère une approche de base de données relationnelle simple utilisant plusieurs tables, une pour chaque taille de N-gramme. Vous pouvez mettre toutes les données dans une seule table avec le maximum de colonnes nécessaires (c'est-à-dire stocker les bigrammes et les trigrammes dans ngram_4, en laissant les dernières colonnes nulles), mais je recommande de partitionner les données. Selon votre moteur de base de données, une seule table avec un grand nombre de lignes peut avoir un impact négatif sur les performances.

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

Ensuite, je vais vous donner une requête qui retournera le mot suivant le plus probable étant donné toutes vos tables de ngram. Mais d'abord, voici quelques exemples de données que vous devez insérer dans les tableaux ci-dessus:

  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)

Pour interroger le mot suivant le plus probable, vous utiliseriez une requête comme celle-ci.

  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

Si vous ajoutez d'autres tables ngram, vous devrez ajouter une autre clause UNION à la requête ci-dessus. Vous remarquerez peut-être que dans la première requête, j'ai utilisé word1 = @ word3. Et dans la deuxième requête, mot1 = @ mot2 ET mot2 = @ mot3. C'est parce que nous devons aligner les trois mots de la requête pour les données ngram. Si nous voulons le mot suivant le plus probable pour une séquence de trois mots, nous devons comparer le premier mot des données bigrammes avec le dernier mot des mots de la séquence.

Vous pouvez modifier les paramètres de poids comme vous le souhaitez. Dans cet exemple, j'ai supposé que des grammes "n" ordinaux supérieurs seraient plus fiables.

PS Je structurerais le code du programme pour gérer n'importe quel nombre de tables ngram_N via la configuration. Vous pouvez modifier le programme de manière déclarative pour utiliser la plage N-grammes N (1..6) après avoir créé les tables ngram_5 et ngram_6.

Contrairement à ce que les autres suggèrent, je suggérerais d'éviter toute structure de données plus complexe qu'une table de hachage ou un magasin de valeurs-clés.

Gardez à l'esprit vos exigences d'accès aux données: a) 99% de requêtes - interrogez le ngram "aaa-bbb-ccc" et récupérez la valeur (ou 0) b) 1% de requêtes - insérer / mettre à jour un décompte de ngram spécifiques c) il n'y a pas (c).

Le moyen le plus efficace consiste à le récupérer avec une seule recherche. Vous pouvez utiliser un séparateur hors limites (ou échappé) pour combiner le n-gramme complet dans une seule chaîne (par exemple, "alpha | beta | gamma" pour 3 grammes, "alpha" pour unigram, etc.) et simplement le récupérer ( par le hachage de cela). C'est ainsi que beaucoup de logiciels NLP le font.

Si vos données de ngram sont petites (disons <1 Go) et tiennent dans la mémoire, je suggère d'utiliser une structure de mémoire en programme efficace (hashmaps, arbres, essais, etc.) pour éviter les frais généraux; et juste sérialiser / désérialiser en fichiers plats. Si vos données ngram sont de plusieurs téraoctets, vous pouvez choisir des magasins de valeurs-clés NoSQL répartis sur plusieurs nœuds.

Pour des performances supplémentaires, vous voudrez peut-être remplacer tous les mots partout avec des identifiants entiers afin que votre algorithme de base ne voie aucune chaîne (lente); il est alors légèrement différent de mettre en œuvre la même idée.

Pas le plus efficace, mais simple et intégré à la base de données comme vous le souhaitez:

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 devrait avoir des index sur le document et pos.

les bigrammes sont:

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

Ensuite, vous pouvez compter () et grouper votre chemin vers des fréquences et d'autres choses.

Pour passer aux trigrammes, il suffit de générer cette chaîne pour inclure un mot3.

J'ai déjà fait cela auparavant (même si le SQL là-haut est probablement un peu rouillé). Je me suis installé sur un ensemble de fichiers plats qui pourraient être recherchés facilement puis diffusés sur le disque. Cela dépend un peu de votre matériel pour mieux le faire.

En essayant d'améliorer les recherches simples de mes applications vers des bigrammes et des trigrammes à partir d'unigrammes, j'ai essentiellement vu votre question.

Si l'une des exigences est la capacité d'interroger un système de fichiers ou une base de données distribuée, cela pourrait également être intéressant pour vous: le document Pibiri et Venturini 2018 «Gérer efficacement les ensembles de données massifs de N-Gram» décrit un moyen efficace de stocker des données de n-grammes dans termes d'exécution et d'espace. Ils ont proposé leur mise en œuvre sur https://github.com/jermp/tongrams

Chaque "n" de n-grammes est conservé dans une table séparée accessible par une fonction de hachage parfaite minimale avec des capacités de sélection et de requête très rapides. Les tableaux sont statiques et construits par le code principal en utilisant une entrée au format de fichiers texte Google n-grammes.

Je n'ai pas encore utilisé le code, mais il existe de nombreuses façons avec vos exigences ouvertes d'où proviennent vos requêtes.

Une façon: si l'équivalent .NET d'un servlet est utilisé avec une base de données ou une banque de données, et si vous devez économiser de l'espace de stockage, le stockage de chaque table ngram sous forme binaire dans la base de données / banque de données en tant que table est une option (une base de données / table de banque de données pour le fichier statique résultant du code ngram efficace pour tous les 1 grammes, un autre pour tous les 2 grammes, etc.). Les requêtes seraient exécutées en invoquant le code n-gram efficace (encapsulé pour être accessible par votre servlet). C'est une solution de contournement pour créer une base de données distribuée qui utilise le code n-gram efficace pour accéder aux fichiers sur un système de fichiers distribué. Notez que les tables de base de données / banque de données binaires ont chacune la restriction de taille de fichier du système de fichiers sous-jacent.