Efficient storage and compression of covering arrays using advanced encoding techniques

Abstract

This paper introduced a novel storage format for covering arrays, designed to optimize file size through efficient compression techniques. The proposed format employed Asymmetric Numeral System (ANS) encoding for array data, as well as Run-Length Encoding (RLE) and Variable Length Encoding (VLE) for metadata storage. The goal was to provide a compact, standardized format that facilitates easier sharing and utilization of covering arrays across different applications. Experimental evaluations on a dataset of 21964 covering arrays from the National Institute of Standards and Technology (NIST) demonstrated that the new format outperforms general-purpose compression algorithms such as ZIP, BZIP2, and XZ in most cases, particularly for larger covering arrays with high parameter counts. While previous work on covering array storage focused on archival and retrieval efficiency, the proposed method significantly reduces storage requirements without loss of structural integrity. The proposed method preserved the combinatorial properties of covering arrays while reducing redundancy, making it a practical alternative for large-scale combinatorial testing applications.

În această lucrare a fost propus un nou format de stocare a matricelor de acoperire, conceput pentru a optimiza dimensiunea fișierelor prin tehnici eficiente de compresie. Formatul utilizat s-a bazat pe codificarea Sistem Numeric Asimetric (SNA) pentru datele din matrice, alături de Codificarea Lungimii de Rulare (CLR) și Codificarea cu Lungime Variabilă (CLV) pentru stocarea metadatelor. Scopul a fost de a oferi un format standardizat și compact, care să faciliteze partajarea și utilizarea eficientă a matricelor de acoperire în diverse aplicații. Experimentele realizate pe un set de date de 21964 de matrice de acoperire, furnizat de Institutul Național de Standarde și Tehnologie (INST), au arătat că noul format depășește algoritmii de compresie generală, precum ZIP, BZIP2 și XZ, în majoritatea cazurilor, în special pentru matrice mari cu un număr ridicat de parametri. În timp ce lucrările anterioare privind stocarea matricelor de acoperire s-au concentrat pe eficiența arhivării și recuperării, abordarea propusă a redus semnificativ cerințele de stocare fără a compromite integritatea structurală. Metoda prezentată a păstrat proprietățile combinatoriale ale matricelor de acoperire și elimină redundanțele, oferind o alternativă practică pentru aplicațiile de testare combinatorială la scară largă.