<p><strong>Which results are known about the string edit distances using the edition operator &quot;Search and Replace&quot;?</strong></p>
<p>Edit distances were traditionally used in bio informatics and to correct typographical errors, and many edit distances (e.g. the &quot;Delete, Insert, Replace&quot; 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.</p>
<p>I believe that <strong>edit distances including an operator where all occurrences of a token</strong> (letter, word, block, your pick) <strong>are replaced by another token</strong>, with cost proportional to the length of the description of the operation (i.e. sum of the lengths of the two token) per operation (corresponding to the time required 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.</p>
<p>Yet, an internet search for &quot;search and replace Edit distance&quot; returned only unrelated results (e.g. a search and replace operators conditioned by edit distance, <a href="https://github.com/soodoku/Search-And-Replace" rel="nofollow noreferrer">https://github.com/soodoku/Search-And-Replace</a>). 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).</p>

CC BY-SA 4.0
2021-07-22T07:15:34.863Z
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)?
D.W.
CC BY-SA 4.0
2021-07-22T11:41:04.127Z
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!
J.y B.y
CC BY-SA 4.0
2021-07-22T18:23:12.133Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-07-22T18:33:03.437Z
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).
Emil Jeřábek
CC BY-SA 4.0
2021-07-23T12:31:51.117Z
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.
J.y B.y
CC BY-SA 4.0
2022-03-19T13:19:04.800Z
@EmilJeřábek Such an asymmetry is already present in edit distances that allow insertions but not deletions (and vice versa): it does not seem to be an issue neither for their use nor for their computation. I guess bioinformatic researchers are ok with an "edit distance" not being a proper metric.
J.y B.y
CC BY-SA 4.0
2024-09-06T19:32:45.823Z
A colleague pointed out that this is related to "Parameterized Pattern Matching", defined in 1996, where two strings $s$ and $s'$ "parameterize match" if there exists a bijection $\pi()$ such that $\pi(s)=s'$, where each character of $s$ is renamed by $\pi()$.  https://www.sciencedirect.com/science/article/pii/S0022000096900033
J.y B.y
<edit-distance><string-search>
"Search and Replace" Edit Distances
J.y B.y
# "Search and Replace" Edit Distances

(Asked by: username_0 on 2021-07-21)

**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 cost proportional to the length of the description of the operation (i.e. sum of the lengths of the two token) per operation (corresponding to the time required 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).

**Tags:** edit-distance, string-search

> **Comments:**
> **username_1**: 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)?  
> **username_0**: 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!  
> **username_2**: 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.  
> **username_2**: 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).  
> **username_0**: 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.  
> **username_0**: @EmilJeřábek Such an asymmetry is already present in edit distances that allow insertions but not deletions (and vice versa): it does not seem to be an issue neither for their use nor for their computation. I guess bioinformatic researchers are ok with an "edit distance" not being a proper metric.  
> **username_0**: A colleague pointed out that this is related to "Parameterized Pattern Matching", defined in 1996, where two strings $s$ and $s'$ "parameterize match" if there exists a bijection $\pi()$ such that $\pi(s)=s'$, where each character of $s$ is renamed by $\pi()$.  https://www.sciencedirect.com/science/article/pii/S0022000096900033  

---

## 0 answers

