5
$\begingroup$

Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm?

I have access to the two original papers, but they do not show the pseudocode of the actual algorithm. Also, I have seen some implementations in Java (preference), but they are part of the larger package and with a complex inheritance and composition hierarchies.

I was wondering if someone can point me to a pseudocode for the algorithm, so that I could implement it myself.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Have you attempted to translate the descriptions in the article into pseudocode? $\endgroup$
    – Raphael ♦
    Nov 1 '14 at 19:30
  • $\begingroup$ Yes, absolutely and implemented most of them. I am specifically asking for the reference on the published pseudocode I would use for my own validation or correction. $\endgroup$
    – Edmon
    Nov 6 '14 at 18:39
  • $\begingroup$ I see. Apparently nobody has one. I don't see how to make an answerable question out of your code and a correctness proof attempt, though; sorry. $\endgroup$
    – Raphael ♦
    Nov 7 '14 at 8:30
  • 2
    $\begingroup$ What research have you done? Have you read the original papers or sources where this was introduced? Can you give a citation or a reference to where this scheme was introduced/defined? $\endgroup$
    – D.W. ♦
    Dec 18 '14 at 18:28
5
$\begingroup$

Algorithm description

The input string are broken into tokens. The best matching token are compared to get the monge-elkan score.

Ex:

Input string 1: "paul johnson"

Input string 2 : "johson paule"

Score : 0.94

The algorithm uses similarity function (Example : Jaro-Winkler or Levenshtein score) as inner function. The inner function is used to compute the scores of the best matching token.

Ex: jaro_winkler("paul","johson") = 0

jaro_winkler("paul","paule") = 0.96

jaro_winkler("johnson","paule") = 0.0

jaro_winkler("johnson","johson") = 0.92

Monge_elkan = final_score = 1/2*(0.92+0.96) = 0.94

 //Python pseudocode
cummax = 0
for ws in s.split(" "):
  maxscore=0
  for wt in t.split(" "):
    maxscore = max(maxscore,j.jaro_winkler(ws,wt))  
  cummax += maxscore
score = cummax/len(s.split(" "))

You can check the implementation in secondstring and in sopremo . The implementation in sopremo is ported to Apache Flink as well.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Since links break (and there's no guarantee these projects will use this algorithm forever), this answer has little value of its own. You should at least link to the exact files in a specific revision; better yet, you could transcribe the code into pseudocode (leaving attribution, of course). $\endgroup$
    – Raphael ♦
    Jul 13 '15 at 15:16
  • $\begingroup$ Actually, simply transcribing here some key parts of those files can often help retrieve them with a search engine. $\endgroup$
    – babou
    Jul 14 '15 at 21:38
3
$\begingroup$

There are apparently several different variants of the Monge–Elkan metric. You can check out Cohen, Ravikumar and Fienberg, A comparison of string metrics for matching names and records, which describes several different metrics (not only Monge–Elkan). Many other online references also exist.

Improve this answer
$\endgroup$
2
  • $\begingroup$ the link returns 404 $\endgroup$
    – joseph
    Jun 20 '17 at 21:58
  • $\begingroup$ The paper doesn't explain the algorithm at all. $\endgroup$
    – Fabian Winkler
    Jul 16 '20 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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