In questo articolo voglio presentare un algoritmo per la compressione del bacode. Quest'algoritmo può essere molto utile nel caso si abbia a che fare con la memorizzazione di codici a barre su dispositivi embedded.
La filosofia
La filosofa dell'algortimo è la seguente, consideriamo un EAN 13 a peso fisso, come ci viene descritto da INDICOD
http://www.indicod-ecr.it/ nel documento
http://www.indicod-ecr.it/chisiamo/manuale/04_Capitolo_1-Parte_I.pdf. Ogni barcode è costuito da 13 cifre, traslasciando l'ultima cifra che funge da controllo, le altre si possono raggruppare in gruppi, le prime due cifre rappresentano la nazione di provenienza del prodotto, le successive 7 sono il codice del produttore e le rimanenti 3 rappresentano il codice del prodotto.
In definitiva le prime 9 cifre identificano il prefisso aziendale (Nazione+Produttore), mentre le ultime 3 rappresentano il prodotto, questo per gli associati indicod-ecr dopo il 1° Gennaio 2002.
Invece prima del 1° gennaio 2002 indicod-ecr assegnava ai nuovi associati prefissi aziendali a 7 cifre divise in questo modo, 2 per la nazione, 5 per il produttore, 5 per il prodotto + la solita cifra di controllo.
Non è ambito di questo articolo trattare l'algoritmo per il calcolo della cifra di controllo e di tutte le problematiche relative ai barcode a peso variabile, per questo rimando al sopra citato link.
Ora quando si ha a che fare con grosse quantità di dati, tipicamenti database aziendali, il barcode viene utilizzato per identificare il prodotto, consideriamo ad esempio di voler archiviare su file il prezzo di ogni articolo, avremo quindi ad esempio nel caso più semplice una tabella prezzi con su : codice_articolo | prezzo. Supponiamo ora di voler memorizzare questi valori su dispositivo portatile batch, dovremmo allora portare il risultato della query
select * from prezzi order by codice_articolo su file, portare il file sul dispositivo e poi farci ricerca binaria sopra.
Ci si accorge subito che data la struttura particolare del barcode discussa in precenza può esistere un modo un po' più furbo per organizzare il file da memorizzare sul dispositivo portatile, infatti ordinando il file per codice_articolo ci accorgeremmo subito che il gruppo nazione e codice produttore viene ripetuto parecchie volte, ad es.
80 80000 00001 | 1.20
80 80000 00002 | 1.90
80 80000 00003 | 1.24
....................................................
80 80000 99999 | 10.20 -> Posizione x sul file
80 80000 00001 | 250.00 -> Posizione y sul file
etc....
è subito evidente che un miglioramento si potrebbe ottenere se spezzassimo la memorizzazione:
File 1:
80 80000 0 x (dove 0 x sono rispettivamente la posizione iniziale e la posizione finale)
80 80001 x y
File 2:
00001 | 1.20
00002 | 1.90
00003 | 1.24
....................................................
99999 | 10.20
00001 | 250.00
già con questa prima elaborazione abbiamo risparmiato (2+5)*(x-1) bytes. Continuando ora con o stesso procedimento, possiamo pensare di spezzare in 4 files ovvero:
1) File delle nazioni
2) File dei produttori
3) File dei prodotti
4) File dei prezzi
1) File nazioni:
80 x y
81 y+1 z
..............
2) File produttori:
Pos x 00001 Px Py
x+1 00002 Py+1 Pz
x+2 00003
..................
y 99999
y+1 00001
3) File Prodotti
Pos Px 00001 Posx
Px+1 00002 Posy
Px+2 00003 Posk
....................
Py 99999
4) File prezzi
0 0.20
1 0.21
2 0.23
...........
Posx 0.50
Posx+1 0.60
...........
Nel file Prodotti la posizione Posx ad esempio è la posizione del valore del prezzo nel file dei prezzi, in questo modo evitiamo anche di avere valori ripetuti nei prezzi.
Procedendo in questo modo l'algoritmo provvede a memorizzare in maniera compressa il file articoli-prezzi, e fare ricerche binarie sull'archivio compresso.
Le prove
Da prove effettuate ho potuto vedere che un lista di circa 35.000 articoli con realitivo prezzo sono risultate memorizzate in circa 170 Kb a fronte dei 700 Kb iniziali.
Il codice
eanzip-0.0.3.tar.gz
La licenza
Il sorgente scritto in C è rilasciato in licenza
GPL. Il software è completo di Makefile, nel pacchetto è compreso anche il codice per poter esportare il file da comprimere direttamente da postgres.
