walkalike

README

walkalike - file tree similarity

Calculates how two or more filesystem trees (or OS images) are similar by applying techniques from Machine Learning, Deep Learning, Big Data and Clustering. In practice, the tool prints out Jaccard similarity coefficient for two directories. Usage:

go run github.com/lzap/walkalike/cmd dir1 dirN

Processing is optimized for SSDs and index creation is parallelized. Example command:

go run github.com/lzap/walkalike/cmd testdata/a testdata/b

Should print:

0.4444444444444 testdata/a testdata/b

Similarity coefficient is between 0.0, when two trees are not similar at all, or 1.0, when two trees are exactly the same. When multiple directories are provided, the first directory is compared against 2nd, 3rd and so on.

go run github.com/lzap/walkalike/cmd testdata/a testdata/b testdata/c

Should print:

0.4444444444444 testdata/a testdata/b
0.9814814814815 testdata/a testdata/c

When the same directory is passed twice:

go run github.com/lzap/walkalike/cmd /usr/lib /usr/lib

Similarity must be 1.0:

1.0000000000000 /usr/lib /usr/lib

OS images support

The tool support listing files inside OS images, it requires the tool virt-ls to be installed:

sudo dnf -f install guestfs-tools

The utility from guestfs-tools is executed as a subprocess and automatically detect OS image, finds root partition and walks the directory tree passing results and checksums to the parent process which calculates the index.

go run github.com/lzap/walkalike/cmd a-fedora-40-minimal-raw-x86_64.raw b-fedora-40-minimal-raw-x86_64.raw

Building the indices will take a little bit more time as walking the tree is not parallelized and some images might be compressed but the result is exactly the same:

0.9995304751005 a-fedora-40-minimal-raw-x86_64.raw b-fedora-40-minimal-raw-x86_64.raw

Output format

Three columns are printed out:

• Similarity (number between 0 and 1)
• Directory A
• Directory B

Index cache

Indices for OS images are kept in cache ($HOME/.cache/walkalike) so further processing will be fast. Directories are never kept in cache however.

Index size is relatively small, for an OS image of about 35k files about 500kB index is created. The rough estimation is 16 bytes per file entry, files are compressed with gzip which brings the size down by about 20%.

Implementation

When a directory is passed, the tree is walked and two CRC32 checksums (compatible with cksum) are calculated for each file: absolute file path and file contents. Then the list of the CRC pairs is stored in XDG_CACHE directory as a small index which is used to perform similarity comparison.

When a file is passed, virt-ls tool is called to detect OS image type, partitions and list all files including the CRC32 checksum. The same checksum is calculated from the file paths as well.

Only regular files, hardlinks and symlinks are subject of processing, directories are skipped. Meaning, an empty directory will not affect the result score.

Currently Jaccard similarity approach is used to calculate the final value. Calculation is done separately for file paths and content checksums with the weight of 0.5. This may be configurable in the future as other algorithms are added.

Download binary

Use releases page on github to download binary for your OS and architecture.

Building

To build the project:

go build ./cmd

API

This repository is also a Go library.

Authors

(c) 2025 Lukáš Zapletal

License

Apache 2.0

Documentation

Index

• Constants
• Variables
• func BuildID() string
• func BuildTime() string
• func ChecksumCache(path string, size int64, modTime time.Time) (string, error)
• func ChecksumPath(s string) uint32
• func ChecksumReader(r io.Reader) (uint32, int, error)
• func CompareContent(a, b Token) int
• func ComparePaths(a, b Token) int
• type Cache
  • func NewCache(root string) *Cache
  • func (c *Cache) Ensure() error
  • func (c *Cache) Get(path string, info os.FileInfo) (*Index, error)
  • func (c *Cache) Put(path string, info os.FileInfo, index *Index) error
• type GuestfsLSCSV
  • func NewGuestfsLSCSV(r io.Reader) *GuestfsLSCSV
  • func (gr *GuestfsLSCSV) Index() *Index
  • func (gr *GuestfsLSCSV) ReadAll() error
• type Index
  • func (ix *Index) Add(pathHash, contentHash uint32)
  • func (ix *Index) Decode(r io.Reader) error
  • func (ix *Index) Encode(w io.Writer, filename string) error
  • func (ix *Index) Size() int
  • func (ix *Index) String() string
• type Indexer
  • func NewIndexer(root string) *Indexer
  • func (i *Indexer) Build(ctx context.Context) (*Index, error)
• type JaccardSimilarity
  • func SimilarityJaccard(a, b *Index) JaccardSimilarity
• type Token
  • func Intersect(a, b []Token, cmp func(a Token, b Token) int) []Token
  • func SortByContent(t []Token) []Token
  • func SortByPaths(t []Token) []Token
  • func (t Token) String() string

Constants

const (
	// BuildCommitChars is the number of characters to show in the build commit.
	BuildCommitChars = 7
)

Variables

var ErrChecksumSizeMismatch = errors.New("checksum size mismatch")

Functions

func BuildID

func BuildID() string

BuildID returns the build ID, typically a git commit but can be overriden via a linker flag. This is the short version, up to BuildCommitChars characters long.

func BuildTime

func BuildTime() string

BuildTime returns the build time, if available.

func ChecksumCache

func ChecksumCache(path string, size int64, modTime time.Time) (string, error)

func ChecksumPath

func ChecksumPath(s string) uint32

func ChecksumReader

func ChecksumReader(r io.Reader) (uint32, int, error)

func CompareContent

func CompareContent(a, b Token) int

CompareContent compares two tokens by their content hash.

func ComparePaths

func ComparePaths(a, b Token) int

ComparePaths compares two tokens by their path hash.

Types

type Cache

type Cache struct {
	// contains filtered or unexported fields
}

func NewCache

func NewCache(root string) *Cache

func (*Cache) Ensure

func (c *Cache) Ensure() error

func (*Cache) Get

func (c *Cache) Get(path string, info os.FileInfo) (*Index, error)

func (*Cache) Put

func (c *Cache) Put(path string, info os.FileInfo, index *Index) error

type GuestfsLSCSV

type GuestfsLSCSV struct {
	// contains filtered or unexported fields
}

func NewGuestfsLSCSV

func NewGuestfsLSCSV(r io.Reader) *GuestfsLSCSV

func (*GuestfsLSCSV) Index

func (gr *GuestfsLSCSV) Index() *Index

func (*GuestfsLSCSV) ReadAll

func (gr *GuestfsLSCSV) ReadAll() error

type Index

type Index struct {
	Tokens []Token
	// contains filtered or unexported fields
}

func (*Index) Add

func (ix *Index) Add(pathHash, contentHash uint32)

Add adds a new token to the index. This function is thread-safe.

func (*Index) Decode

func (ix *Index) Decode(r io.Reader) error

Decode decodes the index using gob and decompresses it using gzip.

func (*Index) Encode

func (ix *Index) Encode(w io.Writer, filename string) error

Encode encodes the index using gob and compresses it using gzip.

func (*Index) Size

func (ix *Index) Size() int

Size returns the number of tokens in the index.

func (*Index) String

func (ix *Index) String() string

type Indexer

type Indexer struct {
	// ErrFn is called when an error occurs during indexing. The first argument
	// is the path of the file that caused the error, and the second argument
	// is the error itself. The function can be called from multiple goroutines.
	ErrFn func(string, error)
	// contains filtered or unexported fields
}

func NewIndexer

func NewIndexer(root string) *Indexer

NewIndexer creates a new Indexer. The root argument is the root of the directory tree to be indexed.

func (*Indexer) Build

func (i *Indexer) Build(ctx context.Context) (*Index, error)

Build walks the directory tree rooted at root and builds the index. It returns the index and an error if one occurs.

type JaccardSimilarity

type JaccardSimilarity struct {
	// Similarity is the overall Jaccard similarity between two indices.
	Similarity float64

	// ContentSimilarity is the Jaccard similarity between two indices by file content.
	ContentSimilarity float64

	// PathSimilarity is the Jaccard similarity between two indices by file paths.
	PathSimilarity float64
}

JaccardSimilarity holds the Jaccard similarity between two indices. It contains the overall similarity, content similarity, and path similarity.

func SimilarityJaccard

func SimilarityJaccard(a, b *Index) JaccardSimilarity

Similarity computes the Jaccard similarity between two indices.

https://en.wikipedia.org/wiki/Jaccard_index

type Token

type Token struct {
	PathHash    uint32
	ContentHash uint32
}

func Intersect

func Intersect(a, b []Token, cmp func(a Token, b Token) int) []Token

Intersect computes the intersection of two sets of tokens by cmp function. It returns a slice of tokens that are present in both sets. Both a and b arguments must be sorted and unique for the cmp function.

func SortByContent

func SortByContent(t []Token) []Token

SortByContent sorts the tokens by their content hash. It returns a new slice of tokens with duplicates removed.

func SortByPaths

func SortByPaths(t []Token) []Token

SortByPaths sorts the tokens by their path hash. It returns a new slice of tokens with duplicates removed.

func (Token) String

func (t Token) String() string