String Distance Implementation JS / PYTHON / PHP

A set of (string) distance-messures functions written in JavaScript / Python / PHP. Every function could be called with two representations of text to compute a distance, no matter if a bag of words represenations or a ngram represenation, string represenation is used. The implementation is derived from

Elena Deza / Michel-Marie Deza "Encyclopedia of Distances", Elsevier Science, 2009 (http://www.uco.es/users/ma1fegan/Comunes/asignaturas/vision/Encyclopedia-of-distances-2009.pdf)

C´edric Villani, "Optimal transport, old and new", Springer, 2008 (http://elenaher.dinauz.org/B07D.StFlour.pdf)

Examples

http://ecomparatio.net/~khk/string-distance-master/test_strdist.php

http://ecomparatio.net/~khk/string-distance-master/test_strdist_rulesets.php

Functions

1. Weighted Levenshtein

INPUT:

• s1 and s2 as representations,
• Wv a weight for pairs in A and B,
• Ws a list of 4 weights related to the operations substitution, insertion, deletion, exchange,

RETURN: Number of edited Letters / sum of editweights,

CALL: WLEV( A, B, Wv, Ws )

2. Damerau Levenshtein

INPUT:

• a text representation s1 and s2,
• Ws a list of 4 weights related to the operations substitution, insertion, deletion, exchange,

RETURN: sum of editweights,

CALL: LEVDAM( s1, s2, Wv )

3. Levenshtein

INPUT:

• s1 and s2 text representations,
• Ws a list of 4 weights related to the operations substitution, insertion, deletion,

RETURN: number of edits,

CALL: levenshtein( s1, s2, Wv )

4. Longest Common Subsequence

NOTE: sequnece is not substring, it is like sequencial but not next to eachother,

INPUT: vecA and vecB text representations,

RETURN: 0 (distant) and max(len(A),len(B)) (not distant),

CALL: LCS( vecA, vecB )

5. Longest Common Substring

NOTE: factor, sequential and next to each other members of a vector,

INPUT: vecA and vecB text representations,

RETURN: 0 (distant, nothing in common) and max(len(A),len(B)) (not distant),

CALL: LCF( vecA, vecB )

6. containednessLCS

NOTE: according to LCS the containedness of a in b or b in a,

INPUT: a and b text representations,

RETURN: 1 (contained) and 0 (not contained),

CALL: containednessLCS( a, b )

7. containednessLCF

NOTE: according to LCF the containedness of a in b or b in a,

INPUT: a and b text representations,

RETURN: 1 (contained) and 0 (not contained),

CALL: containednessLCF( a, b )

8. Longest Commen Prefix,

INPUT: vecA and vecB text representations,

RETURN: 0 (distant) and max(len(A),len(B)) (not distant),

CALL: LCP( vecA, vecB )

9. Bag Distance

NOTE: vecA/vecB is a bag is a sequencial, and next to eachother, redundant vector, aproximation of levensthein,

INPUT: vecA and vecB text representations,

RETURN: max(len(A),len(B)) (distant) and 0 (not distant),

CALL: bagdist( vecA, vecB )

10. Jaro Distance

INPUT: vecA, vecB text represenations,

RETURN: Inf (distant) and 0.0 (not distant) (?),

CALL: JA( vecA, vecB )

11. Jaro-Winkler Distance

INPUT: vecA, vecB text represenations,

RETURN: Inf (distant) and 0.0 (not distant) (?),

CALL: JAWI( vecA, vecB )

12. Baire Distance

INPUT: vecA, vecB text represenations,

RETURN: Inf/1 (distant) and 0.0 (not distant),

CALL: baire( vecA, vecB )

13. not Baire Distance

INPUT: vecA, vecB text represenations,

RETURN: Inf/1 (distant) and 0.0 (not distant),

CALL: notbaire( vecA, vecB )

NOTE: same as baire but uses LCF

14. Gen. Cantor Distance

INPUT: vecA, vecB text represenations,

RETURN: Inf/1 (distant) and 0.0 (not distant),

CALL: generalizedcantor( vecA, vecB )

15. not Gen. Cantor Distance

INPUT: vecA, vecB text represenations,

RETURN: Inf/1 (distant) and 0.0 (not distant),

CALL: notgeneralizedcantor( vecA, vecB )

NOTE: same as generalizedcantor but uses LPC

16. JaccardZwei

NOTE: inverted Jaccard

INPUT: vecA, vecB text represenations,

RETURN: Inf/1 (distant) and 0.0 (not distant),

CALL: jaccardMASZzwei( vecA, vecB )

17. Jaccard Distance

INPUT: vecA, vecB text represenations,

RETURN: Inf/1 (distant) and 0.0 (not distant),

CALL: jaccardMASZ( vecA, vecB )

18. Cosine Distance

INPUT: vecA, vecB text represenations,

RETURN: Inf/1 (distant) and 0.0 (not distant),

CALL: cosineMASZ( vecA, vecB )

19. Quadratic Difference Distance

NOTE: vec A and B are arrays of ngrams, quadra diff is a messure taken from the haufigkeitsvektor of A and B

INPUT: vecA, vecB text represenations,

RETURN: Inf (distant) and 0.0 (not distant) (?),

CALL: quadradiffMASZ( vecA, vecB )

20. Dice Coefficent Distance

INPUT: vecA, vecB text represenations,

RETURN: Inf/1 (distant) and 0.0 (not distant),

CALL: diceMASZ( vecA, vecB )

21. Marking Distance

INPUT: vecA, vecB text represenations,

RETURN: Inf (distant) and 0.0 (not distant) (?),

CALL: markingmetric( vecA, vecB )

22. Set Difference Distance

INPUT: vecA, vecB text represenations,

RETURN: Inf (distant) and 0.0 (not distant) (?),

CALL: setdiffmetric( vecA, vecB )

Minimal Example

NOTE

PHP Version

If mbstring extension is installed, every string is treated as array. That gives better distance results than PHP levenshtein.

Python Version

Use Python3.x!

JS Version

Just tested with the latest Chrome and Forefox, not on server environment, no other interpreters tested. Drop a issue if needed.