# Coarse-to-Fine Embedded PatchMatch and Multi-Scale Dynamic Aggregation for
Reference-based Super-Resolution

Bin Xia1, Yapeng Tian2, Yucheng Hang1, Wenming Yang1, Qingmin Liao1, Jie Zhou1
Corresponding author.

###### Abstract

Reference-based super-resolution (RefSR) has made significant progress in
producing realistic textures using an external reference (Ref) image. However,
existing RefSR methods obtain high-quality correspondence matchings consuming
quadratic computation resources with respect to the input size, limiting its
application. Moreover, these approaches usually suffer from scale
misalignments between the low-resolution (LR) image and Ref image. In this
paper, we propose an Accelerated Multi-Scale Aggregation network (AMSA) for
Reference-based Super-Resolution, including Coarse-to-Fine Embedded PatchMatch
(CFE-PatchMatch) and Multi-Scale Dynamic Aggregation (MSDA) module. To improve
matching efficiency, we design a novel Embedded PatchMacth scheme with random
samples propagation, which involves end-to-end training with asymptotic linear
computational cost to the input size. To further reduce computational cost and
speed up convergence, we apply the coarse-to-fine strategy on Embedded
PatchMacth constituting CFE-PatchMatch. To fully leverage reference
information across multiple scales and enhance robustness to scale
misalignment, we develop the MSDA module consisting of Dynamic Aggregation and
Multi-Scale Aggregation. The Dynamic Aggregation corrects minor scale
misalignment by dynamically aggregating features, and the Multi-Scale
Aggregation brings robustness to large scale misalignment by fusing multi-
scale information. Experimental results show that the proposed AMSA achieves
superior performance over state-of-the-art approaches on both quantitative and
qualitative evaluations. The code is available at https://github.com/Zj-
BinXia/AMSA.

##  1 Introduction

Figure 1: Visual comparison of 4$\times$ SR results. The correspondences
matched by our AMSA are marked in red, and the correspondences matched by the
leading RefSR method, $C^{2}$-Matching (Jiang et al. 2021), are marked in
yellow. Compared with $C^{2}$-Matching, our approach can effectively match and
leverage reference information from the HR reference image to reconstruct a
visually appealing HR image with more accurate structures and fewer artifacts.

Reference-based Super-resolution (RefSR) aims to reconstruct a photo-realistic
high-resolution (HR) image from the low-resolution (LR) counterpart with the
guidance of an additional HR reference (Ref) image. The reference image
contains rich and diverse structures and textures, which could be relevant to
the content in the target HR image. By transferring relevant information
between the LR image and HR reference, recent RefSR methods (Yang et al. 2020;
Zhang et al. 2019b; Lu et al. 2021; Jiang et al. 2021) have shown promising
results.

The essential step in texture transfer for RefSR is to find correspondences
between the input image and the reference image. However, existing RefSR
methods (Yang et al. 2020; Zhang et al. 2019b) enumerate all possible patch
pairs and select the best-matched patches for aggregation, the computational
complexity of which is quadratic to image size. Although MASA (Lu et al. 2021)
matches correspondences in coarser resolution, yet consumes computation
resources quadratic to spatial size. Besides, since the convolution operation
is sensitive to the input scale (Zeiler and Fergus 2014), RefSR may miss the
best patch for reconstruction while matching and aggregating relevant feature
patches at different scales. To alleviate the resolution gap, $C^{2}$-Matching
(Jiang et al. 2021) recently applied knowledge distillation to force
correspondences relevant in feature space. Nevertheless, with the increase of
scale misalignment, the performance of $C^{2}$-Matching decreases rapidly.

To address the challenges mentioned above, we develop an Accelerated Multi-
Scale Aggregation network (AMSA) for Reference-based Super-Resolution. The
design of AMSA has several advantages. First, motivated by the discovery that
a large number of random samples often lead to good guesses (Barnes et al.
2009; Rong and Tan 2006; Duggal et al. 2019; Wang et al. 2021), we design a
novel Embedded PatchMatch scheme embedded in the network for end-to-end
training, which merely requires the asymptotic linear computational cost to
the input size. To further reduce computational cost and accelerate the
convergence of Embedded PatchMatch, we adopt the coarse-to-fine strategy that
uses the matchings from the coarse level to provide the subsequent finer
levels a good initialization start, constituting our Coarse-to-Fine Embedded
PatchMatch (CFE-PatchMatch).

Second, to enhance robustness to scale misalignment between the LR and Ref
image and makes full use of multi-scale relevant information in the Ref image,
we propose the Multi-Scale Dynamic Aggregation (MSDA) consisting of Dynamic
Aggregation and Multi-Scale Aggregation. The Dynamic Aggregation uses the DCN
(Dai et al. 2017) form to correct minor scale misalignment. Furthermore, the
Multi-Scale Aggregation fuses multi-scale reference information to obtain
robustness to large scale misalignment. In sum, as shown in Figure 1, compared
with the state-of-the-art method (Jiang et al. 2021), our AMSA matches and
transfers reference information effectively to produce visually pleasant
details. Additionally, we achieve over 0.3dB improvement on the CUFED5 dataset
with 100 times acceleration in matching correspondences. Our main
contributions are as follows:

  * •

We design a novel Coarse-to-Fine Embedded PatchMatch scheme, which involves
end-to-end training successfully and obtains good matching results with
asymptotic linear computational cost to the input size.

  * •

To enhance robustness to scale misalignment and fully utilize the multi-scale
relevant information in the Ref image, we propose the Multi-Scale Dynamic
Aggregation module. MSDA uses Dynamic Aggregation to correct minor scale
misalignment and applies Multi-Scale Aggregation to obtain robustness to large
scale misalignment.

  * •

Compared with SOTA methods, our model achieves superior performance with less
computational cost in correspondence matching.

##  2 Related Work

###  2.1 Single Image Super-Resolution

The SISR methods (Dong et al. 2015; Lim et al. 2017; Kim, Kwon Lee, and Mu Lee
2016; Zhang et al. 2018a; Ledig et al. 2017; Zhang et al. 2018b; Dai et al.
2019) based on deep learning learn an end-to-end image mapping function
between LR and HR images, which achieves better performance than conventional
algorithms. Generally, commonly used Mean Square Error (MSE) and Mean Absolute
Error (MAE) objective functions are prone to generate unexpected over-
smoothing results. Consequently, various subsequent works tend to design loss
functions to enhance visual quality. Johnson, Alahi, and Fei-Fei (2016)
introduced perceptual loss with VGG (Simonyan and Zisserman 2014) and showed
visually satisfying results. SRGAN (Ledig et al. 2017) enforced SR results
close to the distribution of the natural image by taking GANs as the
adversarial loss. Furthermore, the knowledge distillation framework is also
explored to improve the SR performance in recent works (Gao et al. 2018; Lee
et al. 2020).

###  2.2 Reference-based SR

Unlike Single Image Super-Resolution (SISR), RefSR reconstructs finer details
by referring to additional HR images. The Ref image generally has relevant
content with the LR image to provide realistic details. Recent works (Xie et
al. 2020; Cui 2020) mostly use CNN-based frameworks. One part of RefSR
implicitly aligns Ref and LR images by the network. CrossNet (Zheng et al.
2018) warped reference features with optical flow. Nevertheless, it relied on
the flow estimated network, resulting in high computational burdens and
inaccurate estimation. Besides, SSEN (Shim, Park, and Kweon 2020) employed
deformable convolution (Dai et al. 2017) to align the LR and Ref images.

Another part of RefSR explicitly matches relevant features. SRNTT (Zhang et
al. 2019b) and TTSR (Yang et al. 2020) applied an enumerated patch matching
mechanism upon the feature map to swap relevant texture features, requiring
extensive computational resources. To alleviate the problem, MASA (Lu et al.
2021) adopts a hierarchical enumerated correspondence matching scheme.
Furthermore, the resolution gap between LR and Ref images has negative impacts
on transferring HR details. Consequently, $C^{2}$-Matching introduced
knowledge (Hinton, Vinyals, and Dean 2015) to force correspondences of LR and
Ref images to be similar. However, the computational complexity of MASA is
quadratic to the input size, and the performance of $C^{2}$-Matching still
decreases sharply with the scale misalignment between LR and Ref images
increasing. To address the above issues, we propose CFE-PatchMatch to further
reduce computational cost and develop the MSDA module to enhance robustness to
the scale misalignment and fully use informative features across multiple
scales.

##  3 Method

Figure 2: The overview of Accelerated Multi-Scale Aggregation network for
Reference-based Super-Resolution.

The overview of our proposed AMSA is shown in Figure 2. Given the LR and Ref
image, we apply 4$\times$ bicubic-upsampling on LR to obtain LR$\uparrow$
image and $k^{i}\times$ bicubic-downsampling on Ref image to obtain multi-
scale reference images Refi, where $k$ ($k<1$) is a constant and $i\in[0,n)$.
For correspondence matching, HR Feature Extractor and LR Feature Extractor,
pretrained with contrastive learning (He et al. 2020) and knowledge
distillation (Hinton, Vinyals, and Dean 2015) as $C^{2}$-Matching did,
extracts feature maps $\boldsymbol{Q}_{i}$ and $\boldsymbol{K}$ from Refi and
LR$\uparrow$ image respectively. Afterward, CFE-PatchMatch matches
correspondences between $\boldsymbol{Q}_{i}$ and $\boldsymbol{K}$ efficiently
and effectively, obtaining correspondence position map $\boldsymbol{H}_{i}$
and correspondence relevance map $\boldsymbol{S}_{i}$. For SR restoration, LR
and HR Content Feature Extractor extract feature map $\boldsymbol{F}$ and
$\boldsymbol{V}_{i}$ from LR and Refi for relevant features transfer. After
that, to alleviate minor scale misalignment between LR and Ref images, the
Dynamic Aggregation of MSDA dynamically aggregates features from
$\boldsymbol{V}_{i}$ and $\boldsymbol{F}$ according to $\boldsymbol{H}_{i}$.
To fully exploit reference information across multiple scales and further
enhance robustness to large scale misalignment, the Multi-Scale Aggregation of
MSDA fuses all features maps according to $\boldsymbol{S}_{i}$ and uses
several convolutional layers to generate SR results.

###  3.1 Coarse-to-Fine Embedded PatchMatch

Figure 3:  The illustration of CFE-PatchMatch. (a) Embedded PatchMatch repeats
$M\log(\sqrt{N}/8)$ times ($t=$ 0 to $\log(\sqrt{N}/8)-1$, $T=$ 0 to $M-1$) to
predict the correspondence position map, where $N$ is the Ref and LR$\uparrow$
image spatial size. $\boldsymbol{H}_{i}^{t}$ and $\boldsymbol{S}_{i}^{t}$ are
the middle correspondence positionx and relevance relevance in $t$-th
iteration. (b) Coarse-to-Fine Embedded PatchMatch applies Embedded Patchmatch
on $\frac{1}{8}$, $\frac{1}{4}$, $\frac{1}{2}$ and original scales to obtain
$\boldsymbol{H}_{i}$ and $\boldsymbol{S}_{i}$ rapidly.

Previous RefSR methods (Yang et al. 2020; Zhang et al. 2019b; Jiang et al.
2021) match relevant patches by the enumerated global searching between LR and
Ref images consuming massive computational resources. Although MASA (Lu et al.
2021) matches correspondences in the coarser scale to reduce the computational
cost, its complexity is still quadratic with respect to the input size. To
tackle this issue, we design a Coarse-to-Fine Embedded PatchMatch (CFE-
PatchMatch) scheme to further reduce the computational cost with a
hierarchical random matching strategy.

Embedded PatchMatch. Embedding PatchMatch is embedded in the network
participating in end-to-end training. The illustration of Embedded PatchMatch
is shown in Figure 3 (a). The layers of Embedded PatchMatch are designed as
follows:

  1. 1.

Initialization layer. As shown in Figure 3 (a), for initialization, the
patches in $\boldsymbol{Q}_{i}$ match patches in $\boldsymbol{K}$ randomly or
according to previously obtained the correspondence position map
$\boldsymbol{H}_{i}^{0}\in{\rm\mathbb{R}^{H_{\boldsymbol{K}}\times
W_{\boldsymbol{K}}}}$. Then we calculate
$\boldsymbol{S}_{i}^{0}\in{\rm\mathbb{R}^{H_{\boldsymbol{K}}\times
W_{\boldsymbol{K}}}}$, which represents the relevance between LR$\uparrow$ and
Refi images. For each patch position $j$ in $\boldsymbol{K}$ and $j^{\prime}$
in $\boldsymbol{Q}_{i}$, we calculate the relevance $r_{i,j,j^{\prime}}$
between these two patches by normalized inner product, which is expressed as
Eq 1. Consequently, given patch position $j$ and its matched patch position
$\boldsymbol{H}_{i,j}^{0}$ in $\boldsymbol{Q}_{i}$, we obtain the relevance
$\boldsymbol{S}_{i,j}^{0}$ as Eq 2:

$r_{i,j,j^{{}^{\prime}}}=\left\langle\frac{\boldsymbol{K}_{j}}{{\left\|{{\boldsymbol{K}_{j}}}\right\|}_{2}},\frac{\boldsymbol{Q}_{i,j^{\prime}}}{{\left\|{{\boldsymbol{Q}_{i,j^{\prime}}}}\right\|}_{2}}\right\rangle,$
(1) $\boldsymbol{S}_{i,j}^{0}=r_{i,j,\boldsymbol{H}_{i,j}^{0}}.$ (2)

  2. 2.

LR Propagation & Evaluation layer. Each patch position $j$ in $\boldsymbol{K}$
propagates to its eight neighbors with dilation $2^{t}$. Then we compute the
relevance between $\boldsymbol{K}_{j}$ and the matched patch of its neighbors
and update with the most relevant one. The process can be expressed as:

$\boldsymbol{S}_{i,j}^{t+1}=\mathop{\max}_{{u\in
N_{\boldsymbol{K}}(j)}}r_{i,j,\boldsymbol{H}_{i,u}^{t}},$ (3)

$u^{\prime}=\mathop{\arg\max}_{{u\in
N_{\boldsymbol{K}}(j)}}r_{i,j,\boldsymbol{H}_{i,u}^{t}},$ (4)
$\boldsymbol{H}_{i,j}^{t+1}=\boldsymbol{H}_{i,u^{\prime}}^{t},$ (5)

where $N_{\boldsymbol{K}}(j)$ is a set including position $j$ and its eight
neighbors with dilation $2^{t}$.

  3. 3.

Ref Propagation & Evaluation layer. The matched patch position
$\boldsymbol{H}_{i,j}$ in $\boldsymbol{Q}_{i}$ of each patch position $j$ in
$\boldsymbol{K}$ propagates to eight neighbors with dilation $2^{t}$. Then we
compute the relevance between $\boldsymbol{K}_{j}$ and the neighbors of
$\boldsymbol{H}_{i,j}$, and update with the best-matched patch as step 2 does.

  4. 4.

Iteration. Repeat step 2 and step 3 $M\log(\sqrt{N}/8)$ times.

Coarse-to-Fine Embedded PatchMatch. The illustration of CFE-PatchMatch is
shown in Figure 3 (b). CFE-PatchMatch performs the basic Embedded PatchMatch
module on multiple resolutions to predict correspondence position map Hi while
further reduce computational cost and accelerate convergence.

Computational Complexity Analysis. The Embedded PatchMatch iterates
$M\log(\sqrt{N}/8)$ steps, where $M$ is a constant, and $N$ is the Ref and
LR$\uparrow$ image spatial size. Each patch of Embedded PatchMatch propagates
to eight neighbors with dilation $2^{t}$ and repeats $M\log(\sqrt{N}/8)$
times, the computational complexity of which is
$\mathcal{O}(MN\log(\sqrt{N}/8))$. The Coarse-to-Fine Embedded PatchMatch, as
shown in Figure 3 (b), applies Embedded PatchMatch on $1/8$, $1/4$, $1/2$, and
$1$ scales, which consumes around
$\mathcal{O}(\frac{85}{64}MN\log(\sqrt{N}/8)-\frac{27}{64}MN)$.

###  3.2 Multi-Scale Dynamic Aggregation

To alleviate the performance drop caused by scale misalignment between the LR
and Ref image and make full use of reference information across multiple
scales, we propose Multi-Scale Dynamic Aggregation (MSDA), including Dynamic
Aggregation and Multi-Scale Aggregation. In Dynamic Aggregation, we adopt the
modified DCN form (Dai et al. 2017) to correct minor scale misalignment yet
fail to deal with large scale misalignment. Thus, we design a Multi-Scale
Aggregation by aggregating multi-scale reference information to obtain
robustness to large scale misalignment.

Dynamic Aggregation. After obtaining correspondence position map
$\boldsymbol{H}_{i}$ and relevance map $\boldsymbol{S}_{i}$ between
LR$\uparrow$ and Refi images, MSDA dynamically aggregate reference features
across multiple scales. Specifically, for each position $p$ in
$\boldsymbol{K}$, we need to aggregate the features around its correspondence
position $\boldsymbol{H}_{i,p}$ in $\boldsymbol{Q}_{i}$. Thus, the offset
between position $p$ and $\boldsymbol{H}_{i,p}$ can be denoted as
$p_{0}=\boldsymbol{H}_{i,p}-p$. The dynamic aggregation can be expressed as a
modified DCN form:

$\boldsymbol{Y}^{\prime}_{i}(p)=\sum_{j=1}^{9}w_{j}\cdot\boldsymbol{V}_{i}\left(p+p_{0}+p_{j}\right),$
(6)
$\Delta\boldsymbol{P}=\operatorname{Conv}\left(\left[\boldsymbol{F};\boldsymbol{Y}_{i}^{\prime}\right]\right),$
(7)
$\boldsymbol{Y}_{i}(p)=\sum_{j=1}^{9}w_{j}\cdot\boldsymbol{V}_{i}\left(p+p_{0}+p_{j}+\Delta\boldsymbol{P}_{j}(p)\right),$
(8)

where $w_{j}$ denotes the convolution kernel weight, and
$p_{j}\in\\{(1,1),(1,0)...(-1,-1)\\}$. $\boldsymbol{Y}_{i}^{\prime}$ and
$\boldsymbol{Y}_{i}$ are the standard aggregated reference feature and dynamic
aggregated reference feature, respectively. $\Delta\boldsymbol{P}$ is the
dynamic offset map, and $\boldsymbol{F}$ is the feature map of LR. In
addition, $\operatorname{Conv}$ indicates the convolution operation, and
$\left[;\right]$ represents the concatenation operation.

Multi-Scale Aggregation. To enhance the robustness to large scale misalignment
and fully utilize reference information $\boldsymbol{Y}_{i}$ across scales, we
fuse multi-scale reference features by relevance map $\boldsymbol{S}_{i}$. The
process is expressed as :

$\boldsymbol{S}_{i}^{\prime}=\frac{\exp\left(\boldsymbol{S}_{i}\right)}{\sum_{j=1}^{n}\exp\left(\boldsymbol{S}_{j}\right)},$
(9)
$\boldsymbol{Z}=\operatorname{Conv}\left(\sum_{i}^{n}\boldsymbol{Y}_{i}\cdot\boldsymbol{S}_{i}^{\prime}\right),$
(10)

where $\boldsymbol{Z}$ is the output SR image, and $n$ is the number of
downsampled Ref images.

###  3.3 Loss Functions

We use three commonly used loss functions to train our model, including
reconstruction loss ${\cal L}_{rec}$, perceptual loss ${\cal L}_{per}$, and
adversarial loss ${\cal L}_{adv}$. For the reconstruction loss, we adopt the
$\ell_{1}$-norm. For the perceptual loss, we calculate it on relu5-1 VGG
(Simonyan and Zisserman 2014) features. For the adversarial loss, we employ
WGAN-GP (Gulrajani et al. 2017). The overall loss function of our model is
ultimately designed as:

${\cal L}=\lambda_{rec}{\cal L}_{rec}+\lambda_{per}{\cal
L}_{per}+\lambda_{adv}{\cal L}_{adv}.$ (11)

Table 1: Quantitative Comparisons. PSNR / SSIM are used for evaluation. We group methods by SISR and RefSR. We mark the best results in bold. The models trained with GAN loss are marked in gray. The suffix ’rec’ means only reconstruction loss is used for training. | Method | CUFED5 | Sun80 | Urban100 | Manga109
---|---|---|---|---|---
| SRCNN | 25.33 / .745 | 28.26 / .781 | 24.41 / .738 | 27.12 / .850
| EDSR | 25.93 / .777 | 28.52 / .792 | 25.51 / .783 | 28.93 / .891
| RCAN | 26.06 / .769 | 29.86 / .810 | 25.42 / .768 | 29.38 / .895
SISR | SRGAN | 24.40 / .702 | 26.76 / .725 | 24.07 / .729 | 25.12 / .802
| ENet | 24.24 / .695 | 26.24 / .702 | 23.63 / .711 | 25.25 / .802
| ESRGAN | 21.90 / .633 | 24.18 / .651 | 20.91 / .620 | 23.53 / .797
| RankSRGAN | 22.31 / .635 | 25.60 / .667 | 21.47 / .624 | 25.04 / .803
| CrossNet | 25.48 / .764 | 28.52 / .793 | 25.11 / .764 | 23.36 / .741
| SRNTT | 25.61 / .764 | 27.59 / .756 | 25.09 / .774 | 27.54 / .862
| SRNTT-rec | 26.24 / .784 | 28.54 / .793 | 25.50 / .783 | 28.95 / .885
| TTSR | 25.53 / .765 | 28.59 / .774 | 24.62 / .747 | 28.70 / .886
| TTSR-rec | 27.09 / .804 | 30.02 / .814 | 25.87 / .784 | 30.09 / .907
| SSEN | 25.35 / .742 | - | - | -
RefSR | SSEN-rec | 26.78 / .791 | - | - | -
| CIMR | 26.16 / .781 | 29.67 / .806 | 25.24 / .778 | -
| CIMR-rec | 26.35 / .789 | 30.07 / .813 | 25.77 / .792 | -
| MASA | 24.92 / .729 | 27.12 / .708 | 23.78 / .712 | -
| MASA-rec | 27.54 / .814 | 30.15 / .815 | 26.09 / .786 | -
| $C^{2}$-Matching | 27.16 / .805 | 29.75 / .799 | 25.52 / .764 | 29.73 / .893
|  $C^{2}$-Matching-rec | 28.24 / .841 | 30.18 / .817 | 26.03 / .785 | 30.47 / .911
Ours | AMSA | 27.31 / .809 | 29.83 / .803 | 25.60 / .770 | 29.79 / .896
| AMSA-rec |  28.50 / .849 |  30.29 / .819 |  26.18 / .789 |  30.57 / .914
Figure 4: Qualitative Comparisons. For all the shown examples, our method
significantly outperforms other state-of-the-arts, particularly in the image
rich in texture details.

##  4 Experiments

###  4.1 Dataset

Figure 5: Exploration on Coarse-to-Fine Embedded PatchMatch convergence in
different scales. The horizontal axis represents the number of iteration
times, and the vertical axis indicates the Mean Squared Error (MSE) between
the CFE-PatchMatch and enumerated matching results.

We train and test our network on the CUFED5 (Zhang et al. 2019b) dataset. The
CUFED5 dataset contains a training set with 11871 $160\times 160$ image pairs
and a testing set with 126 images accompanied by 5 reference images in
different relevance levels. Additionally, we test our network on the Sun80,
Urban100, and Manga109 datasets. The Sun80 (Sun and Hays 2012) dataset
consists of 80 natural images, each of which includes several reference
images. The Urban100 (Huang, Singh, and Ahuja 2015) dataset without reference
images contains 100 architectural images with strong self-similarity, and the
LR versions of images serve as reference images. Manga109 (Matsui et al. 2017)
also lacks reference images, and we randomly select HR reference images from
this dataset.

###  4.2 Implementation Details

For Coarse-to-Fine Embedded PatchMatch, the iteration $M$ of Embedded
PatchMatch on $\frac{1}{8}$, $\frac{1}{4}$, $\frac{1}{2}$ and original scales
are set to 1, 1, 2, and 6 times, separately. In addition, for the MSDA module
of AMSA, we set the downsampled factor $k$ and the number of downsampled
$Ref_{i}$ to 0.8 and 5, respectively.

AMSA is trained and tested in a scale factor of 4 between the LR and HR image.
We augment training data by randomly horizontally and vertically flipping
followed by randomly rotating 90∘, 180∘, and 270∘. The model is optimized by
ADAM optimizer with $\beta_{1}=0.9$, $\beta_{2}=0.99$ and initial learning
rate of 1e-4. Each mini-batch includes 9 LR patches with size $40\times 40$
along with 9 Ref patches with size $160\times 160$. The weights for ${\cal
L}_{rec}$, ${\cal L}_{per}$, and ${\cal L}_{adv}$ are 1.0, 10-4, and 10-6,
respectively. The model is implemented by PyTorch on an NVIDIA 2080Ti GPU.

###  4.3 Comparison with State-of-the-Art Methods

We compare the proposed AMSA with state-of-the-art SISR and RefSR algorithms.
The compared SISR methods include SRCNN (Dong et al. 2015), EDSR (Lim et al.
2017), RCAN (Zhang et al. 2018a), SRGAN (Ledig et al. 2017), ENet (Sajjadi,
Scholkopf, and Hirsch 2017), ESRGAN (Wang et al. 2018), RankSRGAN (Zhang et
al. 2019a), among which RCAN has achieved superior performance in terms of
PSNR/SSIM. Thanks to the generative adversarial learning strategy, ESRGAN and
RSRGAN gain state-of-the-art visual quality. For RefSR, the compared methods
include CrossNet (Zheng et al. 2018), SRNTT (Zhang et al. 2019b), TTSR (Yang
et al. 2020), SSEN (Shim, Park, and Kweon 2020), CIMR (Cui 2020), MASA (Lu et
al. 2021), and $C^{2}$-Matching (Jiang et al. 2021), among which
$C^{2}$-Matching and MASA outperform the previous RefSR methods.

Quantitative evaluation. For fair comparison with other methods mainly
minimizing MAE or MSE on PSNR and SSIM, we train AMSA-rec with only
reconstruction loss function. The results of the quantitative evaluation are
illustrated in Table 1. Our AMSA outperforms leading methods by a large margin
on four datasets. Specifically, compared with $C^{2}$-Matching-rec, MASA-rec
and RCAN, the proposed AMSA-rec improves over 0.25 dB in the CUFED5 benchmark
while over 0.1 dB in Sun80, Urban100, and Manga109 datasets. The results
demonstrate that our method is superior to other SR methods.

Qualitative evaluation. The results of the qualitative evaluation are shown in
Figure 4, and our method has the best visual quality containing many realistic
details close to respective HR ground-truths. Specifically, as shown in the
first line, AMSA recovers the challenging face details successfully compared
with other methods. Furthermore, as shown in the second and third lines, AMSA
achieves significant improvements in restoring the word and architecture
textures.

##  5 Ablation Study

Figure 6: Ablation study on the MSDA module. Table 2: Ablation experiments conducted on CUFED5 to study the effectiveness of the proposed Multi-Scale Dynamic Aggregation (MSDA) module and CFE-PatchMatch. The middle three options are correspondence matching modules, where the Enumerated-Matching is adopted in $C^{2}$-Matching, and Match $\&$ Extraction Module (MEM) is the matching acceleration module proposed in MASA. MSDA |  CFE-PatchMatch |  Enumerated Matching |  MEM |  PSNR |  GFLOPs
---|---|---|---|---|---
✓ |  ✓ |  ✗ |  ✗ |  28.50 |  279.52
✓ |  ✗ |  ✓ |  ✗ |  28.51 |  29297.82
✓ |  ✗ |  ✗ |  ✓ |  28.43 |  1479.87
✗ |  ✓ |  ✗ |  ✗ |  28.21 |  83.15
✗ |  ✗ |  ✓ |  ✗ |  28.24 |  8715.44
✗ |  ✗ |  ✗ |  ✓ |  28.09 |  440.23

Accelerated Multi-Scale Aggregation network for Reference-based Super-
Resolution. To demonstrate the effectiveness of the proposed Multi-Scale
Dynamic Aggregation module (MSDA) and Coarse-to-Fine Embedded PatchMatch (CFE-
PatchMatch), we progressively add modules and compare with other matching
methods. The input is assumed to be the size of 250$\times$250, and channels
are 256. As shown in Table 2, comparing the first and fourth lines, MSDA
brings around 0.3 dB improvement on the PSNR. Besides, comparing the first and
second lines, our CFE-PatchMatch is about 100 times more efficient than the
enumerated matching method while achieving comparable performance. Comparing
the first and third lines, CFE-PatchMatch is more efficient and effective than
MEM.

The convergence of Coarse-to-Fine Embedded PatchMatch in different scales. To
explore the convergence of CFE-PatchMatch, we apply Embedded PatchMatch on
$\frac{1}{8}$, $\frac{1}{4}$, $\frac{1}{2}$, and original scales,
respectively. Besides, we verify the convergence of CFE-PatchMatch, which
iterates 1, 1, 2, and 6 times on $\frac{1}{8}$, $\frac{1}{4}$, $\frac{1}{2}$,
and original scales separately. As shown in Figure 5, coarse-to-fine strategy
brings fast convergence with less computational cost. Specifically, CFE-
PatchMatch and Embedded PatchMatch both converge in 10 times iterations on the
original scale, yet CFE-PatchMatch performs the top four iterations on the
coarse scale to save around half computational cost and achieve less MSE.

Multi-Scale Dynamic Aggregation module. To verify the effectiveness of our
MSDA to scale misalignment, we compare Dynamic Aggregation, Multi-Scale
Aggregation, MSDA (Dynamic Aggregation $+$ Multi-Scale Aggregation), and
$C^{2}$-Matching on CUFED5 (4$\times$) by downsampling Reference images with
different scale factors and $\frac{1}{2}\times$ downsampling LR images. As
shown in Figure 7, comparing our MSDA and $C^{2}$-Matching, when the
difference of scale factors ($\gamma$) between LR and reference images are
larger than 4, our MSDA accurately utilizes reference details in different
scales to achieve robust and superior performance. As $\gamma$ is less than 4,
reference images fail to provide $4\times$ reference details for LR images
causing a drop in performance, yet MSDA still performs better than
$C^{2}$-Matching by using several reference details in different scales. As
shown in Figure 6 and Figure 7, comparing Dynamic Aggregation and Multi-Scale
Aggregation, we can see that Dynamic Aggregation performs better on minor
scale misalignment, while Multi-Scale Aggregation shows superiority on large
scale misalignment.

Figure 7: The robustness for scale misalignment. The $\gamma$ indicates the
scale difference between LR and reference images. Table 3: Ablation study on
the influence of the relevance between LR and Ref images.

Method | TTSR-rec | MASA-rec
---|---|---
L1 | 27.09/.804 | 27.35/.814
L2 | 26.74/.791 | 26.92/.796
L3 | 26.64/.788 | 26.82/.793
L4 | 26.58/.787 | 26.74/.790
LR | 26.43/.782 | 26.59/.784
Method |  $C^{2}$-Matching-rec | AMSA-rec (ours)
L1 | 28.24/.841 | 28.58/849
L2 | 27.39/.813 | 27.52/.816
L3 | 27.17/.806 | 27.25/.809
L4 | 26.94/.799 | 27.04/.803
LR | 26.52/.784 | 26.63/.789

Reference relevance influence. To explore the influence of the relevance
between the LR and Ref image on the result, we specially conduct experiments
on CUFED5, which has reference images with different relevances. In Table 3,
”L1” to ”L4” are reference images in CUFED5, where ”L1” is the most relevant
one while ”L4” is the least relevant one. ”LR” represents taking the LR image
as Ref image. As shown in Table 3, our AMSA achieves the best performance
among RefSR methods with the same relevance level Ref image.

##  6 Conclusion

In this paper, we propose a novel Accelerated Multi-Scale Aggregation network
for Reference-based Super-Resolution to enable effective and efficient
reference information matching and aggregating. To reduce the massive
computational cost of matching correspondences between the LR and reference
image, we propose a Coarse-to-Fine Embedded PatchMatch involving end-to-end
training. Furthermore, to fully exploit reference details across multiple
scales and enhance robustness to scale misalignment, we develop a Multi-Scale
Dynamic Aggregation module, which consists of Dynamic Aggregation and Multi-
Scale Aggregation. Specifically, we apply Dynamic Aggregation to correct minor
scale misalignment and employ Multi-Scale Aggregation to enhance robustness to
large scale misalignment. Our method achieves state-of-the-art results both
quantitatively and qualitatively on different datasets.

##  7 Acknowledgments

This work was partly supported by the Natural Science Foundation of China
(No.62171251), the Natural Science Foundation of Guangdong Province
(No.2020A1515010711), the Special Foundation for the Development of Strategic
Emerging Industries of Shenzhen (No.JCYJ20200109143010272) and Oversea
Cooperation Foundation of Tsinghua Shenzhen International Graduate School.

## References

  * Barnes et al. (2009) Barnes, C.; Shechtman, E.; Finkelstein, A.; and Goldman, D. B. 2009.  PatchMatch: A randomized correspondence algorithm for structural image editing.  _ACM Trans. Graph._ , 28(3): 24.
  * Cui (2020) Cui, S. 2020.  Towards content-independent multi-reference super-resolution: Adaptive pattern matching and feature aggregation.  _European conference on computer vision_.
  * Dai et al. (2017) Dai, J.; Qi, H.; Xiong, Y.; Li, Y.; Zhang, G.; Hu, H.; and Wei, Y. 2017.  Deformable convolutional networks.  In _Proceedings of the IEEE international conference on computer vision_ , 764–773.
  * Dai et al. (2019) Dai, T.; Cai, J.; Zhang, Y.; Xia, S.-T.; and Zhang, L. 2019.  Second-order attention network for single image super-resolution.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 11065–11074.
  * Dong et al. (2015) Dong, C.; Loy, C. C.; He, K.; and Tang, X. 2015.  Image super-resolution using deep convolutional networks.  _IEEE transactions on pattern analysis and machine intelligence_ , 38(2): 295–307.
  * Duggal et al. (2019) Duggal, S.; Wang, S.; Ma, W.-C.; Hu, R.; and Urtasun, R. 2019.  Deeppruner: Learning efficient stereo matching via differentiable patchmatch.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 4384–4393.
  * Gao et al. (2018) Gao, Q.; Zhao, Y.; Li, G.; and Tong, T. 2018.  Image super-resolution using knowledge distillation.  In _Asian Conference on Computer Vision_ , 527–541. Springer.
  * Gulrajani et al. (2017) Gulrajani, I.; Ahmed, F.; Arjovsky, M.; Dumoulin, V.; and Courville, A. 2017.  Improved training of wasserstein gans.  _arXiv preprint arXiv:1704.00028_.
  * He et al. (2020) He, K.; Fan, H.; Wu, Y.; Xie, S.; and Girshick, R. 2020.  Momentum contrast for unsupervised visual representation learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 9729–9738.
  * Hinton, Vinyals, and Dean (2015) Hinton, G.; Vinyals, O.; and Dean, J. 2015.  Distilling the knowledge in a neural network.  _arXiv preprint arXiv:1503.02531_.
  * Huang, Singh, and Ahuja (2015) Huang, J.-B.; Singh, A.; and Ahuja, N. 2015.  Single image super-resolution from transformed self-exemplars.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 5197–5206.
  * Jiang et al. (2021) Jiang, Y.; Chan, K. C.; Wang, X.; Loy, C. C.; and Liu, Z. 2021.  Robust Reference-based Super-Resolution via C2-Matching.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2103–2112.
  * Johnson, Alahi, and Fei-Fei (2016) Johnson, J.; Alahi, A.; and Fei-Fei, L. 2016.  Perceptual losses for real-time style transfer and super-resolution.  In _European conference on computer vision_ , 694–711. Springer.
  * Kim, Kwon Lee, and Mu Lee (2016) Kim, J.; Kwon Lee, J.; and Mu Lee, K. 2016.  Accurate image super-resolution using very deep convolutional networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 1646–1654.
  * Ledig et al. (2017) Ledig, C.; Theis, L.; Huszár, F.; Caballero, J.; Cunningham, A.; Acosta, A.; Aitken, A.; Tejani, A.; Totz, J.; Wang, Z.; et al. 2017.  Photo-realistic single image super-resolution using a generative adversarial network.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 4681–4690.
  * Lee et al. (2020) Lee, W.; Lee, J.; Kim, D.; and Ham, B. 2020.  Learning with privileged information for efficient image super-resolution.  In _European Conference on Computer Vision_ , 465–482. Springer.
  * Lim et al. (2017) Lim, B.; Son, S.; Kim, H.; Nah, S.; and Mu Lee, K. 2017.  Enhanced deep residual networks for single image super-resolution.  In _Proceedings of the IEEE conference on computer vision and pattern recognition workshops_ , 136–144.
  * Lu et al. (2021) Lu, L.; Li, W.; Tao, X.; Lu, J.; and Jia, J. 2021.  MASA-SR: Matching Acceleration and Spatial Adaptation for Reference-Based Image Super-Resolution.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 6368–6377.
  * Matsui et al. (2017) Matsui, Y.; Ito, K.; Aramaki, Y.; Fujimoto, A.; Ogawa, T.; Yamasaki, T.; and Aizawa, K. 2017.  Sketch-based manga retrieval using manga109 dataset.  _Multimedia Tools and Applications_ , 76(20): 21811–21838.
  * Rong and Tan (2006) Rong, G.; and Tan, T.-S. 2006.  Jump flooding in GPU with applications to Voronoi diagram and distance transform.  In _Proceedings of the 2006 symposium on Interactive 3D graphics and games_ , 109–116.
  * Sajjadi, Scholkopf, and Hirsch (2017) Sajjadi, M. S.; Scholkopf, B.; and Hirsch, M. 2017.  Enhancenet: Single image super-resolution through automated texture synthesis.  In _Proceedings of the IEEE International Conference on Computer Vision_ , 4491–4500.
  * Shim, Park, and Kweon (2020) Shim, G.; Park, J.; and Kweon, I. S. 2020.  Robust reference-based super-resolution with similarity-aware deformable convolution.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 8425–8434.
  * Simonyan and Zisserman (2014) Simonyan, K.; and Zisserman, A. 2014.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_.
  * Sun and Hays (2012) Sun, L.; and Hays, J. 2012.  Super-resolution from internet-scale scene matching.  In _2012 IEEE International Conference on Computational Photography (ICCP)_ , 1–12. IEEE.
  * Wang et al. (2021) Wang, F.; Galliani, S.; Vogel, C.; Speciale, P.; and Pollefeys, M. 2021.  PatchmatchNet: Learned Multi-View Patchmatch Stereo.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 14194–14203.
  * Wang et al. (2018) Wang, X.; Yu, K.; Wu, S.; Gu, J.; Liu, Y.; Dong, C.; Qiao, Y.; and Change Loy, C. 2018.  Esrgan: Enhanced super-resolution generative adversarial networks.  In _Proceedings of the European Conference on Computer Vision (ECCV) Workshops_ , 0–0.
  * Xie et al. (2020) Xie, Y.; Xiao, J.; Sun, M.; Yao, C.; and Huang, K. 2020.  Feature representation matters: End-to-end learning for reference-based image super-resolution.  In _European Conference on Computer Vision_ , 230–245. Springer.
  * Yang et al. (2020) Yang, F.; Yang, H.; Fu, J.; Lu, H.; and Guo, B. 2020.  Learning Texture Transformer Network for Image Super-Resolution.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 5791–5800.
  * Zeiler and Fergus (2014) Zeiler, M. D.; and Fergus, R. 2014.  Visualizing and understanding convolutional networks.  In _European conference on computer vision_ , 818–833. Springer.
  * Zhang et al. (2019a) Zhang, W.; Liu, Y.; Dong, C.; and Qiao, Y. 2019a.  Ranksrgan: Generative adversarial networks with ranker for image super-resolution.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 3096–3105.
  * Zhang et al. (2018a) Zhang, Y.; Li, K.; Li, K.; Wang, L.; Zhong, B.; and Fu, Y. 2018a.  Image super-resolution using very deep residual channel attention networks.  In _Proceedings of the European conference on computer vision (ECCV)_ , 286–301.
  * Zhang et al. (2018b) Zhang, Y.; Tian, Y.; Kong, Y.; Zhong, B.; and Fu, Y. 2018b.  Residual dense network for image super-resolution.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2472–2481.
  * Zhang et al. (2019b) Zhang, Z.; Wang, Z.; Lin, Z.; and Qi, H. 2019b.  Image super-resolution by neural texture transfer.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 7982–7991.
  * Zheng et al. (2018) Zheng, H.; Ji, M.; Wang, H.; Liu, Y.; and Fang, L. 2018.  Crossnet: An end-to-end reference-based super resolution network using cross-scale warping.  In _Proceedings of the European conference on computer vision (ECCV)_ , 88–104.


#
string2string: A Modern Python Library for String-to-String Algorithms

Mirac Suzgun
Stanford University
Stuart M. Shieber
Harvard University

_In memory of Lynn._ Dan Jurafsky
Stanford University

###### Abstract

We introduce string2string, an open-source library that offers a comprehensive
suite of efficient algorithms for a broad range of string-to-string problems.
It includes traditional algorithmic solutions as well as recent advanced
neural approaches to tackle various problems in string alignment, distance
measurement, lexical and semantic search, and similarity analysis—along with
several helpful visualization tools and metrics to facilitate the
interpretation and analysis of these methods. Notable algorithms featured in
the library include the Smith-Waterman algorithm for pairwise local alignment,
the Hirschberg algorithm for global alignment, the Wagner-Fisher algorithm for
edit distance, BARTScore and BERTScore for similarity analysis, the Knuth-
Morris-Pratt algorithm for lexical search, and Faiss for semantic search.
Besides, it wraps existing efficient and widely-used implementations of
certain frameworks and metrics, such as sacreBLEU and ROUGE, whenever it is
appropriate and suitable. Overall, the library aims to provide extensive
coverage and increased flexibility in comparison to existing libraries for
strings. It can be used for many downstream applications, tasks, and problems
in natural-language processing, bioinformatics, and computational social
sciences. It is implemented in Python, easily installable via pip, and
accessible through a simple API. Source code, documentation, and tutorials are
all available on our GitHub page:
https://github.com/stanfordnlp/string2string.111Correspondence to:
<EMAIL_ADDRESS>
##  1 Introduction

String-to-string problems have a wide range of applications in various domains
and fields, including, but not limited to, natural-language processing (e.g.,
information extraction, spell checking, and semantic search), computational
molecular biology (e.g., DNA sequence alignment), programming languages and
compilers (e.g., parsing and compiling), as well as computational social
sciences and digital humanities (e.g., lexical and semantic analysis of
literary texts and corpora).

The current state of string-to-string processing, alignment, distance,
similarity, and search algorithms is marked by a multitude of implementations
in widely used programming languages, such as C++, Java, and Python. However,
many of these implementations are not integrated with one another—they also
lack flexibility, modularity, and comprehensive documentation, hindering their
accessibility to users. As such, there is a pressing need for a unified
platform that combines these functionalities into one accessible and
comprehensive system.

In this work, we present an open-source library that offers a broad collection
of algorithms and techniques for the alignment, manipulation, or evaluation of
string-to-string mappings.222We define a _string_ as an ordered collection of
characters—such as letters, numerals, symbols—which serves as a representation
of a unit of information, text, or data. Strings can be used to represent
anything, from simple sentences to complex nucleic acid sequences or elaborate
computer programs. These problems include measuring the lexical distance
between two strings (e.g., under the Levenshtein edit distance metric),
computing the local or global alignment between two DNA sequences (e.g., based
on a substitution matrix such as BLOSUM), calculating the semantic similarity
between two texts (e.g., using BART-embeddings), and performing efficient
semantic search (e.g., via the Faiss library by FAIR (Johnson et al., 2019)).

The string2string library has been purposefully crafted to prioritize key
design principles, including modularity, completeness, efficiency,
flexibility, and clarity. As an open-source initiative, the library will
continue to grow and adapt to meet the evolving of its user community in the
future, and we are committed to ensuring that the library remains a flexible,
accessible, and dynamic resource, capable of accommodating the changing
landscape of string-to-string problems and tasks.

Figure 1: The string2string library provides a broad set of algorithms and
techniques to tackle a variety of problems and tasks involving the pairwise
alignment, comparison, evaluation, manipulation, and processing of string-to-
string mappings. It includes the implementation of widely-used algorithms,
such as Smith-Waterman (Smith and Waterman, 1981) for local alignment, Knuth-
Morris-Pratt (Knuth et al., 1977) for identical string matching (search), and
Wagner-Fisher (Wagner and Fischer, 1974) for edit distance, as well as recent
neural approaches, such as BERTScore (Zhang et al., 2020) and BARTScore (Yuan
et al., 2021) for semantic similarity measurements and Faiss (Johnson et al.,
2019) for semantic search. The library has been designed to support not only
individual strings but also lists of strings so that users can align and
compare strings at the token, word, or sentence levels. It further contains
visualization features to allow users to visualize alignments and score
matrices of strings.

##  2 Related Work

The fields of natural-language processing and machine learning have a long-
standing and exemplary tradition of fostering a culture that values open-
source tools and libraries. While designing our own string-to-string library,
which includes both traditional algorithmic and neural approaches to various
problems, we have drawn inspirations from Natural Language Toolkit (NLTK; Bird
and Loper (2004)), Gensim (Řehůřek and Sojka, 2010), OpenGrm Ngram (Roark et
al., 2012), Stanford CoreNLP Toolkit (Manning et al., 2014), OpenNMT (Klein et
al., 2017), tensor2tensor (Vaswani et al., 2018), AllenNLP (Gardner et al.,
2018), fairseq (Ott et al., 2019), spaCy (Neumann et al., 2019), Stanza (Qi et
al., 2020), Transformers (Wolf et al., 2020), and Torch-Struct (Rush, 2020),
among many others.

Pairwise Alignment
---
Local alignment: The best possible matching substring or subsequence alignment
between two strings—based on a substitution matrix and gap penalty
function—allowing for gaps and mismatches within a specified region of the
input sequences.
$\star$ (a) Dynamic programming solution (Smith and Waterman, 1981):
$\mathcal{O}(nm)$ in terms of space and time.
Global alignment: The best possible alignment between two strings over their
entire length.
$\star$ (a) Dynamic programming solution (Needleman and Wunsch, 1970):
$\mathcal{O}(nm)$ in terms of space and time.
$\star$ (b) Divide-and-conquer + dynamic programming solution (Hirschberg,
1975): $\mathcal{O}(m)$ in terms of space and $\mathcal{O}(nm)$ time.
Longest common substring: The longest _contiguous_ substring that appears in
both strings.
$\star$ (a) Dynamic programming solution: $\mathcal{O}(nm)$ in terms of space
and time.
Longest common subsequence: The longest possible sequence of symbols that
appears in the same order in both strings.
$\star$ (a) Dynamic programming solution: $\mathcal{O}(nm)$ in terms of space
and time.
Dynamic time warping (DTW): The optimal warp path that minimizes the distance
between sequences of varying length.
$\star$ (a) Dynamic programming solution (Sakoe and Chiba, 1978):
$\mathcal{O}(nm)$ in terms of space and time.
$\star$ (b) Space-time improved version of (a) via Hirschberg (1975)’s
algorithm: Reduces space complexity to $\mathcal{O}(m)$.
Distance
Levenshtein edit distance: The minimum number of insertions, deletions, and
substitutions needed to convert $S$ into $T$.
$\star$ (a) Dynamic programming solution (Wagner and Fischer, 1974):
$\mathcal{O}(nm)$ in terms of space and time.
$\star$ (b) Space-improved version of (a): Reduces space complexity to
$\mathcal{O}(m)$ by storing only two rows.
Hamming distance: The total number of indices at which strings, $S$ and $T$,
of equal length differ.
$\star$ (a) Naive solution: $\mathcal{O}(n)$ in terms of space and time.
Damerau–Levenshtein distance: The minimum number of insertions, deletions,
substitutions, and adjacent transpositions needed to convert $S$ into $T$.
$\star$ (a) Dynamic programming solution (simple extension of the Wagner-
Fisher algorithm): $\mathcal{O}(nm)$ in terms of space and time.
$\star$ (b) Space-improved version of (a): Reduces space complexity to
$\mathcal{O}(m)$ by storing only two rows.
Jaccard distance: The inverse of Jaccard similarity (that is, 1.0 - Jaccard
similarity coefficient).
$\star$ (a) Naive solution: $\mathcal{O}(n)$ in terms of space and time.
Table 1: Overview of the pairwise string alignment and distance problems
addressed by the library, along with the algorithmic approaches employed to
solve them. In all instances, we assume that we are given two strings, $S$ and
$T$, over a finite alphabet $\Sigma$, where where $n=|S|$, $m=|T|$, and
$k=|\Sigma|$, with $m\leq n$. Also, whenever possible, we include the brute-
force and memoized solutions to these problems (as in the case of edit
distance, for instance).

##  3 Overview of Algorithms

The string2string library offers a rich collection of algorithmic solutions to
tackle a wide range of string-to-string problems and tasks. We have clustered
these algorithms into four categories: pairwise alignment, distance
measurement, similarity analysis, and search.333By duality, distance
measurement methods can naturally be used for string similarity analysis, and
vice versa. Each category contains a suite of efficient algorithms that are
tailored to address specific problems within their respective domain. In what
follows, we provide a brief overview of these algorithms, along with the
associated problems or tasks they are designed to solve.

Similarity
---
Jaccard similarity: The size of the set of unique symbols that appear in both
strings (i.e., in the intersection) divided by the size of the set of the
union of the symbols in both strings.
$\star$ (a) Naive solution: $\mathcal{O}(n)$ in terms of space and time.
Jaro(-Winkler) similarity: A measure of similarity based on matching symbols
and transpositions in two strings.
$\star$ (a) Naive solution: $\mathcal{O}(nm)$ in terms of time and
$\mathcal{O}(n)$ in terms of space.
LCSubsequence similarity: A degree of similarity between two strings based on
the length of their longest common subsequence.
$\star$ (a) Based on the efficient solution to the longest common subsequence
problem.$\clubsuit$
Cosine similarity: The similarity between two strings based on the angle
between their corresponding vector representations.
$\star$ (a) Utilizes numpy and torch functions: $\mathcal{O}(E)$ in terms of
time and $\mathcal{O}(E)$ in terms of space.$\diamondsuit$
BERTScore (Zhang et al., 2020): A measure of semantic similarity that employs
contextualized embeddings derived from the pre-trained BERT model (Devlin et
al., 2019) to estimate the semantic closeness between two pieces of text.
$\star$ (a) Adaptation of the original BERTScore implementation:
$\mathcal{O}(nm)$ in terms of time and $\mathcal{O}(nm\cdot E)$ in terms of
space.
BARTScore (Yuan et al., 2021): A measure of semantic similarity that utilizes
the pre-trained BART model Lewis et al. (2020) and that achieves high
correlation with human judgements.
$\star$ (a) Adaptation of the original BARTScore implementation:
$\mathcal{O}(nm)$ in terms of time and $\mathcal{O}(nm\cdot E)$ in terms of
space.
Search
Lexical search:
$\star$ (a) Naive (brute-force) search: $\mathcal{O}(mn)$ in terms of match
time and $\mathcal{O}(1)$ in terms of space.
$\star$ (b) Rabin-Karp algorithm (Karp and Rabin, 1987): $\mathcal{O}(mn)$ in
terms of match time and $\mathcal{O}(1)$ in terms of space.
$\star$ (c) Boyer-Moore algorithm (Boyer and Moore, 1977): $\mathcal{O}(mn)$
in terms of match time and $\mathcal{O}(|\Sigma|)$ in terms of space..
$\star$ (d) Knuth-Morris-Pratt algorithm (Knuth et al., 1977):
$\mathcal{O}(n)$ in terms of match time and $\mathcal{O}(m)$ in terms of
space.
Semantic search:
$\star$ (a) FAISS (Johnson et al., 2019): $\mathcal{O}(\log^{2}n)$ in terms of
match time and $\mathcal{O}(n\cdot E)$ in terms of space.$\spadesuit$
Table 2: Overview of the string similarity and search solutions used in the
library. As in Table 1, we assume that we are provided with two strings, $S$
and $T$, over a finite alphabet $\Sigma$, where $n=|S|$, $m=|T|$, and
$k=|\Sigma|$, with $m\leq n$. Furthermore, we use $E$ to denote the size of
the embedding space (or token), whenever applicable. Both the Rabin-Karp and
Knuth-Morris-Pratt algorithms require $\Theta(m)$ time for pre-processing and
$\Theta(n)$ time for searching, whereas the Boyer-Moore algorithm has a pre-
processing time complexity of $\Theta(m+k)$. In terms of space, the Rabin-
Karp, Boyer-Moore, and Knuth-Morris-Pratt algorithms require $\Theta(1)$,
$\Theta(k)$. and $\Theta(m)$, respectively. Footnote $\clubsuit$: Please refer
to Eqn. (11) in (Suzgun et al., 2022a) for a mathematical formulation of
LCSubsequence similarity. Note that the authors call this similarity measure
“Sim-LCS.” Footnote $\diamondsuit$: We assume that the dimension (size) of the
two vectors are both $E$. Footnote $\spadesuit$: We invite our readers to look
at the blogpost by Feinberg (2019) for a detailed analysis of Facebook AI
Research’s Faiss algorithm.

###  3.1 Pairwise Alignment

Pairwise string alignment is the problem of identifying an optimal alignment
between two strings, such as nucleotide sequences in DNA or paragraphs in a
text. This task involves aligning them in such a way that maximizes the number
of matching symbols while allowing for gaps or mismatches where necessary.
Pairwise string alignment is a widely-used technique that plays a crucial role
in tasks such as DNA sequence alignment, database searching, and phylogenetic
analysis.

As exhibited in Table 1, the library, in its current state, provides efficient
solutions to local alignment, global alignment, longest common substring
(LCSubstring), longest common subsequence (LCSubsequence), and dynamic time
warping (DTW) problems. It is worth noting that all of the problems and tasks
covered in this suite can be solved using standard dynamic programming-based
solutions. Alternative approaches to long sequence or string alignment
problems, such as FASTA (Lipman and Pearson, 1985) and BLAST (Altschul et al.,
1990), also exist; they offer improved efficiency through the use of
probabilistic or heuristic methods, but they do not always guarantee optimal
solutions and may sacrifice accuracy for speed. Due to their ability to handle
large datasets quickly and provide reasonably accurate results, BLAST and
FASTA are still widely used in bioinformatics, and for that reason, we plan on
including them in the string2string library in the future.

###  3.2 Distance

String distance refers to the problem of quantifying the extent to which two
given strings are dissimilar based on a distance function. The Levenshtein
edit distance metric, for instance, corresponds to the minimum number of
insertion, deletion, or substitution operations required to transform one
string into another. It has a famous dynamic programming solution, which is
often referred to as the Wagner-Fisher algorithm (Wagner and Fischer, 1974).
In this library, we provide an implementation of the Wagner-Fisher
algorithm—which has a quadratic time and space complexity, as well as an
improved version of it—which reduces the overall space complexity to
linear.444Incidentally, we highlight an important discovery by Backurs and
Indyk (2015) that the edit distance between two strings cannot be computed in
strongly subquadratic time, unless the strong exponential time hypothesis is
false. We further cover and provide efficient solutions to the Hamming
distance, Damerau-Levenshtein distance, and Jaccard distance problems, as
shown in Table 1.

One noteworthy feature of the library is that it allows the user to specify
the weight of string operations (viz., insertions, deletions, substitutions,
and transpositions) depending on the distance function of choice. Furthermore,
it can compute the distance between not only string pairs but also pairs of
lists of strings, thereby not limiting the users to make comparisons only at
the character or symbol level.

###  3.3 Similarity

String similarity refers to the problem of measuring the degree to which two
given strings are similar to each other based on a similarity function—which
can be defined on various criteria, such as character matching, longest common
substring or subsequence comparison, or structural alignment. There is a
natural duality between string similarity measures and string distance
measures, which means that it possible to convert one into the other with
ease; hence, it is often the case that one uses string similarity and distance
measures interchangeably.

Jaccard similarity, Jaro similarity, Jaro-Winkler similarity, LCSubsequence
similarity, cosine similarity, BERTScore, and BARTScore are among the
similarity measures that are covered in the library. The first four can be
seen as lexical similarity measures, as they assess surface or structural
closeness, whereas the remaining three can be regarded as semantic similarity
measures, as they incorporate the implied meaning of the constituents of the
given strings into account.

The present library provides users with the ability to calculate cosine
similarity not only between individual words—via pre-trained GloVe (Pennington
et al., 2014) or fastText (Joulin et al., 2016) word embeddings—but also for
longer pieces of text such as sentences, paragraphs, or even documents—via
averaged or last-token embeddings obtained from a neural language model such
as BERT (Devlin et al., 2019). As we also mention in Section 4, this feature
enables users to compare the semantic similarity of longer segments of text in
only a few lines of code, providing greater flexibility in text analysis
tasks.

###  3.4 Search

String search, also known as string matching, refers to the problem of
determining whether a given pattern string exists inside a longer string. The
brute-force approach to string search would involve examining each position of
the longer string to determine if it matches the pattern string; however, this
method can be inefficient, particularly when dealing with large strings. In
the library, we therefore include the Rabin-Karp (Karp and Rabin, 1987),
Boyer-Moore (Boyer and Moore, 1977), and Knuth-Morris-Pratt (Knuth et al.,
1977) algorithms for identical string matching as well.

The library additionally provides support for semantic search via Facebook AI
Research’s Faiss library (Johnson et al., 2019), which, in essence, allows
efficient similarity search and clustering of dense vectors. In contrast to
the previous setup for identical string matching, Faiss initially requires the
user to provide a _list_ of strings (texts) as a corpus and creates a fixed-
vector representation of each string using a neural language model.555The user
is provided with the flexibility to determine how to obtain a fixed embedding
for each text. Specifically, the user has the option to choose between
different embedding methods, such as averaging the token embeddings or
selecting the embedding of the final token in the sequence. Once the
initialization of the corpus is done, one can perform “queries” on the corpus.
Given a new query, one can automatically get the embedding of that query, map
it onto the embedding space of the corpus, and return the nearest neighbours
of the query on the embedding space, thereby finding the texts that are
semantically closest to the query.

As one might imagine, string search algorithms are highly practical tools that
have a wide range of applications across different fields. These algorithms
allow users to locate and retrieve specific patterns within a long text or a
large corpus. For instance, the string search algorithms covered in the
string2string library—as shown in Table 2—can be used for pattern recognition,
DNA matching, plagiarism detection, and data mining, among many other
downstream applications and tasks.

##  4 Additional Features

One noteworthy feature of the library is its ability to simplify the use of
the GloVe (Pennington et al., 2014) or fastText Joulin et al. (2016) word
embeddings by enabling users to download and use them with just one line of
code. This streamlined process not only saves users time and effort but also
eliminates the need for additional installations or complex configurations. By
providing this feature, we have sought to make the library more accessible to
users and encourage the use of pre-trained word embeddings in various string-
to-string tasks and applications, such as measuring the cosine similarity
between two words.666Notably, fastText offers pre-trained word embeddings for
157 languages—trained on Common Crawl and Wikipedia—that one can easily
download and use with our library.

Similarly, users can seamlessly get the averaged or last token embeddings of a
piece of text from a pre-trained language model that is hosted on Hugging Face
Models (Wolf et al., 2020) or on their local path in a few lines of code, and
we provide both CPU and GPU support for these computations.

Figure 2: Alignment of two sequences, [ATT G GC GC A C G] and [X ATT GC GC A A
G], as obtained by the Needleman-Wunsch algorithm (Needleman and Wunsch,
1970). Our library allows users to visualize the pairwise alignment between
strings (or lists of strings).

Finally, we note that the library offers various visualization capabilities
that allow users to visually inspect the alignment between two strings or the
score matrix of the distance or similarity between them. This functionality
facilitates the understanding and interpretation of the output of various
algorithms and can aid in the selection of the most suitable algorithm for a
given task. By incorporating this feature into the library, we aim to enhance
the user experience and provide intuitive means of interpreting the
outputs.777For instance, our library provides a practical, hands-on tutorial
focused on the HUPD (Suzgun et al., 2022b), a large patent corpus. This
tutorial showcases the efficient use of our library’s functionalities and
features for performing semantic search and visualizing the textual content of
patent documents. Figure 2 shows a simple alignment between two lists of
strings, as generated by our library.

##  5 Library Design Principles

We have endeavoured to build a comprehensive and easy-to-use platform for
numerous string-to-string processing, comparison, manipulation, and search
algorithms. We have purposefully structured and organized the library to allow
easy customization, functional extension, and modular integration.

_Completeness._ The library offers a comprehensive set of classical algorithms
as well as neural approaches to tackle a wide range of string-to-string
problems. We have intentionally included both efficient and simpler solutions,
such as brute-force and memoization-based approaches, where appropriate. By
providing multiple solutions to the same problem, the library allows users to
compare and contrast the performance of different algorithmic methods. This
approach enhances users’ understanding of the trade-offs between different
algorithmic solutions and helps them appreciate the strengths and limitations
of each approach.

_Modularity._ To improve the efficiency and maintainability of the codebase,
we have adopted a modular design approach that breaks down the code into
smaller and self-contained modules. This approach simplifies the process of
adding new features and functionalities and modifying existing ones for
developers, while also enabling efficient testing, debugging, and overall
maintenance of the library. The modular design has allowed us to quickly
locate and fix any errors, without disrupting the entire codebase, during
development. Moreover, this modular approach ensures that the library is
scalable and adaptable to future updates and changes, which should enable us
to easily improve the library’s functionality and expand its use in various
tasks and applications moving forward.

_Efficiency._ We have taken great care to ensure that the algorithm
implementations are efficient both computationally and memory-wise so that
they could easily handle large datasets and complex tasks. We provide basic
support for process-based parallelism via Python’s inherent multiprocessing
package, as well as joblib. Additionally, we provide GPU support for neural-
based approaches, whenever applicable. While we strive to balance efficiency
and clarity, we acknowledge that in some cases, trade-offs may exist between
the two. In such cases, we have placed greater emphasis on clarity, ensuring
that the algorithms are transparent and easy to understand, even at the cost
of some efficiency. Nonetheless, we believe that the library’s overall
efficiency, combined with its transparency and comprehensibility, makes it a
valuable resource for the community.

_Support for List of Strings._ The library has been designed to support not
only individual strings but also lists of strings—whenever possible, enabling
users to align or compare strings at the subword or token level. This feature
provides greater flexibility in the library’s use cases, as it allows users to
analyze and compare more complex data structures beyond only individual
strings. By supporting lists of strings, the library can handle a wider range
of textual input types and structures.

_Strong Typing._ The use of strong typing requirements is an essential aspect
of the library, as it ensures that the inputs are always consistent and
accurate, which is crucial for generating reliable results. By carefully
annotating all the arguments of the algorithms used in the library, we have
sought to increase the robustness and reliability of the codebase. This
approach has helped prevent input-related errors, such as incorrect data type
or format, from occurring during execution.

_Accessibility._ The library has been implemented in Python, a programming
language which has been the core of many natural-language processing tools and
applications in academia and industry. The string2string library is
“pip”-installable and can be integrated into common machine learning and
natural-language processing frameworks such as PyTorch, TensorFlow, and
scikit-learn.

_Open-Source Effort._ The library is—and will remain—free and accessible to
all users. We hope that this approach will promote community-driven
development and encourage collaboration among researchers and developers,
enabling them to contribute to and improve the library.

##  6 Conclusion

We introduced string2string, an open-source library that offers a large
collection of algorithms for a broad range of string-to-string problems. The
library is implemented in Python, hosted on GitHub, and installable via pip.
It contains extensive documentation along with several hands-on tutorials to
aid users to explore and utilize the library effectively. With the help of the
open-source community, we hope to grow and improve the library. We encourage
users to feel free to provide us with feedback, report any issues, and propose
new features to expand the functionality and scope of the library.

## Acknowledgements

We would like to express our deepest appreciation to Corinna Coupette for
providing us with the inspiration to create this open-source library.
Furthermore, we would like to thank Sarah DeMott, Sebastian Gehrmann, Elena
Glassman, Tayfun Gür, Daniel E. Ho, Şule Kahraman, Deniz Keleş, Scott D.
Kominers, Christopher Manning, Luke Melas-Kyriazi, Tolúlọpẹ́ Ògúnrẹ̀mí,
Alexander “Sasha” Rush, George Saussy, Kutay Serova, Holger Spamann, Kyle
Swanson, and Garrett Tanzer for their valuable comments, useful suggestions,
and support. We owe a special debt of gratitude to Federico Bianchi for
inspecting our code, documentation, and tutorials many times and providing us
with such helpful and constructive feedback.

## References

  * Altschul et al. (1990) SF Altschul, W Gish, W Miller, EW Myers, and DJ Lipman. 1990.  Basic local alignment search tool.  _Journal of Molecular Biology_ , 215(3):403–410.
  * Backurs and Indyk (2015) Arturs Backurs and Piotr Indyk. 2015.  Edit distance cannot be computed in strongly subquadratic time (unless SETH is false).  In _Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing_ , STOC ’15, page 51–58, New York, NY, USA. Association for Computing Machinery.
  * Bird and Loper (2004) Steven Bird and Edward Loper. 2004.  NLTK: The natural language toolkit.  In _Proceedings of the ACL Interactive Poster and Demonstration Sessions_ , pages 214–217, Barcelona, Spain. Association for Computational Linguistics.
  * Boyer and Moore (1977) Robert S. Boyer and J. Strother Moore. 1977.  A fast string searching algorithm.  _Commun. ACM_ , 20(10):762–772.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Feinberg (2019) Vlad Feinberg. 2019.  Facebook AI similarity search (FAISS), part II.  Accessed on March 13, 2023.
  * Gardner et al. (2018) Matt Gardner, Joel Grus, Mark Neumann, Oyvind Tafjord, Pradeep Dasigi, Nelson F. Liu, Matthew Peters, Michael Schmitz, and Luke Zettlemoyer. 2018.  AllenNLP: A deep semantic natural language processing platform.  In _Proceedings of Workshop for NLP Open Source Software (NLP-OSS)_ , pages 1–6, Melbourne, Australia. Association for Computational Linguistics.
  * Hirschberg (1975) Daniel S. Hirschberg. 1975.  A linear space algorithm for computing maximal common subsequences.  _Communications of the ACM_ , 18(6):341–343.
  * Johnson et al. (2019) Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019.  Billion-scale similarity search with GPUs.  _IEEE Transactions on Big Data_ , 7(3):535–547.
  * Joulin et al. (2016) Armand Joulin, Edouard Grave, Piotr Bojanowski, Matthijs Douze, Hérve Jégou, and Tomas Mikolov. 2016.  FastText.zip: Compressing text classification models.  _arXiv preprint arXiv:1612.03651_.
  * Karp and Rabin (1987) Richard M Karp and Michael O Rabin. 1987.  Efficient randomized pattern-matching algorithms.  _IBM Journal of Research and Development_ , 31(2):249–260.
  * Klein et al. (2017) Guillaume Klein, Yoon Kim, Yuntian Deng, Jean Senellart, and Alexander Rush. 2017\.  OpenNMT: Open-source toolkit for neural machine translation.  In _Proceedings of ACL 2017, System Demonstrations_ , pages 67–72, Vancouver, Canada. Association for Computational Linguistics.
  * Knuth et al. (1977) Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt. 1977.  Fast pattern matching in strings.  _SIAM Journal on Computing_ , 6(2):323–350.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7871–7880.
  * Lipman and Pearson (1985) David J Lipman and William R Pearson. 1985.  Rapid and sensitive protein similarity searches.  _Science_ , 227(4693):1435–1441.
  * Manning et al. (2014) Christopher Manning, Mihai Surdeanu, John Bauer, Jenny Finkel, Steven Bethard, and David McClosky. 2014.  The Stanford CoreNLP natural language processing toolkit.  In _Proceedings of 52nd Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 55–60, Baltimore, Maryland. Association for Computational Linguistics.
  * Needleman and Wunsch (1970) Saul B Needleman and Christian D Wunsch. 1970.  A general method applicable to the search for similarities in the amino acid sequence of two proteins.  _Journal of molecular biology_ , 48(3):443–453.
  * Neumann et al. (2019) Mark Neumann, Daniel King, Iz Beltagy, and Waleed Ammar. 2019.  ScispaCy: Fast and robust models for biomedical natural language processing.  In _Proceedings of the 18th BioNLP Workshop and Shared Task_ , pages 319–327, Florence, Italy. Association for Computational Linguistics.
  * Ott et al. (2019) Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019.  fairseq: A fast, extensible toolkit for sequence modeling.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations)_ , pages 48–53, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014.  GloVe: Global vectors for word representation.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1532–1543, Doha, Qatar. Association for Computational Linguistics.
  * Qi et al. (2020) Peng Qi, Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D. Manning. 2020\.  Stanza: A python natural language processing toolkit for many human languages.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 101–108, Online. Association for Computational Linguistics.
  * Řehůřek and Sojka (2010) Radim Řehůřek and Petr Sojka. 2010.  Software framework for topic modelling with large corpora.  In _Proceedings of the LREC 2010 Workshop on New Challenges for NLP Frameworks_ , pages 45–50, Valletta, Malta. ELRA.  http://is.muni.cz/publication/884893/en.
  * Roark et al. (2012) Brian Roark, Richard Sproat, Cyril Allauzen, Michael Riley, Jeffrey Sorensen, and Terry Tai. 2012.  The OpenGrm open-source finite-state grammar software libraries.  In _Proceedings of the ACL 2012 System Demonstrations_ , pages 61–66, Jeju Island, Korea. Association for Computational Linguistics.
  * Rush (2020) Alexander Rush. 2020.  Torch-Struct: Deep structured prediction library.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 335–342, Online. Association for Computational Linguistics.
  * Sakoe and Chiba (1978) Hiroaki Sakoe and Seibi Chiba. 1978.  Dynamic programming algorithm optimization for spoken word recognition.  _IEEE transactions on acoustics, speech, and signal processing_ , 26(1):43–49.
  * Smith and Waterman (1981) T. F. Smith and Michael S. Waterman. 1981.  Identification of common molecular subsequences.  _Journal of molecular biology_ , 147 1:195–7.
  * Suzgun et al. (2022a) Mirac Suzgun, Luke Melas-Kyriazi, and Dan Jurafsky. 2022a.  Follow the wisdom of the crowd: Effective text generation via minimum Bayes risk decoding.  _arXiv preprint arXiv:2211.07634_.
  * Suzgun et al. (2022b) Mirac Suzgun, Luke Melas-Kyriazi, Suproteem K Sarkar, Scott Duke Kominers, and Stuart M Shieber. 2022b.  The Harvard USPTO Patent Dataset: A Large-Scale, Well-Structured, and Multi-Purpose Corpus of Patent Applications.  _arXiv preprint arXiv:2207.04043_.
  * Vaswani et al. (2018) Ashish Vaswani, Samy Bengio, Eugene Brevdo, Francois Chollet, Aidan N. Gomez, Stephan Gouws, Llion Jones, Łukasz Kaiser, Nal Kalchbrenner, Niki Parmar, Ryan Sepassi, Noam Shazeer, and Jakob Uszkoreit. 2018.  Tensor2tensor for neural machine translation.  _CoRR_ , abs/1803.07416.
  * Wagner and Fischer (1974) Robert A Wagner and Michael J Fischer. 1974.  The string-to-string correction problem.  _Journal of the ACM (JACM)_ , 21(1):168–173.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Yuan et al. (2021) Weizhe Yuan, Graham Neubig, and Pengfei Liu. 2021.  BARTScore: Evaluating generated text as text generation.  In _Advances in Neural Information Processing Systems_ , volume 34, pages 27263–27277. Curran Associates, Inc.
  * Zhang et al. (2020) Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q. Weinberger, and Yoav Artzi. 2020\.  BERTScore: Evaluating text generation with BERT.  In _International Conference on Learning Representations_.