Edit distance

문자열 a를 문자열 b와 일치시키기 위해 몇 번의 편집 연산을 수행해야 하는지를 기준으로 정량화한 두 문자열 사이의 거리.

어떤 연산을 허용하는지에 따라 수치가 달라질 수 있다. 일례로 Levenshtein distance는 삽입, 대체, 삭제를 허용하는 반면, LCS distance는 삽입과 삭제만 허용.

See also

• Convolutional Embedding for Edit Distance
  • Edit-distance-based string similarity search has many applications such as spell correction, data de-duplication, and sequence alignment. However, computing edit distance is known to have high complexity, which makes string similarity search challenging for large datasets. In this paper, we propose a deep learning pipeline (called CNN-ED) that embeds edit distance into Euclidean distance for fast approximate similarity search. A convolutional neural network (CNN) is used to generate fixed-length vector embeddings for a dataset of strings and the loss function is a combination of the triplet loss and the approximation error. To justify our choice of using CNN instead of other structures (e.g., RNN) as the model, theoretical analysis is conducted to show that some basic operations in our CNN model preserve edit distance. Experimental results show that CNN-ED outperforms data-independent CGK embedding and RNN-based GRU embedding in terms of both accuracy and efficiency by a large margin. We also show that string similarity search can be significantly accelerated using CNN-based embeddings, sometimes by orders of magnitude.