[API Proposal]: Add EditDistance (Levenshtein) to TensorPrimitives for unEqual length <T> comparision.

[KungFuryKeyboard]

Background and motivation

With the new Tensor api we now have

HammingBitDistance

HammingDistance(ReadOnlySpan, ReadOnlySpan)

This solves distance between 2 equal-length tensors of values.

However what about unequal lengths ?

Other languages which i don't want to write in implement such as rust implement 'Edit Distance' using Levenshtein Distance

Would it be possible to implement edit distance into the TensorPimatives api ? to support calculating edit distance in .net with unequal length strings or whatever ?

I work at a large financial institution, these methods are required for a lot of things.
we are primarily a dotnet shop.

for reference https://docs.rs/edit-distance/latest/edit_distance/

API Proposal

namespace System.Numerics.Tensor;


Enum DistanceAlgorithm {
  Levenshtein,
  DamerauLevenshtein,
 // ETC
}

Public static class TensorPrimitives {

    public static int EditDistance<T>(DistanceAlgorithm , ReadOnlySpan<T> x, ReadOnlySpan<T> y);
}

API Usage

using System.Numerics.Tensor;

var  result = TensorPrimitives.EditDistance(DistanceAlgorithm.Levenshtein, SomeStringSpanA,SomeStringSpanb)

### Alternative Designs

_No response_

### Risks

_No response_

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-numerics-tensors
See info in area-owners.md if you want to be subscribed.

[huoyaoyuan]

TensorPrimitive is not the correct place for Levenshtein Distance. It requires different element of the input to be processed equally, which isn't applicable to Levenshtein Distance. It doesn't aim to provide edit distance either. Hamming Distance is there because its algorithm meets the requirement, and is low-level enough.

[stephentoub]

It requires different element of the input to be processed equally

While that's true for most if not all of what we've added thus far, I'm not sure it's a requirement. I agree having one or more edit distance metrics somewhere would be valuable, and I'm not sure we have a better place than TP.