1. Purpose

Canon provides two comparison algorithms, each with different strengths and use cases. This section explains how to choose between them and what to expect from each.

This corresponds to Layer 2 (Algorithm Selection) in Canon’s 4-layer architecture. See Comparison Pipeline for the complete flow.

2. Overview

Canon supports two algorithms for document comparison:

  • DOM Algorithm - Fast, stable, positional comparison (default)

  • Semantic Algorithm - Slower, intelligent, detects moves and restructuring (experimental)

Critical: The algorithm choice affects how Layers 3 and 4 behave. See Algorithm-Specific Behavior and Algorithm-Specific Output.

3. Child Pages

4. Algorithm Comparison

Feature DOM Algorithm Semantic Algorithm

Status

Stable, production-ready

Experimental

Performance

Fast (linear with document size)

Slower (quadratic worst case)

Memory

Low (line-by-line processing)

Higher (tree structures in memory)

Matching Strategy

Position-based element matching

Signature-based similarity matching

Move Detection

No (shows as DELETE + INSERT)

Yes (shows as MOVE operation)

Layer 3 Behavior

Element-by-element comparison

Signature calculation

Layer 4 Output

Line-based differences

Operation-based (INSERT, DELETE, UPDATE, MOVE)

Natural Diff Mode

by_line

by_object

Best For

Similar documents, traditional diffs

Restructured documents, operation analysis

Document Size

Handles large documents (> 100KB)

Best for smaller documents (< 10KB)

5. When to Use Each Algorithm

5.1. Use DOM Algorithm When

  • ✓ Documents have similar structure

  • ✓ Position matters in your comparison

  • ✓ Fast performance is critical

  • ✓ Traditional diff output is sufficient

  • ✓ Working with large documents

  • ✓ Stability is important (production use)

  • ✓ You need well-tested, predictable behavior

Example use cases: * Comparing generated vs expected XML in tests * Reviewing code changes in HTML templates * Fast CI/CD validation * Large document comparison

5.2. Use Semantic Algorithm When

  • ✓ Documents may be restructured

  • ✓ Need to detect element moves/reordering

  • ✓ Operation-level analysis is valuable

  • ✓ Content evolution tracking is needed

  • ✓ Willing to accept experimental status

  • ✓ Working with smaller documents

Example use cases: * Detecting document reorganization * Analyzing content migration changes * Understanding structural transformations * Research and development work

6. Configuration

6.1. Setting the Algorithm

Ruby API:

# DOM algorithm (default)
Canon::Comparison.equivalent?(doc1, doc2,
  diff_algorithm: :dom
)

# Semantic algorithm
Canon::Comparison.equivalent?(doc1, doc2,
  diff_algorithm: :semantic
)

CLI:

# DOM algorithm (default)
canon diff file1.xml file2.xml --diff-algorithm dom

# Semantic algorithm
canon diff file1.xml file2.xml --diff-algorithm semantic

RSpec:

# Global configuration
Canon::RSpecMatchers.configure do |config|
  config.xml.diff_algorithm = :semantic
end

# Per-test
expect(actual).to be_xml_equivalent_to(expected)
  .with_options(diff_algorithm: :semantic)

7. Algorithm Selection Decision Tree 

graph TD
    Start[Choose Algorithm] --> Size{Document<br/>size?}
    Size -->|> 100KB| DOM[Use DOM]
    Size -->|< 10KB| Struct{Documents<br/>restructured?}

    Struct -->|Yes| Semantic[Use Semantic]
    Struct -->|No| Speed{Need<br/>speed?}

    Speed -->|Yes| DOM
    Speed -->|No| Features{Need move<br/>detection?}

    Features -->|Yes| Semantic
    Features -->|No| Prod{Production<br/>use?}

    Prod -->|Yes| DOM
    Prod -->|No| Either[Either works,<br/>prefer DOM]

    style DOM fill:#e1f5ff
    style Semantic fill:#ffe1f5
    style Either fill:#e1ffe1

8. Performance Characteristics

8.1. DOM Algorithm Performance

Time Complexity: O(n) where n is document size * Linear scaling with document size * Predictable performance * Handles large documents well

Memory Usage: Low * Line-by-line processing * No complex tree structures * Minimal memory overhead

Throughput: High * ~1000 comparisons/second for typical documents * Suitable for batch processing

8.2. Semantic Algorithm Performance

Time Complexity: O(n²) worst case, O(n log n) typical * Quadratic worst case (highly restructured) * Logarithmic typical case (similar structure) * Slower on large documents

Memory Usage: Higher * Builds tree structures in memory * Stores signatures for all nodes * More memory per comparison

Throughput: Lower * ~100 comparisons/second for typical documents * Better for one-off comparisons

8.3. Performance Comparison Example

Table 1. Comparison time for different document sizes
Document Size DOM Time Semantic Time Ratio

1 KB

~1 ms

~10 ms

10x

10 KB

~10 ms

~150 ms

15x

100 KB

~100 ms

~3000 ms

30x

1 MB

~1 s

~60 s

60x
These are approximate times. Actual performance depends on document structure and complexity.

9. Migration Between Algorithms

9.1. Switching from DOM to Semantic

Expected changes: 1. Reordered elements detected as MOVE instead of DELETE+INSERT 2. attribute_order setting becomes irrelevant 3. Performance slower but more intelligent 4. Output format changes to operation-based

See Algorithm-Specific Behavior for migration details.

9.2. Switching from Semantic to DOM

Expected changes: 1. MOVE operations become DELETE+INSERT pairs 2. Reordered content shows as differences 3. Performance faster 4. Output format changes to line-based

10. Common Patterns

10.1. Pattern 1: Fast Validation (DOM) 

# Fast CI/CD validation
Canon::Comparison.equivalent?(expected, actual,
  diff_algorithm: :dom,
  match_profile: :spec_friendly
)

10.2. Pattern 2: Detailed Analysis (Semantic) 

# Understand what changed
result = Canon::Comparison.equivalent?(old, new,
  diff_algorithm: :semantic,
  verbose: true,
  diff_mode: :by_object
)

puts "Moves: #{result.statistics.moves}"
puts "Updates: #{result.statistics.updates}"

10.3. Pattern 3: Hybrid Approach 

# Try fast DOM first
if Canon::Comparison.equivalent?(doc1, doc2, diff_algorithm: :dom)
  puts "Documents identical"
else
  # Use semantic for detailed analysis
  result = Canon::Comparison.equivalent?(doc1, doc2,
    diff_algorithm: :semantic,
    verbose: true
  )
  analyze_operations(result.operations)
end

11. See also