Which results are known about the string edit distances using the edition operator "Search and Replace"?

Edit distances were traditionally used in bio informatics and to correct typographical errors, and many edit distances (e.g. the "Delete, Insert, Replace" edit distance, aka Levenshtein distance) can be computed in quadratic time via dynamic programming. Some people seem to be using the Levenshtein distance to detect copies by students in online exam answers, which seem wrong: a few search and replace queries can arbitrarily increase the Levenshtein distance between the original answer and it's edited copy.

I believe that edit distances including an operator where all occurrences of a token (letter, word, block, your pick) are replaced by another token, with unitary cost per operation (corresponding to the constant time for a human to instruct a computer to perform such operation), would be more useful in the detection of such plagiarism (and in version control systems too, by the way). Combined with some linear preprocessing of the strings, such edit distances do not seem too prohibitively costly to compute either.

Yet, an internet search for "search and replace Edit distance" returned only unrelated results (e.g. a search and replace operators conditioned by edit distance, https://github.com/soodoku/Search-And-Replace). I am wondering if it already exists but under another name, or if I am mistaken about its difficulty (or if I should go on and work on it)!. Anybody who could let me know if I reinvented the wheel, just under a new name, or if my wheel is actually a square would save me much time!

Take care,


  • $\begingroup$ I imagine the question might be different if you ask about search-and-replace of a single letter vs a word, so it might be worthwhile to ask about those two separately. For a single letter: do you care more about the case of a small alphabet (so $|\Sigma|$ can be considered a constant that is small and unimportant) or a large alphabet (so you care about the running time as a function of both the length of the string and the alphabet size)? $\endgroup$
    – D.W.
    Jul 22 at 7:15
  • $\begingroup$ The difference between letters and words boils down to small and large (up to infinite) alphabets. I am aiming for theoretical results on large alphabets (in particular for the detection of plagiarism), and practical results with mixed weighted operators on words and letters (e.g. deleting a word takes constant time, but typing a new word or editing one takes linear time) matching the costs of human interfaces. But I am curious about any past results on such a problem (and in particular terminology), to make sure I don't reinvente the wheel! $\endgroup$
    – Jeremy
    Jul 22 at 11:41
  • 2
    $\begingroup$ If the operation really has unit cost, then the distance between any two strings is at most one, as you can just "search and replace" the whole text. If you want to get anything useful, the cost has to depend on the lengths of the "tokens" that you search and replace. $\endgroup$ Jul 22 at 18:23
  • $\begingroup$ Also, if you fix that, another funny thing is that the “distance” is not symmetric, as it is generally impossible to reverse a search-and-replace operation by another search-and-replace operation. Thus, it is not really a proper notion of distance (i.e., a metric). $\endgroup$ Jul 22 at 18:33
  • 1
    $\begingroup$ Good point about the asymmetry, thanks! My understanding is that a "token" is generally understood to be a word, but you are right that "students" could replace a sequence of words by another one at unitary cost. Good point, I will think more. $\endgroup$
    – Jeremy
    Jul 23 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.