Native edit distance

[mbaroni]

Is your proposal related to a problem?

Right now, computation of edit distance relies on editdistance pkg: we would like to get rid of this dependency.

Describe the solution you'd like to have implemented

Implement our own edit distance function.

Additional context

Remember this is a textbook example of a problem to be solved with dynamic programming.

[robertodessi]

I agree about the textbook problem but I think we should check for the performance of a proposed implementation. If it is computationally expensive it might be a bottleneck when computing topsim on a large {train|valid|test} set. Thus, I would drop the dependency (https://pypi.org/project/editdistance/) only if a proposed solution has "comparable" performance

[eugene-kharitonov]

I am actually not sure if it is worth the effort at all?..

[mbaroni]

Changed the tag to low-priority

[robertodessi]

Closing this as it's probably not worth the effort