1
$\begingroup$

I'm currently working with finding edit distance between two string of unequal length. But I'm sorry to say that I've got only one algorithm using Dynamic programming to find out edit distance. But I'm dealing with some cryptographic measure with edit distance where algorithm with dynamic programming is not suitable. Please have a look at the algorithm. If we want to do this computation homomorphically, circuit-based computation is needed here which will time consuming one. Usually homomorphic computation works well where there is more additions than multiplications.

enter image description here

This is why, I'm looking for another algorithm rather than the above one.

$\endgroup$

closed as unclear what you're asking by David Richerby, hengxin, Evil, vonbrand, Luke Mathieson Jan 29 '16 at 1:00

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ We don't have a strict policy for list questions, but there is a general dislike. Please note also this and this discussion; you might want to improve your question to avoid the problems explained there. If you explain your specific situation in more detail, including why the algorithm you've already found is unsuitable, people will be able to recommend something specific, rather than creating a big list and hoping something's useful. $\endgroup$ – David Richerby Jan 28 '16 at 8:56
  • 2
    $\begingroup$ Please edit the question to explain what research you've done, why you are unhappy with the algorithm you have, and what requirements you want the other algorithms to satisfy. If you already know that you're not happy with one algorithm, then I'm worried that you might be unhappy with other algorithms we suggest too -- unless you tell us why you're unhappy with that algorithm and what requirements you want the other algorithm to satisfy, it's not clear how to help you. $\endgroup$ – D.W. Jan 28 '16 at 10:12
  • $\begingroup$ I've edited my question. Hopefully it is now better to understand. @David and D.W. $\endgroup$ – Tushar Saha Jan 28 '16 at 11:08
  • 1
    $\begingroup$ I appreciate the edit, but it doesn't really address any of the issues pointed out here. You still haven't told us what the requirements are. What I mean is that you need to give us the criteria by which you will evaluate answers, so we can know in advance whether a particular solution will meet your needs. OK, so you want to use the algorithm with some crypto thing -- well, what requirements does that impose on the algorithm? What properties does the algorithm need to have, in order to be useful to you? $\endgroup$ – D.W. Jan 28 '16 at 18:58
  • $\begingroup$ Question is edited again. Please have a look. @D.W $\endgroup$ – Tushar Saha Jan 29 '16 at 2:45
6
$\begingroup$

The fastest known exact algorithm is due to Masek and Paterson, and runs in time $O(n^2/\log n)$ for two strings of length $n$. Bačkurs and Indyk show that an $O(n^{2-\epsilon})$ algorithm would refute a (somewhat) widely believed conjecture, SETH, and Abboud et al. gave stronger results in this direction.

$\endgroup$
  • $\begingroup$ Many thanks for the papers. Here, so far I understood, both the authors handle string of same length of n. But I need to handle two string of different lengths. $\endgroup$ – Tushar Saha Jan 28 '16 at 11:27
  • $\begingroup$ In fact Masek and Paterson handle the general situation. The lower bounds indeed consider only the case where the two strings have the same length. $\endgroup$ – Yuval Filmus Jan 28 '16 at 11:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.