Skip to content

sorensen_dice byte-length vs character-count mismatch #79

Description

@meng-xu-cs

The current sorensen_dice implementation removes whitespace, builds bigrams in character space via s.chars().zip(s.chars().skip(1)), but then uses a.len() / b.len() for the short-length guard and denominator. In Rust, String::len() is a UTF-8 byte count, not a character count, so multibyte characters inflate the denominator and can deflate the score for non-ASCII input.

For example, with a = "café" and b = "cafë":

  • Character bigrams for a: (c,a), (a,f), (f,é)
  • Character bigrams for b: (c,a), (a,f), (f,ë)
  • Shared bigrams: 2
  • Correct Sørensen-Dice score: 2 * 2 / ((4 - 1) + (4 - 1)) = 4 / 6 = 0.6666666667
  • Current implementation uses byte lengths (5 and 5), so it computes 4 / (5 + 5 - 2) = 4 / 8 = 0.5

So the crate under-reports similarity for multibyte UTF-8 strings.

Incidentally, PR #64: avoid string copy in sorensen dice, fixed it although its title emphasizes performance rather than Unicode correctness.

That PR's diff replaces the byte-based checks and denominator with character-count-based len1 / len2 values, including changing:

  • if a.len() < 2 || b.len() < 2if len1 < 2 { ... } and if len2 < 2 { ... }
  • (a.len() + b.len() - 2)(len1 + len2 - 2)

However, this PR is in draft mode still.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions