Timeline for Edit distance of list with unique elements
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Apr 14, 2018 at 20:42 | history | bounty ended | Stefan Haustein | ||
| S Apr 14, 2018 at 20:42 | history | notice removed | Stefan Haustein | ||
| Apr 14, 2018 at 11:51 | answer | added | j_random_hacker | timeline score: 3 | |
| Apr 14, 2018 at 0:03 | comment | added | Albert Hendriks | For those wondering about the complexities: $m$ and $n$ are the lengths of the input strings and $s$ is the actual edit distance, so it is included in the complexity. The cost of each edit is considered 1 but is probably irrelevant for calculating this distance (the number of edits $s$). | |
| S Apr 13, 2018 at 14:41 | history | bounty started | Stefan Haustein | ||
| S Apr 13, 2018 at 14:41 | history | notice added | Stefan Haustein | Draw attention | |
| Jan 6, 2016 at 11:03 | history | edited | Kaveh | CC BY-SA 3.0 |
added 180 characters in body
|
| Jul 27, 2015 at 10:54 | history | edited | user362178 | CC BY-SA 3.0 |
Formal question
|
| Jul 27, 2015 at 10:06 | comment | added | user362178 | Yes, in this case the large alphabet is made up of database indexes and the "strings", s and t, are lists containing these indexes. | |
| Jul 27, 2015 at 8:53 | comment | added | D.W.♦ | I suspect the question is: How to compute the edit distance between $s,t$, where $s,t \in \Sigma^*$ are strings over some very large alphabet $\Sigma$, and we're guaranteed that no letter appears twice in $s$ or in $t$ (the OP represents each string as a list of letters, i.e., a list of elements). But this needs confirmation. | |
| Jul 27, 2015 at 6:24 | comment | added | Raphael | What is your question now; how to speed up pairwise edit distance, or how to speed up computing all pairwise distances of a list of strings? | |
| Jul 27, 2015 at 6:23 | history | edited | Raphael |
edited tags
|
|
| Jul 26, 2015 at 23:35 | history | tweeted | twitter.com/#!/StackCompSci/status/625449369433677825 | ||
| Jul 26, 2015 at 20:00 | review | First posts | |||
| Jul 27, 2015 at 11:01 | |||||
| Jul 26, 2015 at 19:55 | history | asked | user362178 | CC BY-SA 3.0 |