bk_tree

A Dart BK-Tree implementation for efficient nearest neighbor searches using Hamming distance, optimized for bulk file hash processing and duplicate detection.

Compatibility: Dart ^3.6.0

🚀 Getting Started

Installation

Method 1 (Recommended) With Dart:

dart pub add bk_tree

With Flutter:

flutter pub add bk_tree

Method 2 Add to pubspec.yaml:

dependencies:
  bk_tree: ^0.1.1

Then run:

dart pub get

Basic Usage

import "package:bk_tree/bk_tree.dart";

void main() {
  final tree = BKTree(
    yourHashMap,
    yourDistanceFunction,
  );
  final results = tree.search(
    queryHash: yourQueryHash,
    tolerance: n, // Your allowed n-bit difference
  );
}

📦 Features

Core Feature 1: Return a BK-Tree of a folder (using hamming distance)

final imageHashes = {
  "cat.jpg": "d3b07384d113edec",
  "dog.jpg": "c157a79031e1c40f",
  "cat_copy.jpg": "d3b07384d113edef", // Duplicate
  "landscape.png": "6f4b726212b23f0a",
};

// Create BK-Tree with Hamming distance
final tree = BKTree(
  imageHashes,
  hammingDistance, // Need from another place
);

// Search for duplicates of cat.jpg
final results = tree.search(
  queryHash: imageHashes["cat.jpg"]!,
  tolerance: 2, // Here allow 2-bit difference
);

print("Duplicate findings:");
for (var match in results) {
  match.forEach((file, distance) {
      print("- Target: cat.jpg. Find match $file (distance: $distance)");
  });
}

Output:

- Target: cat.jpg. Find match cat.jpg (distance: 0)
- Target: cat.jpg. Find match cat_copy.jpg (distance: 2)

🧪 Testing

# Run tests with coverage
dart test

🤝 Contributing

Workflow

Fork repository
Create feature branch:
```
git checkout -b feat/your-feature
```

Follow Conventional Commits:

git commit -m "feat: add new validation method"

Code Style

Follow the Effective Dart and analysis_options.yaml

📚 Documentation

📜 License

Full text at LICENSE

🚧 Maintenance Status

Basic functionalities are done. (Current version is to support author's other packages)

More General Version is under development.

Please report issues via GitHub Issues