Landau-Vishkin Algorithm for Approximate String Matching

Author

Your Name

Published

February 8, 2025

Introduction

Approximate string matching is a fundamental problem in computer science with applications in various fields such as bioinformatics, text processing, and information retrieval. Unlike exact string matching, approximate string matching aims to find occurrences of a pattern in a text where the occurrences are "similar" to the pattern, allowing for a certain number of differences or errors. This is crucial in real-world scenarios where data may contain errors, variations, or noise. For instance, in bioinformatics, DNA sequences may have mutations; in text processing, there might be typos or spelling errors; and in information retrieval, users’ queries might not perfectly match the documents.

One common measure of similarity between two strings is the Levenshtein distance (also known as edit distance), which quantifies the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into the other. For example, the Levenshtein distance between "kitten" and "sitting" is 3, as we need to perform three edits: substitution (‘k’ to ‘s’), substitution (‘e’ to ‘i’), and substitution (‘n’ to ‘g’).

This lecture focuses on the Landau-Vishkin algorithm, a highly efficient algorithm for finding all occurrences of a pattern $P$ in a text $T$ with at most $k$ differences, measured by the Levenshtein distance. The algorithm leverages dynamic programming and the concept of Longest Common Extension (LCE) to achieve a significant speedup compared to naive approaches. The algorithm achieves a time complexity of $O(k \cdot m)$, making it particularly efficient when the number of allowed errors $k$ is small. This linear dependency on the text length, for a fixed number of errors, makes the Landau-Vishkin algorithm a valuable tool for large-scale text and sequence analysis.

Problem Definition

Definition: Approximate String Matching with $k$ Differences. Given a text $T$ of length $m$ and a pattern $P$ of length $n$, and a non-negative integer $k$, the $k$-differences approximate string matching problem is to find all substrings of $T$ such that the Levenshtein distance between $P$ and each substring is at most $k$.

In simpler terms, we want to find all substrings in $T$ that are "within $k$ errors" of the pattern $P$. For each possible ending position in the text $T$, we are interested in determining if a substring ending at that position exists such that its edit distance from the pattern $P$ is no more than $k$. If such substrings exist, we need to identify their starting positions in $T$.

Imagine you have a long text document ($T$) and a keyword you’re searching for ($P$). However, you want to find the keyword even if it’s misspelled or slightly different in the document. The $k$-differences approximate string matching problem aims to locate all places in the text where a word or phrase is "almost" the same as your keyword, allowing up to $k$ mistakes (insertions, deletions, or substitutions).

This problem is distinct from exact string matching, where we are only interested in finding identical occurrences of the pattern in the text. Approximate string matching is more flexible and robust, making it suitable for applications where variations and errors are inherent in the data.

Hybrid Dynamic Programming Approach

The Landau-Vishkin algorithm employs a hybrid dynamic programming approach. It is based on the standard dynamic programming solution for edit distance, but it optimizes the computation by focusing on diagonals in the dynamic programming matrix and utilizing the Longest Common Extension (LCE) operation. This approach allows for a more efficient exploration of the edit distance matrix, particularly when searching for matches with a limited number of errors.

Dynamic Programming for Edit Distance

Recall the standard dynamic programming approach to calculate the edit distance between two strings, say $P[1..n]$ and $T[1..m]$. We construct a matrix $D$ of size $(n+1) \times (m+1)$, where $D[i, j]$ represents the edit distance between the prefix $P[1..i]$ and $T[1..j]$. The recurrence relation is as follows:

Initialization:
- $D[0, 0] = 0$
- $D[i, 0] = i$ for $1 \leq i \leq n$
- $D[0, j] = j$ for $1 \leq j \leq m$
Recurrence Relation for $1 \leq i \leq n$ and $1 \leq j \leq m$: \[D[i, j] = \min \begin{cases} D[i-1, j] + 1 & \text{(deletion)} \\ D[i, j-1] + 1 & \text{(insertion)} \\ D[i-1, j-1] + \delta(P[i], T[j]) & \text{(substitution or match)} \end{cases}\] where $\delta(P[i], T[j]) = 0$ if $P[i] = T[j]$ and $\delta(P[i], T[j]) = 1$ if $P[i] \neq T[j]$.

The value $D[n, m]$ gives the Levenshtein distance between $P$ and $T$. For approximate string matching, we are interested in finding substrings of $T$ ending at position $j$ such that $D[n, j] \leq k$ for some starting position.

Diagonals in Dynamic Programming

The Landau-Vishkin algorithm optimizes this dynamic programming approach by working with diagonals. This is motivated by the observation that errors tend to be localized, and focusing on diagonals can efficiently track the propagation of errors.

Definition: Main Diagonal and Diagonals. In the dynamic programming matrix $D$, the main diagonal consists of cells $(i, j)$ where $i = j$. Other diagonals are defined relative to the main diagonal. Diagonal $d$ consists of cells $(i, j)$ where $j - i = d$. We number the diagonals such that the main diagonal is diagonal 0, diagonals above are numbered positively (1, 2, ...), and diagonals below are numbered negatively (-1, -2, ...).

Numbered diagonals of the dynamic programming table (Figure from lecture notes).

Note: Figure 1 illustrates the numbering of diagonals. Diagonal $d$ consists of cells $(i, j)$ where $j - i = d$. This figure, taken from the lecture notes, visually clarifies the concept of diagonals in the dynamic programming matrix. Understanding diagonals is crucial as the Landau-Vishkin algorithm processes the dynamic programming matrix diagonal by diagonal, rather than row by row or column by column, to achieve its efficiency.

d-path

Definition: d-path. A $d$-path is a path in the dynamic programming grid that starts from row 0 and represents a sequence of edit operations resulting in at most $d$ errors. For a given diagonal, we aim to find the farthest reaching $d$-path, which corresponds to maximizing the extent of matching with at most $d$ errors.

For a given diagonal, a step in a $d$-path can be one of the following moves:

Diagonal move: Match (if characters are equal) or substitution (if characters are different). Cost: 0 if $P[i] = T[j]$, 1 if $P[i] \neq T[j]$. This moves from cell $(i-1, j-1)$ to $(i, j)$.
Horizontal move: Insertion (inserting a character into $P$ to match $T$). Cost: 1. This moves from cell $(i, j-1)$ to $(i, j)$.
Vertical move: Deletion (deleting a character from $P$ to match $T$). Cost: 1. This moves from cell $(i-1, j)$ to $(i, j)$.

For a given diagonal $i$, we want to find the farthest reaching $d$-path. This means finding the largest column index $c$ such that there is a path ending at row $n$ and column $c$ on diagonal $i$ with at most $d$ errors. The value $c$ represents how far into the text $T$ we can match the pattern $P$ with at most $d$ errors along diagonal $i$.

Remark: The concept of $d$-path is central to the Landau-Vishkin algorithm. It allows us to think about approximate matching in terms of paths in the edit distance matrix, where each path corresponds to a sequence of edit operations. The algorithm efficiently computes and extends these paths, focusing on reaching as far as possible in the text for each error level $d$. The goal is to find how far we can proceed along each diagonal for a given error budget $d$.

Longest Common Extension (LCE)

The Longest Common Extension (LCE) query is a crucial component of the Landau-Vishkin algorithm. It enables efficient diagonal moves when characters match, significantly speeding up the process of extending $d$-paths.

Definition: Longest Common Extension (LCE). Given two strings $S_1$ and $S_2$, and starting positions $i$ in $S_1$ and $j$ in $S_2$, the Longest Common Extension $\text{LCE}(S_1, i, S_2, j)$ is the length of the longest common prefix of the suffixes $S_1[i..|S_1|]$ and $S_2[j..|S_2|]$.

In the context of the Landau-Vishkin algorithm, LCE is used to efficiently compute diagonal moves when characters match. If we are at position $(i, j)$ and we find that the pattern and text characters match for a certain length $l$, i.e., $P[i+1..i+l] = T[j+1..j+l]$, then we can extend the path diagonally by $l$ steps with zero additional cost (in terms of edit distance). Instead of incrementing diagonally one step at a time, we can "jump" ahead by the length of the longest common extension.

Example: of LCE Usage. Suppose we are comparing pattern $P = \texttt{substring}$ and text $T = \texttt{approximate\_substring\_matching}$. If we are at a point where we’ve matched "subst" and now need to compare "ring" from $P$ with "ring_matching" from $T$, the LCE operation $\text{LCE}(P, 7, T, 12)$ would return 3, because "rin" is the longest common prefix of "ring" and "ring_matching". This allows us to extend our match by 3 characters in a single step, effectively skipping the character-by-character comparison for the common prefix.

To efficiently compute LCE queries in $O(1)$ time after preprocessing, techniques like suffix trees and lowest common ancestor (LCA) queries are employed. Preprocessing typically takes linear time in the size of the strings, i.e., $O(|P| + |T|)$. This preprocessing step is performed once and allows for constant-time LCE queries throughout the algorithm, leading to the overall efficiency of the Landau-Vishkin algorithm.

k-differences Algorithm

The Landau-Vishkin algorithm iteratively computes the farthest reaching $d$-paths for $d = 0, 1, 2, ..., k$. It builds upon the results from the previous error level $(d-1)$ to compute the farthest reach for the current error level $d$.

Algorithm: Landau-Vishkin k-differences algorithm.

Pattern $P[1..n]$, Text $T[1..m]$, maximum errors $k$ Locations of approximate matches of $P$ in $T$ with at most $k$ errors

Initialize $end\_column[0..k, -n..m]$ $d \leftarrow 0$ $end\_column[0, i] \leftarrow \text{LCE}(P, 1, T, \max(1, i+1)) - 1$

$col\_from\_diag\_i \leftarrow end\_column[d-1, i] + 1$ $col\_from\_diag\_im1 \leftarrow (i > -n) ? end\_column[d-1, i-1] + 1 : -1$ $col\_from\_diag\_ip1 \leftarrow (i < m) ? end\_column[d-1, i+1] + 1 : -1$

$max\_col \leftarrow \max(col\_from\_diag\_i, col\_from\_diag\_im1, col\_from\_diag\_ip1)$

$extension\_length \leftarrow \text{LCE}(P, \max(1, 1+max\_col-i), T, max\_col+1)$ $extension\_length \leftarrow 0$

$end\_column[d, i] \leftarrow max\_col + extension\_length -1$

report_match_at_position($i + end\_column[d, i] - n + 1$)

Explanation of the Algorithm:

Note: The pseudocode assumes 1-based indexing for strings $P$ and $T$ for clarity. The ‘LCE(S1, start1, S2, start2)’ function is assumed to return the length of the longest common extension starting at the given positions in strings $S1$ and $S2$. The indices in the pseudocode require careful adjustment based on whether 0-based or 1-based indexing is used in implementation. The ‘end_column’ array stores the farthest column reached for each error level $d$ and diagonal $i$.

Correctness Observations

The correctness of the Landau-Vishkin algorithm is based on the following key observations:

Illustration of d-path extension (Figure from lecture notes).

Note: Figure 2 visually represents the extension of d-paths from previous error levels and diagonals. It illustrates how the algorithm explores possible paths by considering diagonal, vertical, and horizontal extensions. The figure highlights how the farthest reaching $d$-path is constructed by considering the best extensions from the $(d-1)$-paths on neighboring diagonals.

Complexity Analysis

Assuming the LCE operation can be performed in $O(1)$ time after suitable preprocessing (e.g., using suffix trees and lowest common ancestor queries), the time complexity of the Landau-Vishkin algorithm can be analyzed as follows:

The algorithm iterates through error levels $d$ from 1 to $k$, resulting in $k$ iterations.
For each error level $d$, it iterates through diagonals $i$ from $-n$ to $m$. The number of diagonals is $m - (-n) + 1 = m + n + 1$, which is $O(m+n)$.
Inside the nested loops, a constant number of operations are performed. These include comparisons, additions, maximum operations, and at most one LCE query in each iteration. Since we assume $O(1)$ time for LCE queries after preprocessing, all operations within the inner loop take constant time.

Therefore, the overall time complexity of the Landau-Vishkin algorithm is $O(k \cdot (m+n))$. In scenarios where the text length $m$ is significantly larger than the pattern length $n$ (which is common in many applications), the complexity is often simplified to $O(k \cdot m)$. This linear time complexity with respect to text length (for fixed $k$ and after LCE preprocessing) makes the Landau-Vishkin algorithm highly efficient for approximate string matching, especially when the number of allowed errors $k$ is small.

Algorithm: Complexity Analysis of Landau-Vishkin Algorithm.

Preprocessing for LCE: $O(m+n)$ using suffix trees and LCA. Outer loop (error levels $d$): $k$ iterations. Inner loop (diagonals $i$): $O(m+n)$ iterations. Operations inside inner loop: $O(1)$ (including $O(1)$ LCE query). Total time complexity: $O(k \cdot (m+n))$ for search, plus $O(m+n)$ for preprocessing. Simplified complexity (for $m \gg n$): $O(k \cdot m)$ for search.

Remark: Complexity in Lecture Notes. The lecture notes mention "Risultato Lineare! O(1)" likely referring to the $O(1)$ time for LCE queries after preprocessing. It also states "Totale O(k*(m+n))" and "O(k*m)", which aligns with our complexity analysis, highlighting the linear dependency on the text length $m$ and the number of allowed errors $k$. The linear time complexity makes the Landau-Vishkin algorithm a practical and efficient solution for approximate string matching in various applications.

Conclusion

The Landau-Vishkin algorithm offers an efficient solution for the $k$-differences approximate string matching problem. By cleverly combining dynamic programming with diagonal-wise computation and the Longest Common Extension operation, it achieves a time complexity of $O(k \cdot m)$ (assuming $O(1)$ LCE queries after preprocessing). This is a significant improvement over the naive dynamic programming approach, which typically has a complexity of $O(n \cdot m)$, especially when $k$ is small compared to the lengths of the text and pattern. The algorithm’s efficiency stems from its ability to skip over matching portions of the text using LCE, and by focusing computation along diagonals, effectively managing the error propagation.

The algorithm is a fundamental technique in approximate string matching and showcases the effectiveness of integrating dynamic programming with efficient data structures and algorithmic tools like LCE for solving complex pattern matching problems. Its efficiency and conceptual elegance make it a valuable algorithm in various applications requiring fast approximate string searching. These applications span diverse domains, including:

In summary, the Landau-Vishkin algorithm is not only a theoretical achievement in algorithm design but also a practical tool with substantial impact on various real-world applications that rely on efficient approximate string matching. Its linear time complexity with respect to the text length (for a fixed $k$ and after preprocessing) makes it particularly suitable for processing large datasets, solidifying its position as a cornerstone algorithm in the field.

Exercises

Implementation and Testing: Implement the Landau-Vishkin algorithm in your preferred programming language. Ensure your implementation correctly follows the pseudocode provided in Algorithm [alg:lv_k_diff]. Thoroughly test your implementation with diverse sets of patterns, texts of varying lengths, and different values of $k$ (including $k=0$ for exact matching and larger values to explore approximate matching). Consider edge cases, such as empty pattern or text, pattern longer than text, and cases where no matches are expected. Measure the execution time for different inputs to empirically observe the algorithm’s performance and how it scales with $k$, pattern length, and text length.
LCE with Suffix Trees and LCA: Delve into the details of implementing the Longest Common Extension (LCE) operation in $O(1)$ time after preprocessing using suffix trees and Lowest Common Ancestor (LCA) queries.
1. Describe the preprocessing steps required to build a suffix tree for the text $T$ and pattern $P$ (or a concatenated string). Explain how to augment the suffix tree to efficiently answer LCA queries. What is the time complexity of this preprocessing phase?
2. Detail the process of answering an $\text{LCE}(P, i, T, j)$ query using the precomputed suffix tree and LCA. Specifically, explain how to locate the nodes in the suffix tree corresponding to the suffixes $P[i..|P|]$ and $T[j..|T|]$, and how the LCA of these nodes relates to the length of the longest common extension.
3. What is the overall time complexity to answer an LCE query after preprocessing?
Space Complexity Analysis: Analyze the space complexity of the Landau-Vishkin algorithm.
1. Determine the space required by the Landau-Vishkin algorithm itself, focusing on the ‘end_column’ array and any other auxiliary data structures used during the algorithm’s execution. How does this space complexity depend on $k$, $m$, and $n$?
2. Analyze the space complexity of the suffix tree and LCA data structures used for $O(1)$ LCE queries. How does the preprocessing space scale with the lengths of the pattern and text?
3. Considering both the algorithm and the LCE preprocessing, what is the total space complexity of the Landau-Vishkin algorithm with $O(1)$ LCE?
Comparison with Other Algorithms: Compare and contrast the Landau-Vishkin algorithm with other prominent approximate string matching algorithms, such as:
- Bitap Algorithm (Shift-Or Algorithm): Describe the principles of the bitap algorithm. What are its time and space complexities? What are its limitations, particularly concerning the number of errors and alphabet size? In what scenarios is Bitap algorithm more suitable than Landau-Vishkin?
- Algorithms based on Automata (e.g., Wagner-Fischer with Automata): Discuss how finite automata can be used for approximate string matching. What types of automata are relevant (e.g., non-deterministic finite automata - NFA, deterministic finite automata - DFA)? What are the complexities associated with automata-based approaches, considering both construction and search phases? When might automata-based methods be preferred over Landau-Vishkin?
In your comparison, consider factors such as time complexity, space complexity, ease of implementation, and suitability for different values of $k$, pattern lengths, and text lengths.
Adaptation for Transposition Edit Distance: The Landau-Vishkin algorithm, as presented, handles insertions, deletions, and substitutions. Investigate how the algorithm could be adapted to accommodate transpositions (swapping of adjacent characters) as an additional edit operation.
1. How would you modify the dynamic programming recurrence relation to incorporate transpositions? What would be the cost of a transposition operation?
2. Discuss the necessary changes in the Landau-Vishkin algorithm’s logic, particularly in the $d$-path extension process, to account for transpositions. Would the diagonal-based approach still be effective?
3. Analyze the impact of including transpositions on the time and space complexity of the modified Landau-Vishkin algorithm. Would the complexity remain within the same order of magnitude, or would it increase?

--- title: "Landau-Vishkin Algorithm for Approximate String Matching" author: "Your Name" date: "2025-02-08" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction Approximate string matching is a fundamental problem in computer science with applications in various fields such as bioinformatics, text processing, and information retrieval. Unlike exact string matching, approximate string matching aims to find occurrences of a pattern in a text where the occurrences are \"similar\" to the pattern, allowing for a certain number of differences or errors. This is crucial in real-world scenarios where data may contain errors, variations, or noise. For instance, in bioinformatics, DNA sequences may have mutations; in text processing, there might be typos or spelling errors; and in information retrieval, users' queries might not perfectly match the documents. One common measure of similarity between two strings is the Levenshtein distance (also known as edit distance), which quantifies the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into the other. For example, the Levenshtein distance between \"kitten\" and \"sitting\" is 3, as we need to perform three edits: substitution ('k' to 's'), substitution ('e' to 'i'), and substitution ('n' to 'g'). This lecture focuses on the Landau-Vishkin algorithm, a highly efficient algorithm for finding all occurrences of a pattern $P$ in a text $T$ with at most $k$ differences, measured by the Levenshtein distance. The algorithm leverages dynamic programming and the concept of Longest Common Extension (LCE) to achieve a significant speedup compared to naive approaches. The algorithm achieves a time complexity of $O(k \cdot m)$, making it particularly efficient when the number of allowed errors $k$ is small. This linear dependency on the text length, for a fixed number of errors, makes the Landau-Vishkin algorithm a valuable tool for large-scale text and sequence analysis. # Problem Definition ::: tcolorbox **Definition:** Approximate String Matching with $k$ Differences. Given a text $T$ of length $m$ and a pattern $P$ of length $n$, and a non-negative integer $k$, the $k$-differences approximate string matching problem is to find all substrings of $T$ such that the Levenshtein distance between $P$ and each substring is at most $k$. ::: In simpler terms, we want to find all substrings in $T$ that are \"within $k$ errors\" of the pattern $P$. For each possible ending position in the text $T$, we are interested in determining if a substring ending at that position exists such that its edit distance from the pattern $P$ is no more than $k$. If such substrings exist, we need to identify their starting positions in $T$. ::: tcolorbox **Imagine you have a long text document ($T$) and a keyword you're searching for ($P$). However, you want to find the keyword even if it's misspelled or slightly different in the document. The $k$-differences approximate string matching problem aims to locate all places in the text where a word or phrase is \"almost\" the same as your keyword, allowing up to $k$ mistakes (insertions, deletions, or substitutions).** ::: This problem is distinct from exact string matching, where we are only interested in finding identical occurrences of the pattern in the text. Approximate string matching is more flexible and robust, making it suitable for applications where variations and errors are inherent in the data. # Hybrid Dynamic Programming Approach The Landau-Vishkin algorithm employs a hybrid dynamic programming approach. It is based on the standard dynamic programming solution for edit distance, but it optimizes the computation by focusing on diagonals in the dynamic programming matrix and utilizing the Longest Common Extension (LCE) operation. This approach allows for a more efficient exploration of the edit distance matrix, particularly when searching for matches with a limited number of errors. ## Dynamic Programming for Edit Distance Recall the standard dynamic programming approach to calculate the edit distance between two strings, say $P[1..n]$ and $T[1..m]$. We construct a matrix $D$ of size $(n+1) \times (m+1)$, where $D[i, j]$ represents the edit distance between the prefix $P[1..i]$ and $T[1..j]$. The recurrence relation is as follows: - Initialization: - $D[0, 0] = 0$ - $D[i, 0] = i$ for $1 \leq i \leq n$ - $D[0, j] = j$ for $1 \leq j \leq m$ - Recurrence Relation for $1 \leq i \leq n$ and $1 \leq j \leq m$: $$D[i, j] = \min \begin{cases} D[i-1, j] + 1 & \text{(deletion)} \\ D[i, j-1] + 1 & \text{(insertion)} \\ D[i-1, j-1] + \delta(P[i], T[j]) & \text{(substitution or match)} \end{cases}$$ where $\delta(P[i], T[j]) = 0$ if $P[i] = T[j]$ and $\delta(P[i], T[j]) = 1$ if $P[i] \neq T[j]$. The value $D[n, m]$ gives the Levenshtein distance between $P$ and $T$. For approximate string matching, we are interested in finding substrings of $T$ ending at position $j$ such that $D[n, j] \leq k$ for some starting position. ## Diagonals in Dynamic Programming The Landau-Vishkin algorithm optimizes this dynamic programming approach by working with diagonals. This is motivated by the observation that errors tend to be localized, and focusing on diagonals can efficiently track the propagation of errors. ::: tcolorbox **Definition:** Main Diagonal and Diagonals. In the dynamic programming matrix $D$, the **main diagonal** consists of cells $(i, j)$ where $i = j$. Other diagonals are defined relative to the main diagonal. Diagonal $d$ consists of cells $(i, j)$ where $j - i = d$. We number the diagonals such that the main diagonal is diagonal 0, diagonals above are numbered positively (1, 2, \...), and diagonals below are numbered negatively (-1, -2, \...). ::: ![Numbered diagonals of the dynamic programming table (Figure from lecture notes).](./diagram_page2_figure12_4.png){#fig:diagonals width="70%"} **Note:** Figure [1](#fig:diagonals){reference-type="ref" reference="fig:diagonals"} illustrates the numbering of diagonals. Diagonal $d$ consists of cells $(i, j)$ where $j - i = d$. This figure, taken from the lecture notes, visually clarifies the concept of diagonals in the dynamic programming matrix. Understanding diagonals is crucial as the Landau-Vishkin algorithm processes the dynamic programming matrix diagonal by diagonal, rather than row by row or column by column, to achieve its efficiency. ## d-path ::: tcolorbox **Definition:** d-path. A $d$-path is a path in the dynamic programming grid that starts from row 0 and represents a sequence of edit operations resulting in at most $d$ errors. For a given diagonal, we aim to find the farthest reaching $d$-path, which corresponds to maximizing the extent of matching with at most $d$ errors. ::: For a given diagonal, a step in a $d$-path can be one of the following moves: 1. **Diagonal move:** Match (if characters are equal) or substitution (if characters are different). Cost: 0 if $P[i] = T[j]$, 1 if $P[i] \neq T[j]$. This moves from cell $(i-1, j-1)$ to $(i, j)$. 2. **Horizontal move:** Insertion (inserting a character into $P$ to match $T$). Cost: 1. This moves from cell $(i, j-1)$ to $(i, j)$. 3. **Vertical move:** Deletion (deleting a character from $P$ to match $T$). Cost: 1. This moves from cell $(i-1, j)$ to $(i, j)$. For a given diagonal $i$, we want to find the farthest reaching $d$-path. This means finding the largest column index $c$ such that there is a path ending at row $n$ and column $c$ on diagonal $i$ with at most $d$ errors. The value $c$ represents how far into the text $T$ we can match the pattern $P$ with at most $d$ errors along diagonal $i$. ::: tcolorbox **Remark:** The concept of $d$-path is central to the Landau-Vishkin algorithm. It allows us to think about approximate matching in terms of paths in the edit distance matrix, where each path corresponds to a sequence of edit operations. The algorithm efficiently computes and extends these paths, focusing on reaching as far as possible in the text for each error level $d$. The goal is to find how far we can proceed along each diagonal for a given error budget $d$. ::: ## Longest Common Extension (LCE) The Longest Common Extension (LCE) query is a crucial component of the Landau-Vishkin algorithm. It enables efficient diagonal moves when characters match, significantly speeding up the process of extending $d$-paths. ::: tcolorbox **Definition:** Longest Common Extension (LCE). Given two strings $S_1$ and $S_2$, and starting positions $i$ in $S_1$ and $j$ in $S_2$, the Longest Common Extension $\text{LCE}(S_1, i, S_2, j)$ is the length of the longest common prefix of the suffixes $S_1[i..|S_1|]$ and $S_2[j..|S_2|]$. ::: In the context of the Landau-Vishkin algorithm, LCE is used to efficiently compute diagonal moves when characters match. If we are at position $(i, j)$ and we find that the pattern and text characters match for a certain length $l$, i.e., $P[i+1..i+l] = T[j+1..j+l]$, then we can extend the path diagonally by $l$ steps with zero additional cost (in terms of edit distance). Instead of incrementing diagonally one step at a time, we can \"jump\" ahead by the length of the longest common extension. ::: tcolorbox **Example:** of LCE Usage. **Suppose we are comparing pattern $P = \texttt{substring}$ and text $T = \texttt{approximate\_substring\_matching}$. If we are at a point where we've matched \"subst\" and now need to compare \"ring\" from $P$ with \"ring_matching\" from $T$, the LCE operation $\text{LCE}(P, 7, T, 12)$ would return 3, because \"rin\" is the longest common prefix of \"ring\" and \"ring_matching\". This allows us to extend our match by 3 characters in a single step, effectively skipping the character-by-character comparison for the common prefix.** ::: To efficiently compute LCE queries in $O(1)$ time after preprocessing, techniques like suffix trees and lowest common ancestor (LCA) queries are employed. Preprocessing typically takes linear time in the size of the strings, i.e., $O(|P| + |T|)$. This preprocessing step is performed once and allows for constant-time LCE queries throughout the algorithm, leading to the overall efficiency of the Landau-Vishkin algorithm. ## k-differences Algorithm The Landau-Vishkin algorithm iteratively computes the farthest reaching $d$-paths for $d = 0, 1, 2, ..., k$. It builds upon the results from the previous error level $(d-1)$ to compute the farthest reach for the current error level $d$. :::: tcolorbox **Algorithm:** Landau-Vishkin k-differences algorithm. ::: algorithmic Pattern $P[1..n]$, Text $T[1..m]$, maximum errors $k$ Locations of approximate matches of $P$ in $T$ with at most $k$ errors Initialize $end\_column[0..k, -n..m]$ $d \leftarrow 0$ $end\_column[0, i] \leftarrow \text{LCE}(P, 1, T, \max(1, i+1)) - 1$ $col\_from\_diag\_i \leftarrow end\_column[d-1, i] + 1$ $col\_from\_diag\_im1 \leftarrow (i > -n) ? end\_column[d-1, i-1] + 1 : -1$ $col\_from\_diag\_ip1 \leftarrow (i < m) ? end\_column[d-1, i+1] + 1 : -1$ $max\_col \leftarrow \max(col\_from\_diag\_i, col\_from\_diag\_im1, col\_from\_diag\_ip1)$ $extension\_length \leftarrow \text{LCE}(P, \max(1, 1+max\_col-i), T, max\_col+1)$ $extension\_length \leftarrow 0$ $end\_column[d, i] \leftarrow max\_col + extension\_length -1$ report_match_at_position($i + end\_column[d, i] - n + 1$) ::: :::: **Explanation of the Algorithm:** **Note:** The pseudocode assumes 1-based indexing for strings $P$ and $T$ for clarity. The 'LCE(S1, start1, S2, start2)' function is assumed to return the length of the longest common extension starting at the given positions in strings $S1$ and $S2$. The indices in the pseudocode require careful adjustment based on whether 0-based or 1-based indexing is used in implementation. The 'end_column' array stores the farthest column reached for each error level $d$ and diagonal $i$. ## Correctness Observations The correctness of the Landau-Vishkin algorithm is based on the following key observations: ![Illustration of d-path extension (Figure from lecture notes).](./diagram_page5_paths.png){#fig:d_path_extension width="70%"} **Note:** Figure [2](#fig:d_path_extension){reference-type="ref" reference="fig:d_path_extension"} visually represents the extension of d-paths from previous error levels and diagonals. It illustrates how the algorithm explores possible paths by considering diagonal, vertical, and horizontal extensions. The figure highlights how the farthest reaching $d$-path is constructed by considering the best extensions from the $(d-1)$-paths on neighboring diagonals. ## Complexity Analysis Assuming the LCE operation can be performed in $O(1)$ time after suitable preprocessing (e.g., using suffix trees and lowest common ancestor queries), the time complexity of the Landau-Vishkin algorithm can be analyzed as follows: - The algorithm iterates through error levels $d$ from 1 to $k$, resulting in $k$ iterations. - For each error level $d$, it iterates through diagonals $i$ from $-n$ to $m$. The number of diagonals is $m - (-n) + 1 = m + n + 1$, which is $O(m+n)$. - Inside the nested loops, a constant number of operations are performed. These include comparisons, additions, maximum operations, and at most one LCE query in each iteration. Since we assume $O(1)$ time for LCE queries after preprocessing, all operations within the inner loop take constant time. Therefore, the overall time complexity of the Landau-Vishkin algorithm is $O(k \cdot (m+n))$. In scenarios where the text length $m$ is significantly larger than the pattern length $n$ (which is common in many applications), the complexity is often simplified to $O(k \cdot m)$. This linear time complexity with respect to text length (for fixed $k$ and after LCE preprocessing) makes the Landau-Vishkin algorithm highly efficient for approximate string matching, especially when the number of allowed errors $k$ is small. :::: tcolorbox **Algorithm:** Complexity Analysis of Landau-Vishkin Algorithm. ::: algorithmic **Preprocessing for LCE:** $O(m+n)$ using suffix trees and LCA. **Outer loop (error levels $d$):** $k$ iterations. **Inner loop (diagonals $i$):** $O(m+n)$ iterations. **Operations inside inner loop:** $O(1)$ (including $O(1)$ LCE query). **Total time complexity:** $O(k \cdot (m+n))$ for search, plus $O(m+n)$ for preprocessing. **Simplified complexity (for $m \gg n$):** $O(k \cdot m)$ for search. ::: :::: ::: tcolorbox **Remark:** Complexity in Lecture Notes. The lecture notes mention \"Risultato Lineare! O(1)\" likely referring to the $O(1)$ time for LCE queries after preprocessing. It also states \"Totale O(k\*(m+n))\" and \"O(k\*m)\", which aligns with our complexity analysis, highlighting the linear dependency on the text length $m$ and the number of allowed errors $k$. The linear time complexity makes the Landau-Vishkin algorithm a practical and efficient solution for approximate string matching in various applications. ::: # Conclusion The Landau-Vishkin algorithm offers an efficient solution for the $k$-differences approximate string matching problem. By cleverly combining dynamic programming with diagonal-wise computation and the Longest Common Extension operation, it achieves a time complexity of $O(k \cdot m)$ (assuming $O(1)$ LCE queries after preprocessing). This is a significant improvement over the naive dynamic programming approach, which typically has a complexity of $O(n \cdot m)$, especially when $k$ is small compared to the lengths of the text and pattern. The algorithm's efficiency stems from its ability to skip over matching portions of the text using LCE, and by focusing computation along diagonals, effectively managing the error propagation. The algorithm is a fundamental technique in approximate string matching and showcases the effectiveness of integrating dynamic programming with efficient data structures and algorithmic tools like LCE for solving complex pattern matching problems. Its efficiency and conceptual elegance make it a valuable algorithm in various applications requiring fast approximate string searching. These applications span diverse domains, including: In summary, the Landau-Vishkin algorithm is not only a theoretical achievement in algorithm design but also a practical tool with substantial impact on various real-world applications that rely on efficient approximate string matching. Its linear time complexity with respect to the text length (for a fixed $k$ and after preprocessing) makes it particularly suitable for processing large datasets, solidifying its position as a cornerstone algorithm in the field. # Exercises 1. **Implementation and Testing:** Implement the Landau-Vishkin algorithm in your preferred programming language. Ensure your implementation correctly follows the pseudocode provided in Algorithm [\[alg:lv_k_diff\]](#alg:lv_k_diff){reference-type="ref" reference="alg:lv_k_diff"}. Thoroughly test your implementation with diverse sets of patterns, texts of varying lengths, and different values of $k$ (including $k=0$ for exact matching and larger values to explore approximate matching). Consider edge cases, such as empty pattern or text, pattern longer than text, and cases where no matches are expected. Measure the execution time for different inputs to empirically observe the algorithm's performance and how it scales with $k$, pattern length, and text length. 2. **LCE with Suffix Trees and LCA:** Delve into the details of implementing the Longest Common Extension (LCE) operation in $O(1)$ time after preprocessing using suffix trees and Lowest Common Ancestor (LCA) queries. 1. Describe the preprocessing steps required to build a suffix tree for the text $T$ and pattern $P$ (or a concatenated string). Explain how to augment the suffix tree to efficiently answer LCA queries. What is the time complexity of this preprocessing phase? 2. Detail the process of answering an $\text{LCE}(P, i, T, j)$ query using the precomputed suffix tree and LCA. Specifically, explain how to locate the nodes in the suffix tree corresponding to the suffixes $P[i..|P|]$ and $T[j..|T|]$, and how the LCA of these nodes relates to the length of the longest common extension. 3. What is the overall time complexity to answer an LCE query after preprocessing? 3. **Space Complexity Analysis:** Analyze the space complexity of the Landau-Vishkin algorithm. 1. Determine the space required by the Landau-Vishkin algorithm itself, focusing on the 'end_column' array and any other auxiliary data structures used during the algorithm's execution. How does this space complexity depend on $k$, $m$, and $n$? 2. Analyze the space complexity of the suffix tree and LCA data structures used for $O(1)$ LCE queries. How does the preprocessing space scale with the lengths of the pattern and text? 3. Considering both the algorithm and the LCE preprocessing, what is the total space complexity of the Landau-Vishkin algorithm with $O(1)$ LCE? 4. **Comparison with Other Algorithms:** Compare and contrast the Landau-Vishkin algorithm with other prominent approximate string matching algorithms, such as: - **Bitap Algorithm (Shift-Or Algorithm):** Describe the principles of the bitap algorithm. What are its time and space complexities? What are its limitations, particularly concerning the number of errors and alphabet size? In what scenarios is Bitap algorithm more suitable than Landau-Vishkin? - **Algorithms based on Automata (e.g., Wagner-Fischer with Automata):** Discuss how finite automata can be used for approximate string matching. What types of automata are relevant (e.g., non-deterministic finite automata - NFA, deterministic finite automata - DFA)? What are the complexities associated with automata-based approaches, considering both construction and search phases? When might automata-based methods be preferred over Landau-Vishkin? In your comparison, consider factors such as time complexity, space complexity, ease of implementation, and suitability for different values of $k$, pattern lengths, and text lengths. 5. **Adaptation for Transposition Edit Distance:** The Landau-Vishkin algorithm, as presented, handles insertions, deletions, and substitutions. Investigate how the algorithm could be adapted to accommodate transpositions (swapping of adjacent characters) as an additional edit operation. 1. How would you modify the dynamic programming recurrence relation to incorporate transpositions? What would be the cost of a transposition operation? 2. Discuss the necessary changes in the Landau-Vishkin algorithm's logic, particularly in the $d$-path extension process, to account for transpositions. Would the diagonal-based approach still be effective? 3. Analyze the impact of including transpositions on the time and space complexity of the modified Landau-Vishkin algorithm. Would the complexity remain within the same order of magnitude, or would it increase?