Trie à base de disque?

J'essaye de construire un Trie mais sur un téléphone portable qui a la capacité de mémoire très limitée. J'ai pensé qu'il est probablement préférable que la structure entière soit stockée sur le disque, et chargée seulement si nécessaire puisque je peux tolérer quelques lectures de disque. Mais, après quelques tentatives, il semble que ce soit une chose très compliquée à faire.Trie à base de disque?

Quelles sont les manières de stocker un Trie sur le disque (c'est-à-dire seulement partiellement chargé) et conserver la propriété de recherche rapide?
Est-ce une bonne idée pour commencer?

Source

2010-10-01 chakrit

Je chercherais un B-tree plutôt qu'un trie dans cette situation, mais j'aimerais aussi connaître la réponse à cette question. – zwol

Les essais sont des structures permettant une recherche rapide. Cela ressemble à un bon cas d'utilisation pour certains moteur de base de données intégré, comme SQLite, ou certains http://en.wikipedia.org/wiki/Dbm dérivé – permeakra

L'article B-tries for disk-based string management répond à votre question.

Il fait l'observation:

À notre connaissance, il doit encore être une proposition dans la littérature pour une structure de données à base de Trie- , comme la structure arborescente rafale, le peut résider efficacement sur le disque pour supporter les tâches courantes de traitement de chaînes.

Source

2010-11-05 04:06:05 user497981

http://www.naskitis.com/naskitis-vldbj09.pdf – RichardOD

le le papier est en panne :( – bgs

@bgs le lien RichardOD posté fonctionne pour moi – chakrit

Je l'ai seulement regardé brièvement, mais Shang's "Trie methods for text and spatial data on secondary storage" discute des représentations trie paginées, et pourrait être un point de départ utile.

Source

2010-10-01 23:53:56

Trie à base de disque?

Répondre

Questions connexes