Multiset Lempel–Ziv Jaccard Distance
Information · 16.05.2026 · 17 (5) · 489
DOI: 10.3390/info17050489 ↗Kurz gefasst
Fachartikel in der Zeitschrift Information, online erschienen am 16.05.2026. Verfasst von Satoshi Aoki und 1 weiteren Autor:innen. Die Arbeit nennt 16 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Japan Society for the Promotion of Science.
Abstract (Originalsprache)
The performance of pattern classification is affected significantly by feature selection. However, for security applications, selecting proper features is difficult, as malicious software continuously changes its characteristics. Thus, compression-based pattern recognition has attracted much attention because it does not require explicit feature selection to design proper distance measures. LZJD (Lempel–Ziv Jaccard Distance), in particular, has been useful for malware classification, as it computes compression distances without actually compressing objects and is suitable for handling large files like malware. LZJD extracts a compression dictionary for every object in advance and estimates a similarity between two objects by comparing their compression dictionaries. However, LZJD ignores the similarity between words in a compression dictionary. As a result, even if the dictionary has many similar words, they are simply processed as different words. To exploit the similarity between words, we propose to remove the last characters of words in the dictionary and to unify similar words that share the same prefix. This unification of words turns the compression dictionary into a multiset of words. Hence, our compression distance is named MLZJD (Multiset LZJD). In addition, the unification of words in MLZJD decreases the number of word kinds in compression dictionaries and contributes to speeding up the distance computation. We experimentally show that MLZJD halves the execution time as compared with LZJD, while hardly damaging the classification accuracy. Even on condition that the compression distances are approximated with Min-Hash, MLZJD achieves a much shorter running time than LZJD, while retaining almost the same classification accuracy as LZJD.
Förderung
- Japan Society for the Promotion of Science
Zitieren
APA
Aoki, S., & Koga, H. (2026). Multiset Lempel–Ziv Jaccard Distance. Information, 17(5), 489. https://doi.org/10.3390/info17050489
Vancouver
Aoki S, Koga H. Multiset Lempel–Ziv Jaccard Distance. Information. 2026;17(5):489. doi:10.3390/info17050489
BibTeX
@article{Aoki2026,
author = {Aoki, Satoshi and Koga, Hisashi},
title = {Multiset Lempel–Ziv Jaccard Distance},
journal = {Information},
year = {2026},
volume = {17},
number = {5},
pages = {489},
doi = {10.3390/info17050489}
}
EUVIMED