Damerau-levenshtein distance Algorithm

[Jivi-this-side]

What would you like to Propose?

~ Would like to add Damerau-levenshtein distance Algorithm in Dynamic Programming folder.

Issue details

The Damerau–Levenshtein distance is a measure of the similarity between two strings, which takes into account the number of insertion, deletion, substitution, and transposition operations needed to transform one string into the other.

The Damerau–Levenshtein distance differs from the classical Levenshtein distance by including transpositions among its allowable operations in addition to the three classical single-character edit operations (insertions, deletions and substitutions) Time Complexity : O(M*N) (where M is the length of the first string and N is the length of the second one.)

Additional Information

This has a variety of uses in areas like:

~ Correction of misspelled words: The Damerau-Levenshtein distance is frequently employed in algorithms for spelling correction since it can quantify how similar a misspelled word is to a correctly spelled word in the dictionary. Following that, the algorithm may offer a list of words with tiny distances or the correct term with the least distance as potential corrections.

~ Natural language processing: The Damerau-Levenshtein distance can be employed in natural language processing tasks like text classification and language identification. For instance, the method can be used to determine how close a text is to a collection of recognized languages or categories, and then the text can be categorized according to the category with the least distance.

~ Computational biologly: The Damerau-Levenshtein distance is frequently used in computational biology to assess how similar DNA or protein sequences are to one another. Sequence alignment, mutation detection, and evolutionary link analysis can all be done using the technique.

[Jivi-this-side]

Hi, @siriak ! Is it possible to assign me this issue!

[siriak]

I think it's already implemented here https://github.com/TheAlgorithms/Java/blob/4a03f420616a6773e9a5cdc304b1681e96d945bd/src/main/java/com/thealgorithms/dynamicprogramming/LevenshteinDistance.java#L11. Isn't it the same?

[Jivi-this-side]

Nope!!.... the mentioned Java code is not an implementation of the Damerau-Levenshtein distance algorithm. The Damerau-Levenshtein distance is a modification of the Levenshtein distance that also considers transpositions (i.e., swapping two adjacent characters) as a single operation.

The provided code only considers insertions, deletions, and substitutions, but not transpositions. It is an implementation of the Levenshtein distance algorithm, not the Damerau-Levenshtein distance algorithm.

[siriak]

Ok, then please add Damerau-Levenshtein distance and we'll review it

[github-actions[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution!

[github-actions[bot]]

Please reopen this issue once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution!