How to resolve the algorithm Levenshtein distance/Alignment step by step in the Racket programming language

Published on 12 May 2024 09:40 PM
#Racket

How to resolve the algorithm Levenshtein distance/Alignment step by step in the Racket programming language

Table of Contents

Problem Statement

The Levenshtein distance algorithm returns the number of atomic operations (insertion, deletion or edition) that must be performed on a string in order to obtain an other one, but it does not say anything about the actual operations used or their order. An alignment is a notation used to describe the operations used to turn a string into an other. At some point in the strings, the minus character ('-') is placed in order to signify that a character must be added at this very place. For instance, an alignment between the words 'place' and 'palace' is:

Write a function that shows the alignment of two strings for the corresponding levenshtein distance.
As an example, use the words "rosettacode" and "raisethysword". You can either implement an algorithm, or use a dedicated library (thus showing us how it is named in your language).

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Levenshtein distance/Alignment step by step in the Racket programming language

Source code in the racket programming language

#lang racket

(define (memoize f)
  (local ([define table (make-hash)])
    (lambda args
      (dict-ref! table args (λ () (apply f args))))))

(define levenshtein
  (memoize
   (lambda (s t)
     (cond
       [(and (empty? s) (empty? t)) 0]
       [(empty? s) (length t)]
       [(empty? t) (length s)]
       [else
        (if (equal? (first s) (first t))
            (levenshtein (rest s) (rest t))
            (min (add1 (levenshtein (rest s) t))
                 (add1 (levenshtein s (rest t)))
                 (add1 (levenshtein (rest s) (rest t)))))]))))


(levenshtein (string->list "rosettacode") 
             (string->list "raisethysword"))


#lang racket

(struct lev (n s t))

(define (lev-add old n sx tx)
  (lev (+ n (lev-n old))
       (cons sx (lev-s old))
       (cons tx (lev-t old))))

(define (list-repeat n v)
  (build-list n (lambda (_) v)))

(define (memoize f)
  (local ([define table (make-hash)])
    (lambda args
      (dict-ref! table args (λ () (apply f args))))))

(define levenshtein/list
  (memoize
   (lambda (s t)
     (cond
       [(and (empty? s) (empty? t)) 
        (lev 0 '() '())]
       [(empty? s) 
        (lev (length t) (list-repeat (length t) #\-) t)]
       [(empty? t) 
        (lev (length s) s (list-repeat (length s) #\-))]
       [else
        (if (equal? (first s) (first t))
            (lev-add (levenshtein/list (rest s) (rest t))
                     0 (first s) (first t))
            (argmin lev-n (list (lev-add (levenshtein/list (rest s) t)
                                         1 (first s) #\-)
                                (lev-add (levenshtein/list s (rest t))
                                         1 #\- (first t))
                                (lev-add (levenshtein/list (rest s) (rest t))
                                         1 (first s) (first t)))))]))))

(define (levenshtein s t)
  (let ([result (levenshtein/list (string->list s) 
                                  (string->list t))])
    (values (lev-n result)
            (list->string (lev-s result)) 
            (list->string (lev-t result)))))


(let-values ([(dist exp-s exp-t) 
              (levenshtein "rosettacode" "raisethysword")])
  (printf "levenshtein: ~a edits\n" dist)
  (displayln exp-s)
  (displayln exp-t))

You may also check:How to resolve the algorithm Combinations with repetitions step by step in the Arturo programming language
You may also check:How to resolve the algorithm Water collected between towers step by step in the Phix programming language
You may also check:How to resolve the algorithm ABC problem step by step in the Scala programming language
You may also check:How to resolve the algorithm Sorting algorithms/Stooge sort step by step in the Go programming language
You may also check:How to resolve the algorithm Soundex step by step in the Mathematica/Wolfram Language programming language