Modèle de base de données efficace pour stocker des données indexées par n-grammes

Je travaille sur une application qui nécessite de créer une très grande base de données de n-grammes qui existent dans un grand corpus de texte.

J'ai besoin de trois types d'opérations efficaces: recherche et insertion indexées par le n-gramme lui-même, et interrogation pour tous les n-grammes qui contiennent un sous-n-gramme.

Cela me semble que la base de données devrait être une gigantesque arborescence de documents et que les bases de données de documents, par exemple Mongo, devraient être en mesure de bien faire le travail, mais je ne les ai jamais utilisées à grande échelle.

Connaissant le format de question Stack Exchange, je voudrais préciser que je ne demande pas de suggestions sur des technologies spécifiques, mais plutôt un type de base de données que je devrais rechercher pour implémenter quelque chose comme ça à grande échelle.

Voir Lucene NGramTokenizer

Êtes-vous sûr que vous ne pouvez pas simplement utiliser lucene ou des techniques d'indexation similaires?

Les index inversés ne stockent le n-gramme qu'une seule fois, puis uniquement les identifiants de document qui contiennent le ngram; ils ne le stockent pas en tant que texte brut hautement redondant.

Quant à la recherche de ngrams contenant votre sous-n-gramme de requête, je construirais un index sur les ngrams observés, par exemple en utilisant un deuxième index lucene, ou tout autre index de sous-chaîne tel qu'un arbre de trie ou de suffixe. Si vos données sont dynamiques, Lucene est probablement un choix raisonnable, en utilisant des requêtes de phrases pour trouver vos n-grammes.

Fondamentalement, pour cette tâche, vous pouvez utiliser efficacement n'importe quelle base de données SQL avec une bonne prise en charge des index basés sur l'arborescence B + (MySQL s'adaptera à vos besoins).

Créez 3 tables:

1. Tableau des documents, colonnes: id / document
2. Tableau des N-grammes: n_gram_id / n_gram
3. Mappage entre n-grammes et documents: document_id / n_gram_id

Créez des index sur la table N-gramme / chaîne n_gram et la table de mappage / n_gram_id, les clés primaires seront également bien indexées par défaut.

Vos opérations seront efficaces:

1. Insertion du document: il suffit d'extraire tous les n-grammes et de les insérer dans le tableau des documents et le tableau des N-grammes
2. La recherche de in_gram sera rapide avec la prise en charge de l'index
3. Interroger tous les n-grammes qui contiennent un sous-n-gramme: en 2 étapes - il suffit d'interroger en fonction de l'index tous les n-grammes qui contiennent des sous-n-grammes de la 2ème table. Ensuite, récupérez tous les documents correspondants pour chacun de ces n-grammes.

Vous n'avez même pas besoin d'utiliser des jointures pour réaliser toutes ces opérations, les index vous aideront donc beaucoup. De plus, si les données ne sont pas intégrées dans une seule machine - vous pouvez implémenter un schéma de partage, comme le stockage de n_grams démarrés à partir d'un sur un serveur et oz sur un autre ou un autre schéma approprié.

Vous pouvez également utiliser MongoDB, mais je ne sais pas exactement comment vous devez implémenter le schéma d'indexation. Pour MongoDB, vous obtiendrez un schéma de partitionnement gratuit car il est déjà intégré.

Je ne l'ai pas fait auparavant, mais cela ressemble à un travail pour une base de données de graphiques, compte tenu des fonctionnalités que vous souhaitez. Voici une démo dans neo4j .