Sembra

Structural similarity scoring for JSON-compatible data

Italian: "sembrare" — to seem, to resemble

The Problem

Existing deep comparison libraries answer only binary questions:

| Library | Gives you | |---------|-----------| | fast-deep-equal | Equal or not? | | lodash.isequal | Equal or not? | | deep-diff | What changed? |

None answer the most natural question:

How similar are these two structures?

When schemas evolve, keys get renamed, or data comes from different sources, binary equality is useless. You need a similarity score.

The Algorithm: Sembra Similarity

Sembra computes a continuous similarity score S(a, b) ∈ [0, 1] for any two JSON-compatible values using a novel multi-phase algorithm:

Phase 1: Type-Aware Primitive Matching

• Strings: Jaro-Winkler distance (handles typos, minor variations)
• Numbers: Relative difference scoring
• Booleans: Exact match (configurable partial mode)
• Null: Always exact

Phase 2: Optimal Array Alignment

Instead of index-by-index comparison, Sembra computes a similarity matrix between all pairs of elements and finds the optimal matching using a greedy assignment algorithm. This handles:

• Reordered elements
• Inserted/deleted elements
• Partially matching elements

Phase 3: Value-Guided Key Rename Detection

This is the key novelty. When object keys differ between two structures, Sembra infers renames by comparing the values at those keys:

const a = { name: "Alice", age: 30 }
const b = { fullName: "Alice", yearsOld: 30 }
// Sembra detects: name → fullName, age → yearsOld
// Score: >0.85

No other library does this.

Phase 4: Recursive Composition

All phases compose recursively — nested arrays, nested objects, and mixed structures are handled uniformly.

Performance

| Operation | Complexity | |-----------|------------| | Identical structures (early exit) | O(n) | | Similar structures | O(n log n) | | Dissimilar structures | O(n × m) |

n = number of nodes in the larger structure.

Quick Start

import { sembra, sembraReport, defaultConfig } from 'sembra'

// Basic similarity
const score = sembra({ a: 1, b: 2 }, { a: 1, b: 3 })
console.log(score)  // ~0.89

// Key rename detection
const score2 = sembra(
  { userName: "Alice", userAge: 30 },
  { name: "Alice", age: 30 }
)
console.log(score2)  // >0.8

// Reordered arrays
const score3 = sembra([1, 2, 3], [3, 1, 2])
console.log(score3)  // 1.0 (all elements match)

// Detailed report
const report = sembraReport({ a: 1 }, { a: 2 })
console.log(report.score, report.matches)

// Configuration
const cfg = defaultConfig({ stringSimilarity: false })
const score4 = sembra("hello", "hallo", cfg)

Configuration Reference

| Option | Default | Description | |--------|---------|-------------| | stringSimilarity | true | Enable fuzzy string matching | | stringThreshold | 0.6 | Minimum string similarity to count as match | | numberSimilarity | true | Enable fuzzy number matching | | numberThreshold | 0.8 | Minimum number similarity to count as match | | booleanPartial | false | Allow partial boolean matching | | arrayMatching | true | Enable optimal array element matching | | arrayMatchThreshold | 0.4 | Minimum element similarity to match | | objectKeyRename | true | Enable value-guided key rename detection | | objectRenameThreshold | 0.65 | Minimum value similarity to infer rename | | maxDepth | 16 | Maximum recursion depth | | maxArraySize | 200 | Max array size for element-by-element matching | | useCache | true | Cache intermediate results | | earlyExit | true | Exit early for same-reference objects | | keyWeightMode | 'uniform' | Key importance weighting |

Use Cases

• Test assertions with tolerance for structural variation
• Schema migration — map old API responses to new schemas
• Data deduplication — find structurally similar records
• Configuration comparison — detect drifted configs
• API monitoring — alert on structural drift
• Merge conflict resolution — find best correspondence

Comparison with Existing Libraries

| Feature | Sembra | fast-deep-equal | lodash.isequal | deep-diff | |---------|--------|-----------------|----------------|-----------| | Continuous similarity score | ✅ | ❌ | ❌ | ❌ | | Key rename detection | ✅ | ❌ | ❌ | ❌ | | Array alignment | ✅ | ❌ | ❌ | ❌ | | Fuzzy strings | ✅ | ❌ | ❌ | ❌ | | Fuzzy numbers | ✅ | ❌ | ❌ | ❌ | | Binary equality | ✅ | ✅ | ✅ | ❌ | | Diff script | ✅ | ❌ | ❌ | ✅ | | Cross-type matching | ✅ | ❌ | ❌ | ❌ |

License

MIT — see LICENSE

Author

nhemlos