R/dynamic_programming/edit_distance.r at d7c31f2d451a64059d53b8a3d15918b0c83f6fd6 · DiogoRibeiro7/R · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
# edit_distance.r
# Levenshtein edit distance algorithm in R
# Computes the minimum number of insertions, deletions, and substitutions
# required to transform one string into another.
# Time Complexity: O(m * n)
# Space Complexity: O(m * n)

# Compute the Levenshtein distance between two strings
edit_distance <- function(str1, str2) {
  #' @param str1: First string
  #' @param str2: Second string
  #' @return: Integer edit distance
  if (!is.character(str1) || !is.character(str2)) {
    stop("Both inputs must be character strings.")
  }
  if (length(str1) != 1 || length(str2) != 1) {
    stop("Each input must be a single string.")
  }

  m <- nchar(str1)
  n <- nchar(str2)
  dp <- matrix(0L, nrow = m + 1, ncol = n + 1)

  # base cases: transform empty prefix
  dp[, 1] <- seq(0L, m)
  dp[1, ] <- seq(0L, n)

  for (i in seq_len(m) + 1L) {
    for (j in seq_len(n) + 1L) {
      cost <- if (substr(str1, i - 1, i - 1) == substr(str2, j - 1, j - 1)) 0L else 1L
      dp[i, j] <- min(
        dp[i - 1, j] + 1L,      # deletion
        dp[i, j - 1] + 1L,      # insertion
        dp[i - 1, j - 1] + cost # substitution
      )
    }
  }

  return(dp[m + 1, n + 1])
}

# Compute the edit distance and reconstruct an optimal alignment path
edit_distance_with_path <- function(str1, str2) {
  #' @param str1: First string
  #' @param str2: Second string
  #' @return: List with distance, operations, and dp table
  if (!is.character(str1) || !is.character(str2)) {
    stop("Both inputs must be character strings.")
  }
  if (length(str1) != 1 || length(str2) != 1) {
    stop("Each input must be a single string.")
  }

  m <- nchar(str1)
  n <- nchar(str2)
  dp <- matrix(0L, nrow = m + 1, ncol = n + 1)
  dp[, 1] <- seq(0L, m)
  dp[1, ] <- seq(0L, n)

  for (i in seq_len(m) + 1L) {
    for (j in seq_len(n) + 1L) {
      cost <- if (substr(str1, i - 1, i - 1) == substr(str2, j - 1, j - 1)) 0L else 1L
      dp[i, j] <- min(
        dp[i - 1, j] + 1L,
        dp[i, j - 1] + 1L,
        dp[i - 1, j - 1] + cost
      )
    }
  }

  i <- m + 1
  j <- n + 1
  ops <- character()

  while (i > 1 || j > 1) {
    if (i > 1 && j > 1 && dp[i, j] == dp[i - 1, j - 1] +
        (substr(str1, i - 1, i - 1) != substr(str2, j - 1, j - 1))) {
      if (substr(str1, i - 1, i - 1) == substr(str2, j - 1, j - 1)) {
        ops <- c("match", ops)
      } else {
        ops <- c(sprintf("substitute '%s' -> '%s'", substr(str1, i - 1, i - 1), substr(str2, j - 1, j - 1)), ops)
      }
      i <- i - 1
      j <- j - 1
    } else if (i > 1 && dp[i, j] == dp[i - 1, j] + 1L) {
      ops <- c(sprintf("delete '%s'", substr(str1, i - 1, i - 1)), ops)
      i <- i - 1
    } else {
      ops <- c(sprintf("insert '%s'", substr(str2, j - 1, j - 1)), ops)
      j <- j - 1
    }
  }

  return(list(
    distance = dp[m + 1, n + 1],
    operations = ops,
    dp_table = dp
  ))
}

# Example usage:
# print(edit_distance("kitten", "sitting"))
# result <- edit_distance_with_path("kitten", "sitting")
# print(result$distance)
# print(result$operations)