La requête "commence par" ultra-rapide à partir du disque

J'ai une liste de chaînes de 40 Mo (trop grande pour mémoire dans ce cas) que je veux faire "commence par" des requêtes pour extraire des correspondances. Quelqu'un sait-il une bonne structure de données pour cela? Points bonus pour une implémentation os java existante. Je serais prêt à sacrifier "commence par" pour juste correspondre exactement si quelque chose existe déjà. Un système basé sur disque semble idéal.La requête "commence par" ultra-rapide à partir du disque

Source

2010-12-11 ghempton

Les cordes ont-elles la même longueur? Est-ce que le rembourrage tout le long de la plus longue serait un problème? – thejh

quelle est la structure/architecture de la source des chaînes? est-ce un fichier texte séparé de 40 Go? est-ce pour la production de spam? ;) – pstanton

Ce n'est que 40 Mo et non gb et ils sont des termes individuels. C'est fondamentalement juste pour un contrôle d'existence super rapide pour un terme (<40 caractères). Je pourrais même utiliser sql ou lucene pour cela, mais comme les données vont être statiques je suppose que je pourrais faire beaucoup mieux. – ghempton

Il semble que vous besoin de quelque chose comme ceci: http://en.wikipedia.org/wiki/Trie

Une implémentation en Java peut être trouvé here, bien qu'il ne soit pas sur disque. Je vais continuer à chercher:/

documents utiles: Trie methods for text and spatial data on secondary storage, B-tries for disk-based string management

Edit: je suis tombé sur ce qui pourrait peut-être utile: MG4J: Managing Gigabytes for Java™

Source

2010-12-11 20:53:25

ne peut proposer une bibliothèque existante, mais je me suis occupé similaire problème avant. C'est assez simple, si vous ne prévoyez pas de modifier votre liste dynamiquement et vous pouvez trier les chaînes dans le fichier (pour la recherche binaire).

Brisons votre 40 Mo en 1000 morceaux de taille approximativement égale et gardons la première chaîne de chaque morceau en mémoire. Ce serait un tableau de 1000 chaînes. Ils sont commandés, parce que la liste originale est commandée.
Lorsque vous devez exécuter une requête, vous pouvez utiliser la recherche binaire sur ce tableau. Cela vous montrera dans quelle chaîne de résultat de morceau se trouve. Ensuite, vous pouvez lire ce morceau à partir du disque (environ 40ko) et chercher dans son contenu. Par exemple, si le tableau contient les valeurs ["andrew", "brian", "donald", "john"] et que vous recherchez le préfixe "cris", vous savez que tous les Cristophers et Cristians se trouvent dans le deuxième bloc.

Source

2010-12-11 20:57:59

La requête "commence par" ultra-rapide à partir du disque

Répondre

Questions connexes