Recherche rapide dans les fichiers texte compressé

Je peux être complètement faux ici, mais je ne pense pas qu'il y aurait un moyen fiable de rechercher une chaîne donnée sans décoder les fichiers. Ma compréhension des algorithmes de compressions est que le flux de bits correspondant à une chaîne donnée dépend de ce qui se passe avant la chaîne dans le fichier non compressé. Vous pourrez peut-être trouver un codage donné pour une chaîne particulière dans un fichier donné, mais je suis sûr que cela ne serait pas cohérent entre les fichiers.

Il est peu probable que vous puissiez rechercher des chaînes non compressées dans un fichier compressé. Je suppose que l'un pour vos meilleures options consiste à indexer les fichiers en quelque sorte. En utilisant Lucene peut-être?

La plupart des fichiers texte sont compressés avec l'un des LZ-Family d'algorithmes, qui combinent un codeurdicatère avec un codeur d'entropie comme Huffman.

Parce que le codeur de dictionnaire s'appuie sur un "dictionnaire" continuellement mis à jour, son résultat de codage dépend de l'historique (tous les codes du dictionnaire qui est dérivé des données d'entrée jusqu'au symbole actuel), il n'est donc pas possible. Pour passer à un certain endroit et commencer à décoder, sans d'abord décoder toutes les données précédentes.

À mon avis, vous pouvez simplement utiliser un décodeur de flux ZLIB qui renvoie des données décompressées car elle va sans attendre que l'ensemble du fichier soit décompressé. Cela ne sauvera pas l'heure d'exécution mais sauvera la mémoire.

Une seconde suggestion est de faire coder Huffman sur des mots anglais et d'oublier la partie du donneur de dictionnaire. Chaque mot anglais est mappé sur un code de préfixe unique.

Enfin, @shodan a donné la suggestion la plus judicieuse, qui consiste à indexer les fichiers, à compresser l'index et à l'ensemble avec les fichiers texte compressés. Pour effectuer une recherche, décompresser uniquement le fichier d'index et rechercher les mots. C'est en fait une amélioration par rapport à la codage de Huffman sur des mots - une fois que vous avez trouvé la fréquence des mots (afin d'attribuer le code de préfixe de manière optimale), vous avez déjà construit l'index, vous pouvez donc conserver l'index de la recherche.

La recherche de texte dans les fichiers compressé peut être plus rapide que la recherche de la même chose dans des fichiers texte non compressés.

Une technique de compression que j'ai vue qui sacrifie un peu d'espace afin de faire des recherches rapides:

• Maintenir un dictionnaire avec 2 ^ 16 entrées de chaque mot dans le texte. Réservez les 256 premières entrées pour les octets littéraux, au cas où vous allez sur un mot qui n'est pas dans le dictionnaire - même si de nombreux grands textes ont moins de 32 000 mots uniques, ils n'ont donc jamais besoin d'utiliser ces octets littéraux.
• compresse le texte d'origine en remplaçant l'index de dictionnaire 16 bits pour chaque mot.
• (facultatif) Dans le cas normal que deux mots sont séparés par un seul caractère d'espace, supprimez ce caractère d'espace; Sinon, mettez tous les octets dans la chaîne entre les mots dans le dictionnaire sous la forme d'un "mot" spécial (par exemple "." et "\ n") étiqueté avec l'attribut "Aucun espaces par défaut", puis "Compressez "Ces chaînes en les remplaçant avec l'index de dictionnaire correspondant.
• Recherchez des mots ou des phrases en comprimant la phrase de la même manière et en recherchant la chaîne compressée d'octets dans le texte compressé de la même manière que vous recherchez la chaîne d'origine dans le texte d'origine.

  En particulier, la recherche d'un mot unique réduit généralement la comparaison de l'indice 16 bits dans le texte compressé, ce qui est plus rapide que la recherche de ce mot dans le texte d'origine, car

  • Chaque comparaison nécessite de comparer moins d'octets - 2, plutôt que de nombreux octets étaient dans ce mot, et
  • Nous faisons moins de comparaisons, car le fichier compressé est plus court.

    Certaines types d'expressions régulières peuvent être traduites dans une autre expression régulière qui trouve directement des éléments dans le fichier compressé (et trouve également quelques faux positifs). Une telle recherche fait également moins de comparaisons que d'utiliser l'expression régulière d'origine sur le fichier texte d'origine, car le fichier compressé est plus court, mais généralement chaque comparaison d'expression régulière nécessite plus de travail, de sorte qu'il peut ou ne pas être plus rapide que le regex d'origine fonctionnant sur le texte original.

    (en principe, vous pouvez remplacer les codes 16 bits de longueur fixe avec des codes de préfixes de Huffman de longueur variable, car Rwong mentionné - le fichier compressé résultant serait plus petit, mais le logiciel de gérer ces fichiers serait un peu plus lent et plus compliqué).

    Pour des techniques plus sophistiquées, vous pourriez regarder

    • mg4j: Gestion des gigaoctets pour Java
    • "Gestion des gigaoctets: Compression et indexation des documents et des images" par Ian H. Witten, Alistair Moffat et Timothy C. Bell

Ceci est possible et peut être fait de manière assez efficace. Il y a beaucoup de recherches passionnantes sur ce sujet, plus formellement appelée structure de données succinct. Certains sujets que je recommanderais de rechercher: arborescence d'ondelettes, index FM / RRR, suffixe succincte. Vous pouvez également rechercher efficacement les chaînes codées Huffman, car un certain nombre de publications ont démontré.