Take the 2-minute tour ×

I have a number of strings that won't match exactly but should be considered equivalent. For example 'Bob' and 'Robert' or 'WWF' and 'World Wrestling Federation'.

To implement the equivalence function, I was going to put all the equivalent strings into tuples and then all the tuples into a list. Then for each input string pair, check if they both exist inside the same tuple and return true if so. Can anyone suggest a more elegant way to do this?

Thanks, Richard

EDIT: To clarify, the function could receive any two of ('Bob','Robbie','Robert','Roberto') and should return true.

share|improve this question
use a set instead of list, it is faster(maybe frozenset would be even faster.). –  utdemir Aug 3 '11 at 16:37
Do you know which one could be the short form? i.e. if s1 can be "Bob", but s2 is always "Robert", it might be quickest to look up s1 in a dictionary, and compare the value you get from that with s2. –  Thomas K Aug 3 '11 at 16:40
@Thomas K, no I don't know what the inputs will be. It could also be more than two strings that are equivalent (eg Bob, Bobby, Robert and Robbie) any two of those should return true –  richard druce Aug 3 '11 at 16:42
@utdemir - thanks, i didn't know that. –  richard druce Aug 3 '11 at 16:42
@Richard: You could map all the alternatives to one form of the name. Then a comparison will always be O(1). I think all the alternatives are either slower or take more memory for little gain. –  Thomas K Aug 3 '11 at 16:48
show 1 more comment

2 Answers

up vote 2 down vote accepted

If your list of equivalence tuples is EQUIVALENCES, you can create a dictionary mapping each string to its equivalences:

word_equivs = {}

for equiv in EQUIVALENCES:
    for word in equiv:
        word_equivs[word] = equiv

Then you can check if two strings are equivalent by seeing if they map to the same equivalence:

def equivalent(s1, s2):
    e1 = word_equivs.get(s1) 
    e2 = word_equivs.get(s2)
    if e1 and e2:
        return e1 == e2
        return s1 == s2
share|improve this answer
add comment

I would suggest using a dictionary from string to int. Then for every set of equivalent strings increment a counter variable counter may be using a

counter  = 0
d = defaultdict(int)
d["WWF"] = d["World Wrestling Federation"] = counter++;

And when you want to find out equivalence just do

if( d[s1]==d[s2] )
share|improve this answer
You'll need to tweak this: there's no ++ in Python. –  Ned Batchelder Aug 3 '11 at 16:52
There is no postincrement operator in Python. –  Cat Plus Plus Aug 3 '11 at 16:52
add comment

Your Answer


