Introduzione

L’invenzione brevettata riguarda un metodo applicabile al linguaggio informatico utile a comprimere alberi etichettati, cioè che possiede delle etichette sui nodi, e supportare ricerche efficienti su di essi. Gli alberi etichettati sono utilizzati per rappresentare dati o calcoli in applicazioni software tra cui applicazioni di tries, dizionari, alberi sintattici, alberi dei suffissi e pixel trees.

 

Caratteristiche Tecniche

L’etichettatura degli alberi è sui nodi. Le operazioni che possono essere eseguite sull’albero compresso sono la navigazione della sua struttura, oppure ricerche di sequenze di etichette che occorrono come cammini nell’albero stesso. L’aspetto innovativo della tecnica brevettata consiste nel riuscire a: a) operare ricerche senza decomprimere l’albero interamente, ma agendo solo su una piccola porzione di esso, b) ottenere prestazioni in compressione prossime all’entropia di ordine-k (stato dell’arte del Data-Compression) calcolata sul contenuto e sulla struttura dell’albero.​ E’ possibile, pertanto, effettuare delle ricerche anche su documenti di grandi dimensioni senza essere decompressi. L’applicazione più naturale è la compressione e ricerca in documenti in formato XML o JSON.​ Le capacità di comprimibilità sono elevate. Oltre a questo aspetto, la tecnica permette di trasformare l’albero etichettato (image (a)) in due stringhe: una binaria ed una costituita dalle etichette presenti nell’albero (image (b) e (c)). Le sole due stringhe sono sufficienti per effettuare ampie ricerche all’interno del documento compresso.

Possibili Applicazioni

• Esperimenti su dataset XML e JSON;
• Ampliamento su altre possibili applicazioni che considerino alberi etichettati provenienti non soltanto da XML e JSON;
• Compressione e ricerche su altri tipi di dati come: sequenze di byte, interi, grafi etichettati, o strutture più complesse;
• Ingegnerizzazione software dei prototipi realizzati.

Vantaggi

• Notevoli proprietà di comprimibilità;
• Semplicità nell’implementazione del metodo;
• Possibilità di effettuare efficientemente delle ricerche sugli alberi etichettati di grado e forma arbitrari.