  Given two strings $A[1..n]$ and $B[1..m]$, and a set of operations allowed to
edit the strings, the edit distance between $A$ and $B$ is the minimum number
of operations required to transform $A$ into $B$. Sequentially, a standard
Dynamic Programming (DP) algorithm solves edit distance with $\Theta(nm)$ cost.
In many real-world applications, the strings to be compared are similar and
have small edit distances. To achieve highly practical implementations, we
focus on output-sensitive parallel edit-distance algorithms, i.e., to achieve
asymptotically better cost bounds than the standard $\Theta(nm)$ algorithm when
the edit distance is small. We study four algorithms in the paper, including
three algorithms based on Breadth-First Search (BFS) and one algorithm based on
Divide-and-Conquer (DaC). Our BFS-based solution is based on the Landau-Vishkin
algorithm. We implement three different data structures for the longest common
prefix (LCP) queries needed in the algorithm: the classic solution using
parallel suffix array, and two hash-based solutions proposed in this paper. Our
DaC-based solution is inspired by the output-insensitive solution proposed by
Apostolico et al., and we propose a non-trivial adaption to make it
output-sensitive. All our algorithms have good theoretical guarantees, and they
achieve different tradeoffs between work (total number of operations), span
(longest dependence chain in the computation), and space.
  We test and compare our algorithms on both synthetic data and real-world
data. Our BFS-based algorithms outperform the existing parallel edit-distance
implementation in ParlayLib in all test cases. By comparing our algorithms, we
also provide a better understanding of the choice of algorithms for different
input patterns. We believe that our paper is the first systematic study in the
theory and practice of parallel edit distance.
