DOCSEARCHbyAlgolia
Submit Docs

Damerau-Levenshtein Ruby Gem

repository·master·Indexed 41 days ago

https://github.com/globalnamesarchitecture/damerau-levenshtein

A Ruby gem for calculating the edit distance between UTF-8 or ASCII strings and arrays of integers with O(N*M) efficiency. It supports Levenshtein, Damerau-Levenshtein, and Boehmer & Rees algorithms via a configurable block_size. Includes the DamerauLevenshtein::Differ class for generating string differences with :tag (HTML-style <ins>, <del>, <subst>) or :raw formats.

Tokens
2.5K
Snippets
11
Records
12
Agent score
100%

What's inside damerau-levenshtein

  1. How block_size affects transposition logic

    master

    The block_size parameter in DamerauLevenshtein.distance controls how the algorithm handles transpositions (swapping blocks of characters). This allows you to switch between standard Levenshtein, Damerau-Levenshtein, and the Boehmer & Rees modification.

    block_sizeAlgorithm TypeBehavior
    0Pure LevenshteinTransposition does not count as an edit.
    1Pure Damerau-LevenshteinTransposition between 2 adjacent characters counts as 1 edit.
    2Boehmer & ReesTransposition between blocks up to 2 characters (e.g., abcd $\leftrightarrow$ cdab counts as 2 edits).
    3Boehmer & ReesTransposition between blocks up to 3 characters (e.g., abcdef $\leftrightarrow$ defabc counts as 3 edits).

  3. Get string differences with DamerauLevenshtein::Differ

    master

    The DamerauLevenshtein::Differ class provides a way to see the specific differences between two strings using tags or raw formats. This is useful for highlighting insertions, deletions, and substitutions.

    Usage

    1. Instantiate a new differ: differ = DamerauLevenshtein::Differ.new
    2. Set the format (optional): differ.format = :raw (default is :tag).
    3. Run the comparison: differ.run("String1", "String2").

    Formats

    • :tag (Default): Returns strings containing <ins>, <del>, and <subst> tags.
    • :raw: Returns the difference in a raw format.
    require "damerau-levenshtein"

# Default :tag format
differ = DamerauLevenshtein::Differ.new
differ.run("Something", "smthng")
# => ["<ins>S</ins><subst>o</subst>m<ins>e</ins>th<ins>i</ins>ng", "<del>S</del><subst>s</subst>m<del>e</del>th<del>i</del>ng"]

# Raw format
differ = DamerauLevenshtein::Differ.new
differ.format = :raw
differ.run("Something", "smthng")

  4. Calculate edit distance with DamerauLevenshtein.distance

    master

    Use DamerauLevenshtein.distance to find the edit distance between two UTF-8 or ASCII encoded strings or two arrays of integers.

    Signature

    DamerauLevenshtein.distance(string1, string2, block_size, max_distance)

    Arguments

    • string1 / array1: The first input (String or Array of integers).
    • string2 / array2: The second input (String or Array of integers).
    • block_size (Integer, default: 1): Determines the maximum number of characters in a transposition block.
      • 0: Pure Levenshtein algorithm (transposition does not count).
      • 1: Pure Damerau-Levenshtein algorithm (transposition between 2 adjacent characters).
      • 2+: Boehmer & Rees modification (allows transposition of larger blocks).
    • max_distance (Integer, default: 10): A threshold. If the real edit distance exceeds this value, the method returns max_distance instead of calculating the exact value to save computation time.
    require "damerau-levenshtein"

# Pure Damerau-Levenshtein (transposition of 2 adjacent chars counts as 1)
DamerauLevenshtein.distance("Something", "Smoething") # => 1

# Pure Levenshtein (block_size = 0)
DamerauLevenshtein.distance("Something", "Smoething", 0) # => 2

# Boehmer & Rees modification (block_size = 2)
DamerauLevenshtein.distance("Something", "meSothing", 2) # => 2

# Using max_distance threshold
DamerauLevenshtein.distance("abcdefg", "1234567", 0, 3) # => 4 (gave up at threshold 3)

# Array distance
DamerauLevenshtein.array_distance([1,2,3,5], [1,2,3,4]) # => 1

  5. Use the DamerauLevenshtein::Differ class to generate string differences

    master

    The DamerauLevenshtein::Differ class calculates the difference between two strings at a character-by-character resolution. It supports two output formats: :tag (default) and :raw.

    To use it, instantiate a new Differ object, optionally set the format, and call run(str1, str2) with the two strings you wish to compare.

    require 'damerau-levenshtein'

differ = DamerauLevenshtein::Differ.new
differ.format = :tag # or :raw

# Returns a string with <ins>, <del>, and <subst> tags
result = differ.run("something", "ssmething")
puts result

  7. Use FormatterTag for tagged string diffs

    master

    The DamerauLevenshtein::FormatterTag module generates a visual representation of differences using HTML-style tags. It returns an array containing two strings:

    1. The first string formatted with tags representing deletions (<del>) and insertions (<ins>).
    2. The second string formatted with inverted tags (showing what was added/removed relative to the first string).

    This is useful for displaying diffs in web interfaces or environments that support tag-based styling.

    # Returns [formatted_str1, formatted_str2]
results = DamerauLevenshtein::FormatterTag.show(raw_format, str1, str2)

  8. Calculate edit distance between strings or arrays

    master

    The DamerauLevenshtein module provides methods to calculate the Damerau-Levenshtein edit distance between two sequences. You can use these methods to compare either strings or arrays of integers.

    Methods

    • distance(str1, str2, block_size = 1, max_distance = 10): Calculates the distance between two strings. It internally unpacks strings into UTF-8 codepoints.
    • string_distance(*args): An alias for distance.
    • array_distance(array1, array2, block_size = 1, max_distance = 10): Calculates the distance between two arrays of integers.
    • distance_utf(*args): A legacy alias for distance provided for backward compatibility.

    Parameters

    • str1, str2: The two sequences (Strings or Arrays of integers) to compare.
    • block_size (Integer, default: 1): The size of the block used in the calculation.
    • max_distance (Integer, default: 10): The maximum distance threshold. If the calculated distance exceeds this value, the algorithm may stop early and return this threshold value.
    # Example: String distance
DamerauLevenshtein.distance("kitten", "sitting")

# Example: Array distance
DamerauLevenshtein.array_distance([1, 2, 3], [1, 2, 4])

# Example: Using max_distance to limit computation
DamerauLevenshtein.distance("very_long_string_a", "very_long_string_b", 1, 3)

  10. Use DamerauLevenshtein::Formatter to present diff results

    master

    The DamerauLevenshtein::Formatter class is used to wrap a specific formatting strategy (a module implementing a show method) to present the differences between two strings based on a provided raw_format.

    # Initialize with a formatting strategy (e.g., FormatterRaw or FormatterTag)
formatter = DamerauLevenshtein::Formatter.new(DamerauLevenshtein::FormatterTag)

# Use the show method to format the output
# raw_format: the diff data structure
# str1: the first string
# str2: the second string
result = formatter.show(raw_format, str1, str2)

  12. Configure the Differ output format

    master

    The DamerauLevenshtein::Differ class allows you to choose how the difference is presented via the format= method.

    Supported formats are:

    • :tag (default): Generates a string using HTML-style tags like <ins>, <del>, and <subst> to indicate changes.
    • :raw: Generates a raw representation of the differences.
    differ = DamerauLevenshtein::Differ.new

# Valid options are :tag and :raw
differ.format = :raw