<p>I am looking for an extension for Levenshtein distance (Edit distance) for multi dimensional strings (2D and 3D). I am not sure if there is a formal definition for multi dimensional or not, but here is what I am talking about:</p>

<p><strong>1-D string:</strong> is the regular string</p>

<p><strong>2-D string:</strong> is something like a list of 1-D strings like</p>

<pre><code>dfdsfdsfdsf
dsffgdfdgfdsdaf
dsfdsf
fdgfdgfdg
</code></pre>

<p><strong>N-D string:</strong> is list of (N-1)-D strings</p>

CC BY-SA 3.0
2013-09-14T09:55:18.687Z
I am not sure what you are asking about?
J.y B.y
CC BY-SA 3.0
2013-09-14T13:57:48.753Z
Voting to close as unclear. **Why** do you want such an extension?
Jeffε
CC BY-SA 3.0
2013-09-14T14:04:26.663Z
What do you want to extend it to? To the distance between such lists? What do you say that distance would be?
reinierpost
CC BY-SA 3.0
2013-09-14T14:06:17.443Z
A related (but more precise) question: http://stackoverflow.com/questions/16399597/edit-distance-between-two-graphs
J.-E. Pin
CC BY-SA 3.0
2013-09-15T12:22:02.293Z
@JɛﬀE, I disagree that this should be closed. If the asker knew precisely how to formalize the question, probably they would already have an answer! ... iampat, I think the standard dynamic programming approach should be extendable to comparing $n$-dimensional vectors instead of $1$-dimensional. You would need to define which operations you want (i.e., delete a row/column? delete an element and shift row left?). But then maybe we can define d[i1,j1,i2,j2] to be the min distance when comparing up to coordinate (i1,j1) of the first input and (i2,j2) of the second, and use dynamic programming.
usul
CC BY-SA 3.0
2013-09-16T21:35:59.817Z
Thanks for your comments. 
I want to use this distance in Kernel machine for learning some structure. In my problem, I need to model Location and Words simultaneously. I think the edit distance for Graphs can be modified for my application
iampat
<dynamic-programming><edit-distance>
extension for Levenshtein distance
iampat
# extension for Levenshtein distance

(Asked by: username_0 on 2013-09-14)

I am looking for an extension for Levenshtein distance (Edit distance) for multi dimensional strings (2D and 3D). I am not sure if there is a formal definition for multi dimensional or not, but here is what I am talking about:
1-D string: is the regular string
2-D string: is something like a list of 1-D strings like
dfdsfdsfdsf
dsffgdfdgfdsdaf
dsfdsf
fdgfdgfdg

N-D string: is list of (N-1)-D strings

**Tags:** dynamic-programming, edit-distance

> **Comments:**
> **username_1**: I am not sure what you are asking about?  
> **username_2**: Voting to close as unclear. **Why** do you want such an extension?  
> **username_3**: What do you want to extend it to? To the distance between such lists? What do you say that distance would be?  
> **username_4**: A related (but more precise) question: http://stackoverflow.com/questions/16399597/edit-distance-between-two-graphs  
> **username_5**: @JɛﬀE, I disagree that this should be closed. If the asker knew precisely how to formalize the question, probably they would already have an answer! ... username_0, I think the standard dynamic programming approach should be extendable to comparing $n$-dimensional vectors instead of $1$-dimensional. You would need to define which operations you want (i.e., delete a row/column? delete an element and shift row left?). But then maybe we can define d[i1,j1,i2,j2] to be the min distance when comparing up to coordinate (i1,j1) of the first input and (i2,j2) of the second, and use dynamic programming.  
> **username_0**: Thanks for your comments.  I want to use this distance in Kernel machine for learning some structure. In my problem, I need to model Location and Words simultaneously. I think the edit distance for Graphs can be modified for my application  

---

## 0 answers

